文章图片
目录??
1221题目描述:
解题思路：
代码附上：
1217 题目描述：
解题思路: :
代码附上:
1029题目描述：
解题思路：
代码附上：
10.11 题目描述：
解题思路：
代码附上：
前言1221题目描述:
友友们大家好，我是你们的小王同学
今天给大家带来的是 力扣刷题篇——经典的几道贪心的题目
希望能给大家带来有用的知识
小王同学日更的力扣刷题专栏：力扣刷题专栏
觉得小王写的不错的话 麻烦动动小手 点赞 收藏?评论
小王的主页：小王同学
小王的gitee：小王同学
小王的github：小王同学
在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。解题思路：
给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
返回可以通过分割得到的平衡字符串的 最大数量 。
示例 1：
【力扣刷题|力扣刷题篇——贪心】输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
示例 2：
输入：s = "RLLLLRRRLR"
输出：3
解释：s 可以分割为 "RL"、"LLLRRR"、"LR" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
示例 3：
输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR".
示例 4：
输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 "RL"、"RRRLLRLL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
代码附上：
- 将字符串一次性分割成尽可能多的平衡段，则最多段数等于从前往后遍历时达到平衡的次数，一次遍历即可。
- 遇到'L'就加+1 反正就-1
- 每次达到平衡 就是次数为0时就记录count 表示找到了一个平衡字符串
- 输出即可
int count=0;
int res=0;
for(int i=0;
i
文章图片
1217 题目描述：
有 n 个筹码。第 i 个芯片的位置是 position[i] 。解题思路: :
我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个芯片的位置从 position[i] 改变为:
position[i] + 2 或 position[i] - 2 ，此时 cost = 0
position[i] + 1 或 position[i] - 1 ，此时 cost = 1
返回将所有筹码移动到同一位置上所需要的 最小代价 。
示例 1：
输入：position = [1,2,3]
输出：1
解释：第一步:将位置3的芯片移动到位置1，成本为0。
第二步:将位置2的芯片移动到位置1，成本= 1。
总成本是1。
示例 2：
输入：position = [2,2,2,3,3]
输出：2
解释：我们可以把位置3的两个芯片移到位置2。每一步的成本为1。总成本= 2。
示例 3:
输入：position = [1,1000000000]
输出：1
代码附上:
- 根据题意可知，移动偶数步不消耗步数，移动奇数倍消耗步数1步
- 为了最小化步数 先将偶数步数设置为0
- 分别把偶数位跟奇数位各自挪到一起
- 只需要计算一个数组中 奇数跟偶数的数量即可
- 返回最小的那一个
class Solution {
public int minCostToMoveChips(int[] position) {int oddnumber=0;
//奇数的个数
int evennumber=0;
//偶数的个数
for(int i=0;
i
文章图片
1029题目描述：
公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。解题思路：
返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。
示例 1：
输入：costs = [[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 a 市，费用为 10。
第二个人去 a 市，费用为 30。
第三个人去 b 市，费用为 50。
第四个人去 b 市，费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。
示例 2：
输入：costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
输出：1859
示例 3：
输入：costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
输出：3086
代码附上：
- 按照价格A 和价格B分别进行排序
- 将前n个人飞往a 然后用总的人数减去前n个人即为b的人数
class Solution {
public int twoCitySchedCost(int[][] costs) {Arrays.sort(costs, new Comparator() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o1[1] - (o2[0] - o2[1]);
}
});
int res = 0;
int n = costs.length / 2;
for (int i = 0;
i < n;
++i) res += costs[i][0] + costs[i + n][1];
return res;
}
} 
文章图片
10.11 题目描述：
在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。解题思路：
示例:
输入: [5, 3, 1, 2, 3]
输出: [5, 1, 3, 2, 3]
先排序，再依次遍历数组，每两个数交换位置。代码附上：
也可以不排序，直接判断奇数位和偶数位的数字是否符合要求。
- 如果当前i位置为峰判断当前位置跟是否小于前一个位置若小于则交换 大于则不动
- 如果当前位置为谷则判断当前位置是否小于前一个位置若大于则交换小于则不动
class Solution {
public void wiggleSort(int[] nums) {for(int i=1;
inums[i-1])
{
swap(nums,i,i-1);
}
}else{
if(nums[i] | 题目 | 难度 |
| 1221. 分割平衡字符串 | ★☆☆☆☆ |
| 1217. 玩筹码 | ★☆☆☆☆ |
| 1029. 两地调度 | ★★☆☆ |
| 面试题 10.11. 峰与谷 | ★★☆☆ |
以上就是小王同学带给大家的几道经典的贪心算法
觉得写的不错的话 麻烦小手点个三连吧！
谢谢你们这么好还关注我?
文章图片
文章图片
推荐阅读
- 数据库|做 SQL 性能优化真是让人干瞪眼
- 力扣刷题|力扣刷题篇——排序
- C++ STL Multiset与Multimap中的pair有什么区别（）
- Python（算法|Python:递归算法(基础)）
- 互联网和WWW之间有什么区别（）
- 算法（数组元素最高和最低频率之间的差异）
- C#中的Hashtable和Dictionary有什么区别（）
- 算法-差异数组（O(1)时间范围更新查询）
- 数据结构和算法常见试题分享|S34