剑指offer算法总结

siR6jVKErSemtfx

专题1：链表

学链表，我们需要掌握什么？

链表在面试中出现频率排行前2的算法题，因为链表题的特点是：描述非常简单，基本不用花时间去读题，在面试有些的三四十分钟里，链表非常受欢迎。

我们先来说一说学习链表时，我们最需要掌握的是什么？

首先我认为大部分的链表题，解法思路都相对简单，双指针占一半以上，但是上了战场，写链表题的时候，非常容易出错，常见错误是：

1、没有考虑节点为 null 导致空指针异常。

2、容易出现节点位置定位出错，比如往前多走了一步，或者少走了一步。

所以我觉得，做链表题，最重要的就是要掌握：

1、规定好自己的模版，比如我习惯自己弄一个辅助头节点，确定下来之后，就一直这么做，不要变来变去。

2、做的时候，多考虑一步，就是在用 .next 节点的时候，会不会出现异常。

上面这两天是帮助你可以做起题来错误更少，速度更快，除了这两个之外，做链表的题还有非常重要的一个点，那就是：积累解题思路

链表的题型不多，也不难理解，很好积累，所以大家可以多看几道不同类型的题，不然遇到完全陌生的题，那你可能就真的不会的，因为链表的暴力解法都不难。

不过话说回来，在面试中，题型不多，出现最多的还是删除倒数第 K 个节点，反转，交点这一些，思路不难，重在考察代码能力。

所以我觉得，学习链表最大的技巧就是多做几遍。

算法技巧：巧用双指针

对于双指针，在做关于单链表的题是特别有用，比如“判断单链表是否有环”、“如何一次遍历就找到链表中间位置节点”、“单链表中倒数第 k 个节点”等问题。对于这种问题，我们就可以使用双指针了，会方便很多。我顺便说下这三个问题怎么用双指针解决吧。

例如对于第一个问题

我们就可以设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移动一个节点，而快指针一次移动两个节点，如果该链表没有环，则快指针会先遍历完这个表，如果有环，则快指针会在第二次遍历时和慢指针相遇。

对于第二个问题

一样是设置一个快指针和慢指针。慢的一次移动一个节点，而快的两个。在遍历链表的时候，当快指针遍历完成时，慢指针刚好达到中点。

对于第三个问题

设置两个指针，其中一个指针先移动k个节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完成的时候，第二个指针正好处于倒数第k个节点。

你看，采用双指针方便多了吧。所以以后在处理与链表相关的一些问题的时候，可以考虑双指针哦。

也就是说，你掌握了双指针，意味着掌握了大部分常规链表题，当然，双指针不一定就是快慢指针哦，另外就是，双指针另外一个应用的比较多的领域就是：在排序数组在求和，关于这个，后续应该也会有题讲到。

Day1:4道常规题

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

示例 1:
1
2
3
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
1
2
3
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：

题目保证链表中节点的值互不相同

若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

解法一：

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val==val)return head.next;
        ListNode dummy=new ListNode(-1,head);
        while(dummy!=null){
            if(dummy.next!=null){
                if(dummy.next.val==val){
                    ListNode temp=dummy.next;
                    dummy.next=temp.next;
                    temp.next=null;
                }
            }
            dummy=dummy.next;
        }
        return head;
    }
}

解法二：双指针

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val==val)return head.next;
        ListNode pre=head,cur=head.next;
        while(cur!=null){
            if(cur.val==val){
                pre.next=cur.next;
                cur.next=null;
                break;
            }
            pre=pre.next;
            cur=cur.next;
        }
        return head;
    }
}

剑指 Offer 22. 链表中倒数第k个节点

给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。

示例 1：
1
2
输入：head = [2,4,7,8], cnt = 1
输出：8
提示：

1 <= head.length <= 100

0 <= head[i] <= 100

1 <= cnt <= head.length

解法一：直观做法，遍历两遍

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        int len=0;
        ListNode p=head;
        while(p!=null){
            p=p.next;
            len++;
        }
        int id=len-cnt;
        p=head;
        while(p!=null){
            if(id==0)return p;
            p=p.next;
            id--;
        }
        return null;
    }
}

解法二：递归解法

class Solution {
    // 定义一个全局变量用于记录倒数位置
    private int index = 0;
    public ListNode trainingPlan(ListNode head, int cnt) {
        // 递归的终止条件
        if (head == null) {
            return null;
        }
        // 递归到链表的下一节点
        ListNode node = trainingPlan(head.next, cnt);
        // 回溯时增加索引计数
        index++;
        // 当计数等于 cnt 时，返回当前节点
        if (index == cnt) {
            return head;
        }
        // 向上返回找到的节点
        return node;
    }
}

解法三：双指针法

class Solution {
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode former = head, latter = head;
        for(int i = 0; i < cnt; i++) {
            if(former == null) return null;
            former = former.next;
        }
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

剑指 Offer 25. 合并两个排序的链表

给定两个以 有序链表 形式记录的训练计划 l1、l2，分别记录了两套核心肌群训练项目编号，请合并这两个训练计划，按训练项目编号升序记录于链表并返回。

注意：新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
1
2
输入：l1 = [], l2 = []
输出：[]
示例 3：
1
2
输入：l1 = [], l2 = [0]
输出：[0]
提示：
1
0 <= 链表长度 <= 1000

解法一：递归

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }else if(l2==null){
            return l1;
        }else if(l1.val<l2.val){
            l1.next=trainningPlan(l1.next,l2);
            return l1;
        }else{
            l2.next=trainningPlan(l1,l2.next);
            return l2;
        }
    }
}

解法二：双指针

class Solution {
    public ListNode trainningPlan(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;
        }
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }
}

剑指 Offer 52. 两个链表的第一个公共点

某教练同时带教两位学员，分别以链表 l1、l2 记录了两套核心肌群训练计划，节点值为训练项目编号。两套计划仅有前半部分热身项目不同，后续正式训练项目相同。请设计一个程序找出并返回第一个正式训练项目编号。如果两个链表不存在相交节点，返回 null 。

如下面的两个链表：

在节点 c1 开始相交。

输入说明：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0

l1 - 第一个训练计划链表

l2 - 第二个训练计划链表

skip1 - 在 l1 中（从头节点开始）跳到交叉节点的节点数

skip2 - 在 l2 中（从头节点开始）跳到交叉节点的节点数

程序将根据这些输入创建链式数据结构，并将两个头节点 head1 和 head2 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。

示例 1：
1
2
3
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
解释：第一个正式训练项目编号为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
1
2
3
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
解释：第一个正式训练项目编号为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
1
2
3
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：两套计划完全不同，返回 null。从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
注意：

如果两个链表没有交点，返回 null.

在返回结果后，两个链表仍须保持原有的结构。

可假定整个链表结构中没有循环。

程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解法一：双指针，简单的数学计数

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null)return null;
        ListNode l1=headA,l2=headB;
        while(l1!=null||l2!=null){
            if(l1==null)l1=headB;
            if(l2==null)l2=headA;
            if(l1==l2)return l1;
            l1=l1.next;
            l2=l2.next;
        }
        return null;
    }
}

Day2:3道题 + 1个面试找错误

剑指 Offer 06. 从尾到头打印链表

书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。

示例 1：
1
2
3
输入：head = [3,6,4,1]

输出：[1,4,6,3]
提示：
1
0 <= 链表长度 <= 10000

解法一：递归

class Solution {
    ArrayList<Integer>tmp=new ArrayList<Integer>();
    public int[] reverseBookList(ListNode head) {
        recur(head);
        int[] res=new int[tmp.size()];
        for(int i=0;i<res.length;i++){
            res[i]=tmp.get(i);
        }
        return res;
    }
    void recur(ListNode head){
        if(head==null)return;
        recur(head.next);
        tmp.add(head.val);
    }
}

解法二：辅助栈法

class Solution {
    public int[] reverseBookList(ListNode head) {
        LinkedList<Integer>stack=new LinkedList<Integer>();
        while(head!=null){
            stack.addLast(head.val);
            head=head.next;
        }
        int[] res=new int[stack.size()];
        for(int i=0;i<res.length;i++){
            res[i]=stack.removeLast();
        }
        return res;
    }
}

剑指 Offer 24. 反转链表

给定一个头节点为 head 的单链表用于记录一系列核心肌群训练编号，请将该系列训练编号倒序记录于链表并返回。

示例 1：
1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
1
2
输入：head = [1,2]
输出：[2,1]
示例 3：
1
2
输入：head = []
输出：[]
提示：

链表中节点的数目范围是 [0, 5000]

-5000 <= Node.val <= 5000

解法一：递归

class Solution {
    public ListNode trainningPlan(ListNode head) {
        if(head==null)return head;
        if(head.next==null)return head;
        ListNode temp=trainningPlan(head.next);
        head.next.next=head;
        head.next=null;
        return temp;
    }
}

解法二：迭代

class Solution {
    public ListNode trainningPlan(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：
1
2
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
1
2
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
1
2
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
1
2
3
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：

-10000 <= Node.val <= 10000

Node.random 为空（null）或指向链表中的节点。

节点数目不超过 1000 。

解法一：哈希表

用哈希映射，在原链表与新链表之间建立联系

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }
}

方法二：拼接 + 拆分

考虑构建原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，如此便可在访问原节点的 random 指向节点的同时找到新对应新节点的 random 指向节点。

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        // 1. 复制各节点，并构建拼接链表
        while(cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        // 2. 构建各新节点的 random 指向
        cur = head;
        while(cur != null) {
            if(cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        // 3. 拆分两链表
        cur = head.next;
        Node pre = head, res = head.next;
        while(cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null; // 单独处理原链表尾节点
        return res;      // 返回新链表头节点
    }
}

一道常见错误

面试题目：给你一个链表，删除链表的倒数第n个节点，并且返回链表的头节点

参考答案：没有考虑空指针问题，如果删除的是第一个节点，也就是头节点，那么会出现异常。因为在第一个 while循环之后，fast 为 null，这样就无法进去第二个while循环，此时 pre 就一直为 null，最后调用 pre.next 就会出问题。

Day3:复杂链表题

字节真题：单链表相加

LCR 025. 两数相加 II

注意，不允许使用栈，队列等数据结构。

难点就是还得进位，而且链表只能前进不能后退。

思路：可以先它他们进行反转，相加之后，得到结果，再把结果进行反转

解法一：栈

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<Integer>();
        Deque<Integer> stack2 = new ArrayDeque<Integer>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode ans = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int a = stack1.isEmpty() ? 0 : stack1.pop();
            int b = stack2.isEmpty() ? 0 : stack2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            ListNode curnode = new ListNode(cur);
            curnode.next = ans;
            ans = curnode;
        }
        return ans;
    }
}

解法二：翻转链表

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 先反转链表
        ListNode p1 = reverse(l1);
        ListNode p2 = reverse(l2);
        // 记录进位
        int tag = 0;
        ListNode prev = null;
        ListNode curr = null;
        // 如果两个数不为null，或者还有null
        while(p1!=null || p2!=null || tag!=0){
            int a = 0;
            int b = 0;
            if(p1!=null){
                a = p1.val;
            }
            if(p2!=null){
                b = p2.val;
            }
            int sum = a+b+tag;
            if(sum > 9){
                sum = sum%10;
                tag = 1;
            }else{
                tag = 0;
            }
            // 不断进位
            curr = new ListNode(sum, prev);
            prev = curr;
            if(p1!=null){
                p1 = p1.next;
            }
            if(p2!=null){
                p2 = p2.next;
            }
        }
        return curr;
    }

    public ListNode reverse(ListNode head){
        ListNode node = head;
        ListNode prev = null;
        while(node != null){
            ListNode next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }
}

百度真题：三等分环形链表

题目：给一个环形链表，请你将他三等分。

