分发饼干

小饼干先喂饱小胃口。下面的代码中利用遍历start来遍历胃口数组，并没有再使用一个for循环，而是采用自加的方式，这也是常用的技巧。

public int findContentChildren(int[] g, int[] s) {
	Arrays.sort(g);
    Arrays.sort(s);
    int start = 0;
    int count = 0;
    for(int i = 0; i < s.length && start < g.length; i++) {
        if(s.[i] >= g[start]) {
            start++;
            count++;
        }
    }
    return count;
}

摆动序列

给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动序列的长度，所以只需要统计数组的峰值数量就可以了。

public int wiggleMaxLength(int[] nums) {
	if(nums.length <= 1) {
        return nums.length;
    }
    int result = 1;
    int pre = 0;
    int cur = 0;
    
    for(int i = 1; i < nums.length; i++) {
        cur = nums[i] - nums[i - 1];
        if(cur > 0 && pre <= 0 || cur < 0 && pre >= 0) {
            result++;
        	pre = cur;
        }
    }
    return result;
}

最大子序和

给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

局部最优：当前连续和为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素的连续和只会越来越小。全局最优：选取最大“连续和”。

public int maxSubArray(int[] nums) {
	if(nums.length == 1) {
        return nums[0];
    }
    int count = 0;
    int result = Integer.MIN_VALUE;
    
    for(int i = 0; i < nums.length; i++) {
        count += nums[i];
        result = Math.max(result,count);	//取区间累计的最大值（相当于不断确定最大子序终止为止）
        if(count < 0) {
            count = 0;		//相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
    }
    return result;
}

买卖股票的最佳时机II

给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

其实只需要收集每天的正利润就可以了，收集正利润的区间，就是股票买卖的区间，而只需要关注最终利润，不需要记录区间。

局部最优：收集每天的正利润，全局最优：求得最大利润。

public int maxProfit(int[] prices) {
	int result = 0;
    //不要整体的去看，而是把整体利润拆分为每天的利润。即只收集每天的正利润，最后稳稳的就是最大利润了。
    for(int i = 1; i < prices.length; i++) {
        result += Math.max(prices[i] - prices[i - 1],0);
    }
    return result;
}

跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

局部最优：每次取最大跳跃步数（取最大覆盖范围）全局最优：最后得到整体最大覆盖范围，看是否能到达终点。

public boolean canJump(int[] nums) {
	int count = 0;
    if(nums.length == 1) return true;
    
    for(int i = 0; i <= count; i++) {
        count = Math.max(count,i + nums[i]);
        if(count >= nums.length - 1); return true;
    }
    return false;
}

跳跃游戏II

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。

要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数。如果移动下标达到了当前这一步的最大覆盖最远距离，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

public int jump(int[] nums) {
        if(nums == null || nums.length == 0 || nums.length == 1){
            return 0;
        }
        //记录跳跃的次数
        int count = 0;
        //当前覆盖的最大区域
        int curDistance = 0;
        //最大的覆盖区域
        int maxDistance = 0;
        for(int i = 0; i < nums.length; i++) {
            //在可覆盖区域内更新最大的覆盖区域
            maxDistance = Math.max(maxDistance,i + nums[i]);
            //说明当前一步，再跳一步就到达了末尾
            if(maxDistance >= nums.length - 1) {
                count++;
                break;
            }
            //走到当前覆盖的最大区域时，更新下一步可达的最大区域
            if(i == curDistance) {
                curDistance = maxDistance;
                count++;
            }
        }
        return count;
    }

K次取反后最大化的数组和

给定一个整数数组A，只能用以下方法修改该数组：选择某个索引i并将A[i]替换为-A[i]，然后总共重复这个过程K次。（可以多次选择同一个索引i）以这种方式修改数组后，返回数组可能的最大和。

局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。如果将负数都转变为正数了，k依然大于0，此时的问题是一个有序正整数序列，如何转变k次正负，让数组和达到最大。那么又是一个贪心，局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大。全局最优：整个数组和达到最大。

public int largestSumAfterKNegations(int[] nums, int k) {
        //将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
        nums = IntStream.of(nums)
		     .boxed()
		     .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
		     .mapToInt(Integer::intValue).toArray();
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        if(k % 2 == 1) nums[nums.length - 1] = -nums[nums.length - 1];
        return Arrays.stream(nums).sum();
    }

加油站

在一条环路上有N个加油站，其中第i个加油站有汽油gas[i]升，你有一辆容量无限的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环行驶一周，则返回出发时加油站的编号，否则返回-1。

public int canCompleteCircuit(int[] gas, int[] cost) {
    //情况1：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
    //情况2：rest[i] = gas[i] - cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
    //情况3：如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能把这个负数填平
    int curSum = 0;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < gas.length;i++) {
        int rest = gas[i] - cost[i];
        curSum += rest;
        if(curSum < min) {
            min = curSum;
        }
    }
    if(curSum < 0) return -1;   //情况1
    if(min >= 0) return 0;      //情况2
    for(int i = gas.length - 1; i >= 0; i--) {      //情况3
        int rest = gas[i] - cost[i];
        min += rest;
        if(min >= 0) {
            return i;
        } 
    } 
    return -1;
}

