[Leetcode Weekly Contest]261

連結：LeetCode

[Leetcode]2027. 轉換字元串的最少操作次數

給你一個字元串 s ，由 n 個字元組成，每個字元不是 'X' 就是 'O' 。

一次 操作 定義為從 s 中選出 三個連續字元 并将選中的每個字元都轉換為 'O' 。注意，如果字元已經是 'O' ，隻需要保持 不變 。

傳回将 s 中所有字元均轉換為 'O' 需要執行的 最少 操作次數。

周遊即可。

class Solution {
    public int minimumMoves(String s) {
        int i = 0, n = s.length();
        int res = 0;
        while(i<n) {
            if(s.charAt(i) == 'X') {
                res ++;
                i += 3;
            }
            else {
                i ++;
            }
        }
        return res;
    }
}
           

[Leetcode]2028. 找出缺失的觀測資料

現有一份 n + m 次投擲單個 六面 骰子的觀測資料，骰子的每個面從 1 到 6 編号。觀測資料中缺失了 n 份，你手上隻拿到剩餘 m 次投擲的資料。幸好你有之前計算過的這 n + m 次投擲資料的 平均值 。

給你一個長度為 m 的整數數組 rolls ，其中 rolls[i] 是第 i 次觀測的值。同時給你兩個整數 mean 和 n 。

傳回一個長度為 n 的數組，包含所有缺失的觀測資料，且滿足這 n + m 次投擲的 平均值 是 mean 。如果存在多組符合要求的答案，隻需要傳回其中任意一組即可。如果不存在答案，傳回一個空數組。

k 個數字的 平均值 為這些數字求和後再除以 k 。

注意 mean 是一個整數，是以 n + m 次投擲的總和需要被 n + m 整除。

mean * (m + n) 求總數。

sum(rolls) 求已經有的數量。

sum = mean * (m+n) - sum(rolls) 剩下需要補充的平均配置設定就行。< N * 1 或者 > N * 6 則不可能有合法配置設定。

class Solution {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length, sum_ = 0;
        for(var roll:rolls) {
            sum_ += roll;
        }
        int rest = (m+n) * mean - sum_;
        if(rest < n || rest > 6 * n) {
            return new int[0];
        }
        int dev = rest / n;
        int restNum = rest % n;
        int[] res = new int[n];
        Arrays.fill(res,dev);
        for(int i=0;i<restNum;++i) {
            res[i] += 1;
        }
        return res;
    }
}
           

[Leetcode]2029. 石子遊戲 IX

Alice 和 Bob 再次設計了一款新的石子遊戲。現有一行 n 個石子，每個石子都有一個關聯的數字表示它的價值。給你一個整數數組 stones ，其中 stones[i] 是第 i 個石子的價值。

Alice 和 Bob 輪流進行自己的回合，Alice 先手。每一回合，玩家需要從 stones 中移除任一石子。

如果玩家移除石子後，導緻 所有已移除石子 的價值 總和 可以被 3 整除，那麼該玩家就 輸掉遊戲 。

如果不滿足上一條，且移除後沒有任何剩餘的石子，那麼 Bob 将會直接獲勝（即便是在 Alice 的回合）。

假設兩位玩家均采用 最佳 決策。如果 Alice 獲勝，傳回 true ；如果 Bob 獲勝，傳回 false 。

給你一個字元串 word ，如果 word 可以被放入 board 中，請你傳回 true ，否則請傳回 false 。

由于我們隻關心總和能否被 33 整除，我們可以将 \(\textit{stones}\) 按照模 3 的結果分為 3 組，即 0、1 和 2。

根據題意，第一回合不能移除 0，否則直接輸掉遊戲，是以第一回合隻能移除 1 或者 2。我們可以枚舉這兩種情況，如果其中一種可以讓 Alice 獲勝就傳回 \(\texttt{true}\)，否則傳回 \(\texttt{false}\)

下面以第一回合移除 1 來說明。在不考慮移除 0 的前提下，後面的移除由于要滿足總和不能被 3 整除，是以移除的石子是固定的，整體構成一個 \(112121212\dots\) 循環的序列。

