On the shoulders of giants.

weekly-contest-199

重新排列字符串

给你一个字符串 s 和一个 长度相同 的整数数组 indices

请你重新排列字符串 s ,其中第 i 个字符需要移动到 indices[i] 指示的位置。

返回重新排列后的字符串。

示例 1:

输入:s = "codeleet", indices = [4,5,6,7,0,2,1,3]
输出:"leetcode"
解释:如图所示,"codeleet" 重新排列后变为 "leetcode" 。

示例 2:

输入:s = "abc", indices = [0,1,2]
输出:"abc"
解释:重新排列后,每个字符都还留在原来的位置上。

示例 3:

输入:s = "aiohn", indices = [3,1,4,2,0]
输出:"nihao"

示例 4:

输入:s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
输出:"arigatou"

示例 5:

输入:s = "art", indices = [1,0,2]
输出:"rat"

提示:

  • s.length == indices.length == n
  • 1 <= n <= 100
  • s 仅包含小写英文字母。
  • 0 <= indices[i] < n
  • indices 的所有的值都是唯一的(也就是说,indices 是整数 0n - 1 形成的一组排列)。
题解

模拟即可。

时间复杂度:\(O(n)\)

class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        string t = s;
        for(int i = 0; i < indices.size(); i++) {
            t[indices[i]] = s[i];
        }
        return t;
    }
};

灯泡开关 IV

房间中有 n 个灯泡,编号从 0n-1 ,自左向右排成一行。最开始的时候,所有的灯泡都是 着的。

请你设法使得灯泡的开关状态和 target 描述的状态一致,其中 target[i] 等于 1i 个灯泡是开着的,等于 0 意味着第 i 个灯是关着的。

有一个开关可以用于翻转灯泡的状态,翻转操作定义如下:

  • 选择当前配置下的任意一个灯泡(下标为 i
  • 翻转下标从 in-1 的每个灯泡

翻转时,如果灯泡的状态为 0 就变为 1,为 1 就变为 0

返回达成 target 描述的状态所需的 最少 翻转次数。

示例 1:

输入:target = "10111"
输出:3
解释:初始配置 "00000".
从第 3 个灯泡(下标为 2)开始翻转 "00000" -> "00111"
从第 1 个灯泡(下标为 0)开始翻转 "00111" -> "11000"
从第 2 个灯泡(下标为 1)开始翻转 "11000" -> "10111"
至少需要翻转 3 次才能达成 target 描述的状态

示例 2:

输入:target = "101"
输出:3
解释:"000" -> "111" -> "100" -> "101".

示例 3:

输入:target = "00000"
输出:0

示例 4:

输入:target = "001011101"
输出:5

提示:

  • 1 <= target.length <= 10^5
  • target[i] == '0' 或者 target[i] == '1'
题解

贪心,依次遍历记录后续灯被操作奇偶次。

时间复杂度:\(O(n)\)

class Solution {
public:
    int minFlips(string target) {
        int result = 0, s = 0;
        for(auto c : target) {
            if(c - '0' != s) result++, s ^= 1;
        }
        return result;
    }
};

好叶子节点对的数量

给你二叉树的根节点 root 和一个整数 distance

如果二叉树中两个 节点之间的 最短路径长度 小于或者等于 distance ,那它们就可以构成一组 好叶子节点对

返回树中 好叶子节点对的数量

示例 1:

输入:root = [1,2,3,null,4], distance = 3
输出:1
解释:树的叶节点是 3 和 4 ,它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。

示例 2:

输入:root = [1,2,3,4,5,6,7], distance = 3
输出:2
解释:好叶子节点对为 [4,5] 和 [6,7] ,最短路径长度都是 2 。但是叶子节点对 [4,6] 不满足要求,因为它们之间的最短路径长度为 4 。

示例 3:

输入:root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
输出:1
解释:唯一的好叶子节点对是 [2,5] 。

示例 4:

输入:root = [100], distance = 1
输出:0

示例 5:

输入:root = [1,1,1], distance = 2
输出:1

提示:

  • tree 的节点数在 [1, 2^10] 范围内。
  • 每个节点的值都在 [1, 100] 之间。
  • 1 <= distance <= 10
题解

递归,计算每颗子树的方案数。

时间复杂度:\(O(kn)\)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int result = 0;
    vector<int> search(TreeNode* root, int distance) {
        if(!root) return {};
        if(!root->left && !root->right) return {1};
        vector<int> lef_son = search(root->left, distance);
        vector<int> rig_son = search(root->right, distance);
        for(auto& lef : lef_son) {
            for(auto& rig : rig_son) {
                if(lef + rig <= distance) result++;
            }
        }
        vector<int> parent;
        for(auto& lef : lef_son) parent.push_back(lef + 1);
        for(auto& rig : rig_son) parent.push_back(rig + 1);
        return parent;
    }
    int countPairs(TreeNode* root, int distance) {
        search(root, distance);
        return result;
    }
};

