刷题
HOT100 系列
1. 两数之和
题目传送门
实现思路
思路：
1. 创建map，遍历数组
2. 求出差值，判断map中是否存在，如果存在则取出map的value和当前的index 返回。没有则进行下一步
3. 把当前数值存入map中，数值为key，索引为value
2. 两数相加
题目传送门
实现思路
思路：迭代两个链表都有值，累加大于10向下一位进1
1. 声明新链表和进位，迭代两个链表
2. 判断进位变量是否为true，对当前两个链表的数字进行累加，大于10。则进位设置为true。否则设置为false
3. 考虑最后一个元素相加后是否需要进位
3. 无重复字符的最长子串
题目传送门
实现思路
思路：a b c a b c b b ，起始位置start = 0 ， 长度 i - start + 1，更新起始位置 + 1
1. 声明起始位置，最大长度，map
2. 遍历数组，map中不存在当前数值，则更新max最大长度，i - start + 1, max
3. 存在当前数值，则更新start位置 map.get(s[i]) + 1, start
4. 寻找两个正序数组的中位数
题目传送门
5. 最长回文子串
题目传送门
实现思路
思路：双指针
1. 遍历数组，针对当前索引左右迭代，判断是否相同
2. 需要判断奇偶数
64. 最小路径和(mid)
题目传送门
实现思路
思路：
1. 两种情况向左向下移动，算出移动位置的累加和
2. 当在第一行移动，只能累加 j-1
3. 当在第一列移动，只能累加 i-1
4. 都不为 0 的时候，需要取 [i][j-1] 和 [i-1][j]两个位置最小值。进行累加
72. 编辑距离(hard)
题目传送门
76. 最小覆盖子串(hard)
题目传送门
实现思路
思路：
1. 滑动窗口+双指针
2. 用左右指针遍历字符串。
3. 当滑动窗口内不能覆盖t的字符串，右指针向右移动，扩大窗口，把右边字符加入滑动窗口
4. 当滑动窗口内字符可以覆盖t的字符串时，左指针向右移动，缩小窗口
5. 在移动左指针的时候当不满足覆盖t的字符串时，移动结束
139. 单词拆分(mid)
题目传送门
实现思路
1. s（leetcode）是否能够被wordDict([leet, code]) 拼接而成
2. 遍历字符串s， 从下标0 ~ 3的字符串可以在wordDict匹配到。继续遍历 4 ~ 7 也可以匹配到
动态规划
// l e e t c o d e
dp [false, false, false, false, false, false, false, false]
146. LRU 缓存
题目传送门
实现思路
LRU 缓存策略举例：
i. 假设缓存大小为 4，依次打开了 gitlab、力扣、微信、QQ，缓存链表为 QQ -> 微信 -> 力扣 -> gitlab；
ii. 若此时切换到了「微信」，则缓存链表更新为 微信 -> QQ -> 力扣 -> gitlab；
iii. 若此时打开了腾讯会议，因为缓存已经满 4 个 ，所以要进行缓存淘汰机制，删除链表的最后一位 「gitlab」，则缓存链表更新为 腾讯会议 -> 微信 -> QQ -> 力扣；
思路：
1. map特性：有序的。按照写入的顺序顺序输出
2. cache.keys().next().value
152. 乘积最大子数组(mid)
题目传送门
实现思路
思路：
1. 最大乘积值，遍历数组，进行累乘，取最大值
2. 存在负数，负负得正。因此需要考虑最小值
3. 记录每次的最大值及最小值。
max = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]) )
min = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]) )
169. 多数元素(easy)
题目传送门
实现思路
hashMap 思路：
1. 遍历数组，存入hash中，value为次数。
2. 遍历hashMap，取出大于n/2的数
198. 打家劫舍(mid)
题目传送门
实现思路