贪心算法
简介[简单] 455. 分发饼干[中等] 376. 摆动序列[中等] 53. 最大子数组和[中等] 122. 买卖股票的最佳时机 II[中等] 55. 跳跃游戏[中等] 45. 跳跃游戏 II[简单] 1005. K 次取反后最大化的数组和[简单] 134. 加油站[困难] 135. 分发糖果[简单] 860. 柠檬水找零[中等] 406. 根据身高重建队列[中等] 452. 用最少数量的箭引爆气球[中等] 435. 无重叠区间[中等] 763. 划分字母区间[中等] 56. 合并区间[中等] 738. 单调递增的数字[困难] 968. 监控二叉树
简介
记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录的刷题路线。会附上一些个人的思路，如果有错误，可以在评论区提醒一下。
[简单] 455. 分发饼干
原题链接 贪心思路，优先把大的饼干分给胃口大的。
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(s);
Arrays.sort(g);
int ans = 0;
int j = s.length - 1;
for(int i = g.length - 1; i >= 0 && j >= 0; i--){
if(s[j] >= g[i]){
j--;
ans++;
}
}
return ans;
}
}
[中等] 376. 摆动序列
原题链接 初次提交无法通过[0,1,1,2,2]这样的示例，没有判断出带平坡的单调递增，需要注意，只在result++的时候才去记录prediff的值，因为没有判断出result++的节点理论上是被删掉了，下一轮循环使用的还是同一个prediff prediff初值设置为0是假设nums[0] 前面有一个跟他一样的节点。
class Solution {
public int wiggleMaxLength(int[] nums) {
int prediff = 0;
int curdiff;
int length = nums.length;
if(length <= 1) return length;
int result = 1;
for(int i = 0; i < length - 1; i++){
curdiff = nums[i + 1] - nums[i];
if((prediff <= 0 && curdiff > 0) || (prediff >= 0 && curdiff < 0)) {
result++;
prediff = curdiff;
}
}
return result;
}
}
[中等] 53. 最大子数组和
原题链接
从左到右开始累加，如果[0 - i] 的累加<=0,说明这一段肯定不是结果的一部分，可以直接抛弃。
class Solution {
public int maxSubArray(int[] nums) {
int result = Integer.MIN_VALUE;
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
if(sum > result){
result = sum;
}
if(sum <=0 ) sum = 0;
}
return result;
}
}
[中等] 122. 买卖股票的最佳时机 II
原题链接
就按每天的差值来进行交易，差值为正就购入，算入总和。
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
for(int i = 1; i < prices.length; i++){
int count = prices[i] - prices[i - 1];
if(count > 0) ans += count;
}
return ans;
}
}
[中等] 55. 跳跃游戏
原题链接
不需要考虑具体跳到哪里，只要知道能跳的最大范围即可，比如nums = [3,2,1,0,4]中，从第一个位置开始跳，不管跳到 nums[1]/nums[2]/nums[3]，他们最多也都是够到下标为3，所以最后会是false。
class Solution {
public boolean canJump(int[] nums) {
int cover = 0;
for(int i = 0; i <= cover ; i++) {
cover = Integer.max(i + nums[i], cover);
if(cover >= nums.length - 1) return true;
}
return false;
}
}
[中等] 45. 跳跃游戏 II
原题链接
class Solution {
public int jump(int[] nums) {
int count = 0;
int lastCover = 0;
int newCover =0;
while(newCover < nums.length - 1){
count++;
int k = lastCover;
lastCover = newCover;
int j = newCover;
for(int i = k; i <= j; i++){
newCover = newCover > i + nums[i] ? newCover : i + nums[i];
}
}
return count;
}
}
[简单] 1005. K 次取反后最大化的数组和
原题链接
优先把负数变正数，nums全部 >= 0 的时候，如果k还 >= 0，就把最小的数，也就是绝对值最小的数，不停倒转 也可以一开始就把nums按照绝对值进行排序，但是在java中这样需要先转换成Integer数组进行sort操作，效率比较低
按照绝对值排序：
int length = nums.length;
Integer[] integers= new Integer[length];
for (int i = 0; i < length; i++) {
integers[i] = nums[i];
}
//nums数组根据绝对值进行排序
Arrays.sort(integers, (a, b) -> Math.abs(b) - Math.abs(a));
int[] numbers = new int[length];
for (int i = 0; i < length; i++) {
numbers[i] = integers[i];
}
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
int length = nums.length;
Arrays.sort(nums);
for(int i = 0; i < length; i++){
if(k == 0) break;
if(nums[i] < 0 && k > 0){
nums[i] = -nums[i];
k--;
}
}
Arrays.sort(nums);
while(k-- > 0){
nums[0] = -nums[0];
}
int sum = 0;
for(int i = 0; i < length; i++){
sum += nums[i];
}
return sum;
}
}
[简单] 134. 加油站
原题链接
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for(int i = 0; i < gas.length; i++){
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if(curSum < 0){
start = i + 1;
curSum = 0;
}
}
if(totalSum < 0) return -1;
return start;
}
}
[困难] 135. 分发糖果
原题链接
先从左到右遍历，保证右边ratings大于左边时，candy数量也是右边大于左边 再从右往左遍历，保证左边ratings大于右边时，candy数量也能保证左边大于右边，如果本身candy[i] > candy[i + 1]，则无需改变，否则需要给上candy[i + 1] + 1的值
class Solution {
public int candy(int[] ratings) {
int length = ratings.length;
//找到rating最小
int[] candy = new int[length];
candy[0] = 1;
//从左到有遍历，保证右边大于左边的 数字正确
for(int i = 1; i < length; i++){
if(ratings[i] > ratings[i - 1])
candy[i] = candy[i - 1] + 1;
else
candy[i] = 1;
}
int sum = candy[length - 1];
//从右到左遍历，保证左边大于右边的 数字正确
for(int i = length - 2; i >= 0; i--){
if(ratings[i] > ratings[i + 1]) {
candy[i] = candy[i] > candy[i + 1] + 1 ? candy[i] : candy[i + 1] + 1;
}
sum += candy[i];
}
return sum;
}
}
[简单] 860. 柠檬水找零
原题链接
比较简单，感觉就像是流程题，拿到20的时候优先找10，因为10只能用来给20找零，也不用记录20的值，20无法用来找零，没用
class Solution {
public boolean lemonadeChange(int[] bills) {
int fiveCount = 0;
int tenCount = 0;
for(int bill : bills){
if(bill == 5)
fiveCount++;
else if(bill == 10){
if(fiveCount > 0){
fiveCount--;
tenCount++;
}else return false;
} else if(bill == 20){
if(tenCount > 0 && fiveCount > 0){
tenCount--;
fiveCount--;
}else if(fiveCount > 2){
fiveCount -= 3;
}else return false;
}
}
return true;
}
}
[中等] 406. 根据身高重建队列
原题链接
有两个维度需要考虑的情况下，参考分发糖果，先处理一个维度再处理第二个维度。 本题先考虑身高排序，然后再按照k值插入对应的位置即可，因为题目数据确保能被重建，所以插入一个人时，所有比他高的人已经排完队了，前面一定有足够多的比他大的人。
也可以考虑使用LinkedList，但是由于本题的插入是指定下标的插入，在LinkedList也需要用O（n）的时间找到插入位置，效率不会比ArrayList高。
关于toArray()方法
class Solution {
public int[][] reconstructQueue(int[][] people) {
//people按照身高进行降序排序
Arrays.sort(people, new Comparator
@Override
public int compare(int[] o1, int[] o2) {
//如果身高相同，按照k进行升序排序
if (o1[0] == o2[0]) {
return o1[1] - o2[1];
}
//按照身高进行降序排序
return o2[0] - o1[0];
}
});
List
for(int i = 0; i < people.length; i++){
ans.add(people[i][1], people[i]);
}
//ans转换为二维数组
return ans.toArray(new int[0][]);
}
}
[中等] 452. 用最少数量的箭引爆气球
原题链接
其实就是判断重叠区间的问题，这里要判断的是如果区间有重叠区间就可以少射一支箭，箭数 = 区间总数-重叠次数，记住一个问题就是如果区间头尾相接，也算是能够一支箭射中两个。
compare函数不能使用return o1[1] - o2[1]，题目中给了一组数据{{-2147483646,-2147483645},{2147483646,2147483647}}，这组数据下会超出int 的范围，需要使用Integer.compare()函数 同理，没法直接用lambda表达式Arrays.sort(intervals, (i1, i2) -> i1[1] - i2[1]);
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1])
return Integer.compare(o1[0], o2[0]);
return Integer.compare(o1[1], o2[1]);
}
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, new Comparator
@Override
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1])
return Integer.compare(o1[0], o2[0]);
return Integer.compare(o1[1], o2[1]);
}
});
int cover = points[0][1];
int count = 1;
for(int i = 1; i < points.length; i++){
if(points[i][0] <= cover) continue;
count++;
cover = points[i][1];
}
return count;
}
}
[中等] 435. 无重叠区间
原题链接 贪心的思路在于，对所有重叠的区间来说，只能取其中一个，其他都要放弃，在按右端点排序所有区间的条件下，尽可能选择右端点数字最小的，能够尽可能把右边空间空出去选择更多区间。
将区间按右端点排序，然后从小到大循环，如果当前区间左端点大于等于上一次选择区间的右端点，则没有重叠，无需操作，并将cover更新为当前区间右端点，否则需要计数。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (i1, i2) -> i1[1] - i2[1]);
int cover = intervals[0][1];
int count = 0;
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] >= cover) {
cover = intervals[i][1];
continue;
}
count++;
}
return count;
}
}
[中等] 763. 划分字母区间
原题链接
使用char[] c = s.toCharArray比直接在String s 上读取字符效率更高一些，统计每个字符最远出现的下标，再下一次循环中，记录遍历到的字符的最远范围，一旦下标和最远范围相等，说明当前遍历到的字符全部出现在先前的序列里，可以分割。
class Solution {
public List
int[] charCover = new int[26];
char[] c = s.toCharArray();
for(int i = 0; i < s.length(); i++){
charCover[c[i] - 'a'] = i;
}
List
int count = 0;
int remote = 0;
for(int i = 0; i < s.length(); i++){
count++;
remote = Math.max(remote, charCover[c[i] - 'a']);
if(i == remote) {
ans.add(count);
count = 0;
}
}
return ans;
}
}
[中等] 56. 合并区间
原题链接 类似重叠区间和射箭题目，把合并边界记录好即可
class Solution {
public int[][] merge(int[][] intervals) {
List
Arrays.sort(intervals, new Comparator
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0] == o2[0]) return o1[1] - o2[1];
return o1[0] - o2[0];
}
});
int left = intervals[0][0];
int right = intervals[0][1];
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] <= right){
right = Math.max(right, intervals[i][1]);
left = Math.min(left, intervals[i][0]);
}else {
ans.add(new int[]{left, right});
left = intervals[i][0];
right = intervals[i][1];
}
}
ans.add(new int[]{left, right});
return ans.toArray(new int[0][]);
}
}
[中等] 738. 单调递增的数字
原题链接
class Solution {
public int monotoneIncreasingDigits(int n) {
char[] nums = String.valueOf(n).toCharArray();
int len = nums.length;
int flag = len;
for(int i = len - 1; i > 0; i--){
if(nums[i - 1] > nums[i]){
flag = i;
nums[i - 1]--;
}
}
for(int i = flag; i < len; i++){
nums[i] = '9';
}
return Integer.parseInt(new String(nums));
}
}
[困难] 968. 监控二叉树
原题链接
手动模拟了一下，摄像头一般不考虑放在叶子结点，除非这棵树只有一个节点，放在叶子结点浪费了摄像头对其子节点的监控能力。 采用后序遍历的思路来设计，在遍历时通过函数返回值标记当前节点的状态返回给父节点 1:需要摄像头覆盖 0:自身就是摄像头 -1:被摄像头覆盖，空节点也返回-1，假设他被摄像头覆盖而不需要父节点对其进行考虑 在递归处理中，如果左右子树有返回1，则当前节点需要一个摄像头，else if 左右子树有返回0，则当前节点被摄像头覆盖，要么就左右子树返回都是-1，则当前节点需要被父节点的摄像头覆盖。
class Solution {
int sum = 0;
public int minCameraCover(TreeNode root) {
if(recursion(root) == 1)
sum++;
return sum;
}
//三个返回值
// 1:需要摄像头覆盖
// 0:自身就是摄像头
// -1:被摄像头覆盖 空节点也返回-1，假设他被摄像头覆盖而不需要父节点对其进行考虑
public int recursion(TreeNode root){
if(root == null) return -1;
int left = recursion(root.left);
int right = recursion(root.right);
if(left == 1 || right == 1){
sum++;
return 0;
}else if(left == 0 || right == 0){
return -1;
}else{
return 1;
}
}
}
推荐阅读
您阅读本篇文章共花了：
发表评论