5月17日

二叉树的堂兄弟节点

class Solution {
    int x;
    int xLevel;
    TreeNode xFather;

    int y;
    int yLevel;
    TreeNode yFather;

    public boolean isCousins(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;
        xLevel = -1;
        yLevel = -1;
        xFather = null;
        yFather = null;

        dfs (root, 0, null);
        if (xLevel == yLevel && xFather != yFather) return true;
        else return false;
    }
    private void dfs (TreeNode node, int level, TreeNode father) {
        if ((xFather != null && yFather != null) || node == null) return;
        if (node.val == x) {
            xFather = father;
            xLevel = level;
        } else if (node.val == y) {
            yFather = father;
            yLevel = level;
        }
        dfs(node.left, level + 1, node);
        dfs(node.right, level + 1, node);
    }
}

5月16日

数组中两个数的最大异或值

class Solution {
    public int findMaximumXOR(int[] nums) {
        Trie trie = new Trie();
        int ans = 0;
        for (int num : nums) {
            trie.insert(num);
            ans = Math.max(ans, trie.get(num));
        }
        return ans;
    }
}

/**
 * Description: Tire树结点定义
 */
class TrieNode {
    TrieNode[] sub = new TrieNode[2];
}

/**
 * Description: 字典树
 */
class Trie{
    TrieNode root;
    public Trie(){
        root = new TrieNode();
    }

    // 插入
    public void insert(int x){
        TrieNode cur = root;
        for(int i = 30; i >= 0; i--){
            int d = (x >> i) & 1;
            if(cur.sub[d] == null){
                cur.sub[d] = new TrieNode();
            }
            cur = cur.sub[d];
        }
    }

    //获得 x 的最大异或值
    public int get(int x){
        int sum = 0;
        TrieNode cur = root;
        for(int i = 30; i >= 0; i--){
            int d = (x >> i) & 1;
            if(cur.sub[d ^ 1] != null){
                sum = sum * 2 + 1;
                cur = cur.sub[d ^ 1];
            }else if(cur.sub[d] != null){
                sum = sum * 2;
                cur = cur.sub[d];
            }
        }
        return sum;
    }
}

5月15日

罗马数字转整数

class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> map = new HashMap<>(){{
            put('I', 1);
            put('V', 5);
            put('X', 10);
            put('L', 50);
            put('C', 100);
            put('D', 500);
            put('M', 1000);
        }};
        int ans = 0;
        int n = s.length();
        for(int i = 0; i < n; ++ i) {
            int value = map.get(s.charAt(i));
            if (i < n - 1 && value < map.get(s.charAt(i + 1))) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }
}

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日每日一题

- - - 回溯小专题 - - -

寻找目标值序列

⚡ 回溯

import java.util.ArrayList;
import java.util.List;

/**
 * @author Javid Xi
 * @Classname FindTargetList
 * @Description 已知一个无序数组 array，元素均为正整数。给定一个目标值 target，输出数组中是否存在若干元素的组合，相加为目标值。
 * @Date 2021/5/11
 */
public class FindTargetList {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        int[] arr = {1,2,7,3,6,5,4};
        find(arr, 12, 0, 0, list);

    }

    /**
     * Description: 回溯
     */
    public static void find(int[] arr, int tar, int idx, int total, List<Integer> list){
        if(idx == arr.length) return;

        list.add(idx);
        if(total + arr[idx] == tar)
            System.out.println(list);
        else
            find(arr, tar, idx + 1, total + arr[idx], list);

        list.remove(list.size() - 1);
        find(arr, tar, idx + 1, total, list);
    }
}

组合总和

⚡ 回溯

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<>();
        backTrack(candidates, target, list, ans, 0);
        return ans;
    }

    private void backTrack (int[] candidates, int target, List<Integer> list, List<List<Integer>> ans, int idx) {
        ///if (target <= 0) return;
        for (int i = idx; i < candidates.length; ++ i) {
            list.add(candidates[i]);
            if (candidates[i] == target) {
                // 这里不可直接传 list 因为其传递为引用传递 list 中数据的改变会影响到 ans 中的数据
                // 因此需要传入 list 的复制
                ans.add(new ArrayList<Integer>(list));
            } else if (candidates[i] < target) {
                backTrack(candidates, target - candidates[i], list, ans, i);
            }
            list.remove(list.size() - 1);
        }
    }
}

组合总和II

⚡ 回溯 & 剪枝

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        backTrack(candidates, target, 0, list, ans);
        return ans;
    }

    private void backTrack (int[] candidates, int target, int idx, List<Integer> list, List<List<Integer>> ans) {
        for (int i = idx; i < candidates.length; ++ i) {
            if (i != idx && candidates[i] == candidates[i - 1]) continue;
            list.add(candidates[i]);
            if (candidates[i] == target) {
                    ans.add(new ArrayList<>(list));
            } else if (candidates[i] < target) {
                backTrack(candidates, target - candidates[i], i + 1, list, ans);
            } else {
                // 剪枝
                list.remove(list.size() - 1);
                break;
            }
            list.remove(list.size() - 1);
        }
    }
}

组合总和III

⚡ 回溯

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        backTrack(k, n, 1, list, ans);
        return ans;
    }

    private void backTrack (int k, int n, int idx, List<Integer> list, List<List<Integer>> ans) {
        for (int i = idx; i < 10; ++ i) {
            list.add(i);
            k--;
            if (i == n && k == 0) {
                ans.add(new ArrayList<>(list));
            } else if (i < n){
                backTrack(k, n - i, i + 1, list, ans);
            }
            list.remove(list.size() - 1);
            k++;
        }
    }
}

