競(jìng)賽鏈接

https://leetcode.cn/contest/biweekly-contest-113/

Q1：8039. 使數(shù)組成為遞增數(shù)組的最少右移次數(shù)

https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100
nums 中的整數(shù)互不相同。

競(jìng)賽時(shí)代碼——枚舉答案

因?yàn)閿?shù)據(jù)范圍很小，所以可以從小到大枚舉可能的答案。

class Solution {
    public int minimumRightShifts(List<Integer> nums) {
        int n = nums.size();
        // a 是排好序之后的數(shù)組，作為標(biāo)準(zhǔn)答案
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = nums.get(i);
        Arrays.sort(a);
        // 枚舉答案，即枚舉右移次數(shù)
        for (int x = 0; x < n; ++x) {
            boolean f = true;
            // 檢查這個(gè)答案下每一位是否移動(dòng)后相等
            for (int i = 0; i < n; ++i) {
                if (nums.get(i) != a[(i + x) % n]) {
                    f = false;
                    break;
                }
            }
            if (f) return x;
        }
        return -1;
    }
}

Q2：2856. 刪除數(shù)對(duì)后的最小數(shù)組長(zhǎng)度

https://leetcode.cn/problems/minimum-array-length-after-pair-removals/

提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
nums 是 非遞減 數(shù)組。

競(jìng)賽時(shí)代碼——貪心+優(yōu)先隊(duì)列

首先貪心地想，能匹配就匹配。
但是對(duì)于樣例 [2, 3, 5, 4] 來說，2 和 3 匹配之后，5 和 4就不能匹配了。
所以在 2 和 3 匹配之后，當(dāng)枚舉到 5 時(shí)，可以使用 5 替換掉 3，重新將 3 放入待匹配隊(duì)列中。

具體算法如下：

使用兩個(gè)優(yōu)先隊(duì)列維護(hù)已經(jīng)被枚舉過的數(shù)值。
pq1 維護(hù)等待匹配的較小數(shù)字，pq2 維護(hù)已經(jīng)匹配過的較大數(shù)字。

分情況討論：

1. 當(dāng)前數(shù)字比 pq1 中的數(shù)字大時(shí)，就將 pq1 中最小的數(shù)字刪除，兩者完成配對(duì)，當(dāng)前數(shù)字放入 pq2。
2. 當(dāng)前 pq1 中沒有數(shù)字，即前面沒有元素等待配對(duì)時(shí)，將當(dāng)前數(shù)字與 pq2 中最小的數(shù)字比較，如果 pq2 中的數(shù)字較小，就使用當(dāng)前數(shù)字替換 pq2 中的數(shù)字與前面配對(duì)，同時(shí) pq2 中這個(gè)最小的數(shù)字就多余了，將其放入 pq1 中等待后序的匹配。
3. 當(dāng)前數(shù)字無法處理時(shí)，就放入 pq1 等待后面出現(xiàn)更大的數(shù)字時(shí)刪除。

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int cnt = 0;    // 記錄刪除了幾個(gè)數(shù)字
        // pq1記錄較小的數(shù)字，pq2記錄較大的數(shù)字
        PriorityQueue<Integer> pq1 = new PriorityQueue<>(), pq2 = new PriorityQueue<>();
        for (int x: nums) {
            // 如果當(dāng)前數(shù)字比之前出現(xiàn)的 還沒被刪除過的數(shù)字 大
            if (!pq1.isEmpty() && x > pq1.peek()) {
                cnt += 2;
                pq1.poll();
                pq2.offer(x);
            } else {
                if (pq1.isEmpty() && !pq2.isEmpty() && x > pq2.peek()) {
                    // 如果較小的數(shù)字沒有了 且 當(dāng)前數(shù)字比已經(jīng)刪除的較大的數(shù)字大，就替換一下，將之前較大的數(shù)字放入較小的數(shù)字組中
                    pq1.offer(pq2.poll());
                    pq2.offer(x);
                } else pq1.offer(x);
            }
        }
        return nums.size() - cnt;
    }
}

