November

11-29 第K个最小的素数分数

🧩 优先队列(归并)

public class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        int[] cnt = new int[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[0] * y[1] - x[1] * y[0]);
        for (int i = 0; i < n; ++ i) {
            if (cnt[i] == i) continue;
            pq.add(new int[]{arr[cnt[i]], arr[i], i});
            cnt[i] ++;
        }

        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            k--;
            if (k == 0) {
                return new int[]{p[0], p[1]};
            }
            if (cnt[p[2]] != p[2]) {
                pq.add(new int[]{arr[cnt[p[2]]], arr[p[2]], p[2]});
                cnt[p[2]]++;
            }
        }
        return new int[0];
    }
}

🧩 二分(0ms)

func kthSmallestPrimeFraction_b(arr []int, k int) []int {
    l, r := 0., 1.
    n := len(arr)

    for {
        mid := (l + r) / 2
        x, y := 0, 1 // 记录最大分数
        i, cnt := -1, 0
        for j := 1; j < n; j++ {
            for float64(arr[i+1])/float64(arr[j]) < mid {
                i++
                if arr[i]*y > arr[j]*x {
                    x, y = arr[i], arr[j]
                }
            }
            cnt += i + 1
        }

        if cnt == k {
            return []int{x, y}
        } else if cnt < k {
            l = mid
        } else {
            r = mid
        }
    }
}

11-26 可怜的小猪

🧩 dp

func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
    if buckets == 1 {
        return 0
    }

    // 组合数
    c := make([][]int, buckets + 1)
    for i := range c {
        c[i] = make([]int, buckets + 1)
    }
    // 轮次
    iterations := minutesToTest / minutesToDie
    // f[i][j] 表示i个小猪 j轮次 所能确定的最大桶数量
    f := make([][]int, buckets)
    for i := range f {
        f[i] = make([]int, iterations + 1)
    }
    for i := 0; i < buckets; i ++ {
        f[i][0] = 1
    }
    for j := 0; j <= iterations; j ++ {
        f[0][j] = 1
    }

    // dp
    for i := 1; i < buckets; i ++ {
        // 计算组合数
        c[i][0] = 1
        for j := 1; j < i; j ++ {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
        }
        c[i][i] = 1

        // 求 f(i, j)
        for j := 1; j <= iterations; j ++ {
            for k := 0; k <= i; k ++ {
                f[i][j] += f[k][j - 1] * c[i][i - k]
            }
        }
        if f[i][iterations] >= buckets {
            return i
        }
    }
    return 0
}

🧩 香农熵(信息熵 wiki)

// (iterations + 1)^i ≥ buckets
func poorPigs(buckets int, minutesToDie int, minutesToTest int) int {
    states := minutesToTest / minutesToDie + 1
    return int(math.Ceil(math.Log(float64(buckets)) / math.Log(float64(states))))
}

11-24 从英文中重建数字

🧩 有意思的一道解方程题

func originalDigits(s string) string {
    cnt := make([]int, 26)
    nums := make([]int, 10)

    for _, v := range s {
        cnt[v - 'a'] ++
    }

    nums[0] = cnt['z' - 'a']
    nums[2] = cnt['w' - 'a']
    nums[4] = cnt['u' - 'a']
    nums[6] = cnt['x' - 'a']
    nums[8] = cnt['g' - 'a']

    nums[1] = cnt['o' - 'a'] - (nums[0] + nums[2] + nums[4])
    nums[3] = cnt['h' - 'a'] - nums[8]
    nums[5] = cnt['f' - 'a'] - nums[4]

    nums[7] = cnt['v' - 'a'] - nums[5]
    nums[9] = cnt['i' - 'a'] - (nums[5] + nums[6] + nums[8])

    ans := strings.Builder{}
    for i, v := range nums {
        ans.Write(bytes.Repeat([]byte{byte('0' + i)}, v))
    }
    return ans.String()
}

11-22 打乱数组

🧩 Fisher-Yates 洗牌算法 (模版题)

type Solution struct {
    nums, origin []int
}

func Constructor(nums []int) Solution {
    return Solution{nums, append([]int(nil), nums...)}
}

func (this *Solution) Reset() []int {
    copy(this.nums, this.origin)
    return this.nums

}

func (this *Solution) Shuffle() []int {
    n := len(this.nums)
    for i := range this.nums {
        j := i + rand.Intn(n - i)
        this.nums[i], this.nums[j] = this.nums[j], this.nums[i]
    }
    return this.nums
}

11-19 整数替换

🧩 贪心(最优)

func integerReplacement(n int) (ans int) {
    for n != 1 {
        if n % 2 == 0 {
            ans ++
            n /= 2
        } else if n % 4 == 1{
            ans += 2
            n /= 2
        } else if n % 4 == 3 {
            ans += 2
            if n == 3 {
                n = 1
            } else {
                n = n / 2 + 1
            }
        }
    }
    return
}