對于 0，由于移除之後不會改變總和模 33 的結果，是以不會改變後續 11 和 22 的移除順序，是以我們可以在序列的任意非開頭位置插入 0。兩人為了不讓自己輸掉，必然會按照上述序列進行，直到沒有石子，或某一方隻能移除導緻總和被 3 整除的石子時分出勝負。是以我們需要求出讓總和不能被 3 整除的最大的回合數，這相當于 \(112121212\dots\) 序列的最長長度，加上 0 的個數。

若該回合數為奇數，且還有剩餘石子，那麼下一回合要輪到 Bob 移除石子，且他隻能移除一枚讓總和被 3 整除的石子，于是 Alice 獲勝；否則 Bob 獲勝。

對于第一回合移除 2 的情況，同樣會構成一個 \(221212121\dots\) 循環的序列，做法同上。

class Solution {
    public boolean stoneGameIX(int[] stones) {
        HashMap<Integer,Integer> hm = new HashMap<>();
        for(var stone:stones)
        {
            var key =stone % 3;
            hm.put(key,hm.getOrDefault(key,0)+1);
        }
        hm.put(0,hm.getOrDefault(0,0)%2);
        int n = 0;
        for(var val:hm.values()) n += val;
        boolean res = getRes(n,hm,1) || getRes(n,hm,2);
        return res;
    }

    public boolean getRes(int n, HashMap hm, int first) {
        var dic = (HashMap<Integer,Integer>)hm.clone();
        if(dic.getOrDefault(first,0) == 0) {
            return false;
        }
        dic.put(first,dic.get(first)-1);
        var cur = first;
        for(int i=0;i<n-1;++i) {
            int need_to_remove;
            if(dic.getOrDefault(0,0)>0) {
                need_to_remove = 0;
            }
            else if(dic.getOrDefault(cur,0)>0) {
                need_to_remove = cur;
            }
            else {
                return (i & 1) == 0;
            }
            cur  = (cur + need_to_remove) % 3;
            dic.put(need_to_remove,dic.getOrDefault(need_to_remove,0)-1);
        }
        return false;
    }
}
           

[Leetcode]2030. 含特定字母的最小子序列

給你一個字元串 s ，一個整數 k ，一個字母 letter 以及另一個整數 repetition 。

傳回 s 中長度為 k 且 字典序最小 的子序列，該子序列同時應滿足字母 letter 出現 至少 repetition 次。生成的測試用例滿足 letter 在 s 中出現 至少 repetition 次。

子序列 是由原字元串删除一些（或不删除）字元且不改變剩餘字元順序得到的剩餘字元串。

字元串 a 字典序比字元串 b 小的定義為：在 a 和 b 出現不同字元的第一個位置上，字元串 a 的字元在字母表中的順序早于字元串 b 的字元。

• 從原序列中删去n-k個元素，之後得到res
• res中有至少repetition 個letter
• res是滿足上面兩點要求的集合中字典序最小的。

class Solution {
    public String smallestSubsequence(String s, int k, char letter, int repetition) {
        int n = s.length();
        int[] suffix_cnt = new int[n];
        int acc = 0;
        for(int i=n-1;i>=0;--i) {
            if(s.charAt(i)==letter) acc ++;
            suffix_cnt[i] = acc;
        }
        Deque <Character> stk = new LinkedList<>();
        int x = 0;
        for(int i=0;i<n;++i) {
            int y = x;
            while((stk.size()>0) && (stk.size()+(n-i-1)>=k) && (s.charAt(i) < stk.peek())) {
                if(stk.peek() == letter) y--;
                if(y+suffix_cnt[i]<repetition) break;
                stk.pop();
                x = y;
            }
            if(stk.size()<k) {
                if(s.charAt(i) == letter || k - stk.size() > repetition - x) {
                    stk.push(s.charAt(i));
                    if (s.charAt(i) == letter) x++;
                }
            }
        }
        StringBuilder SB = new StringBuilder();
        while (!stk.isEmpty())
        {
            SB.append(stk.pollLast());
        }
        return SB.toString();
    }
}