java算法day23

java算法day23

• 121买卖股票的最佳时机
• 55 跳跃游戏
• 45 跳跃游戏Ⅱ
• 763划分子母区间

121买卖股票的最佳时机

最容易想的应该就是两个for暴力枚举。但是超时

本题用贪心做应该是最快的。
先看清楚题，题目要求在某一天买入，然后在某一天卖出，要求利润最大。因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。

class Solution {
    public int maxProfit(int[] prices) {
        int minValue = Integer.MAX_VALUE;
        int maxValue = 0;
        for(int i = 0;i<prices.length;i++){
            minValue = Math.min(minValue,prices[i]);
            maxValue = Math.max(maxValue,prices[i]-minValue);
        }
        return maxValue;
    }

    
}

最主要的就是minValue不断的在维护左边的最小值，而maxValue = Math.max(maxValue,prices[i]-minValue);会在遍历的过程中，不断往右的过程中，不断的去探索最大值，所以这样就满足了贪心的思想。

真觉得没必要动态规划。

55 跳跃游戏

贪心的核心思路：
问题转化为跳跃覆盖范围究竟可不可以覆盖到终点。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

既然要找覆盖范围，那么扫过来每一个点都不能放过。由于只能在范围之内走动，所以循环条件多了一个i<=cover，但又不能超过数组总长，因此还有一个nums.length。
每到一个点就更新该点所能跳到的覆盖范围，每个点的覆盖范围的计算就是i+nums[i]。但是这个cover，要取最大范围，如果每到一个点用当前点的cover，那么就有可能漏结果。因此一定要是维护最大范围。

一旦发现cover大于等于nums.length-1即覆盖范围达到了最后一个元素，那么返回true。如果循环结束了都没返回true，那么就是不可能达到。

class Solution {
    public boolean canJump(int[] nums) {
        if(nums==null || nums.length==0){
            return false;
        }

        int cover = 0;
        for(int i = 0;i<=cover && i<nums.length;i++){
            cover = Math.max(cover,i+nums[i]);
            if(cover>=nums.length-1){
                return true;
            }
        }

        return false;
    }
}

45 跳跃游戏Ⅱ

这个题和跳跃游戏思维差不多，这里我还是再总结思想。
一定要跳出某一步能不能到达某个位置这种思想。而是应该在遍历中，去寻找某一步所能走出的最大范围。

比如从第一步开始，确定了第一步能够走到的最大范围，那么我们需要做的是，在这个第一步的最大范围内，找到往后覆盖的最大范围。那么i一直往后走，这个时候我们知道i能往后走，但是不关注从哪里跳的，所以没有必要去定位要到哪个地方才能跳到下一个位置。因为对于上一个题（跳跃游戏）而言，题目并不是关注要到哪个地方跳，而是问能不能到。对于本题而言，再每一步中找到下一步所能覆盖到的最大范围，当i走完第一步覆盖的范围，那么此时就必须要走下一步了，还是同理，我们根本就不关注是从哪个地方走的下一步，只是知道我们要走出第一步的范围，那么肯定是要走下一步的。所以可以判断出，如果当前位置到了当前步的最大位置，那么步数肯定要+1了，因为下一个区域是走第二步之后才能到达的区域。

现在来看代码怎么写：
1.关键变量：
curDistance：当前这“一步”能够达到的最远距离
nextDistance：下一步可能到达的最远距离。
ans：跳跃次数

（1）遍历数组，对于每个位置i，都要去更新nextDistance，即“下一步”可能到达的最远位置。
（2）如果i到达了curDistance，当前这一步到达的最远距离，如果curDistance不是数组末尾，那么就要增加跳跃次数，更新curDistance为nextDistance。
如果curDistance是数组末尾，提前break，结束循环。还有一个快速特判，nextDistance已经可以到达数组末尾，提前结束循环。

3.特殊条件，当i==curDistance时我们需要觉得是否再跳一次，如果curDistance不是数组末尾，那么就要再跳一次，如果是那就不需要跳了。

贪心思想：
我们总是贪心地选择当前可以到达的最远距离，然后在这个范围内找下一个最远距离。这样，我们可以保证用最少的跳跃次数到达终点。

class Solution {  
    public int jump(int[] nums) {  
        if (nums.length == 1) {  
            return 0;  
        }  
        
        int curDistance = 0;  // 当前覆盖的最远距离下标  
        int nextDistance = 0; // 下一步覆盖的最远距离下标  
        int jumps = 0;        // 跳跃次数  
        
        //不处理最后一个位置，因为那个位置没必要走。
        for (int i = 0; i < nums.length - 1; i++) {  
            // 更新下一步可以覆盖的最远距离  
            //因为一开始curDistance=0，所以要先更新，不然下一步没法走
            nextDistance = Math.max(nextDistance, i + nums[i]);  
            
            // 走的过程中看看是否到了“当前步的最远”
            if (i == curDistance) {  
            	//到了当前步最远就要进行跳跃了，
                jumps++;                 // 进行跳跃  
                curDistance = nextDistance; // 更新当前覆盖的最远距离  
                
                // 先看看这个覆盖距离，如果已经能到最后一个位置，那么直接break了。
                //也就是在这一步中肯定能到末尾。  
                if (curDistance >= nums.length - 1) {  
                    break;  
                }  
            }  
        }  
        
        return jumps;  
    }  
}

763划分字母区间

题目意思翻译：
段数尽可能多，每一段中保证同一子母最多出现在一个段中。

这个题我建议是理解后记一下思路：
暴力做法就是回溯，这个题如果是回溯，那么就是切割字符串问题。然后对切好的字符串进一步进行题意的判断。但是这就太麻烦了。

贪心做法：

在做之前还要告搞懂一个问题：那么如何把同一个字母的都圈在同一个区间里呢？
做法：
1.遍历统计每一个字符最后出现的位置
2.从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

我只能说这个解法真的很神奇。我是从模拟的角度来看这个算法的：

1.每个子串是从当前未处理的第一个字符开始的。

2.然后，我们不断地"扩展"这个子串，直到包含了所有需要包含的字符。

3.这个"扩展"过程是通过查看每个字符的最后出现位置来实现的。如果我们在扩展过程中遇到了一个字符，它的最后出现位置比我们当前考虑的结束位置更靠后，我们就需要进一步扩展子串。

4.当我们遍历到的位置恰好等于当前考虑的结束位置时，我们就找到了一个可以安全划分的点。

5.然后我们就可以开始处理下一个子串，重复这个过程。

这个方法之所以如此巧妙，是因为它利用了问题的特性：

我们必须把每个字符的所有出现都包含在同一个子串中。
我们想要尽可能多的划分（即尽可能多的子串）

通过只向前看（即只考虑字符的最后出现位置），我们可以在一次遍历中得到最优解，这看起来就是通过局部最优的选择，最终达到全局最优。

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> list = new LinkedList<>();
        //用于记录每个子母最后出现的位置
        int[] edge = new int[26];
        char[] chars = S.toCharArray();
        //遍历字符串s，扫描完之后记录了对应子母最后出现的位置。
        for (int i = 0; i < chars.length; i++) {
            edge[chars[i] - 'a'] = i;
        }
        int idx = 0;//当前子串的结束位置
        int last = -1;//上一个子串的结束位置
        //再次遍历字符串s，这里使用双指针
        for (int i = 0; i < chars.length; i++) {
            idx = Math.max(idx,edge[chars[i] - 'a']);
            if (i == idx) {
                list.add(i - last);
                last = i;
            }
        }
        return list;
    }
}