代码

整理所有题目

09两个栈实现一个队列
- 栈队列
10斐波那契数列
- 迭代递归
03数组中重复的数字
- 数组原地置换
04二维数组中的查找
- 跳表从右往左从上往下
10-II 青蛙跳台阶
- 同斐波那契数列
旋转数组的最小数字
- 二分
05 替换空格
- StringBuffer
06从头到尾打印链表
- 栈反转
12 矩阵中到路径
- BFS +剪枝
07重建二叉树
- 递归
13机器人的运动范围
- DFS 考虑连通性
14剪绳子｜
- dp
14剪绳子｜｜
树的子结构
- 递归
对称的二叉树
- 递归
27二叉树的镜像
- 递归
29 顺时针打印矩阵
- 指针遍历
21 调整数组顺序使奇数位于偶数之前
- 双指针
15 二进制中1的个数
- 位运算 n&(n-1)消去最右边的1
22链表中的倒数第N个节点
- 快慢指针
16 数值的整数次方
- 快速幂
17 打印1到最大到N位数
- 大数打印
最小的K个数
- TOP K
- 快速选择
- 堆
反转链表
- 迭代
删除链表的节点
- 快慢指针
复杂链表的复制
- 复制节点
正则表达式匹配
- dp
30包含min函数的栈
- 最小栈
- 使用Deque
41数据流中的中位数
- 优先级队列
- 大根堆小根堆
42连续子数组的最大和
- 动态规划
36二叉搜索树与双向链表
- 中序遍历
31 栈的压入弹出序列
- 模拟法
37 序列化二叉树
- 层序遍历
43 1-n整数中1出现的个数
- 枚举每一数位上1的个数
39 数组中出现超过一半的数
- hash统计
- 数组排序找中点
- 摩尔投票法
44 数字序列中某一位的数字
- 数学归纳
38 字符串的排列
- 全排列II
- 回溯+剪枝
32 从上到下打印二叉树
- 层序遍历
33 二叉搜索树的后序遍历
- 递归
- 单调栈
51 数组中的逆序对
- 归并排序
50 第一个只出现一次的字符
- hash
34 二叉树中和为某一值的路径
- 回溯
- 剪枝
55 二叉树的深度
- 递归
56数组中数字出现的次数|
- 位运算
- 相同数字异或为0
- 找到其最右边的1 进行分组异或即可
56数组中数字出现的次数｜｜
- 使用数组记录其位的个数然后对3 取余
57 和为s的两个数字
- hash
45 把数组排成最小的数
- 排序重载
57 和为s的连续正序数列
- 双指针
- 滑动窗口
46 把数字翻译成字符串
- 回溯法(数据量少)
- dp(属于是爬楼梯变种)
52 两个链表的第一个公共节点
- 数学归纳
47 礼物的最大价值
- dp
- 可以开大一点的空间，减少边界处理的复杂度比如 0开始的 i-1
- 回溯（超时）
58I反转单词顺序
- substring
- 双指针
58II 左字符串
- substring
53I在排序数组中查找数字I
- 二分
53II 0-n-1中缺失的数字
- 二分
48 最长的不含重复字符的字符串
- 双指针
54 二叉树的第K大节点
- 中序遍历
49 丑数
- 模拟法
65 不用加减乘除做加法
- 位运算
67 把字符串转换为整数
- 模拟法
61 扑克牌中的顺子
- hash
52 II 平衡二叉树
- 递归
62 圆圈中最后剩下的数字
- 约瑟夫环问题
63 股票的最大利润
- dp
59 I 滑动窗口的最大值
- 单调队列
- 大 -> 小
59 II 队列的最大值
- 单调队列
- 注意包装类比较值使用equals方法
60 n个骰子的点数
- dp
66 构建乘积数组
- dp

代码

基础代码

两个栈实现一个队列

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

斐波那契数列