解法2——貪心+二分查找 O ( log ? N ) O(\log{N}) O(logN)

https://leetcode.cn/problems/minimum-array-length-after-pair-removals/solutions/2446146/olog-n-tan-xin-er-fen-cha-zhao-pythonjav-t3qn/

當(dāng) $maxCnt?2<=n$ 時(shí)，最后的結(jié)果只和 n 的奇偶性有關(guān)。
所以我們只需要考慮 maxCnt 超過半數(shù)的情況，此時(shí)有序序列 nums 的中間位置元素 x 一定是出現(xiàn)次數(shù)最多的元素。
使用二分查找可以找到元素 x 出現(xiàn)的次數(shù)。

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size();
        int x = nums.get(n / 2);
        // 只需考慮maxCnt*2>n的情況，其它情況剩下的數(shù)字?jǐn)?shù)量只和n有關(guān)
        int maxCnt = lowerBound(nums, x + 1) - lowerBound(nums, x);
        return Math.max(maxCnt * 2 - n, n % 2);
    }

    // 找nums中最后一個(gè)比target小的位置
    public int lowerBound(List<Integer> nums, int target) {
        int l = -1, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums.get(mid) < target) l = mid;
            else r = mid - 1;
        }
        return l;
    }
}

Q3：6988. 統(tǒng)計(jì)距離為 k 的點(diǎn)對(duì)

https://leetcode.cn/problems/count-pairs-of-points-with-distance-k/

提示：
2 <= coordinates.length <= 50000
0 <= xi, yi <= 10^6
0 <= k <= 100

競(jìng)賽時(shí)代碼——異或性質(zhì)+哈希表

可以看到數(shù)據(jù)范圍很怪，是 50000，而 k 的數(shù)據(jù)范圍比較小，是 100。我們可以寫一個(gè)時(shí)間復(fù)雜度是 $O(n?k)$ 的算法。

將已經(jīng)枚舉過的 x 和 y 放入哈希表中。
對(duì)于一個(gè)新的 x 和 y，他要和另外的坐標(biāo)匹配之和為 k，最多有 k 中可能，即 —— 0 + k， 1 + (k - 1)，2 + (k - 2)，… ，k + 0。枚舉每種情況即可。

根據(jù)異或的性質(zhì)，有 x ^ (i ^ x) = i, y ^ ((k - i) & y) = k - i，因此與 坐標(biāo) (x, y) 可以匹配的坐標(biāo)是 (i ^ x, (k - i) ^ y)，其中 i 的取值范圍是 0 ~ k。

class Solution {
    public int countPairs(List<List<Integer>> coordinates, int k) {
        int ans = 0;
        Map<Integer, Map<Integer, Integer>> cnt = new HashMap<>();
        for (List<Integer> c: coordinates) {
            int x = c.get(0), y = c.get(1);
            // 枚舉 x 和 y 異或取值分配的所有可能。
            for (int i = 0; i <= k; ++i) {
                ans += cnt.getOrDefault(i ^ x, new HashMap<>()).getOrDefault((k - i) ^ y, 0);
            }
            // 將當(dāng)前坐標(biāo)放入哈希表
            if (!cnt.containsKey(x)) cnt.put(x, new HashMap<>());
            cnt.get(x).merge(y, 1, Integer::sum);
        }
        return ans;
    }
}

更多有關(guān)異或的題目可見：異或/XOR部分問題匯總

Q4：100041. 可以到達(dá)每一個(gè)節(jié)點(diǎn)的最少邊反轉(zhuǎn)次數(shù)

提示：
2 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= ui == edges[i][0] < n
0 <= vi == edges[i][1] < n
ui != vi
輸入保證如果邊是雙向邊，可以得到一棵樹。

競(jìng)賽時(shí)代碼——換根DP

第一次 dfs 求各個(gè)節(jié)點(diǎn)向下需要的反轉(zhuǎn)次數(shù)。
第二次 dfs 求答案。

class Solution {
    List<Integer>[] g;
    Set<Integer>[] t;
    int n;
    // 答案，該節(jié)點(diǎn)往下傳遞反轉(zhuǎn)的數(shù)量，
    int[] ans, cnt;
    
