Leecode 刷题归纳（Python——剑指offer）

一、数组操作

二、字符串

1） 2） ▲翻转一个数组可用a =a[::-1] ▲将一个数组（里面都是string），合并成为一个长的string，用“ ”.join(a)，其中“ ”中表示间隔用什么。 3） 要考虑的情况比较多。 4） 5） 6）

三、链表

1） 2） 3） 4） 思路有点巧妙，一开始没想出来。 5) 6) 7) 8) 在链表中，字典用dict.get(key,None)比直接dict[key]好用，因为dict[key]没有值会报错，而那个可以直接返回None。 9）

四、栈

1） ▲.pop()会默认删除最后一个；.pop(index)表示删除索引为index的那一个。 2） 3） 4） 5）

五、回溯法（dfs）

1） 2） ▲list产生矩阵的方法 self.matrix = [[0 for x in range(cols)] for y in range(rows)]。 3） 4） Hard ▲ 用set的话重复的会被删除

六、二叉树

▲知识点： 前序遍历：先遍历树的父节点，然后遍历树的左节点，然后遍历树的右节点。

def preorderTraversal(now, result=[]):
    if now == None:
        return result
    result.append(now.data)
    preorderTraversal(now.left, result)
    preorderTraversal(now.right, result)
    return result
print(preorderTraversal(binaryTree))

中序遍历：先遍历树的左节点，再遍历树的父节点，再遍历树的右节点。

def intermediateTraversal(now, result=[]):
    if now == None:
        return result
    intermediateTraversal(now.left, result)
    result.append(now.data)
    intermediateTraversal(now.right, result)
    return result
print(intermediateTraversal(binaryTree))

后序遍历：先遍历树的左节点，再遍历树的右节点，再遍历树的父节点。

def postorderTraversal(now, result=[]):
    if now == None:
        return
    postorderTraversal(now.left, result)
    postorderTraversal(now.right, result)
    result.append(now.data)
    return result
print(postorderTraversal(binaryTree))

1） 2) 3） 4) 5) ▲ 搜索树遵循右边>中间>左边 6) 7) 8) 9) 10) 11) Hard 12) 13) 14) 15） Hard 16） Hard 其实不难，就是不大熟性质。

七、动态规划

1） 2） 3） 与Ⅰ相比结果要取模（%1000000007） 4） 5） 变换一下也是一个斐波那契数列问题，即F(N) = F(N-1)+F(N-2) 6） 7） 8） 9） Hard 都要分很多情况进行讨论，可以用动态规划法和递归，动态规划速度快很多，但是比较难理解。