class Solution {
    public int fib(int n) {
        int a = 0;
        int b = 1;
        int c = 0;
        for(int i = 1; i < n ;i ++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

数组中重复的数字

class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int i = 0 ; i < nums.length; i++) {
            if(nums[i] != i){
                swap(i, nums[i],nums);
                if(nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
            }

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

二维数组中的查找

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null ||matrix.length == 0 ||matrix[0].length==0) return false;
        //从右上角开始
        int x = matrix.length-1;
        int y = 0;
        while(x>=0 && y<= matrix[0].length-1) {
            if(target == matrix[x][y]) {
                return true;
            }else if(target > matrix[x][y]) {
                y++;
            }else{
                x--;
            }
        }
        return false;
    }
}

旋转数组的最小数字

class Solution {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length-1;
        int min = Integer.MAX_VALUE;
        // 313  3456111
        //num[mid] > num[right]     min 在 右侧  [mid + 1, right]    left = mid + 1.   
        //num[mid] < num[right]     min 在 左侧  [left, mid]         right = mid
        //num[mid] == num[right] unknown. right--;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(numbers[mid] < numbers[right]) {
                right = mid;
            }else if(numbers[mid] > numbers[right]){
                left = mid+1;
            }else {
                right = right - 1;
            }
        }
        return numbers[left];
    }
}

矩阵中的路径

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[] word, int i, int j, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}

重建二叉树

class Solution {
    int[] preorder;
    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 recur(0, 0, preorder.length-1);
    }
    TreeNode recur(int pre_index, int in_left, int in_right){
        if(in_left > in_right) return null;
        int in_index = map.get(preorder[pre_index]);
        TreeNode node = new TreeNode(preorder[pre_index]);
        int left_length = in_index - in_left;
        node.left = recur(pre_index + 1, in_left, in_index-1);
        node.right = recur(pre_index + 1 + left_length, in_index+1, in_right);
        return node;
    }
}

机器人的运动范围

class Solution {
    public int count = 0;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        this.visited = visited;
        dfs(m, n, 0, 0, k);
        return count;
    }

    private void dfs(int m, int n, int i, int j, int k) {
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j]) {
            return;
        }
        if (sum(i) + sum(j) > k) {
            return;
        }
        visited[i][j] = true;
        count++;
        dfs(m, n, i + 1, j, k);
        dfs(m, n, i - 1, j, k);
        dfs(m, n, i, j + 1, k);
        dfs(m, n, i, j - 1, k);
    }

    private int sum(int m) {
        int n = 0;
        while (m != 0) {
            n = n + m % 10;
            m = m / 10;
        }
        return n;
    }
}

树的子结构

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

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

}

对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return is(root.left, root.right);
    }
    public boolean is(TreeNode n1, TreeNode n2){
        if(n1 == null && n2 == null) return true;
        if(n1 == null || n2 == null) return false;
        if(n1.val != n2.val) return false;
        return is(n1.left, n2.right) && is(n1.right, n2.left);
    }
}

二叉树镜像

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

        root.left = leftRoot;
        root.right = rightRoot;
        return root;
    }
}

割绳子

class Solution {
    public int cuttingRope(int n) {
        //dp[i]   len=i max = dp[i]
        //dp[2] = 1
        //dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
        int[] dp = new int[n+1];
        dp[2] = 1;
        dp[1] = 1;
        for(int i = 3; i < n+1; i++) {
            for(int j = 2; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

顺时针打印矩阵

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        //定义四个方向 lrud 确定范围以及走后对l r u d 的影响 注意停止标记
        if(matrix.length == 0) return new int[0];
        int[] res = new int[matrix.length *(matrix[0].length)];
        int k=0;
        int left = 0;
        int right = matrix[0].length-1;
        int up = 0;
        int down = matrix.length-1;
        while(true) {
            for(int i = left; i <= right; i++) res[k++] = matrix[up][i];
            if(++up > down) break;
            for(int i = up; i <= down; i++) res[k++] = matrix[i][right];
            if(--right < left) break;
            for(int i = right; i >= left; i--) res[k++] = matrix[down][i];
            if(--down < up) break;
            for(int i = down; i >= up; i--) res[k++] = matrix[i][left];
            if(++left > right) break;
        }
        return res;
    }
}

二进制中1的个数

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res = res + (n&1);
            n = n >>>1;
        }
        return res;
    }
}

public class Solution {
    public int hammingWeight(int n) {
        //n&(n-1) 将二进制数字中最右边的1变为0
        int res = 0;
        while(n != 0) {
            res++;
            n = n & (n - 1);
        }
        return res;
    }
}

数值的整数次方