方法二：首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明各个站点的加油站剩余油量rest[i]相加一定是大于等于零的。i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0,i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。

public int canCompleteCircuit(int[] gas, int[] cost) {
	int curSum = 0;
    int total = 0;
    int start = 0;
    for(int i = 0; i < gas.length; i++) {
        curSum += gas[i] - cost[i];
        total += gas[i] - cost[i];
        if(curSum < 0) {
            curSum = 0;
            start = i + 1;
        }
    }
    if(total > 0) {
        return start;
    }else {
        return -1;
    }
}

分发糖果

每个孩子至少分配到1个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果。

局部最优：只要右边评分比左边大，右边的孩子就多一个糖果。全局最优：相邻的孩子中，评分高的右孩子获得比左孩子更多的糖果。如果ratings[i] > retings[i - 1]那么i的糖一定要比i-1的糖多一个，所以贪心candyVec[i] = candyVec[i - 1] + 1

确定左孩子大于右孩子的情况一定要从后向前遍历。因为如果从前向后遍历，根据ratings[i+1]来确定ratings[i]对应的糖果，那么每次都不能利用上前一次的比较结果。

局部最优：取candyVec[i + 1] + 1和candyVec[i]最大的糖果数量，保证第i个小孩的糖果数量大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

public int candy(int[] ratings) {
        //分两个阶段
        //1.起点下标1从左往右，只要右边比左边大，右边的糖果 = 左边 + 1
        //2.起点下标rating.length - 2 从右往左，只要左边比右边大，此时左边的糖果应该取本身的糖果数（符合比它左边大）和右边糖果数+1二者的最大值，这样才符合它比它左边的大，也比它右边的大

        int[] candyVec = new int[ratings.length];
        candyVec[0] = 1;
        int result = 0;
        //从前向后  右比左大的情况
        for(int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i - 1]) {
                candyVec[i] = candyVec[i - 1] + 1;
            }else {
                candyVec[i] = 1;
            }
        }
        //从后向前  左比右大的情况   因为要利用上一次循环得出的右比左大的结果，所以要从后向前遍历
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) {
                //若孩子得分为1 2 2 5 4 即可看出为什么要取以下代码的最大值
                candyVec[i] = Math.max(candyVec[i],candyVec[i + 1] + 1);
            }
        }
        for(int i = 0; i < candyVec.length; i++) {
            result += candyVec[i];
        }
        return result;
    }

根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组people表示队列中一些人的属性（不一定按顺序）。每个people[i] = [hi,ki]表示第i个人的身高为hi，前面正好有ki个身高大于或等于hi的人。请你重新构造并返回输入数组people所表示的队列。

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

局部最优：优先按身高高的people的k来插入。插入操作过后的peoplr满足队列属性。全局最优：最后都做完插入操作，整个队列满足题目队列属性。

public int[][] reconstructQueue(int[][] people) {
    //身高从大到小排（身高相同k小的站前面）
	Arrays.sort(people,(a,b) -> {
        if(a[0] == b[0]) return a[1] - b[1];
        return b[0] - a[0];
    });
    LinkedList<int[]> que = new LinkedList<>();
    for(int[] p :people) {
        que.add(p[1],p);
    }
    return que.toArray(new int[people.length][]);
}

用最少数量的箭引爆气球

按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。

public int findMinArrowShots(int[][] points) {
	if(points.length == 0) return 0;
    Arrays.sort(points,(o1,o2) -> Integer.compare(o1[0],o2[0]));
    int count = 1;
    for(int i = 1; i < points.length; i++) {
        if(points[i][0] > points[i - 1][1]) {
            count++;
        }else {
            points[i][1] = Math.min(points[i - 1][1],points[i][1]);
        }
    }
    return count;
}

无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。（此题与上一题类似）

输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

