本文最后更新于：2 个月前

破冰

漫画：什么是红黑树？ - 掘金 (juejin.cn)

脑力激荡

链表基础

基础知识（青铜挑战）

单链表基础及构造方法

链表的内部结构

以下是我对单链表的理解：（2023/07/17午）

链表，是用来存储数据的一种数据结构，其由若干个节点依次连接而成。
一个节点就是一个数据元素，一个节点由两部分构成：数据域和指针域。
数据域存放数据元素的值，指针域存放指针，而该指针用来指向下一个节点。

链表的构造

链表的构造过程很简单：
1. 创建头节点，创建head指针指向头节点
2. 依次创建每个节点，初始化其数据域，并令前驱节点的指针域指向该节点
3. 链表创建完成，返回该链表的head指针
下面给出具体的代码实现

// 单链表节点
  static class Node {
      // 数据域
      public int val;
      // 指针域
      public Node next;
      // 节点初始化
      Node(int x) {
          val = x;
          next = null;
      }

      @Override
      public String toString() {
          return "Node{" +
                  "val=" + val +
                  ", next=" + next +
                  '}';
      }
  }

// 使用数组构建单链表
   private static Node initLinkedList(int[] array) {
       // 1.定义head指针, cur指针
       Node head = null, cur = null;
       // 2.遍历数组, 构建单链表
       for (int i = 0; i < array.length; i++) {
           // 2.1.新建节点, 依次获取数组元素, 并赋值给该节点的数据域
           Node newNode = new Node(array[i]);
           // 2.2.链表为空, 插入头节点
           if (i == 0) {
               // 2.2.1.初始化head指针
               head = newNode;
               // 2.2.2.更新cur指针, 指向新节点
               cur = newNode;
               // 2.3.链表不为空, 插入后继节点
           } else {
               // 2.3.1.更新每个结点的指针域, 指向后继节点
               cur.next = newNode;
               // 2.3.2.更新cur指针, 指向新节点
               cur = newNode;
           }
       }
       // 3.单链表构建完成, 返回头指针
       return head;
   }

// 测试
public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6};
        Node head = initLinkedList(a);
        System.out.println(head);
    }

遍历链表

打印链表：头指针依次向后移动，打印每个节点的数据域
获取链表长度：头指针依次向后移动，累加节点个数，打印链表长度
代码实现如下：（2023/07/17午）

/**
     * 打印链表
     *
     * @param head 头节点
     */
    public static String toString(Node head) {
        Node current = head;
        StringBuilder sb = new StringBuilder();
        while (current != null) {
            sb.append(current.data).append("\t");
            current = current.next;
        }
        return sb.toString();
    }

/**
    * 获取链表长度
    *
    * @param head 链表头节点
    * @return 链表长度
    */
   public static int getLength(Node head) {
       int length = 0;
       Node node = head;
       while (node != null) {
           length++;
           node = node.next;
       }
       return length;
   }

链表插入

向链表中插入节点分以下三种情况：
1. 表头插入：创建新节点，新节点指针域指向原头节点；head指针指向新节点
1. 在表中插入：遍历到插入位置的前驱节点，依次为新节点分配后继节点和前驱节点
1. 表尾插入：可视为 2 的特殊情况，新节点的后继节点为 NULL
代码设计如下：（2023/07/17午）

/**
    * 链表插入
    *
    * @param head       链表头节点
    * @param nodeInsert 待插入节点
    * @param position   待插入位置，取值从2开始
    * @return 插入后得到的链表头节点
    */
   public static Node insertNode(Node head, Node nodeInsert, int position) {
       // 1.头节点判空
       if (head == null) {
           return nodeInsert;
       }
       // 2.越界判断
       int size = getLength(head);
       if (position > size + 1 || position < 1) {
           System.out.println("位置参数越界");
           return head;
       }

       // 3.表头插入
       if (position == 1) {
           nodeInsert.next = head;
           head = nodeInsert;
           return head;
       }
       // 4.表中/表尾插入
       Node pNode = head;
       int count = 1;
       while (count < position - 1) {
           pNode = pNode.next;
           count++;
       }
       nodeInsert.next = pNode.next;
       pNode.next = nodeInsert;
       
       // 5.插入完成, 返回头节点
       return head;
   }

链表删除

删除链表节点同样分三种情况：
1. 删除表头元素：head指针指向要删除节点的后继节点
1. 删除表中元素：拿到要删除节点的前驱节点的指针域，指向要删除节点的后继节点
1. 删除表尾元素：可视为 2 的特殊情况，要删除节点的后继节点为 NULL
代码设计如下：

/**
     * 删除节点
     *
     * @param head     链表头节点
     * @param position 删除节点位置，取值从1开始
     * @return 删除后的链表头节点
     */
    public static Node deleteNode(Node head, int position) {
        // 1.头节点判空
        if (head == null) {
            return null;
        }
        // 2.越界判断
        int size = getLength(head);
        if (position > size || position <= 0) {
            System.out.println("输入的参数有误");
            return head;
        }
        // 3.表头删除
        if (position == 1) {
            // head.next就是链表的新head
            head = head.next;
            return head;
        }
        // 4.表中/表尾删除
        Node preNode = head;
        int count = 1;
        while (count < position - 1) {
            preNode = preNode.next;
            count++;
        }
        Node curNode = preNode.next;
        preNode.next = curNode.next;
        // 5.删除成功, 返回头节点
        return head;
    }

双向链表设计

双向链表的内部结构

以下是我对双向链表的理解（2023/07/17午）

1	`双向链表与单链表的最大区别，就是每个节点增加了一个前驱指针域，指向前驱节点`

链表的构造

代码设计如下：

遍历链表

head指针依次向后移动，遍历每个节点，输出数据域的值：

链表插入

向链表中插入节点分以下三种情况：
- 表头插入：新建新节点，原头节点作新节点的后继节点，新节点作为原头结点的前驱节点，head指针指向新节点
- 表尾插入：新建新节点，原尾节点作新节点的前驱节点，新节点作为头结点的后继节点，tail指针指向新节点
- 表中插入
- 代码实现如下：
1

链表删除

删除双向链表中的节点分以下三种情况：
- 表头删除：head指针指向原头节点的后继节点，并将该后继节点的前驱指针置空（2023/07/17午）
- 表尾删除：tail指针指向原尾节点的前驱节点，并将该前驱节点的后继指针置空
- 表中删除
- 代码实现如下：
1

实战训练（白银挑战）

两个链表第一个公共子节点

前情提要：什么情况下，两条链表存在公共子节点呢？如下图所示：（2023/07/19午）

显而易见，c1、c2、c3均为两链表的公共子节点，且c1是两链表的第一个公共子节点

我们先废话少说，给出四种解题思路：

哈希和集合，代码如下：

/**
     * 方法1：通过Hash辅助查找
     *
     * @param pHead1 链表a
     * @param pHead2 链表b
     * @return 第一个公共节点/null
     */
    public static ListNode findFirstCommonNodeByMap(ListNode pHead1, ListNode pHead2) {
        // 1.判断链表是否为空
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        // 2.保存两链表头节点
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        // 3.通过Hash存储链表a的所有节点
        HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
        while (current1 != null) {
            hashMap.put(current1, null);
            current1 = current1.next;
        }
        // 4.从头结点开始, 依次比较hash表中的节点与链表b的节点
        while (current2 != null) {
            if (hashMap.containsKey(current2))
                return current2;
            current2 = current2.next;
        }
        // 5.未发现公共节点
        return null;
    }

/**
     * 方法2：通过集合辅助查找
     *
     * @param headA 链表a
     * @param headB 链表b
     * @return 第一个公共节点/null
     */
    public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {
        // 1.通过Hash存储链表a的所有节点
        Set<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        // 2.从头结点开始, 依次比较hash表中的节点与链表b的节点
        while (headB != null) {
            if (set.contains(headB))
                return headB;
            headB = headB.next;
        }
        // 3.未发现公共节点
        return null;
    }

栈，代码如下：

/**
    * 方法3：通过栈
    */
   public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {
       // 1.将两条链表从头节点开始, 分别压入栈中
       Stack<ListNode> stackA = new Stack<>();
       Stack<ListNode> stackB = new Stack<>();
       while (headA != null) {
           stackA.push(headA);
           headA = headA.next;
       }
       while (headB != null) {
           stackB.push(headB);
           headB = headB.next;
       }
       // 2.两栈依次出栈, 当栈顶元素相同时, 保存该元素
       ListNode preNode = null;
       while (stackB.size() > 0 && stackA.size() > 0) {
           if (stackA.peek() == stackB.peek()) {
               preNode = stackA.pop();
               stackB.pop();
           } else {
               break;
           }
       }
       // 3.返回第一个公共节点
       return preNode;
   }

两条链表拼接，代码如下：

 /**
     * 方法4：通过序列拼接
     */
    public static ListNode findFirstCommonNodeByCombine(ListNode pHead1, ListNode pHead2) {
//        System.out.println("null == null" + (null == null));
        // 1.判断链表是否为空
        if (pHead1 == null || pHead2 == null) {
            return null;
        }

        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        // 2.依次遍历两条链表
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
            if (p1 != p2) {// 这个判断不能少
                // 2.1.链表a遍历完, 切换遍历链表b
                if (p1 == null) {
                    p1 = pHead2;
                }
                // 2.2.链表b遍历完, 切换遍历链表a
                if (p2 == null) {
                    p2 = pHead1;
                }
            }
        }
        // 3.返回第一个公共节点
        return p1;
    }

这里有必要解释一下这个判断的作用了：

1
2
3

if (p1 == null) {
	...............
}

考虑这个问题：当前链表遍历结束后，什么情况下允许切换遍历另一条链表呢？
答案包括两种情况：未找到公共节点 / 第一次切换遍历链表结束
未找到公共节点很好理解，只有切换遍历另一条链表，才能判断是否有公共节点
第一次切换遍历链表结束，此时p1、p2指针均为null，说明两链表就没有公共节点，我们就结束链表的遍历
所以结束两链表的遍历（p1 == p2）有两种情况：第一个公共节点已找到/不存在公共节点
差和双指针

/**
     * 方法5：通过差值来实现
     *
     * @param pHead1 链表a
     * @param pHead2 链表b
     * @return 
     */
    public static ListNode findFirstCommonNodeBySub(ListNode pHead1, ListNode pHead2) {
        // 1.判断链表是否为空
        if (pHead1 == null || pHead2 == null) {
            return null;
        }

        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        int l1 = 0, l2 = 0;

        // 2.分别拿到两链表的长度
        while (current1 != null) {
            current1 = current1.next;
            l1++;
        }

        while (current2 != null) {
            current2 = current2.next;
            l2++;
        }
        current1 = pHead1;
        current2 = pHead2;

        // 3.计算两链表长度之差
        int sub = l1 > l2 ? l1 - l2 : l2 - l1;

        // 4.长度较大的链表先遍历, 遍历次数即为长度之差
        if (l1 > l2) {
            int a = 0;
            while (a < sub) {
                current1 = current1.next;
                a++;
            }
        }

        if (l1 < l2) {
            int a = 0;
            while (a < sub) {
                current2 = current2.next;
                a++;
            }
        }

        // 5.同时遍历两链表
        while (current2 != current1) {
            current2 = current2.next;
            current1 = current1.next;
        }

        // 6.返回第一个公共节点
        return current1;
    }

上面代码里的注释，已经把解题思路解释的很清晰了
基于我个人的理解，下面讲解一下这些方法的共同点，也就是解题思路的形成过程：

我们的目标是：查出两条链表的第一个公共节点
公共节点是什么我们已经搞清楚了，那如何拿到第一个公共节点呢？
不论是分别正序/倒序遍历两条链表，我们的执行思路始终是：
从两链表的头节点/尾节点开始，分别依次向后遍历链表的每个节点，再比较两节点，判断它们是否相同，即是否为两链表的公共节点
我们能够判断出两链表的公共节点，那么第一个公共节点就好找了：
如果遍历顺序为正序，则选出第一组公共节点；如果遍历顺序为倒序，则选出最后一组公共节点
只需要根据正序/倒序遍历链表，选出第一组公共节点/最后一组公共节点，就找到了两链表的第一个公共节点
这里问题来了，我们要明确一点，即两链表的长度不一定相同
这就带来了问题：
我们上面查找两链表公共节点的思路，其实只有在两链表长度相同时，才行得通
那我们的目标就是，如何构造出两链表长度相同的环境：
哈希和集合：直接消除了链表长度带来的影响，通过开辟了新的空间，判断节点是否相等，进而查找出两链表的公共节点
栈、两链表拼接、差和双指针：本质上都是构造出两链表长度相同的环境，进而查找出两链表的公共节点

这就是查找两链表的第一个公共节点的解题思路了，希望对你有帮助

回文链表的判断

给出一个链表，判断其是否为回文链表，那什么是回文链表？
以下即为一条回文链表：

即对回文链表正序遍历和倒序遍历，得到的结果是一样的

这种题解法很多，我们列举常见的、简单的且容易理解的解法：

压栈法，具体代码如下：

/**
     * 方法1：全部压栈遍历 全部出栈遍历
     *
     * @param head
     * @return
     */
    public static boolean isPalindromeByAllStack(ListNode head) {
        ListNode temp = head;
        Stack<Integer> stack = new Stack<>();
        // 1.压栈 遍历
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
        }
        // 2.出栈 遍历
        while (head != null) {
            if (head.val != stack.pop()) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

/**
     * 方法2：全部压栈遍历 一半出栈遍历
     *
     * @param head
     * @return
     */
    public static boolean isPalindromeByHalfStack(ListNode head) {
        if (head == null)
            return true;
        ListNode temp = head;
        Stack<Integer> stack = new Stack<>();
        //链表的长度
        int len = 0;
        //把链表节点的值存放到栈中
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
            len++;
        }
        //len长度除以2
        len >>= 1;
        //然后再出栈
        while (len-- >= 0) {
            if (head.val != stack.pop())
                return false;
            head = head.next;
        }
        return true;
    }