    public int[] minEdgeReversals(int n, int[][] edges) {
        this.n = n;
        ans = new int[n];
        cnt = new int[n];
        g = new ArrayList[n];
        t = new HashSet[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        Arrays.setAll(t, e -> new HashSet<>());
        
        for (int[] e: edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
            t[x].add(y);
        }
        
        dfs1(0, -1);        // 求cnt
        ans[0] = cnt[0];
        dfs2(0, -1);        // 求ans
        
        return ans;
    }
    
    public void dfs1(int x, int fa) {
        for (int y: g[x]) {
            if (y != fa) {
                dfs1(y, x);         // 先求cnt[y]
                if (!t[x].contains(y)) cnt[x]++;    // 如果x不能往y走,就+1
                cnt[x] += cnt[y];   
            }
        }
    }
    
    public void dfs2(int x, int fa) {
        for (int y: g[x]) {
            if (y != fa) {
                ans[y] = ans[x];    // 兩者的差別只取決于x和y之間邊的情況
                if (t[x].contains(y) && !t[y].contains(x)) ans[y]++;
                else if (!t[x].contains(y) && t[y].contains(x)) ans[y]--;
                dfs2(y, x);
            }
        }
    }
}

更多關(guān)于換根DP可見：
【算法】換根DP
【LeetCode每日一題合集】2023.7.10-2023.7.16（dfs & 換根DP）

相似題目——2581. 統(tǒng)計(jì)可能的樹根數(shù)目（???）

https://leetcode.cn/problems/count-number-of-possible-root-nodes/

提示：
edges.length == n - 1
2 <= n <= 10^5
1 <= guesses.length <= 10^5
0 <= ai, bi, uj, vj <= n - 1
ai != bi
uj != vj
edges 表示一棵有效的樹。
guesses[j] 是樹中的一條邊。
guesses 是唯一的。
0 <= k <= guesses.length

class Solution {
    List<Integer>[] g;
    Set<Long> s = new HashSet<Long>();  // 存儲(chǔ)各個(gè)guess
    // 節(jié)點(diǎn)數(shù)目，答案，k，節(jié)點(diǎn)0作為根節(jié)點(diǎn)猜對(duì)的數(shù)量
    int n, ans, k, cnt0;

    public int rootCount(int[][] edges, int[][] guesses, int k) {
        this.n = edges.length + 1;
        this.k = k;
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<Integer>());
        for (int[] edge: edges) {
            int x = edge[0], y = edge[1];
            g[x].add(y);
            g[y].add(x);
        }

        for (int[] guess: guesses) {
            // 將兩個(gè) 4 字節(jié)數(shù)壓縮成一個(gè) 8 字節(jié)數(shù)
            s.add((long) guess[0] << 32 | guess[1]);    
        }

        dfs(0, -1);
        reroot(0, -1, cnt0);
        return ans;
    }

    // 計(jì)算 0 為根節(jié)點(diǎn)時(shí)猜對(duì)的次數(shù)
    public void dfs(int x, int fa) {
        for (int y: g[x]) {
            if (y != fa) {
                if (s.contains((long) x << 32 | y)) ++cnt0;
                dfs(y, x);
            }
        }
    }

    // 計(jì)算各個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)時(shí)猜對(duì)的次數(shù)
    public void reroot(int x, int fa, int cnt) {
        if (cnt >= k) ++ans;        // 此時(shí)已經(jīng)找到了答案（至少有 k 個(gè)，所以是 >= k）
        for (int y: g[x]) {
            if (y != fa) {
                int c = cnt;
                if (s.contains((long) x << 32 | y)) --c;
                if (s.contains((long) y << 32 | x)) ++c;
                reroot(y, x, c);
            }
        }
    }
}

成績(jī)記錄

靠自己 AK 了！

文章來源地址http://www.zghlxwxcb.cn/news/detail-733250.html

到了這里，關(guān)于【力扣周賽】第 113 場(chǎng)雙周賽（貪心&異或性質(zhì)&換根DP）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！