有序–二分

不会：34

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

剑指 Offer 07. 重建二叉树

剑指 Offer 08. 二叉树的下一个结点

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

剑指 Offer 10-1 求斐波那契数列

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

剑指 Offer 10-3 矩形覆盖

剑指 Offer 10-4 变态跳台阶

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

剑指 Offer 12 矩阵中的路径

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

剑指 Offer 14 剪绳子

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

剑指 Offer 16 数值的整数次方

剑指 Offer 18-2 删除链表中重复的结点

剑指 Offer 19 正则表达式匹配

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

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

剑指 Offer 23 链表中环的入口结点

剑指 Offer 24 反转链表

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

剑指 Offer 26 树的子结构

剑指 Offer 29 顺时针打印矩阵

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

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

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

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

剑指 Offer 35 复制链表的复制

剑指 Offer 36 二叉搜索树与双向链表

剑指 Offer 37 序列化二叉树

剑指 Offer 38 字符串的全排列

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

剑指 Offer 40 最小的k个数

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

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

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

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

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

剑指 Offer 46 把数字翻译成字符串

剑指 Offer 47 礼物的最大价值

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

剑指 Offer 49 丑数

剑指 Offer 50 第一个只出现一次的字符

剑指 Offer 51 数组中的逆序对

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

剑指 Offer 53_1 在排序数组中查找数字

剑指 Offer 53_2 0~n-1中缺失的数字

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

剑指 Offer 55 二叉树的深度

剑指 Offer 55-1 平衡二叉树

剑指 Offer 56-1 数组中数字出现的次数

剑指 Offer 56-2 数组中数字出现的次数2

剑指 Offer 57 和为s的两个数字

剑指 Offer 57_2 和为s的两个数字

剑指 Offer 58_1 和为s的两个数字

剑指 Offer 58_2 左旋转字符串

剑指 Offer 59_1 滑动窗口的最大值

剑指 Offer 59_2 队列的最大值

剑指 Offer 60 n个骰子的点数

剑指 Offer 61 扑克牌中的顺子

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

剑指 Offer 63 股票的最大利润

剑指 Offer 64 求1+2+…+n

剑指 Offer 65 不用加减乘除做加法

剑指 Offer 66 构建乘积数组

剑指 Offer 67 把字符串转换为整数

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

大数的和

接雨水

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

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'''
有序就要想到二分  从数组右上角出发 其实是二叉搜索树
'''
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length<1||matrix[0].length<1) return false;
        int i=0,j=matrix[0].length-1;
        while(i<matrix.length&&j>=0){
            if(matrix[i][j]>target) j--;
            else if(matrix[i][j]<target) i++;
            else return true;
        }
        return false;
    }
}

剑指 Offer 07. 重建二叉树

一、问题描述

题目描述

二、具体代码

$\color{red}{递归}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
'''
前序遍历性质： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。
中序遍历性质： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。
利用map 存中序遍历的值与其对应的下标，这样方便查找根节点在中序遍历数组的下标
'''
class Solution {
    int[] preorder;
    HashMap<Integer,Integer> map=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        this.preorder=preorder;
        return  recur(0,0,inorder.length-1);
    }
    //根节点在前序遍历的索引:root 
    //子树在中序遍历的左边界:left 
    //子树在中序遍历的右边界:right(闭) ；
    public TreeNode recur(int root,int left,int right){
        if(left>right) return null;
        TreeNode node=new TreeNode(preorder[root]);
        int idx=map.get(node.val);
        node.left=recur(root+1,left,idx-1);
        node.right=recur(root+1+idx-left,idx+1,right);
        return  node;
    }
}

class Solution {
    Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for(int i = 0; i<inorder.length;i++){
            map.put(inorder[i], i);
        }
        return helper(preorder, inorder, 0, 0, inorder.length-1);
    }
    private TreeNode helper(int[] preorder, int[] inorder, int preLeft, int inLeft, int inRight){
        TreeNode root = null;
        if(inLeft<=inRight){
            int rootVal = preorder[preLeft];
            root = new TreeNode(rootVal);
            int rootIdx = map.get(rootVal);
            root.left = helper(preorder, inorder, preLeft+1, inLeft, rootIdx-1);
            root.right = helper(preorder, inorder, preLeft+rootIdx-inLeft+1, rootIdx+1, inRight);
        }
        return root;
    }
}

剑指 Offer 08. 二叉树的下一个结点

一、问题描述

题目描述

二、具体代码

$\color{red}{归纳整理}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'''
中序遍历某个节点的下一个节点 要么是该节点右子树的最左边的数，要么是其父节点（该节点是父节点的左子节点） 或者是父节点的父节点....
'''
public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode.right != null) {  //当前节点为某子树的根节点
        TreeLinkNode node = pNode.right;
        while (node.left != null)
            node = node.left;
        return node;
    } else {
        while (pNode.next != null) { //当前节点为左孩子或右孩子
            TreeLinkNode parent = pNode.next;
            if (parent.left == pNode) //假如是左孩子，返回直接父节点即可
                return parent;
            pNode = pNode.next; //假如是右孩子，继续遍历父节点
        }
    }
    return null;
}

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

一、问题描述

题目描述

二、具体代码

$\color{red}{数据结构}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
'''
用两个栈 实现队列
队列入操作：直接入左边的栈
队列出操作：假如右边的栈不为空，则直接输出右边栈顶；假如右边栈为空，则将左边的数都弹出压到右边，再输出右边栈顶
'''
class CQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
    public CQueue() {
        s1=new Stack<>();
        s2=new Stack<>();
    }

    public void appendTail(int value) {
        s1.push(value);
    }

    public int deleteHead() {
        if(!s2.empty()) return s2.pop();
        else if(!s1.empty()){
            while (!s1.empty()){
                s2.push(s1.pop());
            }
            return s2.pop();
        }
        else return -1;
    }
}

# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

剑指 Offer 10-1 求斐波那契数列

一、问题描述

题目描述

二、具体代码

$\color{red}{动态规划}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
由于只跟前两个数有关，于是用两个变量存前两个数
'''
class Solution {
    public int fib(int n) {
         int f0=0,f1=1;
         if(n<2) return n;
         int i=1;
         while(i<n){
             int temp=f1;
             f1=(f0+f1)%1000000007;
             f0=temp;
             i+=1;
         }
         return f1;
    }
}

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

一、问题描述

题目描述

二、具体代码

$\color{red}{动态规划}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
跟10-1一样 也是动态规划问题  F(N)=F(N-1)+F(N-2)) 区别在于F（0）=1
因为跳台阶 
        等于最后剩两步 一次跳两步；
        最后剩一步 一次跳一步，
        全部情况等于上述两种情况的和
'''
class Solution {
    public int numWays(int n) {
        if(n<2) return 1;
        int dp0=1,dp1=1,i=2;
        while(i<=n){
            int temp=dp1;
            dp1=(dp0+dp1)%1000000007;
            dp0=temp;
            i+=1;
        }
        return dp1;
    }
}

剑指 Offer 10-3 矩形覆盖

一、问题描述

题目描述
题目分析

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
public int rectCover(int n) {
    if (n <= 2)
        return n;
    int pre2 = 1, pre1 = 2;
    int result = 0;
    for (int i = 3; i <= n; i++) {
        result = pre2 + pre1;
        pre2 = pre1;
        pre1 = result;
    }
    return result;
}

剑指 Offer 10-4 变态跳台阶

一、问题描述

题目描述
题目分析

二、具体代码

1
2
3
public int JumpFloorII(int target) {
    return (int) Math.pow(2, target - 1);
}

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

一、问题描述

题目描述

二、具体代码