倒序链表法，代码如下：
根据原链表构造一条倒序链表，遍历这两条链表

/**
     * 构造倒序链表
     *
     * @param head
     * @return
     */
    public static boolean isPalindromeByReverseList(ListNode head) {
        // 1.构造反转链表
        ListNode newHead = head, temp = head;

        while (temp != null) {
            ListNode node = new ListNode(temp.val);
            node.next = newHead;

            newHead = node;
            temp = temp.next;
        }

        // 2.同时遍历两链表
        while (newHead != null && head != null) {
            if (head.val != newHead.val)
                return false;

            head = head.next;
            newHead = newHead.next;
        }

        return true;
    }

此外还有双指针法（之后双指针专题练习结束后回来补充）、递归法（不推荐掌握，容易绕晕）

合并两条有序链表

常见的解法就是构造第三条链表，然后依次遍历两条有序链表，比较各节点大小，依次连接到新链表中，整个过程如下图所示：

由于两条链表长度不一定相同，可能出现一条链表遍历完，另一条链表还没有的情况，这其实是一个优化点
具体代码如下：

/**
     * 方法1：面试时就能写出来的方法
     *
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // write code here
        ListNode newHead = new ListNode(-1);
        ListNode res = newHead;
        while (list1 != null || list2 != null) {
			
            if (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    newHead.next = list1;
                    list1 = list1.next;
                } else if (list1.val > list2.val) {
                    newHead.next = list2;
                    list2 = list2.next;
                } else { //相等的情况，分别接两个链
                    newHead.next = list2;
                    list2 = list2.next;
                    newHead = newHead.next;
                    newHead.next = list1;
                    list1 = list1.next;
                }
                newHead = newHead.next;
            } else if (list1 != null && list2 == null) {
                newHead.next = list1;
                list1 = list1.next;
                newHead = newHead.next;
            } else if (list1 == null && list2 != null) {
                newHead.next = list2;
                list2 = list2.next;
                newHead = newHead.next;
            }
        }
        return res.next;
    }

上面的解法当中，我们把两条链表是否都为空/只有一条为空放在了一个循环下，这次我们把它拆开来：

/**
    * 思路更清晰的写法
    *
    * @param list1
    * @param list2
    * @return
    */
   public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
       // write code here
       ListNode newHead = new ListNode(-1);
       ListNode res = newHead;
       // 1.两链表均不为空
       while (list1 != null && list2 != null) {

           if (list1.val < list2.val) {
               newHead.next = list1;
               list1 = list1.next;
           } else if (list1.val > list2.val) {
               newHead.next = list2;
               list2 = list2.next;
           } else { //相等的情况，分别接两个链
               newHead.next = list2;
               list2 = list2.next;
               newHead = newHead.next;
               newHead.next = list1;
               list1 = list1.next;
           }
           newHead = newHead.next;

       }
       // 2.链表a为空
       while (list1 != null) {
           newHead.next = list1;
           list1 = list1.next;
           newHead = newHead.next;
       }
       // 3.链表b为空
       while (list2 != null) {
           newHead.next = list2;
           list2 = list2.next;
           newHead = newHead.next;
       }

       return res.next;
   }

思路更加清晰了，不过还有优化点：

一条链表合合并完成后，直接拼接剩余的另一条链表即可（2023/10/09晚）

/**
    * 方法2：比方法1更加精简的实现方法
    *
    * @param l1
    * @param l2
    * @return
    */
   public static ListNode mergeTwoListsMoreSimple(ListNode l1, ListNode l2) {
       ListNode prehead = new ListNode(-1);
       ListNode prev = prehead;
       // 节点之间的比较，简化为两种情况
       while (l1 != null && l2 != null) {
           if (l1.val <= l2.val) {
               prev.next = l1;
               l1 = l1.next;
           } else {
               prev.next = l2;
               l2 = l2.next;
           }
           prev = prev.next;
       }

       // 一条链表合并完成，直接拼接剩余链表的节点即可
       prev.next = l1 == null ? l2 : l1;
       return prehead.next;
   }

合并K个链表

这个更简单了，上代码：

每次两条链表合成完毕后，返回新链表的头节点，再用这条列表，继续与剩余列表合成（2023/10/09晚）

/**
    * 合并K个链表
    *
    * @param lists
    * @return
    */
   public static ListNode mergeKLists(ListNode[] lists) {
       ListNode res = null;
       for (ListNode list : lists) {
           res = mergeTwoListsMoreSimple(res, list);
       }
       return res;
   }

简单的合并链表

随便给你两条链表，你会怎么连接这两条链表？（比如：将链表b连接到链表a后面）
正确的思路只有一个，那就是拿到链表a的尾节点，拿到链表b的头节点，作：a.next = b，连接完成
举个例子：将链表a的[a，b]区间删掉，把链表b连接进去，代码如下：

/**
     * 简单的合并链表
     *
     * @param listA
     * @param a
     * @param b
     * @param listB
     * @return
     */
    public static ListNode mergeInBetween(ListNode listA, int a, int b, ListNode listB) {
        ListNode preA = listA;
        ListNode postA = listA;
        ListNode postB = listB;

        int i = 0, j = 0;

        while (postA != null && preA != null && j < b) {
            // 1.拿到listA的前半段preA的尾节点
            if (i < a - 1) {
                preA = preA.next;
                i++;
            }

            // 2.拿到listA的后半段postA的头节点
            if (j != b) {
                postA = postA.next;
                j++;
            }
        }

        // 3.分别连接preA与listB, postA与listB
        while (postB.next != null) {
            postB = postB.next;
        }

        preA.next = listB;
        postB.next = postA;

        return preA;
    }

双指针

定义快慢指针（slow、fast）

寻找中间节点

快慢指针均指向头节点
快指针一次跳俩步，慢指针一次跳一步，两指针同时移动
当快指针指向节点为空（偶数个节点）或快指针指向节点的后继节点为空（奇数个节点）时，两指针停止移动
此时，慢指针指向链表中间节点

具体代码如下：

/**
     * 寻找中间节点
     * @param head
     * @return
     */
    public static ListNode middleNode(ListNode head) {
        // 1.快慢指针
        ListNode slow = head, fast = head;
        // 2.快指针指向尾节点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 3.返回中间节点
        return slow;
    }

寻找倒数第K个节点

快慢指针均指向头节点
快指针跳到第K+1个节点，此时慢指针与快指针相距K个节点
快慢指针同时移动，当快指针指向链表末端（即空节点）时，两指针停止移动
此时，慢指针指向链表的倒数第K个节点

具体代码如下：

/**
    * 寻找倒数第K个节点
    * @param head
    * @param k
    * @return
    */
   public static ListNode getKthFromEnd(ListNode head, int k) {
       // 1.快慢指针
       ListNode fast = head;
       ListNode slow = head;
       // 2.快指针指向 K+1
       while (fast != null && k > 0) {
           fast = fast.next;
           k--;
       }
       // 3.快指针指向链表末
       while (fast != null) {
           fast = fast.next;
           slow = slow.next;
       }
       // 4.返回倒数第K节点
       return slow;
   }

寻找倒数第 K 个节点还有两种方法：遍历链表法和压栈法
遍历链表：先遍历一遍链表，得到链表长度 L，再遍历一遍链表，取第 L-K+1个节点
压栈：将链表压入栈，再出栈，取第 K 个出栈的节点
这两种方法很好理解，具体代码择日实现（2023/07/24晚）

旋转链表

常见的情景题：把链表的每个节点，都向右移动K个位置
这个是有两种思路的：反转链表、转化为寻找倒数第 K-1 个节点
反转链表暂且不表，这里可以看看第二种方法：转化为寻找倒数第 K-1 个节点
把链表的每个节点，都向右移动K个位置 => 把链表的后 K 个节点，都旋转成前 K 个节点
那就把问题转换成了：转化为寻找倒数第 K-1 个节点：
此时慢指针指向了倒数第 K-1 个节点，快指针指向了链表的尾节点
倒数第 K 个节点为头节点（断掉慢指针指向节点的后继，快指针指向原头节点）

具体代码如下：

/**
    * 旋转链表
    *
    * @param head
    * @param k
    * @return
    */
   public static ListNode rotateRight(ListNode head, int k) {
       if (head == null || k == 0) {
           return head;
       }
       // 1.快慢节点
       ListNode temp = head;
       ListNode fast = head;
       ListNode slow = head;
       // 2.获取链表长度
       int len = 0;
       while (head != null) {
           head = head.next;
           len++;
       }
       // 3.以首尾旋转
       if (k % len == 0) {
           return temp;
       }
       // 4.快指针先走K步
       while ((k % len) > 0) {
           k--;
           fast = fast.next;
       }
       // 5.快慢指针同时走
       while (fast.next != null) {
           fast = fast.next;
           slow = slow.next;
       }
       // 6.获得截断处
       ListNode res = slow.next;
       slow.next = null;
       // 7.重置头节点
       fast.next = temp;
       return res;
   }

删除特定节点

这类型题目本身不难，因为我们之前学过删除节点，但删除节点有两种情况：删除头节点和删除尾节点
这两种情况的处理方式是不一样的，所以我们提供一个全新的思路：
- 创建虚拟头节点，消除被删节点可能为头节点的情况

具体代码如下：

/**
    * 删除特定值的结点
    *
    * @param head
    * @param val
    * @return
    */
   public static ListNode removeElements(ListNode head, int val) {
       // 虚拟头节点
       ListNode dummyHead = new ListNode(0);
       dummyHead.next = head;
       // 向后遍历，删除指定节点
       ListNode temp = dummyHead;
       while (temp.next != null) {
           if (temp.next.val == val) {
               temp.next = temp.next.next;
           } else {
               temp = temp.next;
           }
       }
       // 返回头节点
       return dummyHead.next;
   }

删除倒数第K个节点

我们之前学过如何查找倒数第K个节点，它们本质上是一样的，我们还是提供三种思路：
- 遍历链表法
- 压栈法
- 双指针法
具体代码如下：

/**
    * 方法1：遍历链表法
    *
    * @param head
    * @param n
    * @return
    */
   public static ListNode removeNthFromEndByLength(ListNode head, int n) {
       // 虚拟头节点
       ListNode dummy = new ListNode(0);
       dummy.next = head;
       // 获取链表长度
       int length = getLength(head);
       ListNode cur = dummy;
       // 删除第L-n+1个节点
       for (int i = 1; i < length - n + 1; ++i) {
           cur = cur.next;
       }
       cur.next = cur.next.next;
       // 返回头节点
       return dummy.next;
   }

/**
   * 方法2：压栈法
   *
   * @param head
   * @param n
   * @return
   */
  public static ListNode removeNthFromEndByStack(ListNode head, int n) {
      // 虚拟头节点
      ListNode dummy = new ListNode(0);
      dummy.next = head;
      // 栈
      Deque<ListNode> stack = new LinkedList<ListNode>();
      // 全部压入栈
      ListNode cur = dummy;
      while (cur != null) {
          stack.push(cur);
          cur = cur.next;
      }
      // 依次出栈，删除第n个节点
      for (int i = 0; i < n; ++i) {
          stack.pop();
      }
      ListNode prev = stack.peek();
      assert prev != null;
      prev.next = prev.next.next;
      // 返回头节点
      return dummy.next;
  }

/**
    * 方法3：双指针法
    *
    * @param head
    * @param n
    * @return
    */
   public static ListNode removeNthFromEndByTwoPoints(ListNode head, int n) {
       // 虚拟头节点
       ListNode dummy = new ListNode(0);
       dummy.next = head;
       // 快慢指针
       ListNode first = head;
       ListNode second = dummy;
       // 快指针先走n步
       for (int i = 0; i < n; ++i) {
           first = first.next;
       }
       // 快慢指针同时走
       while (first != null) {
           first = first.next;
           second = second.next;
       }
       // 删除节点
       assert second.next != null;
       second.next = second.next.next;
       return dummy.next;
   }

删除重复节点

删除重复节点当然有两种情况了：仅留一个或者删除全部，废话少说，直接上代码：
- 重复元素保留一个，在这种情况下，被删除的节点肯定不可能是头节点（头节点删除时的处理是不一样的）2023/11/03晚
- 所以此处不用考虑删除节点是头节点还是中间节点了

/**
     * 重复元素保留一个
     *
     * @param head
     * @return
     */
    public static ListNode deleteDuplicate(ListNode head) {
        if (head == null) {
            return head;
        }
        // 删除重复元素
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        // 返回头节点
        return head;
    }

/**
     * 重复元素都不要
     *
     * @param head
     * @return
     */
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        
        //虚拟节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        // 找到重复元素
        while (cur.next != null && cur.next.next != null) {
            // 删除所有重复元素
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        // 返回头节点
        return dummy.next;
    }

通关（过关挑战）

题目内容：
算法训练营开课了，小伙伴们踊跃报名，请用链表来帮忙统计学员信息：
学院方向不同：Java、Python、C++，仅有一条链表，其前中后三部分，分别是：Java、Python、C++的同学
每种语言都会不断有学生进来，每次都要将对应的同学插入到对应的段的末尾
具体代码如下：（2023/07/27早）

/**
 * @author 邓哈哈
 * 2023/7/27 9:17
 * Function:
 * Version 1.0
 */