public int eraseOverlapIntervals(int[][] intervals) {
	//按照区间右边界升序排序
    Arrays.sort(intervals,(a,b) -> {
        return a[1] - b[1];
    });
    int count = 0;
    int edge = Integer.MIN_VALUE;
    for(int i = 0; i < intervals.length; i++) {
        //若上一个区间的右边界小于当前区间的左边界，说明无交集
        if(intervals[i][0] >= edge) {
            edge = intervals[i][1];
        }else {
            count++;
        }
    }
    return count;
}

划分字母区间

字符串S由小写字母组成，我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

​

public List<Integer> partitionLabels(String s) {
	List<Integer> result = new LinkedList<>();
    int[] hash = new int[26];
    for(int i = 0; i < s.length(); i++) {
        hash[s.charAt(i) - 'a'] = i;
    }
    int idx = 0;
    int last = -1;
    for(int i = 0; i < s.length(); i++) {
        idx = Math.max(idx,hash[s.charAt(i) - 'a']);
        if(i == idx) {
            result.add(idx - last);
            last = i;
        }
    }
    return result;
}

合并区间

给出一个区间的集合，请合并所有重叠的区间。

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了。整体最优：合并所有重叠的区间。

**按照左边界从小到大排序之后，如果intervals[i] [0] < intervals[i - 1] [1]即intervals[i]左边界 < intervals[i - 1]右边界，则一定有重复，因为intervals[i]的左边界一定是大于等于intervals[i - 1]的左边界。 **

如果有重复则合并区间左边界和最大右边界，作为一个新的区间加入到result数组里，如果没有合并就把原区间加入到result数组。

public int[][] merge(int[][] intervals) {
        //按照左边界从小到大排序后，如果intervals[i][0] < intervals[i - 1][1] 即intervals[i]左边界 < intervals[i - 1]右边界，则一定有重复，因为intervals[i]的左边界一定是大于等于intervals[i - 1]的左边界。
	List<int[]> res = new LinkedList<>();
    Arrays.sort(intervals,(o1,o2) -> Integer.compare(o1[0],o2[0]));
    
    int start = intervals[0][0];
    for(int i = 1; i < intervals.length; i++) {
        if(intervals[i][0] > intervals[i - 1][1]) {
            res.add(new int[]{start,intervals[i - 1][1]});
            start = intervals[i][0];
        }else {
            intervals[i][1] = Math.max(intervals[i - 1][1],intervals[i][1]);
        }
    }
    
    res.add(new int[]{start,intervals[intervals.length - 1][1]});
    return res.toArray(new int[res.size()][]);
}

单调递增的数字

给定一个非负整数N，找出小于或等于N的最大的整数，同时这个整数需要满足其各个尾数上的数字是单调递增。当且仅当每个相邻位数上的数字x和y满足x<=y时，我们称这个整数是单调递增的。

局部最优：遇到strNum[i-1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]变为9，可以保证这两位变成最大单调递增整数。全局最优：得到小于等于N的最大单调递增的整数。注意：应该从后向前遍历。

输入: N = 1234
输出: 1234

输入: N = 332
输出: 299

public int monotoneIncreasingDigits(int n) {
	String s = String.valueOf(n);
    char[] chars = s.toCharArray();
    int start = s.length;
    for(int i = s.length - 2; i >= 0; i++) {
        if(chars[i] > chars[i + 1]) {
            chars[i]--;
            start = i + 1;
        }
    }
    for(int i = start; i < s.length; i++) {
        chars[i] = '9';
    }
    return Integer.parseInt(String.valueOf(chars));
}

买卖股票的最佳时机含手续费

给定一个整数数组prices，其中第i个元素代表了第i天的股票价格；非负整数fee代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

示例 1: 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2 输出: 8

解释: 能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

public int maxProfit(int[] prices, int fee) {
	int result = 0;
    int minValue = prices[0];
    
    for(int i = 0; i < prices.length; i++) {
        if(prices[i] < minValue) {
            minValue = prices[i];
        }
        
        if(prices[i] > minValue + fee) {
            result += prices[i] - minValue - fee;
            minValue = prices[i] - fee;		//假设prices = [1, 3, 2, 8, 9] 为了求出最大利润  需要执行此步代码  如果卖出股票的明天股票数还是递增的，此段代码就相当于在卖出股票的这一天不进行任何操作，而在下一天卖出股票得到收益
        }
    }
    return result;
}

监控二叉树

给定一个二叉树，在树的节点上安装摄像头。节点上的每个摄像头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

