本文最后更新于2021年10月16日,已超过 1 个月没更新!

5月14日

整数转罗马数字

硬编码数字

class Solution {
    public String intToRoman(int num) {
        String[] thousands = {"","M","MM","MMM"};
        String[] hundreds = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
        String[] tens = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
        String[] ones = {"","I","II","III","IV","V","VI","VII","VIII","IX"};

        StringBuilder str = new StringBuilder();
        str.append(thousands[num / 1000]);
        str.append(hundreds[(num % 1000) / 100]);
        str.append(tens[num % 100 / 10]);
        str.append(ones[num % 10]);
        return str.toString();
    }
}

5月13日🥗

停在原地的方案数

动态规划

class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = (int)(1e9 + 7);
        // dp[i][j]表示i步跳到j处的方案数
        int size  = Math.min(steps, arrLen);
        long[][] dp = new long[steps + 1][size + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= steps; ++ i) {
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
            for (int j = 1; j < size; ++ j) {
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
            }
        }
        return (int)dp[steps][0];
    }
}

剪枝 & 数组优化

class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = (int)(1e9 + 7);
        // dp[i][j]表示i步跳到j处的方案数
        int size  = Math.min(steps, arrLen);
        int[][] dp = new int[steps + 1][size + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= steps; ++ i) {
            int edge = Math.min(i + 1, size); // 剪枝
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
            for (int j = 1; j < edge; ++ j) {
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod;
                dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod;
            }
        }
        return dp[steps][0];
    }
}

5月12日

子数组异或查询

前缀和

class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        int[] pre = new int[arr.length + 1];
        for (int i = 1; i <= arr.length; ++ i) {
            pre[i] = pre[i - 1] ^ arr[i - 1];
        }
        for (int i = 0; i < n; ++ i) {
            ans[i] = pre[queries[i][1] + 1] ^ pre[queries[i][0]];
        }
        return ans;
    }
}

5月11日🥗

解码异或后的排列

class Solution {
    public int[] decode(int[] encoded) {
        int n = encoded.length;
        int total = 0, odd = 0;
        for (int i = 1; i <= n + 1; ++ i) total ^= i; // 求原数组异或和
        for (int i = 1; i < n; i += 2) odd ^= encoded[i]; // 求原数组除了perm[0]元素之外的异或和

        int[] perm = new int[n + 1];
        perm[0] = total ^ odd;
        for (int i = 1; i <= n; ++ i) {
            perm[i] = encoded[i - 1] ^ perm[i - 1];
        }
        return perm;
    }
}

注:类似题型5月6日每日一题

5月10日

叶子相似的树

递归

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        return list1.equals(list2);
    }
    private void dfs (TreeNode node, List<Integer> list) {
        if (node == null) return;
        if (node.left == null && node.right == null) {
            list.add(node.val);
        }
        dfs(node.left, list);
        dfs(node.right, list);
    }
}

迭代

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        return iterate(root1).equals(iterate(root2));
    }

    private List<Integer> iterate (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> s = new LinkedList<>();
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode node = s.pop();
            if (node.left == null && node.right == null) list.add(node.val);
            if (node.left != null) s.push(node.left);
            if (node.right != null) s.push(node.right);
        }
        return list;
    }
}

5月9日🥗

制作m束花所需的最少天数

二分

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if (k * m > bloomDay.length) return -1;
        int len = bloomDay.length;
        int low = 1, high = 1;
        for (int i = 0; i < len; i ++) {
            high = Math.max(high, bloomDay[i]);
        }
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canMake(bloomDay, mid, m, k)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return high;
    }

    private boolean canMake (int[] bloomDay, int day, int m, int k) {
        int bouquets = 0; // 记录在天数day的限制内能制作的花束
        int len = bloomDay.length;
        int flowers = 0; // 记录花束的数量
        for (int i = 0; i < len; i ++) {
            if (bloomDay[i] <= day) {
                flowers ++;
                if (flowers == k) {
                    bouquets ++;
                    flowers = 0;
                }
            } else flowers = 0;
        }
        return bouquets >= m;
    }
}

下一个更大元素I

单调栈

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < nums2.length; ++ i) {
            while (!stack.isEmpty() && nums2[i] > stack.peek())
                hashMap.put(stack.pop(), nums2[i]);
            stack.push(nums2[i]);
        }
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++ i) {
            ans[i] = hashMap.getOrDefault(nums1[i], -1);
        }
        return ans;
    }
}

下一个更大元素II

单调栈

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < 2 * n; ++i) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ans[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);
        }
        return ans;
    }
}

5月8日

完成所有工作的最短时间

DFS & 剪枝

class Solution {
    int jobs[];
    int n, k, ans;
    public int minimumTimeRequired(int[] jobs, int k) {
        this.jobs = jobs;
        this.k = k;
        this.n = jobs.length;
        this.ans = Integer.MAX_VALUE;
        int[] distributions = new int[n];
        dfs(0, 0, distributions, 0);
        return ans;
    }

