力扣第201场周赛

力扣第201场周赛

整理字符串

题意：

给你一个由大小写英文字母组成的字符串 s 。

一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件：

0 <= i <= s.length - 2
s[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 只包含小写和大写英文字母

思路：栈的模拟

class Solution {
public:stack<char>st;string makeGood(string s) {for(int i=0;i<s.size();i++){bool flag=false;if(st.size()&&((st.top()-32)==(int)s[i]||(st.top()+32)==(int)s[i])){flag=true;st.pop();}if(!flag)st.push(s[i]);}string res="";while(!st.empty()){res+&#p();st.pop();}reverse(res.begin(),d());return res;}
};

找出第 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

思路：看到n这么小，直接模拟就行了

class Solution {
public:string str[25];char findKthBit(int n, int k) {str[0]="0";for(int i=1;i<n;i++){string s=str[i-1];str[i]+=str[i-1]+"1";// cout<<str[i]<<"n";for(int j=0;j<s.size();j++)s[j]^=1;// cout<<s<<"n";reverse(s.begin(),s.end());str[i]+=s;// cout<<str[i]<<"n";}char res;for(int i=0;i<str[n-1].size();i++)if(i+1==k){res=str[n-1][i];break;}return res;}
};

1546和为目标值的最大数目不重叠非空子数组数目

给你一个数组 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

思路：完全可以用前缀和思想处理，因为非空不重叠，找到一个算一个。满足题意那么：sum[r]-sum[l-1]=target（1<=l<=r<=n）看到数据范围肯定得是O(n)做法，而这里有两个变量l，r我们把这个公式换一下–sum[r]-target=sum[l-1]，r直接通过遍历数组的时候给出，而我们每次都保存sum[l-1]就行。O(n)

class Solution {
public:unordered_set<int>st;int maxNonOverlapping(vector<int>& nums, int target) {st.insert(0);int res=0,sum=0;for(auto x:nums){sum+=x;if(st.find(sum-target)!&#d()){res++;sum=0;st.clear();}st.insert(sum);}return res;}
};

切棍子的最小成本

原题链接：传送门

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：

给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的 最小总成本 。

思路：跟石子合并一个道理，只不过他反过来了，变成了切割。通过获得相邻切割点的长度，统计到cnt数组中，然后板子搞一下就可以了

注意：值得注意的是我wa了好几发，其实把0和n放到cuts中可以直接避免少统计长度的。

class Solution {
public:int f[105][105],sum[105];int minCost(int n, vector<int>& cuts) {vector<int>cnt;sort(cuts.begin(),d());if(cuts.size()>1){for(int i=0;i<cuts.size();i++){if(i==0)cnt.push_back(cuts[0]-0);else if(i==cuts.size()-1){cnt.push_back(cuts[i]-cuts[i-1]);cnt.push_back(n-cuts[cuts.size()-1]);}else{cnt.push_back(cuts[i]-cuts[i-1]);}}}else cnt.push_back(cuts[0]-0),cnt.push_back(n-cuts[0]);int lens=cnt.size();// cout<<lens<<"n";for(int i=1;i<=lens;i++)sum[i]=sum[i-1]+cnt[i-1];for(int len=2;len<=lens;len++){for(int l=1;l+len-1<=lens;l++){int r=l+len-1;f[l][r]=0x3f3f3f3f;for(int k=l;k<r;k++)f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);}}return f[1][lens];}
};