局部最优：让叶子节点的父节点安摄像头，所用摄像头最少。全局最优：全部摄像头数量所用最少！

int result = 0;
public int minCameraCover(TreeNode root) {
    //情况4:递归结束之后，可能头结点还有一个无覆盖的情况，所以递归结束之后，还要判断根节点，如果没有覆盖result++
    if(traversal(root) == 0) {      //无覆盖
        result++;
    }
    return result;
}

public int traversal(TreeNode root) {
    if(root == null) return 2;
    int left = traversal(root.left);
    int right = traversal(root.right);

    //情况1：左右节点都有覆盖，那么此时中间节点应该就是无覆盖的状态了
    if(left == 2 && right == 2) {
        return 0;
    }

    //情况2：左右节点至少有一个无覆盖的情况，只要有一个孩子没有覆盖，父节点就应该放摄像头
    if(left == 0 || right == 0) {
        result++;
        return 1;
    }

    //情况3：左右节点至少有一个有摄像头。其实就是左右孩子有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）
    if(left == 1 || right == 1) {
        return 2;
    }

    return -1;
}

额外的题目

最长回文串

给定一个包含大写字母和小写字母的字符串s，返回通过这些字母构造成的最长回文串。在构造过程中，请注意大小写。比如Aa不能当作一个回文字符串。

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

在一个回文串中，只有最多一个字符出现了奇数次，其余的字符都出现偶数次。如果有任何一个字符ch的出现次数v为奇数，那么可以将这个字符作为回文中心，注意只能最多有一个字符作为回文中心。在代码中，用ans存储回文串的长度，由于在遍历字符时，ans每次会增加v / 2 * 2，因此ans一直为偶数。但在发现了第一个出现次数为奇数的字符后，将ans++，这样ans变为奇数，在后面发现其它出现奇数次的字符时，就不改变ans的值了。

public int longestPalindrome(String s) {
    int[] count = new int[128];
    for(int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        count[c]++;
    }
    int ans = 0;
    for(int v : count) {
        ans += v / 2 * 2;
        if(v % 2 == 1 && ans % 2 == 0) {
            ans++;
        }
    }
    return ans;
}

最多删除一个字符得到回文

给定一个非空字符串s，请判断如果最多从字符串中删除一个字符能否得到一个回文字符串。

输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符

在允许最多删除一个字符的情况下，同样可以使用双指针，通过贪心实现。初始化两个指针low和high分别指向字符串的第一个字符和最后一个字符。每次判断两个指针指向的字符是否相同，如果相同，则更新指针，将low加1，high减1，然后判断更新后的指针范围内的子串是否是回文字符串。如果两个指针指向的字符不同，则两个字符中必须有一个被删除，此时可分成两种情况：即删除左指针对应的字符，判断剩下的子串是否为回文串，或者删除右指针对应的字符，执行相同的操作。当这两个子串中至少有一个是回文串时，就说明原始字符串删除一个字符之后可以成为回文串。

public boolean validPalindrome(String s) {
    int low = 0,high = s.length() - 1;
    while(low < high) {
        char char1 = s.charAt(low),char2 = s.charAt(high);
        if(char1 == char2) {
            low++;
            high--;
        }else {
            return validPalindrome(s,low,high - 1) || validPalindrome(s,low + 1,high);
        }
    }
    return true;
}
public boolean validPalindrome(String s,int low,int high) {
    for(int i = low,j = high; i < j; i++,j--) {
        char char1 = s.charAt(i),char2 = s.charAt(j);
        if(char1 != char2) {
            return false;
        }
    }
    return true;
}

盛最多的水

给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i,0)和(i,height[i])。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以容纳最多的水。

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

设两指针i，j指向的水槽高度分别为h[i],h[j]，此状态下水槽面积为S(i,j)。由于可容纳水的高度由两板中的短板决定，因此可得知如下面积公式：S(i,j) = min(h[i],h[j]) × (j - i)

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度-1变短：

• 若向内移动短板，水槽的短板min(h[i],h[j])可能变大，因此下个水槽的面积可能增大。
• 若向内移动长板，水槽的短板min(h[i],h[j])不变或变小，因此下个水槽的面积一定变小。

因此初始化双指针分裂水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出，即可获得最大面积。

public int maxArea(int[] height) {
    //贪心算法
    int i = 0, j = height.length - 1, result = 0;
    while(i < j) {
        result = height[i] < height[j] ? Math.max(result,(j - i) * height[i++]) : Math.max(result,(j - i) * height[j--]);
    }
    return result;
}

