03. 数组中重复的数字

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> hashSet = new HashSet<>();
        for (int n : nums) {
            if (!hashSet.add(n)) return n;
        }
        return -1;
    }
}

04. 二维数组中的查找

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

05. 替换空格

class Solution {
    public String replaceSpace(String s) {
        int len = s.length();
        char[] chars = new char[len * 3];
        int j = 0;
        for (int i = 0; i < len; ++i) {
            char c = s.charAt(i);
            if (c == ' ')  {
                chars[j++] = '%';
                chars[j++] = '2';
                chars[j++] = '0';
            } else chars[j++] = c;
        }
        return new String(chars, 0, j);
    }
}

06. 从尾到头打印链表

class Solution {
    public int[] reversePrint(ListNode head) {
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode root = head;
        while (root != null) {
            stack.push(root);
            root = root.next;
        }

        int size = stack.size();
        int[] ans = new int[size];
        for (int i = 0; i < size; ++i) {
            ans[i] = stack.pop().val;
        }
        return ans;
    }
}

07. 重建二叉树

递归 & 分治

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; ++i) {
            hashMap.put(inorder[i], i);
        }
        return recur(0, 0, preorder.length - 1); 
    }
    //root为preorder中开始坐标
    //start end 为 inorder中的坐标
    public TreeNode recur (int root, int start, int end) {
        if (start > end) return null;
        //创建节点
        TreeNode node = new TreeNode(preorder[root]);
        //递归
        int idx = hashMap.get(preorder[root]);
        node.left = recur(root + 1, start, idx - 1);
        node.right = recur(root + 1 + idx - start, idx + 1, end);
        return node;
    }
}

09. 用两个栈实现队列

class CQueue {
    Deque<Integer> A;
    Deque<Integer> B;

    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();
    }

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

    public int deleteHead() {  
        if (!B.isEmpty()) return B.pop();
        if (A.isEmpty()) return -1;
        while (!A.isEmpty()) {
            B.push(A.pop());
        }
        return B.pop();
    }
}

10-I. 斐波那契数列

动态规划

class Solution {
    public int fib(int n) {
        if (n == 0) return 0;
        int r = 0; int l = 1;
        for (int i = 2; i <= n; ++ i) {
            int tmp = l;
            l = (l + r) % 1000000007;
            r = tmp;
        }
        return l;
    }
}

11. 旋转数组的最小数字

二分法

class Solution {
    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length - 1;

        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (numbers[mid] < numbers[right]) {
                right = mid;
            }
            else if (numbers[mid] > numbers[right]) {
                left = mid + 1;
            }
            else {
                right--;
            }
        }
        return numbers[left];
    }
}

12. 矩阵中的路径

DFS

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                if (dfs(board, i, j, word, 0)) return true;
            }
        }
        return false;
    }

    public static boolean dfs (char[][] board, int i, int j, String word, int idx) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(idx)) {
            return false;
        }
        if (idx == word.length() - 1) return true;
        board[i][j] = ' ';
        boolean res = dfs(board, i + 1, j, word, idx + 1) || dfs(board, i - 1, j, word, idx + 1) || 
                        dfs(board, i, j + 1, word, idx + 1) || dfs(board, i, j - 1, word, idx + 1);
        board[i][j] = word.charAt(idx);
        return res;
    }
}

13. 机器人的运动范围

DFS

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

    public static int dfs (int i, int j, int m, int n, int k, boolean[][] visited) {
        if (i >= m || j >= n || visited[i][j] || (sumDigits(i) + sumDigits(j)) > k) {
            return 0;
        }
        visited[i][j] = true;
        return  1 + dfs(i + 1, j, m, n, k,visited) + dfs(i, j + 1, m, n, k,visited);
    }

    public static int sumDigits (int num) {
        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

14-I. 剪绳子

数学

class Solution {
    public int cuttingRope(int n) {
        // 将绳子 以相等的长度等分为多段 ,得到的乘积最大。
        // 尽可能将绳子以长度 3 等分为多段时,乘积最大。
        // 为使乘积最大,只有长度为 2 和 3 的绳子不应再切分,且 3 比 2 更优
        if (n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if (b == 0) return (int)Math.pow(3, a);
        else if (b == 1) return (int)Math.pow(3, a - 1) * 4;
        else return (int)Math.pow(3, a) * 2;
    }
}

14-II. 剪绳子II

贪心

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        long ans = 1;
        while (n > 4) {
            ans = ans * 3 % 1000000007;
            n -= 3;
        }
        return (int)(ans * n % 1000000007);
    }
}

15. 二进制中1的个数

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

16. 数值的整数次方

class Solution {
    public double myPow(double x, int n) {
        if (x == 0) return 0;
        double ans = 1.0;
        //Java 代码中 int32 变量 n∈[−2147483648,2147483647] ,因此当 n = -2147483648 时执行 n = -n会因越界而赋值出错。
        //因此需将值传给long型变量
        long b = (long) n; 

        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        while (b != 0) {
            if ((b & 1) == 1) ans *= x;
            x *= x;
            b >>= 1; 
        }
        return ans;
    }
}

17. 打印从1到最大的n位数

考虑大数问题

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 位
        }
    }
}

去除多余的'0'

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--;
    }
}

19. 正则表达式匹配🌟

  • dp[i][j] 代表 s 的前 i 个和 p 的前 j 个能否匹配:
    1. 对于前面两个情况,可以合并成一种情况 dp[i][j] = dp[i-1][j-1]
    2. 对于第三种情况,对于 c* 分为看和不看两种情况
      • 不看:直接砍掉正则串的后面两个, dp[i][j] = dp[i][j-2]
      • 看:正则串不动,主串前移一个,dp[i][j] = dp[i-1][j]

动态规划

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        //dp[i][j] 代表 s 的前 i 个和 p 的前 j 个能否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
         for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2]; //当p中有*时长度必不小于2
                    if (isEqual(s, p, i, j - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
                else if (isEqual(s, p, i, j)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    public static boolean isEqual (String s, String p, int i, int j) {
        if (i == 0) return false;
        if (p.charAt(j - 1) == '.') return true;
        return s.charAt(i - 1) == p.charAt(j - 1); 
    }
}

20. 表示数值的字符串🌟

状态机

class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {{ put('d', 3); }},                                        // 4.
            new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {{ put('d', 7); }},                                        // 6.
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {{ put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char 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 = '?';
            if (!states[p].containsKey(t)) return false;
            p = (int) states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

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

class Solution {
    public int[] exchange(int[] nums) {
        for (int i = 0, j = 0; j < nums.length; ++j) {
            if (nums[j] % 2 == 0) continue;
            int tmp = nums[i];
            nums[i++] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}

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

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        for (int i = 0; i < k; ++i) {
            if (fast == null) return null;
            fast = fast.next;
        }
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

24. 反转链表

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

25. 合并两个排序的链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode();
        ListNode p = ret;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2 : l1;
        return ret.next;
    }
}

Try and fail, but don't fail to try.