欢迎光临
我们一直在努力

【贪心算法】加油站,单调递增的数字,坏了的计算器,合并区间,用最少数量的箭引爆气球

1. 加油站(LC 134)

加油站

题目描述

在这里插入图片描述

解题思路

枚举

枚举所有起点,判断是否能绕一周。可以用diff数组记录每个加油站收入与支出,从diff为正数的位置开始枚举

贪心优化

假设i为起点,到j位置油量小于零,由于起点的收益一定是正数,如果从i+1位置开始,到j位置的剩余油量一定更小,也就不可能到j位置。因此下一次枚举可以从j开始尝试。

代码实现

  • 枚举(超时)

public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int[] diff = new int[n];
for(int i = 0;i<n;i++)
diff[i] = gas[i]–cost[i];

for(int i = 0;i<n;i++){
if(diff[i]>=0){
int step = 0;
int rest = 0;
int j = i;
boolean flag = true;
while(step<n){
rest+=diff[j];
if(rest<0){
flag = false;
break;
}
j = j+1<n?j+1:0;
step++;
}
if(flag)
return i;
}
}
return –1;
}

  • 贪心

public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int[] diff = new int[n];
for(int i = 0;i<n;i++)
diff[i] = gas[i]–cost[i];

for(int i = 0;i<n;i++){
if(diff[i]>=0){
int step = 0;
int rest = 0;
int j = i;
boolean flag = true;
while(step<n){
rest+=diff[j];
if(rest<0){
flag = false;
break;
}
j = j+1<n?j+1:0;
step++;
}
if(flag)
return i;
i+=step;
}
}
return –1;
}

2. 单调递增的数字(LC 738)

单调递增的数字

题目描述

在这里插入图片描述

解题思路

  • 如果高位递增,不需要修改
  • 从左向右找到不递增的位置,让它-1,后面的数都填9.
  • 如果遇到一段相同的数字,例如1245554321修改成12345549999,还需要再把前面的5改成4,这里可以用递归的思想,直到修改成递增的数字。
  • 代码实现

    public int monotoneIncreasingDigits(int n) {
    char[] num = (n+"").toCharArray();
    int len = num.length;
    boolean flag = true;
    for(int i = 0;i<len–1;i++){
    if(num[i]>num[i+1]){
    flag = false;
    num[i] -=1;
    for(int j = i+1;j<len;j++)
    num[j] = '9';
    break;
    }
    }
    int ret = Integer.parseInt(new String(num));
    if(flag)
    return ret;
    else
    return monotoneIncreasingDigits(ret);
    }

    3. 坏了的计算器(LC 991)

    坏了的计算器

    题目描述

    在这里插入图片描述

    解题思路

    正难则反

    把target转换成startValue,进行+1或/2操作

  • 如果s>=t只能进行加法操作,两数之差就是操作次数
  • 如果s<t,要分类讨论
    • 如果当前是奇数,只能+1
    • 如果当前是偶数,优先/2
  • 代码实现

    public int brokenCalc(int startValue, int target) {
    int ret = 0;
    while(target>startValue){
    if(target%2 == 0)
    target/=2;
    else
    target+=1;
    ret++;
    }
    ret+=startValue–target;

    return ret;
    }

    4. 合并区间(LC 56)

    合并区间

    题目描述

    在这里插入图片描述

    解题思路

    先按左端点排序,后面依次判断能否合并。创建一个ArrayList<Integer>保存结果

    • 如果当前的数组和Arrlist的最后一个数组存在重叠区域,直接合并,右端点取两者的最大值
    • 如果不重叠,添加新数组

    补充语法知识:

  • Collection的toArray()方法:
    • Object[] toArray():返回包装集合数组,不能强转成int[][]。
    • <T> T[] toArray(T[] a):将集合转换为指定类型的数组。
      • 如果参数数组的大小小于集合,会创建一个新的数组,且类型相同,大小与集合相等。伊因此可以直接传入int[0][]
  • int[] last = list.getLast(),last拿到了list最后一个元素的引用,对last 修改就可以直接修改list
  • 代码实现

    public int[][] merge(int[][] intervals) {
    int n = intervals.length;
    Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));

    ArrayList<int[]> list = new ArrayList<>();
    list.add(intervals[0]);

    for(int i=1;i<n;i++){
    int[] last = list.getLast();
    if(intervals[i][0]<=last[1])
    last[1] = Math.max(intervals[i][1],last[1]);
    else
    list.add(intervals[i]);
    }

    int[][] ret = list.toArray(new int[list.size()][2]);
    return ret;
    }

    5. 无重叠区间(LC 435)

    无重叠区间

    题目描述

    在这里插入图片描述

    解题思路

    对左端点排序,比较右端点,如果有重叠,保留右端点更小的区间,舍弃右端点更大的区间。

    右端点可以用一个变量维护

    代码实现

    public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
    int n = intervals.length;

    int ret = 0;
    int last = intervals[0][1];
    for(int i = 1;i<n;i++){
    if(intervals[i][0]<last){
    last = Math.min(last,intervals[i][1]);
    ret++;
    }else
    last = intervals[i][1];
    }
    return ret;
    }

    6. 用最少数量的箭引爆气球(LC 452)

    用最少数量的箭引爆气球

    题目描述

    在这里插入图片描述

    解题思路

  • 按左端点排序
  • 找出两个区间的交集,与下一个区间比较,如果下一个区间与前面的交集重叠,则证明可以共用一个箭,因为是取交集,右端点取最小值;否则说明需要新的箭,更新右端点。
  • 代码实现

    public int findMinArrowShots(int[][] points) {
    int n = points.length;
    Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
    int ret = 1;
    int right = points[0][1];
    for(int i = 1;i<n;i++){
    if(points[i][0]<=right)
    right = Math.min(points[i][1],right);
    else{
    ret++;
    right = points[i][1];
    }
    }
    return ret;
    }

    赞(0)
    未经允许不得转载:171主机测评 » 【贪心算法】加油站,单调递增的数字,坏了的计算器,合并区间,用最少数量的箭引爆气球
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址