LeetCode 134 加油站

题目链接：134.加油站

文档讲解：代码随想录

视频讲解：加油站

思路与感想：一开始的做法就是普通的暴力写法，但是在内层for循环模拟绕圈的时候想着每次都用Arrays.copyof来创建新的gas和cost数组，实现绕圈，但是这样太麻烦了而且似乎出了点问题，问AI才发现有更优的暴力写法，模拟绕圈可以使用取模，学习了。最后超出时间限制了，然后就去看卡哥的视频讲解，贪心算法的思路其实跟暴力很像，我说的是内层判断当前起点不合适上，但是它这种方法没有让所有索引都成为一次起点，而是只有当不满足条件时，把起点更新为i+1，后面再根据totalSum是否大于等于0再决定是直接返回-1还是返回start。核心逻辑还有一个就是如果totalSum大于等于0，那总有一个起点是可以满足绕一圈的，而如果totalSum小于0，那无论你怎么选起点都饶不了一圈。

收获：1.取模实现绕圈；2.Arrays.copyof的使用

// 模拟法
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (!compare(gas,cost)) { // 如果总油量小于总消耗说明肯定到不了直接返回-1
            return -1;
        }
        for (int i = 0; i < gas.length; i++) { // 外层for循环定起点
            int sum = 0; // 记录同一起点下当前的油量
            boolean mark = true; // 标记有无出现负油量情况
            for (int j = 0; j < gas.length; j++) {
                int idx = (i + j) % gas.length; // 取模运算使得gas和cost能够取到起点之前的索引
                sum += gas[idx] - cost[idx];
                if (sum < 0) { // 一旦当前油量为负数说明该起点不能满足环路行驶一圈
                    mark = false; // 把mark置为false然后直接break进入下一层外层for循环
                    break;
                }
            }
            if (mark) { // 如果mark没被修改，说明没有出现负油量情况，而且内部for循环执行完毕，说明可以完整绕一圈，返回当前起点
                return i;
            }
        }
        return -1; // 如果整个外层for循环都没有return，就说明已经考虑了所有起点情况都无法实现环路行驶一圈，直接return -1
    }
    public boolean compare(int[] gas, int[] cost) { // 比较总油量与总消耗
        int sumGas = 0;
        int sumCost = 0;
        for (int i = 0; i < gas.length; i++) { 
            sumGas += gas[i];
            sumCost += cost[i];
        }
        boolean result = sumGas >= sumCost ? true : false;
        return result;
    }
}

// 贪心算法
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalSum = 0; // 记录总加油量和耗油量差值，如果大于等于0说明一定可以跑完一圈，否则一定不可以跑完
        int curSum = 0; // 记录当前起点下连续经过每一个站点车的剩余油量
        int start = 0; // 记录起点
        for (int i = 0; i < gas.length; i++) {
            totalSum += (gas[i] - cost[i]);
            curSum += (gas[i] - cost[i]);
            if (curSum < 0) { // 一旦发现车的剩余油量小于0说明该起点出发跑不完，就要让i + 1作为新起点
                curSum = 0; // 重置curSum
                start = i + 1;
            }
        }
        if (totalSum < 0) { // 如果totalSum小于0就说明一定跑不完一圈
            return -1;
        }
        return start; // 返回起点
    }
}

LeetCode 135 分发糖果

题目链接：135.分发糖果

文档讲解：代码随想录

视频讲解：分发糖果

思路与感想：这道题完全没思路啊感觉看上去很复杂，卡哥提示的先处理一边再处理另一边完全不知道在说什么。看了视频讲解后却发现整体代码和思路却挺简单的，首先是先从左到右遍历，考虑右边评分大于左边评分，那就更新右孩子的糖果数量为左孩子的数量加一，否则就置为1等后面再处理。然后从右往左遍历，考虑左边评分大于右边评分，那就更新左孩子的糖果数量为右孩子的数量加一，当然这样更新仅仅是满足了左边评分大于右边评分，但别忘了我们之前从左往右遍历的时候，即考虑右边评分大于左边评分的时候candy[i]已经赋过一轮值了，所以这回更新的值是右孩子的数量加一和其原本的candy[i]值做一个取最大值操作，保证两个条件都能满足。当然如果左边评分大于右边评分这个条件不满足的话candy[i]就不用更新了。

收获：1.相邻情况涉及两边，先考虑一边再考虑另一边，注意遍历顺序

// 贪心算法
class Solution {
    public int candy(int[] ratings) {
        int[] candy = new int[ratings.length]; // 记录每个人的糖数量
        candy[0] = 1; // 每个人至少一个糖果，起点先设置为一个糖果
        for (int i = 1; i < candy.length; i++) { // 先考虑从左往右，右边评分大于左边评分的情况，满足条件的把糖果更新为其左边糖果数量加1，不满足的置为1
            candy[i] = (ratings[i] > ratings[i - 1]) ? candy[i - 1] + 1 : 1;
        }
        for (int i = candy.length - 2; i >= 0; i--) { // 再考虑从右往左，左边评分大于右边评分，满足条件的就把糖果更新为右边糖果数加1，但因为还要兼顾右边评分大于左边评分的情况，先前考虑该情况时candy[i]已经有值了，所以为了兼顾两种情况，要在这两个值间取更大的哪个，如果直接取右边糖果数加1，那可能会比原先的candy[i]更小，那样就满足不了右边评分大于左边评分了
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = Math.max(candy[i],candy[i + 1] + 1);
            }
        }
        int result = 0; // 统计总的糖果数量
        for (int i : candy) {
            result += i;
        }
        return result;
    }
}