压缩字符串 II

行程长度编码 是一种常用的字符串压缩方法,它将连续的相同字符(重复 2 次或更多次)替换为字符和表示字符计数的数字(行程长度)。例如,用此方法压缩字符串 "aabccc" ,将 "aa" 替换为 "a2""ccc" 替换为` "c3" 。因此压缩后的字符串变为 "a2bc3"

注意,本问题中,压缩时没有在单个字符后附加计数 '1'

给你一个字符串 s 和一个整数 k 。你需要从字符串 s 中删除最多 k 个字符,以使 s 的行程长度编码长度最小。

请你返回删除最多 k 个字符后,s 行程长度编码的最小长度

示例 1:

输入:s = "aaabcccd", k = 2
输出:4
解释:在不删除任何内容的情况下,压缩后的字符串是 "a3bc3d" ,长度为 6 。最优的方案是删除 'b' 和 'd',这样一来,压缩后的字符串为 "a3c3" ,长度是 4 。

示例 2:

输入:s = "aabbaa", k = 2
输出:2
解释:如果删去两个 'b' 字符,那么压缩后的字符串是长度为 2 的 "a4" 。

示例 3:

输入:s = "aaaaaaaaaaa", k = 0
输出:3
解释:由于 k 等于 0 ,不能删去任何字符。压缩后的字符串是 "a11" ,长度为 3 。

提示:

  • 1 <= s.length <= 100
  • 0 <= k <= s.length
  • s 仅包含小写英文字母
题解

动态规划,设 \(dp_{i,k,l}\) 为前 i 个字符,删除 k 个且第 i 个不删除使其有 l 个相同的该字符的最小编码长度。

有动态转移方程:

  • 如果 s[j] != s[i],\(dp_{i,k+i-j-1,1} = \min dp_{i,k,l}\)
  • 如果 s[j] == s[i],\(dp_{i,k+i-j-1,l+1} = \min (dp_{i,k,l}+cost_{l,l+1})\)

其中 $j < i$,cost(x,y) 为数 x 的位数与 数 y 的位数的差,我们还得在原字符串后面加一个无关字符。

时间复杂度:\(O(n^4)\)

const int N = 1E2 + 5, INF = 0x3f3f3f3f;
class Solution {
public:
    int dp[N][N][N];
    int cost(int x) {
        return (x <= 1 ? 0 : (x < 10 ? 1 : (x < 100 ? 2 : 3)));
    }
    int getLengthOfOptimalCompression(string s, int K) {
        s = s + "@";
        int n = s.length();
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0][0] = 0;
        for(int i = 1; i <= n; i++) {
            char c_y = s[i - 1];
            for(int j = 0; j < i; j++) {
                char c_x = (j > 0 ? s[j - 1] : '#');
                for(int l = 0; l <= j; l++) {
                    for(int k = 0; k + i - j - 1 <= K; k++) {
                        if(dp[j][k][l] == INF) continue;
                        int new_k = k + i - j - 1, new_l = 1, val = 1;
                        if(c_x == c_y) {
                            new_l = l + 1;
                            val = cost(l + 1) - cost(l);
                        }
                        dp[i][new_k][new_l] = min(dp[i][new_k][new_l], dp[j][k][l] + val);
                    }
                }
            }
        }
        int result = INF;
        for(int l = 1; l <= n; l++) {
            for(int k = 0; k <= K; k++) {
                result = min(result, dp[n][k][l]);
            }
        }
        return result - 1;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注