class Solution {
    public double myPow(double x, int n) {
        if(n < 0) {
            x = 1/x;
            n = -n;
        }
        double temp = 1;
        for(int i = 0; i < n ; i++){
            temp = temp * x;
        }
        return temp;
    }
}
class Solution {
    // 11 ->      1011 
    //快速幂2e11 -> X2e3 * x2e1 * x2e1
    public double myPow(double x, int n) {
        if(x==0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1/x;
            b  = -b;
        }
        while(b > 0){
            if((b&1)==1) res = res * x;
            x = x*x;
            b = b >> 1;
        }
        return res;

    }
}

打印1到最大到N位数

//全排列 但是有多余的0
class Solution {
    StringBuilder res;
    int count = 0, n;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public String printNumbers(int n) {
        this.n = n;
        res = new StringBuilder(); // 数字字符串集
        num = new char[n]; // 定义长度为 n 的字符列表
        dfs(0); // 开启全排列递归
        res.deleteCharAt(res.length() - 1); // 删除最后多余的逗号
        return res.toString(); // 转化为字符串并返回
    }
    void dfs(int x) {
        if(x == n) { // 终止条件：已固定完所有位
            res.append(String.valueOf(num) + ","); // 拼接 num 并添加至 res 尾部，使用逗号隔开
            return;
        }
        for(char i : loop) { // 遍历 ‘0‘ - ’9‘
            num[x] = i; // 固定第 x 位为 i
            dfs(x + 1); // 开启固定第 x + 1 位
        }
    }
}
//String 表示
class Solution {
    StringBuilder res;
    int nine = 0, count = 0, start, n;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public String printNumbers(int n) {
        this.n = n;
        res = new StringBuilder();
        num = new char[n];
        start = n - 1;
        dfs(0);
        res.deleteCharAt(res.length() - 1);
        return res.toString();
    }
    void dfs(int x) {
        if(x == n) {
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) res.append(s + ",");
            if(n - start == nine) start--;
            return;
        }
        for(char i : loop) {
            if(i == '9') nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;
    }
}
//real
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];
        num = new char[n];
        start = n - 1;
        dfs(0);
        return res;
    }
    void dfs(int x) {
        if(x == n) {
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) res[count++] = Integer.parseInt(s);
            if(n - start == nine) start--;
            return;
        }
        for(char i : loop) {
            if(i == '9') nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;
    }
}

二叉树搜索树转链表

//中序遍历转链表
class Solution {
    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node cur) {
        if(cur == null) return;
        dfs(cur.left);
        if(pre != null) {
            pre.right = cur;
        } else {
            head = cur;
        }
        cur.left = pre; 
        pre = cur;
        dfs(cur.right);
    }
}

序列化二叉树

public class Codec {

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

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList();
        queue.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;
    }
}

数据流中的中位数

class MedianFinder {

    Queue<Integer> A;
    Queue<Integer> B;
    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue();                     //小顶堆  由大到小
        B = new PriorityQueue<>((o1, o2)-> (o2 - o1));  //大顶堆   由小到大
    }

    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }

    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

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

//多数的票数为+1 少数为-1
class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes = vote + num == x ? 1 : -1;
        }
        return x;
    }
}

数组序列中某一位数字

class Solution {
    public int findNthDigit(int n) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (n > count) { // 1.
            n -= count;
            digit += 1;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit; // 2.
        return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3.
    }
}
//  数学
//           数字范围   位数   数字数量   数位数量
//            1 - 9      1        9          9
//           10 - 99     2        90         180
//          100 - 999    3        900        2700
//             ...      ...       ...        ...
//        start - end   digit    9*start   9*start*dight

class Solution {
public:
    int findNthDigit(int n) {
        int digit = 1;    // 数位
        long start = 1;   // 当前数字范围的左区间
        long count = 9;   // 数位数量

        // 定位目标数字所在数字范围
        while (n > count) {
            n -= count;       // 减去上一个数字范围的总数位数量
            digit += 1;       // "当前数字范围的"数位
            start *= 10;      // "当前数字范围的"左区间
            count = 9 * start * digit;   // "当前数字范围的"总数位数量
        }
        int num = (start - 1) + n / digit;   // 注："start-1"表示上一个数字范围的右区间
        int y = n % digit;                   
        // 如果"余数y"不为0，说明目标数字为 num+1
        if (y) {    
            num += 1;
            string s = std::to_string(num);  
            return s[y - 1] - '0';
        }
        //否则，第n位数即"数字num的个位"
        return num % 10;
    }
};

