转码野生老农刷题打卡

2022-10-03打卡

Interview 16.01        交换数字
Link：https://leetcode.cn/problems/swap-numbers-lcci/
题解：https://gitee.com/vincentmliu/Al ... wapNumbersLcci.java
耗时： 10min


笔记：
我只能想到哈希法。。。
位运算（我自己肯定想不出来）
1. nums[0] ^= nums[1]; //此时nums[0] == nums[0] ^ nums[1]
2. nums[1] ^= nums[0]; //此时nums[1] == nums[0]; nums[0] == nums[0] ^ nums[1]
3. nums[0] ^= nums[1]; //此时nums[0] == nums[1]; nums[1] == nums[0]

时间复杂度 O(1) 三步操作
空间复杂度 O(1) 不需要中间变量

2022-10-04打卡
234        2 的幂
Link：https://leetcode.cn/problems/power-of-two/
题解：https://gitee.com/vincentmliu/Al ... 0231PowerOfTwo.java
耗时： 2min
笔记：
1. 不让循环和递归，找到唯一那个1是不好使了
2. (n & n-1) == 0
3. (n & -n) == n
时间复杂度 O(1)
空间复杂度 O(1)

2022-10-06打卡

48        旋转图像
Link：https://leetcode.cn/problems/rotate-image/
题解：https://gitee.com/vincentmliu/Al ... 048RotateImage.java
耗时： 30min


笔记：
1. 想象正方形分为4部分，就像螺旋桨一样，每一部分都要向前挪一格。所以只用一个tmp变量就能交换所有方格。
2.  int tmp = matrix[i][j];
    matrix[i][j] = matrix[n - j - 1][i];
    matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
    matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
    matrix[j][n - i - 1] = tmp;

3. 另外一种是翻转法，先左右翻转，然后再沿着左下-右上对角线翻转。用手机比划一下就明白了

时间复杂度 O(m*n)
空间复杂度 O(1)  原地

2022-10-06打卡

54        螺旋矩阵
Link：https://leetcode.cn/problems/spiral-matrix/
题解：https://gitee.com/vincentmliu/Al ... 54SpiralMatrix.java
耗时： 30min


笔记：
1. 其实就是写四个方法，右，下，左，上。向不同方向移动坐标。用一个boolean[m][n]数组来标记已经走过的路线
2. 顺序是 右 -- 下 -- 左 -- 上 -- 右。 注意边界条件。


时间复杂度 O(m*n)
空间复杂度 O(m*n) 其实不用boolean数组也行，用一个没有意义的数字来标记也是一样的。

2022-10-11打卡

Offer 22        链表中倒数第k个节点 LCOF
Link：https://leetcode.cn/problems/lia ... -kge-jie-dian-lcof/
题解：https://gitee.com/vincentmliu/Al ... KgeJieDianLcof.java
耗时： 5min



笔记：
1. 先一个指针，一个index，找到lineList的length;
2. 第二轮循环终止位置就是 length - k;
注意边界条件！ 如果index = 0， 终止条件就是 index< length - k;如果 index = 1， 终止条件就是 index = length - k;
比如
1 -> 2 -> 3
k = 1;
那么 3-1 = 2；
count初始化为0；
循环第一次之后count是1，pin指向节点1
循环第二次之后count是2， pin指向节点2
循环第三次之后count是3， pin指向节点3
此时3 不满足 3<3，所以跳出循环
返回节点3

时间复杂度 O(n) 循环两次
空间复杂度 O(1) 只要一个pin和两个index

2022-10-11打卡

25        Reverse Nodes in k-Group
Link：https://leetcode.cn/problems/reverse-nodes-in-k-group/
题解：https://gitee.com/vincentmliu/Al ... eNodesInKGroup.java
耗时： 3days



笔记：
这题简直把我绕晕了
0. 看题意，需要两个循环，一个是整条链表的大循环， 另一个是kgroup内的小循环
1. 首先大循环定义两个变量，
kLastTail：上个kGroup（after reverse）的最后一个节点，初始化为sentry node，虚拟头节点。每个kGroup reverse后会移动到kGroup的最后一个节点
kTail：本个kGroup after reverse的尾结点，reverse前就是本个kGroup的首节点。
每个K group reverse结束之后，kTail会移动到尾部，连接下一个kGroup的首节点（也就是下个kGroup reverse之后的kTail）。

2. 小循环内两个变量
kNow：最开始是本个kGroup before reverse的head，通过kNow指针去找到本个kGroup的最后一个节点。找到后，让kLastTail指向它，表明它会变为本个kGroup的新head
index：数一数当前递归了多少个节点
如果不满足k个，就直接返回null，避免链表reverse

3. 如果链表长度是k的整数倍，会导致kTail = kTail.next的时候，kTail为空。记得判断下边界条件

时间复杂度 O(n) 递一次，归一次。
空间复杂度 O(n) 栈内最坏保存所有k个节点

2022-10-12打卡

19        Remove Nth Node From End of List
Link：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
题解：https://gitee.com/vincentmliu/Al ... eFromEndOfList.java
耗时： 10min



笔记：
1. 两个指针，距离相差n。快指针指向队尾，慢指针指向倒数n的pre节点
2. 快指针到头的时候，把preLastN的next指向next.next

时间复杂度 O(n) 一次扫描
空间复杂度 O(1) 两个指针和一个index

2022-10-12打卡

160        Intersection of Two Linked Lists
Link：https://leetcode.cn/problems/intersection-of-two-linked-lists/
题解：https://gitee.com/vincentmliu/Al ... TwoLinkedLists.java
耗时： 20min



笔记：
要是空间复杂度是O(m+n)那很容易就考虑到哈希set
要是时间复杂度O(n²)也 比较好说，暴力对比就行了
但是时间复杂度O(m+n) 空间复杂度 O（1）就麻烦一点了
1. 两个链表到后面合并成一条，说明后面的节点指针都是相等的。
2. 假如A比B长， skipA肯定大于sKipB。所以从A链表的skipB+1开始对比两条链表，直到找到相等指针就OK了。

时间复杂度 O(m+n) 扫描两者长度，最后再扫描一次短的
空间复杂度 O(1) 两个指针和一个index

2022-10-12打卡

141        Linked List Cycle
Link：https://leetcode.cn/problems/linked-list-cycle/
题解：https://gitee.com/vincentmliu/Al ... inkedListCycle.java
耗时： 10min



笔记：
如果能用哈希set就比较简单，但是不满足O(1) 空间复杂度
如果用O(1)空间复杂度要这样, 没说不可以破坏结构
1. pin往前走，每个节点都翻转，指向前一个节点。如果最后能回到head节点，说明有环。如果没有回到head，最后到null了，说明没环；
2. 注意！！！ 边界条件，head==null return false;

时间复杂度 O(n) 扫描一次
空间复杂度 O(1) 一个pin指针

2022-10-13打卡

Interview 03.01        三合一
Link：https://leetcode.cn/problems/three-in-one-lcci/
题解：https://gitee.com/vincentmliu/Al ... ThreeInOneLcci.java
耗时： 10min

笔记：
1. 初始化的array size * 3
2. 三个size，动态维护，三个top指针动态维护。初始化top指针为负数（空栈）。