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、递归基础知识
– 大问题可以化为更小的问题,小问题和大问题的处理方法一样
– 递归出口、递归体