LeetCode 题解哪家强？来GTA逛一逛！
我们的公众号：Grand Theft Algorithm
每天一道LeetCode题解
每周七种不一样的题型
每月六个周赛大礼包
只要你来，我们就包你学会！
题目1：1544. 整理字符串
思路：栈
签到题，多种解法。
维护一个栈，遍历字符串，每遍历到一个字符就将其与栈顶元素比较。
实现细节：
比较前要保证栈不为空。
最后从栈中提取时，要注意用 res = a.top() + res，而非 res += a.top()，因为是按照顺序入栈的，所以出栈顺序刚好相反。利用 res = a.top() + res 将每次出栈的元素放到字符串最前面，就是正确的顺序了。
代码：
class Solution {
public:
string makeGood(string s) {
stack<char> a;
int len = s.size();
a.push(s[0]);
for(int i = 1; i < len; i++) {
if(!a.empty() && abs(s[i] - a.top()) == 'a' - 'A') {
a.pop();
} else {
a.push(s[i]);
}
}
string res = "";
while(!a.empty()) {
res = a.top() + res; //逆序输出
a.pop();
}
return res;
}
};
复杂度分析：
遍历字符串时间复杂度O(N)，拼接结果字符串也是O(N)，故时间复杂度为O(N)；
维护了一个栈，空间复杂度为O(N)。
题目2：1545. 找出第 N 个二进制字符串中的第 K 位
思路：记录翻转次数
首先，设S(n)对应的位数len，则有：
且我们可以发现，第k个元素与第len + 1 - k个元素刚好是互为翻转，也即一个是0，一个是1，这是因为前一半与后一半互为反转的翻转。
既然这样，我们不需要算出给定 n 对应的 S(n) 究竟是什么样的字符串，而只需要找到当前这第 k 位的元素是怎么出来的就行了。
也就是说，如果这第 k 位元素在当前字符串S(n)的右半部分，则说明它是通过S(n - 1)拓展而来的，而根据我们上面的分析，其对应的 S(n - 1)中的位置是 len + 1 - k；如果在当前字符串的左半部分，说明其并未翻转，直接从S(n - 1)继承而来。
以此类推，我们就找到了一种方式进行递归，每次将S(n)简化到S(n - 1)，最终能够到达 S(1)，而在这个过程中，我们每次只需要记录要找的这个元素被翻转的次数即可。
实现细节：
外层while循环保证n自减，内层判断 k 与 len / 2的关系。
若 k == len / 2，根据题意知，该位置是某一次扩展时直接赋值的1，但是经过我们的分析，当前的k有可能是通过某一轮的 k = len + 1 - k得来的，所以在返回值得部分要加上翻转次数 cnt。
若 k > len / 2，则根据上面的分析，我们将翻转次数 cnt++，并将k挪到字符串的左半部分，也即 k = len + 1 - k，以便于下一轮循环的缩小范围。
代码：
class Solution {
public:
char findKthBit(int n, int k) {
int cnt = 0;
while(n) {
int len = (1 << n) - 1;
if(len == 1) {
return (char)(cnt % 2 + '0');
}
if(k > (len + 1) / 2) {
k = len + 1 - k;
cnt++;
} else if(k == (len + 1) / 2) {
return (char)((cnt + 1) % 2 + '0');
}
n--;
}
return (char)(cnt % 2 + '0');
}
};
复杂度分析：
外层循环嵌套复杂度O(N)，内层处理复杂度O(1)，故总时间复杂度为O(N)；
只用了简单变量，空间复杂度为O(1)。
题目3：1546. 和为目标值的最大数目不重叠非空子数组数目
思路：前缀和+哈希优化
最简单的方式是前缀和遍历，然后双重循环嵌套判断两点(i, j)之间的前缀和之差是否为target，时间复杂度为O(N^2)，但是本题给定的数据会超时，所以要想办法优化。
我们假设前缀和数组为A，由于前缀和的原理就是判断 A[j] - A[i] == target 是否成立，所以我们可以换一种方式，即判断 A[j] = A[i] + target是否成立，由于题目只要求计算这样的(i, j)对的数量，所以我们利用哈希表直接记录 A[i] + target 的值即可。
从前往后遍历的过程中，我们维护 pos 为当前前缀和，判断当前pos在哈希表中是否出现过，并将 pos + target 记录入哈希表。这样只需要一轮遍历就足够了。
实现细节：
维护unordered_map哈希表，记录pos + target值及其对应出现的位置。
维护res记录满足条件的区间数，也即(i, j)对的数量，维护pos记录当前前缀和。
每次找到满足条件的区间后，res++，由于要求区间不重叠，所以直接清空map。
最为关键的是初始化及每次清空后，要单独赋值mp[target] = 1，这样做的原因是在找到一组区间后，清空map，如果之后跟着的连续几个元素之和刚好为target，要保证能够记录该区间。
代码：
class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
unordered_map<int, int> mp;
mp[target] = 1;
int pos = 0;
int res = 0;
for(int x : nums) {
pos += x;
if(mp[pos] > 0) {
pos = 0;
mp.erase(mp.begin(), mp.end());
mp[target] = 1;
res++;
} else {
mp[pos + target]++;
}
}
return res;
}
};
复杂度分析：
数组遍历，时间复杂度为O(N)；
利用了哈希表，空间复杂度为O(N)。
题目4：1547. 切棍子的最小成本
思路：动态规划
设dp(i, j)表示以(i, j)为左右端点时，切割木棍的最小成本，显然(i, j)的取值范围只能是0，n以及cuts数组中的某一个数，所以我们将 cuts 数组扩展，加上最左边界0及最右边界n，表示可供切割的所有端点集合。
对于给定的左右端点(i, j)，切割木棍的最小成本可以通过遍历该区间内所有可供切割的端点，并更新最小值获得。这样通过递归调用的方式可以将整个问题转换为若干子问题求解。
实现细节：
边界条件：dp(i , i + 1) = 0，这是因为间距为1时无法再进行切割
初始化：dp(i, j) = INT_MAX，便于求解最小值
结合上面的分析，我们遍历(i, j)之间所有可供切割的节点k，并将目前的问题转化为在(i, k)与(k, j)上分别求解最小花费的子问题，且对于节点 k 的切割所需花费为 cuts[j] - cuts[i]，所以可以列出动态转移方程如下：
为便于扩展cuts数组，用新数组a来替代。
为了减少重复计算，利用二维数组记录所有已经求出的dp(i)(j)。
代码：
int a[105];
int dp[105][105];
int solve(int l, int r) {
if (dp[l][r] != INT_MAX) return dp[l][r];
if (r - l == 1) {
dp[l][r] = 0;
return dp[l][r];
}
for(int i = l + 1; i <= r - 1; i++) {
dp[l][r] = min(dp[l][r], solve(l, i) + solve(i, r) + a[r] - a[l]);
}
return dp[l][r];
}
class Solution {
public:
int minCost(int n, vector<int>& cuts) {
sort(cuts.begin(), cuts.end());
int len = cuts.size();
for(int i = 1; i <= len; i++) {
a[i] = cuts[i - 1];
}
a[0] = 0;
a[len + 1] = n;
for(int i = 0; i <= len + 1; i++) {
for(int j = 0; j <= len + 1; j++) {
dp[i][j] = INT_MAX;
}
}
int tmp = solve(0, len + 1);
return tmp;
}
};</pre>
复杂度分析：
利用记忆化动态规划，每个(i, j)对对应的最小花费最多只会被计算一次，总时间复杂度为O(len^2)；
空间复杂度为O(len^2)。
公众号
Leetcode题目不知道从何下手？
面试笔试的算法题老是没有思路？
各类比赛打完了很多题还是不会做？
欢迎来我们的公众号：Grand Theft Algorithm
每天一道Leetcode题解，一起交流学习！
我们的题解包含《程序员面试金典》系列、回溯算法、动态规划、图论、树、链表等，一天一个tag！
周赛、双周赛、牛客专题赛、Codeforce等级赛，只要你想看，我们就给你讲明白！
只有你想不到，没有我们写不到！
欢迎大家关注、点赞！一起进步，一起学习，就在我们的公众号：Grand Theft Algorithm
