数组中重复的数

题目：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/submissions/

首先肯定不能暴力（不想动脑，结果直接死了），直接超时，相对简单点是先排序，然后检查前后两个数是否相同。

方法1：排序+遍历判断

1
2
3
4
5
6
7
8
9
class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i=1;i<nums.length;i++)
           if(nums[i-1]==nums[i])
               return nums[i];
        return -1;
    }
}

方法2：利用Set无重复特性

1
2
3
4
5
6
7
8
class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums)
            if(!set.add(num)) return num;
        return -1;
    }
}

方法3：原地交换，书上的解法，可以说是最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findRepeatNumber(int[] nums) {
        int i=0;
        while(i<nums.length){
            if(nums[i]==i){
                i++;
                continue;
            }
            if(nums[i]==nums[nums[i]]) return nums[i];
            nums[i] ^= nums[nums[i]];
            nums[nums[i]] ^= nums[i];
            nums[i] ^= nums[nums[i]];
        }
        return -1;
    }
}

二维数组中的查找

题目：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

暴力不考虑啊，看了下书上提示就懂了大概方法，但一些特殊输入就没考虑到，故报错了好几次。本题从右上角和左下角开始查找都是OK的，因为有一大一小的两个相邻值可以判断位置，缩小查找范围。而使用左上或右下，则会全大或全小，查找不会缩小范围，无法解决问题。

方法1：右上角开始查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length==0) return false;
        //选用右上角开始，但是从左下角开始更好，右上角开始则要对数组判断是否空
        //因为当输入空数组时，matrix[0]不存在，故m初始化会报错
        int n=0,m=matrix[0].length-1;
        while(n<matrix.length && m>=0){
            if(matrix[n][m] > target) m--;
            else if(matrix[n][m] < target) n++;
            else return true;
        }
        return false;
    }
}

方法2：左下角开始查找

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int n=matrix.length-1,m=0;
        while(n>=0 && m<matrix[0].length){
            if(matrix[n][m] == target) return true;
            if(matrix[n][m] > target) n--;
            else if(matrix[n][m] < target) m++;
            else return true;
        }
        return false;
    }
}

替换空格

题目：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

比较简单啊，我们遍历一遍String转化后的数组，每次遇到字符=’ ‘就往StringBuilder添加”%20”并跳出，其他情况直接添加字符。最后转String输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(char c : s.toCharArray()){
            if(c == ' ') {
                sb.append("%20");
                continue;
            }
            sb.append(c);
        }
        return sb.toString();
    }
}

从尾到头打印链表

题目：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

这里用栈就很好想，先进后出吗，先压入栈，在打印栈就是倒叙输出了，用数组也一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> s = new Stack<Integer>();
        //链表不为空时操作
        while(head!=null){
            s.push(head.val);
            head=head.next;
        }
        int[] arr = new int[s.size()]; 
        for(int i=0;i<arr.length;i++)
            arr[i] = s.pop();
        return arr;
    }
}

重建二叉树

题目：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

前序和中序结合推树很好想，但递归不好写，注意右子树的根结点位置是怎么生成的。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] preorder;//res也要用，就定义一下
    Map<Integer,Integer> map =new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        //中序遍历存入哈希表，这里将中序的数存入键，其位置存入值，这是为了方便后续使用
        for(int i=0;i<inorder.length;i++) map.put(inorder[i],i);
        //第一次自行输入根节点位置，然后递归得到结果
        return res(0,0,inorder.length-1);
    }
    
    //root即当前根节点在前序的位置，left、righ结点在中序中的最左和最右，区分左右子树
    TreeNode res(int root,int left,int right){
        //越界无子结点
        if(left>right) return null;
        TreeNode node = new TreeNode(preorder[root]);
        //根节点在中序遍历中的位置，根据键返回值，所以前面键要存中序的数而不是位置
        int i = map.get(preorder[root]);
        /*
         *写出左孩子的根节点和其左右子树边界
         *根节点在前序中的位置是root+1，其左边界还是中序的左边界
         *而右边界是中序根节点的左边第一个，因为中序从其根节点处判断左为左子树，右为右子树
         */
        node.left = res(root+1,left,i-1);
        //前序根节点+左子树长度后的后一位，因为在前序遍历后按根节点|左子树|右子树来排序
        node.right = res(root + i-left + 1,i+1,right);
        return node;
    }
}

用两个栈实现队列

题目：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

A栈主栈，B栈辅助栈，入队时直接压入A栈，出队时A出B入，由于两次先进后出，此时B出栈便会实现元素先进先出。

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 CQueue {
    Stack<Integer> a,b;
    public CQueue() {
        //一个主栈a，一个辅助栈b，实现队列
        a = new Stack<Integer>();
        b = new Stack<Integer>();
    }
    
    public void appendTail(int value) {
        a.push(value);
    }
    
    //队首出队
    public int deleteHead() {
        //因为先进先出，若辅助栈b已有上次的数据，先把这些数据出队
        if(!b.empty()) return b.pop();
        //a栈无数据
        if(a.empty()) return -1;
        //经过前两个验证，b栈空，a栈有数据，则将a出栈，后b入栈
        while(!a.empty())
            b.push(a.pop());
        //使用辅助栈，两个栈的先进后出转变为队列的先进先出
        return b.pop();
    }
}

斐波那契数列

题目：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/、

递归从上到下，会多次重复计算，效率低。

这里使用循环，每次将fn=f0+f1，并更新f0和f1，注意int上限是2^31，一般运算会越界，所以使用取余计算fn=(f0+f1)%1000000007

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        int f0=0,f1=1,fn=0;
        for(int i=2;i<=n;i++){
            fn=(f0+f1)%1000000007;
            f0 = f1;
            f1=fn;
        }
        return fn;
    }
}

青蛙跳台（斐波那契变种）

题目：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

这题首先要通过题目联想到跳上第n层只有上1/2层两种方法，推出f(n)=f(n-1)+f(n-2)，然后得到f(2)=f(1)+f(0)并结合事实推出f(0)=1，这里便是和斐波那契最大的区别，其他的就一样了，当然不能使用递归，毕竟重复计算太多了会超时，使用循环O(n)遍历即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int numWays(int n) {
        /**
         *和斐波那契数列有细微不同，跳台问题f(0)=1,斐波那契f(0)=0
         *因为跳台倒退跳上第n层有两种方法，跳1或跳2，即f(n)=f(n-1)+f(n-2)
         *所以有f(2)=f(1)+f(0)，而跳上两层和跳上一层分别是2、1，这是结合事实的推断
         *所以f(0)只能是2-1=1，尽管它不太对逻辑，其他的都和斐波那契一样
         */
        if(n==0||n==1) return 1;
        int f0=1,f1=1,fn=0;
        for(int i=2;i<=n;i++){
            fn = (f0 + f1)%1000000007;
            f0 = f1;
            f1 = fn;
        }
        return fn;
    }
}

旋转数组的最小数字

题目：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

遍历就不说了啊，这题目考的就是二分找旋转点，注释写的比较清除，还要注意，mid=j不能判断左右递增，因为[0,1,1,1,1,1]这种全是重复值的数组存在。还有为什么mid与j比较，而不是与i比较，因为有[1,2,3,4,5]这种数组，只有右递增，旋转点是num[0]，这个问题要考虑清楚。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minArray(int[] numbers) {
        int i=0,j=numbers.length-1;
        //i<j时二分查找
        while(i<j){
            /*
             *旋转数组会分割成左递增和右递增，实质是找旋转点
             *其中左递增是原本数组的后部部分，旋转到前面来的，故左递增>右递增
             */
            int mid = (i+j)/2;
            //mid>j，则mid一定位于左递增，旋转点位于右递增，左递增全舍弃故+1
            if(numbers[mid]>numbers[j]) i = mid+1;          
            //mid<j，mid一定位于右递增，而右递增包含旋转点，故不舍弃 
            else if(numbers[mid]<numbers[j]) j = mid;
            /*
             *最后剩下的情况只有mid=j，而这种情况是无法确认mid在左还是右的
             *具体论证可看力扣评论区或剑指Offer，主要是因为可以有重复元素导致的
             */
            else j--;
        }
        return numbers[i];
    }
}

矩阵中的路径

题目：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

这题的思想好想，但写起来就不容易了，且要注意细节，就是回溯的时候要把改变的空字符重置回初值，这是回溯法的关键，我理解是当前错误的路径上标记过的值（空字符）全作废，因为这条路是错的，一直回到正确的岔路口来走另一条路。感觉这题没有吃透。。。

评论区看到的分析：一个比较难理解的点，递归搜索匹配字符串过程中，需要 board[i] [j] = ‘0/‘ 来防止 ”走回头路“ 。当匹配字符串不成功时，会回溯返回，此时需要board[i] [j] = word[k] 来”取消对此单元格的标记”。 在DFS过程中，每个单元格会多次被访问的， board[i] [j] = ‘0/‘只是要保证在当前匹配方案中不要走回头路，不复原，在下一个匹配方案中会影响最终结果。

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
class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i=0;i<board.length;i++)
            for(int j=0;j<board[0].length;j++)
                //先遍历查找匹配第一个字符的元素
                if(dfs(board,words,i,j,0)) return true;            
        return false;
    }
    boolean dfs(char[][] board,char[] words,int i,int j,int k){
        //矩阵索引越界，或当前访问的矩阵元素和目标不符
        if(i>=board.length || i<0 || j>=board[0].length || j<0 || board[i][j]!=words[k]) return false;
        //成功访问到字符串最后一个字符且和最后一个也相等，说明匹配存在（第一个if可检验相等）
        if(k==words.length-1) return true;
        //若经过前两个if，说明字符串匹配仍在进行，为了不重复访问，将这次符合的矩阵元素变为空字符
        board[i][j] = '\0';
        //判断其上下左右是否有符合下一个字符的元素，这里有就会一直递归，直到退出
        boolean res = dfs(board,words,i+1,j,k+1) || dfs(board,words,i-1,j,k+1) || dfs(board,words,i,j+1,k+1) || dfs(board,words,i,j-1,k+1);
    /*
	 *这里是关键，只有当前递归终止时会来到这一步，如果结果是false也就是没有匹配的字符串，会一步步
     *回溯到之前匹配的情况，并判断当时是否还有其他路径，也就是说，现在的路径不正确，那刚刚走过的路
     *相当于没有用，我们需要回到初始状态。但可能之后走的另一条路径会经过曾经匹配的元素，如果我们没
     *有回溯则让会未经过的点变成空字符，这肯定是有问题的。而对返回结果true没啥影响。
     */
        board[i][j] = words[k];
        return res;
    }
}

注意其实回溯是针对错误路径的，对正确路径无影响，但为了方便，我们就不分情况回溯了。将代码中加上判断条件只在错误时回溯，发现结果仍然是对的，这也验证了我的想法。

1
2
//可以，但没必要
if(res == false) board[i][j] = words[k];

机器人的运动范围

题目：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

深度优先遍历，每走一个新方格便记录该方格的数位和，并与判断条件比较，直到走到头往回退，给出结果。注意dfs返回值是其右和下的遍历情况+1，因为直接这一格可以走到，所以+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
//只通过向右和向下就能查找到所有的可行的方格，向上和向左一般都遇到重复的
class Solution {
    //变量提升作用域，visited是记录访问情况的辅助数组
    int m,n,k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m; this.n = n; this.k = k;
        this.visited = new boolean[m][n];
        //矩阵起始点
        return dfs(0,0,0,0);
    }
    
    //计算当前方格（行/列）坐标的数位和
    public int sum(int x){
        int sum = 0;
        while(x != 0){
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
    /*
     *注意是m行n列，所以m-1、n-1就是上限了，所以i、j>=m、n时结束查询
     *每次访问过的方格都会visited标记为true，下次再来到这个方格直接结束
     *k的判断要是和m、n一样，由于到m、n会结束，相对的数位和就是sum(m)、sum(n)
     *k是一定要小于sum(m)+sum(n)的，因为是先计算值后判断是否符合情况
     */
    public int dfs(int i, int j, int sumi, int sumj){
        if(i >= m || j >= n || k < sumi + sumj || visited[i][j])
            return 0;
        visited[i][j] = true;
        //1即当前方格本身 + dfs（i+1）是右边方格的全部结果 + dfs（j+1）即下方方格全部结果
        return 1 + dfs(i + 1, j, sum(i + 1), sumj) + dfs(i, j + 1, sumi, sum(j + 1));
    } 
}

剪绳子（n<=58，不考虑大数据）

题目：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

最优子段的推导：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by/

这里使用贪心算法是最优解，而找出最优字段是关键，就是每个>5的数均可继续分割成2&3，2、3的搭配才是最小最优的乘积（整个具体分析得看大佬，例如5<2*3等等），而2&3的优先级怎么判断呢？

1
2
3
6=2+2+2=3+3，f(6)=2*2*2<3*3
所以3的优先级大于2
故我们使用3来作为倍数，剩下的分析看注释即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int cuttingRope(int n) {
        //最优解是分割成2、3，但绳子最少切一段，所以n=2、3时特殊讨论
        if(n<=3) return n-1;
        int i = n/3;
        /*
         *Math.pow即3^i，幂运算
         *因为分割成3的子段是最优解，所以/3算倍数与余数，余数只有0，1，2三种情况
         *余数=0时，说明被3整除可全部被分割成3的小段，f(n)=3^n
         *余数=1时，f(n)=3^n*1，但1+3=4，4可以分割成2+2，显然2+2更优，故优化f(n)=3^(n-1)*4
         *余数=2时，f(n)=3^n*2，2是最优子段直接返回即可
         *又因为只有这三种讨论，可直接把返回值设为余数为2的情况
         */
        if(n%3 == 0) return (int)Math.pow(3,i);
        if(n%3 == 1) return (int)Math.pow(3,i-1)*4;
        return (int)Math.pow(3,i)*2;
    }
}