题目描述
$\color{red}{有序二分}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
1、找到波谷
"""
class Solution {
    public int minArray(int[] numbers) {
        int i=1;
        while(i<numbers.length&&numbers[i-1]<=numbers[i]) i+=1;
        if(i==numbers.length) return numbers[0];
        else return numbers[i];
    }
}
"""
2、因为递增 有序就要想到二分
数组最后一个数一定小于等于数组第一个数
"""
class Solution {
    public int minArray(int[] numbers) {
        int l=0,h=numbers.length-1;
        while(l<h){
            int m=l+(h-l)/2;  //防止high加low溢出
            if(numbers[m]<numbers[h]) h=m; //m右边一定是递增的 都是最小值右边的数
            else if(numbers[m]>numbers[h]) l=m+1; //m与h之间一定有最小值
            else h--; //去重
        }
        return numbers[h];
    }
}

剑指 Offer 12 矩阵中的路径

一、问题描述

题目描述

二、具体代码

$\color{red}{回溯}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
'''
回溯
'''
class Solution {
    public boolean exist(char[][] board, String word) {
        if(board.length<1||board[0].length<1||word.length()<1) return false;
        int w=board[0].length,h=board.length;
        boolean[][] visited=new boolean[h][w];
        char[] words=word.toCharArray();
        for(int i=0;i<h;i++) {
            for (int j=0;j<w;j++){
                if(words[0]==board[i][j]){ //遍历所有节点 看可以从哪个出发
                    if(dfs(board,i,j,visited,words,0)) return true;
                }
            }
        }
        return false;
    }
    //dfs(可访问的所有节点，本步想访问的节点下标，所有节点的访问状态，目标路径，已走到路径的哪一步)
    public boolean dfs(char[][] board,int i,int j,boolean[][] visited,char[] words,int idx){
        //找到满足条件的路径 返回
        if(words.length==idx) return true;
        //是否可以访问board[i][j] 条件判断
        if(i<0||j<0||i==board.length||j==board[0].length||visited[i][j]||board[i][j]!=words[idx]){
            return false;
        }
        //访问
        visited[i][j]=true;
        idx+=1;
        if(dfs(board,i-1,j,visited,words,idx)||dfs(board,i+1,j,visited,words,idx)||dfs(board,i,j-1,visited,words,idx)||dfs(board,i,j+1,visited,words,idx)){
            return true;
        }
        //撤销访问
        visited[i][j]=false;
        idx-=1;
        return false;
    }
}

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

一、问题描述

题目描述

二、具体代码

$\color{red}{回溯}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
'''
题目就是从[0,0]出发，能够达到哪些地方，只能往上下左右移动，且下标数位和小于k，其实也只需计算往右下移动的 因为左上都是回到已访问过的节点
注意 这道题选择后不能撤销 因为算的是全部能访问到的节点  访问后不可撤销
递归
'''
class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return backtrace(m,n,0,0,k,visited);
    }
    private int backtrace(int m ,int n, int i, int j, int k, boolean[][] visited){
        if(i>=m || j>=n) return 0;
        if(isValid(i,j,k,visited)){
            visited[i][j] = true; // 不可撤销访问
            return backtrace(m,n,i+1,j,k,visited)+backtrace(m,n,i,j+1,k,visited)+1;
        }
        return 0;
        
    }
    //判断是否可访问
    private boolean isValid(int i, int j, int k, boolean[][] visited){
        if(visited[i][j]==true) return false;
        int idxSum = 0;
        while(i>0){
            idxSum += i%10;
            i /= 10;
        }
        while(j>0){
            idxSum += j%10;
            j /= 10;
        }
        return !(idxSum>k);
    }
}

剑指 Offer 14 剪绳子

一、问题描述

题目描述
理论推导

二、具体代码

$\color{red}{理论推导 记吧}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
当每段都为3时，乘积最大
若最后为4，因为2*2大于1*3，所以乘4
其余情况就每段取3 再乘以小于3的
'''
class Solution {
    public int cuttingRope(int n) {
        int res=1;
        if(n<4) return n-1;
        while(n>4){
            res*=3;
            n-=3;
        }
        return res*n;
    }
}

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

一、问题描述

题目描述

二、具体代码

$\color{red}{位运算}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''
最右一位和1与 若最右一位为1 则结果为1 否则为0
判断完后 将数往右移一位
'''
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count=0;
        int help=1;
        while(n!=0){ //判断时要判断 n != 0 而不是 n>0 。 因为是无符号整数，带符号整数最高位是1时为负数。

            if((help&n)!=0) count+=1;
            n=n>>>1; //无符号右移 如果有符号 负数右移补1  死循环
        }
        return count;
    }
}

剑指 Offer 16 数值的整数次方

一、问题描述

题目描述
理论推导

二、具体代码

$\color{red}{快速幂（二分法）}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
'''
快速幂法（二分法角度）
'''
class Solution {
    public double myPow(double x, int n) {
        if(n==0) return 1.0;
        //Java 代码中 int32 变量in [-2147483648, 2147483647] n∈[−2147483648,2147483647] ，因此当 n = -2147483648时执行 n = -n会因越界而赋值出错。解决方法是先将n 存入 long 变量b，后面用 b操作即可。
        long b=n; 
        double res=1.0;
        if(n<0){
            x=1/x;
            b=-b;
        }
        while(b>0){
            if((b&1)!=0) res*=x; 
            x*=x;
            b=b>>1;
        }
        return res;
    }
}

剑指 Offer 18-2 删除链表中重复的结点

一、问题描述

题目描述
$\color{red}{链表}$

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
'''
伪造头结点来统一节点为空的情况
'''
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode preHead = new ListNode(-1);  //伪造的头结点
        ListNode pre = preHead;
        ListNode now = pHead;  //当前节点
        ListNode nextNode;  
        while(now != null){
            nextNode = now.next;
            if(nextNode!=null && now.val==nextNode.val){  //假如是重复节点，一直遍历到不同的节点
                while(now!=null && now.next!=null && now.val==nextNode.val){
                    now = nextNode;
                    nextNode = nextNode.next;
                } 
                now = nextNode;  // 因为要删除重复节点，所以直接跳过重复节点，now到下一个不一样的节点（也可能是重复的）
            }else{
                pre.next = now;
                pre = now;
                now = nextNode;
            }
        }
        pre.next = now; //假如由于重复节点一直到链表末，那么会由于now==null跳出循环，这时候要把不重复链表的最后一个节点指向now。否则会保留最后一段重复节点链表
        return preHead.next;
    }
}

剑指 Offer 19 正则表达式匹配

一、问题描述

题目描述
理论推导

二、具体代码

$\color{red}{麻烦}}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
'''
class Solution:
    def isMatch(self, s, p):
        m,n = len(s),len(p)
        dp = [[False for _ in range(n+1)] for _ in range(m+1)]
        dp[0][0] = True #空正则 空串

        for i in range(0,m+1):
            for j in range(1,n+1):
                if p[j-1]!='*':  
                    if i>0 and (p[j-1]==s[i-1] or p[j-1]=='.'):
                        dp[i][j]=dp[i-1][j-1]
                else:
                    if j>=2 and dp[i][j-2]==True:  # 不看*前的字符 
                        dp[i][j]=True
                    if i>=1 and j>=2 and (s[i-1]==p[j-2] or p[j-2]=='.') and dp[i-1][j]==True:  #看
                        dp[i][j]=True
        return dp[m][n]

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

一、问题描述

题目描述

二、具体代码

$\color{red}{双指针}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'''
双指针法 i指向偶数 j指向奇数 若i<j则交换
这种可以用于 不要求稳定性的情况
'''
class Solution {
    public int[] exchange(int[] nums) {
        int l=0,h=nums.length-1;
        while(l<h){
            while(l<nums.length&&(nums[l]&1)==1)l++;
            while(h>0&&(nums[h]&1)==0)h--;
            if(l>=h) return nums; 
            int temp=nums[h];
            nums[h]=nums[l];
            nums[l]=temp;
        }
        return nums;
    }
}

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

一、问题描述

题目描述
$\color{red}{双指针}$

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
双指针法 helper先走k步 随后helper和res同时走，当helper到达末尾时，res也就到达了倒数第k个数
若如果该链表长度小于k，请返回一个长度为 0 的链表。
'''
public ListNode FindKthToTail (ListNode pHead, int k) {
    // write code here
    ListNode res = pHead;
    ListNode p = pHead;
    while(p!=null && k>0){
        p = p.next;
        k--;
    }
    if(k>0) return null;
    while(p!=null){
        res=res.next;
        p=p.next;
    }
    return res;
}

剑指 Offer 23 链表中环的入口结点

一、问题描述

一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。
参考博客：https://blog.csdn.net/u012534831/article/details/74231581
题目描述
题目描述

$\color{red}{快慢指针}$

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
'''
快慢指针
'''
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead==null ||pHead.next==null) return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        do{
            fast = fast.next.next;
            slow = slow.next;
        }while(fast!=null && fast.next!=null && fast!=slow);
        if(fast==null ||fast.next==null) return null;
       
        fast = pHead;
        while(fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

剑指 Offer 24 反转链表

一、问题描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"""
pre p tmp 转p.next=pre 然后pre p后移一位
"""
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode p=head;
        while(p!=null){
            ListNode tmp=p.next;
            p.next=pre;
            pre=p;
            p=tmp;
        }
        return pre;
    }
}

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

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
'''
双指针法 i指向链表1待比较节点  j指向链表2待比较节点
'''
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode pre = new ListNode(-1);
        ListNode now = pre;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                now.next = list1;
                list1 = list1.next;
            }else{
                now.next = list2;
                list2 = list2.next;
            }
            now = now.next;
        }
        if(list2 == null) now.next = list1;
        if(list1 == null) now.next = list2;
        return pre.next;
    }
}
    '''
    同样思路 大佬的写法
    '''
    class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dum=new ListNode(0);//伪节点
        ListNode head=dum;
        while(l1!=null&&l2!=null){
            if(l1.val>l2.val) {
                dum.next=l2;
                l2=l2.next;
            }
            else {
                dum.next=l1;
                l1=l1.next;
            }
            dum=dum.next;
        }
        dum.next=(l1!=null)?l1:l2;
        return head.next;
    }
}

剑指 Offer 26 树的子结构

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
'''
递归
'''
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null) return false;
        if(issame(A,B)) return true;
        else return isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
    public boolean issame(TreeNode A,TreeNode B){
        if(B==null) return true; //遍历完了
        else if(A==null) return false;
        if(A.val!=B.val) return false;
        else return issame(A.left,B.left)&&issame(A.right,B.right);
    }
}
'''
二叉树的镜像（翻转左右子树）
'''
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null||(root.left==null&&root.right==null)) return root;
        mirrorTree(root.left);
        mirrorTree(root.right);
        TreeNode tmp=root.right;
        root.right=root.left;
        root.left=tmp;
        return root;
    }
}
'''
判断是否左右对称 
'''
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return issame(root.left,root.right);
    }
    public boolean issame(TreeNode A,TreeNode B){
        if(A==null&&B==null) return true;
        if(A==null||B==null) return false;
        return A.val==B.val&&issame(A.left,B.right)&&issame(A.right,B.left); //注意左右对称 是要左孩子与右孩子比
    }
}

剑指 Offer 29 顺时针打印矩阵

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
"""
模拟打印 
用二维数组存方向和对应的i，j边界变量增量 简化代码
空间为n  用来存是否访问过 
"""
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length<1||matrix[0].length<0) return new int[0];
        int[][] directions={{0,1},{1,0},{0,-1},{-1,0}};
        int m=matrix.length,n=matrix[0].length;
        boolean[][] visited=new boolean[m][n];
        int[] res=new int[m*n];
        res[0]=matrix[0][0];
        visited[0][0]=true;
        int i=0,j=0,idx=1,direct_idx=0;
        while (idx<res.length){
            int di=directions[direct_idx][0];
            int dj=directions[direct_idx][1];
            while(i+di<m&&i+di>=0&&j+dj<n&&j+dj>=0&& !visited[i + di][j + dj]){//按一个方向走到不能走
                i+=di;
                j+=dj;
                res[idx]=matrix[i][j];
                visited[i][j]=true;
                idx+=1;
            }
            direct_idx=(direct_idx+1)%4; //走不通 换方向
        }
        return res;
    }
}
"""
也可以用四个指针来指示可访问范围
"""
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length==0 || matrix[0].length==0) return new int[0];
        int w = matrix[0].length-1;
        int h = matrix.length-1;
        int[] res = new int[(w+1)*(h+1)];
        int wl = 0, wh = w, hl = 0, hh = h;
        int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};  //左下右上四个遍历方向
        int[][] range = {{1,0,0,0},{0,0,0,-1},{0,-1,0,0},{0,0,1,0}}; //对应遍历方向对可访问范围的影响
        int i = 0,j = 0,idx = 0,flag = 0;
        while(idx<res.length){
            while(j>=wl&&j<=wh&&i>=hl&&i<=hh){
                res[idx++] = matrix[i][j];
                i+=direction[flag][0];
                j+=direction[flag][1];
            }
            i-=direction[flag][0];
            j-=direction[flag][1]; //回到矩阵内
            //修改可访问范围
            hl+=range[flag][0];
            hh+=range[flag][1];
            wl+=range[flag][2];
            wh+=range[flag][3];
            //改变方向
            flag =(flag+1)%4;
            //从可访问的新起点出发
            i+=direction[flag][0];
            j+=direction[flag][1];
        }
        return res;
    }
}

剑指 Offer 30 包含min函数的栈

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
辅助栈 
重复的最小数都入最小栈
当弹出的数与最小栈顶值相同时 最小栈也同时弹出即可
"""
class MinStack {
    Stack<Integer> stack,minstack;
    /** initialize your data structure here. */
    public MinStack() {
        stack=new Stack<>();
        minstack=new Stack<>();
    }

