September

09-30 矩形面积

🧩 贪心

func computeArea(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 int) int {
    area1 := (ax2 - ax1) * (ay2 - ay1)
    area2 := (bx2 - bx1) * (by2 - by1)
    overlapWidth := min(ax2, bx2) - max(ax1, bx1)
    overlapHeight := min(ay2, by2) - max(ay1, by1)
    overlapArea := max(overlapWidth, 0) * max(overlapHeight, 0)
    return area1 + area2 - overlapArea
}

09-29 超级洗衣机

🧩 贪心

func findMinMoves(machines []int) int {
    total := 0
    for _, v := range machines {
        total += v;
    }
    len := len(machines);
    if total % len != 0 {
        return -1;
    }
    avg := total / len;
    sum := 0
    ans := 0
    for _, m := range machines {
        // 组内的某一台洗衣机内的衣服数量过多,需要向左右两侧移出衣服时的移动次数
        m -= avg;
        // A与B两组衣服达到平衡最多需要的移动次数
        sum += m;
        ans = max(ans, max(abs(sum), m));
    }
    return ans;
}

09-24 两个字符串的删除操作

🧩 最长公共子序列dp

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; ++ i) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= m; ++ j) {
                char c2 = word2.charAt(j - 1);
                if (c1 == c2) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return m + n - 2 * f[n][m];
    }
}

🧩 dp

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        // f[i][j]表示使前i个和前j个相等所需的删除操作数
        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i <= m; ++ i) f[0][i] = i;
        for (int i = 0; i <= n; ++ i) f[i][0] = i;

        for (int i = 1; i <= n; ++ i) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= m; ++ j) {
                char c2 = word2.charAt(j - 1);
                if (c1 == c2) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + 1;
                }
            }
        }
        return f[n][m];
    }
}

09-20 最长递增子序列的个数(必)

🧩 dp

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        int ans = 0, maxLen = 0;
        for (int i = 0; i < n; ++ i) {
            dp[i] = 1;
            cnt[i] = 1;
            for (int j = 0; j < i; ++ j) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i];
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
}

09-19 只有两个键的键盘

🧩 dp

class Solution {
    public int minSteps(int n) {
        // f[i] 表示打印出 i 个 A 的最少操作次数
        int[] f = new int[n + 1];
        for (int i = 2; i <= n; ++ i) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; ++ j) {
                if (i % j == 0) {
                    // copy f[i] paste i/j 次
                    f[i] = Math.min(f[i], f[j] + i / j);
                    // copy f[i/j] paste j 次
                    f[i] = Math.min(f[i], f[i / j] + j);
                }
            }
        }
        return f[n];
    }
}

🧩 分解质因数

class Solution {
    public int minSteps(int n) {
        int ans = 0;
        for (int i = 2; i <= n; ++ i) {
            while (n % i == 0) {
                n /= i;
                ans += i;
            }
        }

        if (n > 1) ans += n;
        return ans;
    }
}

09-18 Nim 游戏

🧩 博弈论

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

09-17 有效的数独

🧩 数组代替哈希表

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] subboxes = new int[3][3][9];
        for (int i = 0; i < 9; ++ i) {
            for (int j = 0; j < 9; ++ j) {
                char c = board[i][j];
                if (c != '.') {
                    int idx = c - '0' - 1;
                    rows[i][idx] ++;
                    columns[j][idx] ++;
                    subboxes[i/3][j/3][idx] ++;
                    if (rows[i][idx] > 1 || columns[j][idx] > 1 || subboxes[i/3][j/3][idx] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

09-16 单词搜索 II

🧩 Tire树 + 回溯

class Solution {

    int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public List<String> findWords(char[][] board, String[] words) {
        // 构造Trie树
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        Set<String> ans = new HashSet<>();
        for (int i = 0; i < board.length; ++ i) {
            for (int j = 0; j < board[0].length; ++ j) {
                backTrack(board, trie, i, j, ans);
            }
        }
        return new ArrayList<>(ans);
    }

    private void backTrack (char[][] board, Trie trie, int i, int j, Set<String> ans) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return;
        }
        if (!trie.children.containsKey(board[i][j])) {
            return;
        }

        // 判断是否有单词成功匹配
        char ch = board[i][j];
        Trie nowTrie = trie.children.get(ch);
        if (!"".equals(nowTrie.word)) {
            ans.add(nowTrie.word);
        }

        // 回溯
        board[i][j] = '#';
        for (int[] dir : dirs) {
            backTrack(board, nowTrie, i + dir[0], j + dir[1], ans);
        }
        board[i][j] = ch;
    }

    class Trie {
        String word;
        Map<Character, Trie> children;
        boolean isWord;
        public Trie () {
            word = "";
            children = new HashMap<>();
        }

        public void insert (String word) {
            Trie cur = this;
            for (int i = 0; i < word.length(); ++ i) {
                char ch = word.charAt(i);
                if (!cur.children.containsKey(ch)) {
                    cur.children.put(ch, new Trie());
                }
                cur = cur.children.get(ch);
            }
            cur.word = word;
        }
    }
}

09-11 不含连续1的非负整数

🧩 字典树 + 动态规划

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

        int pre = 0, res = 0;
        for (int i = 29; i >= 0; --i) {
            int val = 1 << i;
            if ((n & val) != 0) {
                res += dp[i + 1];
                if (pre == 1) break;
                pre = 1;
            } else {
                pre = 0;
            }

            if (i == 0) ++res;
        }
        return res;
    }
}

09-08 IPO

🧩 贪心+优先队列(银行家算法)

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; ++ i) {
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }
        Arrays.sort(arr, (x, y) -> x[0] - y[0]);

        int curr = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
        for (int i = 0; i < k; ++ i) {
            while (curr < n && arr[curr][0] <= w) {
                pq.add(arr[curr][1]);
                ++ curr;
            }
            if (!pq.isEmpty()) w += pq.poll();
            else break;
        }
        return w;
    }
}

09-06 用 Rand7() 实现 Rand10()

🧩 拒绝采样

class Solution extends SolBase {
    public int rand10() {
        int row, col, idx;
        do {
            row = rand7();
            col = rand7();
            idx = col + (row - 1) * 7;
        } while (idx > 40);
        return 1 + (idx - 1) % 10;
    }
}

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