转码野生老农刷题打卡

2022-09-08打卡

1        两数之和
Link：https://leetcode-cn.com/problems/two-sum/
题解：https://gitee.com/vincentmliu/Al ... /ID00001TwoSum.java
耗时： 20min



笔记：
1. 记下每种nums[i]的pos；
2. sort一下nums[i]
2. 双指针，一个从头a，一个从尾b，如果sum < target就 a++; 反之b--;

时间复杂度 O(3n) 记录pos n， sort n， 双指针n
空间复杂度 O(n)

2022-09-08打卡

15        三数之和
Link：https://leetcode.cn/problems/3sum/
题解：https://gitee.com/vincentmliu/Al ... D00015ThreeSum.java
耗时： 20min


笔记：
1. 前后指针控制因子大小，排序数组，大了就左移后指针，小了就右移前指针
2. 遍历n，假设指针为a，n-a 的区间通过双指针遍历获得所以和a相加等于0的组合，记录到res中。
3. 左右双指针，终止条件是 b >=c ;


时间复杂度 O(n²) 一次排序耗费NlogN(快排或者归并)，一次遍历耗费n * n ，
空间复杂度 O(1) 不算结果保存，基本是原地

2022-09-09打卡

Offer 21        调整数组顺序使奇数位于偶数前面
Link：https://leetcode.cn/problems/dia ... shu-qian-mian-lcof/
题解：https://gitee.com/vincentmliu/Al ... huQianMianLcof.java
耗时： 5min


笔记：
1. 快慢指针，类似于快排,遇到奇数就swap放前面慢指针前进，遇到偶数就跳过。


时间复杂度 O(n) 遍历
空间复杂度 O(1) 原地

2022-09-13打卡

283        移动零
Link：https://leetcode.cn/problems/move-zeroes/
题解：https://gitee.com/vincentmliu/Al ... 0283MoveZeroes.java
耗时： 5min


笔记：
1. 0不需要保证顺序，非0需要保证顺序
2. 所以遇到非0就往慢指针处交换，把0换到快指针的位置。


时间复杂度 O(n) 遍历
空间复杂度 O(1) 原地

2022-09-20打卡

剑指 Offer 48        最长不含重复字符的子字符串
Link：https://leetcode.cn/problems/zui ... i-zi-fu-chuan-lcof/
题解：https://gitee.com/vincentmliu/Al ... iZiFuChuanLcof.java
耗时： 30min



笔记：
1. 快慢指针维护一个滑动窗口，用map记录下窗口中的所有char和int位置，res结果初始化为1
2. 快指针j不断前移，碰到和[i,j)中相同的字符，先记录当前子串的长度，Math.max(res, j-i), 然后将i前移到j的lastPos + 1的位置，移动过程中删除 lastPos + 1之前的缓存map。
3. 最后在j循环到结尾之后，记录一下当前字串的长度（边界）
4. s.length == 0 return 0 (边界)

时间复杂度 O(n) j从头遍历到尾，最多while内循环再加一次n，所以总共是n
空间复杂度 O(n) 需要保存一个char和pos的对应关系

2022-09-20打卡

438        找到字符串中所有字母异位词
Link：https://leetcode.cn/problems/find-all-anagrams-in-a-string/
题解：https://gitee.com/vincentmliu/Al ... gramsInAString.java
耗时： 1h



笔记：
1. 如何判断两个词是异位词，首先用哈希保存p中所有字母的count数。如果s中截取的字串的所有字母和p中字母相同，且每种字母的count数相同。那就记录一个异位子串。
2. 快指针j不断前移，如果j-i+1 长度小于p.length, j++
大于 则 i++
等于则判断是否为异位子串，i++,j++
3. (优化)如果j遇到了非p中的字母，则i和j都滑动到j+1的位置

时间复杂度 O(n) j从头遍历到尾，最多while内循环26次
空间复杂度 O(p) 需要保存一个char和 char num的对应关系

2022-09-21打卡

76    最小覆盖子串
Link：https://leetcode.cn/problems/minimum-window-substring/
题解：https://gitee.com/vincentmliu/Al ... indowSubstring.java
耗时： 2h



笔记：
1. 首先确定覆盖子串的定义，用两个map保存s中滑动窗口子串中的字母数量和t中的子串字母数量；
2. 两个指针i和j开始滑动窗口，每次比较[i,j)中的子串是否为覆盖子串
a. 如果不是，j++, 并添加sMap中的相应计数
b. 如果是，i++， 尝试寻找最小的覆盖子串

时间复杂度 O(n) j从头遍历到尾，最多while内循环52次
空间复杂度 O(t) 需要保存一个char和 char num的对应关系

2022-09-22打卡

53        最大子数组和
Link：https://leetcode.cn/problems/maximum-subarray/
题解：https://gitee.com/vincentmliu/Al ... aximumSubarray.java
耗时： 2h



笔记：
1. DP解法：先分解子问题，子问题是：以nums[i]结尾的最大 连续 子序列和为多少
2. dp[i] 有两种可能
a. dp[i -1] <=0, 那么对dp[i]是负贡献，所以dp[i] = nums[i] ，需要另起炉灶
b. dp[i -1 ] >0 ,那么对dp[i]就是正贡献，所以dp[i] = dp[i-1] + nums[i];
3. 每次求dp[i]的过程中，需要动态计算一个Max dp值，而不是直接返回最后一个dp


时间复杂度 O(n) 从头到尾遍历一次
空间复杂度 O(1) 滚动dp[i-1]

2022-09-23打卡

121        买卖股票的最佳时机
Link：https://leetcode.cn/problems/maximum-subarray/
题解：https://gitee.com/vincentmliu/Al ... uyAndSellStock.java
耗时： 1h



笔记：
1. 题意就是要求第i天卖出，[i-0, i- (i-1)]的最大值是多少。暴力法肯定是不行的，题意越是直白，越是不能用暴力解。暴力解的时间复杂度是O（n²）
2. DP一次遍历，可以先记录 i天之前，也就是[0, i-1]的价格最低点min。最低点买入肯定利润最高。
3. 如果i <= i-1, 第i天就没有卖出的必要，只需要记录i天价格是否比min低就行Math.min(min, price[i])
4. 如果 i > i-1, i卖出就比i-1要利润高，所以记录一下第i天卖出是不是最高 Math.max(max, price[i] - min)
5. 最后返回max


时间复杂度 O(n) 从头到尾遍历一次
空间复杂度 O(1) 记录一个min和一个max

2022-09-23打卡

238        除自身以外数组的乘积
Link：https://leetcode.cn/problems/product-of-array-except-self/
题解：https://gitee.com/vincentmliu/Al ... rrayExceptSelf.java
耗时： 30min



笔记：
1. 不能用除法，O(n)复杂度。可以存不包含i的前缀积，0位就是1；不包含i的后缀积，末位就是1；
2. 求前缀积需要遍历一遍O(n)，求后缀积再遍历一遍O(n)，前缀积i * 后缀积i 再一遍O(n)。总共就是O(3n)不算answer[]，空间复杂度也是O(n)
3. 优化空间复杂度位O(1)，用answer存储前缀积，求后缀积的时候直接拿后缀积 * answer[i]


时间复杂度 O(n) 从头到尾遍历一次，从尾再返回遍历一次
空间复杂度 O(1) 保存一个后缀积