    public void push(int x) {
       stack.push(x);
       if(minstack.isEmpty()||minstack.peek()>=x){ 
           minstack.push(x);
       }
    }

    public void pop() {
        int tmp=stack.pop();
        if(minstack.peek().equals(tmp)) minstack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minstack.peek();
    }
}

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

一、问题描述

题目描述
$\color{red}{模拟栈}$

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
    """
    辅助栈模拟弹入弹出过程中的栈
    根据弹出序列
        1、若该待弹出元素还没入栈 即在弹入序列中，则将弹入序列中排在该元素前的元素都压入栈中
        2、若该待弹出元素在栈中，则一定是栈顶元素 不然就False
    """
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack= new Stack<>();
        int push_idx=0,i=0;
        while (i<popped.length){
            if(stack.isEmpty()||stack.peek()!=popped[i]){//栈顶元素不为待弹出元素
                while(push_idx<pushed.length&&pushed[push_idx]!=popped[i]){
                    stack.add(pushed[push_idx++]);
                }
                if(push_idx<pushed.length) {
                    i+=1;
                    push_idx+=1;
                    continue;
                }
                return false;//待弹入没有待弹出元素
            }
            else { //若栈顶元素为待弹出的  直接出栈
                stack.pop();
                i+=1;
            }
        }
        return true;
    }
}

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int idx = 0;
        for(int i=0;i<popped.length;i++){
            int popNum = popped[i];
            if(!stack.isEmpty() && stack.peek()==popNum){ //若栈顶元素即为待弹出元素 直接弹出即可
                stack.pop();
                continue;
            }
            while(idx<pushed.length && pushed[idx]!=popNum){  //若不是 则将前面的数都压栈
                stack.push(pushed[idx++]);
            }
            if(idx<pushed.length && pushed[idx]==popNum){ //若未入栈的元素中找到待弹出元素
                idx++;
            }else{ //找不到 
                return false;
            }
        }
        return true;
    }
}

剑指 Offer 32_1 从上到下打印二叉树

一、问题描述

题目描述
$\color{red}{树层序遍历}$

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
"""
层序遍历
"""
class Solution {
    public int[] levelOrder(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;
    }
}
"""
2、分层 二维矩阵输出
"""

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null) return new LinkedList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int len;
        List<List<Integer>> res=new LinkedList<>();
        while(!queue.isEmpty()){
            List<Integer> tmplayer= new LinkedList<>();
            len=queue.size();
            while(len>0){
                TreeNode tmp=queue.poll();
                len-=1;
                tmplayer.add(tmp.val);
                if(tmp.left!=null) queue.add(tmp.left);
                if(tmp.right!=null) queue.add(tmp.right);
            }
            res.add(tmplayer);
        }
        return res;
    }
}
""" 
3、分层 隔层逆序输出 加个flag就可
"""
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null) return new LinkedList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int len;
        List<List<Integer>> res=new LinkedList<>();
        boolean flag=false;
        while(!queue.isEmpty()){
            List<Integer> tmplayer= new LinkedList<>();
            len=queue.size();
            while(len>0){
                TreeNode tmp=queue.poll();
                len-=1;
                if(flag){
                    tmplayer.add(0,tmp.val);
                }
                else
                {tmplayer.add(tmp.val);}
                if(tmp.left!=null) queue.add(tmp.left);
                if(tmp.right!=null) queue.add(tmp.right);
            }
            flag=!flag;
            res.add(tmplayer);
        }
        return res;
    }
}

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

一、问题描述

题目描述

