题目

1. 1221. 分割平衡字符串
2. 1827. 最少操作使数组递增
3. 2144. 打折购买糖果的最小开销
4. 1400. 构造 K 个回文字符串
5. 1221. 分割平衡字符串
6. 1217. 玩筹码
7. 1029. 两地调度
8. 面试题 10.11. 峰与谷

解题思路与代码详情

【题1】1221. 分割平衡字符串

1221. 分割平衡字符串： 在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
返回可以通过分割得到的平衡字符串的 最大数量 。

题目解析： 将字符串分隔成字符L'和 R数目相同的子字符串
解题思路：
遍历字符串数组，分别累积字符L'和 R的数量，一旦字符L'和 R的数量相等就进行切割。

# python3
class Solution:def balancedStringSplit(self, s: str) -> int:Rnum=0Lnum=0ans=0#n=len(s)#for i in range(n):for c in s:if c == 'R':Rnum += 1if c == 'L':Lnum += 1if Rnum==Lnum:ans+=1return ans

//C
int balancedStringSplit(char * s){int Lnum=0, Rnum=0;int ans=0;for(int i=0;i<strlen(s);i++){if(s[i]=='L'){Lnum++;}if(s[i]=='R'){Rnum++;}if(Lnum==Rnum){ans++;}}return ans;
}

【题2】1827. 最少操作使数组递增

1827. 最少操作使数组递增： 给你一个整数数组 nums （下标从 0 开始）。每一次操作中，你可以选择数组中一个元素，并将它增加 1 。

比方说，如果 nums = [1,2,3] ，你可以选择增加 nums[1] 得到 nums = [1,3,3] 。

请你返回使 nums 严格递增 的 最少 操作次数。

我们称数组 nums 是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。

题目解析： 对数组中元素进行加1操作，使得数组元素形成一个递增序列。
解题思路：
对数组元素按升序排列，只要后一个元素等于前一个元素就执行加1操作，逐个遍历，使得后一个元素都比新更新后的前一个元素大1.

#python3
class Solution:def minOperations(self, nums: List[int]) -> int:ans=0n=len(nums)for i in range(1,n):if nums[i]<=nums[i-1]:ans+=((nums[i-1]-nums[i])+1)nums[i]+=((nums[i-1]-nums[i])+1)return ans

//C
int minOperations(int* nums, int numsSize){int ans=0;for(int i=1;i<numsSize;i++){if(nums[i]<=nums[i-1]){ans+=(nums[i-1]-nums[i]+1);nums[i]+=(nums[i-1]-nums[i]+1);}}return ans;
}

【题3】2144. 打折购买糖果的最小开销

2144. 打折购买糖果的最小开销： 一家商店正在打折销售糖果。每购买 两个 糖果，商店会 免费 送一个糖果。

免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。

比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。

给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得 所有糖果的 最小 总开销。

题目解析： 要求每买两个糖果，就可以免费获得一个价钱比所买两个糖果中价钱小或相等的糖果，所以每三种价钱的糖果可归为一组，求算购买所有糖果的最小费用。

解题思路： 糖果的赠送情况跟价钱的高低有关，若争取所赠送的水果的价钱尽量高，所以
（1）首先将所有的糖果价格按降序顺序排列；
（2）将所有糖果按价钱每三个一组（若糖果总种类少于三种，则需要直接购买无赠送情况）
（3）累积每组中前两种糖果的价钱
（4）累积不成组的剩余种类的糖果的价钱（不成组糖果需直接购买）

#python3
class Solution:def minimumCost(self, cost: List[int]) -> int:cost.sort(reverse=1)n=len(cost)num=n//3ans=0if num==0:ans=sum(cost[:(n%3)])else:for i in range(num):ans+=cost[3*i]+cost[3*i+1]ans+=sum(cost[3*num:(3*num+n%3)])return ans

//C
int cmp(const void* p1, const void* p2){return *(int*)p2-*(int*)p1;
}
int minimumCost(int* cost, int costSize){qsort(cost, costSize, sizeof(int),cmp);int num=0,ans=0;num=costSize/3;if(num==0){for(int i=0;i<costSize%3;i++){ans+=cost[i];}}else{for(int i=0;i<num;i++){ans+=(cost[3*i]+cost[3*i+1]);}for(int i=0;i<costSize%3;i++){ans+=cost[3*num+i];}}return ans;
}

【题4】1400. 构造 K 个回文字符串

1400. 构造 K 个回文字符串： 给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。
如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。

解题思路： 糖果的赠送情况跟价钱的高低有关，若争取所赠送的水果的价钱尽量高，所以
（1）首先将所有的糖果价格按降序顺序排列；
（2）将所有糖果按价钱每三个一组（若糖果总种类少于三种，则需要直接购买无赠送情况）
（3）累积每组中前两种糖果的价钱
（4）累积不成组的剩余种类的糖果的价钱（不成组糖果需直接购买）

class Solution:def canConstruct(self, s: str, k: int) -> bool:slist=collections.Counter(s)numodd=0for c in slist:if slist[c]%2==1:numodd+=1if numodd<=k and len(s)>=k:return Trueelse:return False