public class InsertStudent {
    public static void main(String[] args) {
        ListNode node1 = new ListNode("Node 1", "Java");
        ListNode node2 = new ListNode("Node 2", "Python");
        ListNode node3 = new ListNode("Node 3", "C++");
        // 创建节点数组并存储节点
        ListNode[] nodes = new ListNode[3];
        nodes[0] = node1;
        nodes[1] = node2;
        nodes[2] = node3;
        // 初始化链表
        ListNode head = initLinkList(nodes);

        ListNode node4 = new ListNode("Node 4", "Java");
        ListNode node5 = new ListNode("Node 5", "C++");
        ListNode node6 = new ListNode("Node 6", "Python");
        ListNode node8 = new ListNode("Node 8", "C++");
        ListNode node9 = new ListNode("Node 9", "Python");
        ListNode node7 = new ListNode("Node 7", "Java");
        // 插入学生节点
        insertStudentByLanguage(node4, head);
        insertStudentByLanguage(node5, head);
        insertStudentByLanguage(node6, head);
        insertStudentByLanguage(node7, head);
        insertStudentByLanguage(node8, head);
        insertStudentByLanguage(node9, head);

        printLinkList(head);
    }
    // 插入学生节点
    public static void insertStudentByLanguage(ListNode node, ListNode head) {
        ListNode cur = head;
        String language = node.language;

        switch (language) {
            case "Java":
                while (!cur.next.language.equals("Python")) {
                    cur = cur.next;
                }
                node.next = cur.next;
                cur.next = node;
                break;
            case "Python":
                while (!cur.next.language.equals("C++")) {
                    cur = cur.next;
                }
                node.next = cur.next;
                cur.next = node;
                break;
            case "C++":
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = node;
                break;
            default:
                break;
        }
    }
    // 打印链表
    public static void printLinkList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.println(temp + "--> ");
            temp = temp.next;
        }
    }
    // 初始化链表
    public static ListNode initLinkList(ListNode[] array) {
        int i = 0;
        ListNode head = null, cur = null;
        while (i < array.length) {
            ListNode newNode = new ListNode(array[i].name, array[i].language);

            if (head == null) {
                head = newNode;
                cur = head;
            } else {
                cur.next = newNode;
                cur = newNode;
            }
            i++;
        }
        return head;
    }

    // 节点结构
    static class ListNode {
        public String name;
        public String language;
        public ListNode next;
        public ListNode(String name, String language) {
            this.name = name;
            this.language = language;
        }
        @Override
        public String toString() {
            return "ListNode{" +
                    "name='" + name + '\'' +
                    ", language='" + language + '\'' +
                    '}';
        }
    }
}

反转链表

基础知识 + 基本操作（青铜挑战）

什么是链表反转呢？如图所示：

常见的链表反转的方法：虚拟头节点、直接反转、递归
虚拟头节点，具体代码如下：

/**
   * 方法1：虚拟头结点
   *
   * @param head
   * @return
   */
  public static ListNode reverseListByDummyNotCreate(ListNode head) {
      ListNode ans = new ListNode(-1);
      ListNode cur = head;
      while (cur != null) {
          ListNode next = cur.next;
          cur.next = ans.next;
          ans.next = cur;
          cur = next;
      }
      return ans.next;
  }

如图所示：

直接反转，具体代码如下：

/**
    * 方法2：直接反转
    *
    * @param head
    * @return
    */
   public static ListNode reverseListSimple(ListNode head) {
       ListNode prev = null;
       ListNode curr = head;
       while (curr != null) {
           ListNode next = curr.next;
           curr.next = prev;
           prev = curr;
           curr = next;
       }
       return prev;
   }

如图所示：（2023/07/28午）

拓展训练（白银挑战）

区间反转链表

给定一个区间，反转区间内的链表：
头插法：

/**
     * 方法1：头插法
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public static ListNode reverseBetween2(ListNode head, int left, int right) {
        // 1.定义虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        // 2.pre到达left前一节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 3.cur指向left
        ListNode cur = pre.next;
        ListNode next;
        // 4.反转链表
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        // 5.返回头节点
        return dummyNode.next;
    }

穿针引线法：（2023/07/31午）

/**
    * 方法1：穿针引线法
    *
    * @param head
    * @param left
    * @param right
    * @return
    */
   public static ListNode reverseBetween(ListNode head, int left, int right) {
       // 1.定义头节点
       ListNode dummyNode = new ListNode(-1);
       dummyNode.next = head;

       ListNode pre = dummyNode;
       // 2.pre来到left - 1个节点处，记录
       for (int i = 0; i < left - 1; i++) {
           pre = pre.next;
       }

       // 3.pre来到right节点处，记录
       ListNode rightNode = pre;
       for (int i = 0; i < right - left + 1; i++) {
           rightNode = rightNode.next;
       }

       // 4.截断链表
       ListNode leftNode = pre.next;
       ListNode succ = rightNode.next;

       pre.next = null;
       rightNode.next = null;

       // 5.反转链表
       reverseList(leftNode);

       // 6.拼接链表
       pre.next = rightNode;
       leftNode.next = succ;
       
       return dummyNode.next;
   }

两两交换链表中的节点

这是什么操作呢，如下：

这就是区间反转链表的拓展了，无非是区间长度固定为2，一次性反转多个区间
具体代码如下：

/**
 * 两两反转
 *
 * @param head
 * @return
 */
public static ListNode swapPairs(ListNode head) {
    // 1.虚拟头节点
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode cur = dummyHead;
    while (cur.next != null && cur.next.next != null) {
        // 2.拿取反转两节点
        ListNode node1 = cur.next;
        ListNode node2 = cur.next.next;
        // 3.两两反转
        cur.next = node2;
        node1.next = node2.next;
        node2.next = node1;
        cur = node1;
    }
    // 4.返回头节点
    return dummyHead.next;
}

链表相加

链表相加，操作如下：

输入：1 -> 3 -> 6      输出：4 -> 1 -> 3
     2 -> 7 -> 7

即：136 + 277 = 413

即将链表的数据域相连，当作数字进行相加操作，从低位开始相加，涉及到进位，有两种实现思路：
- 压栈
- 反转链表
具体代码如下：

/**
     * 压栈
     *
     * @param head1
     * @param head2
     * @return
     */
    public static ListNode addInListByStack(ListNode head1, ListNode head2) {
        // 1.两链表全入栈
        Stack<ListNode> st1 = new Stack<ListNode>();
        Stack<ListNode> st2 = new Stack<ListNode>();
        while (head1 != null) {
            st1.push(head1);
            head1 = head1.next;
        }
        while (head2 != null) {
            st2.push(head2);
            head2 = head2.next;
        }
        
        // 2.定义进位、虚拟头节点
        ListNode dummy = new ListNode(-1);
        int carry = 0;

        //这里设置carry!=0,是因为当st1,st2都遍历完时，如果carry=0,就不需要进入循环了
        while (!st1.empty() || !st2.empty() || carry != 0) {
            // 1.出栈, 相加
            ListNode a = new ListNode(0);
            ListNode b = new ListNode(0);
            if (!st1.empty()) {
                a = st1.pop();
            }
            if (!st2.empty()) {
                b = st2.pop();
            }
            int get_sum = a.val + b.val + carry;
            // 2.取余数，取进位
            int ans = get_sum % 10;
            carry = get_sum / 10;
            // 3.链表链接
            ListNode cur = new ListNode(ans);
            cur.next = dummy.next;
            dummy.next = cur;
        }
        
        // 4.返回头节点
        return dummy.next;
    }

/**
     * 方法2：链表反转
     *
     * @param head1
     * @param head2
     * @return
     */
    public static ListNode addInListByReverse(ListNode head1, ListNode head2) {
        // 1.分别反转链表
        head1 = reverse(head1);
        head2 = reverse(head2);
        // 2.定义进位、虚拟头节点
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        int carry = 0;

        while (head1 != null || head2 != null) {
            // 3.链表相加
            int val = carry;
            if (head1 != null) {
                val += head1.val;
                head1 = head1.next;
            }
            if (head2 != null) {
                val += head2.val;
                head2 = head2.next;
            }
            // 4.取进位、求余
            cur.next = new ListNode(val % 10);
            carry = val / 10;
            cur = cur.next;
        }
        // 5.进位处理
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }
        // 6.返回头节点
        return reverse(head.next);
    }

奇怪的力扣试题（链表相加）

妈的，今晚再提交一道题就完成任务了，我还选择了这道题，原以为会很顺利（2023/11/10晚）

🍖 力扣原题链接：2. 两数相加 - 力扣（LeetCode）

逼着我认真分析了一遍构造链表的几种方法，捋了捋链表节点插入的各种场景（直接插入 / 虚拟头节点，前插 / 后插）
没有解决问题，最后发现题目要求是这样的：

它怎么是这样的？难道不是这样的吗：

妈的，什么破题，今晚不搞这道题了 🍟（2023/11/10晚）

单链表加一

单链表加一，操作如下：

1 2	`输入：1 -> 3 -> 6 输出：1 -> 3 -> 7`

本质上就是链表相加，只不过另外一条链表只有一个节点，从低位开始加一，涉及到进位，同样有两种实现思路：
- 压栈
- 反转链表
这里仅展示压栈法，具体代码如下：（2023/07/31晚）

/**
     * 压栈
     *
     * @param head
     * @return
     */
    public static ListNode plusOne(ListNode head) {
        // 1.全部压栈
        Stack<Integer> st = new Stack();
        while (head != null) {
            st.push(head.val);
            head = head.next;
        }
        // 2.定义进位、加数、虚拟头节点
        int carry = 0;
        int adder = 1;
        ListNode dummy = new ListNode(0);

        while (!st.empty() || adder != 0 || carry > 0) {
            // 4.执行加法运算
            int digit = st.pop();
            int sum = digit + adder + carry;
            // 5.保存进位和各位结果
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum - 10 : sum;
            ListNode cur = new ListNode(sum);
            // 6.链表链接
            cur.next = dummy.next;
            dummy.next = cur;
            adder = 0;
        }
        // 7.返回头节点
        return dummy.next;
    }

通关（过关挑战）

数组

基础知识（青铜挑战）

有关线性表的内容，这里不过多介绍，详情可看讲义（2023/08/09早）
数组的基本操作：
- 数组的创建和初始化
- 元素查询
- 插入元素
- 删除元素
初始化数组：

/**
  * 初始化数组
  */
 public static void initArray() {
     int[] arr = new int[10];
     int[] arr2 = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
     int[] arr3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 }

元素查询很常见，展示一下最简单的查询方式：

/**
     * 查询单个元素
     *
     * @param arr     数组
     * @param size    元素数量
     * @param element 查询元素
     * @return element
     */
    public static int findByElement(int[] arr, int size, int element) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == element)
                return element;
        }
        return -1;
    }

插入元素：

/***
 * 插入数据
 * @param arr 数组
 * @param size 元素个数
 * @param element 插入元素
 * @return 下标
 */
public static int addByElementSequence(int[] arr, int size, int element) {
    // 1.
    if (size >= arr.length)
        return -1;

    // 2.默认插入元素在数组末
    int index = size;
    // 3.查找插入位置
    for (int i = 0; i < size; i++) {
        if (element < arr[i]) {
            index = i;
            break;
        }
    }
    // 4.元素后移
    for (int j = size; j > index; j--) {
        arr[j] = arr[j - 1];
    }
    arr[index] = element;
    return 0;
}

删除元素：（2023/08/09早）

/**
     * 删除元素
     *
     * @param arr  数组
     * @param size 数组元素个数
     * @param key  删除的下标
     * @return size
     */
    public static int removeByElement(int[] arr, int size, int key) {
        // 1.锁定删除元素下标
        int index = -1;
        for (int i = 0; i < size; i++) {
            if (arr[i] == key) {
                index = i;
                break;
            }
        }

        if (index != -1) {
            // 2.删除元素
            for (int i = index + 1; i < size; i++) {
                arr[i - 1] = arr[i];
            }
            // 3.更新数组元素个数
            size--;
        }
        return size;
    }

单调数组问题

数组单调有两种情况：单调递增、单调递减
如何判断数组是否为单调数组呢？（2023/08/11早）

/**
   * 第一种方法，两次遍历确定，第一次确定是否递增 ，第二次
   *
   * @param nums
   * @return
   */
  public static boolean isMonotonic(int[] nums) {
      // 递增或递减
      return isSorted(nums, true) || isSorted(nums, false);
  }

  public static boolean isSorted(int[] nums, boolean increasing) {
      int n = nums.length;
      for (int i = 0; i < n - 1; ++i) {
          // 1.递增
          if (increasing) {
              if (nums[i] > nums[i + 1]) {
                  return false;
              }
              // 2.递减
          } else {
              if (nums[i] < nums[i + 1]) {
                  return false;
              }
          }
      }
      return true;
  }

/**
 * 第二种方式，一次遍历确定
 * 如果是递增的就一定不能出现递减的相邻元素，
 * 如果出现递减的就一定不能出现递增的相邻元素。
 *
 * @param nums
 * @return
 */
public static boolean isMonotonic_2(int[] nums) {
    boolean inc = true, dec = true;
    int n = nums.length;
    for (int i = 0; i < n - 1; ++i) {
        // 1.递增
        if (nums[i] > nums[i + 1]) {
            inc = false;
        }
        // 2.递减
        if (nums[i] < nums[i + 1]) {
            dec = false;
        }
    }
    return inc || dec;
}

简单的二分查找

在单调数组中查找目标元素，最便捷的方法就是二分查找：（2023/08/11早）

/**  
 * 二分查找  
 *  
 * @param nums 排序好的数组  
 * @param target 目标数字  
 * @return 如果找到目标数字，则返回其下标；否则返回-1  
 */  
public static int search(int[] nums, int target) {  
    int n = nums.length;  
    if (n == 0) {  
        return -1; // 如果数组为空，直接返回-1  
    }  
      
    // 左边界, 右边界  
    int left = 0, right = n - 1;   
      
    while (left <= right) {  
        // 中点  
        int mid = left + (right - left) / 2; // 防止left和right过大时相加导致溢出  
          
        if (nums[mid] == target) {  
            return mid; // 如果找到目标值，直接返回其下标  
        } else if (nums[mid] < target) {  
            left = mid + 1; // 如果目标值大于mid对应的值，则在右半部分继续查找  
        } else {  
            right = mid - 1; // 如果目标值小于mid对应的值，则在左半部分继续查找  
        }  
    }  
      
    return -1; // 没有找到目标值，返回-1  
}

数组合并

我们讨论单调数组的合并：两单调数组合并之后，结果仍然是单调数组
这样的数组合并有很多种方法：
- 新数组：创建一个新数组，依次比较两数组元素大小，存放
- 不新建数组
我们仅展示第二种做法：