1-n 中1的个数

class Solution {
    public int countDigitOne(int n) {
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
            mulk *= 10;
        }
        return ans;
    }
}

二叉树的后序遍历

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

//单调栈
//逆序的后序序列等效先序遍历
//单调栈维护二叉搜索树的右子树 因为大，出栈更新当前子树跟节点
//相当于root是一个MAXroot的左子树
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> stack = new LinkedList();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(postorder[i] > root) return false;
            while(!stack.isEmpty() && stack.peek() > postorder[i]){
                root = stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}

数组中的逆序对

class Solution {
    int count = 0;
    int[] aux;
    public int reversePairs(int[] nums) {
        aux = new int[nums.length];
        sort(nums, 0, nums.length - 1);
        return count;
    }

    public void sort(int[] nums, int lo, int hi){
        if(hi <= lo)    return;

        int mid = (lo + hi) / 2;
        sort(nums, lo, mid);
        sort(nums, mid + 1, hi);

        merge(nums, lo, mid, hi);
    }

    private void merge(int[] nums, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        for(int k = lo; k <= hi; k++)
            aux[k] = nums[k];

        int index = lo;
        while(i <= mid || j <= hi){
            if(i > mid)                 nums[index++] = aux[j++];
            else if(j > hi)             nums[index++] = aux[i++];
            else if(aux[i] <= aux[j])   nums[index++] = aux[i++];
            else                        {nums[index++] = aux[j++];  count += mid - i + 1;}
        }
    }
}

把数字翻译成字符串

//回溯法
class Solution {
    int count = 0;
    int[] nums;
    public int translateNum(int num) {
        String str = String.valueOf(num);
        int[] nums = new int[str.length()];
        for(int i=0; i < str.length(); i++){
            nums[i]=Integer.parseInt(String.valueOf(str.charAt(i)));
        }
        this.nums = nums;
        back(0);
        return count;
    }
    public void back(int i) {
        if(i >= nums.length-1) {
            count++;
            return;
        }
        if(nums[i] <= 2 && i + 1 < nums.length ){
            if(nums[i] == 1||(nums[i]==2 && nums[i+1] <= 5)){
                back(i+2);
            }
        }
        back(i+1);
    }
}
//dp
class Solution {
    public int translateNum(int num) {
        if(num < 10) return 1;
        char[] chars = String.valueOf(num).toCharArray();
        int[] dp = new int[chars.length];

        dp[0] = 1; // 第一个格子只存在跳一格
        // 判断到第二格能否以跳两格的形式
        dp[1] = chars[0]-'0'==1 || (chars[0]-'0'==2 && chars[1]-'0'<6) ? 2 : 1; 

        for(int i = 2; i < dp.length; i++){
            int temp = chars[i-1] - '0';
            dp[i] = temp == 1 || (temp == 2 && chars[i]-'0'<6) ?  // 满足 >=10 <=25 即可跳两格
                        dp[i-1]+dp[i-2] : dp[i-1];
        }
        return dp[chars.length - 1];
    }
}

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;
        for(int i = 2; i <= s.length(); i++) {
            String tmp = s.substring(i - 2, i);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
}

和为s的连续正序数列

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList();
        int i = 1;
        int j = 2;
        int count = 3;
        while(i < j) {
            if(count == target) {
                int[] t = new int[j-i+1];
                for(int k = i; k <= j; k++){
                    t[k-i] = k;
                }
                res.add(t);
            }
            if(count < target){
                j++;
                count = count + j;
            }else{
                count = count - i;
                i++;
            }
        }
        return res.toArray(new int[0][]);
    }
}

数组中数字出现的次数

//2个
class Solution {
    public int[] singleNumbers(int[] nums) {
        int res = 0;
        int m = 1;
        int x = 0;
        int y = 0;
        for(int i : nums){
            res = res ^ i;
        }
        while((res&m) == 0) {
            m = m << 1;
        }
        for(int i : nums){
            if((i&m) == 0) {
                x = x ^ i;
            }else {
                y = y ^ i;
            }
        }
        return new int[]{x,y};
    }
}
//3个
//统计二进制每位的位数 有+1。则最后可以被3整除
class Solution {
    public int singleNumber(int[] nums) {
        int[] k = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                k[i] = k[i] +(num & 1);
                num = num >> 1;
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int temp = (k[i] % 3) << i;
            res = res ^ temp;
        }
        return res;
    }
}