递增的三元子序列

给你一个整数数组nums，判断这个数组是否存在长度为3的递增子序列。如果存在这样的三元组下标(i,j,k)且满足i<j<k，使得nums[i]<nums[j]<nums[k]，返回true；否则返回false。

输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

赋初始值的时候，已经满足second > first了，现在找第三个数third

1. 如果third比second大，那就是找到了，直接返回true
2. 如果third比second小，但是比first大，那就把second的值设为third，然后继续遍历找third
3. 如果third比first还小，那就把first的值设为third，然后继续遍历找third（这样的话first会跑到second的后边，但是因为在second的前面老的first还是满足递增的，所以也符合）例如数组[ 2, 1, 5, 0, 6]

public boolean increasingTriplet(int[] nums) {
    if(nums.length < 3) return false;
    int first = nums[0];
    int second = Integer.MAX_VALUE;
    for(int i = 1; i < nums.length; i++) {
        if(nums[i] > second) {
            return true;
        }else if(nums[i] > first) {
            second = nums[i];
        }else {
            first = nums[i];
        }
    }
    return false;
}

有效三角形的个数

给定一个包含非负整数的数组nums，返回其中可以组成三角形三条边的三元组个数。

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

我们将a = nums[i]，b = nums[j]时，最大的满足nums[k] < nums[i] + nums[j]的下标k记为Kij。可以发现，如果固定i，那么随着j的递增，不等式右侧nums[i] + nums[j]也是递增的，因此kij也是递增的。

这样一来，就可以将j和k看成两个同向递增移动的指针，将进行如下的优化：

• 使用一重循环枚举i。当i固定时，使用双指针同时维护j和k，它们的初始值分别为i+1和i；
• 每一次将j向右移动一个位置，即j = j+1，并尝试不断向右移动k，使得k是最大的满足nums[k] < nums[i] + nums[j]的下标。将max(k-j,0)累加入答案。

在双指针中，也会出现不存在满足nums[k] < nums[i] + nums[j]的下标的情况。此时，指针k不会出现在指针j的右侧，即k-j<=0，因此需要将k-j与0中的较大值累加入答案，防止错误的负数出现。

public int triangleNumber(int[] nums) {
    Arrays.sort(nums);
    int result = 0;
    for(int i = 0; i < nums.length; i++) {
        int k = i;
        for(int j = i + 1; j < nums.length; j++) {
            while(k + 1 < nums.length && nums[k + 1] < nums[i] + nums[j]) {
                ++k;
            }
            result += Math.max(k - j,0);
        }
    }
    return result;
}

通过删除字母匹配到字典里最长单词

给你一个字符串s和一个字符串数组dictionary，找出并返回dictionary中最长的字符串，该字符串可以通过删除s中的某些字符得到。如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

先将dictionary依据字符串长度的降序和字典序的升序进行排序，然后从前向后找到第一个符合条件的字符串直接返回即可。寻找符合条件的字符串，可以使用双指针法，初始化两个指针i和j，分别指向t和s的初始位置。每次贪心地匹配，匹配成功则i和j同时右移，匹配t的下一个位置，匹配失败则j右移，i不变，尝试用s的下一个字符匹配t。

public String findLongestWord(String s, List<String> dictionary) {
    Collections.sort(dictionary,new Comparator<String>() {
        public int compare(String word1,String word2) {
            if(word1.length() != word2.length()) {
                return word2.length() - word1.length();
            }else {
                return word1.compareTo(word2);
            }
        }
    });
    for(String t : dictionary) {
        int i = 0,j = 0;
        while(i < t.length() && j < s.length()) {
            if(t.charAt(i) == s.charAt(j)) i++;
            j++;
        }
        if(i == t.length()) return t;
    }
    return "";
}

救生艇

给定数组people。people[i]表示第i个人的体重，船的数量不限，每艘船可以承载的最大重量为limit。每艘船最多可同时载两人，但条件是这些人的重量之和最多为limit。返回承载所有人所需的最小船数。

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

要使需要的船数尽可能地少，应当使载两人的船尽可能地多。

设people的长度为n。考虑体重最轻的人：

• 若他不能与体重最重的人同乘一艘船，那么体重最重的人无法与任何一人同乘一艘船，此时应单独分配一艘船给体重最重的人。从people中去掉体重最重的人后，缩小了问题的规模，变成求解剩余n-1个人所需的最小船数，将其加一即为原问题的答案。
• 若他能与体重最重的人同乘一艘船，那么他能与其余任何人同乘一艘船，为了尽可能地利用船的承载重量，选择与体重最重的人同乘一艘船是最优的。从people中去掉体重最轻和体重最重的人后，便缩小了问题的规模，变成求解剩余n-2个人所需的最小船数，将其加一即为原问题的答案。

