转码野生老农刷题打卡

2022-11-15打卡

706        设计哈希映射
Link：https://leetcode.cn/problems/design-hashmap/
题解：https://gitee.com/vincentmliu/Al ... 6DesignHashmap.java
耗时： 1min



笔记：
1. 初始化一个默认值为-1的数组，还有很多其它方式，链表。每种设计时间复杂度不一致。array才能保证大部分操作时间复杂度为1

2022-11-15打卡

146        LRU 缓存
Link：https://leetcode.cn/problems/lru-cache/
题解：https://gitee.com/vincentmliu/Al ... D00146LruCache.java
耗时： 2h



笔记：
1. 一定要细心！！！！！
2. 用一个map缓存来查找节点指针，然后用一个双向链表来实现LRU。
3. 首尾各用一个哨兵节点head和tail可以防止很多corner case

2022-11-16打卡

Interview 16.21        交换和
Link：https://leetcode.cn/problems/sum-swap-lcci/
题解：https://gitee.com/vincentmliu/Al ... 21_SumSwapLcci.java
耗时： 1h



笔记：
1. 通过题意，可以得到公式 sum1 - a1 + a2 = sum2 - a2 + a1;
2. 已知sum1 - sum2 = diff； 可以推导出 abs(a1 - a2) = diff/2;
3. 那么如果diff是奇数，一定没有整数的abs(a1 - a2)
4. 剩下的可能性就出在 两数和 的那题了 a1 + diff/2 = a2; 或者 a2 + diff/2 = a1;


时间复杂度 O(n+m) 需要循环a1 和 a2 分别求合，然后再各自循环一遍，求是否存在相加和等于 diff/2的一组元素
空间复杂度 O(N) 最差情况需要保存两边的所有元素再set中

今天为止，王争200题终于刷了一遍啦。明天开始就随机刷两题，总共刷3遍

2022-11-17
12        剑指 Offer 57 II        和为s的连续正数序列        简单       
维护一个滑动窗口，大了就左边缩小，小了就右边扩大。O（n/2）就可以完成        滑动窗口       
https://leetcode.cn/problems/he- ... ng-shu-xu-lie-lcof/

12,Interview 01.08,零矩阵,true,2022-11-17
91,141,环形链表,true,2022-11-18

1306        跳跃游戏 III        中等        DFS&BFS

2022-11-20
543        二叉树的直径        简单

Interview 03.05        栈排序        中等

2022-11-22打卡
1122. 数组的相对排序