leetcode201场周赛
T1：整理字符串，T2：找出第N个二进制字符串中的第K位， T3:和为目标值的最大数目不重叠非空子数组数目，T4：切棍子的最小成本（区间dp）
T1：整理字符串
给你一个由大小写英文字母组成的字符串 s 。
一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件：
0 <= i <= s.length - 2s[i]是小写字符，但s[i + 1]是相同的大写字符；反之亦然 。
请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。
请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。
注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。
示例 1：
输入：s = "leEeetcode"
输出："leetcode"
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 。
示例 2：
输入：s = "abBAcC"
输出：""
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""
示例 3：
输入：s = "s"
输出："s"
提示：
1 <= s.length <= 100
s 只包含小写和大写英文字母由于该问题的大写字母只能与其相邻的对应的小写字母相消，因此无论先消哪一对，最终的结果总是相同的。
因此尝试着消N / 2次，以O（N^2）的时间复杂度求解：
class Solution {
public String makeGood(String s) {
int N = s.length();
boolean[] delet = new boolean[N];
for(int i = 0; i < N / 2; i++){
for(int j = 0; j < N - 1;){
if(delet[j]){
j++;
continue;
}
int next = j + 1;
// 找到下一个未删除的元素
while(next < N && delet[next]){
next++;
}
if(next == N){
break;
}
if(Math.abs(s.charAt(j) - s.charAt(next)) == 'a' - 'A'){
delet[j] = true;
delet[next] = true;
break;
}else{
j = next;
}
}
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < N; i++){
if(!delet[i]){
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}T2：找出第N个二进制字符串中的第K位
给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下：
S1 = “0”
当 i > 1 时，Si = Si-1 + “1” + reverse(invert(Si-1)) 其中 + 表示串联操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（0 变为 1，而 1 变为 0）例如，符合上述描述的序列的前 4 个字符串依次是：
S1 = "0"
S2 = "011"
S3 = "0111001"
S4 = "011100110110001"
请你返回 Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。
示例 1：
输入：n = 3, k = 1
输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0" 。
示例 2：
输入：n = 4, k = 11
输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1" 。
示例 3：
输入：n = 1, k = 1
输出："0"
示例 4：
输入：n = 2, k = 3
输出："1"
提示：
1 <= n <= 20
1 <= k <= 2n - 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-kth-bit-in-nth-binary-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。对于该问题直接使用一list模拟即可。
class Solution {
public char findKthBit(int n, int k) {
List<Character> ans = new ArrayList<>((int)Math.pow(2,n));
ans.add('0');
for(int i = 2; i <= n; i++){
int leng = ans.size();
ans.add('1');
for(int j = leng - 1; j >= 0; j--){
ans.add(ans.get(j) == '1' ? '0' : '1');
}
}
return ans.get(k - 1) ;
}
}T3:和为目标值的最大数目不重叠非空子数组数目
给你一个数组 nums 和一个整数 target 。
请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。
示例 1：
输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。
示例 2：
输入：nums = [-1,3,5,1,4,2,-9], target = 6
输出：2
解释：总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。
示例 3：
输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出：3
示例 4：
输入：nums = [0,0,0], target = 0
输出：3
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。该问题由于存在负值不能使用滑动窗口毛毛虫算法求解。
类似两数之和问题，定义sum为当前的前缀和，right为当前能取得的最小下标，使用一HashMap存储前缀和及其最新的下标（key ： sum ，value ： index）。
遍历过程中判断sum - target是否存在于map中，若在map中则判断其下标是否过期（过期指的是 get(sum - target) <= right - 1）若未过期则从get(sum - target) + 1 到当前位置可以组成一个target，此时更新right为当前位置的下一个位置。
class Solution {
public int maxNonOverlapping(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int left = 0;
int sum = 0;
int ans = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
if(!map.containsKey(sum - target)){
map.put(sum, i);
continue;
}
int pre = map.get(sum - target);
if(pre >= left - 1){
ans++;
left = i + 1;
}
map.put(sum, i);
}
return ans;
}
}T4：切棍子的最小成本
有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：
给你一个整数数组 cuts ，其中 cutsi 表示你需要将棍子切开的位置。
你可以按顺序完成切割，也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。
示例 1：
输入：n = 7, cuts = [1,3,4,5]
输出：16
解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：
第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。
示例 2：
输入：n = 9, cuts = [5,6,1,4,2]
输出：22
解释：如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4，6，5，2，1] 的总成本 = 22，是所有可能方案中成本最小的。
提示：
2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
cuts 数组中的所有整数都 互不相同
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-cost-to-cut-a-stick
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。这题应该是最简单的T4了吧，不就是石子合并问题嘛。
首先按照需要切割的位置计算最终切割后每一段的长度，转化为合并石子问题，该问题是一道典型的区间dp问题。
定义dpi 为从i位置木棍合并到j位置的木棍需要的最小花费。
对于dpi的计算 列举出i到j中所有的可以切割的位置，然后凭借该切割位置将问题转化为两个小区间的问题，最后取其中花费最小的切割位置。
转移方程：
上述公式中sumi:j为计算从i位置到j位置的木棍总长。
baseline:
$$
dpi =
\begin{cases}
0, \qquad i = j
\\
- \infty, \quad else \end{cases} $$ 代码如下：
class Solution {
public int minCost(int n, int[] cuts) {
Arrays.sort(cuts);
int pre = 0;
int[] len = new int[cuts.length + 1];
for(int i = 0; i < cuts.length; i++){
len[i] = cuts[i] - pre;
pre = cuts[i];
}
int N = len.length;
len[N - 1] = n - pre;
int[] sum = new int[N + 1];
for(int i = 1; i <= N; i++){
sum[i] = sum[i - 1] + len[i - 1];
}
// dp[i][j]为切割i ~ j部分花费的代价
int[][] dp = new int[N][N];
for(int i = N - 1; i >= 0; i--){
for(int j = i + 1; j < N; j++){
dp[i][j] = Integer.MAX_VALUE;
for(int k = i; k < j; k++){
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j + 1] - sum[i]);
}
}
}
return dp[0][N - 1];
}
}对于区间dp感兴趣的朋友还可以看看我之前写的扎气球问题。
腾讯云开发者