剪绳子（大数据情况，考虑越界）

题目：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

注意要逐位取余，不然连乘中途可能已经越界了，所以老办法不行，同一个思路要换一个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int cuttingRope(int n) {
        //最优解是分割成2、3，但绳子最少切一段，所以n=2、3时特殊讨论
        if(n<=3) return n-1;
        int i = n/3;
        /*
         *Math.pow即3^i，幂运算
         *因为分割成3的子段是最优解，所以/3算倍数与余数，余数只有0，1，2三种情况
         *余数=0时，说明被3整除可全部被分割成3的小段，f(n)=3^n
         *余数=1时，f(n)=3^n*1，但1+3=4，4可以分割成2+2，显然2+2更优，故优化f(n)=3^(n-1)*4
         *余数=2时，f(n)=3^n*2，2是最优子段直接返回即可
         *又因为只有这三种讨论，可直接把返回值设为余数为2的情况
         */
        if(n%3 == 0) return (int)Math.pow(3,i);
        if(n%3 == 1) return (int)Math.pow(3,i-1)*4;
        return (int)Math.pow(3,i)*2;
    }
}

二进制中1的个数

题目：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/

1
2
3
4
5
6
7
8
">>>"无符号右移
操作规则：无论正负数，前面补零。

">>"右移
操作规则：正数前面补零，负数前面补1

"<<"左移
操作规则：无论正负数，后面补零。

末位按位与1 + 逐位右移：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int hammingWeight(int n) {
        int res=0;
        /* 
         * n&1直接+即可，可以省去if判断，因为n&1为T=1，F=0，等价了
         * java要使用无符号右移，也就是>>>
         * 因为负数右移左补1，然后会无限循环1，出不来了
         */
        while(n!=0){
            res += n&1;
            n = n>>>1;
        }
        return res;
    }
}

新思路：

  • 数-1：即二进制最右的1变为0，该位后面的0全变为1
  • 将-1的数&原数：可得到只有最右的1变为0的数，其余不变
  • 重复该操作，直到全部变为0
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int hammingWeight(int n) {
        int res=0;
        while(n!=0){
            res++;
            n = n & (n-1);
        }
        return res;
    }
}

数值的整数次方

题目：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

参考：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/jian-zhi-offer-16-shu-zhi-de-zheng-shu-c-rgqy/

可类比斐波那契数列，均有递归关系，一般只在偶数情况下递归，奇数情况则提一个a，转变次数为偶数

1
2
3
4
5
6
7
8
偶数情况
    a^n = a^(n/2) * a^(n/2)
    a^n = a^[2*(n/2)]
    a^n = (a^2)^(n/2) (效率更高，递归得用这个，不然超时)
奇数情况
    a^n = a^[(n-1)/2] * a^[(n-1)/2] * a
    a^n = a * a^(2*[(n-1)/2])
    a^n = a * (a^2)^[(n-1)/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
/*
 * int32位，第一位符号位，所以正数最大是0+31个1，即2^31-1
 * 负数最小是-0，也就是规定的1+31个0，规定为-2^31 
 * 所以迭代要转换负数要将int提升到long，不然-2^31反转后会越界
 */
class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long m = n;
        double res = 1.0;
        if(m<0){
            x = 1/x;
            m = -m;
        }
        while(m>0){
           /*
            * 现在已经转换为正数了，以二进制来思考，1101即x^8 * x^4 * x^1
            * 我们会与1做按位与，查看当前位是否为1，若为1则将res * 当前位的对应数值
            * 这个数值就是上述例子的x^8、x^4这样，即每次右移都会把下一位和1比较
            * 而当前位的数值是逐渐叠加的，所以每次 x自乘 也就是在计算相应位置的数值
            */
            if((m&1) == 1) res *= x;//比较当前二进制位数是否存在，存在就乘以对应位置的数值
            x *= x;//每一位的数值都在叠加，从1位开始
            m >>= 1;//右移，比较下一位
        }
        return res;
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        if(n==0){
            return 1;//0次方返回1
        }else if(n<0){
            //转换负数，这里为了防止转换越界，取了一个x出来
            return 1/(x * myPow(x,-n-1));
        }else if((n&1) == 1){
            //若为奇数，提一个x，将次数转换为偶数
             return x * myPow(x,n-1);
        }else{
            /*
             * a^n = a^(n/2) * a^(n/2)
             * a^n = a^[2*(n/2)]
             * a^n = (a^2)^(n/2) 
             * 这里要多转换一步
             * 如果是myPow(x,n/2)*myPow(x,n/2)则超时，因为多了一次递归
             */
            return myPow(x*x,n/2);
        }
    }
}

打印从1到最大的n位数（大数情况得重新看）

难，大数情况不好想

题目：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/

参考：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/

int不越界

1
2
3
4
5
6
7
8
9
class Solution {
    public int[] printNumbers(int n) {
        int end = (int)Math.pow(10,n)-1;
        int[] res = new int[end];
        for(int i=1;i<=end;i++)
            res[i-1]=i;
        return res;
    }
}

大数情况！！！

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
class Solution {
    int[] res;
    int nine=0,count=0,start,n;
    char[] num,loop={'0','1','2','3','4','5','6','7','8','9'};
    public int[] printNumbers(int n) {
        this.n = n;
        res = new int[(int)Math.pow(10,n)-1];//返回结果上限(10^n)-1
        num = new char[n];//每一个数的长度
        start = n-1;//字符串左边界，左边0的个数
        dfs(0);//全排列
        return  res;
    }
    void dfs(int x){
        //符合当前位数，返回当前的数
        if(x==n){
            String s = String.valueOf(num).substring(start);//截取子串，舍去前面的0
            //不为0，添加进结果，逗号隔开。因为有10，所以必须考虑0，但0、00、000就不要了
            if(!s.equals("0")) res[count++] = Integer.parseInt(s);
            if(n-start == nine) start--;//进位了，更新左起0的个数
            return;
        }
        for(char i : loop){
            if(i == '9') nine++;//9的数量
            num[x] = i;
            dfs(x+1);
        }
        nine--;//开始一次新的计算，9计数倒退一层
    }
}

删除链表的节点

题目：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/

就是删除链表的节点，注意头结点为空的特殊情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head == null) return null;
        if(head.val == val) return head.next;//val相等，跳过当前结点
        ListNode pre = head, cur = head.next;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;//val相等，跳过cur，并退出循环
                break;
            }
            pre = cur;
            cur = cur.next;
        }
        return head;
    }
}

正则表达式匹配(难！)

题目：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

参考：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/jian-zhi-offer-19-zheng-ze-biao-da-shi-pi-pei-dong/

  • 初始化时，要给两个字符串添加一个首空字符
  • 正则表达式判断，匹配串当前字符是’ * ‘时
    • ‘ * ‘修饰字符重复0次情况
    • ‘ * ‘ 与上一个主串字符匹配，看当前主串字符是否仍能与 ‘ * ‘修饰字符匹配，即重复一次’ * ‘修饰字符
    • ‘ * ‘ 与上一个主串字符匹配，但’ * ‘修饰’ . ‘，主串当前字符一定匹配
  • 正则表达式判断，匹配串当前字符不是’ * ‘时，且前部分主串与匹配串相匹配
    • 当前主串与匹配串字符相等
    • 当前匹配串字符是’ . ‘，一定匹配
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
//我们现在s串为主串，p串为匹配串
class Solution {
    public boolean isMatch(String s, String p) { 
        /* 初始化布尔数组，默认值为false，所以我们只需要标出true即可
         * 本来矩阵长度等于字符串的长度，但为了方便操作，在每一个字符串前引进了一个空字符
         * 因为两个空字符串本身是匹配的，会带来一个true，方便后续判断
         */ 
        int m = s.length()+1,n = p.length()+1;
        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;

        /* dp[i][0]、[0][j]一般都是默认值false，而dp[i][0]则会有特殊情况
         * 就是两个字符串以空值匹配的特殊情况，此处s串确定为空，p串是有*的特殊情况
         * 只有*修饰的字符才会因为重复0次变成空字符，因为*都是和一个字符配套使用的
         * 所以只有偶数串，且每一个字符都有*修饰时才会和空串匹配，而*必处于偶数位
         * 而奇数串必有无*修饰的字符，肯定不会是空字符串
         */
        for(int j=2;j<n;j += 2)
            dp[0][j] = dp[0][j-2] && p.charAt(j-1) == '*';

        // 行列第0位的初始化及特殊情况均已讨论完，现在讨论字符串本身
        // [j] = (j-1)，一个是处于矩阵中的位置，一个是处于字符串本身的位置
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                // 当前p串来匹配的字符是*
                if(p.charAt(j-1) == '*'){
                    // 情况1：*修饰的字符重复0次，即当前字符和*都被跳过后字符串能否匹配
                    // [j-2]其实是p.charAt(j-3)，当前*是p.charAt(j-1)，所以是前2位
                    if(dp[i][j-2]) dp[i][j] = true;
                    
                    // 情况2：若s串上一个字符和*匹配成功，则判断s串当前字符和*修饰的字符是否匹配
                    // 也就是说延续上一个字符与*的匹配，即*修饰的字符再出现一次，看能否匹配
                    else if(dp[i-1][j] && s.charAt(i-1) == p.charAt(j-2)) 
                        dp[i][j] = true;
                    
                    // 情况3：这是2的特殊情况，*修饰的字符是'.'，所以当前字符在此情况下一定匹配
                    else if(dp[i-1][j] && p.charAt(j-2) == '.') 
                        dp[i][j] = true;
                } 
                // p串当前匹配字符不是*
                else{
                    //s、p串前面每一位都匹配，且当前字符s、p串也匹配
                    if(dp[i-1][j-1] && s.charAt(i-1) == p.charAt(j-1)) 
                        dp[i][j] = true;
                    //s、p串前面字符均匹配，而p串当前字符为'.'，这是特殊情况一定匹配
                    else if(dp[i-1][j-1] && p.charAt(j-1) == '.') 
                        dp[i][j] = true; 
                }
            }
        }
        //矩阵长度m、n，0~m-1，0~n-1。m-1、n-1就是最后一位
        return dp[m-1][n-1];
    }
}

表示数值的字符串（优化了不用状态机的作法）

题目：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/

参考：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/solution/mian-shi-ti-20-biao-shi-shu-zhi-de-zi-fu-chuan-y-2/

k神的解法太妙了，看懂后就觉得理解起来很容易，用Map数组规定8种状态，然后从初值0开始，依当前情况进入对应的状态。

3.png

