【669】LeetCode系列集锦

LeetCode系列001 - 两数之和

通过哈希思想可以大大缩小时间复杂度，一遍查询一遍存储，因此涉及到查找用字典就对了，只是这个想法很抽象。
新建一个反着的字典，其实字典只关注结果的 v 值，其它的就是叠加进去就行。

LeetCode系列002 - 两数相加

主要考虑链表的使用，首先就是循环读取链表，不停的切换每一个node所对应的地址，进行不停的移动
考虑进位的计算，可以通过整除和取模来实现
考虑位数增加的情况，需要单独考虑
考虑新建链表结构，需要增加链表的表头，设置为一个空的节点 ListNode()，结果是 .next
设置一个变量 tmp 来记录每一个节点的地址，从而连续下去

LeetCode系列003 - 无重复字符的最长子串

最简单的办法就是两层嵌套遍历，然后选出长度最长的
高效方法，遍历一次，在一个字符串上进行操作

LeetCode系列004 - 寻找两个正序数组的中位数

直接利用 Python3 内置函数操作了

LeetCode系列004 - 最长回文子串

Manacher (马拉车) 算法 - 知乎
算法想要高效，就需要减少一些重复的计算过程，这样就可以提高效率

代码：

# manacher算法。
def manacher(s):
    # 首先通过 # 隔开，并在两边加上 ^ 和 $
    T = '#'.join('^{}$'.format(s))
    # 初始化 P 列表，用来记录每个位置的最长回文半径
    P = [0] * len(T)
    # 初始化 半径 R 和 中心点 C 均为 0，C 与 R 是成对出现的
    R, C = 0, 0
    
    for i in range(1, len(T) - 1):
        # 这里太抽象了
        # 首先 C R 对应的就是试探出最右边的子串
        # 如果 i >= R，就说明需要正常扩展半径就是 while 语句，如果都这么做，复杂度会很大
        # 如果 i < R，分成两种情况考虑
            # 第一种：i 与 C 的映射点所对应的 半径值 P[2 * C - i] 比 R - i 小，取 小值，基本上也没法扩展了
            # 第二种：P[2 * C - i] 比 R - i 大，说明映射点 2*C-i 的半径已经超过了 C 为中点的子串范围，因此 取小值 R-i
            # 总结，就是两次都是取小的值
        if i < R:
            P[i] = min(P[2 * C - i], R - i)
        
        # 扩展半径，每次扩展 1 个步长
        while T[i+(P[i]+1)] == T[i-(P[i]+1)]:
            P[i] += 1
        
        # 最后判断是否有扩展最右边的端点，如果有，就将 R C 重新赋值
        if i + P[i] > R: 
            R = i + P[i]
            C = i 
            
    r_m = max(P)
    c_m = P.index(r_m) 
    l_m = T[c_m-r_m:c_m+r_m+1]
    
    return "".join(l_m.split("#"))

数据结构&amp算法

【669】LeetCode系列集锦

相关

标签