贪心策略在算法设计中的应用与优化

• 思路&＃xff1a;dp[i]表示能否到达位置i&＃xff0c;对每个位置i判断能否通过前面的位置跳跃过来&＃xff0c;当前位置j能达到&＃xff0c;并且当前位置j加上能到达的位置如果超过了i&＃xff0c;那dp[i]更新为ture&＃xff0c;便是i位置也可以到达。
• 复杂度&＃xff1a;时间复杂度O(n^2)&＃xff0c;空间复杂度O(n)

class Solution {
public boolean canJump(int[] nums) {
int n &＃61; nums.length;
boolean[] dp &＃61; new boolean[n];
dp[0] &＃61; true;
for (int i &＃61; 1; i < n; i&＃43;&＃43;) {
for (int j &＃61; 0; j < i; j&＃43;&＃43;) {
//当前位置j能达到&＃xff0c;并且当前位置j加上能到达的位置如果超过了i&＃xff0c;那dp[i]更新为ture&＃xff0c;便是i位置也可以到达
if(dp[j] &＃61;&＃61; true && nums[j] &＃43; j >&＃61; i){
dp[i] &＃61; true;
break;
}
}
}
return dp[n - 1];
}
}


2.贪心

• 思路&＃xff1a;不用考虑每一步跳跃到那个位置&＃xff0c;而是尽可能的跳跃到最远的位置&＃xff0c;看最多能覆盖的位置&＃xff0c;不断更新能覆盖的距离。
• 复杂度&＃xff1a;时间复杂度O(n)&＃xff0c;遍历一边。空间复杂度O(1)

public boolean canJump(int[] nums) {
if (nums.length &＃61;&＃61; 1) {
return true;
}
int cover &＃61; nums[0];//能覆盖的最远距离
for (int i &＃61; 0; i <&＃61; cover; i&＃43;&＃43;) {
cover &＃61; Math.max(cover, i &＃43; nums[i]);//当前覆盖距离cover和当前位置加能跳跃的距离中取一个较大者
// 覆盖距离超过或等于nums.length - 1 说明能到达终点
if (cover >&＃61; nums.length - 1) {
return true;
}
}
return false;//循环完成之后 还没返回true 就是不能达到终点
}


• 思路&＃xff1a;题意是一条船只能坐2人&＃xff0c;要求尽可能的用少的船装下这些人。所以可以用贪心策略。让更多的人组成2人组&＃xff0c;而且这些2人组的两人重量加起来不超过船的载重。所以可以先排序people&＃xff0c;用双指针从两边向中间遍历&＃xff0c;让重的人和轻的人组成2人组&＃xff0c;如果当前最重的人和最轻的人的重量和超过了载重&＃xff0c;那只能让重的人先乘一条船。
• 复杂度&＃xff1a;时间复杂度O(nlogn)&＃xff0c;排序的复杂度。空间复杂度O(logn)&＃xff0c;排序的栈空间

代码

public int numRescueBoats(int[] people, int limit) {
int n &＃61; people.length;
Arrays.sort(people);
int left &＃61; 0;
int right &＃61; n-1;
int nums &＃61; 0;
//让最重的最轻的先走
while (left <&＃61; right){
if(people[right] &＃43; people[left] <&＃61; limit){
right--;
left&＃43;&＃43;;
nums&＃43;&＃43;;
}else{
//让最重的一个人走
right--;
nums&＃43;&＃43;;
}
}
return nums;
}


class Solution {
public int findMinArrowShots(int[][] points) {

//按照右边界升序排序
Arrays.sort(points, (o1, o2) -> {
return Integer.compare(o1[1], o2[1]);
});
int n &＃61; points.length;
// for (int[] point : points) {
// for (int i : point) {
// System.out.print(i &＃43; " ");
// }
// System.out.println();
// }
int nums &＃61; 1;
int right &＃61; points[0][1];

//如果下一个的左边比之前的右边大 nums&＃43;1
for (int i &＃61; 1; i < n; i&＃43;&＃43;) {
if (points[i][0] > right) {
right &＃61; points[i][1];
nums&＃43;&＃43;;
}
}
return nums;
}
}


• 思路&＃xff1a;首先判断总油量是否小于总油耗&＃xff0c;如果是则肯定不能走一圈。如果否&＃xff0c;那肯定能跑一圈。接下来就是循环数组&＃xff0c;从第一个站开始&＃xff0c;计算每一站剩余的油量&＃xff0c;如果油量为负了&＃xff0c;就以这个站为起点从新计算。如果到达某一个点为负&＃xff0c;说明起点到这个点中间的所有站点都不能到达该点。
• 复杂度&＃xff1a;时间复杂度O(n)&＃xff0c;空间复杂度O(1)

代码

class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n &＃61; gas.length;
int sumGas &＃61; 0;
int sumCost &＃61; 0;
for (int i &＃61; 0; i < n; i&＃43;&＃43;) {
sumGas &＃43;&＃61; gas[i];
sumCost &＃43;&＃61; cost[i];
}
//如果总油量小于总距离,失败
if (sumGas < sumCost) {
return -1;
}
int currentGas &＃61; 0;
int start &＃61; 0;
for (int i &＃61; 0; i < n; i&＃43;&＃43;) {
currentGas &＃43;&＃61; gas[i] - cost[i];
//如果到达下一站的时候油量为负数 就以这个站为起点 从新计算
if (currentGas < 0) {
currentGas &＃61; 0;
start &＃61; i &＃43; 1;
}
}
return start;
}
}


class Solution {
public boolean lemonadeChange(int[] bills) {
int five &＃61; 0, ten &＃61; 0;
for (int bill : bills) {
if (bill &＃61;&＃61; 5) {
five&＃43;&＃43;;
} else if (bill &＃61;&＃61; 10) {
if (five &＃61;&＃61; 0) {
return false;
}
five--;
ten&＃43;&＃43;;
} else {
if (five > 0 && ten > 0) {
five--;
ten--;
} else if (five >&＃61; 3) {
five -&＃61; 3;
} else {
return false;
}
}
}
return true;

}
}