刷题

深度优先搜索，小蜜蜂采蜜最短路径

a = [0,1,2]
pos = [(1,1),(0,2),(-1,0)]
def dis(a,b):
    return m.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

def build_matrix(pos):
    matrix = [[0]*3 for i in range(3)]
    for i in range(3):
        matrix[i][i] = dis(pos[i], (0,0))
        for j in range(i+1,3):
            matrix[i][j] = dis(pos[i], pos[j])
            matrix[j][i] = matrix[i][j]
    return matrix

def all_per(a, matrix, s=[], ans=0, ss=[]):
    if not a:
        return None
    m = len(a)
    if m==1:
        print(s+a, ans+matrix[s[-1]][a[0]]+matrix[a[0]][a[0]])
        ss.append(s+a)
        return
    for i, e in enumerate(a):
        if m == len(matrix):
            ans = matrix[i][i]
            all_per(a[:i] + a[i+1:], matrix, s+[a[i]], ans)
        else:
            all_per(a[:i] + a[i+1:], matrix, s+[a[i]], ans+matrix[s[-1]][a[i]])
    return ss
        
matrix = build_matrix(pos)
ss = all_per([0,1,2], matrix)
        

LeetCode经典题

1. 贪心算法

455 分发糖果
376 摇摆序列
402 移掉K位数字
55 跳跃游戏
45 跳跃游戏2
452 射击气球

2. 动态规划

70 爬楼梯
198 打家劫舍
53 最大子段和
322 找零钱
120 三角形最小路径
300 最长上升子序列
64 最小路径和
174 地下城

3. 搜索

200 岛屿数量
127 单词接龙
126 单词接龙2
473 火柴棍
407 接雨水

4. 高级数据结构

208 实现Tire树
211 Tire树搜索
547 朋友圈并查集
307 线段树

5. 回溯递归分治

78 子集
90 重复子集
40 子集和
22 括号生成
51 N皇后
315 逆序数

6. 二叉树与图

113 路径之和
236 最近公共祖先
114 二叉树转链表
199 二叉树右视图
207 课程表

7. 哈希表与字符串

409 最长回文串
290 词语模式
49 字母异位
3 无重复字符最长字串
187 重复的DNA序列
76 最小窗口字串

8. 二分法，二叉搜索树

35 插入位置
34 区间查找
33 旋转数组查找
449 二叉树序列化
315 逆序数

9. 栈，队列，堆

225 用队列实现栈
232 用栈实现队列
155 最小栈
224 简单的计算器
215 数组中第K大的数
295 数据流中位数

10. 链表

206 链表逆序
92 链表逆序2
160 链表交点
142 链表环节点
86 链表划分
138 复杂链表拷贝
21 合并排序链表
23 合并多排序链表