8种状态的个人理解我也写在注解里了，原谅我是个菜鸡，看半天才看懂，还没法举一反三😭

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
//小数表示可省去0，-0.4 = -.4，0.4 = .4；2.、3. = 2、3，小数点前有数，后面可以不跟数代表原数
//注意e8即10的8次幂（8次方），也可以是e-7，但题目要求必须跟整数
//题目规定是数值前后可有空格，中间不能有，这个情况要考虑清楚。s：符号、d：数字
class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            //0：规定0是初值，字符串表示数值，有4种起始状态，开头空格、符号、数字、前面没有数的小数点
            //其中 开头空格 还是指向states[0]，上一位是 开头空格，下一位可以是 空格、符号、数字、前面没有数的小数点
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, 
            //1：上一位是符号，符号位后面可以是 数字、前面没有数的小数点
            new HashMap<>() {{ put('d', 2); put('.', 4); }},
            //2：上一位是数字，数字的下一位可以是 数字、前面有数的小数点、e、结尾空格
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, 
            //3：上一位是前面有数的小数点，下一位可以是 数字、e（8.e2 = 8e2，和2的情况一样）、结尾空格
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},
            //4：上一位是前面没有数的小数点，下一位只能是 数字（符号肯定不行，e得前面有数才行）
            new HashMap<>() {{ put('d', 3); }},
            //5：上一位是e，下一位可以是 符号、数字
            new HashMap<>() {{ put('s', 6); put('d', 7); }},
            //6：：上一位是e后面的符号，下一位只能是 数字
            new HashMap<>() {{ put('d', 7); }},
            //7：上一位是e后面的数字，下一位可以是 数字、结尾空格
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},
            //8：上一位是结尾空格，下一位只能是 结尾空格
            new HashMap<>() {{ put(' ', 8); }}
        };
        int p = 0;
        char t;
        //遍历字符串，每个字符匹配对应属性并用t标记，非法字符标记？
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else if(c == 'e' || c == 'E') t = 'e';
            else if(c == '.' || c == ' ') t = c;
            else t = '?';
            //当前字符标记和任何一种当前规定格式都不匹配，直接返回false
            if(!states[p].containsKey(t)) return false;
            //更新当前字符的规定格式，进入下一个规定的Map数组
            p = (int)states[p].get(t);
        }
        //2（正、负整数）、3（正、负小数）、7（科学计数法）、8（前三种形式的结尾加上空格）
        //只有这四种才是正确的结尾
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

2021.12.24 二刷剑指，yysy状态机一般人写不出来，只能背，然后发现剑指官方没有使用状态机，而且状态机也不是时间复杂度最优解，看了看评论区发现了简易写法，简单易懂good！

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
class Solution {
    public boolean isNumber(String s) {
        if (s.length() == 0) return false;
        
        s = s.trim();
        boolean numFlag = false; //数字
        boolean dotFlag = false; //小数点
        boolean eFlag = false;   //e 
        for (int i = 0; i < s.length(); i++) {
            //判定为数字，则标记numFlag
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') numFlag = true;

            //判定为'.'需要没出现过'.'并且没出现过'e'
            else if (s.charAt(i) == '.' && !dotFlag && !eFlag) dotFlag = true;

            //判定为'e'，需要没出现过'e'，并且出过数字了，小数点无影响
            else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eFlag && numFlag){
                eFlag = true;
                //为了避免12e这种情况，e后面必须跟数字，出现e之后就数字标识为false
                numFlag = false;
            }

            //判定为+-符号，只能出现在第一位或者紧接e后面，标识一种符合情况，以免+-直接false
            //多次+-不满足的情况自然会走最后的false，所以方法体不需要内容
            else if ((s.charAt(i) == '+' || s.charAt(i) == '-') && (i == 0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {}

            //其他情况，都是非法的
            //如多个小数点，e后小数点，这些都在if判断中规避了
            else return false;
        }
        // 最后结果一定要有数字输出，数字位即答案
        // 主要注意e后面必须跟数字，所以判断有e后要把数字位重置
        return numFlag;
    }
}

调整数组顺序是奇数位于偶数前

题目：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/

采用左右双指针，前提left小于right，left循环匹到偶数停止，然后right循环匹配到奇数停止，随后二者交换数值，多次循环后最后完成奇数排列于偶数前，但没有顺序。

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 int[] exchange(int[] nums) {
        int left = 0,right = nums.length-1;
        while(left < right){
            //循环与1按位与，判断奇偶，直到出现偶数
            while(left<right && (nums[left] & 1) == 1){
                left++;   
            }
            //循环判断奇偶，直到出现奇数
            while(left<right && (nums[right] & 1) == 0){
                right--;
            }
            //异或交换数据
            if(left<right){
                nums[left] = nums[left] ^ nums[right];
                nums[right] = nums[left] ^ nums[right];
                nums[left] = nums[left] ^ nums[right];
            }
        } 
        return nums;
    }
}

链表中倒数第k个节点

题目：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

左右指针遍历一次链表即可，先右指针空出k个位置给倒数节点，随后左右同时前进直到越界，因为遍历到表尾时，左指针在倒数节点的前一个节点，右指针在表尾节点，随后越界左指针就指向了倒数节点。注意空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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 //左右（前后）两指针遍历链表一次即可
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode left=head,right=head;
        //右指针先跑k个位置，这样左右指针就空出了倒数节点的空间
        for(int i=0;i<k;i++){
            //右指针越界说明链表不符合题意
            if(right == null) return null;
            right = right.next;
        }
        //左右指针同时前进，右指针越界时退出，此时右指针刚刚越界，
        //而左指针刚好在倒数指针第k个节点
        while(right != null){
            left = left.next;
            right = right.next;
        }
        return left;
    }
}

反转链表

题目：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

双指针，前缀指针pre、当前指针cur，next用来保存预更新值，首先保存下一结点的值给next，然后反转cur指向，最后更新pre、cur直到cur指向null，此时pre便是原表尾结点，返回pre即反转链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 //双指针，先把当前结点的后一位保存。然后将该结点指向前一位，最后在更新当前结点和前缀结点
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null,cur = head,next = null;
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //当当前结点为空时，前缀结点走到表尾结点，并且所有的指向已经反转，直接返回前缀结点
        return pre;
    }
}

合并两个排序的链表

题目：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

最近都在搞期末，没怎么写题，今天看题很简单，简单写完就发现是局域烂代码，太啰嗦了。。。感觉没啥进步。还是对着题解改进一下，md思路都一样别人的简洁很多。。。主要是最后的一个链表为空时，另一个链表直接连接的写法，我这很啰嗦，题解就很简明。

烂代码

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur = null,head = null;
        if(l1 == null && l2 == null) return null;
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val <= l2.val){
                head = l1;
                cur = head;  
                l1 = l1.next;
            }else {
                head = l2;
                cur = head;
                l2 = l2.next;
            }    
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            }else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        if(l1 == null){
            while(l2 != null){
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }else {
            while(l1 != null){
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            }
        }
        return head;
    }
}

改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //初始化头指针，使用光标连接链表，最后返回head.next，即舍去头指针
        //注意头指针需一个初值，不能空指针，否则循环一开始便会空指针异常，反正最后头指针会舍弃
        ListNode head = new ListNode(0),cur = head;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        //当一个链表为空时，使用一句话就能直接连接另一个链表
        cur.next = l1 != null ? l1 : l2;
        return head.next;
    }
}

树的子结构

题目：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

需要多写一个子树判断，也就是当前结点判断函数。我们先在a树中查找符合b子树根结点的点，查找到后再执行左右子树的判断。注意子树中b树为空说明子树查找完毕，a中有b子树，而b未空，a先空时说明查找失败，毕竟a已经无法继续了。这题相对于前序遍历，先判断当前结点是否有子树，然后看其左右结点是否有子树。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode a, TreeNode b) {
        //空树不是任意一个树的子结构
        if(a == null || b == null) return false;
        //当前根结点匹配，且左右子树均匹配，返回true
        if(a.val == b.val && ( cur(a.left,b.left) && cur(a.right,b.right) )) return true;
        //递归，更新a的当前匹配根结点，分别走左右子树
        return isSubStructure(a.left,b) || isSubStructure(a.right,b);
    }
    //判断当前a为根结点的子树是否包含b
    boolean cur(TreeNode a,TreeNode b){
        //b树匹配完了，说明成功匹配
        if(b == null) return true;
        //而b树没匹配完，a树却走完了，没有结点可以匹配，返回false
        if(a == null) return false;
        //当前结点相匹配在，则继续匹配左右子树，不匹配返回false
        if(a.val == b.val)
            return cur(a.left,b.left) && cur(a.right,b.right);
        else return false;
    } 
}

题解改进版，超精简

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isSubStructure(TreeNode a, TreeNode b) {
        return (a != null && b != null) && (cur(a,b) || isSubStructure(a.left,b) || isSubStructure(a.right,b));
    }
    //判断当前a为根结点的子树是否包含b
    boolean cur(TreeNode a,TreeNode b){
        if(b == null) return true;
        if(a == null || a.val != b.val) return false;
        //能返回递归，说明没有当前a，b没有走完，且当前a，b结构符合，然后同时返回左右子树
        return cur(a.left,b.left) && cur(a.right,b.right);
    } 
}

二叉树的镜像

题目：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/

说实话，简单题思路很容易想到，但就是写完有点啰嗦，大佬的解法是真简洁。

简单的前序遍历

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode temp = null;
    public TreeNode mirrorTree(TreeNode root) {
        preorder(root);
        return root;
    }
    public void preorder(TreeNode root){
        if(root == null || (root.left == null && root.right == null) ) return;
        // 不能这样判断，虽然写法一样，但这种写法单子树的另一半空结点不会打印
        // if(root.left != null && root.right != null){
        //     temp = root.left;
        //     root.left = root.right;
        //     root.right = temp;
        // }
        temp = root.left;
        root.left = root.right;
        root.right = temp;
        preorder(root.left);  
        preorder(root.right);
    }
}

大佬简洁易懂写法

1
2
3
4
5
6
7
8
9
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return root;
        TreeNode temp = root.right;
        root.right = mirrorTree(root.left);
        root.left = mirrorTree(temp);
        return root;
    }
}

对称二叉树

题目：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/

思路很简单，就是想不出来，我一开始做了一个镜像树与原树比较，属实笨比。然后看了下书发现想复杂了，直接树的左右结点对称比较即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
       return mirror(root,root);
    }
    boolean mirror(TreeNode root1,TreeNode root2){
        if(root1 == null && root2 == null) return true;
        if(root1 == null || root2 == null) return false;
        if(root1.val != root2.val) return false;
        return mirror(root1.left,root2.right) && mirror(root1.right,root2.left);
    }
}

顺时针打印矩阵

题目：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/

很好想，但我自己写的时候对边界的判断很模糊，没有进行明确规定，写着写着就卡住了。看了下题解发现思路很清晰，特别是每次判断的时候使用 ++i 的格式，使得if语句很简洁，而且还更新了边界，所以下个循环的开始结点就更新好了，我一开始就是不知道怎么写这个结点更新导致卡壳了。

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 int[] spiralOrder(int[][] matrix) {
        //注意矩阵为空，直接返回0
        if(matrix.length == 0) return new int[0];
        //初始化上下左右四个边界，以及数组计数
        int t=0,b=matrix.length-1,l=0,r=matrix[0].length-1,num=0;
        int[] ans = new int[(b+1) * (r+1)];
        
        //我们要注意退出循环的条件，即l>r，t>b按情况变形
        //++t、--r很重要即进行了条件判断，而且还更新了边界方便后续操作
        while(true){
            //上边界从左到右
            for(int i=l;i<=r;i++) ans[num++] = matrix[t][i];
            //更新上边界并判断是否打印完
            if(++t > b) break;
            //右边界从上到下
            for(int i=t;i<=b;i++) ans[num++] = matrix[i][r];
            //更新右边界更新并判断
            if(--r < l) break;
            //下边界从右到左
            for(int i=r;i>=l;i--) ans[num++] = matrix[b][i];
            //更新下边界并判断
            if(--b < t) break;
            //左边界从下到上
            for(int i=b;i>=t;i--) ans[num++] = matrix[i][l];
            //更新左边界并判断
            if(++l > r) break;
        }
        return ans;
    }
}

包含min函数的栈

题目：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

使用辅助栈存储最小值即可，其他和普通栈无区别，注意出栈时栈顶元素匹配用equals，因为这里是两个栈顶元素在比较，也就是是对象在比较。

  • ==
    • 基本数据类型，比较值
    • 引用数据类型（对象、数组），比较内存地址

所以这里肯定不能用==。

  • equals
    • 不可用于基本数据类型的判断
    • 当前类没有覆盖equals()方法，则使用equals()会相对于使用==，即比较两个对象的内存地址
    • 若当前类覆盖equals()方法，则按照覆盖的方法来判断，如String的方法就是直接判断值（Integer、String、Date、File这四个覆写了）

所以我们使用equals()，因为这里是Integer包装类是覆盖过的equals()，可以比较值。

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
class MinStack {
    Stack<Integer> a,b;
    /** initialize your data structure here. */
    public MinStack() {
        a = new Stack<Integer>();
        b = new Stack<Integer>();
    }
    
    public void push(int x) {
        a.push(x);
        if(b.empty() || b.peek() >= x) b.push(x);
    }
    