    /**
     * u: 当前处理的job
     * used: 当前分配给了多少个工人了
     * distributions: 工人的分配情况 distributions[0] = x 代表 0 号工人工作量为 x
     * maxTime: 当前的「最大工作时间」
     */
    private void dfs (int u, int used, int[] distributions, int maxTime) {
        if (maxTime >= ans) return;
        if (u == n) {
            ans = maxTime;
            return;
        }
        // 优先分配给未分配的工人
        // 先找到一个较小ans,便于 maxTime >= ans return剪枝
        if (used < k) {
            distributions[used] = jobs[u];
            dfs(u + 1, used + 1, distributions, Math.max(distributions[used], maxTime));
            distributions[used] = 0;
        }

        for (int i = 0; i < used; ++i) {
            distributions[i] += jobs[u];
            dfs(u + 1, used, distributions, Math.max(distributions[i], maxTime));
            distributions[i] -= jobs[u];
        }
    }
}

5月7日🥗

数组异或操作

利用异或性质

class Solution {
    public int xorOperation(int n, int start) {
        int b0 = n & start & 1; // 确定最低位
        int s = start >> 1;
        // 3^4^5^6^7^8^9 = (1^2)^(1^2^3^4^5^6^7^8^9)
        int ans = sumXor(s - 1) ^ sumXor(s + n - 1);
        return ans << 1 | b0;
    }
    // 4i ⊕ (4i+1) ⊕ (4i+2) ⊕ (4i+3) = 0
    private static int sumXor (int x) {
        switch (x % 4) {
            case 0 : return x;
            case 1 : return 1;
            case 2 : return x + 1;
        }
        return 0; 
    }
}

5月6日

解码异或后的数组

class Solution {
    public int[] decode(int[] encoded, int first) {
        int n = encoded.length;
        int[] arr = new int[n + 1];
        arr[0] = first;
        for (int i = 0; i < n; ++i) {
            // 异或满足交换律
            arr[i + 1] = arr[i] ^ encoded[i];
        }
        return arr;
    }
}

5月5日

删除并获得点数

动态规划

class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxNum = Arrays.stream(nums).max().getAsInt();
        int[] sums = new int[maxNum + 1];
        for (int num : nums) {
            sums[num] += num;
        }

        // 动态规划
        for (int i = 2; i <= maxNum; ++i) {
            sums[i] = Math.max(sums[i - 1], sums[i - 2] + sums[i]);
        }
        return sums[maxNum];
    }
}

排序 & 动态规划

class Solution {
    // 将 nums 排序后,将其划分成若干连续子数组,子数组内任意相邻元素之差不超过 1。
    // 对每个子数组按照方法一的动态规划过程计算出结果,累加所有结果即为答案。
    public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        int size = 1, ans = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == nums[i - 1]) {
                list.set(size - 1, list.get(size - 1) + nums[i]);
            } else if (nums[i] == nums[i - 1] + 1) {
                list.add(nums[i]);
                ++size;
            } else {
                ans += rob(list);
                list.clear();
                list.add(nums[i]);
                size = 1;
            }
        }
        ans += rob(list);
        return ans;
    }

    private int rob (List<Integer> list) {
        int size = list.size();
        if (size == 1) return list.get(0);
        int first = list.get(0), second = Math.max(first, list.get(1));
        for (int i = 2; i < size; ++i) {
            int tmp = second;
            second = Math.max(first + list.get(i), second);
            first = tmp;
        }
        return second;
    }
}

打家劫舍

5月4日🥗

粉刷房子III

三维动态规划

class Solution {
    // 为防止溢出,Integer最大值除2表示无穷大
    static final int INFTY = Integer.MAX_VALUE / 2;

    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        //为了叙述方便, 令所有的变量都从 0 开始编号, 即: 
        // 房子的编号为 [0, m-1]
        // 颜色的编号为 [0, n-1] 如果房子没有涂上颜色,那么记为 -1
        // 街区的编号为 [0,target−1]

        // 让房间颜色数从零开始计 -1为未涂色
        for (int i = 0; i < m; ++i) {
            houses[i]--;
        }
        // dp(i,j,k) 表示将 [0, i] 的房子都涂上颜色,最末尾的第 i 个房子的颜色为 j,并且它属于第 k 个街区时,需要的最少花费。
        int[][][] dp = new int[m][n][target];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                Arrays.fill(dp[i][j], INFTY);
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (houses[i] != -1 && houses[i] != j) { // 房间i已被上色且不属于此街区
                    continue;
                }

                for (int k = 0; k < target; ++k) { // 枚举所有街区
                    for (int j0 = 0; j0 < n; ++j0) { // 枚举所有颜色
                        if (j == j0) { // 颜色相同,属于同一个街区
                            if (i == 0) {
                                if (k == 0) {
                                    dp[i][j][k] = 0;
                                }
                            } else {
                                dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][k]);
                            }
                        }
                        else if (i > 0 && k > 0) {  //颜色不同,不属于同一个街区
                            dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j0][k - 1]);
                        }
                    }
                    // 若dp传递成功,且此房间未被上色
                    if (dp[i][j][k] != INFTY && houses[i] == -1) {
                        dp[i][j][k] += cost[i][j];
                    }
                } 
            }
        }

        int ans = INFTY;
        for (int j = 0; j < n; ++j) {
            ans = Math.min(ans, dp[m - 1][j][target - 1]);
        }
        return ans == INFTY ? -1 : ans;
    }
}