//C
//计算每个字符出现的次数
/*int num(char * s, char c){int numap=0;for(int i=0;i<strlen(s);i++){if(c==s[i]){numap++;}}return numap;
}*/bool canConstruct(char * s, int k){int ans=0;int a[26]={0};int lens=strlen(s);//memset(a, 0, sizeof(a));for(int i=0;i<lens;i++){++a[s[i]-97];}for(int i=0;i<26;i++){if(a[i]%2==1){ans++;}}if(ans<=k && lens>=k){return true;}else{return false;}
}

【题5】1221. 分割平衡字符串

1221. 分割平衡字符串： 在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。
给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

见【题1】。

【题6】1217. 玩筹码

1217. 玩筹码： 有 n 个筹码。第 i 个芯片的位置是 position[i] 。
我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个芯片的位置从 position[i] 改变为:
position[i] + 2 或 position[i] - 2 ，此时 cost = 0
position[i] + 1 或 position[i] - 1 ，此时 cost = 1
返回将所有筹码移动到同一位置上所需要的 最小代价 。

题目解析： 移动n个位置上的筹码，移动2步则代价为0，移动1步则代价为1，求总代价最低的移动策略。

解题思路： 若所固定的位置与需要移动的位置奇偶性相同，则必然移动的步数为0，若奇偶性不同，则可先移动多个2步，最后再移动1步达到指定位置。所以
（1）计算所有位置是奇数的个数与是偶数的个数；
（2）如果所有的位置全部为奇数或全部为偶数，则移动步数为0；
（3）如果奇数个数和偶数个数相同，则所有的位置为奇数（偶数）的位置上的筹码可全部移动到一个固定的位置为偶数（奇数）的位置上，总得费用即为奇数（偶数）位置的个数。
（4）若奇偶个数的位置不相同，为最小化代价，可将位置个数少的那些位置上的筹码进行移动。

#python3
class Solution:def minCostToMoveChips(self, position: List[int]) -> int:n=len(position)odd = 0even = 0cost=0for i in range(n):if position[i]%2==0:even+=1if position[i]%2==1:odd+=1if even==odd:cost=evenelif even==0 or odd==0:cost=0else:cost=min(even,odd)return cost

//C
int minCostToMoveChips(int* position, int positionSize){int odd=0,even=0;int cost=0;for(int i=0;i<positionSize;i++){if(position[i]%2==0){even++;}if(position[i]%2==1){odd++;}}if(even==0||odd==0){cost=0;}else if(even==odd){cost=even;}else{cost=fmin(even,odd);}return cost;
}

【题7】1029. 两地调度

1029. 两地调度： 公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第i人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。

返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。

题目解析： 2n个人出差去往a,b两地，每个地方都要求有n人抵达，求费用最小的出差策略。

解题思路： 假设所有的人都去往b地，那么相较于去a地会产生价格差，将2n个人都去a地喝都去b地的价格差按升序排列，用所有人都去b地的总费用加上最大的a，b两地价格差即得最小费用。

class Solution:def twoCitySchedCost(self, costs: List[List[int]]) -> int:n=len(costs)ans=0costdifference=[0]*nfor i in range(n):costdifference[i]=costs[i][0]-costs[i][1]ans+=costs[i][1]costdifference.sort()ans+=sum(costdifference[:n//2])return ans

//C
int cmp(const void*p1, const*p2){return *(int*)p1-*(int*)p2;
}
int twoCitySchedCost(int** costs, int costsSize, int* costsColSize){int ans=0;int* temp=(int*)malloc(sizeof(int)*costsSize);for(int i=0;i<costsSize;i++){temp[i]=costs[i][0]-costs[i][1];ans+=costs[i][1];}qsort(temp,costsSize, sizeof(int),cmp);for(int i=0;i<costsSize/2;i++){ans+=temp[i];}return ans;
}

【题8】面试题 10.11. 峰与谷

面试题 10.11. 峰与谷： 在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。

现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。

题目解析： 将数组内的元素按大小大小的顺序排列。

解题思路： 奇数位置放大数，偶数位置放小数。

class Solution:def wiggleSort(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""#奇数位置放大数，偶数位置放小数n=len(nums)for i in range(n-1):if i%2==0:if nums[i]<nums[i+1]:nums[i],nums[i+1]=nums[i+1],nums[i]if i%2==1:if nums[i]>nums[i+1]:nums[i],nums[i+1]=nums[i+1],nums[i]

//C
void wiggleSort(int* nums, int numsSize){int temp = 0;for(int i=0;i<numsSize-1;i++){if(i%2==0){if(nums[i]<nums[i+1]){temp=nums[i];nums[i]=nums[i+1];nums[i+1]=temp;}}if(i%2==1){if(nums[i]>nums[i+1]){temp=nums[i];nums[i]=nums[i+1];nums[i+1]=temp;}}}
}

参考文献

1. https://blog.csdn.net/WhereIsHeroFrom/article/details/124565071
2. https://blog.csdn.net/WhereIsHeroFrom/article/details/125118295