    public void pop() {
        if( a.peek().equals(b.peek()) ) b.pop();
        a.pop();
    }
    
    public int top() {
        return a.peek();
    }
    
    public int min() {
        return b.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

栈的压入、弹出序列

题目：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/

使用辅助栈同步操作，不能完全出栈的出栈序列就是错误的，故最后返回ans.empty()判断即可。我自己写的时候还想着O(n)做出来，结果就卡壳了，看见题解双循环就懂了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> ans = new Stack<Integer>();
        int i=0;
        for(int num : pushed){
            ans.push(num);
            while(!ans.empty() && ans.peek().equals(popped[i]) ){
                ans.pop();
                i++;
            }
        }
        return ans.empty();
    } 
}

从上到下打印二叉树（层序遍历）

题目：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/

就是层序遍历，使用队列辅助，由于队列先进先出，每次循环都是把下一层的结点从左到右加入队列，然后先进先出完成层序。队列要初始化加入根结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        List<Integer> list = new ArrayList<Integer>();
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        int[] ans = new int[list.size()];
        for(int i=0;i<list.size();i++)
            ans[i] = list.get(i);
        return ans;
    }
}

从上到下打印二叉树（二）

题目：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/

我自己的做法就是普通的层序遍历，然后每层使用一个辅助队列保存当层应该打印的结点，然后打印并统计。

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 List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if(root == null) return ans;
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> exm = new ArrayList<Integer>(); 
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            while(!queue.isEmpty())
                q.add(queue.poll());
            while(!q.isEmpty()){
                TreeNode node = q.poll();
                exm.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            ans.add(exm); 
        }
        return ans;
    }
}

然后看了下k神的题解，进行了代码优化，循环里面使用初始队列长度来规定每层应该打印的次数，写法太强了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> exm = new ArrayList<Integer>(); 
			//循环初始化为当前队列的元素个数然后i--，根据这个次数来循环，避免后续加入的新元素干扰判断
            for(int i = queue.size();i > 0;i--){
                TreeNode node = queue.poll();
                exm.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            ans.add(exm); 
        }
        return ans;
    }
}

从上到下打印二叉树（三）

题目：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/

和前两天的没有大差别，无非是奇偶数层要正序/倒序打印，但组件一开始写的时候犯难了，一开始想着加入一个辅助栈，结果后续元素入队列的顺序越写越乱。看了下题解发现直接用链表控制每层要打印的数据，对应奇偶层进行正倒序排列。还是LinkedList用少了，完全没想到它自带添加首尾的方法。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if(root != null) queue.add(root);
        int j=1;//当前的层数，从1开始
        while(!queue.isEmpty()){
            LinkedList<Integer> temp = new LinkedList<Integer>();
            for(int i=queue.size();i>0;i--){
                TreeNode node = queue.poll();
                //奇数层正序，偶数层倒序
                //addLast每次都加到链表尾部，最后就是正序
                //addFirst每次加到链表头部，最后就是倒叙
                if((j & 1) == 1) temp.addLast(node.val);
                else temp.addFirst(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            j++;//层数递增
            ans.add(temp);
        }
        return ans;
    }
}

二叉搜索树的后续遍历序列

题目：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

注意二叉搜索树左小右大，查找左右子树的分割点再进行递归判断。

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 boolean verifyPostorder(int[] postorder) {
        //初始化0 ~ root(postorder.length-1)
        return recur(postorder, 0, postorder.length-1);
    }
    //根据后序遍历左右根，将postorder分割成 左0~mid-1, 右mid~root-1, 根root
    //其中mid是数组中第一个大于根结点的位置，也就是左右子树的分割位置
    boolean recur(int[] postorder,int left,int root){
        //左子树结点序号 >= 根结点序号，说明当前树结点<=1，说明后序判断成功
        if(left >= root) return true;
        //数组从左到右，第一个左子树结点初始化结点
        int cur = left;
        //遍历数组，小于根结点的都属于左子树
        while(postorder[cur] < postorder[root]) cur++;
        //退出循环，说明当前结点大于根结点，已经属于右子树的范围了
        int mid = cur;
        //继续遍历数组，但cur已经是右子树了，变更条件为大于根结点
        while(postorder[cur] > postorder[root]) cur++;
        
        //cur == root说明遍历到了最后，当前左右根无问题，可继续递归
        //递归分为左右子树 左子树在left ~ mid-1中继续判断是否符合二叉搜索树的后序
        //同理 右子树在mid ~ root-1中判断其是否符合二叉搜索树的后序
        return cur == root&&recur(postorder,left,mid-1)&&recur(postorder,mid,root-1);
    }
}

二叉树中和为某一值的路径

题目：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

我们使用先序遍历递归查找路径，保存路径值以便判断符合题目的路径。注意添加符合结果的路径需要新建一个对象，否则直接添加的path是同一个对象，后续会被覆盖。最后退出该层递归时，我们应删除当前结点，方便更新后续的路径。

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
/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<Integer>();//使用链表，方便删尾部

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        preorder(root,target);
        return ans;
    }

    //使用前序遍历，然后保存路径值判断是否符合条件
    void preorder(TreeNode root, int target){
        if(root == null) return;
        path.add(root.val);
        
        //更新当前的目标值，方便后续判断，因为使用递归，上一层的值不受影响
        target -= root.val;
        //如果当前路径值符合条件，且它是一个叶子结点
        if(target == 0 && root.left == null && root.right == null)
            //添加的当前路径到结果集中，这里注意需要新建一个对象添加
            //若一直使用path，是使用同一个对象，后续会被直接覆盖
            ans.add(new LinkedList(path));
        preorder(root.left,target);
        preorder(root.right,target);
        //当前结点递归完毕，返回上一层时要被删除，因为path存放的是一个路径，而不是树
        path.removeLast(); 
    }
}

复杂链表的复制

题目：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/

先是拼接新旧链表，然后巧妙的使用链表的指向特性给新链表的结点赋值，最后再将原链表和新链表拆分开。

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
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        //新旧链表的拼接复制，也就是在原链表每个结点后复制一个值相等的新链表结点
        while(cur != null){
            Node temp = new Node(cur.val);
            temp.next = cur.next;
            cur.next = temp;
            cur = temp.next;
        }

        cur = head;//重置光标
        //给每一个复制结点的random赋值
        while(cur != null){
            //注意例子中的7，其新链表复制结点的random不赋值，默认为null
            if(cur.random != null)
            /*
             * 复制结点的random = 原结点的random的后一位
             * 当不为空时，由于拼接复制，原结点random的后一位就是它本身
             * 而random为空时，不会走这个赋值，因为null没有复制结点
             * 且不赋值会自动初始化为null，就像例子里的7一样
             */
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        cur = head.next;//新链表
        Node ori = head, ans = head.next;//原链表和新链表的头
        while(cur.next != null){
            //两个联表都是隔一个，直接连接next.next即可
            ori.next = ori.next.next;
            cur.next = cur.next.next;
            ori = ori.next;
            cur = cur.next;
        }
        ori.next = null;//将原链表的结尾指向null
        return ans;//返回新链表的头
    }
}

二叉搜索树与双向链表

题目：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

注意是要构造双向循环链表，最后首尾指向也要更新。

然后使用中序遍历做即可，注意pre、head结点的初始化。

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 {
    Node pre,head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        inorder(root);
        //结点的前驱与后继更新成功，还要头尾相连循环
        pre.right = head;
        head.left = pre;
        return head;
    }

    void inorder(Node cur){
        if(cur == null) return ;
        inorder(cur.left);
        //前驱结点不为空时，更新其后继指向当前结点
        if(pre != null) pre.right = cur;
        //前驱结点为空，也就是第一个结点，此时应初始化头结点
        else head = cur;
        //更新当前结点的前驱结点
        cur.left = pre;
        //更新前驱结点
        pre = cur;
        inorder(cur.right);
    }
}

序列化二叉树

题目：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/

本题类似层序遍历的使用，先将二叉树转层序遍历的字符串形式，后使用层序遍历的字符串重新转变成二叉树。我们需要数以拼接时末尾的逗号应该去掉，转变二叉树时字符串的首尾是中括号，不能要。

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
 //先序列化成一个字符串，后使用字符串反序列化得到二叉树
public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder ans = new StringBuilder("[");//单线程使用StringBuilder拼接字符串
        Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};//队列初始化加入头结点
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();//出队列
            //结点不为空则拼接结点的值并让其左右孩子入队列，为空直接拼接null
            if(node != null){
                ans.append(node.val+",");
                queue.add(node.left);
                queue.add(node.right);
            }else {
                ans.append("null,");
            }
        }
        ans.deleteCharAt(ans.length() - 1);//删除末尾逗号
        ans.append("]");
        return ans.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        //字符串转字符串数组
        //0~1和length-1 ~ length是拼接字符串的[]，所以范围是1 ~ length-1
        String[] vals = data.substring(1,data.length()-1).split(",");
        //构造方法赋值，用parseInt字符串转十进制，初始化根结点
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<TreeNode>(){{ 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;
    }
}

字符串的排列（回溯法）

题目：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

其实思想就是传统的回溯，奈何之前算法了解片面，没用看相关书籍，回溯的原理似懂非懂，今天就mark一下，准备记录算法基础的了解与学习。

也就是每当我们递归前改变了”字符串”的状态，在结束当前递归后需撤销该状态改变，因为后续还要基于该层的最初基础也就是上一层的状态来改变，所以要回溯，这里仅限个人理解。

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
class Solution {
    List<String> ans = new LinkedList<String>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        // 导出为String类型数组
        return ans.toArray(new String[ans.size()]);
    }
    void dfs(int x){
        if(x == c.length-1){
            //已遍历到当前数组末位，转字符串存储
            ans.add(String.valueOf(c));
            return ;
        }
        HashSet<Character> set = new HashSet<Character>();
        for(int i=x;i < c.length;i++){
            //如果字符重复就跳过，使用set进行剪枝
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            
            //开始对字符两两换位改变字符串，并保持当前更换的状态递归
            swap(i,x);
            dfs(x+1);
            //退出递归后，将状态回溯到上一层，也就是该层递归前的状态改变要撤销
            //因为我们进行下一个循环是和现在这一层平行的，要保持该层最初状态
            swap(i,x);
        }
    }
    void swap(int a,int b){
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }
}

评论区精简版，还可剪枝优化，但比交换看起来好理解一点，递归推到最外层时继续循环，然后就把第二个先标记了，随后的递归第二个就先添加了，然后依此类推。就是在依次固定首尾，其实思想都一样，就是有个交换看起来更复杂了。所以说剑指Offer书上为什么要交换？

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 String[] permutation(String s) {
        Set<String> list = new HashSet<>();
        char[] arr = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        boolean[] visited = new boolean[arr.length];
        dfs(arr, "", visited, list);
        return list.toArray(new String[0]);
    }
    public void dfs(char[] arr, String s,  boolean[] visited, Set<String> list){
        if(s.length() == arr.length){
            list.add(s);
            return;
        }
        for(int i=0; i<arr.length; i++){
            if(visited[i]) continue;
            visited[i] = true;
            dfs(arr, s+String.valueOf(arr[i]), visited, list);
            visited[i] = false;
        }
    }
}

数组中出现次数超过一半的数字

题目：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

基础做法就是使用哈希表，遍历数组，键就是数组元素，值是该元素出现的次数，统计好后再遍历一次哈希表找到值最大的键输出即可。

取巧点就排序数组（ Arrays.sort() ），然后输出中间值，因为题目说该数字出现次数超过了数组的一半，排序后的中间值一定就是答案。

然后更巧妙的算法可以看大佬题解，例如摩尔投票法等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int majorityElement(int[] nums) {
        int max = 0,ans = 0;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            //统计键重复的次数，更新值
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
		//遍历取出最大值的键
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue() > max){
                max = entry.getValue();
                ans = entry.getKey();
            }
        }
        return ans;
    }
}

摩尔投票法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int majorityElement(int[] nums) {
        // 初始化投票数与众数
        int vote = 0, mode = 0;
        // 遍历一次数组，若投票和为0，说明上一个数不是当前的众数
        // 因为众数就会有多个连续相等，投票和不会归0
        // 随后就是判断当前众数是不是整个数组的众数
        // 若遍历完数组，当前众数的投票和不为0，说明它就是数组的众数
        for(int num : nums){
            if(vote == 0) mode = num;
            if(mode == num) vote += 1;
            else vote -= 1;
        }
        // 返回众数，没有众数则是初始值0
        return mode;
    }
}

最小的k个数

题目：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

