刷题记录｜目标101题--贪心算法
写在前面
开个贴记录一下刷题的过程，目前参照leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～
贪心算法
No.1 assign cookies
题目链接：https://leetcode.com/problems/assign-cookies/
涉及到的算法：贪心
解题思路：这里涉及到的贪心策略是给剩余孩子里饥饿度最小的孩子分配能满足他的最小饼干
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int result = 0;
for (int i = 0,j = 0; i < g.length && j < s.length;) {
if (g[i] <= s[j]) {
result++;
i++;
j++;
} else {
j++;
}
}
return result;
}
}
No.2 Candy
题目链接：https://leetcode.com/problems/candy/
涉及到的算法：贪心
解题思路：
这里巧妙在如果是从左向右，只用处理增长，为n和n+1比较时，为n+1的点增加计数，所以可以用i和i-1，对i做增加计数，不用处理边际条件
从右向左，也只用处理增长，且是为i和i-1比较时增加i-1的计数，
即从左到右，使用i和i-1，为右置位增加计数，从右到左使用n和n+1，为左置位增加计数
class Solution {
public int candy(int[] ratings) {
if (ratings.length < 2) {
return ratings.length;
}
int[] candies = new int[ratings.length];
Arrays.fill(candies,1);
for (int i = 1; i < candies.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i -1] + 1;
}
}
for (int i = ratings.length - 2; i >= 0; i --){
if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
}
}
int result = 0;
for (int candy : candies) {
result += candy;
}
return result;
}
}
No.3 Non-overlapping Intervals
题目链接:https://leetcode.com/problems/non-overlapping-intervals/
涉及到的算法：贪心
解题思路： 先将区间结尾升序排列，从头开始遍历一次，不重叠的就保留。 之所以选择结尾排序是为了尽可能少的去除数组，好保证result是minimum。因为如果选择的区间结尾越小，留给别的区间的空间越大，如果用开发排序，在面对存在一个很长的区间时就会误判从而多去除很多，比如[[1,10], [2,3], [4,5], [7,8]]
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length < 2) return 0;
Arrays.sort(intervals, (a,b) -> Integer.compare(a[1],b[1]));
int result = 0;
for (int i = 1,j = 0; i < intervals.length; i ++) {
if (intervals[i][0] < intervals[j][1]) {
result++;
} else {
j = i;
}
}
return result;
}
}
No.4 Can Place Flowers
题目链接：https://leetcode.com/problems/can-place-flowers/
涉及到的算法：贪心
解题思路： 遍历一遍数组，如果一个位置前后都是0就可以种植，对最开始和最后的位置特殊判断其前后，如果已经满足就可以提前break。 这里是因为从左到右数一遍，能种就种就可以贪心，不存在堵了后续的路。
public class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count = 0;
for(int i = 0; i < flowerbed.length && count < n; i++) {
if(flowerbed[i] == 0) {
//get next and prev flower bed slot values. If i lies at the ends the next and prev are considered as 0.
int next = (i == flowerbed.length - 1) ? 0 : flowerbed[i + 1];
int prev = (i == 0) ? 0 : flowerbed[i - 1];
if(next == 0 && prev == 0) {
flowerbed[i] = 1;
count++;
}
}
}
return count == n;
}
}
No.5 Minimum Number of Arrows to Burst Balloons
题目链接：https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
解题思路： 本题依然是使用尾部排序，因为这样可以确保更多的气球被射中 class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 1) return 1;
Arrays.sort(points, (a,b) -> Integer.compare(a[1],b[1]));
int result = 1;
for(int i = 1,current = points[0][1]; i < points.length; i ++) {
if (points[i][0] > current) {
result++;
current = points[i][1];
}
}
return result;
}
}
No. 6 Partition Labels
题目链接：https://leetcode.com/problems/partition-labels/
解题思路：
This gives us the idea for the algorithm: For each letter encountered, process the last occurrence of that letter, extending the current partition [anchor, j] appropriately.
每一个最小的部分都需要他的包含第一个字母（这里假设他是a）以及字母a最后一次出现的位置，但是在第一个a和最后一个a的中间会有bcd等字母，这个最小部分也需要包含到他们的字母对应的最后一次出现的位置，所以我们需要存储每个字母对应的最后一个字母出现的位置。
即开拓一个26长度的数组，对string两次遍历，第一次记录下来这个string中出现的字母x最后一次在string中出现的位置，第二次遍历即可根据他们的位置计算最小的部分
相关java知识：https://www.cainiaojc.com/java/java-list.html
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> result = new ArrayList<>();
if (s.length() == 1) {
result.add(1);
return result;
}
int[] characters = new int[26];
Arrays.fill(characters, -1);
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) -'a';
characters[index] = i;
}
for (int i = 0,lastEnd = -1,currentEnd = characters[s.charAt(0) - 'a'];
i < s.length(); i++) {
int index = s.charAt(i) - 'a';
if (characters[index] > currentEnd) {
currentEnd = characters[index];
}
if (i == currentEnd) {
result.add(currentEnd - lastEnd);
lastEnd = currentEnd;
}
}
return result;
}
}
No. 7 Best Time to Buy and Sell Stock II
题目链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
解题思路：
只需要保证每个增长的区间可以盈利就可以，所以我们可以累加所有的增长区间的差值，对应到代码上，只要prices[i]>prices[i -1] 就可以计入盈利，比如对下图来说，只要吃到A-B，C-D，E-F的盈利就可以
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 1) return 0;
int result = 0;
for (int i = 1; i < prices.length; i ++) {
if (prices[i] > prices[i - 1]) {
result += prices[i] - prices[i -1];
}
}
return result;
}
}
No.8 Queue Reconstruction by Height
题目链接：
https://leetcode.com/problems/queue-reconstruction-by-height/
涉及到的算法：贪心
解题思路：
1。将这个数组根据身高从高到低排序，如果高度一样，k值小的站前面（因为k代表前面身高不低于他的人的数量）。
这样排序以后身高最高的人在最前面，因为没有人比他们高，所以他们的k值就是他们的顺序
2。将身高次高的人根据k值插入，因为目前数组中只有比他们高的人，所以他们的k值就是他们自己的位置，（剩余身高依次类推）
这里因为要进行插入操作，所以要用到link-list
涉及到的java知识：
list to array -> list.toArray(new int[len])
class Solution {
public int[][] reconstructQueue(int[][] people) {
if (people.length == 1) return people;
Arrays.sort(people,(a,b) -> {
return a[0] == b[0] ? (a[1] - b[1]) : (b[0] - a[0]);
});
List<int[]> result = new LinkedList<>();
for (int i = 0; i < people.length; i ++) {
result.add(people[i][1],people[i]);
}
int[][] finalResult = new int[people.length][2];
result.toArray(finalResult);
return finalResult;
}
}
No.8 Non-decreasing Array
题目链接：https://leetcode.com/problems/non-decreasing-array/
涉及到的思路：贪心
解题思路：
当我们从左往右便利的时候，如果遇到一个nunms[i-1]>nums[i]的下降趋势的情况，有两种做法
- 将nums[i]变大
- 将nums[i-1]变小
因为将nums[i] 变大的方法在面对连续后续的数字会有更大的风险无法符合要求，比如8，2，3样一组数，只需将8改小就可以，将2改大就错误了，
所以最好采用将nums[i-1]变小的方法。
将nums[i-1]变小也涉及两种情况：
1.nums[i-2]<=nums[i] 可以正常将nums[i-1]变小
2.nums[i-2]>nums[i]，此时单纯的让nums[i-1]变小是不可行的，需要让nums[i-2]变小，且不清楚nums[i-3]的情况，所以需要在这个时候采取将nums[i]变大的策略
class Solution {
public boolean checkPossibility(int[] nums) {
if (nums.length == 1) return true;
int flag = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i]) {
flag++;
if (i == 1) {
nums[i - 1] = nums[i];
} else if (nums[i - 2] > nums[i]) {
nums[i] = nums[i -1];
} else {
nums[i - 1] = nums[i];
}
}
if (flag > 1) {
return false;
}
}
return true;
}
}
#逃离互联网##力扣刷题#
