本文共 3448 字，大约阅读时间需要 11 分钟。
1.一次性：某个状态以后的过程不会影响以前的状态，只与当前状态有关。
2.局部最优集合能得到全局最优。 （如果某次选择会对之后选择产生影响，局部最优不能获得全局最优可以直接KO贪心思路） 第一步，判断是否属于贪心算法的情况：对一组数据加了一定的限制，希望从中选出几个数据，在满足限制值的情况下，达到最大期望值。 第二步，用简单例子检测贪心算法是否最优。依据个人经验分成了三大类
1.分饼干，跳跃游戏，环绕加油站等每次从最小的开始分配从问题的某一初始解出发； while （到达目标边界） { if(该阶段的状态满足最优条件)加入此局部最优解； 进入下一阶段； } return 由所有解元素组合成问题的一个可行解； 注：求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
import java.util.Arrays; public class AssignCookie{ public static int contentChildren(int[]g,int[]s){ assert g.length>0||s.length>0; Arrays.sort(g); Arrays.sort(s); //定义第i个小孩的appetite对应第j块饼干 int i=0,j=0; //当小孩没满足完或饼干没发完 while(i /** *在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 * 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。 */public class GasStation { /** *一旦遇到第一个无法到达的点 i，直接更换起始点为 i+1。中间的 [1,i-1] 的点一定不是起始点 * @param gas * @param cost */ public int canCompleteCircuit(int[] gas, int[] cost) { int sum = 0;//选定起点到现在的油缸量 int total = 0;//总的加油与耗油差值 int result = 0;//选定的起点 for(int i = 0;i =0?result:-1; }} public class isSubsequence { /* * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 * 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。 *字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。 */ public boolean isSubsequence(String s, String t) { if(0==s.length()) return true; //母串序列索引i，子串j int sub = 0,j = 0; //不能用for循环是考虑到s比t长 while( sub < t.length()){ //如果不同只有母串后移 if(s.charAt(sub)==t.charAt(j)) sub++; j++; } //返回结果里判别是否子串全找到了，很有技巧 return sub==s.length(); }} 192.跳跃游戏
public class JumpGame { public static boolean canJump(int[] nums){ assert nums.length>0; if(nums.length==1)return true; //数组首位为0且0不是唯一元素肯定跳不到最后 if(nums.length>1&&nums[0]==0)return false; for (int i = 1; i < nums.length-1; i++) { int j = i - 1; while (nums[i] == 0) { //前面两个if是找到j的情况，说明这个0元素是可以被到达或跳过的 // if (nums[j] >= i - j&&i==nums.length-1) break; if (nums[j] > i - j) break; if (j <= 0) return false; j--; } } return true; } //just for test public static void main(String[] args) { Scanner input = new Scanner(System.in); String s = input.next(); String[] arr = s.split(","); int[] arry = new int[arr.length]; for (int i = 0; i < arr.length; i++) { arry[i] = Integer.parseInt(arr[i]); } boolean result =canJump(arry); System.out.println(result); }} import java.util.Scanner;/** * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 * 输入[-2,1,-3,4,-1,2,1,-5,4]；输出6；因为连续子数组 [4,-1,2,1] 的和最大，为 6。 */public class MaxSubarray { public static int maxSubarray(int[] nums) { //sum存子序和，max表示选好子序手标的某次的和 int sum = nums[0]; int max = 0; for(int i=0;i 转载地址：http://dfrsi.baihongyu.com/