LeetCode题解

455. 分发饼干

leetcode链接

完成日期：2022/12/19

分类：贪心

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int cnt = 0;
        for (int i = g.length - 1; i >= 0 && s.length - cnt - 1 >= 0; i--) {
            if (g[i] <= s[s.length - cnt - 1]) {
                cnt++;
            }
        }
        return cnt;
    }
}

112. 路径总和

leetcode链接

完成日期：2022/12/19

分类：二叉树

class Solution {
    private boolean isExist = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        pre(root, root.val, targetSum);
        return isExist;
    }
    private void pre(TreeNode root, int sum, int targetSum) {
        if (root.left == null && root.right == null) {
            if (sum == targetSum) {
                isExist = true;
            }
            return;
        }
        if (root.left != null) {
            pre(root.left, sum + root.left.val, targetSum);
        }
        if (root.right != null) {
            pre(root.right, sum + root.right.val, targetSum);
        }
    }
}

513. 找树左下角的值

leetcode链接

完成日期：2022/12/19

分类：二叉树

class Solution {
    int depth = 0;
    int value = -1;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        pre(root, 0);
        return value;
    }
    private void pre(TreeNode root, int currentDepth) {
        if (root.left == null && root.right == null) {
            if (currentDepth > depth) {
                depth = currentDepth;
                value = root.val;
            }
            return;
        }
        if (root.left != null) {
            pre(root.left, currentDepth + 1);
        }
        if (root.right != null) {
            pre(root.right, currentDepth + 1);
        }
    } 
}

111. 二叉树的最小深度

leetcode链接

完成日期：2022/12/19

分类：二叉树

class Solution {
    int minDepth = 999999;
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        pre(root, 1);
        return minDepth;
    }
    private void pre(TreeNode root, int depth) {
        if (root.left == null && root.right == null) {
            if (depth < minDepth) {
                minDepth = depth;
            }
            return;
        }
        if (root.left != null) {
            pre(root.left, depth + 1);
        }
        if (root.right != null) {
            pre(root.right, depth + 1);
        }
    }
}

104. 二叉树的最大深度

leetcode链接

完成日期：2022/12/19

分类：二叉树

class Solution {
    int maxDepth = -1;
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        pre(root, 1);
        return maxDepth;
    }
    private void pre(TreeNode root, int depth) {
        if (root.left == null && root.right == null) {
            if (depth > maxDepth) {
                maxDepth = depth;
            }
            return;
        }
        if (root.left != null) {
            pre(root.left, depth + 1);
        }
        if (root.right != null) {
            pre(root.right, depth + 1);
        }
    }
}

226. 翻转二叉树

leetcode链接

完成日期：2022/12/20

分类：二叉树

class Solution {
    private TreeNode reverseRoot = new TreeNode();
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        reverse(root, reverseRoot);
        return reverseRoot;
    }
    private void reverse(TreeNode root, TreeNode newNode) {
        newNode.val = root.val;
        if (root.left != null) {
            newNode.right = new TreeNode();
            reverse(root.left, newNode.right);
        }
        if (root.right != null) {
            newNode.left = new TreeNode();
            reverse(root.right, newNode.left);
        }
    }
}

101. 对称二叉树

leetcode链接

完成日期：2022/12/20

分类：二叉树

class Solution {
    ArrayList<Integer> arr1 = new ArrayList<>();
    ArrayList<Integer> arr2 = new ArrayList<>();
    public boolean isSymmetric(TreeNode root) {
        pre(root);
        reverserPre(root);
        return arr1.equals(arr2);
    }
    private void pre(TreeNode root) {
        if (root == null) {
            arr1.add(null);
            return;
        }
        arr1.add(root.val);
        pre(root.left);
        pre(root.right);
    }
    private void reverserPre(TreeNode root) {
        if (root == null) {
            arr2.add(null);
            return;
        }
        arr2.add(root.val);
        reverserPre(root.right);
        reverserPre(root.left);
    }
}

222. 完全二叉树的节点个数

leetcode链接

完成日期：2022/12/20

分类：二叉树

class Solution {
    private Integer count = 0;
    public int countNodes(TreeNode root) {
        pre(root);
        return count;
    }
    private void pre(TreeNode root) {
        if (root == null) {
            return;
        }
        count++;
        pre(root.left);
        pre(root.right);
    }
}

110. 平衡二叉树

leetcode链接

完成日期：2022/12/20

分类：二叉树