弱智写法：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        int[] ans = new int[k];
        for(int i=0 ;i<k;i++){
            ans[i] = arr[i];
        }
        return ans;
    }
}

快排：

基础算法要从头过一遍了，都忘了😂

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
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr,0,arr.length-1);
        return Arrays.copyOf(arr,k);
    }
    //就是寻找中间值，每次都把数组分成左小右大，然后递归左右数组继续
    private void quickSort(int[] arr,int l,int r){
        if(l>r) return ;
        int i = l,j = r;//i、j是现在操作的索引，l、r是当前的左右边界
        //l充当中间值，寻找比它小和大的数
        while(i<j){
            //从右边界开始，>=中间值l就通过
            while(i<j && arr[j] >= arr[l]) j--;
            //右边界索引遇到小于l，所以暂停了
            //然后从左边界开始，<=中间值l就通过
            while(i<j && arr[i] <= arr[l]) i++;
            //i对应一个左边>=中间值的数，j对应一个右边<=中间值的数
            //因为需要调整数组为左小右大，二者换位
            swap(arr,i,j);
        }
        /*在完成一次次大小交换后，i，j会指向同一个元素，因为i<j以及i++的特性
         *且每次都是先判断j，也就是说i=j这个元素是根据j的暂停位置定下的，这个值小于中间值
         *然后我们可以把中间值真正的换到中间来，形成左小右大，然后根据左右数组继续递归
         */
        swap(arr,l,j);
        //现在i、j指向同一个即中间值，舍去中间值来划分左右区间即可
        quickSort(arr,l,i-1);
        quickSort(arr,j+1,r);
    } 

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

其实完全遍历一遍排序后时间都差不多，来看看大佬的优化，限制了返回的长度，只需要找出前k个元素来排序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) return arr;
        return quickSort(arr, k, 0, arr.length - 1);
    }
    private int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        return Arrays.copyOf(arr, k);
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

数据流中的中位数（堆排序）

题目：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/

使用优先队列实现大小堆，可以让查找中间值变为O1，因为中间值只会和大小堆顶元素产生关系。做这题前可以先去了解一下优先队列的规则，然后就明白为什么用它初始化大小堆。

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
class MedianFinder {
    Queue<Integer> max,min;
    /* 123大顶堆，队首出队顺序为321。456小顶堆，队首出队顺序为456
     * 可以发现123456这个数据流存放两个堆后，大顶堆保存小的部分，小顶堆保存大的部分
     * 这样维护的两个堆的堆顶就和中间值产生了联系，数据是从小到大排序，会先在大顶堆存放
     * 所以当数据个数为奇数时，大顶堆比小顶堆多一个，也就是说中间值就是大顶堆的堆顶
     * 而个数为偶数时，中间值就是中间两个数的平均值，也就是大小堆顶元素的平均值
     */
    public MedianFinder() {
        //使用优先队列，默认为升序排列，队首一定是最小的，符合小顶堆
        max = new PriorityQueue<>();
        //优先队列使用降序排列，队首一定是最大值，符合最大堆
        min = new PriorityQueue<>(Comparator.reverseOrder());
    }
    
    public void addNum(int num) {
        /* 现在数据存放个数为奇数，也就是大顶堆比小顶堆多一个，往小顶堆存放
         * 否则两个堆都是偶数，该往大顶堆存放
         * 注意存放大小堆前一定要先存到对面然后再取，因为我们大顶堆要小的，小顶堆要大的
         * 但新进来的数据元素是无法分辨大小的，比方说要存入小顶堆，先存入大顶堆，然后取其队首
         * 保证入队的元素一定是除了小顶堆中最大的，存入大顶堆也同理，保证是除了大顶堆中最小的
         */
        if(max.size() != min.size()){
            max.add(num);
            min.add(max.poll());
        }else{
            min.add(num);
            max.add(min.poll());
        }
    }
    
    public double findMedian() {
        return max.size() != min.size() ? max.peek() : (max.peek() + min.peek())/2.0;
    }
}

连续子数组的最大值

题目：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

没有使用dp，直接分析数组，当前和为正数时，直接比较取最大值，若当前和为负数且小于待加的数就舍弃。（因为有全是负数的情况，所以和为负数不能直接舍弃）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxSubArray(int[] nums) {
        int max=Integer.MIN_VALUE,sum=0;
        //正数相加取最大值，负数的sum和下一个加的元素比较，若该值比待加元素还小就舍弃
        for(int num : nums){
            //如果当前sum小于0，且小于当前正处理的数，则这个sum无效并舍弃
            if(sum<num && sum<0){
                sum=0;
            }
            sum += num;
            max = Math.max(max,sum);
        }
        return max;
    }
}

1~n整数中1出现的次数

题目：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/

我们将整个数分成3部分，高位、当前位、低位，然后逐位进行1数量的累加

  • 当前位=0，说明当前位无1，低位的改变不影响当前位1的数量，数量是high * 该位的幂因子
  • 当前位=1，当前位可与低位配合增加1出现的数量（1000~1XXX），一共有XXX+1个，也就是low+1，然后加上高位的组合，数量是high * 幂因子+low+1
  • 当前位=29，当前位可与低位配合增加1出现的数量（X000XXXX），X>1所以10001999这个区间被包含，也只有该区间有1出现，所以29都是一个情况，而此时低位组合后1出现次数为 该位的幂因子（1019 = 10，100199 = 100，1000~1999 = 1000 ·····），所以数量是high * 幂因子 + 幂因子，即(high+1) * 幂因子
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 int countDigitOne(int n) {
        //初始化幂因数，也就是10的0次方，高位数、当前位、低位数
        int factor=1,ans=0,high = n/10,cur = n%10,low = 0;
        //从个位开始循环，直到最高位
        while(high != 0 || cur != 0){
        /*分三种情况，当前位为0时，该位出现1的次数只与高位相关，high * factor
         *当前位为1时，该位出现1的次数除高位外，还要加低位即1000~1XXX(low)，也就是加low+1
         *当前位2~9时，只有一种情况即10~19的1，20~99当前位均不出现1，(high+1) * factor
         */
            if(cur == 0) ans += high * factor;
            else if(cur == 1) ans += high * factor + low + 1;
            else ans += (high + 1) * factor;
            
            low += cur * factor;//低位更新为当前位*幂因子，当前位要前移，记录它现在的值归并到低位
            cur = high % 10;//当前位更新为高位取余，也就是顺移下一位
            high = high / 10;//高位更新为高位除去末位，也就是舍弃末位给当前位
            factor *= 10;//根据当前位数改变相应幂因子，也就是10的n次方
        }
        return ans;
    }
}

数字序列中某一位的数字

题目：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/

8.png

用了K神题解的图，先分析数字位数区间，起始位，数的数量（数字），数字数量（数位），得出关系式，然后用n减去低位数的数字数量直到<0，此时说明现在的位数就是n的位数，然后再找n处于哪一个数的某个位置上，最后转换成int输出。注意start是第0个数，所以后续使用n-1计算，而不是n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findNthDigit(int n) {
        int digit = 1; //数位，也就是几位数
        long start = 1; //每位数的起始位，1、10、100····
        long count = 9; //该位数有多少个数字，一位数1~9有9个，三位数100~999有900个
        //n<0退出循环
        while(n > count){
            n -= count; //减去低位数的数量
            digit++; //位数递增
            start *= 10; //更新起始位
            count = 9 * start * digit;//9*start计算有多少个数，*digit计算有多少个数字
        }
        //跳出循环，说明低位数字的数量减完了，现在的位数就是当前n的
        //(n-1)/digit说明处于哪一个数中
        long num = start + (n-1)/digit;
        //(n-1) % dight查看n是数的哪一个数字，-'0'是为了字符转换int型
        //'9'-'0'=9两个ascll码差值为int
        return Long.toString(num).charAt((n-1) % digit) - '0';
    }
}

把数组排成最小的数

题目：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

这题本质就是快排，只不过判断条件的书写需要注意一下。排序其实还是有点生疏，得抽空把排序练熟。

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
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]);
        quickSort(strs,0,strs.length-1);
        //排好序后，拼接字符串数组，并返回String
        StringBuilder ans = new StringBuilder();
        for(String s : strs)
            ans.append(s);
        return ans.toString();
    }

    void quickSort(String[] strs,int l,int r){
        if(l > r) return;
        int i = l,j = r;
        String temp = strs[i];
        //快排和哨兵做比较，哨兵左小右大
        while(i < j){
            //字符串比较， >=0说明ji的排序比lj的大，j大于哨兵,j>l，符合题意，j--查找下一位
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            //<=0说明il比li的排序值小，i是小于哨兵，i<l，符合题意，j++查找下一位
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            //前两个循环退出，说明此时的i>l，j<l，得出i>j，打印最小数要从小到大，所以交换i、j
            temp = strs[i];
            strs[i] = strs[j];
            strs[j] = temp;
        }
        //此时循环退出，i=j处于数组的中间部分，哨兵和i(j)交换，实现数组左小右大
        strs[i] = strs[l];
        strs[l] = temp;
        //开启递归
        quickSort(strs,l,i-1);
        quickSort(strs,i+1,r);
    }
}

把数字翻译成字符串

题目：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

本质就是一个动态规划的题目，需要找到dp的规律。这里借用一下k神的图来理解。

9.png

1i-1也就是前i-1个数的方案记为f(i-1)，推断出单独翻译第i个数时，有f(i-1)个方案，因为单独翻译i只有1种，其方案数由前i-1来决定。而题目种有26个字母，也就是两个数组合在[10,25]这个区间时，我们组合出新的方案，例：i-1i两个组合成一个可被翻译的数，其方案数为f(i-2)，由前i-2来决定。

所以计算f(i)，分两种情况，i-1i可以组合，f(i) = f(i-2) + f(i-1)；i-1i不可组合，f(i) = f(i-1)。通过字符串的分割和比较来实现区间判断。substring(i-2,i)是i-2、i-1的组合字符串。

假设dp[2]也就是前两个数可组合，得到dp[2]=dp[0]+dp[1]，明确知道dp[2]=2，dp[1]=1，倒推出dp[0]=1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int[] dp = new int[s.length()+1];//多了一种空串的情况dp[0]
        dp[0] = 1;//空串
        dp[1] = 1;//只有一个字符
        
        for(int i = 2 ;i < s.length()+1 ;i++){
            String temp = s.substring(i-2,i);//左闭右开
            //判断是否能两两组合，[10,25]才能被翻译
            if(temp.compareTo("10") >= 0 && temp.compareTo("25") <=0)
                dp[i] = dp[i-2] + dp[i-1];
            else 
                dp[i] = dp[i-1];
        }
        return dp[s.length()];
    }
}

礼物的最大价值

题目：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/

标准的动态规划题目，找到转义方程就很好做了，注意我们可以直接在原来的二维数组上覆盖值变成答案，最后直接返回最后一个元素即可。直接覆盖比较节省空间，然后分四种处理情况，左上角初始值不变，上和左靠边的值只受单方向影响，其余值则累加左和上的最大值。左和上对应 只能右和下移动。

有两种方法，一种是直接遍历数组，分情况判断，但多执行多次边情况的判断语句，所以另一种方案是先初始化边上值，然后遍历其余元素即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // for(int i=0;i < m;i++){
        //     for(int j=0;j < n;j++){
        //         if(i==0 && j==0) continue;
        //         if(i==0) grid[i][j] += grid[i][j-1];
        //         else if(j==0) grid[i][j] += grid[i-1][j];
        //         else grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
        //     }
        // }
        
        //边界初始化
        for(int j=1;j < n;j++) grid[0][j] += grid[0][j-1];//上边界
        for(int i=1;i < m;i++) grid[i][0] += grid[i-1][0];//左边界
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
        return grid[m-1][n-1];
    }
}

最长不含重复字符的子字符串

题目：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/

这题书上用的是动态规划，但我一开始想到的思路就是滑动窗口的，所以就没有选择动态规划的做法，用哈希表来进行滑动窗口，我一开始还在那捣鼓数组和字符串，根本没想到用Map容器比较好。