11-16 完美矩形

🧩 哈希表统计

func isRectangleCover(rectangles [][]int) bool {
    type point struct {x, y int}
    cnt := map[point]int{}
    area := 0
    rectMax := rectangles[0]

    for _, rect := range rectangles {
        area += getArea(rect)

        cnt[point{rect[0], rect[1]}] ++;
        cnt[point{rect[2], rect[3]}] ++;
        cnt[point{rect[0], rect[3]}] ++;
        cnt[point{rect[2], rect[1]}] ++;

        rectMax[0] = min(rect[0], rectMax[0])
        rectMax[1] = min(rect[1], rectMax[1])
        rectMax[2] = max(rect[2], rectMax[2])
        rectMax[3] = max(rect[3], rectMax[3])
    }

    if getArea(rectMax)  != area {
        return false
    }

    key1 := point{rectMax[0], rectMax[1]}
    key2 := point{rectMax[2], rectMax[3]}
    key3 := point{rectMax[0], rectMax[3]}
    key4 := point{rectMax[2], rectMax[1]}
    if cnt[key1] != 1 || cnt[key2] != 1 || cnt[key3] != 1 || cnt[key4] != 1 {
        return false
    }
    delete(cnt, key1)
    delete(cnt, key2)
    delete(cnt, key3)
    delete(cnt, key4)

    for _, r := range cnt {
        if r != 2 && r != 4 {
            return false
        }
    }
    return true
}

func getArea(r []int) int {
    return (r[3] - r[1]) * (r[2] - r[0])
}

11-15 灯泡开关

🧩 数学
1,2,...,n 中的完全平方数的个数为⌊sqrt(n)⌋

func bulbSwitch(n int) int {
    return int(math.Sqrt(float64(n) + 0.5));
}

11-14 键值映射

🧩 Trie + Map

type MapSum struct {
    head *TrieNode
    cnt map[string]int
}

type TrieNode struct {
    sub [26]*TrieNode
    val int
}

func Constructor() MapSum {
    return MapSum{&TrieNode{}, map[string]int{}}
}

func (this *MapSum) Insert(key string, val int)  {
    detla := val - this.cnt[key]
    this.cnt[key] = val
    cur := this.head
    for _, ch := range key {
        i := ch - 'a'
        if cur.sub[i] == nil {
            cur.sub[i] = &TrieNode{}
        }
        cur = cur.sub[i]
        cur.val += detla
    }
}


func (this *MapSum) Sum(prefix string) int {
    cur := this.head
    for _, ch := range prefix {
        i := ch - 'a'
        if cur.sub[i] == nil {
            return 0
        }
        cur = cur.sub[i]
    }
    return cur.val
}

11-12 猜数字大小 II

🧩 dp

func getMoneyAmount(n int) int {
    f := make([][]int, n + 1)
    for i := range f {
        f[i] = make([]int, n + 1)
    }

    for i := n - 1; i >= 1; i -- {
        for j := i + 1; j <= n; j ++ {
            f[i][j] = math.MaxInt32;
            for k := i; k < j; k ++ {
                f[i][j] = min(f[i][j], k + max(f[i][k - 1], f[k + 1][j]))
            }
        }
    }
    return f[1][n];
}

11-11 K个逆序对数组🔫

🧩 dp

class Solution {
    public int kInversePairs(int n, int k) {
        int mod = (int) 1e9 + 7;
        int[][] f = new int[n + 1][k + 1];
        f[1][0] = 1;

        // dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-i-1]
        // dp[i][j-1] =            dp[i-1][j-1] + ... + dp[i-1][j-1-(i-1-1)] + dp[i-1][j-1-i-1]
        // dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1-i-1]
        for (int i = 2; i <= n; ++ i) {
            for (int j = 0; j <= Math.min(k, i * (i - 1) / 2); ++ j) {
                // for (int x = Math.max(0, j - i + 1); x <= j; ++ x) {
                //     f[i][j] = (f[i][j] + f[i - 1][x]) % mod;
                // }
                f[i][j] = (int)(((long)f[i - 1][j] + (j < 1 ? 0 : f[i][j - 1]) - (j < i ? 0 : f[i - 1][j - i]) + mod) % mod);
            }
        }
        return f[n][k];
    }
}

🧩 滚动数组优化空间