可以先对people排序，然后用两个指针分别指向体重最轻和体重最重的人，按照上述规则来移动指针，并统计答案。

public int numRescueBoats(int[] people, int limit) {
    int result = 0;
    Arrays.sort(people);
    int left = 0;
    int right = people.length - 1;
    while(left <= right) {
        if(people[left] + people[right] <= limit) left++;
        right--;
        ++result;
    }
    return result;
}

最短无序连续子数组

给你一个整数数组nums，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排列。请你找出符合题意的最短子数组，并输出它的长度。（感觉和贪心没太大关系）

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

我们将给定的数组nums表示为三段子数组拼接的形式，分别记作numsA，numsB，numsC。当我们对numsB进行排序，整个数组将变为有序。换而言之，当对整个序列进行排序，numsA和numsC都不会改变。

本题要求找最短的numsB，即找到最大的numsA和numsC的长度之和。因此可以将原数组nums排序与原数组进行比较，取最长的相同的前缀为numsA，取最长的相同的后缀为numsC，这样就可以取到最短的numsB。特别地，当原数组有序时，numsB的长度为0，可以直接返回结果。

public int findUnsortedSubarray(int[] nums) {
    if(isSorted(nums)) return 0;
    int[] numsSorted = new int[nums.length];
    System.arraycopy(nums,0,numsSorted,0,nums.length);
    Arrays.sort(numsSorted);
    int left = 0;
    while(nums[left] == numsSorted[left]) {
        left++;
    }
    int right = nums.length - 1;
    while(nums[right] == numsSorted[right]) {
        right--;
    }
    return right - left + 1;
}
public boolean isSorted(int[] nums) {
    for(int i = 1; i < nums.length; i++) {
        if(nums[i - 1] > nums[i]) return false;
    }
    return true;
}

任务调度器

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

public int leastInterval(char[] tasks, int n) {
    //统计每个任务出现的次数，找到出现次数最多的任务
    int[] hash = new int[26];
    for(int i = 0; i < tasks.length; ++i) {
        hash[tasks[i] - 'A'] += 1;
    }
    Arrays.sort(hash);
    //因为相同元素必须有n个冷却时间，假设A出现3次，n = 2，任务要执行完，至少形成AXX AXX A序列（X看作预占位置）
    //该序列长度为
    int minLen = (n+1) *  (hash[25] - 1) + 1;

    //此时为了尽量利用X所预占的空间（贪心）使得整个执行序列长度尽量小，将剩余任务往X预占的空间插入
    //剩余的任务次数有两种情况：
    //1.与A出现次数相同，比如B任务最优插入结果是ABX ABX AB，中间还剩两个空位，当前序列长度+1
    //2.比A出现次数少，若还有X，则按序插入X位置，比如C出现两次，形成ABC ABC AB的序列
    //直到X预占位置还没插满，剩余元素逐个放入X位置就满足冷却时间至少为n
    for(int i = 24; i >= 0; --i){
        if(hash[i] == hash[25]) ++ minLen;
    }
    //当所有X预占的位置插满了怎么办？
    //在任意插满区间（这里是ABC）后面按序插入剩余元素，比如ABCD ABCD发现D之间距离至少为n+1，肯定满足冷却条件
    //因此，当X预占位置能插满时，最短序列长度就是task.length，不能插满则取最少预占序列长度
    return Math.max(minLen, tasks.length);
}

整数替换

给定一个正整数，你可以做如下操作：

1. 如果n是偶数，则用n/2替换n。
2. 如果n是奇数，则可以用n+1或n-1替换n。

返回n变为1所需的最小替换次数。

输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1

输入：n = 7
输出：4
解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1

可以使用递归的方法枚举所有将n变为1的替换序列：

• 当n为偶数时，只有唯一的方法将n替换为n/2。
• 当n为奇数时，可以选择将n增加1或减少1。由于这两种方法都会将n变为偶数，那么下一步一定是除以2，因此这里可以看成使用两次操作，将n变为(n + 1) / 2或(n - 1) / 2。

细节：当n=2^31 - 1时，计算n+1会导致溢出，因此可以使用整数除法n / 2 + 1和n / 2分别计算(n + 1) / 2或(n - 1) / 2。