基本思路就是遍历一次字符串，无重复右边界++，记录长度最大值，有重复则修改左边界然后记录最大值，这里关键就是这个左边界的更新。使用的是下面这个语句，一开始不知道为什么要取max，然后发现了一个特殊情况**”abba”**，max就是为了应对这种情况，详细看下面分析：

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 int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int l = 0,r = 0,ans = 0;
        while(r < s.length()){
            char cur = s.charAt(r);
            if(map.containsKey(cur)){
            /* 右边界值cur重复，所以更新左边界，但map存放的cur是第一次的位置还没有更新
             * 所以我们现在是获取cur上次位置+1，在"abca"中a重复，l指向b，就没有重复的值
             * 但是为什么与l取最大值呢，在"abba"中a重复，l应指向第二个b，因为b之前已经重复了
             * 若指向a重复的初始位置+1，则bba还包含一个重复，所以我们是取一个最大值 
             */
                l = Math.max(l, map.get(cur) + 1);
            }
            map.put(s.charAt(r),r);
            //我边界初始化l=0，而不是l=-1，所以重复计算是r-i+1
            ans = Math.max(ans,r-l+1);
            r++;
        }
        return ans;
    }
}

丑数

题目：https://leetcode-cn.com/problems/chou-shu-lcof/

按照2、3、5的倍数，从1开始，模拟构造整个丑数序列，返回第n个数，其中每次返回乘积最小值作为这一个序列的值，给每一个倍数都标记一个索引值，即代表处于数组的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//我们直接求出丑数序列，返回第n个即为答案
//因为丑数只与2、3、5有关，序列初始化第一个是1，随后序列中的数分别乘以2、3、5
//取最小值为第二个，然后该最小值的倍数的索引++，这样从1开始就是一个完整的丑数序列
class Solution {
    public int nthUglyNumber(int n) {
        int i2=0,i3=0,i5=0;
        int[] res = new int[n];
        res[0] = 1;
        for(int i=1;i<n;i++){
            int ans2 = res[i2] * 2;
            int ans3 = res[i3] * 3;
            int ans5 = res[i5] * 5;
            res[i] = Math.min(ans2,Math.min(ans3,ans5));
            if(ans2 == res[i]) i2++;
            if(ans3 == res[i]) i3++;
            if(ans5 == res[i]) i5++;
        }
        return res[n-1];
    }
}

第一个只出现一次的字符

题目：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/

注意这里键值对使用的是布尔值，方便后续判断返回，如果记数统计，后续还要加一个判断语句。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public char firstUniqChar(String s) {
        //哈希表按字符、布尔值的键值对存储
        Map<Character,Boolean> map = new HashMap<>();
        char[] str = s.toCharArray();
        //将当前字符存入哈希表，有重复字符则记为false，无重复true
        for(char c : str)
            map.put(c, !map.containsKey(c));
        //因为要按序返回结构，遍历字符串，若当前字符无重复就返回字符
        for(char c : str)
            if(map.get(c)) return c;
        //所有其他情况返回空格
        return ' '; 
    }
}

有序哈希表，使用LinkedHashMap这个特殊结构，保证哈希表的存储是有序的，最后我们直接遍历哈希表的即可，因为哈希表去重，我们不用重复访问同一字符，比遍历字符串可能快一点。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public char firstUniqChar(String s) {
        Map<Character,Boolean> map = new LinkedHashMap<>();
        char[] str = s.toCharArray();
        for(char c : str)
            map.put(c, !map.containsKey(c));
        for(Map.Entry<Character,Boolean> entry : map.entrySet())
            if(entry.getValue()) return entry.getKey();
        return ' '; 
    }
}

数组中的逆序对

题目：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

归并排序题目，下面写了K神的注释版，这个看明白后可以再看一下另外一个版本，我感觉看起来思路会更加清晰。

20.png

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
class Solution {
    int[] nums, temp;
    public int reversePairs(int[] nums) {
        this.nums = nums;
        temp = new int[nums.length];
        return mergeSort(0,nums.length-1);
    }
    
    private int mergeSort(int l, int r){
        if(l >= r) return 0;
        int m = (l + r) / 2;
        int ans = mergeSort(l,m) + mergeSort(m+1,r);
        
        
        //nums是原数组，我们要通过归并排序来排序
        //先把值赋予临时数组，临时数组通过排序再来更新nums
        for(int k = l; k <= r; k++)
            temp[k] = nums[k];
        //i、j分别指向左右子数组的初始位，l~m，m+1~r
        int i = l, j = m + 1;
        for(int k = l; k <= r; k++){
            //i==m+1，说明左子数组合并完毕，直接把剩下的右子数组合并即可
            //因为左右子数组是已经排好序的，所以左边合并完，右边可以直接进来
            if(i == m + 1)
                nums[k] = temp[j++];
            //右子数组边界r，r+1代表有子数组合并完毕，后把剩下的左子数组合并
            //当左值小于右值，就把左值存放到nums，此时没有逆序对
            else if(j == r + 1 || temp[i] <= temp[j])
                nums[k] = temp[i++];
            //else即左值大于右指，出现逆序对，需要存入右指并计算逆序对数量
            else{
                nums[k] = temp[j++];
                //我们计算逆序对数量通过左子数组判断，当前出现逆序对
                //左子数组索引是i，i之后的值都是大于右值的，因为子数组有序
                //而i之前的值都是小于右值，然后才i++通过的
                //所以计算左子数组当前位到末位的数量，即当前位逆序对数量
                ans += m - i + 1;
            } 
        }
        return ans;
    }
}

评论区版本，理解归并排序后，我感觉这个写的更清晰。

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 {
    //归并排序，在其过程中统计逆序数量，右边每次放上去都要加上：left.length - i
    int count = 0;//统计归并过程中的逆序对数情况
    public int reversePairs(int[] nums) {
        int len = nums.length;
        if(len < 2) return 0;//不构成任何一对
        mergesort(nums, 0, len - 1);
        return count;
    }

    public int[] mergesort(int[] nums, int l, int h){
        if(l == h) return new int[]{nums[l]};//单个数据直接返回
        int mid = l + (h - l) / 2;
        int[] left = mergesort(nums, l, mid);
        int[] right = mergesort(nums, mid + 1, h);
        int[] res = new int[h - l + 1];
        int i = 0, j = 0, m = 0;
        while (i < left.length && j < right.length) {
            if(left[i] <= right[j]){
                res[m++] = left[i++];
            }else{
                res[m++] = right[j++];
                count += left.length - i;
            }
        }
        while (i < left.length)
            res[m++] = left[i++];
        while (j < right.length)
            res[m++] = right[j++];
        return res;
    }
}

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

题目：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

通过数学思维来简化代码，很巧妙，语句也很简便易懂。可以看看题解的动图详解：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 //通过数学思维简化，将两个链表相交转换为
 //走完a.length + B相交前的length = b.length + A相交前的length
 //设公共结点same个，A总结点a个，B总结点b个
 //a + (b-same) = b + (a-same)，可以直接画个图看看
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA,B = headB;
        //!=null的判断就是为了走完原链表后，继续走另一个链表的未相交部分
        //这里用三元运算符就很简便
        while(A != B){
            A = A!=null ? A.next : headB;
            B = B!=null ? B.next : headA;
        }
        return A;
    }
}

在排序数组中查找数字

题目：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/

这里使用二分法加快时间效率，需要注意中间值与目标值相等时，后续的边界该如何判断，查找重复目标数的右边界就归于小于情况，查找左边界归于大于情况，然后退出循环的边界复制可以去看K神题解的动图，边界好理解退出循环时l、r的位置。

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
/* 中间值mid小于target和大于的情况与以前二分一样
 * 小于说明目标值在右边，左边界=mid+1
 * 大于说明目标值在左边，右边界=mid-1
 * 而mid==target时，我们根据情况分类：
 * 查询重复目标数的右边界，就归于小于的情况，向右查找
 * 查询重复目标数左边界时，归于大于情况，向左查找
 */

class Solution {
    public int search(int[] nums, int target) {
        //查找重复目标数的右边界
        int l=0,r=nums.length-1;
        while(l<=r){
            int mid = (l + r)/2;
            if(nums[mid] <= target) l = mid+1;
            else r = mid-1;
        }
    /* 此时数组边界l>r，也就是当l=r的数大于target，执行了r=mid-1
     * 可以看题解的动图很直观，处理后r处于重复目标数的右边界，l在右边界后一位
     * r应该是最后一个重复目标数，而它不等于target则说明数组无目标数，返回0
     */
        int right = r;
        if(r >= 0 && nums[r] != target) return 0;

        //查找重复目标数的左边界
        l=0;r=nums.length-1;
        while(l<=r){
            int mid = (l + r)/2;
            if(nums[mid] < target) l = mid+1;
            else r = mid-1;
        }
        //l是第一个重复目标数
        int left = l;
        //重复目标数的首尾索引相减后+1，就是重复的次数
        return right - left + 1;
    }
}

隔了好久回来刷题，发现下面简写版本更易理解，说实话这题二分想的挺多的，不如遍历😂，但是思想要到位。遍历也可以剪枝的，当值大于目标就可以直接退出了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int search(int[] nums, int target) {
        return local(nums, target) - local(nums, target - 1);
    }
    // 二分查询目标值，返回最终两索引碰头位置，也就是目标值区间后第一个数
    // 通过两次相邻目标值返回的终结索引，可以得到目标值的区间，计算差值可得出现次数
    public int local(int[] nums, int target){
        int l = 0, r = nums.length - 1;
        while(l <= r){
            int m = (l + r) / 2;
            if(nums[m] <= target) l = m + 1;
            else r = m - 1;
        }
        return l;
    }
}

0~n-1中缺失的数字

题目：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

K神：排序数组的搜索问题，优先二分法、双指针。要注意退出循环后的两个指针的位置，然后判断返回值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int missingNumber(int[] nums) {
        int l = 0,r = nums.length-1;
        //如果中间值不相等，那么一定是已经缺失了数字，向左查找
        //而相等缺失数字还不存在，向右查找
        while(l<=r){
            int mid = (l+r)/2;
            if(nums[mid] == mid) l = mid + 1;
            else r = mid - 1;
        } 
        //退出循环，r<l,此时nums[r]与nums[l]间即为缺值
        //l、r分别指向"右子数组的首位元素"和"左子数组的末位元素"
        return l;
    }
}

二叉搜索树的第k大结点

题目：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

因为是二叉搜索树，左小右大，我们使用右根左的中序遍历，递归二叉树后，数组记录从大到小的根结点值，返回第k-1个结点即可。但还可以优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    List<Integer> ans = new ArrayList<Integer>();
    public int kthLargest(TreeNode root, int k) {
        inorder(root);
        return ans.get(k-1);
    }
    void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.right);
        ans.add(root.val);
        inorder(root.left);
    }
}

递归时实时更新k值，当k==0时就纪录当前根节点，随后的递归全部直接退出，这样可以不用遍历完二叉树。走到第k个就返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    int ans,k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        inorder(root);
        return ans;
    }
    //中序遍历到第k个值后就记录值并退出
    void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.right);
        //如果当前k==0，说明值已找到，可以停止递归了
        if(k == 0) return;
        /* if(k == 0) return;
         * k--;
         * if(k == 0) ans = root.val;
         * 当前k!=0，--k即走过一个结点，若==0就记录值
         * 这里是把走过一个结点改变k值和第二次判断k写一起了
         */
        if(--k == 0) ans = root.val;
        inorder(root.left);
    }
}

二叉树的深度

题目：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

easy题，记录深度状态，每次叶子结点就更新深度，最后返回深度即可。（也就是所有路径长度的最大值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 遍历二叉树，往下走一层，深度++，然后走左右子树
 * 左右子树都返回后退回上一层，深度--
 * 每次走到叶子结点就返回并更新深度值
 * 最后返回深度的值即可
 */
class Solution {
    //初始化深度为0，每往下走一层就+1
    int depth=0,ans;
    public int maxDepth(TreeNode root) {
        tree(root);
        return ans;
    }
    void tree(TreeNode root){
        if(root == null){
            ans = Math.max(depth,ans);
            return;
        }
        depth++;//往下走一层
        tree(root.right);//走右子树
        tree(root.left);//走左子树
        depth--;//返回上一层
    }
}

平衡二叉树

题目：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

自底向上，我们先走到叶子结点，然后返回上一层，并记录左右子树的深度，然后每走到一个子树根结点就判断其子树是否为AVL，如果是就继续返回上层进行判断，如果不是就返回-1来标记不是AVL，且每次计算子树深度后都判断该值是否为-1，如果是-1则说明这棵树不是AVL，然后就可以直接返回进行剪枝操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isBalanced(TreeNode root) {
        //等于-1则不是AVL树，这里true要判断是AVL，所以要不等于-1
        return balance(root) != -1;
    }
    private int balance(TreeNode root){
        //走到叶子结点就终止
        if(root == null) return 0;
        //当前左子树的深度
        int left = balance(root.left);
        //如果左子树为-1说明已判断不是AVL，直接返回-1进行剪枝处理
        if(left == -1) return -1;
        //当前右子树深度
        int right = balance(root.right);
        //右子树不是AVL，直接返回进行剪枝
        if(right == -1) return -1;
        //abc绝对值取当前左右子树差值，若深度差小于1，说明当前结点左右子树符合AVL
        //返回当前结点的深度，深度差大于1，说明该结点子树已不是AVL返回-1
        return Math.abs(left - right) <= 1 ? Math.max(left,right)+1 : -1; 
    }
}