把数组排成最小的数

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]);
        }
        Arrays.sort(strs, (x, y)-> (x+y).compareTo(y+x));
        StringBuilder res = new StringBuilder();
        for(String s: strs){
            res.append(s);
        }
        return res.toString();
    }
}

丑数

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
        }
        return dp[n - 1];
    }
}

在排序数组中查找数字I

//统计一个数字在排序数组中出现的次数
//输入: nums = [5,7,7,8,8,10], target = 8
//输出: 2
class Solution {
    public int search(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }
    int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= tar) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

0-n-1中缺失的数字

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0;
        int j = nums.length-1;
        while(i <= j){
            int mid = (i+j)/2;
            if(nums[mid] != mid) {
                j = mid-1;
            }else{
                i = mid+1;
            }
        }
        return i;
    }
}

不用加减乘除做加法

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

圆圈中的最后一位数字

class Solution {
    public int lastRemaining(int n, int m) {
        //当只剩一个人时其下标必为0，从此反推即可
        //补上m个位置，然后模上当时的数组大小，得到其在此轮的下标位置
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }
}

股票的最大利润

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

扑克牌中的顺子

class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> repeat = 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(repeat.contains(num)) return false; // 若有重复，提前返回 false
            repeat.add(num); // 添加此牌至 Set
        }
        return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

滑动窗口的最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //单调队列
        //下面是要注意的点：
        //队列按从大到小放入
        //如果首位值（即最大值）不在窗口区间，删除首位
        //如果新增的值小于队列尾部值，加到队列尾部
        //如果新增值大于队列尾部值，删除队列中比新增值小的值，如果在把新增值加入到队列中
        //如果新增值大于队列中所有值，删除所有，然后把新增值放到队列首位，保证队列一直是从大到小
        if (nums.length == 0)   return nums;

        Deque<Integer> deque = new LinkedList<>();
        int[] arr = new int[nums.length - k + 1];
        int index = 0;  //arr数组的下标
        //未形成窗口区间
        for (int i = 0; i < k; i++) {
            //队列不为空时，当前值与队列尾部值比较，如果大于，删除队列尾部值
            //一直循环删除到队列中的值都大于当前值，或者删到队列为空
            while (!deque.isEmpty() && nums[i] > deque.peekLast())  deque.removeLast();
            //执行完上面的循环后，队列中要么为空，要么值都比当前值大，然后就把当前值添加到队列中
            deque.addLast(nums[i]);
        }
        //窗口区间刚形成后，把队列首位值添加到队列中
        //因为窗口形成后，就需要把队列首位添加到数组中，而下面的循环是直接跳过这一步的，所以需要我们直接添加
        arr[index++] = deque.peekFirst();
        //窗口区间形成
        for (int i = k; i < nums.length; i++) {
            //i-k是已经在区间外了，如果首位等于nums[i-k]，那么说明此时首位值已经不再区间内了，需要删除
            if (deque.peekFirst() == nums[i - k])   deque.removeFirst();
            //删除队列中比当前值大的值
            while (!deque.isEmpty() && nums[i] > deque.peekLast())  deque.removeLast();
            //把当前值添加到队列中
            deque.addLast(nums[i]);
            //把队列的首位值添加到arr数组中
            arr[index++] = deque.peekFirst();
        }
        return arr;
    }
}

队列的最大值

class MaxQueue {
    Deque<Integer> q1;
    Deque<Integer> q2;
    public MaxQueue() {
        q1 = new LinkedList();
        q2 = new LinkedList();
    }
    public int max_value() {
        if(q2.isEmpty()) {
            return -1;
        }
        return q2.peekFirst();
    }
    public void push_back(int value) {
        while(!q2.isEmpty() && value > q2.peekLast()){
            q2.removeLast();
        }
        q1.addLast(value);
        q2.addLast(value);
    }

    public int pop_front() {
        if(q1.isEmpty()) {
            return -1;
        }
        if(q1.peekFirst().equals(q2.peekFirst())) {
            q2.removeFirst();
        }
        return q1.removeFirst();
    }
}

n个骰子的点数

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

