算法面试——贪心算法：跳跃游戏、分发饼干、加油站

贪心算法是每一步都选局部最优解，期望得到全局最优。不一定对所有问题有效，但对这几类经典题有效。

一、跳跃游戏

publicbooleancanJump(int[]nums){intmaxReach=0;for(inti=0;i<nums.length;i++){if(i>maxReach)returnfalse;maxReach=Math.max(maxReach,i+nums[i]);if(maxReach>=nums.length-1)returntrue;}returntrue;}

二、分发饼干

publicintfindContentChildren(int[]g,int[]s){Arrays.sort(g);Arrays.sort(s);intchild=0,cookie=0;while(child<g.length&&cookie<s.length){if(s[cookie]>=g[child]){child++;}cookie++;}returnchild;}

三、加油站

publicintcanCompleteCircuit(int[]gas,int[]cost){inttotal=0,current=0,start=0;for(inti=0;i<gas.length;i++){total+=gas[i]-cost[i];current+=gas[i]-cost[i];if(current<0){start=i+1;current=0;}}returntotal>=0?start:-1;}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！