个人技术分享

LeetCode 1005 K次组饭后最大化的数组

这题贪的主要是数值最大化。如果K > 负数个数，我们就先将负数全部转换成它的相反数，并将K--，之后K剩余的值可以对2取模，为0的话直接得出最后结果，为的话我们要在当前所有值里取最小值，对其进行取反。如果K <= 负数个数，K用完直接结束，将数组累加即可。

代码如下：

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (k == 0) break;
            if (nums[i] < 0) {
                k--;
                nums[i] *= -1;
            } else break;
        }
        if (k > 0 && k % 2 == 1) {
            Arrays.sort(nums);
            nums[0] *= -1;
        }
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return sum;
    }
}

LeetCode 134 加油站

兄弟们，这题我老一时隔一天，终于写出来了！其实也不是很难，就是一个比较复杂的模拟。但是里面用贪心缩短了循环次数，这就造成我们的麻烦了。

主要思路是用一个cnt模拟每次的起点，在循环内部用一个i变量模拟走过的加油站数，这里面涉及到i到达右边界后要回到1的问题。比较麻烦的是在刚开始起步时需要先走一步，便于二重循环的判断条件能够正常运转，不然i和cnt开始时处于同一位置无法判断是已经走一圈了还是刚开始的状态，这个后面需要优化下不然面试时也无法立刻就写出来。

同时这里面还用到一个特别的规律：如果从某个加油站起步没能到达的第一个加油站是a，那么从该起始加油站到a中间的任何一个加油站，都无法到达a，所以遇到无法到达的第一个加油站时，直接将cnt移到i + 1退出循环即可。需要注意判别cnt比i+1大的情况，这是为了防止多次遍历造成死循环的出现。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int cnt = 0;
        int gasNum = 0;
        while (cnt < gas.length) {
            gasNum += (gas[cnt] - cost[cnt]);
            if (gasNum < 0)  {
                cnt = cnt + 1;
                gasNum = 0;
                continue;
            }
            int i = cnt + 1;
            if (i == gas.length) i = 0;
            while (i != cnt) {
                if (gasNum + gas[i] - cost[i] >= 0) {
                    gasNum += (gas[i] - cost[i]);
                    i++;
                } else if (cnt < i + 1) {
                    gasNum = 0;
                    cnt = i + 1;
                    break;
                } else {
                    cnt = gas.length;
                    break;
                }
                if (i == gas.length) i = 0;
            }
            if (i == cnt) return cnt;
        }   
        return -1;
    }
}

LeetCode 135 分发糖果

这题要贪心两次，一次从前往后遍历，如果右孩子比左孩子大并且他的评分比左孩子小或者相等，那么他的评分赋为左孩子评分+1

第二次从后往前遍历，如果左孩子比右孩子大并且他的评分比右孩子小或者相等，那么他的评分等于右孩子评分+1

两次分别取反向遍历的原因是有递推关系存在，前序遍历可以处理这样的情况：假如左边增加了，右边也要跟着增长，适用于右边大于左边的情况；后序遍历可以处理这样的情况：假如右边增长了，左边也要跟着增长，适用于左边大于右边的情况

这题需要再看下，不知道解法恐怕挺难写得出来

代码如下：

class Solution {
    public int candy(int[] ratings) {
        int[] num = new int[ratings.length];
        for (int i = 0; i < num.length; i++) {
            num[i] = 1;
        }
        for (int i = 0; i < ratings.length - 1; i++) {
            if (ratings[i] < ratings[i + 1] && num[i + 1] <= num[i]) num[i + 1] = num[i] + 1;
        }
        for (int i = ratings.length - 1; i > 0; i--) {
            if (ratings[i - 1] > ratings[i] && num[i - 1] <= num[i]) num[i - 1] = num[i] + 1;
        }
        int sum = 0;
        for (int i = 0; i < num.length; i++) sum+= num[i];
        return sum;
    }
}