/**
 * 方法1：先合并再排序实现排序
 *
 * @param nums1 第一个数组
 * @param nums1_len 第一个数组的长度
 * @param nums2  第二个数组，将nums2合并到nums1中
 * @param nums2_len 第二个数组的长度
 */
public static void merge1(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {
    for (int i = 0; i < nums2_len; ++i) {
        nums1[nums1_len + i] = nums2[i];
    }
    Arrays.sort(nums1);
}

/**
    * 方法2：两个数组从后向前逐步合并
    *
    * @param nums1
    * @param nums1_len
    * @param nums2
    * @param nums2_len
    */
   public static void merge2(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {
       int i = nums1_len + nums2_len - 1;
       int len1 = nums1_len - 1, len2 = nums2_len - 1;
       
       while (len1 >= 0 && len2 >= 0) {
           if (nums1[len1] <= nums2[len2])
               nums1[i--] = nums2[len2--];
           else if (nums1[len1] > nums2[len2])
               nums1[i--] = nums1[len1--];
       }
       //假如A或者B数组还有剩余
       while (len2 != -1) nums1[i--] = nums2[len2--];
       while (len1 != -1) nums1[i--] = nums1[len1--];
   }

实战训练（白银挑战）

双指针

我们使用双指针，能够很清晰、方便地解决问题，接下来我们使用双指针来解决一些典型问题：

删除重复元素

给定一个数组，要求删除其中所有重复元素，重复元素保留一个
对于这种问题，我们使用快慢双指针来解决：
- 快指针在前，慢指针在后，快指针向前移动
- 如果快指针所指元素，与此时慢指针所指元素相同（即重复元素），则慢指针等待，快指针继续向前移动
- 如果快指针所指元素，与此时慢指针所指元素不相同，则慢指针：先记录快指针指向的值，然后向前移动，快指针继续向前移动
- 循环执行，直到快指针移动到右边界为止
- 即：慢指针左侧维护了所有未重复的元素值
具体代码实现如下：（2023/08/13午）

/**
    * 快慢指针
    *
    * @param nums
    * @return
    */
   public static int removeDuplicates(int[] nums) {
       // slow维护左侧，未重复元素
       int slow = 0;
       // 快指针移动
       for (int fast = 1; fast < nums.length; fast++) {
            if(nums[fast] != nums[slow]){
               // slow负责维护未重复的元素
               slow++;
               nums[slow] = nums[fast];
           }
       }
            
       return slow + 1;
   }

删除指定元素

给定一个数组，要求删除指定元素
对于这种问题，我们也可以使用双指针解决，且有两种思路：
- 快慢双指针
- 对撞双指针
快慢双指针的思路与上面如出一辙，无非是：快指针寻找的元素不再是与慢指针重复的元素，而是指定元素
具体代码如下：（2023/08/13午）

/**
     * 快慢双指针
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        //最后剩余元素的数量
        return slow;
    }

这里简单捋一捋对撞双指针的思路：（2023/08/13午）
- 左指针在左，右指针在右，左指针向前移动
- 如果左指针未找到指定元素，则左指针继续向前移动
- 如果左指针找到了指定元素，就拿右指针所指元素覆盖，左指针向前移动，右指针向后移动
- 循环执行，直到两指针碰撞
- 即：左指针左侧维护了所有正确的元素值
使用对撞双指针解决思路：（2023/08/15晚）
- 设左右双指针
- 左指针向前移动，遇到指定元素就停下来
- 这时，将两指针所指元素交换，右指针向前一步
- 重复以上操作，直至两指针相撞
具体代码实现如下：（2023/08/13午）

/**
   * 对撞双指针
   *
   * @param nums
   * @param val
   * @return
   */
  public static int removeElement3(int[] nums, int val) {
      // 1.定义左右指针
      int right = nums.length - 1;
      for (int left = 0; left < right; ) {
          // 2.左指针找到目标元素
          if (nums[left] == val) {
              // 3.右指针覆盖左指针
              nums[left] = nums[right];
              right--;
          } 
          
          left++;    
      }
      return right;
  }

元素奇偶移动专题

情景：
给你一个数组，设计一种算法，要求操作结束后，数组中所有偶数都在左，所有奇数都在右
首先想到的方法应该是：new一个新数组，把该数组遍历两遍，依次将偶数元素、奇数元素先后插入 ✔
那么有没有不开辟新空间，即空间复杂度为O(1)的算法呢？
当然有：
- 设左右双指针
- 左指针遇到偶数元素就跳过，遇到奇数元素就停下来
- 右指针相反遇到奇数元素就跳过，遇到偶数元素就停下来
- 这时，将两指针指向元素交换
- 重复以上操作，直至两指针相撞
这不就是 “对撞双指针” 思想吗？，具体代码如下：（2023/08/15晚）

/**
  * 双指针，不稳定 的移动
  *
  * @param A
  * @return
  */
 public static int[] sortArrayByParity(int[] A) {
     int left = 0, right = A.length - 1;
     while (left < right) {
         if (A[left] % 2 > A[right] % 2) {
             int tmp = A[left];
             A[left] = A[right];
             A[right] = tmp;
         }

         if (A[left] % 2 == 0) left++;
         if (A[right] % 2 == 1) right--;
     }

     return A;
 }

数组轮转

情景：
给你一个数组，将数组的每个元素，向右轮转k个位置，得到新数组，即：

1 2	`输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]`

看起来好像挺简单，但怎么实现没思路，这里介绍一种简单的方法：两轮反转（2023/08/25早）
- 首先，对整个数组实行翻转
- 然后，从k处将数组分隔，分别翻转分隔后的两个数组
- 这样就得到了最终结果
具体代码如下：

/**
     * 数组轮转
     * @param nums
     * @param k
     */
    public static void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }

数组的区间专题

情景：

1
2
3

示例:
输入: nums = [0,1,2,4,5,7]
输出: ["0->2","4->5","7"]

实现思路：
- 定义快慢指针
- 快指针向前移动
- 快指针找到了不连续递增的数，慢指针指向该数，快指针继续移动
- 快指针到达数组边缘，结束
具体代码如下：

/**
     * 区间合并
     *
     * @param nums
     * @return
     */
    public static List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        // slow 初始指向第 1 个区间的起始位置
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            // fast 向后遍历，直到不满足连续递增(即 nums[fast] + 1 != nums[fast + 1])
            // 或者 fast 达到数组边界，则当前连续递增区间 [slow, fast] 遍历完毕，将其写入结果列表。
            if (fast + 1 == nums.length || nums[fast] + 1 != nums[fast + 1]) {
                // 将当前区间 [slow, fast] 写入结果列表
                StringBuilder sb = new StringBuilder();
                sb.append(nums[slow]);
                if (slow != fast) {
                    sb.append("->").append(nums[fast]);
                }
                res.add(sb.toString());
                // 将 slow 指向更新为 fast + 1，作为下一个区间的起始位置
                slow = fast + 1;
            }
        }
        return res;
    }

字符串替换空格问题

情景：
给你一个字符串，实现：将该字符串中的所有空格都替换为”20%”
这个简单，很快就能有思路：
- 创建一个新的String对象newString
- 依次拿到字符串中的字符，检查是否为空格，拼接到newString中
- 如果是空格，则拼接”20%”，反之拼接该字符
具体代码如下：（2023/08/25早）

/**
     * 方法1：创建新的字符串
     *
     * @param str
     * @return
     */
    public static String replaceSpace1(StringBuffer str) {
        String res = "";
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == ' ')
                res += "%20";
            else
                res += c;
        }
        return res;
    }

我们创建了一个新的字符串来完成👆，那么如果我们在原字符串上，扩充所需空间，不必开辟新的空间就能完成呢？
思路如下：
- 扩充字符串长度
- 定义快慢指针，快指针指向原长度末，慢指针指向现长度末
- 快指针向前移动，检查每个字符
- 如果该字符是为非空格字符，则慢指针维护该字符，两指针向前移动
- 如果是空格，慢指针维护”20%”，两指针向前移动
- 快指针到达数组边缘，结束

具体代码如下：（2023/08/25早）

/**
     * 方法2：在原数组基础上改
     *
     * @param str
     * @return
     */
    public static String replaceSpace2(StringBuffer str) {
        if (str == null)
            return null;
        int numOfblank = 0;//空格数量
        int len = str.length();
        for (int i = 0; i < len; i++) {  //计算空格数量
            if (str.charAt(i) == ' ')
                numOfblank++;
        }
        str.setLength(len + 2 * numOfblank); //设置长度
        int fast = len - 1;  //两个指针
        int slow = (len + 2 * numOfblank) - 1;

        while (fast >= 0 && slow > fast) {
            char c = str.charAt(fast);
            if (c == ' ') {
                fast--;
                str.setCharAt(slow--, '0');
                str.setCharAt(slow--, '2');
                str.setCharAt(slow--, '%');
            } else {
                str.setCharAt(slow, c);
                fast--;
                slow--;
            }
        }
        return str.toString();
    }

栈

基础知识（青铜挑战）

认识栈这个数据结构：先进先出
常用的栈操作有：
- push(E e)：入栈
- peek()：弹出栈顶元素
- pop()：出栈
- empty()：判断栈是否为空
我们尝试手动创建一个栈数据结构，并实现它的基础功能：

基于数组实现栈

/**
 * 基于数组实现
 * @param <T>
 */
class Mystack2<T> {
    // 内部数组
    private Object[] stack;
    // 栈顶
    private int top;

    // 初始化
    public Mystack2(int size) {
        stack = new Object[size];
    }

    // 入栈
    public void push(T t) {
        // todo 检查数组是否已满，扩容
        this.expandCapacity(top + 1);
        this.stack[top] = t;
        top++;
    }

    // 弹出栈顶元素
    public T peek() {
        T t = null;
        if (!this.empty())
            t = (T) this.stack[top - 1];
        return t;
    }

    // 出栈
    public T pop() {
        T t = this.peek();

        this.stack[top - 1] = null;
        top--;

        return t;
    }

    // 判空
    public boolean empty() {
        return this.top <= 0;
    }

    // 校验数组大小，判断是否需要扩容
    public void expandCapacity(int size) {
        int capacity = this.stack.length;
        if (size > capacity) {
            // 扩容1.5倍
            capacity = capacity * 3 / 2 + 1;
            // capacity = capacity + capacity >> 1;
            this.stack = Arrays.copyOf(stack, capacity);
        }
    }

    public static void main(String[] args) {
        Mystack2<String> stack = new Mystack2<>(10);
        System.out.println(stack.peek());
        System.out.println(stack.empty());
        stack.push("java");
        stack.push("is");
        stack.push("beautiful");
        stack.push("language");
        System.out.println(stack.pop());
        System.out.println(stack.empty());
        System.out.println(stack.peek());
    }
}

基于链表实现栈

/**
 * 基于链表实现
 *
 * @param <T>
 */
class ListStack2<T> {
    // 栈顶节点
    private Node head;

    // 入栈
    public void push(T t) {
        if (t == null) {
            throw new NullPointerException("参数不能为空");
        }

        if (head == null) {
            head = new Node(t);
        } else {
            Node node = new Node(t);
            node.next = head;
            head = newNode;
        }
    }

    // 弹出栈顶元素
    public T peek() {
        return head.t;
    }

    // 出栈
    public T pop() {
        head = head.next;
        return head.t;
    }

    // 判断栈是否为空
    public boolean empty() {
        return head == null;
    }

    // 节点结构
    class Node {
        private T t;
        private Node next;

        public Node(T t) {
            this.t = t;
        }
    }
}

实战训练（白银挑战）

括号匹配问题

情景：
给定一个字符串，仅包含”(“、”)”、”[“、”]”等字符，要求如下：
如果该字符中的左括号与右括号连续且成对出现，则说明该字符串有效，如下：

1	`String str = "(){}[]" // 有效字符串`

实现一个算法，判断该字符串是否有效
实现思路：
- 构造一个HashMap，将左右括号以键值对形式存放进去
- 构造一个栈Stack
- 依次遍历字符串中的字符s，如果存在Map中的key值与s相等，则入栈
- 如果该字符s不是key值，即不是左括号，则Stack出栈，计算value值是否与s相等
- 不相等则说明括号不连续或不成对，该字符串是无效的
这里利用的是栈的特性：先进先出，用来判断括号是否连续且成对（2023/08/26午）
具体代码实现：

/**
    * 括号匹配问题
    *
    * @param s
    * @return
    */
   static boolean isValid(String s) {
       if (s.length() <= 1) {
           return false;
       }
       // 1.构造HashMap
       Map<Character, Character> smap = new HashMap<>();
       smap.put('(', ')');
       smap.put('{', '}');
       smap.put('[', ']');
       // 2.构造栈
       Stack<Character> stack = new Stack<>();
       // 3.遍历字符串
       for (int i = 0; i < s.length(); i++) {
           char item = s.charAt(i);
           // 入栈左括号
           if (smap.containsKey(item)) {
               stack.push(item);
               //检查右括号
           } else {
               if (stack.isEmpty()) {
                   return false;
               }

               Character left = stack.pop();
               char rightChar = smap.get(left);
               if (rightChar != item) {
                   return false;
               }
           }
       }
       //
       return stack.isEmpty();
   }

最小栈

实现快速获取栈中的最小元素

我们设计这样一个数据结构：

构建两个栈，一个栈存放入栈元素，另一个栈存放栈顶元素对应的此时栈中最小的元素
即最小栈中的栈顶，始终维护栈中的最小元素（2023/08/26午）
具体代码如下：

/**
* 最小栈
*/
public class MinStack {  
    private Stack<Integer> stack;  
    private Stack<Integer> minStack;  
  
    public MinStack() {  
        stack = new Stack<>();  
        minStack = new Stack<>();  
    }  
  
    public void push(int x) {  
        stack.push(x);  
        if (minStack.isEmpty() || x <= minStack.peek()) {  
            minStack.push(x);  
        }  
    }  
  
    public void pop() {  
        if (stack.peek().equals(minStack.peek())) {  
            minStack.pop();  
        }  
        stack.pop();  
    }  
  