class Solution {
    public int kInversePairs(int n, int k) {
        int mod = (int) 1e9 + 7;
        int[][] f = new int[2][k + 1];
        f[1][0] = 1;

        for (int i = 2; i <= n; ++ i) {
            for (int j = 0; j <= Math.min(k, i * (i - 1) / 2); ++ j) {
                f[i & 1][j] = (int)(((long)f[(i - 1) & 1][j] + (j < 1 ? 0 : f[i & 1][j - 1]) - (j < i ? 0 : f[(i - 1) & 1][j - i]) + mod) % mod);
            }
        }
        return f[n & 1][k];
    }
}

11-09 祖玛游戏🔫

🧩 BFS & 双指针

class Solution {
    public int findMinStep(String board, String hand) {
        // sort
        char[] chars = hand.toCharArray();
        Arrays.sort(chars);
        hand = new String(chars);

        Queue<State> q = new ArrayDeque<>();
        Set<String> visitedSet = new HashSet<>();
        // origin state
        State originState = new State(board, hand, 0);
        q.offer(originState);
        visitedSet.add(originState.toString());
        // BFS
        while (!q.isEmpty()) {
            State st = q.poll();
            String curB = st.board;
            String curH = st.hand;
            for (int i = 0; i <= curB.length(); ++ i) {
                for (int j = 0; j < curH.length(); ++ j) {
                    // 剪枝1: 当前放置球的颜色和上一个球的颜色相同
                    if (j > 0 && curH.charAt(j) == curH.charAt(j - 1)) continue;
                    // 剪枝2: 只在连续相同颜色的球的开头位置插入新球
                    if (i > 0 && curB.charAt(i - 1) == curH.charAt(j)) continue;
                    // 剪枝3: 只在以下两种情况放置新球 (优化效率最高的: 245ms -> 34ms)
                    boolean choose = false;
                    // 剪枝3.1: 当前球颜色与后面的球的颜色相同
                    if (i < curB.length() && curH.charAt(j) == curB.charAt(i)) choose = true;
                    // 剪枝3.2: 当前后颜色相同且与当前颜色不同时候放置球
                    if (i > 0 && i < curB.length() && curB.charAt(i) == curB.charAt(i - 1) && curH.charAt(j) != curB.charAt(i))
                        choose = true;

                    if (choose) {
                        String newB = clean(curB.substring(0, i) + curH.charAt(j) + curB.substring(i));
                        String newH = curH.substring(0, j) + curH.substring(j + 1);

                        if (newB.length() == 0) return st.step + 1;
                        State newSt = new State(newB, newH, st.step + 1);
                        if (visitedSet.add(newSt.toString())) q.offer(newSt);
                    }
                }
            }
        }
        return -1;
    }

    private String clean(String s) {
        String clean = cleanOnce(s);
        while (!s.equals(clean)) {
            s = clean;
            clean = cleanOnce(clean);
        }
        return clean;
    }

    private String cleanOnce(String s) {
        int i = 0, j = 0;
        StringBuilder sb = new StringBuilder();
        while (j < s.length()) {
            if (s.charAt(j) == s.charAt(i)) {
                ++ j;
            } else {
                if (j - i < 3) {
                    sb.append(s, i, j);
                }
                i = j;
            }
        }
        if (j - i < 3) {
            sb.append(s, i, j);
        }
        return sb.toString();
    }

    class State {
        String board;
        String hand;
        int step;

        public State(String board, String hand, int step) {
            this.board = board;
            this.hand = hand;
            this.step = step;
        }

        @Override
        public String toString() {
            return board + "-" + hand;
        }
    }
}

11-03 接雨水 II

🧩 BFS

class Solution {
    int[] dx = {-1, 0, 1, 0, -1};
    public int trapRainWater(int[][] heightMap) {
        int n = heightMap.length, m = heightMap[0].length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[2] - y[2]);
        boolean[][] vis = new boolean[n][m];
        // 初始化将最外一圈点入队
        for (int j = 0; j < m; ++ j) {
            pq.add(new int[]{0, j, heightMap[0][j]});
            pq.add(new int[]{n - 1, j, heightMap[n - 1][j]});
            vis[0][j] = true;
            vis[n - 1][j] = true;
        }
        for (int i = 1; i < n - 1; ++ i) {
            pq.add(new int[]{i, 0, heightMap[i][0]});
            pq.add(new int[]{i, m - 1, heightMap[i][m - 1]});
            vis[i][0] = true;
            vis[i][m - 1] = true;
        }
        // BFS
        int ans = 0;
        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            for (int i = 0; i < 4; ++ i) {
                int x = p[0] + dx[i], y = p[1] + dx[i + 1];
                if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y]) {
                    continue;
                }
                if (p[2] > heightMap[x][y]) {
                    ans += p[2] - heightMap[x][y];
                }
                pq.add(new int[]{x, y, Math.max(p[2], heightMap[x][y])});
                vis[x][y] = true;
            }
        }
        return ans;
    }
}

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