粉刷房子⭐⭐

DFS(超时)

class Solution {
    private int[][] costs;
    public int minCost(int[][] costs) {
        if (costs.length == 0) return 0;
        this.costs = costs;
        return Math.min (paintCost(0, 0), Math.min(paintCost(0, 1), paintCost(0, 2)));
    }

    private int paintCost (int n, int color) {
        int total = costs[n][color];
        if (n < costs.length - 1) {
            if (color == 0) {
                total += Math.min(paintCost(n + 1, 1), paintCost(n + 1, 2));
            } else if (color == 1) {
                total += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 2));
            } else {
                total += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 1));
            }
        }
        return total;
    }
}

记忆化搜索DFS

class Solution {
    private int[][] costs;
    HashMap<String, Integer> hashMap; // 使用HashMap储存已经计算过的total值
    public int minCost(int[][] costs) {
        if (costs.length == 0) return 0;
        this.costs = costs;
        hashMap = new HashMap<>();
        return Math.min (paintCost(0, 0), Math.min(paintCost(0, 1), paintCost(0, 2)));
    }

    private int paintCost (int n, int color) {
        String key = getKey(n, color);
        if (hashMap.containsKey(key)) {
            return hashMap.get(key);
        }
        int total = costs[n][color];
        if (n < costs.length - 1) {
            if (color == 0) {
                total += Math.min(paintCost(n + 1, 1), paintCost(n + 1, 2));
            } else if (color == 1) {
                total += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 2));
            } else {
                total += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 1));
            }
        }
        hashMap.put(key, total);
        return total;
    }

    private String getKey(int n, int color) {
        return String.valueOf(n) + " " + String.valueOf(color);
    }
}

动态规划

class Solution {
    // 在原数组上修改
    public int minCost(int[][] costs) {
        int n = costs.length;
        for (int i = 1; i < n; ++i) {
            costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
            costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
            costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
        }
        return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1], costs[n - 1][2]));
    }
}

动态规划(空间优化)

class Solution {
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[] preCosts = costs[0];
        for (int i = 1; i < n; ++i) {
            int[] currentCosts = costs[i];
            currentCosts[0] += Math.min(preCosts[1], preCosts[2]);
            currentCosts[1] += Math.min(preCosts[0], preCosts[2]);
            currentCosts[2] += Math.min(preCosts[0], preCosts[1]);
            preCosts = currentCosts;
        }
        return Math.min(preCosts[0], Math.min(preCosts[1], preCosts[2]));
    }
}

二叉搜索树中的插入操作

递归

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        recur(root, val);
        return root;
    }
    public void recur(TreeNode root, int val) {
        if (root == null) return;
        if (val > root.val) {
            if (root.right == null) {
                root.right = new TreeNode(val);
                return;
            } else {
                recur(root.right, val);
            }
        }
        else if (val < root.val) {
            if (root.left == null) {
                root.left = new TreeNode(val);
                return;
            } else recur(root.left, val);
        }
    }
}

迭代

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode pos = root;
        while (pos != null) {
            if (val < pos.val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                } else {
                    pos = pos.left;
                }
            } else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                } else {
                    pos = pos.right;
                }
            }
        }
        return root;
    }
}

5月2日

砖墙

哈希表

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int size = wall.size();
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (List<Integer> level : wall) {
            int sum = 0;
            for (int j = 0; j < level.size() - 1; ++j) {
                sum += level.get(j);
                hashMap.put(sum, hashMap.getOrDefault(sum, 0) + 1);
            }
        }

        int max = 0;
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            max = Math.max(max, entry.getValue());
        }
        return size - max;
    }
}

5月1日

员工的重要性

递归

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        int ans = 0;
        for (int i = 0; i < employees.size(); ++i) {
            if (employees.get(i).id == id) {
                ans += employees.get(i).importance;
                for (int num : employees.get(i).subordinates) {
                    ans += getImportance(employees, num);
                }
                break;
            }
        }
        return ans;
    }
}

用HashMap加快查找

class Solution {
    HashMap<Integer, Employee> hashMap = new HashMap<>();
    public int getImportance(List<Employee> employees, int id) {
        for (Employee employee : employees) {
            hashMap.put (employee.id, employee);
        }
        return dfs(id);
    }

    public int dfs (int id) {
        Employee employee = hashMap.get(id);
        int total = employee.importance;
        List<Integer> subordinates = employee.subordinates;
        for (int subId : subordinates) {
            total += dfs (subId);
        }
        return total;
    }
}

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