$\color{red}{递归}$

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
"""
二叉搜索树的后序遍历有个特点：
根节点是最后一个数  并且可以将序列按顺序切割  前一截小于根节点的为左子树，后一截大于根节点的为右子树。
l,m-1为左子树
m,h-1为右子树
"""
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder,0,postorder.length-1);
    }
    public boolean recur(int[] postorder,int l,int h){
        if(l>=h) return true;
        int m,p=l;
        int root=postorder[h];
        while(postorder[p]<root) p++;
        m=p;
        while(postorder[p]>root) p++;
        return p==h&&recur(postorder,l,m-1)&&recur(postorder,m,h-1); 
    }
}

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

一、问题描述

题目描述

二、具体代码

回溯+dfs 先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    private ArrayList<Integer> path = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        backtrace(root, target);
        return res;
    }
    private void backtrace(TreeNode root, int target){
        if(root == null) return;
        path.add(root.val); //选择
        if(root.left==null && root.right==null && root.val==target){
            res.add(new ArrayList<>(path));
        }else{
            backtrace(root.left, target-root.val);
            backtrace(root.right, target-root.val);
        }
        path.remove(path.size()-1); //撤销选择
    }
}

剑指 Offer 35 复杂链表的复制

一、问题描述

题目描述

二、具体代码

具体分为3步:

1、在每个原节点后面新增一个节点 值与原节点一致 temp=Node(cur.val,cur.next)

2、复制原节点的randan指针  新节点的randan指向原节点randan的后一个节点  copycur.random=cur.random.next

3、拆分链表  要注意两个链表的末尾的next都为None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;      // 返回新链表头节点
    }
}

剑指 Offer 36 二叉搜索树与双向链表

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
"""
利用二叉搜索树中序遍历是递增的这一特性  
递归中序遍历
另外新增两个指针节点 head和pre
"""

public class Solution {
    private TreeNode pre;
    private TreeNode head;
    public TreeNode Convert(TreeNode pRootOfTree) {
        inOrder(pRootOfTree);
        return head;
    }
    private void inOrder(TreeNode root){
        if(root == null) return;
        inOrder(root.left);
        root.left = pre;
        if(pre!=null) pre.right = root;
        if(head == null) head = root;
        pre = root;
        inOrder(root.right);
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    Node pre ;
    Node head = null;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        reCur(root);
        //循环双向链表 头尾节点连起来
        head.left = pre; 
        pre.right = head;
        return head;
    }
    private void reCur(Node root){
        if(root==null) return;
        reCur(root.left);
        if(head == null){
            head = root;
        }
        if(pre != null){
            pre.right = root;   
        }
        root.left = pre;
        pre = root;
        reCur(root.right);
    }
}

剑指 Offer 37 序列化二叉树

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
"""
序列化的字符串实际上是二叉树的 “层序遍历”（BFS）结果
队列模仿层序遍历 
string->int  Integer.parseInt(string)
int ->string   string.valueof(int)
string截断  .substring()

"""

public class Codec {
    public String serialize(TreeNode root) {
        if(root==null) return "[]";
        StringBuilder res=new StringBuilder("[");
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode temp=queue.poll();
            if(temp!=null){
                res.append(temp.val+",");
                queue.add(temp.left);//左右节点入队
                queue.add(temp.right);
            }
            else res.append("null,");
        }
        res.delete(res.length()-1,res.length()-1);
        res.append("]");
        return res.toString();
    }
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] nums=data.substring(1,data.length()-1).split(",");
        Queue<TreeNode> queue=new LinkedList<>();
        TreeNode root=new TreeNode(Integer.parseInt(nums[0]));
        queue.add(root);
        int i=1;
        while (!queue.isEmpty()){
            TreeNode temp=queue.poll();
            if(temp!=null){
                if(!nums[i].equals("null")){
                    temp.left=new TreeNode(Integer.parseInt(nums[i]));
                    queue.add(temp.left);
                }
                i+=1;
                if(!nums[i].equals("null")){
                    temp.right=new TreeNode(Integer.parseInt(nums[i]));
                    queue.add(temp.right);
                }
                i+=1;
            }
        }
        return root;
    }
}

剑指 Offer 38 字符串的全排列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
"""
回溯+剪枝
"""
import java.util.*;

public class Solution {
    public String[] permutation(String s) {
        int len = s.length();
        if (len == 0) {
            return new String[0];
        }
        // 转换成字符数组是常见的做法
        char[] charArr = s.toCharArray();
        // 排序是为了去重方便
        Arrays.sort(charArr);
        // 由于操作的都是字符，使用 StringBuilder
        StringBuilder path = new StringBuilder();
        boolean[] used = new boolean[len];

        // 为了方便收集结果，使用动态数组
        List<String> res = new ArrayList<>();
        dfs(charArr, len, 0, used, path, res);

        // 记得转成字符串数组
        return res.toArray(new String[0]);
    }

    /**
     * @param charArr 字符数组
     * @param len     字符数组的长度
     * @param depth   当前递归深度
     * @param used    当前字符是否使用
     * @param path    从根结点到叶子结点的路径
     * @param res     保存结果集的变量
     */
    private void dfs(char[] charArr,
                     int len,
                     int depth,
                     boolean[] used,
                     StringBuilder path,
                     List<String> res) {
        if (depth == len) {
            // path.toString() 恰好生成了新的字符对象
            res.add(path.toString());
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                if (i > 0 && charArr[i] == charArr[i - 1] && !used[i - 1]) {
                    continue;
                }
                used[i] = true;
                path.append(charArr[i]);

                dfs(charArr, len, depth + 1, used, path, res);

                // 递归完成以后，需要撤销选择，递归方法执行之前做了什么，递归方法执行以后就需要做相应的逆向操作
                path.deleteCharAt(path.length() - 1);
                used[i] = false;
            }
        }
    }
}
"""
不剪枝
"""
class Solution {
    Set<String> res = new HashSet<>();
    public String[] permutation(String s) {
        char[] charArr = s.toCharArray();
        boolean[] visited = new boolean[charArr.length];
        backTrace(charArr, visited, new StringBuilder());
        return res.toArray(new String[0]);
    }
    private void backTrace(char[] charArr, boolean[] visited, StringBuilder tmp){
        if(tmp.length()==charArr.length){
            res.add(tmp.toString());
            return;
        }
        for (int i = 0; i < charArr.length; i++) {
            if(!visited[i]){
                visited[i] = true;
                tmp.append(charArr[i]);
                backTrace(charArr, visited, tmp);
                visited[i] = false;
                tmp.deleteCharAt(tmp.length()-1);
            }
        }
    }
}

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

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
"""
摩尔投票法：
设输入数组 nums 的众数为 x ，数组长度为 n 。
推论一： 若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 > 0。                                  
推论二： 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n-a)个数字的 票数和一定仍 >0 ，即后(n−a) 个数字的 众数仍为x 。

算法流程:
初始化： 票数统计 votes = 0 ， 众数 x；
循环： 遍历数组 nums 中的每个数字 num ；
当 票数 votes 等于 0 ，则假设当前数字 num 是众数；
当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 ；
返回值： 返回 x 即可；
"""

class Solution {
    public int majorityElement(int[] nums) {
        int num=nums[0];
        if(nums.length<3){
            return nums[0];
        }
        int count=0;
        for(int i:nums){
            if(i==num){
                count+=1;
            }
            else if(count>1){
                count-=1;
            }
            else{
                num=i;
                count=1;
            }
        }
        return num;
    }
}

"""
若找出投票超过1/3的候选人
"""
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        // 创建返回值
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        // 初始化两个候选人candidate，和他们的计票
        int cand1 = nums[0], count1 = 0;
        int cand2 = nums[0], count2 = 0;

        // 摩尔投票法，分为两个阶段：配对阶段和计数阶段
        // 配对阶段
        for (int num : nums) {
            // 投票
            if (cand1 == num) {
                count1++;
                continue;
            }
            if (cand2 == num) {
                count2++;
                continue;
            }

            // 第1个候选人配对
            if (count1 == 0) {
                cand1 = num;
                count1++;
                continue;
            }
            // 第2个候选人配对
            if (count2 == 0) {
                cand2 = num;
                count2++;
                continue;
            }

            count1--;
            count2--;
        }

        // 计数阶段
        // 找到了两个候选人之后，需要确定票数是否满足大于 N/3
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (cand1 == num) count1++;
            else if (cand2 == num) count2++;
        }

        if (count1 > nums.length / 3) res.add(cand1);
        if (count2 > nums.length / 3) res.add(cand2);

        return res;
    }
}