面试分析：对于这种题，一定要和面试官讨论一些条件，比如这个链表的节点个数是否为 3 的倍数？如果不是 3 的倍数，是否是让前面一部分的链表的节点个数多一些？

反正就是，看到一道面试题，切完不能噼里啪啦做，而是要讨论好边界条件，再去做，否则你就要自己判断所有边界，麻烦的很。

解法一：三指针

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class GetThreeListNode {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        ListNode l6 = new ListNode(6);
        ListNode l7 = new ListNode(7);
        ListNode l8 = new ListNode(8);
        ListNode l9 = new ListNode(9);
        ListNode l10 = new ListNode(10);
        ListNode l11 = new ListNode(11);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l5.next = l6;
        l6.next = l7;
        l7.next = l8;
        l8.next = l9;
        l9.next = l10;
        l10.next = l11;
        l11.next = l1;
        List<ListNode> threeListNode = getThreeListNode(l1);

        // 打印
        for(int i = 0; i < threeListNode.size(); i++){
            ListNode head = threeListNode.get(i);
            System.out.println("链表 i = " + i);
            while(head != null){
                System.out.println(head.val);
                head = head.next;
            }
        }
    }
    public static List<ListNode> getThreeListNode(ListNode head){
        if(head==null){
            List<ListNode> list = new ArrayList<>();
            list.add(null);
            list.add(null);
            list.add(null);
            return list;
        }
        ListNode l1 = head;
        ListNode l2 = head.next;
        ListNode l3 = head.next.next;
        int count =1;
        ListNode temp = head;
        while (head.next!=temp){
            count++;
            head = head.next;
        }
        if (count==1){
            List<ListNode> list = new ArrayList<>();
            temp.next = null;
            list.add(temp);
            list.add(null);
            list.add(null);
            return list;
        }
        if(count == 2){
            List<ListNode> list = new ArrayList<>();
            ListNode a =temp.next;
            temp.next = null;
            list.add(temp);
            a.next = null;
            list.add(a);
            list.add(null);
            return list;
        }
        System.out.println(count);
        List<ListNode> list= new ArrayList<>();
        if((count%3)==0){
            while(l3.next!=temp){
                l3 = l3.next.next.next;
                l2 = l2.next.next;
                l1 = l1.next;
            }
            ListNode a1 = l3.next;
            ListNode a2 = l2.next;
            ListNode a3 = l1.next;
            l1.next = null;
            l2.next = null;
            l3.next = null;
            list.add(a1);
            list.add(a2);
            list.add(a3);
        }else{
            int k = (int) Math.round(count*1.0/3)-1;
            while (k!=0){
                l2 = l2.next.next;
                l1 = l1.next;
                k--;
            }
            while(l3.next!=temp){
                l3 = l3.next;
            }
            ListNode a1 = l3.next;
            ListNode a2 = l2.next;
            ListNode a3 = l1.next;
            l1.next = null;
            l2.next = null;
            l3.next = null;
            list.add(a1);
            list.add(a3);
            list.add(a2);
        }


        return list;
    }

    public static class ListNode{
        int val;
        ListNode next;
        public ListNode(int x){
            this.val = x;
        }
    }
}

专题2：基础数据结构的视线

面试有时候会让你实现某个数据结构的一些操作，不过一般不会去让你实现一个链表啊，也不会让你去实现一个二叉树啊，但是会经常让你用队列来实现栈，或者用栈来实现队列。

这个其实也不难，主要就是考察你对基本数据结构的理解，比如栈是先进后出，而队列则先进先出，这是两种既相似又相反的数据结构，使得他们经常会被关联在一起。

不过呢，只要理解了，还是比较简单，做的也没啥技巧，所以这里也不提供什么算法思想之类的哦，最大的技巧就是自己找两组数组模拟一下。

Day4： 2道题，队列与栈的相互转换

剑指 Offer 09. 用两个栈实现队列

读者来到图书馆排队借还书，图书管理员使用两个书车来完成整理借还书的任务。书车中的书从下往上叠加存放，图书管理员每次只能拿取书车顶部的书。排队的读者会有两种操作：

push(bookID)：把借阅的书籍还到图书馆。

pop()：从图书馆中借出书籍。

为了保持图书的顺序，图书管理员每次取出供读者借阅的书籍是最早归还到图书馆的书籍。你需要返回 每次读者借出书的值 。

如果没有归还的书可以取出，返回 -1 。

示例 1：
1
2
3
4
5
6
7
8
9
输入：
["BookQueue", "push", "push", "pop"]
[[], [1], [2], []]
输出：[null,null,null,1]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.pop(); // return 1, queue is [2]
提示：

1 <= bookID <= 10000

最多会对 push、pop 进行 10000 次调用

思路：A做原栈，B做辅助栈。A中顺序，倾倒进B后为队列顺序

class CQueue {
    LinkedList<Integer> A, B;
    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }
    public void appendTail(int value) {
        A.addLast(value);
    }
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty())
            B.addLast(A.removeLast());
        return B.removeLast();
    }
}

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

方法一：两个队列

class MyStack {
    Queue<Integer>queue1;
    Queue<Integer>queue2;
    public MyStack() {
        queue1=new LinkedList<Integer>();
        queue2=new LinkedList<Integer>();
    }
    
    public void push(int x) {
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer>temp=queue1;
        queue1=queue2;
        queue2=temp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

解法二：一个队列

class MyStack {
    Queue<Integer> queue;

    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        for (int i = 0; i < n; i++) {
            queue.offer(queue.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

Day5：两道题 + 一道面试变形题

剑指 Offer 30. 包含min函数的栈

请你设计一个 最小栈 。它提供 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。

void push(int val) 将元素val推入堆栈。

void pop() 删除堆栈顶部的元素。

int top() 获取堆栈顶部的元素。

int getMin() 获取堆栈中的最小元素。

示例 1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(2);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
提示：

$-2^{31} <= val <= 2^{31} - 1$

pop、top 和 getMin 操作总是在 非空栈 上调用

push、pop、top 和 getMin 最多被调用 3 * 10^4 次

解法一：辅助栈

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

剑指 Offer 31. 栈的压入、弹出序列

现在图书馆有一堆图书需要放入书架，并且图书馆的书架是一种特殊的数据结构，只能按照一定的顺序放入和拿取书籍。

给定一个表示图书放入顺序的整数序列 putIn，请判断序列 takeOut 是否为按照正确的顺序拿取书籍的操作序列。你可以假设放入书架的所有书籍编号都不相同。

示例 1：
1
2
3
4
5
输入：putIn = [6,7,8,9,10,11], takeOut = [9,11,10,8,7,6]
输出：true
解释：我们可以按以下操作放入并拿取书籍：
push(6), push(7), push(8), push(9), pop() -> 9,
push(10), push(11),pop() -> 11,pop() -> 10, pop() -> 8, pop() -> 7, pop() -> 6
示例 2：
1
2
3
输入：putIn = [6,7,8,9,10,11], takeOut = [11,9,8,10,6,7]
输出：false
解释：6 不能在 7 之前取出。
提示：

0 <= putIn.length == takeOut.length <= 1000

0 <= putIn[i], takeOut < 1000

putIn 是 takeOut 的排列。

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : putIn) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == takeOut[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

变形题：最小栈的最优解

实现一个这样的栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值。栈里面存放的都是 int 整数，并且数值的范围是 [-100000, 100000]。要求所有操作的时间复杂度是 O(1)。
附加：如果空间复杂度也能O(1)的话可加分

解法：保存差值法

class MinStack {

    Stack<Long> stack;
    Long min;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }
    
    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0l);
            min = Long.valueOf(x);
        } else {
            stack.push((long) (x - min));
            min = Math.min(x, min);
        }
    }
    
    public void pop() {
        if (stack.peek() < 0) {
            min = min - stack.pop();
            return;
        }
        stack.pop();
    }
    
    public int top() {
        if (stack.peek() > 0) {
            return (int) (min + stack.peek());
        } else {
            return Math.toIntExact(min);
        }
    }
    
    public int min() {
        return Math.toIntExact(min);
    }
}

专题3：二叉树

考察分析+需要掌握的算法思想

链表考察频率第一，二叉树则可以是排名第二，并且考察的问题也不会很难，easy + medium 考察的比较多，和链表一样，二叉树多描述也是很简单，描述简单是考察高频的一个原因。

另外一个原因则和链表不同，链表思路简单，考察代码严谨性；而二叉树，则考察你的抽象能力，基本大多数二叉树的问题，都得用递归来处理，不然就是用队列或者栈来辅助（队列居多），而且好多还要你懂回溯的思想，这意味着，你懂二叉树，说明你至少是对一些算法思想了解的，否则你就是一脸懵逼。

下面说一说学习二叉树你需要掌握什么：

1、前中后三种遍历，你得会，怎么着得会递归的解法吧？当然，最好也要会非递归的方法。

2、能够熟悉使用递归去解决问题，部分题还得用回溯

3、掌握前中后遍历的一些关系：二叉树的问题，有时候会让你去重建一颗二叉树，这个时候你就得明白他们的一些关系了。

会了 1 和 2，你其实可以解决挺多二叉树的问题的，然后二叉树有很多打印的问题，如果你要轻松掌握打印这类问题，那你要去研究二叉树与队列的一些关系，可以说，遇到层序遍历相关，基本就是和队列相关了。

Day6：关于树深度的两道算法题

剑指 Offer 55 – I. 二叉树的深度

某公司架构以二叉树形式记录，请返回该公司的层级数。

示例 1：
1
2
3
输入：root = [1, 2, 2, 3, null, null, 5, 4, null, null, 4]
输出: 4
解释: 上面示例中的二叉树的最大深度是 4，沿着路径 1 -> 2 -> 3 -> 4 或 1 -> 2 -> 5 -> 4 到达叶节点的最长路径上有 4 个节点。
提示：

节点总数 <= 10000

解法：经典递归

class Solution {
    public int calculateDepth(TreeNode root) {
        if(root==null)return 0;
        return 1+Math.max(calculateDepth(root.left),calculateDepth(root.right));
    }
}

剑指 Offer 55 – II. 平衡二叉树】

剑指 Offer 55 – II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:
1
2
3
输入：root = [3,9,20,null,null,15,7]
输出：true 
解释：如下图
示例 2:
1
2
3
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
解释：如下图
提示：

0 <= 树的结点个数 <= 10000

方法一：后序遍历 + 剪枝（从底至顶）

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

方法二：先序遍历 + 判断深度（从顶至底）

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

Day7：3道二叉树

剑指 Offer 27. 二叉树的镜像

给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点。

示例 1：
1
2
输入：root = [5,7,9,8,3,2,4]
输出：[5,9,7,4,2,3,8]
提示：

树中节点数目范围在 [0, 100] 内

-100 <= Node.val <= 100

解法一：递归

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
}

class Solution {
    public TreeNode flipTree(TreeNode root) {
        fz(root);
        return root;
    }
    private void fz(TreeNode root){
        if(root==null)return;
        TreeNode l=root.left;
        TreeNode r=root.right;
        root.right=l;
        root.left=r;
        fz(root.left);
        fz(root.right);
    }
}

解法二：辅助栈

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>() {{ add(root); }};
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}

剑指 Offer 28. 对称的二叉树

请设计一个函数判断一棵二叉树是否 轴对称 。

示例 1：

1
2
3

输入：root = [6,7,7,8,9,9,8]
输出：true
解释：从图中可看出树是轴对称的。

示例 2：

1
2
3

输入：root = [1,2,2,null,3,null,3]
输出：false
解释：从图中可看出最后一层的节点不对称。

解法一：递归