数组中数字出现的次数（一）

题目：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

规定O(n)的时间复杂度，我们不可以使用Map键值对，这里很巧妙使用了异或以及按位与的位运算。先通过异或找到两个不相等数的异或和；然后按位与找到异或和中的差异位，这就是两个不相等数的不同位，只有其中一个数有这个位数；接着我们就把数组以该位数分成两部分，一部分有这一位，另一部分没有这一位，并异或计算；由于其他数都是成对出现，异或后都会变为0不影响结果，我们通过差异位分组异或就得到了两个不相等的数。

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[] singleNumbers(int[] nums) {
        int ans1=0,ans2=0,a=0,b=1;
        /* 异或，两个相等的数计算后等于0，0与任意数计算等于该数本身
         * 根据题意数组异或后得到两个不相等数的异或和
         */
        for(int num : nums)
            a ^= num;
        /* 由于a是两个不相等数的异或和，那么a一定有为1的位数
         * 这一位就代表两个不相等数的差异位，我们从1位开始查找异或和的差异位
         * 只要当前位不为1，说明还没找到差异位，就左移参数b，继续查找
         * 最后退出循环时，b就是差异位的位数
         */
        while( (a & b) == 0 )
            b <<= 1;
        /* b代表差异位，我们通过按位与操作来查找存在差异位的数
         * 将存在差异位的数和不存在的数分成两个部分分别异或计算，也就是按位与b判断
         * 除了两个不相等的数，其余数都是成对出现，我们相当于在分开两个不相等的数
         * 由于其余数的都是成对的，异或和为0，则分开异或得到的结果就是两个不相等的数
         */
        for(int num : nums){
            if( (num & b) == 0 ) ans1 ^= num;
            else ans2 ^= num;
        }
        return new int[] {ans1,ans2};
    }
}

数组中数字出现的次数（二）

题目：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

思路就是把数组每一个数逐位判断，统计该位==1的次数，然后和3取余，由于其他数都是3个一对，只有一个数是单独的，所以当我们取余后与1判断，如果等于1说明这一位是单独数所包含的，然后就按位 或运算 给结果的这一位数赋值。逐位判断后即可得到这个单独的数。

其他的简答方法，哈希表存储后查找值==1的键；使用排序算法将数组排序，然后有三种情况：ABBBCCC、BBBACCC、BBBCCCA，我们就分三种情况讨论，若第一个!=第二个，最后一个不等于倒数第二个，遍历数组的中间值不等于前后两个数，那么第一个、最后一个、中间值就是三种情况下的单独数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int singleNumber(int[] nums) {
        //结果初始化全0
        int res = 0;
        //标记结果的位数，逐位赋值，int上限32位
        for(int i=0;i<32;i++){
            int count = 0;
            //把全部数组的值右移要标记的位数，计算数组这一位有多少个1
            for(int j = 0;j < nums.length;j++)
                count += (nums[j] >>> i) & 1;

            //没有余2的情况，都是3个一对，多出了1个，只会余1
            //所以余1代表，这一位出现了单独的数字，要记入结果
            if(count % 3 == 1)
                //<<优先级高于|=，我们先左移i位1，然后将结果的这一位标记为1
                res |= 1 << i;
        }
        return res;
    }
}

和为s的两个数字

题目：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/

简单题，左右双指针解决。还有哈希表存值匹配的做法，就是两数之和那题的解法，不过这里数据更多O(n)很慢了，我们可以借助排序特性，使用左右双指针只遍历一次数组实现O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
//左右边界双指针判断值所在区间，然后更新左右边界
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0,r = nums.length-1;
        while(l<r){
            if(nums[l] + nums[r] > target) r--;
            else if(nums[l] + nums[r] < target) l++;
            else return new int[]{nums[l],nums[r]};
        }
        return new int[0];
    }
}

和为s的连续正数序列

题目：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

题目思路很简单，滑动窗口。但最后list转数组让我犯了愁，可以看看下面这个文章，写的比较清楚：

https://juejin.cn/post/6844904145753735176

也就是说我们使用toArray方法，不带参数返回Object类型，带参数就返回参数类型，由于Object是不能直接强转其他类型的，所以我们使用**toArray(T[] a)**这个重载方法参数就是我们需要返回的类型，而这个参数数组一般大小设为0，Java为这一块进行过优化，如果设置大小偏大或偏小都要重新分配，还不如一开始设为0，且大小设置相等时，遇见高并发情况也会出现问题，所以我们直接设大小为0是性能最优的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] findContinuousSequence(int target) {
        //滑动窗口，思路比较简单，因为最少两个数，左右边界初始化为1、2
        int l=1,r=2,sum=3;
        List<int[]> ans = new ArrayList<>();
        while(l < r){
            //注意判断完一组符合target的数组并添加后，我们要让循环继续
            //所以要改变边界，左右均可
            if(sum == target){
                int[] res = new int[r-l+1];
                for(int i = l;i <= r;i++)
                    res[i-l] = i;
                ans.add(res);
                sum += ++r;
            }
            if(sum < target) sum += ++r;
            else if(sum > target) sum -= l++;
        }
        //这里返回值要集合list转数组，使用toArray重载方法
        //也就是toArray(T[] a)带参数的，不带参数是Object，带参数就是指定类型
        return ans.toArray(new int[0][]);
    }
}

翻转单词顺序

题目：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/

双指针的思路很简单，而且K神还想到了分割字符串后倒叙拼接，我一开始是倒叙+栈😂，慢哭了。看到双指针就明白优化的方法了，一开始还没想到，而且分割+倒叙拼接也很巧妙。有思路后马上就懂了，就是需要注意的空格的处理，自己写的时候没考虑周全，为了满足空格的处理情况加了很多不必要判断。

我的脑抽写法：

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 String reverseWords(String s) {
        if(s.equals("")) return "";
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        char[] temp = s.toCharArray();
        if(temp[temp.length-1] != ' ') stack.push(temp[temp.length-1]);
        for(int i=temp.length-2;i>=0;i--){
            if(temp[i] == ' '){
                if(temp[i+1] == ' ') continue;
                while(!stack.isEmpty())
                    sb.append(stack.pop());
                sb.append(' ');
            }else{
                stack.push(temp[i]);
            }
        }
        while(!stack.isEmpty())
            sb.append(stack.pop());
        return sb.toString().trim();
    }
}

双指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String reverseWords(String s) {
        //去首尾空格，并初始化左右边界，从后往前
        s = s.trim();
        int r = s.length()-1,l = r;
        StringBuilder ans = new StringBuilder();
        while(l>=0){
            //查找单词左边界，也就是单词前的第一个空格
            while(l>=0 && s.charAt(l) != ' ') l--;
            //截取字符串左闭右开，现在l处于单词前一个空格处，r处于单词末位
            //故根据左闭右开，截取范围是l+1~r+1
            ans.append(s.substring(l+1,r+1) + ' ');
            //单词之间的多个空格直接省略
            while(l>=0 && s.charAt(l) == ' ') l--;
            //多个空格省略后，左边界的位置就是下一个单词的右边界
            r = l;
        }
        //返回值还要取出每次拼接的空格，因为最后一次会多一个
        return ans.toString().trim();
    }
}

分割+倒叙拼接：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String reverseWords(String s) {
        //将字符串去首尾空格后，按照空格分割单词
        //但是要注意有X个空格相连时(X>1)，分割后会形成X-1个空字符串""
        String[] strs = s.trim().split(" ");
        StringBuilder ans = new StringBuilder();
        for(int i = strs.length-1;i >= 0;i--){
            //把分割时形成的空字符串跳过
            if(strs[i].equals("")) continue;
            ans.append(strs[i] + " ");
        }
        return ans.toString().trim();
    }
}

左旋转字符串

题目：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/

简单题，左右截取，反转拼接即可。

1
2
3
4
5
6
7
8
9
10
//不允许使用substring，则可以遍历字符串
//使用StringBuilder拼接第n+1~末位，然后是第0到第n，是一个意思
class Solution {
    public String reverseLeftWords(String s, int n) {
        String left = s.substring(0,n);
        String right = s.substring(n,s.length());
        right += left;
        return right;
    }
}

滑动窗口的最大值

题目：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

滑动窗口的思路其实很好想，我一开始也想到了先找一次max，然后每次与新的右边界比较依照结果更新max，如果max是左边界则要重新找max，因为max已不存在更新后的滑动窗口。但在数据存放上没有找到一个好都容器。这里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
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        //最大值结果输出的次数，也就是滑动了几次
        int[] ans = new int[nums.length - k + 1];

        //窗口还未形成，0~k-1，没有滑动
        //队列存放从大到小，队首是最大值
        for(int i = 0; i < k; i++){
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
        }
        //完成遍历后，此时形成第一个滑动窗口，右边界k-1，最大值就是队首
        ans[0] = deque.peekFirst();

        //已形成窗口，i表示为当前滑动窗口的右边界
        //但此时右边界为k，说明初始化为第二个滑动窗口
        //滑动时，如果最大值是未滑动前的左边界，那么之后就不在考虑它，因为它不在窗口内了
        for(int i = k; i < nums.length; i++){
            //队列最大值与未滑动前窗口左边界比较
            //若二者相等，说明最大值马上和现在的新窗口无关，让最大值出队
            if(deque.peekFirst() == nums[i - k])
                deque.removeFirst();
            //判断完左边界最大值的特殊情况后，我们只用考虑右边界与最大值的情况
            //然后更新对垒，形成从大到小排序
            //最后记录第二个滑动窗口的max
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
            ans[i - k + 1] = deque.peekFirst();
        }
        return ans;
    }
}

队列的最大值

题目：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

构造一个正常的先进先出队列queue，然后再构造一个双端队列deque进行两头操作来维护最大值，和昨天题目一样，值在deque中从大到小排序。

queue就是正常入队出队，deque需要进行最大值维护。

queue入队时，若当前值>deque末值，末值出队，将deque所有小于当前值的值都出队后，当前值入deque队尾。

queue出队时，若当前值=deque首位，首位也要出队，毕竟现在最大值已不存在queue中。

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
class MaxQueue {
    //队列正常记录先进先出
    Deque<Integer> deque;
    //双端队列记录最大值的变化，队首即最大值
    Queue<Integer> queue;
    public MaxQueue() {
        deque = new LinkedList<>();
        queue = new LinkedList<>();
    }
    
    public int max_value() {
        return deque.isEmpty() ? -1 : deque.peekFirst();
    }   
    
    public void push_back(int value) {
        queue.add(value);//入队
        //更新最大值
        while(!deque.isEmpty() && deque.peekLast() < value)
            deque.pollLast();
        deque.addLast(value);
    }
    
    public int pop_front() {
        if(queue.isEmpty()) return -1;
        //如果正常队首是最大值，我们双端队列也要舍去该值
        if(queue.peek().equals(deque.peekFirst()))
            deque.pollFirst();
        return queue.poll();
    }
}

n个骰子的点数

题目：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/

做这道题首先是理解题目意思，然后理解暴力破解思路，然后动态规划的做法就很好理解了。这道题就是逐渐加入骰子，然后求有n个骰子时其点数产生的范围是什么，然后求处这个范围里的值的分布概率，按序输出值的分布概率。下面贴一下K神题解的图。

12.png

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 double[] dicesProbability(int n) {
        double[] cur = new double[6];
        //初始化只有一个骰子的情况，即出现值为1~6，每个概率为1/6
        Arrays.fill(cur,1.0/6.0);
        //从加入第二个骰子开始dp计算概率，直到第n个
        for(int i = 2; i <= n; i++){
            //初始化现在新加入骰子后的值分布范围
            //从1~6开始，每次加入新骰子即最小值+1，最大值+6的范围
            //1~6，2~12，3~18，4~24，即6+5+5+···，综上得出5*i+1
            double[] temp = new double[5 * i + 1];

            //第一层记录n-1个骰子有多少个值，每一个值都要+1···+6来计算概率
            //概率依值递增，1+1，1+2，1+3···3+1···3+6···6+6
            for(int j = 0; j < cur.length; j++){ 
                for(int k = 0; k < 6; k++){
                    //每次出现重复值都会++，然后要/6.0计算当前分布的基数
                    //1/6，1/36，1/216就是基数，多个骰子肯定会有重复值，那么重复值概率也要++
                    temp[j+k] += cur[j]/6.0;//cur[j] * (1.0/6.0)
                }
            }
            //更新现在第n个骰子的值分布概率
            cur = temp;
        }
        return cur;
    }
}

