from 2022-08-29 to 2022-09-04

leetcode 1470.重新排列数组

class Solution {
        public int[] shuffle(int[] nums, int n) {
            int[] ans = new int[2 * n];
            for (int i = 0; i < n; i++) {
                ans[2 * i] = nums[i];
                ans[2 * i + 1] = nums[i + n];
            }
            return ans;
        }
    }

leetcode 998.最大二叉树 II

class Solution {
        public TreeNode insertIntoMaxTree(TreeNode root, int val) {
            // val 如果是最大值，那么直接把原先的树设为新节点的左子树
            // 否则，遍历最右子节点，寻找临界节点
            if(root == null) {
                return new TreeNode(val);
            }
            TreeNode father = null;
            TreeNode child = root;
            while(child != null && child.val > val) {
                father = child;
                child = child.right;
            }
            // val 为最大值
            if(father == null) {
                return new TreeNode(val, child, null);
            } else {
                father.right = new TreeNode(val, child, null);
                return root;
            }
        }
}

LeetCode 946.验证栈序列

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
            int n = pushed.length;
            for (int i = 0, j = 0; i < n; i++) {
                stack.push(pushed[i]);
                while (!stack.isEmpty() && stack.peek() == popped[j]) {
                    stack.pop();
                    j++;
                }
            }
            return stack.isEmpty();
    }
}

leetcode 1475.商品折扣后的最终价格

    class Solution {
        public int[] finalPrices(int[] prices) {
            int[] res = new int[prices.length];
            for(int i = 0; i < prices.length; i++) {
                res[i] = prices[i];
            }
            for(int i = 0; i < prices.length; i++) {
                for(int j = i + 1; j < prices.length; j++) {
                    if(prices[j] <= prices[i]) {
                        res[i] = prices[i] - prices[j];
                        break;
                    }
                }
            }
            return res;
        }
    }
    class Solution1 {
        public int[] finalPrices(int[] prices) {
            int[] res = new int[prices.length];
            for(int i = 0; i < prices.length; i++) {
                int discount = 0;
                for(int j = i + 1; j < prices.length; j++) {
                    if(prices[j] <= prices[i]) {
                        discount = prices[j];
                        break;
                    }
                }
                res[i] = prices[i] - discount;
            }
            return res;
        }
    }

leetcode 687.最长同值路径

class Solution {
    int max = 0;
    public int longestUnivaluePath(TreeNode root) {
        helper(root);
        return max;
    }

    private int helper(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int lefMax = helper(root.left);
        int rightMax = helper(root.right);
        int left1 = 0; int right1 = 0;
        if(root.left != null && root.left.val == root.val) {
            left1 = lefMax + 1;
        }
        if(root.right != null && root.right.val == root.val) {
            right1 = rightMax + 1;
        }
        max = Math.max(max, left1 + right1);
        return Math.max(left1, right1);

    }
}

leetcode 646.最长数对链

class Solution {
        public int findLongestChain(int[][] pairs) {
            int n = pairs.length;
            Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
            int[] dp = new int[n];
            Arrays.fill(dp, 1);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (pairs[i][0] > pairs[j][1]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            return dp[n - 1];
        }
}

leetcode 1582. 二进制矩阵中的特殊位置

class Solution {
        public int numSpecial(int[][] mat) {
            int res = 0;
            int rowsSum[] = new int[mat.length];
            int columSum[] = new int[mat[0].length];
            for (int i = 0; i < mat.length; i++) {
                for (int j = 0; j < mat[0].length; j++) {
                    rowsSum[i] += mat[i][j];
                    columSum[j] += mat[i][j];
                }
            }
            for (int i = 0; i < mat.length; i++) {
                for (int j = 0; j < mat[0].length; j++) {
                    if (mat[i][j] == 1 && rowsSum[i] == 1 && columSum[j] == 1) {
                        res++;
                    }
                }
            }
            return res;
        }
}