Max Consecutive Ones II

最简单的方式是存一个prevCount的变量，O(1) space, 每次碰到0的时候，遇到1的数量是prevCount＋Count＋1，如果0后面跟的是1的话，prevCount＝count， 否则prevCount＝0.

注意两个corner case，[1,1,1,1] ，一个0都没有出现，ans是count的值。

最后一个是1，循环完以后要补一个判断。不要忽视很多循环都最后要判断一下，

public class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int prevCount = 0; int count = 0; int ans = 0; boolean zero = false;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==1) count++;
            else{
                ans = Math.max(ans, prevCount+count+1);
                if(i+1>=nums.length||nums[i+1]==1) prevCount = count;
                else prevCount = 0;
                count=0;
                zero = true;
            }
        }
        if(zero) ans = Math.max(ans, prevCount+count+1);
        else ans = Math.max(ans, count);
        return ans;
    }
}

简洁解法是two pointers(sliding window)的解法。这个同时可以扩展到k个0的情况。然而这个需要保存部分input，没法拓展到stream的情况

public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0, zero = 0, k = 1; // flip at most k zero
        for (int l = 0, h = 0; h < nums.length; h++) {
            if (nums[h] == 0)                                           
                zero++;
            while (zero > k)
                if (nums[l++] == 0)
                    zero--;                                     
            max = Math.max(max, h - l + 1);
        }                                                               
        return max;             
    }

stream 的情况下，不需要保存input，只需要记录0的index出现的位置。

public int findMaxConsecutiveOnes(int[] nums) {                 
        int max = 0, k = 1; // flip at most k zero
        Queue<Integer> zeroIndex = new LinkedList<>(); 
        for (int l = 0, h = 0; h < nums.length; h++) {
            if (nums[h] == 0)
                zeroIndex.offer(h);
            if (zeroIndex.size() > k)                                   
                l = zeroIndex.poll() + 1;
            max = Math.max(max, h - l + 1);
        }
        return max;                     
    }

Relative Ranks

FB面试follow up问了相似的问题，当时用hashmap maintain了mapping，面试官提示hashmap scalability不好，有什么方式？建立一个tuple，拉进去排序。

无聊 贴答案

public class Solution {
    public String[] findRelativeRanks(int[] nums) {
        int[][] pair = new int[nums.length][2];

        for (int i = 0; i < nums.length; i++) {
            pair[i][0] = nums[i];
            pair[i][1] = i;
        }

        Arrays.sort(pair, (a, b) -> (b[0] - a[0]));

        String[] result = new String[nums.length];

        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                result[pair[i][1]] = "Gold Medal";
            }
            else if (i == 1) {
                result[pair[i][1]] = "Silver Medal";
            }
            else if (i == 2) {
                result[pair[i][1]] = "Bronze Medal";
            }
            else {
                result[pair[i][1]] = (i + 1) + "";
            }
        }

        return result;
    }
}

Shortest Unsorted Continuous Subarray

这道题的核心在于two pointers，开始只考虑了nums[i]>nums[i+1], 即使后面的元素递增，如果小于已扫过的Max，right point也需要移动。忽略了[1,2,4,5,3]这个case，只排序5，3，后面扫到的元素也有可能小于前面扫过的元素，需要排序[4,5,3]。

参考论坛上的解法，最简单有效的方式是从两边用two pointer说的方式扫。排序的核心就是“后面的元素总要比前面的元素大”，换一种说法就是“后面出现的最小值要比前面的元素大，前面出现的最大值要比后面的元素小”，想到了这里，问题解决。

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if(nums==null || nums.length==0) return 0;
        int max = nums[0]; int min = nums[nums.length-1]; int start = 0; int end = -1;
        for(int i=1;i<nums.length;i++){
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[nums.length-i-1]);
            if(max>nums[i])
                end = i;
            if(min<nums[nums.length-i-1])
                start = nums.length-i-1;
        }
        return end-start+1;
    }
}

Array Partition I

这道题有毒，很容易看错题。要求组成pair后，将pair里的较小值相加。为了加最小值，每次都会牺牲一个较大值，所以最好的策略就是排序后将第0，2，...个元素相加。

public class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int result = 0;
        for (int i = 0; i < nums.length; i += 2) {
            result += nums[i];
        }
        return result;
    }
}

Teemo Attacking

核心在分析当前时刻和“下一全新时刻“的关系，如果当前时刻在“下一全新时刻”之前，那么所能加的duration就是t+duration-1-prev；如果是之后，那么就是一个完整的duration。再更新“下一全新时刻”

public class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if(timeSeries==null || timeSeries.length==0) return 0;
        int ans = 0; int prev = timeSeries[0]-1;
        for(int t : timeSeries){
            if(t<=prev){
                ans += t+duration-1-prev;
            }
            else
                ans+=duration;
            prev = t+duration-1;

        }
        return ans;
    }
}

Super Washing Machines

很好玩的一道题，开始猜是个DP，然而根据已知信息很难construct一个dp方程出来，事实证明这不是一个dp，而是一个数学推导。DP是数学推导中的一种，而这题是一个数学推导。

关键的第一步，求出每个machines gain/loss array，然后在这个基础上由左向右推导，最左边的机器，如果是gain，那么需要向右边索取，索取完后平衡；左数第二个机器，最左已经平衡，只能再向右索取。最后取move的最大值。

将这个问题想象成一个pipeline（多个machine可以同时输送）pipeline宽为1，从最左边machine确定pipeline的方向，pipeline只能向右边看，左边的都是平衡状态，右边的可以流入， 可以流出。计算最多需要用几次pipeline

注意区分moves和machines数组

这道题不用考虑pipeline的正负，machine可以同时向左或者向右移动。

public class Solution {
    public int findMinMoves(int[] machines) {
        int total = 0; for (int x : machines) total+=x;
        if(total==0) return 0;
        if(total%machines.length!=0) return -1;
        int avg = total/machines.length;
        int ans = 0;

        int[] moves = new int[machines.length];
        for(int i=0;i<machines.length-1;i++){
            if(machines[i]-avg>0){
                moves[i] += machines[i]-avg;
                machines[i+1] += machines[i]-avg;
                machines[i] = avg;
                ans = Math.max(ans, moves[i]);
            }
            else{
                moves[i+1] = avg-machines[i];
                machines[i+1] += machines[i]-avg;
                machines[i] = avg;
                ans = Math.max(ans, moves[i+1]);
            }
        }
        return ans;
    }
}

问一个数组能否只改变一个数字，从而让他变成单调增的数组。比如[3,3,2,2] 不可以，[1,2,5,3,3] 可以把5变成2或者3(G)

用max1和max2两个变量更新已经看过的最大数，如果当前的数字同时小于max1和max2，意味着至少要换两个数才能单调递增。