作者：wotxdx
链接：https://leetcode-cn.com/problems/majority-element-ii/solution/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

剑指 Offer 40 最小的k个数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
"""
1、大堆  
我们用一个大根堆实时维护数组的前 k 小值。每次大根堆中数字的个数超过k后，将最大的弹出，这样每次留下来的都是最小的k个数

"""
public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
    if (k > nums.length || k <= 0)
        return new ArrayList<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    for (int num : nums) {
        maxHeap.add(num);
        if (maxHeap.size() > k)
            maxHeap.poll();
    }
    return new ArrayList<>(maxHeap);
}


"""
2、快排
当partition的下标i==k-1时 要找的便为该数
"""
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0 || arr.length==0){
            return new int[0];
        }
        else
            return quicksort(arr,0,arr.length-1,k-1);//第k个数的下标为k-1
    }
    //nums[k]的左边都小于它  右边都大于它
    //其中k为下标
    private int[] quicksort(int[] nums,int lo,int hi,int k){
        int pivot=partition(nums,lo,hi);
        if(pivot==k){
            return Arrays.copyOf(nums,k+1);
        }
        else{
            return pivot>k?quicksort(nums,lo,pivot-1,k):quicksort(nums,pivot+1,hi,k);
        }
    }
    // 将nums[lo]作为基准 进行划分  最后返回pivot 
    //nums[pivot]的左边都小于它  右边都大于它
    private int partition(int[] nums,int lo,int hi){
        int pivot_value=nums[lo];
        int i=lo,j=hi+1;
        while(true){
            while(++i<=hi && nums[i]<pivot_value);
            while (--j>=lo && nums[j]>pivot_value);
            if(i>=j){
                break;
            }
            int temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
        nums[lo]=nums[j];
        nums[j]=pivot_value;
        return j;
    }
}
"""
3、二叉搜索树--TreeMap
我们遍历数组中的数字，维护一个数字总个数为 K 的 TreeMap：
1.若目前 map 中数字个数小于 K，则将 map 中当前数字对应的个数 +1；
2.否则，判断当前数字与 map 中最大的数字的大小关系：若当前数字大于等于 map 中的最大数字，就直接跳过该数字；若当前数字小于 map 中的最大数字，则将 map 中当前数字对应的个数 +1，并将 map 中最大数字对应的个数减 1。

"""
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是为了更方便的输出map键值对。entry.getvalue()获得当前entry的值   entry.getkey()获得当前entry的键
            //java.util.TreeMap.lastEntry() 返回具有最大键的键值对；如果没有这样的键，则返回null。
            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 42 连续子数组的最大和

一、问题描述

题目描述
问题思路

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
动态规划
dp 以当前节点为结尾的数组和的最大值 若前一个节点的最大值为正 直接加上即可 不然就不加
随时更新全局最大值
"""
class Solution {
    public int maxSubArray(int[] nums) {
        int pre = nums[0]; //以上一个节点结尾的子数组和的最大值
        int res = nums[0]; //全局最大
        for(int idx = 1;idx < nums.length; idx++){
            if(pre<=0){ // 前一个节点没贡献 直接放弃
                res = Math.max(res, nums[idx]);
                pre = nums[idx];
            }else{ //若前一个节点的最大值为正 直接加上即可
                pre = nums[idx] + pre;
                res = Math.max(res, pre);
            }
        }
        return res;
    }
}

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

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
"""
左右均分用大小堆存  注意返回要为double，所以最后/2.0
"""
class MedianFinder {
    Queue<Integer> left,right; //数组排序后均分到left，right
    /** initialize your data structure here. */
    public MedianFinder() {
        left=new PriorityQueue<>((x,y)->(y-x));//大堆 堆顶元素为最靠近middle的元素
        right=new PriorityQueue<>();//小堆 堆顶元素为最靠近middle的元素
    }
    //默认把多的一个数加到left  中位数就为left的堆顶
    public void addNum(int num) {
        if(left.size()==right.size()){
            right.add(num);//先加到右边 再把右边最小的元素加到左边
            left.add(right.poll());
        }
        else {
            left.add(num);
            right.add(left.poll());
        }
    }

    public double findMedian() {
        if(left.size()==right.size()){
            return (left.peek()+right.peek())/2.0;
        }
        else return left.peek();
    }
}
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

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

一、问题描述

题目描述

二、具体代码

问题思路
问题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int countDigitOne(int n) {
        int digit=1,low=0,high=n/10;
        int cur=n%10,res=0;
        while(cur!=0||high!=0){
            if(cur==0) res+=high*digit;  
            else if(cur==1) res+=high*digit+low+1;
            else res+=(high+1)*digit;
            low+=cur*digit;
            digit*=10;
            cur=high%10;
            high/=10;
        }
        return res;
    }
}

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

一、问题描述

题目描述

二、具体代码

问题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findNthDigit(int n) {
        int digit = 1;   // n所在数字的位数
        long start = 1;  // 数字范围开始的第一个数
        long count = 9;  // 占多少位
        while(n>count){
            n-=count;
            digit+=1;
            start*=10;
            count=digit*start*9; //每个位数对应数字占的总个数
        }
        //属于哪个数
        long num=start+(n-1)/digit;  //n-1是因为最开始的0没计数
        int res=(n-1)%digit;  //属于该数的第几位
        return Long.toString(num).charAt(res)-'0';
    }
}

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

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String minNumber(int[] nums) {
        String[] strs=new String[nums.length];
        for(int i=0;i<nums.length;i++){
            strs[i]=String.valueOf(nums[i]);  //把int数组转化为string数组
        }
         //string数组排序  排序规则 x+y(字符串拼接)>y+x 则x大 否则y大
         //lamda表达式  (参数)->{表达式}
        Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x));
        //把string数组转化为string
        StringBuilder res=new StringBuilder();  
        for(String temp:strs){
            res.append(temp);
        }
        return res.toString();
    }
}

剑指 Offer 46 把数字翻译成字符串

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"""
递归  也可以dp
"""
class Solution {
    public int translateNum(int num) {
        if(num<10){  //单位数 只有一种翻译
            return 1;
        }
        int yushu=num%100;
        if(yushu<10 || yushu>25) //只有一种翻译
            {return translateNum(num/10);}
        else{
            return translateNum(num/10)+translateNum(num/100); //可以有两种翻译  既可以当做一个字母，也可以当做两个字母
        }
    }
}

剑指 Offer 47 礼物的最大价值

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
dp
"""
class Solution {
    public int maxValue(int[][] grid) {
        int[][] dp=new int[grid.length][grid[0].length];
        dp[0][0]=grid[0][0];//dp[i][j]代表到达(i,j)能拿到的最大礼物价值
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                int left=j>0?dp[i][j-1]:0;  //从左边到达
                int top=i>0?dp[i-1][j]:0;   //从上边到达
                dp[i][j]=Math.max(left,top)+grid[i][j];  //取最大
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}

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

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
右边界一步一步向右移，左边界=无重复元素的最左下标  left只可能增加，不可能减少，采用Math.max来更新left
不重复的长度= right-left+1
动态更新res即可
"""
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i))+1); //若下标i的对应重复元素下标为idx，下标i+1的对应重复元素下标为jdx，且jdx<idx。采用Math.max可以避免检测到区间外的重复字符。
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;   
    }
}

//每次
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        char[] charArrs = s.toCharArray();
        int res = 0;
        int left = 0, right = 0;
        while(right<charArrs.length){
            if(!map.containsKey(charArrs[right])){
                map.put(charArrs[right], right);
            }else{
                int preIdx = map.get(charArrs[right]);
                while(left<=preIdx){  //去除区间外的元素
                    map.remove(charArrs[left]);
                    left++;
                }
                map.put(charArrs[right], right);
            }
            right++;
            res = Math.max(res, right-left);
        }
        return Math.max(res, right-left);
    }
}

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
动态规划 
"""
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res=0;
        int temp=0; // dp[j-1]
        Map<Character,Integer> map=new HashMap<>();
        for(int j=0;j<s.length();j++) {
            int i = map.getOrDefault(s.charAt(j),-1);   // 获取最新出现字符j对应的索引 i
            map.put(s.charAt(j),j); //更新索引表
            temp=temp<j-i?temp+1:j-i; //获得dp[j] 若dp[j-1]<j-i即i在子串dp[j-1]区间之外 dp[j]=dp[j-1]+1 不然就在区间内 dp[j]=j-i  
            res=Math.max(temp,res); 
        }
        return res;
    }
}