class Solution {
    public boolean checkSymmetricTree(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

class Solution {
    public boolean checkSymmetricTree(TreeNode root) {
        return root == null || recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if(L == null && R == null) return true;
        if(L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

剑指 Offer 26. 树的子结构

给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。
注意，空树不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。

示例 1：
1
2
3
输入：tree1 = [1,7,5], tree2 = [6,1]
输出：false
解释：tree2 与 tree1 的一个子树没有相同的结构和节点值。
示例 2：
1
2
3
输入：tree1 = [3,6,7,1,8], tree2 = [6,1]
输出：true
解释：tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。
提示：
1
0 <= 节点个数 <= 10000

先序遍历树 A 中的每个节点 node ；（对应函数 isSubStructure(A, B)）
判断树 A 中以 node 为根节点的子树是否包含树 B 。（对应函数 recur(A, B)）

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

Day8：3道二叉树的基本遍历题+前中序二叉树遍历非递归实现

剑指 Offer 32 – I. 从上到下打印二叉树

一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照从左到右的顺序返回每一层彩灯编号。

示例 1：
1
2
输入：root = [8,17,21,18,null,null,6]
输出：[8,17,21,18,6]
提示：

节点总数 <= 1000

解法：层序遍历，模板

class Solution {
    public int[] decorateRecord(TreeNode root) {
        if(root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};
        ArrayList<Integer> ans = new ArrayList<>();
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }
}

剑指 Offer 32 – II. 从上到下打印二叉树

一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照从左到右的顺序返回每一层彩灯编号，每一层的结果记录于一行。

示例 1：
1
2
输入：root = [8,17,21,18,null,null,6]
输出：[[8],[17,21],[18,6]]
提示：

节点总数 <= 1000

在上一题层序遍历的基础上，本题要求将 每层打印到一行。考虑将当前全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

剑指 Offer 32 – III. 从上到下打印二叉树

一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照如下规则记录彩灯装饰结果：

第一层按照从左到右的顺序记录

除第一层外每一层的记录顺序均与上一层相反。即第一层为从左到右，第二层为从右到左。

示例 1：
1
2
输入：root = [8,17,21,18,null,null,6]
输出：[[8],[21,17],[18,6]]
提示：

节点总数 <= 1000

方法一：层序遍历 + 双端队列

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) tmp.addLast(node.val);
                else tmp.addFirst(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

方法二：层序遍历 + 双端队列（奇偶层逻辑分离）

class Solution {
    public List<List<Integer>> decorateRecord(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) deque.add(root);
        while(!deque.isEmpty()) {
            // 打印奇数层
            List<Integer> tmp = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                // 从左向右打印
                TreeNode node = deque.removeFirst();
                tmp.add(node.val);
                // 先左后右加入下层节点
                if(node.left != null) deque.addLast(node.left);
                if(node.right != null) deque.addLast(node.right);
            }
            res.add(tmp);
            if(deque.isEmpty()) break; // 若为空则提前跳出
            // 打印偶数层
            tmp = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                // 从右向左打印
                TreeNode node = deque.removeLast();
                tmp.add(node.val);
                // 先右后左加入下层节点
                if(node.right != null) deque.addFirst(node.right);
                if(node.left != null) deque.addFirst(node.left);
            }
            res.add(tmp);
        }
        return res;
    }
}

前中序非递归实现

要点总结：

非递归遍历本质上是使用栈来模拟递归调用栈。
前序遍历的关键是先访问根，并入栈时保持「先右后左」的顺序，这样出栈时就能保证先访问左子树再访问右子树。
中序遍历则先一路向左入栈，直到左子为空后开始出栈访问，然后转向右子树继续。
如果有需求，还可实现后序遍历的非递归，通常可以通过双栈或巧妙的判断条件来完成。

import java.util.*;

public class BinaryTreeTraversals {
    
    // 前序遍历（非递归）
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            // 前序为 根->左->右，栈是后进先出，所以先压右子树再压左子树
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }

    // 中序遍历（非递归）
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        
        while (cur != null || !stack.isEmpty()) {
            // 不断将左子树压入栈中
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            
            // 弹出栈顶节点并访问
            cur = stack.pop();
            result.add(cur.val);
            // 转向右子树
            cur = cur.right;
        }
        
        return result;
    }

    // 可选: 后序遍历（非递归）示例，方便参考
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode prev = null;
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode cur = stack.peek();
            // 从上到下，左右子树还未访问
            if ((cur.left == null && cur.right == null) || (prev != null && (prev == cur.left || prev == cur.right))) {
                result.add(cur.val);
                stack.pop();
                prev = cur;
            } else {
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
        
        return result;
    }

    // TreeNode 定义
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

Day9：2道关于二叉树的重建

剑指 Offer 07. 重建二叉树】

剑指 Offer 07. 重建二叉树

某二叉树的先序遍历结果记录于整数数组 preorder，它的中序遍历结果记录于整数数组 inorder。请根据 preorder 和 inorder 的提示构造出这棵二叉树并返回其根节点。

注意：preorder 和 inorder 中均不含重复数字。

示例 1：
1
2
3
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

输出: [3,9,20,null,null,15,7]
示例 2:
1
2
3
输入: preorder = [-1], inorder = [-1]

输出: [-1]
提示:

1 <= preorder.length <= 3000

inorder.length == preorder.length

-3000 <= preorder[i], inorder[i] <= 3000

inorder 均出现在 preorder

preorder 保证为二叉树的前序遍历序列

inorder 保证为二叉树的中序遍历序列

分治思想

前序遍历性质：节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。
中序遍历性质：节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。

以题目示例为例：

前序遍历划分 [ 3 | 9 | 20 15 7 ]
中序遍历划分 [ 9 | 3 | 15 20 7 ]
根据以上性质，可得出以下推论：

前序遍历的首元素为树的根节点 node 的值。
在中序遍历中搜索根节点 node 的索引，可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ] 。
根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ] 。

通过以上三步，可确定三个节点：1.树的根节点、2.左子树根节点、3.右子树根节点。

根据「分治算法」思想，对于树的左、右子树，仍可复用以上方法划分子树的左右子树。

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> hmap = new HashMap<>();
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++)
            hmap.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int root, int left, int right) {
        if(left > right) return null;                          // 递归终止
        TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
        int i = hmap.get(preorder[root]);                      // 划分根节点、左子树、右子树
        node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                           // 回溯返回根节点
    }
}

剑指 Offer 33. 二叉搜索树的后序遍历序列

请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。

示例 1：
1
2
3
输入: postorder = [4,9,6,5,8]
输出: false 
解释：从上图可以看出这不是一颗二叉搜索树
示例 2：
1
2
3
输入: postorder = [4,6,5,9,8]
输出: true 
解释：可构建的二叉搜索树如上图
提示：

数组长度 <= 1000

postorder 中无重复数字

后序遍历定义： [ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。

二叉搜索树定义：左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。

解法:递归分治

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}

解法：辅助栈

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > postorder[i])
                root = stack.pop();
            stack.add(postorder[i]);
        }
        return true;
    }
}

Day10：2道二叉树搜索树

剑指 Offer 54. 二叉搜索树的第k大节点

某公司组织架构以二叉搜索树形式记录，节点值为处于该职位的员工编号。请返回第 cnt 大的员工编号。

示例 1：
1
2
3
4
5
6
7
输入：root = [7, 3, 9, 1, 5], cnt = 2
       7
      / \
     3   9
    / \
   1   5
输出：7
示例 2：
1
2
3
4
5
6
7
8
9
输入: root = [10, 5, 15, 2, 7, null, 20, 1, null, 6, 8], cnt = 4
       10
      / \
     5   15
    / \    \
   2   7    20
  /   / \ 
 1   6   8
输出: 8
提示：

1 ≤ cnt ≤ 二叉搜索树元素个数

class Solution {
    LinkedList<Integer>arr=new LinkedList<Integer>();
    private void dfs(TreeNode root){
        if(root==null)return;
        dfs(root.left);
        arr.add(root.val);
        dfs(root.right);
    }
    public int findTargetNode(TreeNode root, int cnt) {
        dfs(root);
        return arr.get(arr.size()-cnt);
    }
}

解法二：红黑树

Java 中的 TreeMap 是基于红黑树实现的，可以直接利用其功能来完成排序和快速查询。以下是使用红黑树（TreeMap）来解决该问题的思路和实现

import java.util.TreeMap;

class Solution {
    public int findTargetNode(TreeNode root, int cnt) {
        // 用 TreeMap 统计每个值的频率
        TreeMap<Integer, Integer> valueCountMap = new TreeMap<>();

        // 遍历二叉树并统计频率
        traverseAndCount(root, valueCountMap);

        // 使用 TreeMap 的倒序键集合，找到第 cnt 大的值
        int totalCount = 0;
        for (int key : valueCountMap.descendingKeySet()) {
            totalCount += valueCountMap.get(key);
            if (totalCount >= cnt) {
                return key;
            }
        }

        // 如果没有找到结果（理论上不会发生）
        throw new IllegalArgumentException("Invalid cnt value: " + cnt);
    }

    // 遍历二叉树，统计每个值的频率
    private void traverseAndCount(TreeNode root, TreeMap<Integer, Integer> map) {
        if (root == null) return;
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        traverseAndCount(root.left, map);
        traverseAndCount(root.right, map);
    }
}

剑指 Offer 68 – I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:
1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
1
2
3
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:

所有节点的值都是唯一的。

p、q 为不同节点且均存在于给定的二叉搜索树中。

遍历两次

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path_p = getPath(root, p);
        List<TreeNode> path_q = getPath(root, q);
        TreeNode ancestor = null;
        for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) {
            if (path_p.get(i) == path_q.get(i)) {
                ancestor = path_p.get(i);
            } else {
                break;
            }
        }
        return ancestor;
    }

    public List<TreeNode> getPath(TreeNode root, TreeNode target) {
        List<TreeNode> path = new ArrayList<TreeNode>();
        TreeNode node = root;
        while (node != target) {
            path.add(node);
            if (target.val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        path.add(node);
        return path;
    }
}

遍历一次

我们从根节点开始遍历；
如果当前节点的值大于 p 和 q 的值，说明 p 和 q 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
如果当前节点的值小于 p 和 q 的值，说明 p 和 q 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；
如果当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时，p 和 q 要么在当前节点的不同的子树中，要么其中一个就是当前节点

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }
}

Day11：一道二叉树题:二叉树序列化

剑指 Offer 37. 序列化二叉树

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：
1
2
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
1
2
输入：root = []
输出：[]
示例 3：
1
2
输入：root = [1]
输出：[1]
示例 4：
1
2
输入：root = [1,2]
输出：[1,2]
提示：

树中结点数在范围 [0, 104] 内

-1000 <= Node.val <= 1000

解法：层序遍历

序列化 Serialize ：
借助队列，对二叉树做层序遍历，并将越过叶节点的 null 也打印出来。

算法流程：

特例处理：若 root 为空，则直接返回空列表 “[]” ；

初始化：队列 queue （包含根节点 root ）；序列化列表 res ；

层序遍历：当 queue 为空时跳出；
a. 节点出队，记为 node ；
b.若 node 不为空：(1) 打印字符串 node.val ，(2) 将左、右子节点加入 queue ；
c.否则（若 node 为空）：打印字符串 “null” ；

返回值：拼接列表，用 ‘,’ 隔开，首尾添加中括号；

反序列化 Deserialize ：
基于本文开始推出的 node , node.left , node.right 在序列化列表中的位置关系，可实现反序列化。

利用队列按层构建二叉树，借助一个指针 i 指向节点 node 的左、右子节点，每构建一个 node 的左、右子节点，指针 i 就向右移动 1 位。

算法流程：

特例处理：若 data 为空，直接返回 null ；

初始化：序列化列表 vals （先去掉首尾中括号，再用逗号隔开），指针 i = 1 ，根节点 root （值为 vals[0] ），队列 queue（包含 root ）；

按层构建：当 queue 为空时跳出；
a.节点出队，记为 node ；
b.构建 node 的左子节点：node.left 的值为 vals[i] ，并将 node.left 入队；
c.执行 i += 1 ；
d.构建 node 的右子节点：node.right 的值为 vals[i] ，并将 node.right 入队；
e.执行 i += 1 ；

