2022年 3 月 7 日
今天是否学习了算法训练营内容
是
学习时长：
3h
学习了哪些题目：
1、链表基础知识
2、反转链表
3、相交链表
4、合并两个有序链表
18、滑动窗口最大值
21、K个一组反转链表
遇到的问题：
为什么 i – k 为滑动窗口的最左边？
初始i=k,这不就成deque.peekFirst() == nums[0]了，这不太明白
if(deque.peekFirst() == nums[i - k]){
deque.removeFirst();
}
思考与总结：
2、反转链表非递归写法
– 定义了两个指针pre和cur，cur指向要处理的节点，pre指向cur的前一个节点；
– 为了防止链表丢失因此需要先将cur的后一个节点保存下来；
– 翻转的动作就是将cur指向pre，即 cur.next = pre；
– 之后，将pre和cur依次后移即可，循环往复直至cur为null。
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
3、相交链表
– 两个指针不断向后移动，如果为空，就跳到另一个链表头部。
4、合并两个有序链表
– 搞一个虚拟头节点，最后只要返回这个虚拟头结点的next即可；
– 定义一个工作指针cur，初始指向虚拟头结点，由它来穿针引线；
– 因为是有序的，因此只要不断循环比较两个链表的节点，将小的用cur串起来，即cur = l1/l2.next；
– 最后把剩余的再串起来。
18、滑动窗口最大值
– 定义一个存储最大值的数组用于收集答案；
– 定义一个双端队列，就用这个双端队列来完成后续步骤，保持队列中元素从队首到队尾，元素从大到小；
– 最开始走K步成为合格的窗口，将元素加入到队尾，但要保持递减特性，因此需要将不符合的队尾元素删除，最后走完了K步之后最大值取队头元素；
– 然后开始一步步向后滑，每滑动一步，得到新进窗口的元素：
– 1. 判断队首元素是否和窗口中最左元素相等，需要将队首元素抛出
– 2. 要保持递减特性，因此需要将不符合的元素从队尾删除，和上面类似
– 3. 元素加入队尾
– 4. 将这一步得到的将队首元素放入答案数组中
21、K个一组反转链表
– 定义一个虚拟节点，最后虚拟节点的next即可；
– 定义三个指针：start表示每次要翻转链表头结点、end 表示每次要翻转的链表的尾节点、pre表示每次要翻转链表头结点的【上一个节点】，初始状态，pre = dummy; end = dummy;
– 先走K步，让end指到要翻转链表的尾部；
– 为了防止后面链表丢失，用next指针保存下来；将start、end标好；
– 翻转start到end部分；
– 将前后都连好，不断循环。
2022年 3 月 8 日
今天是否学习了算法训练营内容
否
原因：
加班
思考与总结：
1.需要不断复习
2.得摸鱼刷题，否则时间和精力不够用
2022年 3 月 9 日
今天是否学习了算法训练营内容
是
学习时长：
2h
学习了哪些题目：
12、最小栈
14、每日温度
遇到的问题：
思考与总结：
2022年 3 月 13 日
今天是否学习了算法训练营内容
是
学习时长：
3h
学习了哪些题目：
17、用栈实现队列 （ LeetCode 232 ）
19、设计循环双端队列（ LeetCode 641 ）
20、移除链表元素（ LeetCode 203 ）
22、回文链表（ LeetCode 234 ）
23、奇偶链表（ LeetCode 328 ）
24、从尾到头打印链表（ 剑指Offer 06 ）
25、链表中倒数第 k 个节点（ 剑指Offer 22 ）
遇到的问题：
思考与总结：
17、用栈实现队列 （ LeetCode 232 ）
– 用两个栈，输入栈和输出栈，来相互倒
19、设计循环双端队列（ LeetCode 641 ）
– 用数组作为底层数据结构实现双端队列
– 用front标记队头位置，rear标记队尾的下一个位置
20、移除链表元素（ LeetCode 203 ）
– 用一个虚拟头节点统一操作，cur是工作指针，pre是cur的前一个节点；
– 遍历链表找到要删除的节点，然后让pre指向cur的下一个节点。
22、回文链表（ LeetCode 234 ）
23、奇偶链表（ LeetCode 328 ）
– 定义了3个指针，odd奇数指针（工作指针），even偶数指针（工作指针），因为最后要将偶数链表串起来，所以用evenHead保存偶数链表的头结点；初始时 odd = head；even = head.next; evenHead = even;
– 从偶数链表的头节点开始向后遍历，然后将odd.next = even.next；even.next = odd.next;然后odd、even后移一步。最后将奇数工作指针odd将evenHead串起来；
– 最后返回head
24、从尾到头打印链表（ 剑指Offer 06 ）
– 利用栈，依次入栈，在依次出栈打印
25、链表中倒数第 k 个节点（ 剑指Offer 22 ）
– 利用快慢指针思想，快指针先走K步，然后快慢指针再同时移动，这样两个指针之间就相距K个距离
2022年 3 月 14 日
今天是否学习了算法训练营内容
是
学习时长：
1h
学习了哪些题目：
5、快速排序基础知识
8、剑指 Offer 40. 最小的k个数
遇到的问题：
思考与总结：
5、快速排序基础知识
– 关键就是partition方法，首尾指针相向而行。
8、剑指 Offer 40. 最小的k个数
– 利用快排思想，因为只需要返回最小的k个数，所以得到mid与k比较，就3种情况：1.相等；2.小于；3.大于。
2022年 3 月 16 日
今天是否学习了算法训练营内容
是
学习时长：
学习了哪些题目：
1、递归基础知识
2、冒泡排序基础知识
3、选择排序基础知识
4、插入排序基础知识
6、计数排序基础知识
7、归并排序
9、剑指 Offer 41. 数据流中的中位数
10、剑指 Offer 51. 数组中的逆序对
11、合并 K 个升序链表（LeetCode 23）
12、合并两个有序数组( LeetCode 88 )
13、颜色分类( LeetCode 75 )
14、部分排序 （面试题 16）
遇到的问题：
思考与总结：
1、递归基础知识
– 大问题可以化为更小的问题，小问题和大问题的处理方法一样
– 递归出口、递归体