LeetCode 860 柠檬水找零

题目链接：860.柠檬水找零

文档讲解：代码随想录

视频讲解：柠檬水找零

思路与感想：这道题目看上去确实有点唬人，但却是纸老虎，稍一分析就会发现如卡哥所说情景十分固定，由于找零只需要5和10美元，所以每次遍历一个新的订单也只需要记录这两种钞票即可，至于找零首先出价5美元是不需要找零的，10美元呢也只有找零5美元一种方式，20美元呢有10+5或者5+5+5两种方式，而本题的贪心也在于此，自己AC的时候确实潜意识里觉得这就是常识，但还是意识到这是一种贪心策略了，如果有10美元就尽可能在这种情况下使用10美元，毕竟5美元找零的通用性可比10美元更好，其实这也就是一种局部最优了，而全局最优就是店家能够找零所有订单，保留找零通用性更大的5美元也是服务于这一全局最优目的。

收获：1.分析不同情况，不被题目吓到

// 贪心算法
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int dollarFive = 0; // 只有5美元和10美元可以用于找零，所以只需要记录手上这两种钞票的数量
        int dollarTen = 0;
        for (int i = 0; i < bills.length; i++) { // 遍历所有账单
            if (bills[i] == 10) { // 如果遇到出价10美元的订单
                if (dollarFive > 0) { // 检查手中也没有5美元进行找零
                    dollarTen++; // 有的话10美元钞票数量加一
                    dollarFive--; // 5美元钞票数量减少
                    continue; // 继续下一个订单
                } else {
                    return false; // 没有5美元找零的话那就只能return false了
                }
            } else if (bills[i] == 20) { // 遇到出价20美元订单,检查手中也没有至少一张5美元和一张10美元钞票，或者至少3张五美元钞票
                if (dollarFive > 0 && dollarTen > 0) { // 本题贪心局部贪心，如果有10美元肯定优先花10美元，因为10美元通用性不如5美元，无法找零10美元的订单，以利于店家正确找零所有顾客
                    dollarTen--; // 10美元钞票自减
                    dollarFive--; // 5美元钞票也要自减
                } else if (dollarFive > 2) { // 没有十美元钞票那只能找三张5美元了
                    dollarFive -= 3;
                } else { // 找不了零直接return
                    return false;
                }
            } else {
                dollarFive++; // 碰到5美元出价订单了，不用找零，手上5美元钞票数量自增
            }
        }
        return true; // 如果所有账单遍历完了还没有return false，说明成功给每位顾客找零，return true
    }
}

LeetCode 406 根据身高重建队列

题目链接：406.根据身高重建队列

文档讲解：代码随想录

视频讲解：根据身高重建队列

思路与感想：这道题目真难想到啊，完全想不到处理的两个维度，但一说出来又觉得确实只能这么想，而且题目两个维度给的很明确就是一个h一个k。那接下来呢，其实就算知道了这俩维度你也不一定能想到接下来的”处理“对应的是什么操作，那其实要靠分析的就是排序操作，首先尝试对k维度进行处理，那排序操作是升序还是降序呢，那一定是升序，因为k的意思是前面有几个人人身高大于等于此人身高，但是这样排序后，由于k一定是建立在h之上进行判断的，这样暴力升序排的话h首先就是乱的，h一乱那k不必说也是乱的，所有这样排哪一个维度都没确定下来。那就考虑先处理h维度，那还是先问自己升序还是降序呢，那肯定是降序的。原因的话我也不是特别清楚，大概是降序的话，如果后面的人要插到前面来是不会影响前面的人的顺序，因为k表示的是前面大于等于自己身高的人数，哪怕说后面矮的人插到前面来了，那这个k也不会变，所有也没有影响。那如果排序的时候遇到h相同的应该怎么排，那就按照k升序排，使之尽可能符合k的含义与题目要求。这样排序拍好了之后就可以依次遍历队列中每个人，按照它们各自的k插入的重建的新队列中，最后得到的结果就是正确的。

收获：1.多个维度要考虑时一个维度一个维度的考虑，试着确定一个维度考虑另一个维度。

// 贪心算法
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(a,b) -> { // 把people按照身高维度降序排序
            if (a[0] == b[0]) { // 如果身高相同，按照k维度升序排序
                return a[1] - b[1]; // a - b是升序
            };
            return b[0] - a[0]; // b-a是降序
        });
        List<int[]> que = new LinkedList<>(); // 作为重建的队列
        for (int[] i : people) {
            que.add(i[1],i); // 每个人按照k进行插入操作
        }
        return que.toArray(new int[people.length][]); // 转换成二维数组
    }
}

今天花了八个小时，贪心的题目真的越来越难了我操了，加油站和柠檬水找零都撕出来了，分发糖果和根据身高重建队列这两个都比较复杂，考虑一个维度再考虑另一个维度的思想好歹熟悉了点了。希望下次碰到相似的可以做出来吧。一个月刷了也有一百道题目了，加油！