剑指 Offer 49 丑数

一、问题描述

题目描述

二、具体代码

$\color{red}{多路归并 多指针}$

$\color{red}{优先队列 集合去重}$
具体思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

"""
三指针法  所有丑数的排列，必定就是ABC3个数组的合并结果然后去重得到的，就转换成了三个有序数组的无重复元素合并的问题
"""
class Solution {
    public int nthUglyNumber(int n) {
        if(n==0){
            return 0;
        }
        int[] ugly = new int[n];
        ugly[0]=1;
        int i=0,j=0,k=0;
        for(int idx=1;idx<n;idx++){
            int temp=Math.min(ugly[i]*2,Math.min(ugly[j]*3,ugly[k]*5));
            // 由于可能不同有序序列之间产生相同丑数，因此只要一样的丑数就跳过（不能使用 else if ）
            if(temp==ugly[i]*2)i++;
            if(temp==ugly[j]*3)j++;
            if(temp==ugly[k]*5)k++;
            ugly[idx]=temp;
        }
        return ugly[n-1];
    }
}

"""
优先队列去重  最小堆
"""
class Solution {
    int[] nums = new int[]{2,3,5};
    public int nthUglyNumber(int n) {
        Set<Long> set = new HashSet<>();
        Queue<Long> pq = new PriorityQueue<>();
        set.add(1L);
        pq.add(1L);
        for (int i = 1; i <= n; i++) {
            long x = pq.poll();
            if (i == n) return (int)x;
            for (int num : nums) {
                long t = num * x;
                if (!set.contains(t)) {
                    set.add(t);
                    pq.add(t);
                }
            }
        }
        return -1;
    }
}

373. 查找和最小的K对数字

一、问题描述

题目描述

解题思路：
题目描述

https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/solution/bu-chong-guan-fang-ti-jie-you-xian-dui-l-htf8/

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
"""
多路归并  + 优先队列（最小堆）

我们可以将 nums2 的前 k 个索引数对 (0,0),(0,1),…,(0,k−1) 加入到队列中，每次从队列中取出元素 (x,y) 时，我们只需要将 nums1的索引增加即可，这样避免了重复加入元素【不然（0,1)  (1,0)都会将(1,1)加入堆中】的问题。

"""
class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        // 最小堆 存下一个选择
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b)->{return nums1[a[0]]+nums2[a[1]]-nums1[b[0]]-nums2[b[1]];});
        int m = nums1.length;
        int n = nums2.length;
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0;i<n;i++) {
            heap.add(new int[]{0,i});  
        }
        int idx = 0;
        while(idx<k && !heap.isEmpty()){
            int[] minCouple = heap.poll(); //下一个选择
            List<Integer> couple = new ArrayList<>();
            couple.add(nums1[minCouple[0]]);
            couple.add(nums2[minCouple[1]]);
            res.add(couple);
            idx++;
            if(minCouple[0]+1<m){ //该选择后新增的可选择
                heap.add(new int[]{minCouple[0]+1, minCouple[1]});
            }
           
        }
        return res;
    }
}

剑指 Offer 50 第一个只出现一次的字符

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
"""
数组存出现次数 再遍历一次找第一个出现次数为一次的字符返回即可
"""
class Solution {
    public char firstUniqChar(String s) {
        int[] count=new int[26];
        for(char c:s.toCharArray()){
            count[c-'a']+=1;
        }
        for(char c:s.toCharArray()){
            if(count[c-'a']==1){
                return c;
            }
        }
        return ' ';
    }
}

"""
维持一个队列，其中队首永远是目前只出现一次的数
也就是每次insert的时候，都去检测队首，若队首出现不止一次，则删除，直到队首只出现一次为止
由于是字符，ASCII码只有128个字符，所以可以用128长的数组来记录出现次数
"""
import java.util.*;
public class Solution {
    //Insert one char from stringstream
    int[] cnt = new int[128];
    Queue<Character> queue = new LinkedList<>();
    public void Insert(char ch)
    {
        cnt[ch]++;
        queue.add(ch);
        while(!queue.isEmpty() && cnt[queue.peek()]>1){
            queue.poll();
        }
        
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        return queue.isEmpty()?'#':queue.peek();
    }
}

剑指 Offer 51 数组中的逆序对

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
"""
归并排序
在于「归并」当中「并」的过程：在左右两个有序数组合并的过程中计算逆序对
"""
public class Solution {
    public int reversePairs(int[] nums) {
        int len = nums.length;

        if (len < 2) {
            return 0;
        }

        int[] copy = new int[len];
        for (int i = 0; i < len; i++) {
            copy[i] = nums[i];
        }

        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    //nums[left..right] 计算逆序对个数并且排序
    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(nums, left, mid, temp);  //左半数组的逆序对
        int rightPairs = reversePairs(nums, mid + 1, right, temp); //右半数组的逆序对

        if (nums[mid] <= nums[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int crossPairs = mergeAndCount(nums, left, mid, right, temp); //交叉的逆序对
        return leftPairs + rightPairs + crossPairs;
    }

    //nums[left..mid] 有序，nums[mid + 1..right] 有序
    private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int count = 0;
        for (int k = left; k <= right; k++) {

            if (i == mid + 1) {
                nums[k] = temp[j];//左边已全部入栈 将右边顺序入就可以
                j++;
            } else if (j == right + 1) { //右边已全部入栈 将左边顺序入就可以
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else { //只有左边大于右边 才需要计算逆序对
                nums[k] = temp[j];
                j++;
                count += (mid - i + 1); //重点！逆序对个数
            }
        }
        return count;
    }
}

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

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
"""
求得A,B的长度 由于公共节点，则最后的末节点一定一致
双指针 将两者的长度调为一致后  一起往后移动  遇到第一个相同的节点即为第一个公共节点
"""
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int len1 = 0;
        int len2 = 0;
        ListNode p1 = pHead1, p2 = pHead2;
        //
        while(p1!= null){
            len1+=1;
            p1= p1.next;
        }
        while(p2 != null){
            len2+=1;
            p2 = p2.next;
        }
        if(len1>len2){
            int k = len1-len2;
            while(k>0){
                pHead1 = pHead1.next;
                k-=1;
            }
        }else{
            int k = len2-len1;
            while(k>0){
                pHead2 = pHead2.next;
                k-=1;
            }
        }
        while(pHead2 != pHead1){
            pHead2 = pHead2.next;
            pHead1 = pHead1.next;
        }
        return pHead2;
    }
}

"""
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。

当访问链表 A 的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问链表 B 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
"""
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    ListNode l1 = pHead1, l2 = pHead2;
    while (l1 != l2) {
        l1 = (l1 == null) ? pHead2 : l1.next;
        l2 = (l2 == null) ? pHead1 : l2.next;
    }
    return l1;
}

剑指 Offer 53_1 在排序数组中查找数字

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
"""
二分查找+双指针拓展找边界
"""
class Solution {
    public int search(int[] nums, int target) {
        //二分查找
        int index=bisearch(nums,target);
        if(index==-1){
            return 0;
        }
        int low=index-1,high=index+1;
        //拓展找边界
        while(low>=0&&nums[low]==target)low--;
        while (high<nums.length&&nums[high]==target) high++;
        return high-low-1;
    }
    //二分查找
    public int bisearch(int[] nums,int target){
        int low=0,high=nums.length-1;
        while(low<=high){
            int mid=(low+high)/2;
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[mid]<target){
                low=mid+1;
            }
            else {
                high=mid-1;
            }
        }
        return -1;
    }
}

剑指 Offer 53_2 0~n-1中缺失的数字

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
二分查找
"""
class Solution {
    public int missingNumber(int[] nums) {
        int low=0,high=nums.length-1;
        while(low<=high){
            int mid=(low+high)/2;
            if(nums[mid]==mid){
                low=mid+1;
            }
            else{
                high=mid-1;
            } 
        }
        return low; //low指向右子数组的首位元素
    }
}

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

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""
利用二叉搜索树中序遍历递增的规则 右中左遍历 第k个数即为所求结果。
"""
class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }
}
"""
递归 但时间复杂度高  若k=1 则重复计算右子树个数
"""
    public int kthLargest(TreeNode root, int k) {
        int right=treenum(root.right);
        if(right<k){
            if(right==k-1){
                return root.val;
            }
            else {
                return kthLargest(root.left,k-right-1);
            }
        }
        else {
            return kthLargest(root.right,k);
        }
    }
    public int treenum(TreeNode root){
        if(root==null){
            return 0;
        }
        return treenum(root.left)+treenum(root.right)+1;
    }