//2
public double[] dicesProbability(int n) {
        double res[] = new double[n*5+1];
        double dp[][] = new double[n+1][n*6+1];
        for(int i = 1;i <= 6;i++){
            dp[1][i] = 1.0/6;
        }
        for(int i = 2;i <= n;i++){
            for(int j = i;j <= i*6;j++){
                for(int k = 1;k <= 6;k++){
                    if(j-k > 0)
                        dp[i][j] += dp[i-1][j-k]/6;
                    else
                        break;
                }
            }
        }
        for(int i = 0;i <= 5*n;i++){
            res[i] = dp[n][n+i];
        }
        return res;
}
//1-1
public double[] dicesProbability(int n) {
        //因为最后的结果只与前一个动态转移数组有关，所以这里只需要设置一个一维的动态转移数组
        //原本dp[i][j]表示的是前i个骰子的点数之和为j的概率，现在只需要最后的状态的数组，所以就只用一个一维数组dp[j]表示n个骰子下每个结果的概率。
        //初始是1个骰子情况下的点数之和情况，就只有6个结果，所以用dp的初始化的size是6个
        double[] dp = new double[6];
        //只有一个数组
        Arrays.fill(dp,1.0/6.0);
        //从第2个骰子开始，这里n表示n个骰子，先从第二个的情况算起，然后再逐步求3个、4个···n个的情况
        //i表示当总共i个骰子时的结果
        for(int i=2;i<=n;i++){
        //每次的点数之和范围会有点变化，点数之和的值最大是i*6，最小是i*1，i之前的结果值是不会出现的；
        //比如i=3个骰子时，最小就是3了，不可能是2和1，所以点数之和的值的个数是6*i-(i-1)，化简：5*i+1
            //当有i个骰子时的点数之和的值数组先假定是temp
            double[] temp = new double[5*i+1];
            //从i-1个骰子的点数之和的值数组入手，计算i个骰子的点数之和数组的值
            //先拿i-1个骰子的点数之和数组的第j个值，它所影响的是i个骰子时的temp[j+k]的值
            for(int j=0;j<dp.length;j++){
            //比如只有1个骰子时，dp[1]是代表当骰子点数之和为2时的概率，它会对当有2个骰子时的点数之和为3、4、5、6、7、8产生影响，因为当有一个骰子的值为2时，另一个骰子的值可以为1~6，产生的点数之和相应的就是3~8；比如dp[2]代表点数之和为3，它会对有2个骰子时的点数之和为4、5、6、7、8、9产生影响；所以k在这里就是对应着第i个骰子出现时可能出现六种情况，这里可能画一个K神那样的动态规划逆推的图就好理解很多
                for(int k=0;k<6;k++){
                    //这里记得是加上dp数组值与1/6的乘积，1/6是第i个骰子投出某个值的概率
                    temp[j+k]+=dp[j]*(1.0/6.0);
                }
            }
            //i个骰子的点数之和全都算出来后，要将temp数组移交给dp数组，dp数组就会代表i个骰子时的可能出现的点数之和的概率；用于计算i+1个骰子时的点数之和的概率
            dp = temp;
        }
        return dp;
    }

构建乘积数组

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

class Solution {
    public int[] constructArr(int[] a) {
        //记录左右前缀和 相乘
        if (a == null || a.length == 0) return a;
        int len = a.length;
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = right[len - 1] = 1;

        for (int i = 1; i < len; i++) {
            left[i] = left[i - 1] * a[i - 1];
        }
        for (int i = len - 2; i >= 0; i--) {
            right[i] = right[i + 1] * a[i + 1];
        }

        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }
}

剑指offer

代码

两个栈实现一个队列

斐波那契数列

数组中重复的数字

二维数组中的查找

旋转数组的最小数字

矩阵中的路径

重建二叉树

机器人的运动范围

树的子结构

对称二叉树

二叉树镜像

割绳子

顺时针打印矩阵

二进制中1的个数

打印1到最大到N位数

二叉树搜索树转链表

序列化二叉树

数据流中的中位数

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

数组序列中某一位数字

1-n 中1的个数

二叉树的后序遍历

数组中的逆序对

把数字翻译成字符串

和为s的连续正序数列

数组中数字出现的次数

把数组排成最小的数

丑数

在排序数组中查找数字I

0-n-1中缺失的数字

不用加减乘除做加法

圆圈中的最后一位数字

股票的最大利润

扑克牌中的顺子

滑动窗口的最大值

队列的最大值

n个骰子的点数

构建乘积数组