返回值：返回根节点 root 即可；

public class Codec {
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

Day12：额外补充 2 道二叉树回溯题

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

示例 1：
1
2
3
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
1
2
输入：root = [1,2]
输出：1
提示：

树中节点数目在范围 [1, 104] 内

-100 <= Node.val <= 100

class Solution {
    private int maxDiameter = 0;

    // 深度函数，同时计算直径
    private int depth(TreeNode root) {
        if (root == null) return 0;

        int leftDepth = depth(root.left);  // 计算左子树的深度
        int rightDepth = depth(root.right); // 计算右子树的深度

        // 更新树的直径
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);

        // 返回当前节点的深度
        return 1 + Math.max(leftDepth, rightDepth);
    }

    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);  // 触发递归计算
        return maxDiameter;  // 返回最大直径
    }
}

注意最大直径有可能不经过根节点

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

输入：root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

示例 2：

输入：root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]

解释：

示例 3：

输入：root = [1,null,3]

输出：[1,3]

示例 4：

输入：root = []

输出：[]

提示:

二叉树的节点个数的范围是 [0,100]

-100 <= Node.val <= 100

解法一：BFS

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        // 队列用于进行层次遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();  // 当前层的节点数
            TreeNode rightMost = null;

            // 逐一访问当前层的所有节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                rightMost = node;  // 每次遍历时更新最右节点
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            // 当前层的最右节点加入结果
            result.add(rightMost.val);
        }

        return result;
    }
}

解法二：DFS

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        dfs(root, 0, result);
        return result;
    }

    // 深度优先搜索：node是当前节点，depth是当前深度，result是结果列表
    private void dfs(TreeNode node, int depth, List<Integer> result) {
        if (node == null) {
            return;
        }

        // 如果当前深度没有记录过节点，说明这是该深度的第一个节点
        if (depth == result.size()) {
            result.add(node.val);
        }

        // 先递归右子树，再递归左子树，确保右侧的节点先被记录
        dfs(node.right, depth + 1, result);
        dfs(node.left, depth + 1, result);
    }
}

专题4：二分查找

二分查找意味着数组有序，所以你们在做题的时候，如果看到有序，那么脑子里应该要浮现是否可以采取二分查找这样一种方法，二分查找的题很多，不过我们这个专题，重点是掌握二分查找的一些变种。

我们常规的二分查找，是寻找某个元素 target 的下标（并且该数组没有重复的元素），不过还有四种变形的二分查找（有重复元素），具体描述看Day13.

对于这四种题型，大家要去研究一下适合自己的模版，并且记住这个模版，以后做题都不要改动。

Day13：给出四种变形二分查找的模版

四种二分查找模板

本次打卡的任务很简单，就是给出四种变形二分查找的模版代码。

比如对于一个有序数组：arr = [1，2，3，3，3，4，5，5，7]，target = 3，那么

寻找第一个大于 target 的元素的下标，本案例中4 就是第一个大于 target 的元素，下标 = 5。
对应方法名格式为
int upper(int[] arr, int target){

//如果都不存在，则返回-1
}
如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，如果不存在，则返回第一个大于 target 的元素下标。本案例中最后一个等于target的下标 = 4。
对应方法名
int floor_upper(int[] arr, int target){
//如果都不存在，则返回-1
}
寻找最后一个小于 target 的元素的下标，本案例中 2 则是最后一个小于 target 的，下标 = 1.
对应方法名格式为
int lower(int[] arr, int target){

//如果都不存在，则返回-1
}
如果数组中存在元素等于 target，则返回第一个等于target 的下标，如果不存在，则返回最后一个小于 target 的元素的下标。本案例中第一个等于target的下标 = 2。
对应方法名格式为
int floor_lower(int[] arr, int target){

//如果都不存在，则返回-1
}

解答：

package sort;

public class BinarySort {

    public static void main(String[] args) {
        // 测试 floor_lower 方法
        int[] arr = new int[]{1, 2, 3, 3, 3, 4, 5, 5, 7};
        int target = 3;
        int index = floor_lower(arr, target);
        System.out.println("floor_lower: index = " + index + ", value = " + arr[index]);
    }

    // 1. 寻找第一个大于 target 的元素的下标
    public static int upper(int[] arr, int target){
        int l = 0;
        int r = arr.length - 1;
        if(arr[r] <= target){
            return -1;
        }
        while(l < r){
            int mid = l + (r - l) / 2;
            if(arr[mid] > target){
                r = mid;
            } else { // arr[mid] <= target
                l = mid + 1;
            }
        }
        return l;
    }

    // 2. 如果数组中存在元素等于 target，则返回最后一个等于 target 的元素下标，
    //    如果不存在，则返回第一个大于 target 的元素下标
    public static int floor_upper(int[] arr, int target){
        int l = 0, r = arr.length - 1;
        if(arr[r] < target){
            return -1;
        }
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(arr[mid] <= target){
                l = mid + 1;
            } else{
                r = mid - 1;
            }
        }
        // 此时 r 是最后一个 <= target 的下标
        if(r >= 0 && arr[r] == target){
            return r;
        }
        return l;
    }

    // 3. 寻找最后一个小于 target 的元素的下标
    public static int lower(int[] arr, int target){
        int l = 0;
        int r = arr.length - 1;
        if(arr[l] >= target){
            return -1;
        }
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(arr[mid] >= target){
                r = mid - 1;
            } else { // arr[mid] < target
                l = mid + 1;
            }
        }
        return r;
    }

    // 4. 如果数组中存在元素等于 target，则返回第一个等于 target 的下标，
    //    如果不存在，则返回最后一个小于 target 的元素下标
    public static int floor_lower(int[] arr, int target){
        int l = 0, r = arr.length - 1;
        if(arr[l] > target){
            return -1;
        }
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(arr[mid] >= target){
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        // 此时 l 是第一个 >= target 的下标
        if(l < arr.length && arr[l] == target){
            return l;
        }
        return r;
    }
}

Day 14：2道二分查找题

剑指 Offer 53 – I. 在排序数组中查找

某班级考试成绩按非严格递增顺序记录于整数数组 scores，请返回目标成绩 target 的出现次数。

示例 1：
1
2
输入: scores = [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target = 4
输出: 3
示例 2：
1
2
输入: scores = [1, 2, 3, 5, 7, 9], target = 6
输出: 0
提示：

0 <= scores.length <= 10^5

-10^9 <= scores[i] <= 10^9

scores 是一个非递减数组

-10^9 <= target <= 10^9

二分查找模板O(log n)

class Solution {
    // 查找最后一个等于 target 的元素下标
    public static int floor_upper(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;

        // 判断特殊情况
        if (arr[r] < target) {
            return -1;
        }

        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] > target) {
                r = mid - 1;
            } else if (arr[mid] == target) {
                // 找到相等的 target，继续向右边找
                l = mid + 1;
            } else { // arr[mid] < target
                l = mid + 1;
            }
        }

        // 最后一个等于 target 的元素下标是 r
        return r;
    }

    // 查找第一个等于 target 的元素下标
    public static int floor_lower(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;

        // 判断特殊情况
        if (arr[l] > target) {
            return -1;
        }

        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] > target) {
                r = mid - 1;
            } else if (arr[mid] == target) {
                // 找到相等的 target，继续向左边找
                r = mid - 1;
            } else { // arr[mid] < target
                l = mid + 1;
            }
        }

        // 第一个等于 target 的元素下标是 l
        return l;
    }

    // 计算 target 出现的次数
    public int countTarget(int[] scores, int target) {
        if (scores.length == 0) return 0;

        // 获取第一个等于 target 的下标
        int lid = floor_lower(scores, target);
        // 获取最后一个等于 target 的下标
        int rid = floor_upper(scores, target);

        if (lid == -1 || rid == -1 || scores[lid] != target) return 0;

        // 出现次数为最后一个位置和第一个位置之差加1
        return rid - lid + 1;
    }
}

剑指 Offer 53 – II. 0～n-1中缺失的数字

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

示例 1:
1
2
输入: records = [0,1,2,3,5]
输出: 4
示例 2:
1
2
输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7
提示：
1
1 <= records.length <= 10000

解法一：数学计算O(N)

class Solution {
    public int takeAttendance(int[] records) {
        int n=records.length+1;
        int sum = java.util.Arrays.stream(records).sum();
        return (n-1)*n/2-sum;
    }
}

解法二：二分查找

class Solution {
    public int takeAttendance(int[] records) {
        // 特例处理：如果数组为空或仅包含一个元素
        if (records[0] != 0) {
            return 0; // 缺席的学号是 0
        }
        if (records[records.length - 1] == records.length - 1) {
            return records.length; // 缺席的是最后一个学号
        }
        int l = 0, r = records.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            // 如果 mid 对应的学号与下标相等，缺席在右半部分
            if (records[mid] == mid) {
                l = mid + 1;
            } else {
                // 否则缺席在左半部分
                r = mid;
            }
        }
        // 最后返回 l，l 就是缺席的学号
        return l;
    }
}

Day15：1道二分查找题

剑指 Offer 11. 旋转数组的最小数字

仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品 id，可能存在重复。原库存表按商品 id 升序排列。现因突发情况需要进行商品紧急调拨，管理员将这批商品 id 提前依次整理至库存表最后。请你找到并返回库存表中编号的 最小的元素 以便及时记录本次调拨。

示例 1：
1
2
输入：stock = [4,5,8,3,4]
输出：3
示例 2：
1
2
输入：stock = [5,7,9,1,2]
输出：1
提示：

1 <= stock.length <= 5000

-5000 <= stock[i] <= 5000

解法：直接在原数组上用二分查找来做是道困难题

难在:stock[pivot] == stock[high],high-1所做的数学证明

class Solution {
    public int inventoryManagement(int[] stock) {
        int low = 0;
        int high = stock.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (stock[pivot] < stock[high]) {
                high = pivot;
            } else if (stock[pivot] > stock[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return stock[low];
    }
}

专题5：位运算

关于位运算，说实话，没啥技巧，靠曾经做过，比如一道题如果你从来没有接触过，那你大概率不晓得还能用位运算来做了，所以对于位运算，那就是多接触几道题。

不过位运算的题也不多，技巧也就那么几个，通过这个专题把常见位运算掌握一下就可以了。

基础位运算技巧

1.判断奇偶数

1
2
3

if(n & 1 == 1){
    // n 是个奇数。
}

2、交换两个数

不允许你使用额外的辅助变量来完成交换呢？位运算代码如下：

1
2
3

x = x ^ y   // （1）
y = x ^ y   // （2）
x = x ^ y   // （3）

3、找出没有重复的数

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数。

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

时间复杂度为 O(n)，空间复杂度为 O(1)。

4、m的n次方(快速幂)

例如 n = 13，则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:

m^1101 = m^0001 m^0100 m^1000。

我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。直接看代码吧，反而容易理解：

int pow(int n, int m){
    int sum = 1;
    int tmp = m;
    while(n != 0){
        if(n & 1 == 1){
            sum *= tmp;
        }
        tmp *= tmp;
        n = n >> 1;
    }
    return sum;
}

时间复杂度近为 O(logn)

这里说一下，位运算很多情况下都是很二进制扯上关系的，所以我们要判断是否是否位运算，很多情况下都会把他们拆分成二进制，然后观察特性，或者就是利用与，或，异或的特性来观察，总之，多看一些例子，加上自己多动手，就比较容易上手了。

5、找出不大于N的最大的2的幂指数

int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8 // 整型一般是 32 位，上面我是假设 8 位。
    return (n + 1) >> 1;
}

Day16：2道题

剑指 Offer 15. 二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量).）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。

在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

示例 1：
1
2
3
输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
1
2
3
输入：n = 128 (控制台输入 00000000000000000000000010000000)
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
1
2
3
输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：