剑指 Offer 55 二叉树的深度

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
"""
层序遍历
"""
class Solution {
    public int maxDepth(TreeNode root) {
        //层序遍历
        if(root==null) return 0;
        List<TreeNode> now_layer=new ArrayList<TreeNode>();
        List<TreeNode> next_layer=new ArrayList<TreeNode>();
        int res=0;
        now_layer.add(root);
        while(now_layer.size()>0){
            res+=1;
            for(TreeNode p:now_layer){
                if(p.left!=null) next_layer.add(p.left);
                if(p.right!=null) next_layer.add(p.right);
            }
            now_layer=next_layer;
            next_layer=new ArrayList<TreeNode>();
        }
        return res;
    }
}
"""
深度遍历（递归）
"""
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

剑指 Offer 55-1 平衡二叉树

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""
自底向上 剪枝
"""
public class code {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        return treedepth(root)!=-1;
    }
    //在计算高度的时候同时判断是否平衡 若不平衡 直接返回
    public int treedepth(TreeNode root){
        if(root==null) return 0; //高度为0
        int left=treedepth(root.left);
        if(left==-1) return -1;
        int right=treedepth(root.right);
        if(right==-1) return -1;
        return Math.abs(left-right)<=1?Math.max(left,right)+1:-1; //若平衡 则返回高度 不然就返回-1；
    }
}
"""
自上而下直接递归算子树高度 判断平衡条件  因为会有重复计算 所以时间复杂度会比较高
"""
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if(isBalanced(root.left)&&isBalanced(root.right)){
            if(Math.abs(treedepth(root.left)-treedepth(root.right))<=1){
                return true;
            }   
        }
        return false;
    }
    public int treedepth(TreeNode root){
        if(root==null){
            return 0;
        }
        return Math.max(treedepth(root.left),treedepth(root.right))+1;
    }
}

剑指 Offer 56-1 数组中数字出现的次数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
在异或结果中找到任意为 1 的位(取最低位为1的那位）。
根据这一位对所有的数字进行分组。
在每个组内进行异或操作，得到两个数字。
"""
class Solution {
    public int[] singleNumbers(int[] nums) {
        int res=0;
        int[] result=new int[2];
        for(int temp:nums){
            res^=temp;  //得到两个数的异或
        }
        int k=1;
        while((k&res)==0){ //得到最低位为1的那个位
            k=k<<1;
        }
        int a=0,b=0;
        for(int temp:nums){
            if((k&temp)==0){
                a^=temp;  
            }
            else{
                b^=temp;  
            }
        }
        result[0]=a;
        result[1]=b;
        return result;
    }
}

剑指 Offer 56-2 数组中数字出现的次数2

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1;
同样适用于某位数字出现一次 其余数字出现奇数次的情况
若其余数字出现偶数次 则可以直接用异或
"""
public class Solution56_2 {
	
    public int singleNumber(int[] nums) {//本算法同样适用于数组nums中存在负数的情况
        if(nums.length==0) return -1;//输入数组长度不符合要求，返回-1;
        int[] bitSum = new int[32];//java int类型有32位，其中首位为符号位
        int res=0;
        for(int num:nums){
            int bitMask=1;//需要在这里初始化，不能和res一起初始化
            for(int i=31;i>=0;i--){//bitSum[0]为符号位
            	//这里同样可以通过num的无符号右移>>>来实现，否则带符号右移(>>)左侧会补符号位，对于负数会出错。
            	//但是不推荐这样做，最好不要修改原数组nums的数据
                if((num&bitMask)!=0) bitSum[i]++;//这里判断条件也可以写为(num&bitMask)==bitMask,而不是==1
                bitMask=bitMask<<1;//左移没有无符号、带符号的区别，都是在右侧补0
            }
        }
        for(int i=0;i<32;i++){//这种做法使得本算法同样适用于负数的情况
            res=res<<1;
            res+=bitSum[i]%3;//这两步顺序不能变，否则最后一步会多左移一次
        }
        return res;
    }
}

剑指 Offer 57 和为s的两个数字

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
递增所以可以用双指针法
不然直接用Hashmap遍历
"""
import java.util.ArrayList;
import java.util.*;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int left = 0;
        int right = array.length-1;
        while(left<right){
            int now_sum = array[left]+array[right];
            if(now_sum==sum){
                return new ArrayList<>(Arrays.asList(array[left],array[right]));
            }else if(now_sum<sum){
                left++;
            }else{
                right--;
            }
        }
        return new ArrayList<>();
    }
}

剑指 Offer 57_2 和为 S 的连续正数序列

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
"""
用双指针法
"""
import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
       int left = 1, right = 2, curSum = 3;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        while(right<sum){
            if(curSum<sum){  //若和小
                right++;
                curSum+=right;
            }else if(curSum>sum){  //若和大
                curSum-=left;
                left++;
            }else{
                ArrayList list = new ArrayList<>();
                for(int i = left; i<=right; i++){
                    list.add(i);
                }
                res.add(list);
                // 整体往后移，找新的连续序列
                // 新的肯定left++  left增加后 cursum肯定小于sum，于是直接right++
                curSum-=left;
                left+=1;
                right+=1;
                curSum+=right;
            }
        }
        return res;
    }
}

剑指 Offer 58_1 翻转单词顺序列

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
用双指针法
public String trim()
    返回一个字符串，其值为此字符串，删除了所有前导和尾随空格
"""
class Solution {
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }
}
"""
用java内置函数split
public String[] split​(String regex)
    将此字符串拆分为给定regular expression的匹配项 。
    结尾的空字符串不包含在结果数组中。
"""
class Solution {
    public String reverseWords(String s) {
        String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
        StringBuilder res = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            if(strs[i].equals("")) continue; // 遇到空单词则跳过
            res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
        }
        return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
    }
}

剑指 Offer 58_2 左旋转字符串

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
"""
左旋 右旋 然后一起旋
"""
public String LeftRotateString(String str, int n) {
    if (n >= str.length())
        return str;
    char[] chars = str.toCharArray();
    reverse(chars, 0, n - 1);
    reverse(chars, n, chars.length - 1);
    reverse(chars, 0, chars.length - 1);
    return new String(chars);
}

private void reverse(char[] chars, int i, int j) {
    while (i < j)
        swap(chars, i++, j--);
}

private void swap(char[] chars, int i, int j) {
    char t = chars[i];
    chars[i] = chars[j];
    chars[j] = t;
}
"""
内置substring函数
"""
class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n)+s.substring(0,n);
    }
}
"""
stringbuilder  .charAt()  .append()  .toString
"""
class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder();
        for(int i = n; i < s.length(); i++)
            res.append(s.charAt(i));
        for(int i = 0; i < n; i++)
            res.append(s.charAt(i));
        return res.toString();
    }
}

"""
string函数 .charAt()
"""
class Solution {
    public String reverseLeftWords(String s, int n) {
        String res = "";
        for(int i = n; i < s.length(); i++)
            res += s.charAt(i);
        for(int i = 0; i < n; i++)
            res += s.charAt(i);
        return res;
    }
}

剑指 Offer 59_1 滑动窗口的最大值

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
用双端队列来维护窗口内的单调栈（单调递减
"""
import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        if(num.length<0 || size>num.length || size<1){
            return new ArrayList<>();
        }
        Deque<Integer> deque = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<>();
        for(int i=0;i<size;i++){ //窗口未形成
            while(!deque.isEmpty() && deque.peekLast()<num[i]){
                deque.removeLast();
            }
            deque.addLast(num[i]);
        }
        for(int i = size;i<num.length;i++){ 
            res.add(deque.peekFirst()); //前一个滑动窗口的最大值
            //移动 需要删除头部
            if(num[i-size]==deque.peekFirst()){ 
                deque.removeFirst();
            }
            //移动 需要添加尾部
            while(!deque.isEmpty() && deque.peekLast()<num[i]){ 
                deque.removeLast();
            }
            deque.addLast(num[i]);
        }
        res.add(deque.peekFirst());
        return res;
    }
}

