打卡打卡

刷题学习，开贴打卡
抽取最重要的思考和当日总结

1/16/2022
TSP DFS 动态规划
把路径中的点存成二进制，利用异或操作判断是否访问过，利用二维数组记录新加入的点预算与之前每个点预算，和直接用原来路径加入新的点，进行比较，返回f[state_size - 1]最小值。时间复杂度优化到 2 ^ n * n ^ 2，指数比阶乘时间复杂度低

这个解法不记录具体路径所以降低时间复杂度（状态压缩），即点是如何连接的，但是在比较较小值中计算保留

1/14/2022
TSP DFS 剪枝优化
类似于构图，在寻找路径的时候每个点分别反转最后一个点与新点的连接大小比较的逻辑(中间点已经试过了不用再试)，可以去掉一些明显错误的路径，相较于暴力dfs的一种优化。剪枝只是剪去了当前加入点中明显错误的部分，因为还没有加入其他点所以不代表唯一最优，还是需要dfs出口的时候打擂台进行最小预算的比较

补充内容 (2022-01-16 12:24 +8:00):
时间复杂度还是n! * n = 全排列数 * 构造函数数

1/30/2022
LRU Cache
写数据结构，比较全面的数据结构操作，有插入，更新，删除，移动位置，查找，指针，类和变量
更新之后需要移动到最后，插入也需要放到最后
因为没有用双链表，所以指针需要指向前一个位置

非常有代表性的一道题，如果有cache的问题follow up或者类似题，可以再做一遍

11/6

Leetcode 5: 最长回文串  longest palindrome substring

小结
1. 回溯产生新的映射：字符 -> 循环 -> 动态规划 -> 状态dependency -> 扫法定义循环写法
2. 需要进一步理解时间复杂度和空间复杂度的原理

11/10

Leetcode 680：有效回文II Valid Palindrome II

小结

• 先归类到某一种算法，定出代码基本框架，图形记忆法，具体展开解题思路
• 然后根据函数调用关系、异常检测、排除法、判断条件来写代码
  

11/10

Leetcode 1: Two Sum

小结

• 哈希表方式：逻辑思维点主要在哈希表的查找和建立
• 哈希表方式：循环考虑的是day n的common case，所以添加在之后，起到day 1的作用
  

Two Sum - Less than or equal to target

小结：

• 双指针和排序有关联性，循环是根据比较条件进行移动的
  
  

11/11/2021

Leetcode 88: Merge Sorted Array

小结：
1. 用的quick sort做法，很多语法需要熟练

补充内容 (2021-11-15 16:17 +8:00):
*merge sort

11/21/2021

Leetcode 509: Fibonacci

递推

11/27/2021

Leetcode 704 Binary Search

二分法

11/27/2021

Leetcode 34: Last Position of Sorted Array

二分法

11/27/2021

Leetcode 852: peak index in a mountain array

二分法