    public int top() {  
        return stack.peek();  
    }  
  
    public int getMin() {  
        return minStack.peek();  
    }  
}

最大栈

思路与最小栈基本一致，具体代码如下：

/**
* 最大栈
*/
public class MaxStack {  
    private Stack<Integer> stack;  
    private Stack<Integer> maxStack;  
  
    public MaxStack() {  
        stack = new Stack<>();  
        maxStack = new Stack<>();  
    }  
  
    public void push(int x) {  
        stack.push(x);  
        if (maxStack.isEmpty() || x >= maxStack.peek()) {  
            maxStack.push(x);  
        }  
    }  
  
    public void pop() {  
        if (stack.peek().equals(maxStack.peek())) {  
            maxStack.pop();  
        }  
        stack.pop();  
    }  
  
    public int top() {  
        return stack.peek();  
    }  
  
    public int getMax() {  
        return maxStack.peek();  
    }  
}

解释：
- 对于实现最大栈的pop()方法：
- 当你从主栈中弹出一个元素，你会检查这个元素是否是辅助栈的栈顶元素。如果是，那么辅助栈的栈顶元素会被弹出。无论这个元素是否是辅助栈的栈顶元素，主栈的元素都会被弹出。
- 这样做的目的是为了维护辅助栈的栈顶元素始终是主栈当前的最大元素。当主栈的元素被弹出时，如果它不是最大的元素（即它不是辅助栈的栈顶元素），那么辅助栈的栈顶元素（即当前的最大元素）就不会被弹出。
- 因此，通过这种方式，辅助栈可以持续地维护主栈中的最大值。
实在理不清过程的，强烈建议画个图，很直观，一目了然，尤其是栈、队列这种数据结构（2023/11/10晚）

通关（过关挑战）

这是要求：

1	`给你一个栈，依次入栈1 2 3 4，请问以下出栈顺序可能出现吗？为什么？`

我们解释两个例子吧：（2023/08/26午）

1 2	`出栈顺序：2 3 4 1 √ 先出栈2，必然是1已经入栈了，再入栈3、出栈3，入栈4、出栈4，最后出栈1，没有问题`

1 2	`出栈顺序：1 4 2 3 × 先入栈1、出栈1，要出栈4，必然是2 3 4依次入栈了，出栈4之后的出栈顺序只能是3 2，而不可能是2 3，故错误`

多做这样的例子，你就能彻底明白栈这个数据结构了：先进先出

队列和Hash

基础知识（青铜挑战）

Hash

Hash，又称散列，将任意长度的输入，通过散列算法，转换为固定长度的输出
映射、扩容机制
碰撞处理（Hash冲突）
- 开放寻址法
- 链地址法
- 再哈希法（布隆过滤）
- 建立公共溢出区

队列

特点：先进先出（2023/09/03午）
用链表实现队列
具体代码如下：

public class LinkQueue {
    private Node front;
    private Node rear;
    private int size;

    public LinkQueue() {
        this.front = new Node(0);
        this.rear = new Node(0);
    }

    /**
     * 入队
     */
    public void push(int value) {
        // 尾插法
        Node newNode = new Node(value);
        Node temp = front;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        rear = newNode;
        size++;
    }

    /**
     * 出队
     */
    public int pull() {
        // 头删法
        if (front.next == null) {
            System.out.println("队列已空");
        }
        Node firstNode = front.next;
        front.next = firstNode.next;
        size--;
        return firstNode.data;
    }

    /**
     * 遍历队列
     */
    public void traverse() {
        Node temp = front.next;
        while (temp != null) {
            System.out.print(temp.data + "\t");
            temp = temp.next;
        }
    }

    static class Node {
        public int data;
        public Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    //测试main方法
    public static void main(String[] args) {
        LinkQueue linkQueue = new LinkQueue();
        linkQueue.push(1);
        linkQueue.push(2);
        linkQueue.push(3);
        System.out.println("第一个出队的元素为:" + linkQueue.pull());
        System.out.println("队列中的元素为:");
        linkQueue.traverse();
    }
}

实战训练（白银挑战）

用栈实现队列

情景：使用栈实现队列
实现思路：（2023/09/03午）
- 利用栈先进后出的特性，首先一个栈inStack将元素压栈，它负责 “进” 元素
- inStack再依次出栈，另一个栈outStack负责将出栈的元素压栈，它负责 “出” 元素
具体代码如下：

/**
 * 用栈实现队列
 */
class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;
    public MyQueue() {
        inStack = new LinkedList<Integer>();
        outStack = new LinkedList<Integer>();
    }
    public void push(int x) {
        inStack.push(x);
    }
    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }
    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
    
    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

用队列实现栈

实现思路：（2023/09/03午）
- 用两个队列实现栈可以这样做：假设你有队列A和队列B，每次push一个元素，都放入队列A中
- 当你想要pop一个元素时，先将队列A中的元素依次出队并入队到队列B中，直到队列A中只剩下一个元素，然后将这个元素出队
- 这样，你就模拟了栈后进先出的特性
- 当你继续执行push操作时，将元素放入非空的队列（此时是队列A）
- 而当你想要pop操作时，将除队列A中最后一个元素外的所有元素从队列A出队并依次入队到队列B中，再将队列A中剩下的最后一个元素出队
- 这样，可以保持栈的后进先出的特性，并且实现了用两个队列来模拟栈的功能
- 需要注意的是，每次pop操作后，需要交换队列A和队列B的角色，以便下一次的操作
上面的思路是正确的，但是没有把核心思想说清楚，看的是云里雾里，实现思路如下：（2023/11/10晚）

初始化阶段：创建两个队列，queue1和queue2。这两个队列开始时都是空的。topElement变量用来跟踪当前栈顶的元素。

push操作：当执行push操作时，将新元素添加到queue1的尾部。同时，因为这个新元素就是当前的栈顶元素，所以更新topElement为这个新元素。

pop操作：当执行pop操作时，首先将queue1中的所有元素（除了最后一个）依次弹出并添加到queue2中。这样做的效果是，queue2中的元素就是queue1中元素的逆序，即最后一个进入的元素现在成为了第一个。然后，将queue1和queue2交换，使得queue2成为了主要的队列。最后，从queue2中弹出的最后一个元素就是原来的栈顶元素，返回这个元素。

peek操作：这个操作只需要返回当前的topElement即可，不需要进行任何操作。

isEmpty操作：检查queue1是否为空，如果为空，那么栈就是空的，返回true；否则返回false。

核心就是：两队列交换，queue1始终负责入栈，queue始终负责出栈

具体代码如下：

/**
 * 用队列实现栈
 */
  
public class StackUsingQueues {  
    private Queue<Integer> queue1;  
    private Queue<Integer> queue2;  
    private int topElement;  
  
    public StackUsingQueues() {  
        queue1 = new LinkedList<>();  
        queue2 = new LinkedList<>();  
    }  
  
    public void push(int x) {  
        queue1.add(x);  
        topElement = x;  
    }  
  
    public int pop() {  
        while(queue1.size() > 1) {  
            queue2.add(queue1.remove());  
        }  
  
        int poppedElement = queue1.remove();  
        Queue<Integer> temp = queue1;  
        queue1 = queue2;  
        queue2 = temp;  
        return poppedElement;  
    }  
  
    public int peek() {  
        return topElement;  
    }  
  
    public boolean isEmpty() {  
        return queue1.isEmpty();  
    }  
}

还是看不明白的，强烈建议画个图，一目了然，就算忘了也能快速回忆起来：（2023/11/10晚）

两数之和

这题我之前做过，力扣里为数不多做过的题
情景：

1
2
3

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:2 + 7 = 9, 返回二者下标

解决思路有三种，这里统一讲：
- 遍历数组，依次两两相加，判断是否等于 target。缺点：双层循环嵌套 —> 时间复杂度大
- 建立一张Hash表，存储 target - x，存在即返回，不存在即存储 x，继续遍历 —> 遍历过的数字已经存储到map中了，减少了遍历元素的个数
- 排序数组，将二层循环改为二分查找
具体代码如下：

public static int[] twoSum(int[] nums, int target) {
      int n = nums.length;
      for (int i = 0; i < n; ++i) {
          for (int j = i + 1; j < n; ++j) {
              if (nums[i] + nums[j] == target) {
                  return new int[]{i, j};
              }
          }
      }
      return new int[0];
  }

public int[] twoSum3(int[] nums, int target) {
     // 数组元素值 -> 对应下标
     HashMap<Integer, Integer> map = new HashMap<>();
     for (int i = 0; i < nums.length; i++) {
         if (map.containsKey(target - nums[i])) {
             return new int[]{i, map.get(target - nums[i])};
         }
         map.put(nums[i], i);
     }
     return new int[0];
 }

三数之和

二叉树遍历（层数优先）

基础知识（青铜挑战）

了解二叉树的基础知识

实战训练（白银挑战）

简单的层序遍历

基本的层序遍历思路很清晰：
- 给你一个二叉树根节点，你需要创建一个队列 queue 来遍历节点，一个链表 list 来存储节点的数据域，即值
- 首先将根节点入队
- 队列 queue 出队，将该节点值存入 list，再依次将左右孩子节点入队
- 重复以上操作，每个节点出对后，都存储该节点值到 list 中，再依次将左右孩子节点入队，直到队列 queue为空
- 这样得到的数据链表 list 就是按层序遍历的顺序得到的
具体代码如下：（2023/09/09午）

public static List<Integer> simpleLevelOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<Integer>();
    }

    List<Integer> res = new ArrayList<Integer>();
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    //将根节点放入队列中，然后不断遍历队列
    queue.add(root);
    //有多少元素执行多少次
    while (queue.size() > 0) {
        //获取当前队列的长度，这个长度相当于 当前这一层的节点个数
        TreeNode t = queue.remove();
        res.add(t.val);
        if (t.left != null) {
            queue.add(t.left);
        }
        if (t.right != null) {
            queue.add(t.right);
        }
    }
    return res;
}

层序遍历分层

层序遍历我们做到了，这里添加一个要求：对层序遍历的节点值分层处理，即二叉树每层的节点值分别存放进一个链表 list 中
这个代码怎么写呢？很简单的，按这个思路走：
- 我们之前层序遍历时，每出队一个节点，都把其值存入 list 链表中，然后入队其孩子节点
- 在开始出队某一层的节点时，此时队列的节点数，就是二叉树这一层的节点数
- 那我们根据可以某时刻队列容量来遍历队列，将这层的节点全部出队，并且把节点值存入该层独有的 list 中
- 当然了，每个节点出队后，要将自己的孩子节点依次入队
- 这样，当队列为空时，我们得到了各层的节点链表 list，返回一个包含各层 list 的 list 即可
具体代码如下：（2023/09/09晚）

public static List<List<Integer>> level102Order(TreeNode root) {
      if (root == null) {
          return new ArrayList<List<Integer>>();
      }

      List<List<Integer>> res = new ArrayList<List<Integer>>();
      LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
      //将根节点放入队列中，然后不断遍历队列
      queue.add(root);
      while (queue.size() > 0) {
          //获取当前队列的长度，这个长度相当于 当前这一层的节点个数
          int size = queue.size();
          ArrayList<Integer> tmp = new ArrayList<Integer>();
          //将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
          //如果节点的左/右子树不为空，也放入队列中
          for (int i = 0; i < size; ++i) {
              TreeNode t = queue.remove();
              tmp.add(t.val);
              if (t.left != null) {
                  queue.add(t.left);
              }
              if (t.right != null) {
                  queue.add(t.right);
              }
          }
          //将临时list加入最终返回结果中
          res.add(tmp);
      }
      return res;
  }

自底向上的层序遍历

在前面学习的基础上，实现这个要求就很简单了
在拿到各层节点值的 list 后，按头插的方式，插入链表 list 中，就实现了自底向上的层序遍历了（2023/09/09晚）
具体代码如下：

public static List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
    if (root == null) {
        return levelOrder;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<Integer>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            TreeNode left = node.left, right = node.right;
            if (left != null) {
                queue.offer(left);
            }
            if (right != null) {
                queue.offer(right);
            }
        }
        levelOrder.add(0, level);//栈
    }
    return levelOrder;
}

锯齿形层序遍历

情景：

二叉树如下:
	 3
   /   \  
  8     9
 / \   /
20  11 6
锯齿形遍历：3 9 8 20 11 6

在基本的层序遍历的基础上，如何实现锯齿形层序遍历？
这样的思路能否完成呢：其他条件不变，改变存放节点值的顺序如何？（2023/09/10午）
我们这里将 list 该换为 queue ，因为它可以提供了不同的入队方式
具体代码如下：

public static List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
       // 节点值列表
       List<List<Integer>> ans = new LinkedList<>();
       if (root == null)
           return ans;
       // 队列，控制遍历节点顺序
       Deque<TreeNode> queue = new LinkedList<>();
       // 根节点入队
       queue.offer(root);
       // 控制存放节点值顺序
       boolean isOrderLeft = true;
       while (!queue.isEmpty()) {
           // 每层的节点值列表
           Deque<Integer> levelList = new LinkedList<>();
           // 该层节点数
           int size = queue.size();
           for (int i = 0; i < size; i++) {
               // 出队，存值
               TreeNode poll = queue.poll();
               if (isOrderLeft) {
                   levelList.addFirst(poll.val);
               } else {
                   levelList.addLast(poll.val);
               }
               // 左右孩子节点入队
               if (poll.left != null) {
                   queue.add(poll.left);
               }
               if (poll.left != null) {
                   queue.add(poll.right);
               }
           }
           ans.add(new LinkedList<Integer>(levelList));
           // 变换存放节点值顺序
           isOrderLeft = !isOrderLeft;
       }
       return ans;
   }

N叉数的层序遍历

问题：将二叉树的情景改为N叉数，遍历结果也是很简单的，即将左右子节点改为若干子节点（2023/09/10午）
具体代码如下：