Map<Integer,Integer> map = new HashMap<Integer,Integer>();
public int integerReplacement(int n) {
    /*if(n == 1) return 0;
        if(n % 2 == 0) return 1 + integerReplacement(n / 2);
        return 2 + Math.min(integerReplacement(n / 2),integerReplacement(n / 2 + 1));*/
    //增加记忆化搜索
    if(n == 1) return 0;
    if(!map.containsKey(n)) {
        if(n % 2 == 0) {
            map.put(n,1 + integerReplacement(n / 2));
        }else {
            map.put(n,2 + Math.min(integerReplacement(n / 2),integerReplacement(n / 2 + 1)));
        }
    }
    return map.get(n);
}

森林中的兔子

林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你（指被提问的兔子）颜色相同?" ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。给你数组answers，返回森林中兔子的最少数量。

输入：answers = [1,1,2]
输出：5
解释：
两只回答了 "1" 的兔子可能有相同的颜色，设为红色。 
之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。 
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 
因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。

输入：answers = [10,10,10]
输出：11

两只相同颜色的兔子看到的其他同色兔子数必然是相同的。反之，若两只兔子看到的其它兔子数不同，那么这两只兔子颜色不同。因此，将answers中值相同的元素分为一组，对于每一组，计算出兔子的最少数量，然后将所有组的计算结果累加，就是最终的答案。

例如，现在有 13 只兔子回答 5。假设其中有一只红色的兔子，那么森林中必然有 6 只红兔子。再假设其中还有一只蓝色的兔子，同样的道理森林中必然有 6 只蓝兔子。为了最小化可能的兔子数量，我们假设这 12 只兔子都在这 13 只兔子中。那么还有一只额外的兔子回答 5，这只兔子只能是其他的颜色，这一颜色的兔子也有 6 只。因此这种情况下最少会有 18 只兔子。

一般地，如果有x只兔子都回答y，则至少有⌈x / y + 1⌉种不同的颜色，且每种颜色的兔子有y+1只兔子，因此兔子数至少为⌈x / y + 1⌉ * (y + 1)。可以用哈希表统计answers中各个元素的出现次数，对每个元素套用上述公式计算，并将计算结果累加，即为最终答案。

public int numRabbits(int[] answers) {
    Map<Integer,Integer> count = new HashMap<Integer,Integer>();
    for(int y : answers) {
        count.put(y,count.getOrDefault(y,0) + 1);
    }
    int result = 0;
    for(Map.Entry<Integer,Integer> entry : count.entrySet()) {
        int y = entry.getKey(),x = entry.getValue();
        //(x + y) / (y + 1)  等价于 ⌈x / y + 1⌉向上取整
        result += (x + y) / (y + 1) * (y + 1);
    }
    return result;
}

最长快乐字符串

如果字符串中不含有任何'aaa'，'bbb'或'ccc'这样的字符串作为子串，那么该字符就是一个快乐字符串。给你三个整数a,b,c，请你返回任意一个满足下列全部条件的字符串s：

• s是一个尽可能长的快乐字符串。
• s中最多有a个字母'a'、b个字母'b'、c个字母'c'。
• s中只含有'a'、'b'、'c'三种字母。

如果不存在这样的字符串s，请返回一个空字符串""。

输入：a = 1, b = 1, c = 7
输出："ccaccbcc"
解释："ccbccacc" 也是一种正确答案。

输入：a = 2, b = 2, c = 1
输出："aabbc"

题目要求找到最长的快乐字符串，且快乐字符串中不含有三个连续相同的字母。

• 尽可能优先使用当前数量最多的字母，因为最后同一种字母剩余的越多，越容易出现字母连续相同的情况。如果构建完成最长的快乐字符串后还存在剩余未选择的字母，则剩余的字母一定为同一种字母且该字母的总数量最多。
• 依次从当前数量最多的字母开始尝试，如果发现加入当前字母会导致出现三个连续相同字母，则跳过当前字母，直到我们找到可以添加的字母为止。实际上每次只会在数量最多和次多的字母选择一个。
• 如果尝试所有的字母都无法添加，则直接退出，此时构成的字符串即为最长的快乐字符串。

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        StringBuilder result = new StringBuilder();
        Pair[] arr = { new Pair(a,'a'),new Pair(b,'b'),new Pair(c,'c')};

        while(true) {
            Arrays.sort(arr,(p1,p2) -> p2.freq - p1.freq);
            boolean hasNext = false;
            for(Pair pair : arr) {
                if(pair.freq <= 0) break;
                int m = result.length();
                if(m >= 2 && result.charAt(m - 2) == pair.ch && result.charAt(m - 1) == pair.ch) {
                    continue;
                }
                hasNext = true;
                result.append(pair.ch);
                pair.freq--;
                break;
            }
            if(!hasNext) {
                break;
            }
        }
        return result.toString();
    }
}
class Pair {
    int freq;
    char ch;
    public Pair(int freq,char ch) {
        this.freq = freq;
        this.ch = ch;
    }
}