class Solution {
    private boolean balanced = true;
    public boolean isBalanced(TreeNode root) {
        pre(root);
        return balanced;
    }
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return left > right ? left + 1: right + 1;
    }
    private void pre(TreeNode root) {
        if (root == null) {
            return;
        }
        int subHeight = Math.abs(getHeight(root.left) - getHeight(root.right));
        if (subHeight > 1) {
            balanced = false;
        }
        pre(root.left);
        pre(root.right);
    }
}

404. 左叶子之和

leetcode链接

完成日期：2022/12/20

分类：二叉树

class Solution {
    private int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return sum;
        }
        pre(root, 0);
        return sum;
    }
    private void pre(TreeNode root, int flag) {
        if (root.left == null && root.right == null) {
            if (flag == -1) {
                sum += root.val;
            }
            return;
        }
        if (root.left != null) {
            pre(root.left, -1);
        }
        if (root.right != null) {
            pre(root.right, 1);
        }
    }
}

509. 斐波那契数

509. 斐波那契数 - 力扣（Leetcode）

完成日期：2022/12/22

分类：动态规划

class Solution {
    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
       return dp[n];
    }
}

70. 爬楼梯

70. 爬楼梯 - 力扣（Leetcode）

完成日期：2022/12/22

分类：动态规划

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        if (n == 1) {
            return dp[1];
        }
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
}

746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（Leetcode）

完成日期：2022/12/23

分类：动态规划

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}

349 两个数组的交集

349. 两个数组的交集 - 力扣（Leetcode）

完成日期：2022/12/23

分类：哈希表

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        for (int num : nums1) {
            set1.add(num);
        }
        for (int num : nums2) {
            set2.add(num);
        }
        HashSet<Integer> intersectSet = new HashSet<>();
        for (int num : set1) {
            if (set2.contains(num)) {
                intersectSet.add(num);
            }
        }
        return intersectSet.stream().mapToInt(i -> i).toArray();
    }
}

202 快乐数

202. 快乐数 - 力扣（Leetcode）

完成日期：2022/12/23

分类：哈希表

class Solution {
    HashSet<Integer> hashSet = new HashSet<>();
    public boolean isHappy(int n) {
        while (n != 1) {
            n = compute(n);
            if (hashSet.contains(n)) {
                return false;
            } else {
                hashSet.add(n);
            }
        }
        return true;
    }
    private int compute(int num) {
        int sum = 0;
        do {
            sum += Math.pow(num % 10, 2); 
            num /= 10;
        } while (num > 0);
        return sum;
    }
}

剑指 Offer 05. 替换空格

剑指 Offer 05. 替换空格 - 力扣（Leetcode）

完成日期：2022/12/23

class Solution {
    public String replaceSpace(String s) {
        return s.replaceAll(" ", "%20");
    }
}

77. 组合

77. 组合 - 力扣（Leetcode）

完成日期：2022/12/23

class Solution {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
    private void backtracking(int n, int k, int beginIndex) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = beginIndex; i <= n; i++) {
            path.add(i);
            backtracking(n, k, i + 1);
            path.removeLast();
        }
    }
}

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

题目链接：剑指 Offer 09. 用两个栈实现队列 - 力扣（Leetcode）

完成日期：2023/1/4

class CQueue {
    Stack<Integer> inStack;
    Stack<Integer> outStack;
    public CQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }
    
    public void appendTail(int value) {
        inStack.push(value);
    }
    
    public int deleteHead() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        if (outStack.isEmpty()) {
            return -1;
        }
        return outStack.pop();
    }
}

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

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

完成日期：2023/1/4

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

2. 两数相加

题目链接：https://leetcode.cn/problems/add-two-numbers/description

完成时间：2023/1/4

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode tail = null;
        ListNode head = null;
        int flag = 0;
        while (l1 != null && l2 != null) {
            int result = l1.val + l2.val + flag;
            flag = 0;
            if (result > 9) {
                result -= 10;
                flag = 1;
            }
            ListNode node = new ListNode(result);
            if (head == null) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                tail = tail.next;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        if (l1 == null && l2 == null) {
            if (flag == 1) {
                tail.next = new ListNode(flag);
            }
        } else if (l1 == null) {
            while (l2 != null) {
                int result = l2.val + flag;
                flag = 0;
                if (result > 9) {
                    result -= 10;
                    flag = 1;
                }
                ListNode node = new ListNode(result);    
                tail.next = new ListNode(result);
                tail = tail.next;            
                l2 = l2.next;
            }
        } else if (l2 == null) {
            while (l1 != null) {
                int result = l1.val + flag;
                flag = 0;
                if (result > 9) {
                    result -= 10;
                    flag = 1;
                }
                ListNode node = new ListNode(result);    
                tail.next = new ListNode(result);
                tail = tail.next;            
                l1 = l1.next;
            }
        }
        if (flag == 1) {
            tail.next = new ListNode(1);
        }
        return head;
    }
}

