转码野生老农刷题打卡

2022-09-27打卡

Interview 05.03        翻转数位
Link：https://leetcode.cn/problems/reverse-bits-lcci/
题解：https://gitee.com/vincentmliu/Al ... everseBitsLcci.java
耗时： 3h



笔记：
1. 判断前一位是否为0容易落到陷阱里，101010101这种情况没法解释。
2. 最长肯定是 前半段 + 后半段 + 翻转1位组成
3. 分成两个参数，cur(当前连续1，后半段），last(0之前连续1，前半段)， 每次都等于Math.max(res, last + cur + 1); 取最终最大值
4. 边界条件太多了，如果num == 0的话，逻辑右移while（num!=0） 不会执行。
        如果 num == -1的话，last + cur + 1 == 33。
        要注意这两个边界条件


时间复杂度 O(1) 最多遍历32次
空间复杂度 O(1) 只有前半段和后半段两个临时变量

2022-09-28打卡

42        接雨水
Link：https://leetcode.cn/problems/reverse-bits-lcci/
题解：https://gitee.com/vincentmliu/Al ... ppingRainWater.java
耗时： 3h



笔记：
说得明白的题解
https://leetcode.cn/problems/tra ... -duo-jie-fa-by-w-8/
1. 按行求，求每个高度有多少雨水，小于该高度且两边有大于该高度的墙时，就可以更新tmp到最终的res里面，时间复杂度O(n * max(height)), 超时了。
2. 按列求，分别要获取 （左边最高的墙，和右边最高的墙），木桶效应，取两者间较小的min。如果min大于当且列的高度，此列能接的水就是min - height[i]。如果min <= 当前列高度，此列接不了水。
每列要遍历左边 + 右边 n， 总共求n列，所以时间复杂度还是O(n²） 又超时了。
3. 重点！！！！动态规划，用两个数组 max_left[] 和 max_right[]来表示不包含i的左右最高，只需要两遍n就能求出。然后按照按列求的方式，分别计算min - height[i]; 时间复杂度O(n), 空间复杂度O(n)

4. 双指针，
对双指针的理解：两个指针接水

left从左向右遍历，right从右向左遍历；
条件一
则对left来说，leftLeftMax一定准确，leftRightMax不一定准确，因为区间（left, right）的值还没有遍历，但是leftRightMax一定 >= rightRightMax，所以只要leftLeftMax < rightRightMax时，我们不关心leftRightMax是多少了，因为它肯定比leftLeftMax大（leftLeftMax < rightRightMax < leftRightMax），我们可以直接计算出left的存水量leftLeftMax - nums[left];

条件二
对right来说，rightRightMax一定准确，rightLeftMax不一定准确，因为区间（left, right）的值还没有遍历，但是rightLeftMax一定 >= leftLeftMax，所以只要leftLeftMax >= rightRightMax时，我们不关系rightLeftMax是多少了，因为它肯定比rightRightMax大，我们可以直接计算出right的存水量rightRightMax - nums[right];

一开始两个指针在两端，假设h[left] < h[right] ，则有left ++ 直到 h[left] > h[right]。那么此时，h[left] == leftLeftMax 是遍历过程中第一个大于h[right]的，显然是遍历过程中的最大值。 然后right ++ 直到 h[right] > h[left] ，同样的，此时h[right] == rightRightMax为遍历过程中的最大值。

//首次找到leftLeftMax 或 rightRightMax的时候，对结果的贡献实际是0，关键是下一个move

假设上一轮移动的是 left 指针，有 height[0, left- 1] < height[right]，又 height[left] < height[right]，则 height[0, left] = leftLeftMax < height[right] == rightRightMax <= leftRightMax， height[left] < height[right]符合条件一
假设上一轮移动的是 right 指针，有 leftLeftMax = height[left] >= height[right + 1, n - 1]，又 height[left] >= height[right]，则 rightLeftMax >= leftLeftMax >= height[left] >= rightrightMax = height[right , n - 1]， height[left] >= height[right]符合条件二



5. 单调栈
类似于括号匹配，栈顶的高度最小，如果当前高度 < 栈顶高度，说明里面可能有积水。一直再碰到 当前高度 >= 栈顶高度的时候，可以计算积水了。计算后，当前高度变为栈顶。
计算前，栈顶高度是在不断变低的。
总体的原则就是，

当前高度小于等于栈顶高度，入栈，指针后移。

当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。

时间复杂度 O(n) 左右遍历一次
空间复杂度 O(1) 只有前半段和后半段两个临时变量

2022-09-28打卡

191        位1的个数
Link：https://leetcode.cn/problems/number-of-1-bits/
题解：https://gitee.com/vincentmliu/Al ... 1NumberOf1Bits.java
耗时： 2min



笔记：
1. 考察点就是逻辑右移>>>和算数右移>>, 逻辑右移通通左边补0，算数右移根据符号来，负数补1，正数补0
2. 如果多次调用，可以建立一个 int[Integer.Max_INT], 0直接返回0，其它的如果是0就计算，不是0就返回下标的数。

时间复杂度 O(1) 最多32次
空间复杂度 O(1) 只有一个变量保存结果

2022-09-29打卡

461        汉明距离
Link：https://leetcode.cn/problems/hamming-distance/
题解：https://gitee.com/vincentmliu/Al ... ammingDistance.java
耗时： 5min



笔记：
1. 先求x^y;
2. 记录1的个数。

时间复杂度 O(1) 最多32次
空间复杂度 O(1) 只有一个变量

2022-09-29打卡

Interview 05.06        整数转换
Link：https://leetcode.cn/problems/convert-integer-lcci/
题解：https://gitee.com/vincentmliu/Al ... ertIntegerLcci.java
耗时： 2min



笔记：
和上题一样
1. 先求x^y;
2. 记录1的个数。

时间复杂度 O(1) 最多32次
空间复杂度 O(1) 只有一个变量

2022-09-29打卡

Interview 05.07        配对交换
Link：https://leetcode.cn/problems/exchange-lcci/
题解：https://gitee.com/vincentmliu/Al ... 7_ExchangeLcci.java
耗时： 20min



笔记：
位运算还是有点不太熟练，理解题意要了些时间
1. 还是先&1，然后逻辑右移，终止条件是num!=0;这样可以求得每一位的bit值。
2. 重点是记录一下当前是奇数位还是偶数位，如果是基数odd，就左移 当前weight+1位，如果是偶数，就左移 当前weight-1 位。这样就是实现奇偶互换了。

时间复杂度 O(1) 最多32次
空间复杂度 O(1) 一个weight变量记录当前位移数目，一个sum求合计算所有位数相加的结果

2022-09-30打卡

Interview 05.01        插入
Link：https://leetcode.cn/problems/insert-into-bits-lcci/
题解：https://gitee.com/vincentmliu/Al ... rtIntoBitsLcci.java
耗时： 10min



笔记：
1. 记录Nindex，每位先右移再左移Nindex位，一直到i-1；
2. 插入M，记录Mindex的，每位右移Mindex，再左移Nindex，一直到j；
3. 最后补全j之后的。


时间复杂度 O(1) 最多32次
空间复杂度 O(1) 一个Nindex，一个Mindex，一个res

2022-09-30打卡

Interview 17.04        消失的数字
Link：https://leetcode.cn/problems/missing-number-lcci/
题解：https://gitee.com/vincentmliu/Al ... singNumberLcci.java
耗时： 10min



笔记：
哈希表：
1. 存一个boolean[n+1], 少谁谁就false，时间复杂度O(n),空间O(n)
数学：
2. 0-n求合，高斯告诉我们 sum = n*(n-1)/2， 挨个再减去数组里的数组，就是缺的那只。时间复杂度O(n),空间O(1)
位运算：
！！！我才知道
1. 按位异或 运算满足交换律和结合律，也就是 a^b^c = a^c^b
2. 按位异或 满足  x^x = 0 和 x^0=x
3. 那也就是说 按先把nums中的数字全部按位异或一遍 a^c
4. 得到的结果再从0-n异或一遍（x^x = 0）,最后少的那一个b也就是缺失的
时间复杂度O(n),空间O(1)

2022-10-01打卡

Offer 56 I        数组中数字出现的次数
Link：https://leetcode.cn/problems/shu ... ian-de-ci-shu-lcof/
题解：https://gitee.com/vincentmliu/Al ... ianDeCiShuLcof.java
耗时： 25min


笔记：
1. 因为 x^x = 0, x^0 = x;所以全部num异或一遍，最后的结果等于a^b
2. a^b二进制位为1的位置表示两者不同，一个为0，一个为1
3. 按a^b不同的某个二进制位，将nums数组分成a，b两组。每组最后全部异或一次的结果就是a和b


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

2022-10-02打卡

Offer 56 II        数组中数字出现的次数 II
Link：https://leetcode.cn/problems/shu ... -de-ci-shu-ii-lcof/
题解：https://gitee.com/vincentmliu/Al ... nDeCiShuIiLcof.java
耗时： 25min


笔记：
哈希map
1. 就创建个map，扫一遍，出现次数存起来。
2. 再遍历一遍map，谁小于3，就返回谁。
时间复杂度 O(n) 遍历两次
空间复杂度 O(n) 需要一个map来保存

位运算（我自己肯定想不出来）
1. 所有都出现过3次，之有一个出现过一次。说明32位bit 1的和%3，要么=0，要么=1；
2. 如果余数为1，就代表那是只出现过一次的数的二进制位。

时间复杂度 O(n) 遍历两次
空间复杂度 O(1) int[32] 来保存二进制位