输入必须是长度为 32 的 二进制串 。

注意：java没有无符号整数类型，要用>>>运算符，与C/C++不同

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int cnt=0;
        while(n!=0){
            if((n&1)==1)cnt++;
            n>>>=1;
        }
        return cnt;
    }
}

剑指 Offer 16. 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。

示例 1：
1
2
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
1
2
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
1
2
3
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：

-100.0 < x < 100.0

-2^31 <= n <= 2^31-1

-10^4 <= x^n <= 10^4

解法一：迭代

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N>>>=1;
        }
        return ans;
    }
}

解法二：递归

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}

Day17：2道位运算

剑指 Offer 56 – I. 数组中数字出现的次数

整数数组 sockets 记录了一个袜子礼盒的颜色分布情况，其中 sockets[i] 表示该袜子的颜色编号。礼盒中除了一款撞色搭配的袜子，每种颜色的袜子均有两只。请设计一个程序，在时间复杂度 O(n)，空间复杂度O(1) 内找到这双撞色搭配袜子的两个颜色编号。

示例 1：
1
2
输入：sockets = [4, 5, 2, 4, 6, 6]
输出：[2,5] 或 [5,2]
示例 2：
1
2
输入：sockets = [1, 2, 4, 1, 4, 3, 12, 3]
输出：[2,12] 或 [12,2]
提示：

2 <= sockets.length <= 10000

解法：找到a,b中第一个不同的位，以此将数组分为两个子数组

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int ret=0;
        for(int n:sockets){
            ret^=n;
        }
        int div=1;
        while((div&ret)==0)div<<=1;
        int a=0,b=0;
        for(int n:sockets){
            if((div&n)==0)a^=n;
            else b^=n;
        }
        return new int[]{a,b};
    }
}

剑指 Offer 56 – II. 数组中数字出现的次数 II：构造自动机

剑指 Offer 56 – II. 数组中数字出现的次数 II

教学过程中，教练示范一次，学员跟做三次。该过程被混乱剪辑后，记录于数组 actions，其中 actions[i] 表示做出该动作的人员编号。请返回教练的编号。

示例 1：
1
2
输入：actions = [5, 7, 5, 5]
输出：7
示例 2：
1
2
输入：actions = [12, 1, 6, 12, 6, 12, 6]
输出：1
提示：

1 <= actions.length <= 10000

1 <= actions[i] < 2^31

解法一：数组统计

class Solution {
    public int trainingPlan(int[] actions) {
        int[] counts = new int[32];
        for(int action : actions) {
            for(int i = 0; i < 32; i++) {
                counts[i] += action & 1; // 更新第 i 位 1 的个数之和
                action >>= 1;            // 第 i 位 --> 第 i 位
            }
        }
        int res = 0, m = 3;
        for(int i = 31; i >= 0; i--) {
            res <<= 1;
            res |= counts[i] % m;        // 恢复第 i 位
        }
        return res;
    }
}

解法二：有限状态自动机(必须掌握)

class Solution {
    public int trainingPlan(int[] actions) {
        int ones = 0, twos = 0;
        for(int action : actions){
            ones = ones ^ action & ~twos;
            twos = twos ^ action & ~ones;
        }
        return ones;
    }
}

专题6:数学知识+排序算法+滑动窗口

由于这部分的题都比较少，所以这里把它们合并在一起，这类题更多还是考察你做过的题型 + 你的思维联想

Day18：2道数学相关题

剑指 Offer 14- I. 剪绳子

现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。

示例 1：
1
2
输入: bamboo_len = 12
输出: 81
提示：

2 <= bamboo_len <= 58

解法一：动态规划

由于数据规模较小，考虑动态规划

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        int[] dp=new int[bamboo_len+1];
        for(int i=2;i<=bamboo_len;i++){
            int curMax=0;
            for(int j=1;j<i;j++){
                curMax=Math.max(curMax,Math.max(j*(i-j),j*dp[i-j]));
            }
            dp[i]=curMax;
        }
        return dp[bamboo_len];
    }
}

解法二：数学证明

拆成最多的3，接着是2

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if (bamboo_len <= 3) {
            return bamboo_len - 1;
        }
        int quotient = bamboo_len / 3;
        int remainder = bamboo_len % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        } else if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        } else {
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

剑指 Offer 14- II. 剪绳子 II

现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为 正整数。请返回每段竹子长度的 最大乘积 是多少。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
1
2
输入：bamboo_len = 12
输出：81
提示：

2 <= bamboo_len <= 1000

了解快速幂求余

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if(bamboo_len <= 3) return bamboo_len - 1;
        int b = bamboo_len % 3, p = 1000000007;
        long rem = 1, x = 3;
        for(int a = bamboo_len / 3 - 1; a > 0; a /= 2) {
            if(a % 2 == 1) rem = (rem * x) % p;
            x = (x * x) % p;
        }
        if(b == 0) return (int)(rem * 3 % p);
        if(b == 1) return (int)(rem * 4 % p);
        return (int)(rem * 6 % p);
    }
}

Day19：2道数学相关题

剑指 Offer 43. 1～n 整数中 1 出现的次数: 数位DP

剑指 Offer 43. 1～n 整数中 1 出现的次数

给定一个整数 num，计算所有小于等于 num 的非负整数中数字 1 出现的个数。

示例 1：
1
2
输入：num = 0
输出：0
示例 2：
1
2
输入：num = 13
输出：6
提示：

0 <= num < 10^9

数位DP

class Solution {
    private char s[];
    private int dp[][];

    public int digitOneInNumber(int n) {
        s = Integer.toString(n).toCharArray();
        int m = s.length;
        dp = new int[m][m];
        for (int[] row : dp) Arrays.fill(row, -1);
        return f(0, 0, true);
    }

    private int f(int i, int cnt1, boolean isLimit) {
        if (i == s.length) return cnt1;
        if (!isLimit && dp[i][cnt1] >= 0) return dp[i][cnt1];
        int res = 0;
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = 0; d <= up; d++) // 枚举要填入的数字 d
            res += f(i + 1, cnt1 + (d == 1 ? 1 : 0), isLimit && d == up);
        if (!isLimit) dp[i][cnt1] = res;
        return res;
    }
}

剑指 Offer 44. 数字序列中某一位的数字

某班级学号记录系统发生错乱，原整数学号序列 [1,2,3,4,...] 分隔符丢失后变为 1234... 的字符序列。请实现一个函数返回该字符序列中的第 k 位数字。

示例 1：
1
2
输入：k = 5
输出：5
示例 2：
1
2
3
输入：k = 12
输出：1
解释：第 12 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 1 ，它是 11 的一部分。
提示：

0 <= k < 2^31

数学规律

class Solution {
    public int findKthNumber(int k) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (k > count) { // 1.
            k -= count;
            start *= 10;
            digit += 1;
            count = digit * start * 9;
        }
        long num = start + (k - 1) / digit; // 2.
        return Long.toString(num).charAt((k - 1) % digit) - '0'; // 3.
    }
}

Day20：2 道数学相关题

剑指 Offer 39. 数组中出现次数超过一半的数字

仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品 id，可能存在重复。请返回库存表中数量大于 stock.length / 2 的商品 id。

示例 1:
1
2
输入: stock = [6, 1, 3, 1, 1, 1]
输出: 1
限制：

1 <= stock.length <= 50000

给定数组为非空数组，且存在结果数字

摩尔投票法

摩尔投票法（Moore Voting Algorithm）是一种用于在数组中找到可能的多数元素（出现次数超过数组长度一半的元素）的算法。它由Robert S. Boyer和J Strother Moore提出，因此也被称为Boyer-Moore Voting Algorithm。

算法的核心思想：

假设候选：通过一次遍历数组，选择一个元素作为候选多数元素，并记录其“支持票数”。

票数加减：

如果遇到与候选相同的元素，增加票数；

如果遇到不同的元素，减少票数；

当票数减到0时，重新选择当前元素为候选并将票数重置为1。

验证候选：完成一次遍历后，候选元素未必一定是多数元素，因此需要额外再遍历一次来确认候选元素是否确实是多数元素。

算法步骤：

遍历数组，选出一个候选元素。

重新遍历数组，统计候选元素的出现次数，判断其是否为多数元素。

时间复杂度与空间复杂度：

时间复杂度：O(n)，因为数组只需遍历两次。

空间复杂度：O(1)，只需要常数的额外空间。

示例代码（Python）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def majority_element(nums):
    # 第一步：找到候选多数元素
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    
    # 第二步：验证候选多数元素,摩尔投票法只能保证选出众数，不能保证其超过半数
    count = sum(1 for num in nums if num == candidate)
    return candidate if count > len(nums) // 2 else None

# 测试
nums = [3, 3, 4, 2, 3, 3, 3]
print(majority_element(nums))  # 输出：3
应用场景：

在选举投票场景中快速找到可能的多数选票候选。

数组数据分析中查找占据主导地位的元素。

摩尔投票法是一种非常巧妙且高效的算法，用简单的步骤解决了多数元素/众数问题。

class Solution {
    public int inventoryManagement(int[] stock) {
        int x=0,votes=0;
        for(int num:stock){
            if(votes==0)x=num;
            votes+=(num==x)?1:-1;
        }
        return x;
    }
}

剑指 Offer 61. 扑克牌中的顺子

展览馆展出来自 13 个朝代的文物，每排展柜展出 5 个文物。某排文物的摆放情况记录于数组 places，其中 places[i] 表示处于第 i 位文物的所属朝代编号。其中，编号为 0 的朝代表示未知朝代。请判断并返回这排文物的所属朝代编号是否能够视为连续的五个朝代（如遇未知朝代可算作连续情况）。

示例 1：
1
2
输入: places = [0, 6, 9, 0, 7]
输出: True
示例 2：
1
2
输入: places = [7, 8, 9, 10, 11]
输出: True
提示：

places.length = 5

0 <= places[i] <= 13

class Solution {
    public boolean checkDynasty(int[] places) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for(int place : places) {
            if(place == 0) continue; // 跳过未知朝代
            max = Math.max(max, place); // 最大编号朝代
            min = Math.min(min, place); // 最小编号朝代
            if(repeat.contains(place)) return false; // 若有重复，提前返回 false
            repeat.add(place); // 添加此朝代至 Set
        }
        return max - min < 5; // 最大编号朝代 - 最小编号朝代 < 5 则连续
    }
}

class Solution {
    public boolean checkDynasty(int[] places) {
        int unknown = 0;
        Arrays.sort(places); // 数组排序
        for(int i = 0; i < 4; i++) {
            if(places[i] == 0) unknown++; // 统计未知朝代数量
            else if(places[i] == places[i + 1]) return false; // 若有重复，提前返回 false
        }
        return places[4] - places[unknown] < 5; // 最大编号朝代 - 最小编号朝代 < 5 则连续
    }
}

Day21：2道滑动窗口题

剑指 Offer 57 – II. 和为s的连续正数序列

待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。

注意，返回时需遵循以下规则：

每种组合按照文件编号升序排列；

不同组合按照第一个文件编号升序排列。

示例 1：
1
2
3
输入：target = 12
输出：[[3, 4, 5]]
解释：在上述示例中，存在一个连续正整数序列的和为 12，为 [3, 4, 5]。
示例 2：
1
2
3
输入：target = 18
输出：[[3,4,5,6],[5,6,7]]
解释：在上述示例中，存在两个连续正整数序列的和分别为 18，分别为 [3, 4, 5, 6] 和 [5, 6, 7]。
提示：

1 <= target <= 10^5

双指针维护滑动窗口

class Solution {
    public int[][] fileCombination(int target) {
        List<int[]> vec = new ArrayList<int[]>();
        for (int l = 1, r = 2; l < r;) {
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] res = new int[r - l + 1];
                for (int i = l; i <= r; ++i) {
                    res[i - l] = i;
                }
                vec.add(res);
                l++;
            } else if (sum < target) {
                r++;
            } else {
                l++;
            }
        }
        return vec.toArray(new int[vec.size()][]);
    }
}