组合总和Ⅳ

⚡ 动态规划

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; ++ i) {
            for (int num : nums) {
                if (num <= i) {
                    dp[i] += dp[i - num]; 
                }
            }
        }
        return dp[target];
    }
}

注：回溯会超时

三数之和

⚡ 双指针O(n2)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        // 枚举 a
        for (int first = 0; first < n; ++ first) {
            if (first != 0 && nums[first] == nums[first - 1]) continue;
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++ second) {
                if (second != first + 1 && nums[second] == nums[second - 1])
                    continue;
                while (second < third && nums[second] + nums[third] > target) {
                    -- third;
                }
                if (second == third) break;
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

注：回溯O(n3)会超时

较小的三数之和

⚡ 双指针O(n2)

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 0;
        // 枚举 a
        for (int first = 0; first < n; ++ first) {
            int third = n - 1;
            int tar = target - nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++ second) {
                while (second < third && nums[second] + nums[third] >= tar) {
                    -- third;
                }
                if (second == third) break;
                ans += third - second;
            }
        }
        return ans;
    }
}

四数之和

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        // 枚举 a
        for (int first = 0; first < n; ++ first) {
            if (first != 0 && nums[first] == nums[first - 1])
                continue;
            // 枚举 b
            for (int second = first + 1; second < n; ++ second) {
                if (second != first + 1 && nums[second] == nums[second - 1])
                    continue;
                int fouth = n - 1;
                int tar = target - nums[first] - nums[second];
                // 枚举 c
                for (int third = second + 1; third < n; ++ third) {
                    if (third != second + 1 && nums[third] == nums[third - 1])
                        continue;
                    while (third < fouth && nums[third] + nums[fouth] > tar) {
                        -- fouth;
                    }
                    if (fouth == third) break;
                    if (nums[fouth] + nums[third] == tar) {
                        ans.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fouth]));
                    }
                }
            }
        }
        return ans;
    }
}

注：

• Arrays.asList() 该方法是将数组转化成List集合的方法。
  1. 该方法适用于对象型数据的数组（String、Integer...）；
  2. 该方法不建议使用于基本数据类型的数组（byte,short,int,long,float,double,boolean）；
  3. 该方法将数组与List列表链接起来：当更新其一个时，另一个自动更新；
  4. 不支持add()、remove()、clear()等方法；
  5. 用此方法得到的List的长度是不可改变的。
• 总结：
  • 如果List只是用来遍历，就用Arrays.asList()；
  • 如果List还要添加或删除元素，就new一个java.util.ArrayList，然后一个一个地添加元素。

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

无重复字符的最长子串⭐

⚡ 滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int len = s.length();
        int rk = 0, ans = 0;
        for (int i = 0; i < len; ++i) {
            if (i != 0) set.remove(s.charAt(i - 1));
            while (rk < len && !set.contains(s.charAt(rk))) {
                set.add(s.charAt(rk));
                ++ rk;
            }
            ans = Math.max(ans, rk - i);
        }
        return ans;
    }
}

寻找两个正序数组的中位数⭐⭐

⚡ 二分法

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int total = len1 + len2;
        if (total % 2 == 1) {
            return getKthNum(nums1, nums2, total / 2 + 1);
        } else {
            return (getKthNum(nums1, nums2, total / 2 + 1) + getKthNum(nums1, nums2, total / 2)) / 2.0;
        }
    }

    // 二分查找 两数组按顺序 k 位置的数
    private int getKthNum (int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length, len2 = nums2.length;
        int idx1 = 0, idx2 = 0;
        int kElem = 0;
        while (true) {
            // 处理边界情况
            if (idx1 == len1) return nums2[idx2 + k - 1];
            if (idx2 == len2) return nums1[idx1 + k - 1];
            if (k == 1) return Math.min(nums1[idx1], nums2[idx2]);

            int half = k >> 1;
            int newIdx1 = Math.min(idx1 + half, len1) - 1;
            int newIdx2 = Math.min(idx2 + half, len2) - 1;
            int pivot1 = nums1[newIdx1], pivot2 = nums2[newIdx2];
            if (pivot1 <= pivot2) {
                k -= newIdx1 - idx1 + 1;
                idx1 = newIdx1 + 1;
            } else {
                k -= newIdx2 - idx2 + 1;
                idx2 = newIdx2 + 1;
            }
        }
    }
}

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月3日

整数反转

class Solution {
    public int reverse(int x) {
        int ans = 0;
        while (x != 0) {
            if (ans > Integer.MAX_VALUE / 10 || ans < Integer.MIN_VALUE / 10) return 0;
            ans = ans * 10 + x % 10; 
            x /= 10;
        }
        return ans;
    }
}

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

下一个排列⭐

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }
        if (i >= 0) {
            int j = n - 1;
            while (j > i && nums[j] <= nums[i]) {
                --j;
            }
            int tmp = nums[j];
            nums[j] = nums[i];
            nums[i] = tmp;
        }   
        for (int left = i + 1, right = n - 1; left < right; ++left,--right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }
}

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

最长回文子串

⚡ 中心扩散 枚举

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int n = s.length();
        int start = 0, end = 0;
        for (int i = 0; i < n; ++i) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (end - start < len) {
                start = i - (len - 1) / 2; //仔细体会
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private static int expandAroundCenter (String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1; //仔细体会
    }
}