和为k的最少斐波那契数字数目

给你数字k，请你返回和为k的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。

输入：k = 7
输出：2 
解释：斐波那契数字为：1，1，2，3，5，8，13，……
对于 k = 7 ，我们可以得到 2 + 5 = 7 。

输入：k = 10
输出：2 
解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。

首先找到所有不超过k的斐波那契数字，然后每次贪心地选取不超过k的最大斐波那契数字，将k减去该斐波那契数字，重复该操作直到k变为0，此时选取的斐波那契数字满足和为k且数目最少。

public int findMinFibonacciNumbers(int k) {
    List<Integer> f = new ArrayList<Integer>();
    f.add(1);
    int a = 1, b = 1;
    while(a + b <= k) {
        int c = a + b;
        f.add(c);
        a = b;
        b = c;
    }
    int result = 0;
    for(int i = f.size() - 1; i >= 0 && k > 0; i--) {
        int num = f.get(i);
        if(k >= num) {
            k -= num;
            result++;
        }
    }
    return result;
}

使数组变成交替数组的最少操作数

给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。

如果满足下述条件，则数组 nums 是一个 交替数组 ：

nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。 nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。 在一步 操作 中，你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。

返回使数组变成交替数组的 最少操作数 。

输入：nums = [3,1,3,2,4,3]
输出：3
解释：
使数组变成交替数组的方法之一是将该数组转换为 [3,1,3,1,3,1] 。
在这种情况下，操作数为 3 。
可以证明，操作数少于 3 的情况下，无法使数组变成交替数组。

输入：nums = [1,2,2,2,2]
输出：2
解释：
使数组变成交替数组的方法之一是将该数组转换为 [1,2,1,2,1].
在这种情况下，操作数为 2 。
注意，数组不能转换成 [2,2,2,2,2] 。因为在这种情况下，nums[0] == nums[1]，不满***替数组的条件。

根据交替数组的定义，可以将数组根据下标奇偶性分成两个序列，最终目的是：使用最少的修改次数，使得两个序列均成为公差为0等差数列，同时两序列的首项不相等。要用最少次数将一个序列修改为公差为0等差数列，等价于修改最少的数字，等价于保留最多的数字，容易想到将序列中的其他非众数修改为众数（若有多个众数，取任一）

因此可以对nums进行扫描，分别统计偶数下标序列和奇数下标序列的最大值（众数）和次大值（注意是非严格的次大值，即为其它众数或者出现次数比众数小的数），使用a和b代替偶数下标序列的最大值和次大值，使用c和d代指奇数下标序列的最大值和次大值，同时使用m1和m2分别统计偶数下标序列和奇数下标序列中某个数的出现次数。

根据两序列的最大值是否冲突进行分情况讨论：

• 若两序列的最大值不冲突：那么两序列都可以取得最小修改次数，整体的最小修改次数为n - m1[a] - m2[c];
• 若两序列的最大值冲突：那么仅一序列可以取得最小修改次数，另一序列只能取得次小的修改次数，此时整体的最小修改次数为n - max(m1[a] + m2[d],m1[b] + m2[c])。

static int N = 100010;
static int[] m1 = new int[N],m2 = new int[N];
public int minimumOperations(int[] nums) {
    int n = nums.length;
    Arrays.fill(m1,0);
    Arrays.fill(m2,0);
    int a = 0,b = 0,c = 0,d = 0;
    for(int i = 0; i < n; i++) {
        int t = nums[i];
        if(i % 2 == 0) {
            m1[t]++;
            if(a == 0 || m1[t] > m1[a]) {
                b = a; a = t;
            }else if(t != a && (b == 0 || m1[t] > m1[b])) {
                b = t;
            }
        }else {
            m2[t]++;
            if(c == 0 || m2[t] > m2[c]) {
                d = c; c = t;
            }else if(t != c && (d == 0 || m2[t] > m2[d])) {
                d = t;
            }
        }
    }
    if(a != c) return n - m1[a] - m2[c];
    else return n - Math.max(m1[a] + m2[d],m1[b] + m2[c]);
}