118. 杨辉三角

题目链接：https://leetcode.cn/problems/pascals-triangle/description

完成时间：2022/1/4

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>(); 
        for (int i = 1; i <= numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                if (j == 0 || j == i - 1) {
                    row.add(1);
                } else {
                    row.add(ans.get(i - 2).get(j - 1) + ans.get(i - 2).get(j));
                }
            }
            ans.add(row);
        }
        return ans;
    }
}

69. x 的平方根

题目链接：https://leetcode.cn/problems/sqrtx/description

完成时间：2023/1/4

class Solution {
    public int mySqrt(int x) {
        long i;
        for (i = 0; i * i <= (long)x; i++) {}
        return (int)(i - 1); 
    }
}

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

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

完成时间：2023/1/5

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private Stack<Integer> stack = new Stack<>();
    public int[] reversePrint(ListNode head) {
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int[] result = new int[stack.size()];
        int pos = 0;
        while (!stack.isEmpty()) {
            result[pos++] = stack.pop();
        }
        return result;
    }
}

剑指 Offer 24. 反转链表

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

完成日期：2023/1/5

/**
 * 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 newHead = null;
        while (head != null) {
            ListNode node = new ListNode(head.val);
            if (head == null) {
                newHead = node;
            } else {
                node.next = newHead;
                newHead = node; 
            }
            head = head.next;
        }
        return newHead;
    }
}

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

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

完成日期：2023/1/5

/*
// 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) {
        HashMap<Node, Node> map1 = new HashMap<>();
        HashMap<Node, Node> map2 = new HashMap<>();
        Node newHead = null;
        Node tail = null;
        Node p = head;
        while (p != null) {
            Node node = new Node(p.val);
            Node randomNode = p.random;
            map1.put(node, randomNode);
            if (newHead == null) {
                newHead = node;
            } else {
                tail.next = node;
            }
            map2.put(p, node);
            tail = node;
            p = p.next;
        }
        p = head;
        tail = newHead;
        while (p != null && tail != null) {
            Node randomNode = p.random;
            tail.random = map2.get(map1.get(tail));
            tail = tail.next;
            p = p.next;
        }
        return newHead;
    }
}

141. 环形链表

题目链接：https://leetcode.cn/problems/linked-list-cycle/description

完成日期：2023/1/5

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }
}

剑指 Offer 05. 替换空格

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

完成时间：2023/1/6

class Solution {
    public String replaceSpace(String s) {
        StringBuilder str = new StringBuilder(s);
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                str.replace(i, i + 1, "%20");
            }
        }
        return str.toString();
    }
}

剑指 Offer 58 - II. 左旋转字符串

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

完成时间：2023/1/6

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder str = new StringBuilder(s);
        String subStr = s.substring(0, n);
        str.delete(0, n);
        str.append(subStr);
        return str.toString();
    }
}

62. 不同路径

题目链接：https://leetcode.cn/problems/unique-paths

完成日期：2023/1/6

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        } 
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

63. 不同路径II

题目链接：https://leetcode.cn/problems/unique-paths-ii

完成日期：2023/1/6

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;            
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

96. 不同的二叉搜索树

题目链接：https://leetcode.cn/problems/unique-binary-search-trees

完成日期：2023/1/6

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

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

题目链接：https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/description

完成日期：2023/1/7

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return num;
            }
            set.add(num);
        }
        return 0;
    }
}

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

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

完成日期：2023/1/7

class Solution {
    public int search(int[] nums, int target) {
        int count = 0;
        for (int num : nums) {
            if (num == target) {
                count++;
            }
        }
        return count;
    }
}

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

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

完成日期：2023/1/7

class Solution {
    public int missingNumber(int[] nums) {
        int count = 0;
        for (int num : nums) {
            if (num != count++) {
                return count - 1;
            }
        }
        return count;
    }
}

98. 验证二叉搜索树

题目链接：98. 验证二叉搜索树 - 力扣（Leetcode）

完成日期：2023/1/7

/**
 * 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<Integer> order = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        if (root != null) {
            in(root);
        }
        int pre = order.get(0);
        for (int i = 0; i < order.size(); i++) {
            if (i != 0) {
                if (pre >= order.get(i)) {
                    return false;
                }
                pre = order.get(i);
            }
        }
        return true;
    }
    private void in(TreeNode root) {
        if (root == null) {
            return;
        }
        in(root.left);
        order.add(root.val);
        in(root.right);
    }
}

103. 二叉树的锯齿形层序遍历

题目链接：103. 二叉树的锯齿形层序遍历 - 力扣（Leetcode）

完成日期：2023/1/7

/**
 * 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>> result = new ArrayList<>();
    LinkedList<TreeNode> queue = new LinkedList<>();
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        int current = 0;
        int next = 0;
        boolean flag = false;
        if (root != null) {
            queue.offer(root);
            current = 1;
        }
        ArrayList<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode head = queue.remove();
            order.add(head.val);
            current--;
            if (head.left != null) {
                queue.add(head.left);
                next++;
            }
            if (head.right != null) {
                queue.add(head.right);
                next++;
            }
            if (current == 0) {
                if (flag) {
                    Collections.reverse(order);
                }
                flag = !flag;
                result.add(order);
                order = new ArrayList<>();
                current = next;
                next = 0;
            }
        }
        return result;
    }
}

107. 二叉树的层序遍历 II

107. 二叉树的层序遍历 II - 力扣（Leetcode）

完成日期：2023/1/7

/**
 * 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>> result = new ArrayList<>();
    LinkedList<TreeNode> queue = new LinkedList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        int current = 0;
        int next = 0;
        if (root != null) {
            queue.offer(root);
            current = 1;
        }
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode head = queue.poll();
            order.add(head.val);
            current--;
            if (head.left != null) {
                queue.offer(head.left);
                next++;
            }
            if (head.right != null) {
                queue.offer(head.right);
                next++;
            }
            if (current == 0) {
                result.add(order);
                order = new ArrayList<>();
                current = next;
                next = 0;
            }
        }
        Collections.reverse(result);
        return result;
    }
}

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

题目链接

完成日期：2023/1/8

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

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

题目链接

完成日期：2023/1/8

class Solution {
    public int minArray(int[] numbers) {
        Arrays.sort(numbers);
        return numbers[0];
    }
}

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

题目链接

完成日期：2023/1/8

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, 1);
            } else {
                map.put(c, map.get(c) + 1);
            }
        }
        Set<Character> set = map.keySet();
        for (Character c : set) {
            if (map.get(c) == 1) {
                return c;
            }
        }
        return ' ';
    }
}

55. 跳跃游戏

题目链接

完成日期：2023/1/8

class Solution {
    public boolean canJump(int[] nums) {
        int bound = nums.length - 1;
        if (bound == 0) {
            return true;
        }
        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(cover, nums[i] + i);
            if (cover >= bound) {
                return true;
            }
        }
        return false;
    }
}

215. 数组中的第K个最大元素

题目链接

完成日期：2023/1/8

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Integer[] newNums = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        List<Integer> list= Arrays.asList(newNums);
        list.sort((o1, o2) -> o2 - o1);
        return list.get(k - 1);
    }
}

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

题目链接

完成日期：2023/1/9

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private LinkedList<TreeNode> queue = new LinkedList<>(); 
    private ArrayList<Integer> list = new ArrayList<>();
    public int[] levelOrder(TreeNode root) {
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            TreeNode head = queue.poll();
            list.add(head.val);
            if (head.left != null) {
                queue.offer(head.left);   
            } 
            if (head.right != null) {
                queue.offer(head.right);
            }
        }
        Integer[] array = list.toArray(new Integer[list.size()]);
        return Arrays.stream(array).mapToInt(Integer::valueOf).toArray();
    }
}

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

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

完成日期：2023/1/9

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private LinkedList<TreeNode> queue = new LinkedList<>(); 
    private List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        int current = 0;
        int next = 0;
        if (root != null) {
            queue.offer(root);
            current = 1;
        }
        List<Integer> level = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode head = queue.poll();
            level.add(head.val);
            current--;
            if (head.left != null) {
                queue.offer(head.left);
                next++;   
            } 
            if (head.right != null) {
                queue.offer(head.right);
                next++;
            }
            if (current == 0) {
                ans.add(level);
                level = new ArrayList<>();
                current = next;
                next = 0;
            }
        }
        return ans;        
    }
}

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

题目链接

完成日期：2023/1/8

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private LinkedList<TreeNode> queue = new LinkedList<>(); 
    private List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        int current = 0;
        int next = 0;
        boolean flag = false;
        if (root != null) {
            queue.offer(root);
            current = 1;
        }
        List<Integer> level = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode head = queue.poll();
            level.add(head.val);
            current--;
            if (head.left != null) {
                queue.offer(head.left);
                next++;   
            } 
            if (head.right != null) {
                queue.offer(head.right);
                next++;
            }
            if (current == 0) {
                if (flag) {
                    Collections.reverse(level);
                }
                ans.add(level);
                level = new ArrayList<>();
                current = next;
                next = 0;
                flag = !flag;
            }
        }
        return ans;        
    }
}

216. 组合总和 III

[题目链接](216. 组合总和 III - 力扣（Leetcode）)

完成日期：2023/1/9

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    int num = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(1, k, n);
        return result;
    }
    private void backtracking(int startIndex, int k, int n) {
        if (path.size() > k || num > n) {
            return;
        }
        if (path.size() == k && num == n) {
            result.add(new LinkedList<>(path));
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            path.add(i);
            num += i;
            backtracking(i + 1, k, n);
            path.removeLast();
            num -= i;
        }
    }
}

剑指 Offer 26. 树的子结构

题目链接

完成日期：2023/1/10

/**
 * 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;
        }
        if (isSame(A, B)) {
            return true;
        }
        if (isSubStructure(A.left, B)) {
            return true;
        }
        if (isSubStructure(A.right, B)) {
            return true;
        }
        return false;
    }   
    boolean isSame(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null || A.val != B.val) {
            return false;
        }
        return isSame(A.left, B.left) && isSame(A.right, B.right);
    }
}

剑指 Offer 27. 二叉树的镜像

题目链接

完成日期：2023/1/10

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode mRoot = null;
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        mRoot = new TreeNode();
        pre(root, mRoot);
        return mRoot;
    }
    void pre(TreeNode root, TreeNode mRoot) {
        mRoot.val = root.val;
        if (root.left != null) {
            mRoot.right = new TreeNode(root.left.val);
            pre(root.left, mRoot.right);
        }
        if (root.right != null) {
            mRoot.left = new TreeNode(root.right.val);
            pre(root.right, mRoot.left);
        }
    }
}

剑指 Offer 28. 对称的二叉树

题目链接

完成日期：2023/1/10

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    ArrayList<Integer> list1 = new ArrayList<>();
    ArrayList<Integer> list2 = new ArrayList<>();
    public boolean isSymmetric(TreeNode root) {
        pre(root);
        symmetricPre(root);
        return list1.equals(list2);
    }
    void pre(TreeNode root) {
        if (root == null) {
            list1.add(null);
            return;
        }
        list1.add(root.val);
        pre(root.left);
        pre(root.right);
    }   
    void symmetricPre(TreeNode root) {
        if (root == null) {
            list2.add(null);
            return;
        }
        list2.add(root.val);
        symmetricPre(root.right);
        symmetricPre(root.left);
    }
}

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

题目链接

完成日期：2023/1/11

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] % 1000000007 + dp[i - 2] % 1000000007) % 1000000007;
        }
        return dp[n];
    }
}

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

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

完成日期：2023/1/11

class Solution {
    public int numWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] % 1000000007 + dp[i - 2] % 1000000007) % 1000000007;
        }
        return dp[n];
    }
}

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

题目链接

完成日期：2023/1/11

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[len];
        dp[0] = 0;
        int min = prices[0];
        for (int i = 1; i < len; i++) {
            if (min > prices[i]) {
                min = prices[i];
            }
            dp[i] = Math.max(dp[i - 1], prices[i] - min);
        }
        return dp[len - 1];
    }
}

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

题目链接

完成日期：2023/1/13

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

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

题目链接

完成日期：2023/1/12

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

78. 子集

78. 子集 - 力扣（Leetcode）

完成日期：2023/1/1

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        result.add(new LinkedList<>());
        backtracking(0, nums);
        return result;
    }
    private void backtracking(int startIndex, int[] nums) {
        if (startIndex == nums.length) {
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            result.add(new LinkedList(path));
            backtracking(i + 1, nums);
            path.removeLast();
        }
    }
}

150. 逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（Leetcode）

完成日期：2023/1/12

class Solution {
    Stack<Integer> nums = new Stack<>();
    public int evalRPN(String[] tokens) {
        for (String token : tokens) {
            if ("+".equals(token)) {
                int num1 = nums.pop();
                int num2 = nums.pop();
                int result = num1 + num2;
                nums.push(result);
            } else if ("-".equals(token)) {
                int num1 = nums.pop();
                int num2 = nums.pop();                
                int result = num2 - num1;
                nums.push(result);
            } else if ("*".equals(token)) {
                int num1 = nums.pop();
                int num2 = nums.pop();                
                int result = num1 * num2;
                nums.push(result);
            } else if ("/".equals(token)) {
                int num1 = nums.pop();
                int num2 = nums.pop();                
                int result = num2 / num1;
                nums.push(result);
            } else {
                nums.push(Integer.valueOf(token));
            }
        }
        return nums.peek();
    }
}

225. 用队列实现栈

225. 用队列实现栈 - 力扣（Leetcode）

完成日期：2023/1/12

class MyStack {
    LinkedList<Integer> queue1;
    LinkedList<Integer> queue2;
    public MyStack() {
        queue1 = new LinkedList<>(); 
        queue2 = new LinkedList<>(); 
    }
    
    public void push(int x) {
        queue1.offer(x);
    }
    
    public int pop() {
        while (queue1.size() > 1) {
            queue2.offer(queue1.poll());
        }
        int top = queue1.poll();
        while (!queue2.isEmpty()) {
            queue1.offer(queue2.poll());
        }
        return top;
    }
    
    public int top() {
        int top = pop();
        queue1.offer(top);
        return top;
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

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

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

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

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

题目链接

完成日期：2023/1/14

/**
 * 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) {
        while (head != null && head.val == val) {
            head = head.next;
        }
        if (head == null) {
            return null;
        }        
        ListNode p1 = head;
        ListNode p2 = head.next;
        while (p2 != null) {
            if (p2.val == val) {
                p1.next = p2.next;
                return head;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return head;
    }
}

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

题目链接

完成日期：2023/1/14

/**
 * 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) {
        Map<Integer, ListNode> map = new HashMap<>();
        int count = 0;
        while (head != null) {
            map.put(++count, head);
            head = head.next;
        }
        return map.get(count - k + 1);
    }
}

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

题目链接

完成日期：2023/1/15

/**
 * 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) {
        if (l1 == null && l2 == null) {
            return null;
        }  
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head  = null;
        ListNode tail = null;
        while (l1 != null && l2 != null) {
            ListNode p;
            if (l1.val < l2.val) {
                p = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                p = new ListNode(l2.val);
                l2 = l2.next;
            }
            if (head == null) {
                head = p;
            } else {
                tail.next = p;
            }
            tail = p;
        }
        if (l1 == null) {
            while (l2 != null) {
                ListNode p = new ListNode(l2.val);
                l2 = l2.next;  
                tail.next = p;
                tail = tail.next;              
            }
        }
        if (l2 == null) {
            while (l1 != null) {
                ListNode p = new ListNode(l1.val);
                l1 = l1.next;
                tail.next = p;
                tail = tail.next;
            }
        }
        return head;
    }
}

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

题目链接

完成日期：2023/1/16

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

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

题目链接

完成日期：2023/1/16

class Solution {
    public int[] exchange(int[] nums) {
        int[] newNums = new int[nums.length];
        int count = 0; 
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 1) {
                newNums[count++] = nums[i];
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 0) {
                newNums[count++] = nums[i];
            }
        }
        return newNums;
    }
}

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

题目链接

完成日期：2023/1/16

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (nums[i] + nums[j] != target) {
            if (nums[i] + nums[j] < target) {
                i++;
            } else if (nums[i] + nums[j] > target) {
                j--;
            }
        }   
        return new int[]{nums[i], nums[j]};
    }
}

剑指 Offer 58 - I. 翻转单词顺序

[题目链接](剑指 Offer 58 - I. 翻转单词顺序)

完成日期：2023/1/16

class Solution {
    public String reverseWords(String s) {
        String[] strs = s.trim().split(" ");
        Stack<String> stack = new Stack<>();
        for (String str : strs) {
            if (!"".equals(str.trim())) {
                stack.push(str.trim());
            }
        }
        StringBuilder result  = new StringBuilder();
        int cnt = 0;
        while (!stack.isEmpty()) {
            if (cnt != 0) {
                result.append(" ");
            }
            result.append(stack.pop());
            cnt++;
        }
        return result.toString();
    }
}

剑指 Offer 12. 矩阵中的路径

面试题13. 机器人的运动范围

题目链接

完成日期：2023/1/17

class Solution {       
    int[][] direction ={{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    int count = 0;
    boolean[][] isVisited = null;
    public int movingCount(int m, int n, int k) {
        isVisited = new boolean[m][n];
        backtracking(0, 0, m, n, k);
        return count;
    }
    void backtracking(int x, int y, int m, int n, int k) {
        if (!isVisited[x][y]) {
            count++;
        }
        isVisited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            if (isVaild(x + direction[i][0], y + direction[i][1], m, n, k)
             && !isVisited[x + direction[i][0]][y + direction[i][1]]) {
                backtracking(x + direction[i][0], y + direction[i][1], m, n, k);
            }
        }
    }        
    boolean isVaild(int x, int y, int m, int n, int k) {
        if (!(x >= 0 && x < m)) {
            return false;
        }
        if (!(y >= 0 && y < n)) {
            return false;
        }
        if (compute(x, y) > k) {
            return false;
        }
        return true;
    }
    int compute(int x, int y) {
        int sum = 0;
        do {
            sum += x % 10;
            x /= 10;
        } while (x > 0);
        do {
            sum += y % 10;
            y /= 10;
        } while(y > 0);
        return sum;
    }
}

15. 三数之和

15. 三数之和 - 力扣（Leetcode）

完成日期: 2023/1/17

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int x = 0; x < nums.length; x++) {
            if (nums[0] > 0) {
                return result;
            }
            if (x > 0 && nums[x] == nums[x - 1]) {
                continue;
            }
            int i = x + 1;
            int j = nums.length - 1;
            while (i < j) {
                if (nums[x] + nums[i] + nums[j] == 0) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[x]);
                    list.add(nums[i]);
                    list.add(nums[j]);
                    result.add(list);
                    while (i < j && nums[j - 1] == nums[j]) {
                        j--;
                    }
                    while (i < j && nums[i + 1] == nums[i]) {
                        i++;
                    }
                    j--;
                    i++;
                } else if (nums[x] + nums[i] + nums[j] > 0) {
                    j--;
                } else if (nums[x] + nums[i] + nums[j] < 0) {
                    i++;
                }
            }
        }
        return result;
    }
}

28. 找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标 - 力扣（Leetcode）

完成日期：2023/1/17

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

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

题目链接

完成日期：2023/1/18

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        in(root);
        return list.get(k - 1);
    }
    void in(TreeNode root) {
        if (root == null) {
            return;
        }
        in(root.right);
        list.add(root.val);
        in(root.left);
    }
}

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

题目链接

完成日期：2023/1/18

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

    public Node() {}

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

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    Node head;
    Node tail;
    public Node treeToDoublyList(Node root) {
        in(root);
        if (head != null) {
            tail.right = head;
            head.left = tail;
        } 
        return head;
    }
    void in(Node root) {
        if (root == null) {
            return;
        }
        in(root.left);
        if (head == null) {
            head = root;
        } else {
            root.left = tail;
            tail.right = root;
        }
        tail = root;
        in(root.right);
    } 
}

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

题目链接

完成日期：2023/1/18

/**
 * 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>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    int sum = 0;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root !=  null) {
            backtracking(root, target);
        }
        return result;
    }
    void backtracking(TreeNode root, int target) {
        path.add(root.val);
        sum += root.val;
        if (root.left == null && root.right == null) {
            if (sum == target) {
                result.add(new LinkedList<>(path));
            }
            return;
        }
        if (root.left != null) {
            backtracking(root.left, target);
            path.removeLast();
            sum -= root.left.val;
        }
        if (root.right != null) {
            backtracking(root.right, target);
            path.removeLast();
            sum -= root.right.val;
        }
    }
}

376. 摆动序列

面试题45. 把数组排成最小的数

题目链接

完成日期：2023/1/19

class Solution {
    public String minNumber(int[] nums) {
        Long[] longs = Arrays.stream(nums)
                .mapToLong(integer -> Long.parseLong(String.valueOf(integer)))
                .boxed()
                .toArray(Long[]::new);
        Arrays.sort(longs, (o1, o2) -> {
            String s1 = o1.toString() + o2.toString();
            String s2 = o2.toString() + o1.toString();
            return Math.toIntExact(Long.parseLong(s1) - Long.parseLong(s2));
        });
        StringBuilder stringBuilder = new StringBuilder();
        Arrays.stream(longs).forEach(stringBuilder::append);
        return stringBuilder.toString();
    }
}

面试题61. 扑克牌中的顺子

面试题61. 扑克牌中的顺子

完成日期：2023/1/19

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int cnt = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == 0) {
                cnt++;
            } else if (nums[i] == nums[i + 1]) {
                return false;
            }
        }
        return nums[4] - nums[cnt] < 5; 
    }
}

701. 二叉搜索树中的插入操作

701. 二叉搜索树中的插入操作 - 力扣（Leetcode）

完成日期：2023/1/19

/**
 * 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 {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        insert(root, val);
        return root;
    }
    void insert(TreeNode root, int val) {
        if (val < root.val) {
            if (root.left == null) {
                root.left = new TreeNode(val);
                return;
            }
            insert(root.left, val);
        }
        if (val > root.val) {
            if (root.right == null) {
                root.right = new TreeNode(val);
                return;
            }
            insert(root.right, val);
        }
    }
}

剑指 Offer 40. 最小的k个数

题目链接

完成日期：2023/1/20

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        return Arrays.stream(arr).sorted().limit(k).toArray();
    }
}

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

题目链接

完成日期：2023/1/21

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } 
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

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

题目链接

完成日期：2023/1/21

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }  
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
}

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

题目链接

完成日期：2023/1/22

class Solution {
    public int sumNums(int n) {
        return IntStream.range(1, n + 1).sum();
    }
}

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

题目链接

完成日期：2023/1/22

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<TreeNode> listP = new ArrayList<>();
    List<TreeNode> listQ = new ArrayList<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        search(root, p, listP);
        search(root, q, listQ);
        TreeNode ancestor = null;
        int len = Math.min(listP.size(), listQ.size());
        for (int i = 0; i < len; i++) {
            if (listP.get(i) == listQ.get(i)) {
                ancestor = listP.get(i);
            }
        }
        return ancestor;
    }
    void search(TreeNode root, TreeNode target, List<TreeNode> list) {
        list.add(root);
        if (root == target) {
            return;
        }
        if (target.val < root.val) {
            search(root.left, target, list);
        }
        if (target.val > root.val) {
            search(root.right, target, list);
        }
    }
} 

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

题目链接

完成日期：2023/1/23

class Solution {
    public double myPow(double x, long n) {
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        return quickPow(x, n);
    }
    double quickPow(double x, long n) {
        double result = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                result *= x;
            }
            n /= 2;
            x *= x;    
        }
        return result;
    }
}   

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

题目链接

完成日期：2023/1/24

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

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

题目链接

完成日期：2023/1/24

class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a ^= b;
            b = carry;
        }
        return a;
    }
}

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

题目链接

完成日期：2023/1/25

class Solution {
    public int[] singleNumbers(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum ^= num;
        }
        int m = 1;
        while ((m & sum) == 0) {
            m <<= 1;
        }
        int x = 0;
        int y = 0;
        for (int num : nums) {
            if ((m & num) == 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }
}

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

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

完成日期：2023/1/25

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        for (Integer num : nums) {
            if (map.get(num) == 1) {
                return num;
            }
        }
        return 1;
    }
}

剑指 Offer 07. 重建二叉树

题目链接

完成日期：2023/1/25

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, 0, 0, preorder.length - 1);
    }
    TreeNode build(int[] preorder, int index, int left, int right) {
        if (left > right) {
            return null; 
        }
        TreeNode root = new TreeNode(preorder[index]);
        int i = map.get(preorder[index]);
        root.left = build(preorder, index + 1, left, i - 1);
        root.right = build(preorder, index - left + i + 1, i + 1, right);
        return root;
    }
}

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

题目链接

完成日期：2023/1/26

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int cnt = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] == nums[i]) {
                cnt++;
            } else {
                cnt = 1;
            }
            if (cnt > nums.length / 2) {
                return nums[i];
            }
        }
        return nums[0];
    }
}

剑指 Offer 66. 构建乘积数组

题目链接

完成日期：2022/1/26

class Solution {
    public int[] constructArr(int[] a) {
        int result = 1;
        int cnt = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] != 0) {
                result *= a[i];
            } else {
                cnt++;
            }
        }
        int current = 1;
        int[] b = new int[a.length];
        for (int i = 0; i < b.length; i++) {
            current = a[i];
            if (cnt == 0) {
                b[i] = result / current;
            } else if (cnt == 1) {
                if (a[i] == 0) {
                    b[i] = result;
                } else {
                    b[i] = 0;
                }
            }
        }
        return b;
    }
}