重新排列字符串

class Solution {
public:
    vector<char> res;
    string restoreString(string s, vector<int>& indices) {
        int n = s.size();
        res.resize(n);
        for(int i = 0;i < n;i ++ )
            res[indices[i]] = s[i];
        string ans;
        for(auto &c : res) ans += c;
        return ans;
    }
};

灯泡开关

这个题其实还可以设置一个初始状态不为 0 的

class Solution {
public:
    int minFlips(string target) {
        bool flag = false;
        int res = 0;
        for(auto &c : target)
            if((c - '0') ^ flag) res ++ , flag ^= 1;
        return res;
    }
};

好叶子的数量

本来以为这是一个点分治的题目
但是这个只是统计叶子 而且边权都是 1 所以没必要用点分治
直接 dfs 即可

const int N = 1050 + 50;
int ans;
int cnt[N][15]; // cnt[i][j] 表示距离第 i 个节点为 j 的叶子数量
int tot;
class Solution {
public:
    int dfs(TreeNode* root, int d){
        int x = ++ tot; // 给每个节点一个编号
        int l = 0, r = 0;
        if(root->left) l = dfs(root->left, d);
        if(root->right) r = dfs(root->right, d);
        // 叶子
        if(!l && !r) { cnt[x][0] = 1; return x; }

        if(l > 0 && r > 0){
            for(int i = 0;i <= d;i ++ )
                for(int j = 0;j <= d;j ++ )
                    if(i + j + 2 <= d) ans += cnt[l][i] * cnt[r][j];
        }

        for(int i = 0;i <= d;i ++ )
            cnt[x][i + 1] = cnt[l][i] + cnt[r][i];

        return x;
    }
    int countPairs(TreeNode* root, int distance) {
        ans = tot = 0;
        memset(cnt, 0, sizeof cnt);
        dfs(root, distance);
        return ans;
    }
};

压缩字符串II

// 加个 滚动数组优化不然会 tle qwq
const int N = 110;
// dp[i][j][c][k] 表示 上一个是 i 上一个删除了 j 个字符 上一个的最后一个字母是 c 且长度为 l 的最小值
int dp[2][N][27][N];

class Solution {
public:
    int getLengthOfOptimalCompression(string s, int k) {
        int n = s.size();
        memset(dp, 0x3f, sizeof dp);
        dp[0][1][26][0] = 0;
        dp[0][0][s[0] - 'a'][1] = 1;
        s = s + '%';
        int ans = 0x3f3f3f3f;
        for(int i = 0;i < n;i ++ ){
            int c = s[i + 1] - 'a';
            memset(dp[i + 1 & 1], 0x3f, sizeof dp[0]);
            for(int j = 0;j <= k;j ++ ){
                for(int x = 0;x <= 26;x ++ ){
                    for(int l = 0;l <= n;l ++ ){
                        if(i == n - 1){
                            ans = min(ans, dp[i & 1][j][x][l]);
                            continue;
                        }
                        if(dp[i & 1][j][x][l] == 0x3f3f3f3f) continue;
                        if(j + 1 <= k) dp[i + 1 & 1][j + 1][x][l] = min(dp[i + 1 & 1][j + 1][x][l], dp[i & 1][j][x][l]);
                        if(c == x){
                            int w = 0;
                            if (l == 0 || l == 1 || l == 9 || l == 99) w = 1;
                            if(dp[i & 1][j][x][l] == 0x3f3f3f3f) continue;
                            dp[i + 1 & 1][j][x][l+1] = min(dp[i + 1 & 1][j][x][l+1], dp[i & 1][j][x][l] + w);
                        }
                        else{
                            if(dp[i & 1][j][x][l] == 0x3f3f3f3f) continue;
                            dp[i + 1 & 1][j][c][1] = min(dp[i + 1 & 1][j][c][1], dp[i & 1][j][x][l] + 1);
                        }
                    }
                }
            }
        }
        return ans;
    }
};