public static List<List<Integer>> nLevelOrder(NTreeNode root) {
      List<List<Integer>> ans = new ArrayList<>();
      Deque<NTreeNode> queue = new ArrayDeque<>();

      if (root != null)
          queue.addLast(root);

      while (!queue.isEmpty()) {
          Deque<NTreeNode> next = new ArrayDeque<>();
          List<Integer> nd = new ArrayList<>();

          while (!queue.isEmpty()) {
              NTreeNode cur = queue.pollFirst();
              nd.add(cur.val);
              // 入队，将孩子节点依次入队
              for (NTreeNode chd : cur.children) {
                  if (chd != null)
                      next.add(chd);
              }
          }
          queue = next;
          ans.add(nd);
      }
      return ans;
  }

这里暂时没看懂为什么加了个 queue，日后解答

获取每一层的最大数（扩展）

出队每层节点时，累加节点值，求平均值即可：（2023/09/11早）

public static List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if (root == null) return res;
        
        Queue<TreeNode> list = new LinkedList<>();
        list.add(root);
        
        while (list.size() != 0) {
            int len = list.size();
            double sum = 0;
            for (int i = 0; i < len; i++) {
                TreeNode node = list.poll();
                
                sum += node.val;
                if (node.left != null) list.add(node.left);
                if (node.right != null) list.add(node.right);
            }
            res.add(sum / len);
        }
        return res;
    }

获取每一层的平均数（扩展）

出队节点时，比较节点值，求取最大值即可：

public static List<Double> largestValues2(TreeNode root) {
      List<Double> res = new ArrayList<>();
      if (root == null) return res;

      Queue<TreeNode> list = new LinkedList<>();
      list.add(root);

      while (list.size() != 0) {
          int len = list.size();
          double max = Double.MIN_VALUE;
          for (int i = 0; i < len; i++) {
              TreeNode node = list.poll();

              max = Double.max(max, node.val);
              if (node.left != null) list.add(node.left);
              if (node.right != null) list.add(node.right);
          }
          res.add(max);
      }
      return res;
  }

获取二叉树的右视图（扩展）

统计每一层出队的最后一个节点即可

public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {  //将当前层的最后一个节点放入结果列表
                    res.add(node.val);
                }
            }
        }
        return res;
    }

通关（过关挑战）

情景：获取一个二叉树的左视图（2023/09/12午）

public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == 0) {  //将当前层的第一个节点放入结果列表
                    res.add(node.val);
                }
            }
        }
        return res;
    }

二叉树遍历（深度优先）

基础知识（青铜挑战）

理解递归思想：调用自己、压栈、明确终止条件

实战训练（白银挑战）

递归实现二叉树的前、中、后序遍历

我的建议是直接把代码背下来
你当然可以尝试去理解，也不是很难想明白，但是不要钻牛角尖了，递归这玩意儿，很不友好

/**
    * 前序遍历，将结果返回到list中
    *
    * @param root
    * @param res
    */

   public static void preOrder(TreeNode root, List<Integer> res) {
       if (root == null) {
           return;
       }
       res.add(root.val);
       preOrder(root.left, res);
       preOrder(root.right, res);
   }

 /**
   * 中序遍历，将结果返回到list中
   *
   * @param root
   * @param res
   */
public static void inOrder(TreeNode root, List<Integer> res) {
      if (root == null) {
          return;
      }
      inOrder(root.left, res);
      res.add(root.val);
      inOrder(root.right, res);
  }

/**
 * 后序遍历，将结果返回到list中
 *
 * @param root
 * @param res
 */
public static void postOrder(TreeNode root, List<Integer> res) {
    if (root == null) {
        return;
    }
    postOrder(root.left, res);
    postOrder(root.right, res);
    res.add(root.val);
}

迭代实现二叉树的前、中、后序遍历

前序遍历

public static List<Integer> preOrderTraversal(TreeNode root) {
     List<Integer> res = new ArrayList<Integer>();
     if (root == null) {
         return res;
     }

     Deque<TreeNode> stack = new LinkedList<TreeNode>();
     TreeNode node = root;
     while (!stack.isEmpty() || node != null) {
         while (node != null) {
             res.add(node.val);
             stack.push(node);
             node = node.left;
         }

         node = stack.pop();
         node = node.right;
     }
     return res;
 }

中序遍历（2023/09/12午）

public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

前序遍历和中序遍历的代码不复杂，还是注意：挺不好理解的，不要钻牛角尖，那么我们接下来看下后序遍历
后序遍历
这个相较于前两个更难实现，但可以这样想：
- 前序遍历的顺序是：中、左、右，我们简单该两个参数，实现遍历顺序为中、右、左
- 再将遍历结果reserve反转，不就得到左、右、中的遍历顺序了吗？

public static List<Integer> postOrderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      if (root == null) return res;
      Stack<TreeNode> stack = new Stack<>();
      TreeNode node = root;

      while (!stack.isEmpty() || node != null) {
          while (node != null) {
              res.add(node.val);
              stack.push(node);
              node = node.right;
          }
          node = stack.pop();
          node = node.left;
      }
      Collections.reverse(res);
      return res;
  }

通关（过关挑战）

理解中序遍历的递归过程，挺难的，努努力吧（2023/09/12午）

二叉树深度优先经典问题

这块儿内容我个人认为非常抽象，虽然重要，但我还是决定先跳过这部分了，脑壳疼（2023/09/12午）

最大深度问题

判断平衡树

最小深度

N叉数的最大深度

二分查找和搜索数

基础知识（青铜挑战）

了解顺序查找、以及二分查找的简单实现。经典的顺序查找：

简单的二分查找

简单的二分查找，具体代码如下：（2023/09/12午）

/**
   * 循环实现二分查找
   *
   * @param array
   * @param low
   * @param high
   * @param target
   * @return
   */
  public static int binarySearch1(int[] array, int low, int high, int target) {

      // 循环
      while (low <= high) {
          int mid = (low + high) / 2;
	//1.右移提高性能
          if (array[mid] == target) {
              return mid;
          } else if (array[mid] > target) {
              // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
              high = mid - 1;
          } else {
              // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
              low = mid + 1;
          }
      }
      return -1;
  }

待优化有两点：解决溢出问题、除法->移位（提高运算效率）

/**
   * 循环实现二分查找
   *
   * @param array
   * @param low
   * @param high
   * @param target
   * @return
   */
  public static int binarySearch1(int[] array, int low, int high, int target) {

      // 循环
      while (low <= high) {
          int mid = low + ((high - low) >> 1); // 防止溢出 右移提高性能
          if (array[mid] == target) {
              return mid;
          } else if (array[mid] > target) {
              // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
              high = mid - 1;
          } else {
              // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
              low = mid + 1;
          }
      }
      return -1;
  }

上面提到的二分查找是最常用的循环法，还有一种递归法：（2023/09/12午）

二分查找（递归法）

/**
    * 方法二：递归方式实现
    *
    * @param array
    * @param low
    * @param high
    * @param target
    * @return
    */
   public static int binarySearch2(int[] array, int low, int high, int target) {
       //递归终止条件
       if (low < high) {
           int mid=low + ((high-low) >> 1);
           if (array[mid] == target) {
               return mid;  // 返回目标值的位置，从1开始
           }
           if (array[mid] > target) {
               // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
               return binarySearch2(array, low, mid - 1, target);
           } else {
               // 由于array[mid]不是目标值，因此再次递归搜索时，可以将其排除
               return binarySearch2(array, mid + 1, high, target);
           }
       }
       return -1;   //表示没有搜索到
   }

含重复元素的二分查找

思路：
- 找到指定元素 target 后，继续向左查找，mid–，
- 直到到达数组左边界，或者 nums[mid] 不等于 target 为止
- 返回 nums[mid++]

/**
     * 含重复元素的二分搜索
     *
     * @param nums
     * @param target
     * @return
     */
    public static int search1(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return -1;
        int left = 0;

        if (nums[0] == target) {
            return 0;
        }

        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                //找到之后，往左边找
                while (mid != 0 && nums[mid] == target)
                    mid--;
                return mid + 1;
            }
        }
        return -1;
    }

实战训练（白银挑战）

山脉数组峰顶查找

情景：给定一个山脉数组，查找峰顶（即最大的数）

         17  
      /      \
    5          7
  /              \
1                  3

如上图所示，峰顶为17，那么峰顶有什么特别之处吗？
- 当然是：nums[i] > nums[i - 1] && nums[i] > nums[i + 1]
- 所以跟普通的二分查找相比，仅仅多考虑到了进行节点左右的大小比较
具体代码如下：（2023/09/15晚）

/**  
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可  
     *  
     * @param nums int整型一维数组  
     * @return int整型  
     */  
    public int findPeakElement(int[] arr) {  
        int n = arr.length;  
  
        if (n == 1) {  
            return 0; // 如果数组只有一个元素，它自然就是峰值  
        }  
  
        for (int i = 0; i < n - 1; ++i) {  
            if (arr[i] > arr[i + 1]) {  
                return i; // 如果当前元素大于其下一个元素，则找到了峰值，返回其索引  
            }  
        }  
  
        // 如果循环结束还没有返回，说明数组是递增的，那么最后一个元素是峰值  
        return n - 1;  
    }

旋转数组最小数字

1
2
3

输入: nums = [4,4,4,5,1,2,3]
输出: 1
原数组为[1,2,3,4,5]，旋转3次得到输入数组

这个图很形象：

最小值就在中轴线，仍然是考虑到了进行节点左右大小的比较，并且在二分结束之后，直接拿到 nums[low]，即为最小值
具体代码如下：

/**
     * 旋转数字的最小数字
     *
     * @param nums
     * @return
     */
    public static int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = low + ((high - low) >> 1);
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }

有序数组缺失数字

简单，二分查找，当 nums[i] != i 时，就拿到了这个数字（2023/09/15晚）
具体代码如下：

/**
    * 缺失数字
    *
    * @param a
    * @return
    */
   public static int solve(int[] a) {
       // write code here
       int left = 0;
       int right = a.length - 1;
       while (left < right) {
           int mid = (left + right) / 2;
           if (a[mid] == mid) {
               left = mid + 1;
           } else {
               right = mid;
           }
       }
       return left;
   }

优化求平方根

快速排序

基础知识（青铜挑战）

快速排序通过多次比较与交换来完成排序。而这个过程又被分为了多次重复单趟排序，接下来我们先从每一趟的排序讲起。
快速排序思想很简单，也很重要：
在一个无序数组中取一个数key，每一趟排序的最终目的是：让key的左边的所有数小于key，key的右边都大于key（假设排升序）
接下来，我们对key的左右区间进行单趟排序，可以预见的是，每次排序都固定好了一个数。而当我们对细分的左右区间进行单趟排序，最终整个数组都会化为有序
最常用的快排实现方法：快慢指针法
- 取最左边的数为key
- 定义两个快慢指针，都从key的下一位往右走
- fast每走一步判断一下它指向的元素是否小于key，若小于则交换fast和slow位置的元素，并且让slow向前走
- 直到fast走到底，结束循环
- 最后让slow和key位置的值交换，再返回key的位置
具体代码如下：（2023/09/19午）