扑克牌中的顺子

题目：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/

这道题可以想到很复杂，但解题关键就一句话，max-min<5，满足这个判断的无重复序列即可组成顺子，不得不说K神这规律挺会找啊，我一开始还在纠结怎么判断顺子，然而K神直接从结果出发，很容易解决了问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int max = 0, min = 14;
        for(int num : nums){
            //若当前牌是癞子，直接跳过
            if(num == 0) continue;
            //更新最大、小牌值
            max = Math.max(max,num);
            min = Math.min(min,num);
            //除癞子外，有重复牌的情况一定组成不了顺子
            if(set.contains(num)) return false;
            //首次出现的牌，添加到set
            set.add(num);
        }
        //能通过循环，说明5个数除癞子外无重复
        //也就是最大最小之间差4个以内的无重复序列是可以组成顺子的
        return max - min < 5;
    }
}

圆圈中最后剩下的数字（约瑟夫环）

题目：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

数学问题，这个解法只能说是看得懂讲不清楚的🤣，关键就是推导公式cur = (cur + m) % i，理解了这个题目就很容易了。注意我们解法就是倒推，这里贴一下K神的图，看图比较好理解。

14.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lastRemaining(int n, int m) {
        //当前剩下数字的索引位置
        //我们从只剩下一个数字的最终情况出发，来倒推该数字存在于原队列的位置
        //只剩一个数字的情况可以确定该数字的索引为0
        int cur = 0;
        //i即当前的数字总数，由于倒推从2开始一直到n，因为一开始给的是n个数
        for(int i = 2; i <= n; i++){
            //这一步是在还原上一层删除前，最后剩下数字在该队列的位置
            //cur + m是加每一层删除的个数，比如每次删第2个
            //01234、2340、402、24、2，我们通过加上m并取余获取索引变化前的位置
            cur = (cur + m) % i;
        }
        //最后直接返回cur，因为序列是从0开始，和索引从0开始一致
        return cur;
    }
}

股票的最大利润

题目：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/

这道题自己想到了非暴力破解思路就试着写写看，没想到过了，然后再去学习一下K神的题解，没想到大佬的更简洁😂，动态规划的思想还需要锻炼。

其实我的思想和K神的差不多，时间、空间效率算下来也差不多，就是写的有点冗杂了。，可以稍稍精简一下。然后说一下题目思路，利润主要讲究低买高卖，我们维护最小值来记录最大利润即可。当前最小值一有更新就使用新的min，最后返回利润即可。

自己的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int min_key = 0, min_value = prices[0], profit = 0, ans = 0, cur = 0;
        while(cur < prices.length){
            if(min_key == prices.length-1) return ans;
            for(int i = min_key + 1; i < prices.length; i++){
                if(prices[i] < min_value){
                    min_key = i;
                    min_value = prices[i];
                    break;
                }else {
                    profit = prices[i] - min_value;
                    ans = Math.max(ans,profit);
                }
                cur++;
            }
        }
        return ans;
    }
}

K神：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, profit = 0;
        for(int price : prices){
            min = Math.min(min,price);
            profit = Math.max(profit,price - min);
        }
        return profit;
    }
}

求1+2+…+n

题目：https://leetcode-cn.com/problems/qiu-12n-lcof/

由于限制了运算符，我们使用&&逻辑运算符的短路特性，即A&&B，若A为falseB就不会判断了，所以我们通过一个布尔值来确实 n==1 时退出递归。

1
2
3
4
5
6
7
8
9
class Solution {
    int sum = 0;
    public int sumNums(int n) {
        //通过布尔值辅助，判断递归的结束
        boolean x = n > 1 && sumNums(n - 1) > 1;
        sum += n;
        return sum;
    }
}

不用加减乘除做加法

题目：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/

题目一上来就禁止了+-*/，我们很自然就想到要用位运算，但怎么用就不知道了，看了下K神的题解，解析的很详细。我们把加法过程分为不进位和进位两种情况。

  • 不进位：此时我们只需要通过异或运算计算01->1、00->0、11->0，11此时要进位，不能记为1，所以没有使用按位与，然后就算出了当前不用进位的和。
  • 进位：通过按位与和移位运算，我们将同为1的位标记出来，并实现进位，也就是将其高的一位记为1，也就是左移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
class Solution {
    //a相当于无进位和，b相当于进位数，carry在汇编里代表进位
    public int add(int a, int b) {
        //没有进位时，直接算出和即可
        while(b != 0){
            //进位就是ab二进制有两位同为1就进位
            //同时左移一位，因为进位后肯定到高位了
            int carry = (a & b) << 1;
            //a与b计算不用进位的位数和，异或符合条件
            //因为 1 1 的情况，异或返回0
            a ^= b;
            //b更新为进位数，然后再去和无进位和相加
            b = carry;
        }
        //最后没有进位时返回的位数和就是答案
        return a;
    }
}
//详细一点的写法
class Solution {
    public int add(int a, int b) {
        int carry = (a & b) << 1, sum = a ^ b;
        while(carry != 0){
            a = sum;
            b = carry;
            carry = (a & b) << 1;
            sum = a ^ b;
        }
        return sum;
    }
}

构建乘积数组

题目：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/

看到题目我以为又是用位运算模拟，然后看了题解发现解法很巧妙，暴力解法肯定就是遍历数组a，然后b[i]等于这一排的数连乘，但不包括a[i]，使用暴力肯定是超时的。

我们可以拆分问题，通过i把数组分割成左右两部分，先遍历一次a数组，把左半部分对应每个b[i]进行连乘，然后在进行一次a数组遍历，从倒数第二个开始反向遍历，补上b[i]的右半部分，我们只需要两次拆分遍历便可完成连乘数组b的构建。可以看K神的分析图来理解。

15.png

16.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] constructArr(int[] a) {
        if(a.length == 0) return new int[0];
        int[] b = new int[a.length];
        int temp = 1;
        b[0] = 1;
        //计算左半部分，i之前的数值连乘
        for(int i = 1; i < a.length; i++){
            b[i] = b[i-1] * a[i-1];
        }
        //计算右半部分，i之后的数值连乘并乘以左部分得到结果
        for(int i = a.length-2; i >= 0; i--){
            temp *= a[i+1];
            b[i] *= temp;
        }
        return b;
    }
}

把字符串转换成整数

题目：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/

这道题确实有思路，也写出来了90%，就在最后拉了跨，超过long的范围的值确实有点不会处理，但tm怎么会有”+-2”、”-5-“、”-13+5”这种测试用例的。。。。。这几个用例真nm绝了。

自己写的有缺陷版本：

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 strToInt(String str) {
        str = str.trim();
        StringBuilder temp = new StringBuilder();
        for(int i = 0; i < str.length(); i++){
            char c = str.charAt(i);
            if(c == ' ' || c == '+') continue;
            if(c == '-') temp.append('-');
            else if(c >= 48 && c <= 57) temp.append(c);
            else break;
        }
        str = temp.toString();
        long ans = 0, cur = 1;
        for(int i = str.length() - 1; i >= 0; i--){
            char c = str.charAt(i);
            if(c == '-'){
                ans = 0 - ans;
                break;
            } 
            ans += (c-48) * cur;
            cur *= 10;
        }
        if(ans < 0 && ans < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        if(ans > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        return (int)ans;
    }
}

K神yyds，不多说啊，符号位和越界的处理都十分巧妙，五体投地了这下是。时间复杂度O(n)，因为使用了trim()去空格。

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 strToInt(String str) {
        //去空格，转换字符数组
        char[] c = str.trim().toCharArray();
        if(c.length == 0) return 0;

        // 这里判断越界的边界设置的很巧妙，并不是MAX，而是MAX/10
        // 我们判断时，只要非最终位越界，说明下一位肯定会越界
        // 这里/10，不用在最高位判断越界情况，因为越界就无法判断
        int ans = 0, bndry = Integer.MAX_VALUE / 10;

        // 判断标志位，这里就限制了标志位只在第一位生效
        // 后续出现的标志位就和其他字符一样没有用了
        // 这里i初始化1也很关键，若第一位是符号，则遍历从第2位开始
        // 而第1位不是符号的情况，遍历就从第1位开始
        int i = 1, sign = 1;
        if(c[0] == '-') sign = -1;
        else if(c[0] != '+') i = 0;

        for(int j = i; j < c.length; j++){
            // 遍历到数字以外的字符，直接退出
            if(c[j] < '0' || c[j] > '9') break;
            // 越界判断，这里是从左往右遍历，越界情况分两种
            // 判断时都是先判断越界再更新结果，走n前判断n-1值是否越界
            // 1、当前结果已越界，因为判定时一定不是最后一位
            //    所以接下来ans*10+x，最后一位肯定越界
            // 2、当前结果和界限相等，只有ans*10+x <= max时不越界
            //    max个位是7，也就我们的是后一位数字是8、9时越界
            if(ans > bndry || ans == bndry && c[j] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            ans = ans * 10 + (c[j] - '0');
        }
        return sign * ans;
    }
}

k神究极优化版本，没有使用trim()，将时间复杂度降到O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int strToInt(String str) {
        int res = 0, bndry = Integer.MAX_VALUE / 10;
        int i = 0, sign = 1, length = str.length();
        if(length == 0) return 0;
        while(str.charAt(i) == ' ')
            if(++i == length) return 0;
        if(str.charAt(i) == '-') sign = -1;
        if(str.charAt(i) == '-' || str.charAt(i) == '+') i++;
        for(int j = i; j < length; j++) {
            if(str.charAt(j) < '0' || str.charAt(j) > '9') break;
            if(res > bndry || res == bndry && str.charAt(j) > '7')
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            res = res * 10 + (str.charAt(j) - '0');
        }
        return sign * res;
    }
}

二叉搜索树的最近公共祖先

题目：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-i-er-cha-sou-suo-shu-de-zui-jin-g-7/

自己的解法，我们充分应用二叉搜索树的特性，左小右大，若根结点刚好处于两结点中间，说明根结点就是最小公共结点，返回根结点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    TreeNode ans;
    int min, max;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        min = Math.min(p.val, q.val);
        max = Math.max(p.val, q.val);
        MinCommonNode(root, min, max); 
        return ans;
    }
    // 充分应用二叉搜索树的特性，左小右大，若根结点刚好处于两结点中间
    // 说明根结点就是最小公共结点，返回根结点即可
    private void MinCommonNode(TreeNode root, int min, int max){
        if(root == null) return;
        if(root.val >= min && root.val <= max ){
            ans = root;
            return;
        }
        MinCommonNode(root.left, min, max);
        MinCommonNode(root.right, min, max);
    }
}

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
//迭代
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val > q.val) { // 保证 p.val < q.val
            TreeNode tmp = p;
            p = q;
            q = tmp;
        }
        while(root != null) {
            if(root.val < p.val) // p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            else if(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.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right, p, q);
        if(root.val > p.val && root.val > q.val)
            return lowestCommonAncestor(root.left, p, q);
        return root;
    }
}

二叉树的最近公共祖先

题目：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

  • 根结点的左右子树分别包含一个p、q结点，此时根结点就是位于正中间，即p、q最近公共祖先
  • 如果p、q结点不是分布于根结点左右两侧，说明只分布于其中的一侧
    • 位于左子树，返回递归左子树的结果即最近公共祖先
    • 位于右子树，返回递归右子树的结果即最近公共祖先
    • 如果两侧都没有，说明p、q并不在当前根结点下，返回空

这道题其实就是递归思路的运用，题解没看懂只能说还没理解清楚递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        //当前结点就是p、q返回p、q
        if(root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //左右子树均不为空，说明p、q分别位于左右子树，此时根结点即为中心，也就是最小父节点
        if(left != null && right != null) return root;
        //上面一个if未通过，说明p、q只存在于左子树 或 右子树
        //左子树不为空，说明p、q同时存在于左子树，返回左子树的结果
        if(left != null) return left;
        //右子树不为空，说明p、q同时存在于右子树，返回右子树的结果
        if(right != null) return right;
        //左右子树均不存在p、q结点，返回空
        return null;
    }
}

K神优化版本，转换了一点点思路就优化了代码，是真的强。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //根结点为空返回空，其实就是返回其本身，可以和遍历到p、q返回根结点的情况合并
        if(root == null || root == p || root == q) return root;
        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;
    }
}