1528、给你一个字符串 s 和一个 长度相同 的整数数组 indices 。
请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。
返回重新排列后的字符串。
示例 1：
输入：s = "codeleet", indices = [4,5,6,7,0,2,1,3]
输出："leetcode"
解释：如图所示，"codeleet" 重新排列后变为 "leetcode" 。
class Solution {
public:
string restoreString(string s, vector<int>& indices) {
string ans = s;
for(int i = 0; i < indices.size(); i++)
ans[indices[i]] = s[i];
return ans;
}
};
结果：
执行用时：16 ms, 在所有 C++ 提交中击败了79.32% 的用户
内存消耗：15.4 MB, 在所有 C++ 提交中击败了26.03% 的用户
1529、房间中有 n 个灯泡，编号从 0 到 n-1 ，自左向右排成一行。最开始的时候，所有的灯泡都是 关 着的。
请你设法使得灯泡的开关状态和 target 描述的状态一致，其中 target[i] 等于 1 第 i 个灯泡是开着的，等于 0 意味着第 i 个灯是关着的。
有一个开关可以用于翻转灯泡的状态，翻转操作定义如下：
- 选择当前配置下的任意一个灯泡（下标为 i ）
- 翻转下标从 i 到 n-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 描述的状态
简单版的开关问题
class Solution {
public:
int minFlips(string target) {
int ans = 0;
for(int i = 0; i < target.size(); i++)
if((target[i] - '0' + ans) % 2 == 1) ans++;
return ans;
}
};
结果：
执行用时：48 ms, 在所有 C++ 提交中击败了57.53% 的用户
内存消耗：9.5 MB, 在所有 C++ 提交中击败了52.94% 的用户
1530、给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。
示例 2：
输入：root = [1,2,3,4,5,6,7], distance = 3
输出：2
解释：好叶子节点对为 [4,5] 和 [6,7] ，最短路径长度都是 2 。但是叶子节点对 [4,6] 不满足要求，因为它们之间的最短路径长度为 4 。
dfs，求每个节点的左右子树的叶子深度，再存入数组中。完成dfs后，逆向遍历内部节点，比较左右子树的深度和是否<=distance，若小于则将二者节点数相乘。问题：数组耗内存，无法满足题目的条件。21 / 113 个通过测试用例。
/**
* 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:
vector<map<int,int>> lbuf;
vector<map<int,int>> rbuf;
int tail = 0;
void dfs(TreeNode * root, int id){
tail = max(tail, id);
if(root->left) {
dfs(root->left, id * 2);
for(auto &i:lbuf[id * 2]) lbuf[id][i.first + 1] += i.second;
for(auto &i:rbuf[id * 2]) lbuf[id][i.first + 1] += i.second;
}
if(root->right) {
dfs(root->right, id * 2 + 1);
for(auto &i:lbuf[id * 2 + 1]) rbuf[id][i.first + 1] += i.second;
for(auto &i:rbuf[id * 2 + 1]) rbuf[id][i.first + 1] += i.second;
}
if(root->right == nullptr && root->left == nullptr)
lbuf[id][0] = 1;
}
int countPairs(TreeNode* root, int distance) {
lbuf.resize(1e4);
rbuf.resize(1e4);
dfs(root, 1);
int ans = 0;
for(int i = tail / 2; i > 0; i--){
for(auto &j:lbuf[i]){
for(auto &k:rbuf[i]){
if(j.first + k.first <= distance) ans += j.second * k.second;
else break;
}
}
}
return ans;
}
};
修改：不需要存储每个节点的叶子深度信息，只存当前节点的信息，直接判断深度和，<=distance?，在dfs时给出结果
- 对树后序遍历 ，需要返回这个节点到其下方所有叶子节点的距离vector<int>
- 将这个节点的左子树所有叶子节点和右子树所有叶子节点凑对，是否<=distance
- 然后将所有叶子节点不超过distance的存入vector一起返回
/**
* 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 ans;
vector<int> dfs(TreeNode * root, int d){ // dfs返回值为，需要从其子情况中得到什么？
if(root == nullptr) return{};
if(root->left == nullptr && root->right == nullptr) return{0}; // 叶子
vector<int> vec;
auto left = dfs(root->left, d);
for(auto &i:left) if(++i <= d) vec.push_back(i);
auto right = dfs(root->right, d);
for(auto &i:right) if(++i <= d) vec.push_back(i);
for(auto &l:left)
for(auto &r:right)
if(l + r <= d) ans++;
return vec;
}
int countPairs(TreeNode* root, int distance) {
ans = 0;
dfs(root, distance);
return ans;
}
};
结果：
执行用时：156 ms, 在所有 C++ 提交中击败了48.85% 的用户
内存消耗：35.3 MB, 在所有 C++ 提交中击败了64.62% 的用户
1531、行程长度编码 是一种常用的字符串压缩方法，它将连续的相同字符（重复 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" 。
DP 周赛国服第一：
- dp[i][j]表示从前i个字符中最多选择j个字符进行删除。
- 如果删除字符i，则此时dp[i][j] = dp[i-1][j-1].
- 如果保留字符i, 则此时后续尽量选择保留与字符i相同的字符
**把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。
// dp[i][j] 从前i个字符中，最多选择j个删除
// 1)第i个字符删除 dp[i][j + 1] = min(dp[i][j + 1], dp[i-1][j]);
// 2)第i个字符保留 则往后查找，与第i个字符相同的字符，更新其dp
int dp[101][101];
int cal(int x){ // 将重复字符的数目s替换时，所占位数
if(x == 1) return 0;
else if(x < 10) return 1;
else if(x < 100) return 2;
else if(x < 1000) return 3;
else return 4;
}
class Solution {
public:
int getLengthOfOptimalCompression(string s, int k) {
memset(dp,0x3f,sizeof(dp)); //把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。
dp[0][0] = 0;
for(int i = 1; i <= s.size(); i++){ // 找s时s[i-1]
for(int j = 0; j <= k; j++){
// 删除第i个
dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][j]);
// 保留第i个,往后找和i同字符的dp更新
int cnt = 0, del = 0; // cnt计算与第i个字符相同的个数，del第i个数不同的个数(即删除的数目)
for(int p = i; p <= s.size(); p++){
if(s[i - 1] == s[p - 1]) cnt++;
else del++;
if(j + del <= k) dp[p][j + del] = min(dp[p][j + del], dp[i - 1][j] + 1 + cal(cnt));
}
}
}
return dp[s.size()][k];
}
};
例子：s = "aaabcccd" ; k = 2 ;
dp[1][0] : 1 dp[1][1] : 0 dp[1][2] : 1061109567
dp[2][0] : 2 dp[2][1] : 1 dp[2][2] : 0
dp[3][0] : 2 dp[3][1] : 2 dp[3][2] : 1
dp[4][0] : 3 dp[4][1] : 2 dp[4][2] : 2
dp[5][0] : 4 dp[5][1] : 3 dp[5][2] : 2
dp[6][0] : 5 dp[6][1] : 4 dp[6][2] : 3
dp[7][0] : 5 dp[7][1] : 4 dp[7][2] : 4
dp[8][0] : 6 dp[8][1] : 5 dp[8][2] : 4
结果：
执行用时：140 ms, 在所有 C++ 提交中击败了69.33% 的用户
内存消耗：6.1 MB, 在所有 C++ 提交中击败了93.39% 的用户 | 
转播