public void quickSort(int[] nums, int start, int end) {
        // 判断递归结束的条件
        if (start >= end) {
            return;
        }
        // 选定最左边的元素作为基准值
        int pivot = nums[start];
        // 初始化快慢指针
        int slow = start;
        int fast = start + 1;

        // 快慢指针法进行划分
        while (fast <= end) {
            if (nums[fast] < pivot) {
                // 如果当前元素小于基准值，将其交换到基准值的左侧
                slow++;
                swap(nums, slow, fast);
            }
            fast++;
        }
        // 将基准值交换到正确的位置
        swap(nums, start, slow);

        // 递归对基准值的左右两部分进行排序
        quickSort(nums, start, slow - 1);
        quickSort(nums, slow + 1, end);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

实战训练（白银挑战）

数组中K大的数

我们要找第K大的元素，如果我们能够将数组排好序，再取 nums[K - 1] 元素，就是目标值了
试想一下，每一轮快排结束之后，我们能知晓基准值的位置，即我们知晓基准值的下标
- 如果目标元素在基准元素的左侧，就对左侧进行递归快排
- 否则，对右侧进行递归快排
- 最后，在已经 ”排好序的“ 数组中，轻松就能找到第K大的元素
- 其实就是快速排序对半砍，每次只快排一半元素，要么左侧，要么右侧（2023/09/27晚）

public static void quicksort(int[] nums, int left, int right) {
       int start = left;
       int end = right;
       int pivot = nums[(end + start) / 2]; //取中位值作左右参考对比

       //每次循环都将大的放到左边，小的放到右边
       while (start < end) {
           while (nums[start] > pivot) {
               start++;
           }

           while (nums[end] < pivot) {
               end--;
           }

           //如果l>=r说明mid左边的值全部大于等于mid的值，右边全是小的，退出
           if (start >= end) {
               break;
           }
           //交换
           int temp = nums[start];
           nums[start] = nums[end];
           nums[end] = temp;

           //解决值相同的情况，如果交换后发现左边的值等于mid目标值，则使右边指针向左移
           if (nums[start] == pivot) {
               end--;
           }
           //右边的值等于mid目标值，则使左边指针向左移
           if (nums[end] == pivot) {
               start++;
           }
       }

       if (start == end) { //退出循环防止栈溢出
           start++;
           end--;
       }
       
       if (left < end) {
           quicksort(nums, left, end);   //向左递归
       }
       
       if (right > start) {
           quicksort(nums, start, right); //向右递归
       }
   }

归并排序

好难好难，需要先理解思路，再考虑编码实现：
- 归并排序简单来讲，就是将大的序列视为若干小的数组，利用归并思想实现排序的方法。
- 分治策略（分：把问题分成小的问题分别求解；治：将分的阶段得到的各答案合在一起）

位运算

基础知识（青铜排序）

原码、反码、补码
与运算 &，或运算 |，异或运算 ^，取反运算 !
移位运算：左移、算术右移、逻辑右移
移位运算与乘除法的关系

字符串

基础知识（青铜挑战）

转换成小写字母

遍历该字符串，依次转换为小写，存入新的字符串中
具体代码如下：

public static String toLowerCase(String s) {
      int n = s.length();
      char[] chars = s.toCharArray();
      for (int i = 0; i < n; ++i) {
          if (chars[i] >= 65 && chars[i] <= 90) {
              chars[i] += 32;
          }
      }
      String str = new String(chars);
      return str;
  }

实战训练（白银挑战）

反转字符串

思路：
- 使用双指针，一个在前，一个在后，相向移动，遍历字符串
- 在遍历的过程中，将两指针指向的元素交换位置
- 直到两指针相遇
具体代码如下：(2023/09/30早)

public static void reverseString(char[] s) {
       int n = s.length;
       for (int left = 0, right = n - 1; left < right; ++left, --right) {
           char tmp = s[left];
           s[left] = s[right];
           s[right] = tmp;
       }
   }

K个一组反转

仅反转字母

我们有两种思路：
- 将所有的字母压栈
- 双指针遍历字符串
压栈法：
- 遍整个字符串，将字母依次压入栈中
- 创建一个新的字符串对象，再次遍历该字符串：如果是非字母，将该字符放入新字符串；如果是字母，则从存入弹出的栈顶元素
- 直到遍历结束
具体代码如下：

public static String reverseOnlyLetters(String S) {
       Stack<Character> letters = new Stack();
       for (char c : S.toCharArray())
           if (Character.isLetter(c))
               letters.push(c);

       StringBuilder ans = new StringBuilder();
       for (char c : S.toCharArray()) {
           if (Character.isLetter(c))
               ans.append(letters.pop());
           else
               ans.append(c);
       }

       return ans.toString();
   }

双指针法：
- 定义两个指针，一个从头向后遍历，一个从后向前，维护字母字符
- 创建一个新的字符串对象，前指针遍历字符串
- 如果是非字母，则将该字符放入新字符串；如果是字母，则移动后指针，找到字母，将该字母存入新的字符串
- 直到前指针遍历结束
具体代码如下：

public static String reverseOnlyLetters2(String S) {
     if (S == null || S.length() == 0){
         return  S;
     }

     StringBuffer ans = new StringBuffer();
     int j =  S.length() - 1;
     for (int i = 0; i < S.length(); i++) {
         if(Character.isLetter(S.charAt(i))){
             while (!Character.isLetter(S.charAt(j)))
                 j--;
             ans.append(S.charAt(j--));
         }else {
             ans.append(S.charAt(i));
         }
     }
     return ans.toString();
 }

反转字符串里的单词

可以使用语言提供的方法解决：
- 将字符串按空格分开，转换为数组/集合
- 使用 reserve 方法，反转数组/集合元素
- 再将数组/集合转换为字符串
具体代码如下：(2023/09/30早)

public static String reverseWords2(String s) {
      if (s == null || s.length() == 0) {
          return s;
      }
      // 取出首尾空白字符串
      s = s.trim();
      // 分割单词
      String[] split = s.split("\\s+");
      List<String> wordList = Arrays.asList(split);
      // 反转
      Collections.reverse(wordList);
      // 转换为字符串
      return String.join(" ", wordList);
  }

验证回文串

什么是回文字符串？示例如下：

1 2	`A man, a plan, a canal: Panama 将该字符串反转后: amanaplanacanalpanama，这就是回文字符串`

我们仍然使用双指针法解决：
- 首先要做的就是遍历一遍字符串，把所有的字母都放到新的字符串中
- 再使用双指针相向遍历新字符串，遍历的的过程中，判断两指针指向元素是否相同
- 直到两指针相遇，说明是回文字符串
具体代码如下：

public static boolean isPalindrome(String s) {
       StringBuffer sgood = new StringBuffer();
       int length = s.length();
       for (int i = 0; i < length; i++) {
           char ch = s.charAt(i);
           if (Character.isLetterOrDigit(ch)) {
               sgood.append(Character.toLowerCase(ch));
           }
       }
       StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
       return sgood.toString().equals(sgood_rev.toString());
   }

字符串里的第一个唯一字符

最好用的方法：Hash法
- 定义一个 Map 集合，我们遍历一遍字符串，使用 Map 记录每个字符出现过的次数
- 再次遍历该 Map，取到第一个出现次数大于1的元素
具体代码如下：(2023/09/30早)

public static int firstUniqChar(String s) {
     if (s == null || s.length() == 0) {
         return 0;
     }
     Map<Character, Integer> frequency = new HashMap<Character, Integer>();
     for (int i = 0; i < s.length(); ++i) {
         char ch = s.charAt(i);
         frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
     }
     for (int i = 0; i < s.length(); ++i) {
         if (frequency.get(s.charAt(i)) == 1) {
             return i;
         }
     }
     return -1;
 }

判断是否互为字符重排

什么是字符重排？就是将其中一个字符串中的字符顺序打乱重新排列后，能否成为另一个字符串
这个就更好办了，我们有两种思路：
- 排序法
- Map法
排序法：
- 分别快速地对两个字符串中的字符进行排序
- 然后直接比较两字符串是否相等即可
具体代码如下：

public static boolean checkPermutation(String s1, String s2) {
      // 将字符串转换成字符数组
      char[] s1Chars = s1.toCharArray();
      char[] s2Chars = s2.toCharArray();
      // 对字符数组进行排序
      Arrays.sort(s1Chars);
      Arrays.sort(s2Chars);
      // 再将字符数组转换成字符串，比较是否相等
      return new String(s1Chars).equals(new String(s2Chars));
  }

Map法：
- 分别统计两个字符串中，各个字符出现的次数
- 再次比较字符出现次数，只有每个字符出现的次数都一样，才能算两字符串互为字符重排
具体代码如下：(2023/09/30早)

public static boolean checkPermutation2(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }

        char[] s1chars = s1.toCharArray();
        HashMap<Character, Integer> s1Map = getMap(s1);
        HashMap<Character, Integer> s2Map = getMap(s2);
        for (char s1char : s1chars) {
            if (!s2Map.containsKey(s1char) || (int) s1Map.get(s1char) != (int) s2Map.get(s1char)) {
                return false;
            }
        }
        return true;
    }

    private static HashMap<Character, Integer> getMap(String str) {
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chars = str.toCharArray();
        for (char aChar : chars) {
            map.put(aChar, map.getOrDefault(aChar, 0) + 1);
        }
        return map;
    }

堆结构

基础知识（青铜挑战）

堆的概念：堆是一种数据结构，按照完全二叉树的存储顺序，将数据存储在一个一维数组中
- 大顶堆：任意节点值均大于它的左右节点值
- 小顶堆：任意节点值均大于它的左右节点值
堆的构造过程：按照层次将所有元素一次添入二叉树中，再不断调整，最终使其符合堆结构
堆中插入元素：确认插入位置能够保持原二叉树为完全二叉树，再自底向上调整，保证每一层的子树都符合堆结构
堆中删除元素：一般都是删除堆顶元素，将堆顶元素与二叉树最后一个元素对调，删除堆顶元素后，再依次调整每一层的各子树

实战训练（白银挑战）

数组中查找第K大的元素

这个问题很重要很经典，解决方法也有多种，我们提三个：选择法、快排、堆排序
堆排序：
- 我们需要在数组中查找第K大的元素，就创建一个大小为K的小顶堆
- 堆满后，只有比堆顶元素小的元素，才可以插入堆中；新插入的元素先覆盖堆顶元素后，再调整
- 将数组序列依次插入堆中，每插入一个元素，就调整堆使之符合堆的结构
- 全部序列入堆完毕后，堆顶元素就是要查找的第K大的元素了
具体代码如下：

public static int findKthLargest(int[] nums, int k) {
        if (k > nums.length) {
            return -1;
        }
        int len = nums.length;
        // 使用一个含有 k 个元素的最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
        for (int i = 0; i < k; i++) {
            minHeap.add(nums[i]);
        }
        for (int i = k; i < len; i++) {
            // 看一眼，不拿出，因为有可能没有必要替换
            Integer topEle = minHeap.peek();
            // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
            if (nums[i] > topEle) {
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }
        return minHeap.peek();
    }

堆排序

堆排序是什么原理呢？
构造大顶堆，依次取出堆顶元素；每取出一个堆顶元素后，重新调整堆，这样得到的序列就是从大到小排序的（降序排序）
小顶堆同理，得到的序列就是从小到大排序的（升序排序）
升序用小，降序用大 （2023/09/30晚）

合并K个有序链表

图算法

基础知识（青铜挑战）

有向图、无向图
边、弧
节点的度、入度、出度
描述节点之间的关系：<V1,V2> (V1,V2)
路径、回路
权、网
连通图、连通分量、强连通图
生成树、生成森林

实战训练（白银挑战）

图的存储

图的遍历

最小生成树问题

最短路径问题

排序算法

推荐阅读：十大经典排序算法总结 | JavaGuide(Java面试 + 学习指南)
各算法动态图演示：各算法动态图演示（2023/10/17完晚）
数据结构与算法精讲：数据结构与算法精讲

冒泡排序

/**
 * 冒泡排序
 * @param arr
 * @return arr
 */
public static int[] bubbleSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // Set a flag, if true, that means the loop has not been swapped,
        // that is, the sequence has been ordered, the sorting has been completed.
        boolean flag = true;
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
       // Change flag
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
    return arr;
}

选择排序

/**
 * 选择排序
 * @param arr
 * @return arr
 */
public static int[] selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
    return arr;
}

插入排序

/**
 * 插入排序
 * @param arr
 * @return arr
 */
public static int[] insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int preIndex = i - 1;
        int current = arr[i];
        while (preIndex >= 0 && current < arr[preIndex]) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex -= 1;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

快速排序

public static void quickSort(int[] arr, int low, int high) {
        // 判断递归结束的条件
        if (low >= high) {
            return;
        }
        // 定义快慢指针、基准值
        int point = arr[low];

        int slow = low;
        int fast = low + 1;

        // 快指针检索大数
        while (fast <= high) {
            // 慢指针维护小数
            if (arr[fast] < point) {
                // todo 0
                slow++;
                int temp = arr[slow];
                arr[slow] = arr[fast];
                arr[fast] = temp;
            }
            fast++;
        }

        // 返回基准值
        // todo 1
        int temp = arr[slow];
        arr[slow] = arr[low];
        arr[low] = temp;

        quickSort(arr, low, slow - 1);
        quickSort(arr, slow + 1, high);
    }

各排序算法比较

贪心

每一步中寻找最优解，或者说相对最优解的算法思想

小试牛刀

分发饼干

你有几个孩子和几摞饼干，孩子有胃口，饼干有数量，尽可能分发饼干以满足胃口大的孩子
解题思路：
- 要尽可能满足胃口大的孩子，我们不妨把孩子们按胃口排序，从胃口最大的孩子开始，分发饼干
- 当然，与之对应的，每一摞饼干也要按照数量排好序
- 从胃口大的孩子开始，从数量多的饼干开始，依次给孩子分配
- 如果饼干不满足该孩子的胃口（此时饼干数量最多了），那就分配给下一个孩子（他的胃口更小），看能不能满足这个孩子的胃口
- 以此类推，饼干不满足孩子胃口，就找下一个孩子；满足了，再拿下一摞饼干进行分配
- 这样就能保证：能够合理分配这些饼干来尽可能满足胃口大的孩子 （2023/10/19晚）
具体代码如下：

/**
     * 分发饼干
     *
     * @param g 孩子数
     * @param s 饼干数
     * @return 成功分配的孩子数
     */
    public static int findContentChildren(int[] g, int[] s) {
        // 排列孩子、饼干
        Arrays.sort(g);
        Arrays.sort(s);
        // 记录成功分配的孩子数、每摞饼干数
        int count = 0;
        int start = s.length - 1;
        // 遍历孩子的胃口
        for (int index = g.length - 1; index >= 0; index--) {
            if (start >= 0 && g[index] <= s[start]) {
                start--;
                count++;
            }
        }
        // 返回成功分配的孩子数
        return count;
    }

/**
     * 分发饼干
     *
     * @param g 孩子数
     * @param s 饼干数
     * @return 成功分配的孩子数
     */
    public static int findContentChildren(int[] g, int[] s) {
        // 排列孩子、饼干
        Arrays.sort(g);
        Arrays.sort(s);
        // 记录成功分配的孩子数、每摞饼干数
        int count = 0;
        int index = g.length - 1;
        int start = s.length - 1;
        // 遍历孩子的胃口
        while (index >= 0) {
            if (start >= 0 && g[index] <= s[start]) {
                start--; 
                count++;
            }
            index--;
        }
        // 返回成功分配的孩子数
        return count;
    }

柠檬水找零

情景：
- 你在卖柠檬水，一杯柠檬水 5 块钱，顾客排队购买你的柠檬水
- 每位顾客只买一杯，他们给你的金额有5块、10块和20块
- 最初你手头的余额为0，确保给每位顾客正确找零
解题思路：
- 顾客给你5块钱，你就照收不误
- 顾客给你10块钱，你得找他5块钱
- 顾客给你20块钱，你得找他5块钱和10块钱（优先），或者找他3张5块钱（其次）
- 也就是说，20块钱是不会用来找零钱的，我们就不关注手头20块钱的数目了
- 如果你找不了零钱，那一定是5块和10块其一不够找零钱了，我们只需关注这两种面值即可
- 确保给每位顾客正确找零，就要保证每处理一个顾客（每次找完零钱）后，手头的5块和10块不能“欠费”（2023/10/19晚）
具体代码如下：

/**
    * 柠檬水找零
    * @param bills 排队中的顾客
    * @return 能否全部找零
    */
   public static boolean lemonadeChange(int[] bills) {
       // 这里只表示5元和10元纸币的数量，而不是总金额
       int cash_5 = 0;
       int cash_10 = 0;
       for (int i = 0; i < bills.length; i++) {
           // 收到5块钱
           if (bills[i] == 5) {
               cash_5++;
               // 收到10块钱
           } else if (bills[i] == 10) {
               cash_5--;
               cash_10++;
               // 收到20块钱
           } else if (bills[i] == 20) {
               if (cash_10 > 0) {
                   cash_10--;
                   cash_5--;
               } else {
                   cash_5 -= 3;
               }
           }
           if (cash_5 < 0 || cash_10 < 0) return false;
       }
       return true;
   }