剑指 Offer 59_2 队列的最大值

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
"""
用双端队列来维护队列内的单调栈（单调递减
"""
class MaxQueue {
    Queue<Integer> q;
    Deque<Integer> d;

    public MaxQueue() {
        q = new LinkedList<Integer>();
        d = new LinkedList<Integer>();
    }
    
    public int max_value() {
        if (d.isEmpty()) {
            return -1;
        }
        return d.peekFirst();
    }
    
    public void push_back(int value) {
        while (!d.isEmpty() && d.peekLast() < value) {
            d.removeLast();
        }
        d.addLast(value);
        q.add(value);
    }
    
    public int pop_front() {
        if (q.isEmpty()) {
            return -1;
        }
        int ans = q.remove();
        if (ans == d.peekFirst()) {
            d.removeFirst();
        }
        return ans;
    }
}

剑指 Offer 60 n个骰子的点数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
"""
动态规划
n个筛子能投的点数k的次数等于n-1个筛子能投的点数（k-6,k-5,k-4,k-3,k-2,k-1)的个数和
for (第n枚骰子的点数 i = 1; i <= 6; i ++) {
    dp[n][j] += dp[n-1][j - i]
}
"""
class Solution {
    public double[] dicesProbability(int n) {
        int[] counts=new int[n*6+1];  
        double[] res=new double[n*5+1];
        for(int i=1;i<=6;i++) {
            counts[i]=1;  //一个筛子 能得到点数i（1~6）的次数为1
        }
        for(int i=2;i<=n;i++){
            for(int j=6*i;j>=i;j--){ //i个筛子能得到点数��[i，6*i]
                int count=6; 
                counts[j]=0;  //去除脏数据 counts[j]代表i个筛子能得到点数和为j的次数
                while(count>0){
                    if(j-count+1>=i){
                        counts[j]+=counts[j-count]; //转移方程
                    }
                    count-=1;
                }
            }
        }
        for(int i=n;i<=6*n;i++){
            res[i-n]=counts[i]/Math.pow(6,n);
        }
        return res;
    }
}

剑指 Offer 61 扑克牌中的顺子

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
先找到最小的牌 然后向后遍历5个数 若没有 就用大小王代替 没有大小王就报错 若有则跳过
"""
class Solution {
    public boolean isStraight(int[] nums) {
        int[] count=new int[14];
        for(int i=0;i<5;i++){
            count[nums[i]]+=1;
        }
        int magic=count[0]; //大小王个数
        int i=1;
        while(count[i]==0) i+=1 //最小的牌;
        for(int idx=1;idx<5;idx++){
            if(i+idx<14&&count[i+idx]>0) continue; //当前牌与上一张连续
            else{
                if(magic>0){ //不连续 就用掉一张大小王
                    magic-=1;
                }
                else return false; //没有 就报错
            }
        }
        return true;
    }
}

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

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
模拟过程
"""
class Solution {
    public int lastRemaining(int n, int m) {
        int idx=0,len=n;
        List<Integer> nums=new ArrayList<>();
        for(int j=0;j<n;j++){ //初始化
            nums.add(j);
        }
        while(len>1){
            idx=(idx+m-1)%len;
            nums.remove(idx);
            len-=1;
        }
        return nums.get(0);
    }
}

剑指 Offer 63 股票的最大利润

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
"""
动态规划
第i天的最大利润=max(第i-1天的最大利润,第i天卖出(第i天的价格-前i-1天的最低价格)
"""
class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);  //前i-1天的最低价格
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

剑指 Offer 63-1 股票的最大利润 可买卖多次

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
爬坡两端卖出
降坡不卖
"""
class Solution {
    public int maxProfit(int[] prices) {
        int i =0, j=1;
        int minIdx = 0;
        int res = 0;
        while(j<prices.length){
            minIdx = i;
            if(prices[i]<prices[j]){
                while(j<prices.length&&prices[i]<prices[j]){
                    i++;
                    j++;
                }
                res+=prices[i] - prices[minIdx];
            }else{
                while(j<prices.length&&prices[i]>=prices[j]){
                    i++;
                    j++;
                }
            }
        }
        return res;
    }
}

剑指 Offer 64 求1+2+…+n

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
"""
利用&&实现递归判断
以逻辑运算符 && 为例，对于 A && B 这个表达式，如果 A 表达式返回 False ，那么 A && B 已经确定False ，此时不会去执行表达式 B
将判断是否为递归的出口看作 A && B 表达式中的 A 部分，递归的主体函数看作 B 部分。如果不是递归出口，则返回True，并继续执行表达式 B 的部分，否则递归结束。
"""
class Solution {
    public int sumNums(int n) {
        Boolean x=n>0&&((n+=sumNums(n-1))>0);
        return n;
    }
}

剑指 Offer 65 不用加减乘除做加法

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
"""
利用位运算实现加法
a^b 等于a与b不考虑进位的加法结果
a&b 等于a与b加法的进位结果
"""
class Solution {
    public int add(int a, int b) {
        if(b==0) return a;
        return add(a^b,(a&b)<<1);
    }
}

剑指 Offer 66 构建乘积数组

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
可以将B[i] 拆分为两部分：
    A[0]×A[1]×…×A[i-1]
    A[i+1]×…×A[n-1]
"""
class Solution {
    public int[] constructArr(int[] a) {
        int n=a.length;
        int[] B=new int[n];
        for(int i=0,product=1;i<n;product*=a[i],i++){ //A[0]×A[1]×…×A[i-1]
            B[i]=product;
        }
        for(int i=n-1,product=1;i>=0;product*=a[i],i--){ //A[i+1]×…×A[n-1]
            B[i]*=product;
        }
        return B;
    }
}

剑指 Offer 67 把字符串转换为整数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int strToInt(String str) {
        char[] s=str.toCharArray();
        int i=0,flag=1;
        long  res=0;
        if(s.length==0) return 0; //str=""
        while(i<s.length&&s[i]==' '){ //找到第一个非空字符
            i++;
        }
        if(i<s.length&&(s[i]=='-'||s[i]=='+')){ //若开头为正负
            if(s[i]=='-') flag=-1;
            i+=1;
        }
       //若只有正负（i会越界）  若第一个非空字符不为字符整数
        if(i>=s.length ||!((s[i]>='0'&&s[i]<='9')||s[i]=='-'||s[i]=='+')){
            return 0;
        }
        while(i<s.length&&s[i]>='0'&&s[i]<='9'){
            res=res*10+(s[i]-'0');
            if(res>Integer.MAX_VALUE) return flag>0?Integer.MAX_VALUE:Integer.MIN_VALUE;//中间就可以判断是否大于int最大值 不然太大long也装不下
            i++;
        }
        return flag*(int)res;
    }
}

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

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
"""
利用二叉搜索树 左<中<右这个规律
"""
"""
1、递归
"""
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null)
        return root;
    if (root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    return root;
}
"""
2、迭代
    循环搜索： 当节点 root为空时跳出；
        当 p, q都在 root 的 右子树 中，则遍历至 root.right；
        否则，当 p, q 都在 root 的 左子树 中，则遍历至 root.left；
        否则，说明找到了 最近公共祖先 ，跳出。
    返回值： 最近公共祖先 root 。

"""
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null) {
            if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                root = root.left; // 遍历至左子节点
            else break;
        }
        return root;
    }
}
"""
若为普通二叉树
"""
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root; 
        //类似于搜索  若以p或q存在于root.left为根 则left不为空 
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }
}

大数的和

1
2
3
4
5
6
7
8
9
10
11
12
public String solve(String s, String t) {
    StringBuilder stringBuilder = new StringBuilder();
    int i = s.length() - 1, j = t.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry != 0) {
        int x = i < 0 ? 0 : s.charAt(i--) - '0';
        int y = j < 0 ? 0 : t.charAt(j--) - '0';
        int sum = x + y + carry;
        stringBuilder.append(sum % 10);//添加到字符串尾部
        carry = sum / 10;
    }
    return stringBuilder.reverse().toString();//对字符串反转
}

42接雨水


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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;
    }
}
"""
对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去height[i]。

如果 height[left]<height[right]，则必有 leftMax<rightMax，下标left 处能接的雨水量等于 leftMax−height[left]，将下标left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）；

"""
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 (leftMax < rightMax) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
}