剑指 Offer 59 – I. 滑动窗口的最大值

科技馆内有一台虚拟观景望远镜，它可以用来观测特定纬度地区的地形情况。该纬度的海拔数据记于数组 heights ，其中 heights[i] 表示对应位置的海拔高度。请找出并返回望远镜视野范围 limit 内，可以观测到的最高海拔值。

示例 1：
1
2
3
4
5
6
7
8
9
10
输入：heights = [14,2,27,-5,28,13,39], limit = 3
输出：[27,27,28,28,39]
解释：
  滑动窗口的位置                最大值
---------------               -----
[14 2 27] -5 28 13 39          27
14 [2 27 -5] 28 13 39          27
14 2 [27 -5 28] 13 39          28
14 2 27 [-5 28 13] 39          28
14 2 27 -5 [28 13 39]          39
提示：

你可以假设输入总是有效的，在输入数组不为空的情况下：

1 <= limit <= heights.length

-10000 <= heights[i] <= 10000

单调队列

回忆“最小栈”问题，其使用单调栈实现了随意入栈、出栈情况下的 O(1) 时间获取 “栈内最小值” 。本题同理，不同点在于 “出栈操作” 删除的是 “列表尾部元素” ，而 “窗口滑动” 删除的是 “列表首部元素” 。

窗口对应的数据结构为双端队列，本题使用单调队列即可解决以上问题。遍历数组时，每轮保证单调队列 deque ：

deque 内仅包含窗口内的元素 ⇒ 每轮窗口滑动移除了元素 heights[i−1] ，需将 deque 内的对应元素一起删除。
deque 内的元素非严格递减 ⇒ 每轮窗口滑动添加了元素 heights[j+1] ，需将 deque 内所有 <heights[j+1] 的元素删除。

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        if(heights.length == 0 || limit == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[heights.length - limit + 1];
        // 未形成窗口
        for(int i = 0; i < limit; i++) {
            while(!deque.isEmpty() && deque.peekLast() < heights[i])
                deque.removeLast();
            deque.addLast(heights[i]);
        }
        res[0] = deque.peekFirst();
        // 形成窗口后
        for(int i = limit; i < heights.length; i++) {
            if(deque.peekFirst() == heights[i - limit])
                deque.removeFirst();
            while(!deque.isEmpty() && deque.peekLast() < heights[i])
                deque.removeLast();
            deque.addLast(heights[i]);
            res[i - limit + 1] = deque.peekFirst();
        }
        return res;
    }
}

Day22：2道排序算法相关题

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

教练使用整数数组 actions 记录一系列核心肌群训练项目编号。为增强训练趣味性，需要将所有奇数编号训练项目调整至偶数编号训练项目之前。请将调整后的训练项目编号以数组形式返回。

示例 1：
1
2
3
输入：actions = [1,2,3,4,5]
输出：[1,3,5,2,4] 
解释：为正确答案之一
提示：

0 <= actions.length <= 50000

0 <= actions[i] <= 10000

双指针

class Solution {
    public int[] trainingPlan(int[] actions) {
        int i = 0, j = actions.length - 1, tmp;
        while(i < j) {
            while(i < j && (actions[i] & 1) == 1) i++;
            while(i < j && (actions[j] & 1) == 0) j--;
            tmp = actions[i];
            actions[i] = actions[j];
            actions[j] = tmp;
        }
        return actions;
    }
}

排序方法

Arrays.stream(actions)：将数组转换为流，方便使用流式 API。

boxed()：将基本类型 int 转换为包装类型 Integer，以便使用自定义比较器。

sorted((a, b) -> Integer.compare(a % 2, b % 2))：使用自定义比较器进行排序，奇数优先（a % 2 的值为 1，偶数为 0）。

mapToInt(Integer::intValue)：将流中的 Integer 转换回 int。

toArray()：将流转换为数组。

import java.util.Arrays;

class Solution {
    public int[] trainingPlan(int[] actions) {
        // 使用稳定排序
        return Arrays.stream(actions)
                     .boxed() // 将 int 转换为 Integer（便于使用 Comparator）
                     .sorted((a, b) -> Integer.compare(a % 2, b % 2)) // 按奇偶排序：奇数优先
                     .mapToInt(Integer::intValue) // 转回 int
                     .toArray(); // 转为数组
    }
}

剑指 Offer 45. 把数组排成最小的数

闯关游戏需要破解一组密码，闯关组给出的有关密码的线索是：

一个拥有密码所有元素的非负整数数组 password

密码是 password 中所有元素拼接后得到的最小的一个数

请编写一个程序返回这个密码。

示例 1:
1
2
输入: password = [15, 8, 7]
输出: "1578"
示例 2:
1
2
输入: password = [0, 3, 30, 34, 5, 9]
输出: "03033459"
提示:

0 < password.length <= 100

说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数

拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

class Solution {
    public String crackPassword(int[] password) {
        String[] strs = new String[password.length];
        for(int i = 0; i < password.length; i++)
            strs[i] = String.valueOf(password[i]);
        quickSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
    void quickSort(String[] strs, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        String tmp = strs[i];
        while(i < j) {
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        quickSort(strs, l, i - 1);
        quickSort(strs, i + 1, r);
    }
}

Day23：3道算法排序应用相关题

剑指 Offer 40. 最小的k个数: 自建堆、快排、BST各种都能说

剑指 Offer 40. 最小的k个数

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

示例 1：
1
2
输入：stock = [2,5,7,4], cnt = 1
输出：[2]
示例 2：
1
2
输入：stock = [0,2,3,6], cnt = 2
输出：[0,2] 或 [2,0]
提示：

0 <= cnt <= stock.length <= 10000 0 <= stock[i] <= 10000

库函数堆

// 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
// 1. 若目前堆的大小小于K，将当前数字放入堆中。
// 2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
//    反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int num: arr) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (num < pq.peek()) {
                pq.poll();
                pq.offer(num);
            }
        }
        
        // 返回堆中的元素
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
}

自建堆

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        if (cnt == 0) return new int[0]; // 如果 cnt 为 0，直接返回空数组
        
        // 构建最大堆（数组形式）
        int[] maxHeap = new int[cnt];
        int size = 0; // 当前堆的大小

        // 遍历 stock 数组
        for (int num : stock) {
            if (size < cnt) {
                // 堆未满，直接插入并调整
                maxHeap[size++] = num;
                heapifyUp(maxHeap, size - 1);
            } else if (num < maxHeap[0]) {
                // 新元素小于堆顶，替换堆顶并调整堆
                maxHeap[0] = num;
                heapifyDown(maxHeap, 0, size);
            }
        }

        return maxHeap;
    }

    // 上浮操作：将新插入的元素调整到合适位置
    private void heapifyUp(int[] heap, int index) {
        int parent = (index - 1) / 2;
        while (index > 0 && heap[index] > heap[parent]) {
            swap(heap, index, parent);
            index = parent;
            parent = (index - 1) / 2;
        }
    }

    // 下沉操作：将堆顶元素调整到合适位置
    private void heapifyDown(int[] heap, int index, int size) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != index) {
            swap(heap, index, largest);
            heapifyDown(heap, largest, size);
        }
    }

    // 交换两个元素
    private void swap(int[] heap, int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

快排

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 最后一个参数表示我们要找的是下标为k-1的数
        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSearch(int[] nums, int lo, int hi, int k) {
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
        int j = partition(nums, lo, hi);
        if (j == k) {
            return Arrays.copyOf(nums, j + 1);
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
    }

    // 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
    private int partition(int[] nums, int lo, int hi) {
        int v = nums[lo];
        int i = lo, j = hi + 1;
        while (true) {
            while (++i <= hi && nums[i] < v);
            while (--j >= lo && nums[j] > v);
            if (i >= j) {
                break;
            }
            int t = nums[j];
            nums[j] = nums[i];
            nums[i] = t;
        }
        nums[lo] = nums[j];
        nums[j] = v;
        return j;
    }
}

计数排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 统计每个数字出现的次数
        int[] counter = new int[10001];
        for (int num: arr) {
            counter[num]++;
        }
        // 根据counter数组从头找出k个数作为返回结果
        int[] res = new int[k];
        int idx = 0;
        for (int num = 0; num < counter.length; num++) {
            while (counter[num]-- > 0 && idx < k) {
                res[idx++] = num;
            }
            if (idx == k) {
                break;
            }
        }
        return res;
    }
}

BST

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // TreeMap的key是数字, value是该数字的个数。
        // cnt表示当前map总共存了多少个数字。
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int cnt = 0;
        for (int num: arr) {
            // 1. 遍历数组，若当前map中的数字个数小于k，则map中当前数字对应个数+1
            if (cnt < k) {
                map.put(num, map.getOrDefault(num, 0) + 1);
                cnt++;
                continue;
            } 
            // 2. 否则，取出map中最大的Key（即最大的数字), 判断当前数字与map中最大数字的大小关系：
            //    若当前数字比map中最大的数字还大，就直接忽略；
            //    若当前数字比map中最大的数字小，则将当前数字加入map中，并将map中的最大数字的个数-1。
            Map.Entry<Integer, Integer> entry = map.lastEntry();
            if (entry.getKey() > num) {
                map.put(num, map.getOrDefault(num, 0) + 1);
                if (entry.getValue() == 1) {
                    map.pollLastEntry();
                } else {
                    map.put(entry.getKey(), entry.getValue() - 1);
                }
            }
            
        }

        // 最后返回map中的元素
        int[] res = new int[k];
        int idx = 0;
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            int freq = entry.getValue();
            while (freq-- > 0) {
                res[idx++] = entry.getKey();
            }
        }
        return res;
    }
}

剑指 Offer 41. 数据流中的中位数

中位数 是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。

double findMedian() - 返回目前所有元素的中位数。

示例 1：
1
2
3
4
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
1
2
3
4
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
提示：

最多会对 addNum、findMedian 进行 50000 次调用。

class MedianFinder {
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

剑指 Offer 51. 数组中的逆序对

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例 1:
1
2
3
输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
限制：
1
0 <= record.length <= 50000

归并排序

class Solution {
    int[] record, tmp;
    public int reversePairs(int[] record) {
        this.record = record;
        tmp = new int[record.length];
        return mergeSort(0, record.length - 1);
    }
    private int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = record[k];
        for (int k = l; k <= r; k++) {
            if (i == m + 1)
                record[k] = tmp[j++];
            else if (j == r + 1 || tmp[i] <= tmp[j])
                record[k] = tmp[i++];
            else {
                record[k] = tmp[j++];
                res += m - i + 1; // 统计逆序对
            }
        }
        return res;
    }
}

专题7：回溯算法

掌握回溯算法非常重要，一般回溯算法 = 暴力法，基本很多题都可以采用回溯法来做，其实就是深度优先搜索或者广度优先搜索，掌握了这两个，就等于入门的回溯算法了。

Day24：2道回溯算法题

剑指 Offer 12. 矩阵中的路径

字母迷宫游戏初始界面记作 m x n 二维字符串数组 grid，请判断玩家是否能在 grid 中找到目标单词 target。
注意：寻找单词时必须按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用 。

示例 1：
1
2
输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "ABCCED"
输出：true
示例 2：
1
2
输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "SEE"
输出：true
示例 3：
1
2
输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = "ABCB"
输出：false

