2109. 向字符串添加空格
题解
本题按照题意在对应的位置插入空格并构造新字符串，可以创建一个空的新字符串，在扫描原字符串的同时在给定的下标位置插入空格，再继续遍历原字符串，用一个变量记录原字符串遍历到的下标。当遍历到的下标满足要插入空格的位置时在新字符串中插入一个空格，继续遍历并复制原始字符串。
代码
class Solution {
public:
string addSpaces(string s, vector<int>& spaces) {
string news = "";
int index = 0;
int n = s.size();
for(const int& space : spaces){
while(index != space){
news.push_back(s[index]);
index++;
}
news.push_back(' ');
}
news.append(s,index,n);
return news;
}
};
1 个赞
2825. 循环增长使字符串子序列等于另一个字符串
题解
本题仍是字符串匹配问题，只是做了一些小变动。因为题目中允许我们将指定位置上的字符变换到下一个字符，因此在str1中匹配str2的子序列时，除了和str2中的字符完全相同外，在字母表上比str2的字符小一个位置的字符也可以。
则用指针p遍历str2字符串，并同时用指针q遍历str1字符串直到碰到str2[p]和str1[q]相同或等于str1[q]+1。此时成功匹配str2中的一个字符，移动指针p至下一位，继续用q向后遍历str1重复上述过程，直到将str2完全匹配完返回true或str1已经到末尾但str2仍未完全匹配则返回false。
代码
class Solution {
public:
bool canMakeSubsequence(string str1, string str2) {
int m = str1.size();
const char map[26] = {'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y'};
int str1index = 0;
for (const char& ch : str2){
while(ch != str1[str1index] && map[ch-'a'] != str1[str1index]){
if(str1index < m){
str1index++;
}else{
return false;
}
}
str1index++;
}
return true;
}
};
2337. 移动片段得到字符串
题解
本题是一道字符串问题，对于这种问题我们无需考虑将start变为target的具体移动步骤，只需考虑什么条件下一定能通过移动将start中的字符移动为target中的某个字符。对于字符’L’来说，只要target中存在一个’L’在start中这个’L’的相同或者左侧位置并且二者之间的位置全部为空格，就可以将start的’L’移动到target中对应的’L’处，'R’同理。
则可以同时用两个指针分别遍历target和start，每当在target中遇到一个非空字符时，若为’L’则移动start中的指针直到找到一个’L’，若start中的’L’的下标和target中’L’下标相同或者更大（即start中的’L’在target中对应’L’的右侧，这样就可以通过左移移动到target中对应的’L’）。对’R’同理，注意target中L R出现的顺序要与start中相同且start中的非空格字符满足上述的下标条件（'L’在target右侧，'R’在target左侧）。如果全部满足条件则说明可以转换成target，否则不可以。
代码
class Solution {
public:
bool canChange(string start, string target) {
int startindex = 0;
int targetindex = 0;
int n = start.size();
for(targetindex=0;targetindex<n;targetindex++){
if (target[targetindex] == '_'){
continue;
}else if(target[targetindex] == 'L'){
while(start[startindex] == '_'){
startindex++;
}
if (start[startindex] == 'R' || startindex<targetindex || startindex >= n){
return false;
}
startindex++;
}else{
while(start[startindex] == '_'){
startindex++;
}
if (start[startindex] == 'L' || startindex>targetindex || startindex >= n){
return false;
}
startindex++;
}
}
while(startindex<n){
if(start[startindex] != '_'){
return false;
}
startindex++;
}
return true;
}
};
2554. 从一个范围内选择最多整数 I
题解
本题先将banned数组排序，再根据有序的banned数组中的数字和n的范围限制将banned数组中相邻两个数字中间的数字段的全部数字加和，与maxSum比较，小于maxSum则说明这些数字可以全部取得，加到计数总数中，否则使用二分法找到这个数字区间内满足n的范围限制且加和后和小于等于maxSum的最大数字，累加计数即得最终结果。
代码
class Solution {
public:
int maxCount(vector<int>& banned, int n, int maxSum) {
sort(banned.begin(), banned.end());
vector<int> nums;
nums.push_back(0);
for (int x : banned) {
if (x <= n) nums.push_back(x);
}
nums.push_back(n + 1);
int ans = 0;
long long sum = 0;
for (int i = 1; i < nums.size(); i++) {
int left = nums[i-1] + 1;
int right = nums[i] - 1;
if (left > right || left > n) continue;
right = min(right, n);
long long count = right - left + 1;
long long rangeSum = (left + right) * count / 2;
if (sum + rangeSum <= maxSum) {
ans += count;
sum += rangeSum;
} else {
int low = left;
int high = right;
while (low <= high) {
int mid = low + (high - low) / 2;
count = mid - left + 1;
rangeSum = (left + mid) * count / 2;
if (sum + rangeSum <= maxSum) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if (high >= left) {
count = high - left + 1;
ans += count;
sum += (left + high) * count / 2;
}
break;
}
}
return ans;
}
};
1760. 袋子里最少数目的球
题解
本题起初想到计算出最终能分出的袋子的总数，将球的总数求和再按照尽可能均分的方式将球均分到袋子中，但这种思路在本题并不适用，因为均分后的最少的球的个数可能比当前某些袋子中已有的球的个数要多，而题目只允许将袋子中的球分开而不允许向袋子中添加球，因此这种情况是不符合题目要求的。我们只能通过模拟拆分的方式来模拟球的拆分过程最终得到每个袋子中球的个数。
既然只能通过模拟拆分方式来得到最终每个袋子中球的分配，那么必须要对拆分过程进行一个限制，这里我们可以限制允许拆分出来的每个袋子中球的最大个数，可以从具有最多球的袋子中球的个数减一开始，依次减一作为最大个数限制并模拟拆分过程来判断最终能否在满足我们自己定义的限制条件下拆分成功。如果成功，则可继续减小限制，不成功则不能继续减小限制。
一个一个的减少个数限制效率比较低，此时发现其实“能否在最大个数限制下成功拆分”是一个二元条件，具有一个临界值，即比该临界个数大的个数限制必定都可以成功拆分，而小于该临界个数的个数限制必定不能成功拆分。因此可以使用二分法找到这个临界限制，这个临界限制就是我们最终要求的最小可能惩罚。
代码
class Solution {
public:
// 检查在给定的最大球数限制下是否可以完成分割
bool canSplit(vector<int>& nums, int maxOperations, int limit) {
int operations = 0;
for (int num : nums) {
operations += (num - 1) / limit;
if (operations > maxOperations) {
return false;
}
}
return true;
}
int minimumSize(vector<int>& nums, int maxOperations) {
int maxNum = 0;
for (int num : nums) {
maxNum = max(maxNum, num);
}
int left = 1;
int right = maxNum;
int result = maxNum;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canSplit(nums, maxOperations, mid)) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
};
2054. 两个最好的不重叠活动
题解
本题只需要取两个互不重叠的事件并得到二者的值的和，因此我们只需考虑某个事件a开始时间之前已经结束的所有事件中价值最大的事件，并将其和事件a的价值加和即为事件a与其前面可以共同取得的事件的价值和的最大值。
为什么不考虑事件a后面的事件呢，当遍历到后面的事件时，按照同样的方法与前面的事件的最大价值加和，此时若事件a不是这个最大值对应的事件，则事件a与后面事件的加和必然没有最大值对应事件与后面事件加和大，因此并不影响最终结果，换言之，我们将事件a和事件a后面发生的事件的和的大小问题推迟到处理后面的事件时一起处理，这样充分利用了前面已经处理过的事件的信息。
要实现前面所讲的思路，我们需要将事件按开始时间和结束时间分别排序，按开始时间遍历事件，确定事件的开始时间后遍历结束时间数组，找到所有开始时间之前结束的事件并更新这些事件中的价值的最大值，此处仅记录最大值即可，无需保存其他信息。随后将当前事件的价值和最大值加和并与全局最大值比较并更新全局最大值。
代码
class Solution {
public:
int maxTwoEvents(vector<vector<int>>& events) {
int n = events.size();
// 创建两个数组分别存储按开始时间和结束时间排序的事件
vector<pair<int, int>> starts(n);
vector<pair<int, int>> ends(n);
for(int i = 0; i < n; i++) {
starts[i] = {events[i][0], i};
ends[i] = {events[i][1], i};
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int maxValue = 0; // 记录已处理事件中的最大价值
int result = 0;
int endIndex = 0;
for(int i = 0; i < n; i++) {
int currentStart = starts[i].first;
int currentIndex = starts[i].second;
while(endIndex < n && ends[endIndex].first < currentStart) {
int idx = ends[endIndex].second;
maxValue = max(maxValue, events[idx][2]);
endIndex++;
}
result = max(result, events[currentIndex][2] + maxValue);
}
return result;
}
};
3152. 特殊数组 II
题解
本题若要query中的每个查询范围内都满足相邻元素具有不同的奇偶性，本题数字的奇偶性是有用的信息，数字本身的数值没什么用，故可以先遍历数组确定每个数字和其相邻数字的奇偶性的差异，我们用奇偶性差异值来表示这一差异，若下标i和下标i+1的数字的奇偶性不同，则称下标i处的奇偶性差异值为1，否则为0。在判断相邻数字奇偶性差异的同时，构造一个前缀和数组，保存从开头到每个下标处的子数组中奇偶性差异值的和。
对于一个query范围，若范围内的所有数字和其相邻数字的奇偶性均不同，则范围内的数字的奇偶性差异值的和应该和该范围的长度-1相等（每个奇偶差异值均为1），否则不同。求某个范围内的数字和是一个之前已经做过多次的题目，这种题目可以用前缀和求解，只需先求出确定了奇偶性的nums数组的全部下标的奇偶性差异前缀和，对每个query范围就可以快速确定范围内的子数组奇偶性差异和为多少。
代码
class Solution {
public:
vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
vector<int> prefix;
prefix.push_back(0);
int pre = 0;
for(int i=0;i<nums.size()-1;i++){
pre += (nums[i]%2)^(nums[i+1]%2);
prefix.push_back(pre);
}
vector<bool> result;
for(const auto& query : queries){
if(query[1]-query[0] == prefix[query[1]]-prefix[query[0]]){
result.push_back(true);
}else{
result.push_back(false);
}
}
return result;
}
};
2981. 找出出现至少三次的最长特殊子字符串 I
题解
本题若在遇到重复字符时直接统计字符的个数，由于相同字符的个数情况可能有很多，如当有四个重复字符时，其实包含了四个重复一次的字符，三个重复两次的字符，两个重复三次的字符及一个重复四次的字符，则每次遇到重复字符时，先将局部字符的个数全部记录，再利用一个哈希表，将每个重复个数的出现次数加入到哈希表对应的项中是可行的，但这样实际上需要将每个重复个数的字符串项都遍历一遍，如上面的例子，在有四个重复字符时，我们要在哈希表中分别更改1个，2个，3个，4个重复字符对应的项的值。
为了避免每次都要将所有重复字符的项都遍历一遍，可以想到如果我们先确定重复字符的个数，再去找这样的重复个数出现了几次就可以不用在意其他重复个数出现的情况了。如果这个重复个数的某个字符串在字符串中有三次及以上的出现次数，说明这个重复个数是可以取到的，否则不能取到，这种说法是不是感觉非常熟悉，没错这又是一个经典的二分法可以发挥作用的场景。存在一个临界值，使得临界值上成立，临界值下不成立，而要找的最大值也正是这个临界值。
使用二分法的左侧当然指向0，右边界可以先遍历数组，找到数组中相同字符最多重复了几次，以此作为右边界，再使用二分法，判断当前重复个数是否存在某个字符串出现了三次及以上（此处可使用滑动窗口，确定窗口内字符是否完全一样并用哈希表记录个数即可），最终找到刚好满足条件的临界个数即得结果。
代码
class Solution {
public:
int maximumLength(string s) {
int maxrepeat = 0;
char cur = ' ';
int repeat = 0;
for(const auto& ch : s){
if (ch != cur){
maxrepeat = max(maxrepeat, repeat);
repeat = 1;
cur = ch;
}else{
repeat++;
}
}
maxrepeat = max(maxrepeat, repeat);
int left = 0;
while(left <= maxrepeat){
int mid = (left+maxrepeat)/2;
if(valid(s,mid)){
left = mid+1;
}else{
maxrepeat = mid-1;
}
}
if(maxrepeat == 0){
return -1;
}else{
return maxrepeat;
}
}
bool valid(string s, int repeat){
vector<int> count(26,0);
for(int i=0;i<s.size();i++){
char cur = s[i];
bool flag = true;
for(int j=0;j<repeat;j++){
if(s[i+j] != s[i]){
flag = false;
break;
}
}
if(flag){
count[s[i]-'a']++;
if(count[s[i]-'a'] >= 3){
return true;
}
}
}
return false;
}
};
2779. 数组的最大美丽值
题解
首先注意本题要找的是最长的子序列而不是子数组，因此不需要数字之间相邻，数字的先后顺序在本题中也不重要。考虑题目中允许的操作为将任意一个数字加上k或者减去k，且该操作只能执行一次。则设当前的数字为i，则在i-k和i+k范围内的全部数字均可通过题目所述操作变为相同数字。这个范围的大小是固定的2k，因此可以使用滑动窗口不断确定在这个范围内的所有数字的个数。
使用滑动窗口要有一个窗口的增长和收缩条件，我们知道要将窗口的范围始终限制在2k，则可先移动窗口左端的数字，使其变大，再根据左侧数字确定右侧的数字范围，移动窗口右侧的指针。这要求数组必须是有序的，有序情况下窗口左右才可以随着指针的移动数值自然变大。因此要先将数组排序，再使用上述滑动窗口方法即可得最终结果。
代码
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int left = 0;
int right = 0;
int n = nums.size();
int maxlen = 0;
while(left<n){
while(right<n && nums[right] <= nums[left]+2*k){
right++;
}
maxlen = max(maxlen, right-left);
while(left<n-1 && nums[left+1]==nums[left]){
left++;
}
left++;
}
return maxlen;
}
};
总结
看了看最快的示例代码，发现了一个非常妙的思路，即可以直接通过设定每个nums中的值可以覆盖的数值范围，超出范围则减去相应的数字个数。这种方式可以直接通过不断加和的方式自动求得不同范围内的有效数字有多少个。
用这种方法要根据nums中的值来构造数组，数组的大小为nums中的最大值加上2*k+1。这样构造的数组覆盖了nums中的全部值范围，上面说到的设定覆盖范围可以通过例子来理解，如当前数字为1，k的值为2，则可以直接将构造的新数组中下标为1处的值加1，而将1+2*k+1，即6处的值减1。含义即为从1~1+2k范围内的数字都可以通过加减k的方式变成同一个数字，所以已有的1在这个范围内是一个有效的计数，但一旦离开这个范围，1就无法通过变换和其他数字变成同一个数了，因此1就不再是一个有效计数，因此可以减去数字1的计数。
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
int m = *max_element(nums.begin(), nums.end()) + k * 2 + 2;
vector<int> d(m);
for (int x : nums) {
d[x]++;
d[x + k * 2 + 1]--;
}
int ans = 0, s = 0;
for (int x : d) {
s += x;
ans = max(ans, s);
}
return ans;
}
};
2558. 从数量最多的堆取走礼物
题解
本题是一道比较常规的模拟问题，对题目中每次都取所有礼物中的最大值自然想到这是一个最大堆的典型场景。先构建最大堆同时求出所有礼物个数的总和。使用最大堆记录礼物的数量，每次都取堆顶的个数，对其按照题目要求取平方根，计算原数字和平方根后取下整的数字的差并从总和中减去，再将新的取下整后的数字放入最大堆中。如此重复k次即得最终结果。
代码
class Solution {
public:
long long pickGifts(vector<int>& gifts, int k) {
priority_queue<int> pq;
long long int sum = 0;
for(const auto& gift : gifts){
sum += gift;
pq.push(gift);
}
for(int i=0;i<k;i++){
int newgift = (int)floor(sqrt(pq.top()));
sum -= pq.top()-newgift;
pq.pop();
pq.push(newgift);
}
return sum;
}
};
2593. 标记所有元素后数组的分数
题解
本题每次都要选择未标记的数字中最小的那个，并将其相邻位置标记，可以构造一个布尔型标记数组来记录被标记的下标位置，该数组下标和nums中的下标对应。因为每次都选最小的，故先排序后直接遍历就能得到当前的最小数字，只需再判断其是否被标记即可。
对nums中的数字先构造结构体，将数字和对应的下标绑定，再使用稳定的排序方法对数字进行排序。按照上述算法不断遍历有序数组，用一个变量记录当前已经被标记的个数，当标记个数和数组长度相同时结束遍历并返回最终分数。
代码
class Solution {
public:
long long findScore(vector<int>& nums) {
int n = nums.size();
vector<bool> mark(n,false);
vector<pair<int,int>> sorted;
for(int i=0;i<n;i++){
sorted.push_back({nums[i],i});
}
sort(sorted.begin(),sorted.end());
int marked = 0;
long long int score = 0;
for(const auto& sort_num : sorted){
if(!mark[sort_num.second]){
score += sort_num.first;
mark[sort_num.second] = true;
marked++;
if(sort_num.second > 0 && !mark[sort_num.second-1]){
mark[sort_num.second-1] = true;
marked++;
}
if(sort_num.second < n-1 && !mark[sort_num.second+1]){ mark[sort_num.second+1] = true;
marked++;
}
if(marked == n){
break;
}
}
}
return score;
}
};
2762. 不间断子数组
题解
本题思考题目条件，要求子数组中任意两个数字之间差的绝对值不超过2。则可使用双指针来指示子数组当前的范围，同时使用两个变量分别记录当前子数组内的最大值和最小值。先将右指针向后移动，同时更新子数组内的最大值和最小值，判断二者的差是否小于等于2。等于则说明该子数组满足条件，要给结果加上子数组长度（相当于新加入的数字自身，加上数字和前面的各个子数组的组合）。
当新遍历的数使得数组内的最大值和最小值差大于2时，考虑两种情况，如上述情况数字范围为3~5，则若新数字为6，则之前的数组中若尾部仅包含4，5两个数字，4，5，6仍然符合题目要求的差的绝对值为2。故找到之前子数组的尾部仅包含4，5两个数字的部分保留。对于7同理。但若数字大于7，则之前的数组中不可能存在可以和7组合满足条件的数字，因此直接从7开始向后遍历即可。由此得出对于新数字使得子数组极差大于2时，若新数字和数组内的最大值或最小值差的绝对值不超过2，此时移动左指针直到子数组中的数字全部在新的给定范围内（具体实现上，只需超出范围的数字的个数为0即可）。否则直接从新数字开始向后遍历数组（将左右指针都设为该数字的位置）。
将每次新找到的满足条件的子数组长度加和即得最终结果。
代码
class Solution {
public:
long long continuousSubarrays(vector<int>& nums) {
long long int result = 0;
int left = 0;
int right = 0;
int n = nums.size();
unordered_map<int,int> count;
int current_min = nums[0];
int current_max = nums[0];
while (right < n) {
if (right > left &&
(abs(nums[right] - current_max) > 2 &&
abs(nums[right] - current_min) > 2)) {
count.clear();
left = right;
current_max = nums[right];
current_min = nums[right];
}
count[nums[right]]++;
current_max = max(current_max, nums[right]);
current_min = min(current_min, nums[right]);
while (current_max - current_min > 2) {
count[nums[left]]--;
if (count[nums[left]] == 0) {
count.erase(nums[left]);
}
left++;
current_max = nums[left];
current_min = nums[left];
for (auto& pair : count) {
if (pair.second > 0) {
current_max = max(current_max, pair.first);
current_min = min(current_min, pair.first);
}
}
}
// 计算当前窗口内的所有有效子数组数量
result += (right - left + 1);
right++;
}
return result;
}
};
1792. 最大平均通过率
题解
本题首先要了解一个分数自身的性质，对一个分数给分子分母同时加1，会使得分数的值向1靠近，意味着若分数小于1，则同时加1会使分数变大，分数大于1，同时加1会使分数变小。
本题学生的通过率都是小于等于1的，因此给通过率小于1的class分配一个通过的学生会使分子分母同时加1使得分数变大。本题要提高总体的平均通过率，需要使分配学生后通过率的增加幅度尽可能大，因此本题可使用最大堆，每次弹出在分子分母同时加1后通过率增加幅度最大的组合，给它分子分母同时加1并计算新的通过率增加幅度重新放入堆中。注意此处为了计算的精确性，需要保留通过率的浮点数和原始的分子分母的整数用于后续计算。
代码
class Solution {
public:
struct Class {
int pass;
int total;
double delta;
Class(int p, int t) {
pass = p;
total = t;
delta = (double)(p + 1) / (t + 1) - (double)p / t;
}
};
double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
// 按照delta降序排列的优先队列
auto comp = [](const Class& a, const Class& b) {
return a.delta < b.delta;
};
priority_queue<Class, vector<Class>, decltype(comp)> pq(comp);
for (const auto& c : classes) {
pq.push(Class(c[0], c[1]));
}
while (extraStudents--) {
Class curr = pq.top();
pq.pop();
curr.pass++;
curr.total++;
curr.delta = (double)(curr.pass + 1) / (curr.total + 1) - (double)curr.pass / curr.total;
pq.push(curr);
}
double sum = 0;
int n = classes.size();
while (!pq.empty()) {
const Class& c = pq.top();
sum += (double)c.pass / c.total;
pq.pop();
}
return sum / n;
}
};
3264. K 次乘运算后的最终数组 I
题解
本题使用最小堆可解。构造一个pair将数字和对应的下标存储起来，再将这些pair插入最小堆，此处注意定义最小堆的比较规则，当比较数值后，若数值相同还要比较下标。每次从最小堆中弹出顶部数字，按照下标将nums对应数字和multiplier相乘即可。
代码
class Solution {
public:
vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
auto cmp = [](const pair<int,int> a, const pair<int,int> b){
if(a.first == b.first){
return a.second > b.second;
}
return a.first>b.first;
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
for(int i=0;i<nums.size();i++){
pq.push({nums[i],i});
}
while(k>0){
auto num = pq.top();
nums[num.second] *= multiplier;
num.first *= multiplier;
pq.pop();
pq.push(num);
k--;
}
return nums;
}
};
2182. 构造限制重复的字符串
题解
本题先统计字符串s中各个字母的字数，再根据题意构造最大字符串，构造最大字符串需要将所有字符从最大字符开始排列，但排列时相同字符的连续重复次数不能超过repeatLimit。则每次当最大字符重复了repeatLimit后，需要插入一个次大字符，再继续插入最大字符，因此可以使用双指针，分别指示当前的最大字符和次大字符，再按照题目要求通过不断交替插入尽可能多的最大字符和用于分隔的次大字符来构造整个字符串。
这样得到的就是最大的字符串，对于剩余的多余字符，如剩下了很多a没有使用并不影响这个字符串的最大性，因为题目只要求使用s中的字符得到最大字符串，不要求将字符全部用完。
代码
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
int maxindex = 0;
int secondindex = -1;
vector<int> count(26,0);
for(const auto& ch : s){
count[ch-'a']++;
}
for(int i=25;i>=0;i--){
if(count[i] > 0){
maxindex = i;
for(int j=i-1;j>=0;j--){
if(count[j]>0){
secondindex = j;
break;
}
}
break;
}
}
string result;
int limit = repeatLimit;
while(maxindex >= 0){
while(count[maxindex] > 0 && limit > 0){
result.push_back('a' + maxindex);
count[maxindex]--;
limit--;
}
if(count[maxindex] > 0){
if(secondindex >= 0){
if(count[secondindex] > 0){
result.push_back('a' + secondindex);
count[secondindex]--;
limit = repeatLimit;
} else {
secondindex = -1;
for(int i = maxindex-1; i >= 0; i--){
if(count[i] > 0){
secondindex = i;
break;
}
}
if(secondindex < 0) break;
result.push_back('a' + secondindex);
count[secondindex]--;
limit = repeatLimit;
}
} else {
break;
}
} else {
maxindex = secondindex;
secondindex = -1;
for(int i = maxindex-1; i >= 0; i--){
if(count[i] > 0){
secondindex = i;
break;
}
}
limit = repeatLimit;
}
}
return result;
}
};
总结
这次代码写的有点丑陋了，但思路上是没问题的，可以参考下其他人写的思路基本一样的代码，更简洁
class Solution {
public:
string repeatLimitedString(string s, int repeatLimit) {
vector<int> freq(26, 0);
for (char ch : s) {
freq[ch - 'a']++;
}
string result;
int currentCharIndex = 25; // Start from the largest character
while (currentCharIndex >= 0) {
if (freq[currentCharIndex] == 0) {
currentCharIndex--;
continue;
}
int use = min(freq[currentCharIndex], repeatLimit);
result.append(use, 'a' + currentCharIndex);
freq[currentCharIndex] -= use;
if (freq[currentCharIndex] >
0) { // Need to add a smaller character
int smallerCharIndex = currentCharIndex - 1;
while (smallerCharIndex >= 0 && freq[smallerCharIndex] == 0) {
smallerCharIndex--;
}
if (smallerCharIndex < 0) {
break;
}
result.push_back('a' + smallerCharIndex);
freq[smallerCharIndex]--;
}
}
return result;
}
};
1475. 商品折扣后的最终价格
题解
本题要考虑j>i的下标j的情况，则可以从右向左遍历数组，这样当遍历到下标i时下标j及j右侧已经处理过了，必然可以拿到一些信息。考虑下标j，对每个下标j如果其右侧已经遍历过，则此时必然已知一个下标k使得k是大于j的价格小于等于j的最小下标，则对于i，如果j不满足条件，那么价格大于j的当然同样不满足条件，我们要找的是价格小于j的在j右侧的下标，则此时下标k正满足条件。如果k的价格仍不满足条件，则同样在遍历k时已知一个p满足题目条件，再继续找到p，如此链式查找直到找到一个数字的结果的下标就是其自身说明没有满足条件的数字，直接使i的价格为其自身。若找到满足条件的则设为满足条件的价格。
设定两个数组，一个用来保存找到的满足条件的打折扣的数字下标，另一个保存当前下标是否能打折扣。最终遍历数组，对于能打折扣的数字，减去其折扣值。
代码
class Solution {
public:
vector<int> finalPrices(vector<int>& prices) {
int n = prices.size();
vector<int> targetindex(n,0);
vector<bool> discount(n,false);
for(int i=prices.size()-1;i>=0;i--){
int nextindex=i+1;
if(nextindex == n){
targetindex[i] = i;
continue;
}
while(nextindex < n){
if(prices[nextindex] > prices[i]){
if(nextindex == targetindex[nextindex]){
targetindex[i] = i;
break;
}else{
nextindex = targetindex[nextindex];
}
}else{
targetindex[i] = nextindex;
discount[i] = true;
break;
}
}
}
for(int i=0;i<n;i++){
if(discount[i]){
prices[i] = prices[i]-prices[targetindex[i]];
}
}
return prices;
}
};
769. 最多能完成排序的块
题解
本题若要在分块后将块内排序，使得每个块内有序后整体自然有序，则假设块i之前的所有块包含的数字个数为k，则块i必须包含从k+1到出现的块内最大值的所有数字（如果第一个出现的数字是k+3，就要包含k+1~k+3，如果第一个出现的就是k+1，则只包含一个k+1即可）。这样才能保证块内排序后不会出现后面有数字小于块内最大值从而使整体不满足有序这样的问题。则用一个数字统计当前最大值m之前已经出现的数字个数，当数字个数达到m-1时，从上一块结尾开始到当前数字就可以被分为单独的一块。
此处我们并不需要知道每个块都有哪些数字，只要已经出现了当前最大值之前的全部数字，我们就知道前面的数字一定可以排列成有序的，否则后面还可能出现更小的数字使得整体不满足有序，因此可以排列成有序的时候就可以分为单独的一块。如果数组本身就是有序的，那么按照我们的算法，对每个数字，遍历到该数字时小于该数字的全部数字都已经出现了，则一定可以排列成有序的，因此这个数字本身就可以单独分为一块。
代码
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int count = -1;
int result = 0;
int maxnum = -1;
for(const int& num : arr){
maxnum = max(num,maxnum);
if (count == maxnum-1){
result++;
}
count++;
}
return result;
}
};
