【Leetcode刷题】【45558604551221343921221】跳跃游戏，柠檬水找零，分发饼干，买卖股票的最佳时机,加油站

文章目录

跳跃游戏II题目描述 跳跃游戏I题目描述 860柠檬水找零题目描述 455分发饼干题目描述 122买卖股票的最佳时机题目描述 134加油站题目描述 392判断子序列题目描述 1221分割平衡字符串题目描述

跳跃游戏II

题目描述

首先我们来审题，这里是要找出到达最后一个位置需要跳跃多少次，而每次跳跃的步数要在该位置的值之内，注意，比如第0号位置值为2，则可以跳1补，也可以跳两步，主要是要找到最少次数跳到最后一个位置

如下图，开始的位置是 2，可跳的范围是橙色的。然后因为 3 可以跳的更远，所以跳到 3 的位置。

如下图，然后现在的位置就是 3 了，能跳的范围是橙色的，然后因为 4 可以跳的更远，所以下次跳到 4 的位置 所以我们这里主要是更新边界值，边界值则是找i+nums[i]最大的，跳的最远，同时还要注意i<length-1,少了末尾，因为到末尾也不能往后跳了，所以不用遍历，同时第0号位置时跳跃次数已经加了1。

class Solution { public int jump(int[] nums) { int length = nums.length; int end = 0; int maxPosition = 0; int steps = 0; for (int i = 0; i < length - 1; i++) { //找能跳的最远的 maxPosition = Math.max(maxPosition, i + nums[i]); if (i == end) {//遇到边界更新边界 end = maxPosition; steps++; } } return steps; } }

跳跃游戏I

题目描述

这里要判断能否到达最后一个元素，只要看边界能否大于等于length-1,也就是边界大于等于最后一个位置，就可以跳跃到最后一个位置

class Solution { public boolean canJump(int[] nums) { int length = nums.length; int end = 0; int maxPosition = 0; for (int i = 0; i < length - 1; i++) { //找能跳的最远的 maxPosition = Math.max(maxPosition, i + nums[i]); if (i == end) {//遇到边界更新边界 end = maxPosition; } } return end>=length-1; } }

860柠檬水找零

题目描述

我们这里的思路是用两个变量来记录5元的张数和10元的张数，当遍历过程发现有一个变量小于0就返回false,然后在面值为20的时候判断，如果10元的还有剩余，就返还一张10元和一张5元，若无剩余则直接返还3张5元。

class Solution { public boolean lemonadeChange(int[] bills) { if(bills[0]==10||bills[0]==20){ return false; } int count=0;//计算5美元的剩余张数 int cnt=0;//计算10美元的剩余张数 for(int i=0;i<bills.length;i++){ if(bills[i]==5){ count++;//5美元加一 } if(bills[i]==10){ count--;//5美元减一，10美元加一 cnt++; } if(bills[i]==20){ if(cnt>0){//如果10美元张数大于0，就返还1张10美元1张5美元 cnt--; count--; } else{//否则返还3张5美元 count-=3; } } if(cnt<0||count<0){//每一轮循环判断5美元和10美元的张数是否小于0，小于则返回false return false; } } return true; } }

455分发饼干

题目描述

贪心算法： 从胃口小的开始分配，所以将孩子数组从小到大排序，饼干也从小到大排序，第一个孩子开始匹配饼干，遍历饼干数组直到找到满足的，满足则i++,j++轮换到下一个孩子，不满足就j++遍历饼干。

class Solution { public int findContentChildren(int[] g, int[] s) { int res=0; Arrays.sort(g); Arrays.sort(s); int i=0; int j=0; while(i<g.length&&j<s.length){ if(g[i]<=s[j]){ res++; i++; j++; } else {j++;} } return res; } }

122买卖股票的最佳时机

题目描述

找到前一个比后一个小的，因为不能同时参与多笔交易，然后拿后一个值减去前一个，得到的就是该笔交易利润，然后存在res，之后把每一个res相加，就是最后总的交易利润。

class Solution { public int maxProfit(int[] prices) { int res=0; for(int i=0;i<prices.length-1;i++){ if(prices[i]<prices[i+1]){ res+=prices[i+1]-prices[i]; } } return res; } }

134加油站

题目描述

gas = [1,2,3,4,5] cost = [3,4,5,1,2] 记tmpCost[i]=cost[i]-gas[i]，那么我们就能得到

tmpCost=[2,2,2,-3,-3]

其中负数表示加油站能额外提供给车子的油量，显然当tmpCost的总和小于等于0时有解，否则无解（因为整个过程中车子自己不能变出油来）。在一遍扫描的过程中使用一个变量totalCost存储tmpCost[i]的和就可以了（并不需要建立该O(n)大小的数组，上面的数组只是为了便于说明）。

下面要找到开始出发点，假设出发点为startIndex，当前位置为i，则一旦[startIndex,i]区间中所有的tmpCost之和大于0，说明汽车走不下去了。使用一个变量startToCurrentCost来保存这个值，当汽车走到当前位置走不下去时，重置startIndex为i+1、startToCurrentCost为0。

当最终遍历完，并且totalCost<0时，startIndex就是始发加油站，否则无解返回-1

class Solution {//一次遍历 public int canCompleteCircuit(int[] gas, int[] cost) { int totalCost=0,startIndex=0,startToCurrentCost=0; for(int i=0;i<gas.length;i++){ //tmpCost表示从当前加油站到达下一个加油站至少需要汽车已有油多少升 int tmpCost=cost[i]-gas[i]; totalCost+=tmpCost; startToCurrentCost+=tmpCost; //如果该值大于零，则重置始发站为下一站点，重置startToCurrentCost为0 if (startToCurrentCost > 0) { startIndex = i + 1; startToCurrentCost = 0; } } if(totalCost<=0) return startIndex; else return -1; } }

392判断子序列

题目描述

//贪心算法 class Solution { public boolean isSubsequence(String s, String t) { if (s == null || t == null) return true; int sLen = s.length(); int index = 0, loc = 0; for (int i = 0; i < sLen; i++) { loc = t.indexOf(s.charAt(i), index);//返回从 index 位置开始查找指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。 if (loc < 0) return false;//如果找不到这个字符indexOf（）则会返回-1 index = loc + 1;//从找到字符的下一个位置开始继续查找下一个字符，因为是要按顺序的 } return true; } }

1221分割平衡字符串

题目描述

class Solution { public int balancedStringSplit(String s) { int balance=0; int cnt=0; for(int i=0;i<s.length();i++){ if(s.charAt(i)=='R') balance++; if(s.charAt(i)=='L') balance--; if(balance==0) cnt++; } return cnt; } }