class Solution {
    public boolean wordPuzzle(char[][] grid, String word) {
        int h = grid.length, w = grid[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = exist(grid, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean exist(char[][] grid, boolean[][] visited, int i, int j, String s, int k) {
        if (grid[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < grid.length && newj >= 0 && newj < grid[0].length) {
                if (!visited[newi][newj]) {
                    boolean flag = exist(grid, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}

剑指 Offer 13. 机器人的运动范围

家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。

整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。

请返回整理师 总共需要整理多少个格子。

示例 1：
1
2
输入：m = 4, n = 7, cnt = 5
输出：18

BFS

class Solution {
    public int wardrobeFinishing(int m, int n, int cnt) {
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        Queue<int[]> queue= new LinkedList<int[]>();
        queue.add(new int[] { 0, 0, 0, 0 });
        while(queue.size() > 0) {
            int[] x = queue.poll();
            int i = x[0], j = x[1], si = x[2], sj = x[3];
            if(i >= m || j >= n || cnt < si + sj || visited[i][j]) continue;
            visited[i][j] = true;
            res ++;
            queue.add(new int[] { i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
            queue.add(new int[] { i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
        }
        return res;
    }
}

DFS

class Solution {
    int m, n, cnt;
    boolean[][] visited;
    public int wardrobeFinishing(int m, int n, int cnt) {
        this.m = m; this.n = n; this.cnt = cnt;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }
    public int dfs(int i, int j, int si, int sj) {
        if(i >= m || j >= n || cnt < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
}

Day25：2道回溯算法题

剑指 Offer 34. 二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：
1
2
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
1
2
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
1
2
输入：root = [1,2], targetSum = 0
输出：[]
提示：

树中节点总数在范围 [0, 5000] 内

-1000 <= Node.val <= 1000

-1000 <= targetSum <= 1000

class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        recur(root, target);
        return res;
    }
    void recur(TreeNode root, int tar) {
        if(root == null) return;
        path.add(root.val);
        tar -= root.val;
        if(tar == 0 && root.left == null && root.right == null)
            res.add(new LinkedList(path));
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }
}

剑指 Offer 38. 字符串的排列

某店铺将用于组成套餐的商品记作字符串 goods，其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。

返回结果 无顺序要求，但不能含有重复的元素。

示例 1:
1
2
输入：goods = "agew"
输出：["aegw","aewg","agew","agwe","aweg","awge","eagw","eawg","egaw","egwa","ewag","ewga","gaew","gawe","geaw","gewa","gwae","gwea","waeg","wage","weag","wega","wgae","wgea"]
提示：

1 <= goods.length <= 8

class Solution {
    List<String> res = new LinkedList<>();
    char[] arr;
    public String[] goodsOrder(String goods) {
        arr = goods.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == arr.length - 1) {
            res.add(String.valueOf(arr));      // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < arr.length; i++) {
            if(set.contains(arr[i])) continue; // 重复，因此剪枝
            set.add(arr[i]);
            swap(i, x);                      // 交换，将 arr[i] 固定在第 x 位
            dfs(x + 1);                      // 开启固定第 x + 1 位字符
            swap(i, x);                      // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

专题8：动态规划

关键是列出状态转移方程。

Day26：2到稍微简单的动态规划题

剑指 Offer 42. 连续子数组的最大和

某公司每日销售额记于整数数组 sales，请返回所有连续一或多天销售额总和的最大值。

要求实现时间复杂度为 O(n) 的算法。

示例 1:
1
2
3
输入：sales = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：[4,-1,2,1] 此连续四天的销售总额最高，为 6。
示例 2:
1
2
3
输入：sales = [5,4,-1,7,8]
输出：23
解释：[5,4,-1,7,8] 此连续五天的销售总额最高，为 23。 
提示：

1 <= arr.length <= 10^5

-100 <= arr[i] <= 100

基础dp

class Solution {
    public int maxSales(int[] sales) {
        int res=Integer.MIN_VALUE;
        int[] dp=new int[sales.length];
        for(int i=0;i>dp.length;i++)dp[i]=Integer.MIN_VALUE;
        dp[0]=sales[0];
        res=Math.max(res,dp[0]);
        for(int i=1;i<sales.length;i++){
            dp[i]=dp[i-1]>0?dp[i-1]+sales[i]:sales[i];
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}

LeetCode 64. 最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：
1
2
3
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
1
2
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：

m == grid.length

n == grid[i].length

1 <= m, n <= 200

0 <= grid[i][j] <= 200

class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        if(n==0)return 0;
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0)dp[i][j]=grid[i][j];
                else if(i==0)dp[i][j]=grid[i][j]+dp[i][j-1];
                else if(j==0)dp[i][j]=grid[i][j]+dp[i-1][j];
                else dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

Day27：2道中等难度DP

剑指 Offer 63. 股票的最大利润

数组 prices 记录了某芯片近期的交易价格，其中 prices[i] 表示的 i 天该芯片的价格。你只能选择 某一天 买入芯片，并选择在 未来的某一个不同的日子 卖出该芯片。请设计一个算法计算并返回你从这笔交易中能获取的最大利润。

如果你不能获取任何利润，返回 0。

示例 1：
1
2
3
输入：prices = [3, 6, 2, 9, 8, 5]
输出：7
解释：在第 3 天（芯片价格 = 2）买入，在第 4 天（芯片价格 = 9）卖出，最大利润 = 9 - 2 = 7。
示例 2：
1
2
3
输入：prices = [8, 12, 15, 7, 3, 10]
输出：7
解释：在第 5 天（芯片价格 = 3）买入，在第 6 天（芯片价格 = 10）卖出，最大利润 = 10 - 3 = 7。
提示：

0 <= prices.length <= 10^5

0 <= prices[i] <= 10^4

class Solution {
    public int bestTiming(int[] prices) {
        int n=prices.length;
        if(n==0)return 0;
        int res=0;
        int mi=prices[0];
        for(int i=0;i<n;i++){
            res=Math.max(res,prices[i]-mi);
            mi=Math.min(mi,prices[i]);
        }
        return res;
    }
}

剑指 Offer 47. 礼物的最大价值

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

只能从架子的左上角开始拿珠宝

每次可以移动到右侧或下侧的相邻位置

到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

示例 1:
1
2
3
输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝
提示：

0 < frame.length <= 200

0 < frame[0].length <= 200

class Solution {
    public int jewelleryValue(int[][] frame) {
        int m=frame.length;
        int n=frame[0].length;
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 && j==0)dp[i][j]=frame[i][j];
                else if(i==0 && j!=0)dp[i][j]=dp[i][j-1]+frame[i][j];
                else if(i!=0 && j==0)dp[i][j]=dp[i-1][j]+frame[i][j];
                else dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])+frame[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

Day28：一道中等+一道困难DP

剑指 Offer 48. 最长不含重复字符的子字符串

某套连招动作记作序列 arr，其中 arr[i] 为第 i 个招式的名字。请返回 arr 中最多可以出连续不重复的多少个招式。

示例 1:
1
2
3
输入: arr = "dbascDdad"
输出: 6
解释: 因为连续且最长的招式序列是 "dbascD" 或 "bascDd"，所以其长度为 6。
示例 2:
1
2
3
输入: arr = "KKK"
输出: 1
解释: 因为无重复字符的最长子串是 "K"，所以其长度为 1。
示例 3:
1
2
3
4
输入: arr = "pwwkew"
输出: 3
解释: 因为连续且最长的招式序列是 "wke"，所以其长度为 3。     
请注意区分 子串 与 子序列 的概念：你的答案必须是 连续招式 的长度，也就是 子串。而 "pwke" 是一个非连续的 子序列，不是 子串。
提示：

0 <= arr.length <= 40000

arr 由英文字母、数字、符号和空格组成。

class Solution {
    public int dismantlingAction(String arr) {
        HashMap<Character, Integer> mp = new HashMap<>();
        int st=0;
        int res=0;
        for(int i=0;i<arr.length();i++){
            char ch=arr.charAt(i);
            if(!mp.containsKey(ch)){
                res=Math.max(res,i-st+1);
            }else if(mp.get(ch)<st){
                res=Math.max(res,i-st+1);       
            }else{
                st=mp.get(ch)+1;
                res=Math.max(res,i-st+1);
            }
            mp.put(ch, i); 
        }
        return res;
    }
}

剑指 Offer 19. 正则表达式匹配

请设计一个程序来支持用户在文本编辑器中的模糊搜索功能。用户输入内容中可能使用到如下两种通配符：

'.' 匹配任意单个字符。

'*' 匹配零个或多个前面的那一个元素。

请返回用户输入内容 input 所有字符是否可以匹配原文字符串 article。

示例 1:
1
2
3
输入: article = "aa", input = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
1
2
3
输入: article = "aa", input = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
1
2
3
输入: article = "ab", input = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
提示：

1 <= article.length <= 20

1 <= input.length <= 20

article 只包含从 a-z 的小写字母。

input 只包含从 a-z 的小写字母，以及字符 . 和 * 。

保证每次出现字符 * 时，前面都匹配到有效的字符

递归

class Solution {
    public boolean articleMatch(String article, String input) {
        return matchHelper(article, input, 0, 0);
    }

    // 递归辅助函数
    private boolean matchHelper(String article, String input, int i, int j) {
        // 如果模式已经匹配完
        if (j == input.length()) {
            return i == article.length();
        }

        // 判断当前字符是否匹配
        boolean firstMatch = (i < article.length() && (input.charAt(j) == article.charAt(i) || input.charAt(j) == '.'));

        // 如果下一个字符是 '*'
        if (j + 1 < input.length() && input.charAt(j + 1) == '*') {
            // '*' 可以表示 "零次" 或 "多次"
            return matchHelper(article, input, i, j + 2) || (firstMatch && matchHelper(article, input, i + 1, j));
        } else {
            // 当前字符匹配的情况下递归检查下一个字符
            return firstMatch && matchHelper(article, input, i + 1, j + 1);
        }
    }
}

class Solution {
    public boolean articleMatch(String article, String input) {
        // 动态规划表：dp[i][j] 表示 article 的前 i 个字符和 input 的前 j 个字符是否匹配
        int m = article.length();
        int n = input.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 基础情况：空的 article 和空的 input 是匹配的
        dp[0][0] = true;

        // 处理像 a*，a*b* 等模式可以与空的 article 匹配的情况
        for (int j = 1; j <= n; j++) {
            if (input.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2]; // '*' 可以表示 "前一个元素出现零次"
            }
        }

        // 填充动态规划表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char articleChar = article.charAt(i - 1);
                char inputChar = input.charAt(j - 1);

                if (inputChar == '.' || inputChar == articleChar) {
                    // 当前字符匹配
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (inputChar == '*') {
                    // '*' 可以表示 "前一个元素出现零次或多次"
                    char precedingChar = input.charAt(j - 2);
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (precedingChar == '.' || precedingChar == articleChar));
                } else {
                    // 当前字符不匹配
                    dp[i][j] = false;
                }
            }
        }

        // 结果存储在 dp[m][n] 中
        return dp[m][n];
    }
}

Day29：3道DP

剑指 Offer 49. 丑数

给你一个整数 n ，请你找出并返回第 n 个丑数。

说明：丑数是只包含质因数 2、3 和/或 5 的正整数；1 是丑数。

示例 1：
1
2
3
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
提示：

1 <= n <= 1690

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp=new int[n+1];
        dp[1]=1;
        int p2=1,p3=1,p5=1;
        for(int i=2;i<=n;i++){
            int num2=dp[p2]*2,num3=dp[p3]*3,num5=dp[p5]*5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
                p2++;
            }
            if (dp[i] == num3) {
                p3++;
            }
            if (dp[i] == num5) {
                p5++;
            }
        }
        return dp[n];
    }
}

最小堆

class Solution {
    public int nthUglyNumber(int n) {
        int[] factors={2,3,5};
        Set<Long> seen=new HashSet<Long>();
        PriorityQueue<Long>heap=new PriorityQueue<Long>();
        seen.add(1L);
        heap.offer(1L);
        int ugly=0;
        for(int i=0;i<n;i++){
            long curr=heap.poll();
            ugly=(int) curr;
            for(int factor:factors){
                long next=curr*factor;
                if(seen.add(next)){
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }
}

剑指 Offer 60. n个骰子的点数

你选择掷出 num 个色子，请返回所有点数总和的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 num 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1：
1
2
输入：num = 3
输出：[0.00463,0.01389,0.02778,0.04630,0.06944,0.09722,0.11574,0.12500,0.12500,0.11574,0.09722,0.06944,0.04630,0.02778,0.01389,0.00463]
示例 2：
1
2
输入：num = 5
输出:[0.00013,0.00064,0.00193,0.00450,0.00900,0.01620,0.02636,0.03922,0.05401,0.06944,0.08372,0.09452,0.10031,0.10031,0.09452,0.08372,0.06944,0.05401,0.03922,0.02636,0.01620,0.00900,0.00450,0.00193,0.00064,0.00013]
提示：

1 <= num <= 11

方法一：暴力法

方法二：dp

class Solution {
class Solution {
    public double[] statisticsProbability(int num) {
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        for (int i = 2; i <= num; i++) {
            double[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}

LeetCode 42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
示例 2：
1
2
输入：height = [4,2,0,3,2,5]
输出：9
提示：

n == height.length

1 <= n <= 2 * 104

0 <= height[i] <= 105

单调栈

class Solution {
   public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int n = height.length;
        int totalWater = 0;
        java.util.Stack<Integer> stack = new java.util.Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop(); // 当前柱子的索引
                if (stack.isEmpty()) {
                    break; // 栈为空时无法形成凹槽
                }
                int left = stack.peek(); // 左边界的索引
                int width = i - left - 1; // 两柱子之间的宽度
                int boundedHeight = Math.min(height[i], height[left]) - height[top]; // 有效的高度
                totalWater += width * boundedHeight; // 计算当前凹槽可以存的水量
            }

            stack.push(i); // 将当前柱子的索引入栈
        }

        return totalWater;
    }
}

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

双指针

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}

Day30：4道额外DP精选

LeetCode 198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
1
2
3
4
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
1
2
3
4
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：

1 <= nums.length <= 100

0 <= nums[i] <= 400

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

LeetCode 322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：
1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：
1
2
输入：coins = [2], amount = 3
输出：-1
示例 3：
1
2
输入：coins = [1], amount = 0
输出：0
提示：

1 <= coins.length <= 12

1 <= coins[i] <= 2^31 - 1

0 <= amount <= 10^4

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n=coins.length;
        int[][] dp=new int[n+1][amount+1];
        Arrays.fill(dp[0],Integer.MAX_VALUE/2);
        dp[0][0]=0;
        for(int i=0;i<n;i++){
            for(int c=0;c<=amount;c++){
                if(c<coins[i]){
                    dp[i+1][c]=dp[i][c];
                }else{
                    dp[i+1][c]=Math.min(dp[i][c],dp[i+1][c-coins[i]]+1);
                }
            }
        }
        int ans=dp[n][amount];
        return ans<Integer.MAX_VALUE/2?ans:-1;
    }
}

记忆化搜索

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }
        return coinChange(coins, amount, new int[amount]);
    }

    private int coinChange(int[] coins, int rem, int[] count) {
        if (rem < 0) {
            return -1;
        }
        if (rem == 0) {
            return 0;
        }
        if (count[rem - 1] != 0) {
            return count[rem - 1];
        }
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = coinChange(coins, rem - coin, count);
            if (res >= 0 && res < min) {
                min = 1 + res;
            }
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }
}

LeetCode 174. 地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只向右或向下移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

示例 1：
1
2
3
输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
示例 2：
1
2
输入：dungeon = [[0]]
输出：1
提示：

m == dungeon.length

n == dungeon[i].length

1 <= m, n <= 200

-1000 <= dungeon[i][j] <= 1000

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length, m = dungeon[0].length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; ++i) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[n][m - 1] = dp[n - 1][m] = 1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j >= 0; --j) {
                int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = Math.max(minn - dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
}

LeetCode 72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符

示例 1：
1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
1
2
3
4
5
6
7
8
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：

0 <= word1.length, word2.length <= 500

word1 和 word2 由小写英文字母组成

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        // 有一个字符串为空串
        if (n * m == 0) {
            return n + m;
        }

        // DP 数组
        int[][] D = new int[n + 1][m + 1];

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }

        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    left_down += 1;
                }
                D[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return D[n][m];
    }
}

Day31：杂题(最后一天)

剑指 Offer 10- I. 斐波那契数列

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。

示例 1：
1
2
3
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
1
2
3
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
1
2
3
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：

0 <= n <= 100

class Solution {
    public int fib(int n) {
        final int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = (p + q) % MOD;
        }
        return r;
    }
}

剑指 Offer 10- II. 青蛙跳台阶问题

今天的有氧运动训练内容是在一个长条形的平台上跳跃。平台有 num 个小格子，每次可以选择跳 一个格子 或者 两个格子。请返回在训练过程中，学员们共有多少种不同的跳跃方式。

结果可能过大，因此结果需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
1
2
输入：n = 2
输出：2
示例 2：
1
2
输入：n = 5
输出：8
提示：

0 <= n <= 100

class Solution {
    public int trainWays(int num) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < num; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

剑指 Offer 62. 圆圈中最后剩下的数字

社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

示例 1：
1
2
输入：num = 7, target = 4
输出：1
示例 2：
1
2
输入：num = 12, target = 5
输出：0
提示：

1 <= num <= 10^5

1 <= target <= 10^6

递归

class Solution {
    public int iceBreakingGame(int num, int target) {
        return f(num, target);
    }

    public int f(int num, int target) {
        if (num == 1) {
            return 0;
        }
        int x = f(num - 1, target);
        return (target + x) % num;
    }
}

剑指 Offer 03. 数组中重复的数字

设备中存有 n 个文件，文件 id 记于数组 documents。若文件 id 相同，则定义为该文件存在副本。请返回任一存在副本的文件 id。

示例 1：
1
2
输入：documents = [2, 5, 3, 0, 5, 0]
输出：0 或 5
提示：

0 ≤ documents[i] ≤ n-1

2 <= n <= 100000

class Solution {
    public int findRepeatDocument(int[] documents) {
        int i = 0;
        while(i < documents.length) {
            if(documents[i] == i) {
                i++;
                continue;
            }
            if(documents[documents[i]] == documents[i]) return documents[i];
            int tmp = documents[i];
            documents[i] = documents[tmp];
            documents[tmp] = tmp;
        }
        return -1;
    }
}

class Solution {
    public int findRepeatDocument(int[] documents) {
        Set<Integer> hmap = new HashSet<>();
        for(int doc : documents) {
            if(hmap.contains(doc)) return doc;
            hmap.add(doc);
        }
        return -1;
    }
}

剑指 Offer 04. 二维数组中的查找

m*n 的二维数组 plants 记录了园林景观的植物排布情况，具有以下特性：

每行中，每棵植物的右侧相邻植物不矮于该植物；

每列中，每棵植物的下侧相邻植物不矮于该植物。

请判断 plants 中是否存在目标高度值 target。

示例 1：
1
2
3
输入：plants = [[2,3,6,8],[4,5,8,9],[5,9,10,12]], target = 8

输出：true
示例 2：
1
2
3
输入：plants = [[1,3,5],[2,5,7]], target = 4

输出：false
提示：

0 <= n <= 1000

0 <= m <= 1000

class Solution {
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        int i = plants.length - 1, j = 0;
        while(i >= 0 && j < plants[0].length)
        {
            if(plants[i][j] > target) i--;
            else if(plants[i][j] < target) j++;
            else return true;
        }
        return false;
    }
}

剑指 Offer 29. 顺时针打印矩阵

给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。

螺旋遍历：从左上角开始，按照向右、向下、向左、向上的顺序依次提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。

示例 1：
1
2
输入：array = [[1,2,3],[8,9,4],[7,6,5]]
输出：[1,2,3,4,5,6,7,8,9]
示例 2：
1
2
输入：array  = [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
输出：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
限制：

0 <= array.length <= 100

0 <= array[i].length <= 100

class Solution {
    public int[] spiralArray(int[][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return new int[0];
        }
        int rows = array.length, columns = array[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int[] order = new int[total];
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order[i] = array[row][column];
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }
}

专题1：链表

Day1:4道常规题

剑指 Offer 18. 删除链表的节点

剑指 Offer 22. 链表中倒数第k个节点

剑指 Offer 25. 合并两个排序的链表

剑指 Offer 52. 两个链表的第一个公共点

Day2:3道题 + 1个面试找错误

剑指 Offer 06. 从尾到头打印链表

剑指 Offer 24. 反转链表

剑指 Offer 35. 复杂链表的复制

一道常见错误

Day3:复杂链表题

字节真题：单链表相加

百度真题：三等分环形链表

专题2：基础数据结构的视线

Day4： 2道题，队列与栈的相互转换

剑指 Offer 09. 用两个栈实现队列

225. 用队列实现栈

Day5：两道题 + 一道面试变形题

剑指 Offer 30. 包含min函数的栈

剑指 Offer 31. 栈的压入、弹出序列

变形题：最小栈的最优解

专题3：二叉树

Day6：关于树深度的两道算法题

剑指 Offer 55 – I. 二叉树的深度

剑指 Offer 55 – II. 平衡二叉树 】

Day7：3道二叉树

剑指 Offer 27. 二叉树的镜像

剑指 Offer 28. 对称的二叉树

剑指 Offer 26. 树的子结构

Day8：3道二叉树的基本遍历题+前中序二叉树遍历非递归实现

剑指 Offer 32 – I. 从上到下打印二叉树

剑指 Offer 32 – II. 从上到下打印二叉树

剑指 Offer 32 – III. 从上到下打印二叉树

前中序非递归实现

Day9：2道关于二叉树的重建

剑指 Offer 07. 重建二叉树 】

剑指 Offer 33. 二叉搜索树的后序遍历序列

Day10：2道二叉树搜索树

剑指 Offer 54. 二叉搜索树的第k大节点

剑指 Offer 68 – I. 二叉搜索树的最近公共祖先

Day11：一道二叉树题:二叉树序列化

剑指 Offer 37. 序列化二叉树

Day12：额外补充 2 道二叉树回溯题

543. 二叉树的直径

199. 二叉树的右视图

专题4：二分查找

Day13：给出四种变形二分查找的模版

四种二分查找模板

Day 14：2道二分查找题

剑指 Offer 53 – I. 在排序数组中查找

剑指 Offer 53 – II. 0～n-1中缺失的数字

Day15：1道二分查找题

剑指 Offer 11. 旋转数组的最小数字

专题5：位运算

基础位运算技巧

Day16：2道题

剑指 Offer 15. 二进制中1的个数

剑指 Offer 16. 数值的整数次方

Day17：2道位运算

剑指 Offer 56 – I. 数组中数字出现的次数

剑指 Offer 56 – II. 数组中数字出现的次数 II：构造自动机

专题6:数学知识+排序算法+滑动窗口

Day18：2道数学相关题

剑指 Offer 14- I. 剪绳子

剑指 Offer 14- II. 剪绳子 II

Day19：2道数学相关题

剑指 Offer 43. 1～n 整数中 1 出现的次数: 数位DP

剑指 Offer 44. 数字序列中某一位的数字

Day20：2 道数学相关题

剑指 Offer 39. 数组中出现次数超过一半的数字

剑指 Offer 61. 扑克牌中的顺子

Day21：2道滑动窗口题

剑指 Offer 57 – II. 和为s的连续正数序列

剑指 Offer 59 – I. 滑动窗口的最大值

Day22：2道排序算法相关题

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

剑指 Offer 45. 把数组排成最小的数

Day23：3道算法排序应用相关题

剑指 Offer 40. 最小的k个数: 自建堆、快排、BST各种都能说

剑指 Offer 55 – II. 平衡二叉树】

剑指 Offer 07. 重建二叉树】