分发糖果

情景：
- 你有几个孩子，糖果是无限制的，每个孩子都有各自的评分
- 要求根据他们的评分合理地给他们分发糖果，并要求用最少的糖果数完成
解题思路：
具体代码如下：

public static int candy(int[] ratings) {
        int[] candyVec = new int[ratings.length];
        candyVec[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candyVec[i] = candyVec[i - 1] + 1;
            } else {
                candyVec[i] = 1;
            }
        }
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        int ans = 0;
        for (int s : candyVec) {
            ans += s;
        }
        return ans;
    }

高频问题

判断区间是否重叠

情景：

输入：intervals = [[0, 30], [15, 20], [5, 10]]

解释：存在重叠区间

详情如下图所示：

解题思路：（2023/10/22晚）
- 遍历每一个区间，相邻的两个区间作比较
- 如果前区间的尾部大于后区间的首部，就说明两区间重叠了
具体代码如下：

public static boolean canAttendMeetings(int[][] intervals) {
      // 将区间按照会议开始实现升序排序
      Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
      // 遍历会议，如果下一个会议在前一个会议结束之前就开始了，返回 false。
      for (int i = 1; i < intervals.length; i++) {
          if (intervals[i][0] < intervals[i - 1][1]) {
              return false;
          }
      }
      return true;
  }

区间合并

情景：

输入：intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

输出：[[1, 6], [8, 10], [15, 18]]

解释：区间 [1, 3] 和 [2, 6] 重叠, 将它们合并为 [1, 6]

详情如下图所示：

解题思路（2023/10/22晚）
- 还是遍历每一个区间，判断相邻的两个区间是否重合
- 如果不重合，就继续向后遍历区间；如果重合，就合并两区间·
- 判断是否重合就能确定是否需要合并了，那么具体该如何合并呢？我们拿一个新的数组来维护合并区间后的新数组
  - 合并：合并后的区间尾部取重合区间尾部的最大的那个，继续向后遍历区间
  - 维护新的区间，一直比较新数组的尾部，直到不合并才开辟新区间（++idx）
具体代码如下：

public static int[][] merge(int[][] intervals) {
      // 先按照区间起始位置排序
      Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
      // 遍历区间
      int[][] res = new int[intervals.length][2];
      int idx = -1;
      for (int[] interval : intervals) {
          // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，说明不重叠。
          // 则不合并，直接将当前区间加入结果数组。
          if (idx == -1 || interval[0] > res[idx][1]) {
              res[++idx] = interval;
          } else {
              // 反之说明重叠，则将当前区间合并至结果数组的最后区间
              res[idx][1] = Math.max(res[idx][1], interval[1]);
          }
      }
      return Arrays.copyOf(res, idx + 1);
  }

// 先按照区间起始位置排序
     Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
     // 遍历区间
     int[][] res = new int[intervals.length][2];

     int idx = 0;
     if (intervals.length > 0) {
         res[idx] = intervals[0];
     }

     for (int i = 1; i < intervals.length; i++) {
         // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，说明不重叠。
         // 则不合并，直接将当前区间加入结果数组。
         if (intervals[i][0] > res[idx][1]) {
             res[++idx] = intervals[i];
         } else {
             // 反之说明重叠，则将当前区间合并至结果数组的最后区间
             res[idx][1] = Math.max(res[idx][1], intervals[i][1]);
         }
     }
     return Arrays.copyOf(res, idx + 1);

区间插入

情景

输入：intervals = [[1, 3], [6, 9]], newInterval = [2, 5]

输出：[1, 5], [6, 9]

解释：新区间 [2, 5] 和 [1, 3] 重叠, 因此合并成为 [1, 5]

详情可参考下图：

解题思路（2023/10/22晚）
- 我们仍然拿一个新数组来维护结果集
- 遍历所有区间，将新区间左边且不重合的区间加入结果集（区间尾部小于新区间首部，就说明该区间在新区间的左边且不重合）
- 再次遍历所有区间，合并与新区间重合的区间（在经过第一轮遍历筛选后，这次遍历时，区间首部小于新区间尾部的都属于重合）
- 最后剩下的区间就属于新区间右边且不重合的区间了，直接挨个放进结果集就行
具体代码如下：

public static int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length + 1][2];
        int idx = 0;
    
        // 遍历区间列表：
        // 首先将新区间左边且相离的区间加入结果集
        int i = 0;
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            res[idx++] = intervals[i++];
        }
    
        // 判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，
        // 将最终合并后的新区间加入结果集
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
    
        res[idx++] = newInterval;
        // 最后将新区间右边且相离的区间加入结果集
        while (i < intervals.length) {
            res[idx++] = intervals[i++];
        }

        return Arrays.copyOf(res, idx);
    }

滑动窗口

高频问题

最小覆盖子串

// 用于记录需要的字符和窗口中的字符及其出现的次数
   Map<Character, Integer> need = new HashMap<>();
   Map<Character, Integer> window = new HashMap<>();
   // 统计 t 中各字符出现次数
   for (char c : t.toCharArray()) 
       need.put(c, need.getOrDefault(c, 0) + 1);

   int left = 0, right = 0;
   int valid = 0; // 窗口中满足需要的字符个数
   // 记录最小覆盖子串的起始索引及长度
   int start = 0, len = Integer.MAX_VALUE;
   while (right < s.length()) {
       // c 是将移入窗口的字符
       char c = s.charAt(right);
       // 扩大窗口
       right++;
       // 进行窗口内数据的一系列更新
       if (need.containsKey(c)) {
           window.put(c, window.getOrDefault(c, 0) + 1);
           if (window.get(c).equals(need.get(c)))
               valid++; // 只有当 window[c] 和 need[c] 对应的出现次数一致时，才能满足条件，valid 才能 +1
       }

       // 判断左侧窗口是否要收缩
       while (valid == need.size()) {
           // 更新最小覆盖子串
           if (right - left < len) {
               start = left;
               len = right - left;
           }
           // d 是将移出窗口的字符
           char d = s.charAt(left);
           // 缩小窗口
           left++;
           // 进行窗口内数据的一系列更新
           if (need.containsKey(d)) {
               if (window.get(d).equals(need.get(d)))
                   valid--; // 只有当 window[d] 内的出现次数和 need[d] 相等时，才能 -1
               window.put(d, window.get(d) - 1);
           }
       }
   }

   // 返回最小覆盖子串
   return len == Integer.MAX_VALUE ?
       "" : s.substring(start, start + len);

字符串排列

HashMap<Character, Integer> need = new HashMap<>();
   HashMap<Character, Integer> window = new HashMap<>();
   for (int i = 0; i < t.length(); i++) {
       char c = t.charAt(i);
       need.put(c, need.getOrDefault(c, 0) + 1);
   }

   int left = 0, right = 0;
   int valid = 0;
   while (right < s.length()) {
       char c = s.charAt(right);
       right++;
       if (need.containsKey(c)) {
           window.put(c, window.getOrDefault(c, 0) + 1);
           if (window.get(c).equals(need.get(c)))
               valid++;
       }

       // 判断左侧窗口是否要收缩
       while (right - left >= t.length()) {
           // 在这里判断是否找到了合法的子串
           if (valid == need.size())
               return true;
           char d = s.charAt(left);
           left++;
           if (need.containsKey(d)) {
               if (window.get(d).equals(need.get(d)))
                   valid--;
               window.put(d, window.getOrDefault(d, 0) - 1);
           }
       }
   }
   // 未找到符合条件的子串
   return false;

找所有字母异位词

Map<Character, Integer> need = new HashMap<>();
  Map<Character, Integer> window = new HashMap<>();
  for (int i = 0; i < t.length(); i++) {
      char c = t.charAt(i);
      need.put(c, need.getOrDefault(c, 0) + 1);
  }

  int left = 0, right = 0;
  int valid = 0;
  List<Integer> res = new ArrayList<>(); // 记录结果
  while (right < s.length()) {
      char c = s.charAt(right);
      right++;
      // 进行窗口内数据的一系列更新
      if (need.containsKey(c)) {
          window.put(c, window.getOrDefault(c, 0) + 1);
          if (window.get(c).equals(need.get(c))) {
              valid++;
          }
      }
      // 判断左侧窗口是否要收缩
      while (right - left >= t.length()) {
          // 当窗口符合条件时，把起始索引加入 res
          if (valid == need.size()) {
              res.add(left);
          }
          char d = s.charAt(left);
          left++;
          // 进行窗口内数据的一系列更新
          if (need.containsKey(d)) {
              if (window.get(d).equals(need.get(d))) {
                  valid--;
              }
              window.put(d, window.get(d) - 1);
          }
      }
  }
  return res;

最长无重复字符串

Map<Character, Integer> window = new HashMap<>();

  int left = 0, right = 0;
  int res = 0; // 记录结果
  while (right < s.length()) {
      char c = s.charAt(right);
      right++;
      // 进行窗口内数据的一系列更新
      window.put(c, window.getOrDefault(c, 0) + 1);
      // 判断左侧窗口是否要收缩
      while (window.get(c) > 1) {
          char d = s.charAt(left);
          left++;
          // 进行窗口内数据的一系列更新
          window.put(d, window.get(d) - 1);
      }
      // 在这里更新答案
      res = Math.max(res, right - left);
  }
  return res;

算法 > 经验

#经验 #算法

探索算法学习之旅：经验分享与解题思路

https://test.atomgit.net/memory_blog/2023/07/17/探索算法学习之旅：经验分享与解题思路/

作者

Memory

发布于

2023年7月17日

更新于

2024年4月24日

许可协议

浴火重生：从挫败到成功，前端框架的疑难杂症解决之道上一篇

解决 Git 远程推送报错的终极指南下一篇

探索算法学习之旅：经验分享与解题思路

破冰

脑力激荡

链表基础

基础知识（青铜挑战）

单链表基础及构造方法

链表的内部结构

以下是我对单链表的理解：（2023/07/17午）

链表的构造

链表的构造过程很简单：

创建头节点，创建head指针指向头节点

依次创建每个节点，初始化其数据域，并令前驱节点的指针域指向该节点

链表创建完成，返回该链表的head指针

下面给出具体的代码实现

遍历链表

打印链表：头指针依次向后移动，打印每个节点的数据域

获取链表长度：头指针依次向后移动，累加节点个数，打印链表长度

代码实现如下：（2023/07/17午）

链表插入

向链表中插入节点分以下三种情况：

表头插入：创建新节点，新节点指针域指向原头节点；head指针指向新节点

在表中插入：遍历到插入位置的前驱节点，依次为新节点分配后继节点和前驱节点

表尾插入：可视为 2 的特殊情况，新节点的后继节点为 NULL

代码设计如下：（2023/07/17午）

链表删除

删除链表节点同样分三种情况：

删除表头元素：head指针指向要删除节点的后继节点

删除表中元素：拿到要删除节点的前驱节点的指针域，指向要删除节点的后继节点

删除表尾元素：可视为 2 的特殊情况，要删除节点的后继节点为 NULL

代码设计如下：

双向链表设计

双向链表的内部结构

以下是我对双向链表的理解（2023/07/17午）

链表的构造

代码设计如下：

遍历链表

head指针依次向后移动，遍历每个节点，输出数据域的值：

链表插入

向链表中插入节点分以下三种情况：

表头插入：新建新节点，原头节点作新节点的后继节点，新节点作为原头结点的前驱节点，head指针指向新节点

表尾插入：新建新节点，原尾节点作新节点的前驱节点，新节点作为头结点的后继节点，tail指针指向新节点

表中插入

代码实现如下：

链表删除

删除双向链表中的节点分以下三种情况：

表头删除：head指针指向原头节点的后继节点，并将该后继节点的前驱指针置空（2023/07/17午）

表尾删除：tail指针指向原尾节点的前驱节点，并将该前驱节点的后继指针置空

表中删除

代码实现如下：

实战训练（白银挑战）

两个链表第一个公共子节点

前情提要：什么情况下，两条链表存在公共子节点呢？如下图所示：（2023/07/19午）

显而易见，c1、c2、c3均为两链表的公共子节点，且c1是两链表的第一个公共子节点

我们先废话少说，给出四种解题思路：

哈希和集合，代码如下：

栈，代码如下：

两条链表拼接，代码如下：

这里有必要解释一下这个判断的作用了：

考虑这个问题：当前链表遍历结束后，什么情况下允许切换遍历另一条链表呢？

答案包括两种情况：未找到公共节点 / 第一次切换遍历链表结束

未找到公共节点很好理解，只有切换遍历另一条链表，才能判断是否有公共节点

第一次切换遍历链表结束，此时p1、p2指针均为null，说明两链表就没有公共节点，我们就结束链表的遍历

所以结束两链表的遍历（p1 == p2）有两种情况：第一个公共节点已找到/不存在公共节点

差和双指针

上面代码里的注释，已经把解题思路解释的很清晰了

基于我个人的理解，下面讲解一下这些方法的共同点，也就是解题思路的形成过程：

这就是查找两链表的第一个公共节点的解题思路了，希望对你有帮助

回文链表的判断

给出一个链表，判断其是否为回文链表，那什么是回文链表？

以下即为一条回文链表：

即对回文链表正序遍历和倒序遍历，得到的结果是一样的

这种题解法很多，我们列举常见的、简单的且容易理解的解法：

压栈法，具体代码如下：

倒序链表法，代码如下：

根据原链表构造一条倒序链表，遍历这两条链表

此外还有双指针法（之后双指针专题练习结束后回来补充）、递归法（不推荐掌握，容易绕晕）

合并两条有序链表

常见的解法就是构造第三条链表，然后依次遍历两条有序链表，比较各节点大小，依次连接到新链表中，整个过程如下图所示：

由于两条链表长度不一定相同，可能出现一条链表遍历完，另一条链表还没有的情况，这其实是一个优化点

具体代码如下：