贪心算法

贪心专题。

通过局部最优解得到全局最优解

leetcode 334 递增的三元子序列注意递增的子序列可以是不连续的。first， second，third，只要维护这三个数。先确定first和second。

55. 跳跃游戏明明用了贪心为什么待在动态规划列表里。时隔四个月重新做，思路都忘了。此处的贪心是记录最远的位置。

45. 跳跃游戏 II 贪心，还是这个思路写的清楚，每次在上次跳到的最大范围内选择跳的最远的。有点像最短/长路径问题。

基本思路就是设置最大位置，在遍历的过程中更新最大的位置。

int n = nums.length;
int maxP = 0, step = 0, end = 0;

for(int i = 0; i < n - 1; i++){
    maxP = Math.max(maxP, nums[i] + i);
    if(i == end){
        end = maxP;
        step++;
    }
}

leetcode 122 买卖股票的最佳时机II 买股票系列

leetcode 334 递增的三元子序列，最长连续子序列。

455. 分发饼干思路是先排序，然后挨个匹配。和官解思路是一致的。

376. 摆动序列

int prediff = nums[1] - nums[0];
int len = prediff != 0 ? 2:1;
for(int i = 2; i < n; i++){
    int diff = nums[i] - nums[i - 1];
    if((diff > 0 && prediff <= 0) || (diff < 0 && prediff >= 0)){
        len++;
        prediff = diff;
    }
}

53. 最大子数组和思路是动态规划。关键在于状态转移方程。

1005. K 次取反后最大化的数组和思路是排序，把负数取反。这里有个巧妙地点是在负数取反以后再进行一次排序。

Arrays.sort(nums);
int sum = 0;
for(int i = 0; i < nums.length; i++){
    if(nums[i] < 0 &&  k > 0){
        nums[i] = -nums[i];
        k--;
    }
    sum+=nums[i];
}
Arrays.sort(nums);
if(k % 2 != 0){
    sum -= 2 * nums[0];
}

134. 加油站一次遍历。有点像加了cost的跳跃游戏。看了题解有点不理解为什么贴贪心标签。

补充一个推理：

如果x到不了y+1（但能到y），那么从x到y的任一点出发都不可能到达y+1。因为从其中任一点出发的话，相当于从0开始加油，而如果从x出发到该点则不一定是从0开始加油，可能还有剩余的油。既然不从0开始都到不了y+1，那么从0开始就更不可能到达y+1了…

来源：官解评论区

int n = gas.length;
int i = 0;
while(i < n){
    int gasSum = 0, costSum = 0, count = 0;//走过的站点个数
    //找到第一个不能通过的站点
    while(count < n){
        int curr = (i + count) % n;//环形路
        gasSum += gas[curr];
        costSum += cost[curr];
        if(gasSum < costSum){
            break;
        }
        count++;
    }
    if(count == n){
        return i;
    }else{
        i = i + count + 1;
    }
}

135. 分发糖果两次遍历。

int n = ratings.length;
int[] left = new int[n];//先看左边的情况
for(int i = 0; i < n; i++){
    if(i > 0 && ratings[i] > ratings[i - 1]){
        left[i] = left[i - 1] + 1;
    }else{
        left[i] = 1;
    }
}
int right = 0, ans = 0;//right节省空间
for(int i = n - 1; i >=0; i--){
    if(i < n - 1 && ratings[i] > ratings[i + 1]){
        right++;  
    }else{
        right = 1;
    }
    ans += Math.max(right, left[i]);
}

860. 柠檬水找零面值有三种，采用计数的方法，分情况讨论。

int five = 0, ten = 0;//张数
for(int bill : bills){
    if(bill == 5){
        five++;
    }else if(bill == 10){
        if(five > 0){
            five--;
            ten++;
        }else{
            return false;
        }
        
    }else{
        if(ten > 0 && five > 0){
            ten--;
            five--;
        }else if(five >= 3){
            five -= 3;
        }else{
            return false;
        }
    }
}

406. 根据身高重建队列思路从高到低对身高排序，然后依次插入。遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。

回顾一下，重写compare和Arraylist用法

arraylist.add（int index，E element）

Arrays.sort(people, new Comparator<int[]>(){
    public int compare(int[] p1, int[] p2){
        if(p1[0] != p2[0]){
            return p2[0] - p1[0];
        }else{
            return p1[1] - p2[1];
        }
    }
});
List<int[]> ans = new ArrayList<>();
for(int[] person : people){
    ans.add(person[1], person);
}

区间问题

435. 无重叠区间解法以右端点排序。为什么要选择从左到右遍历，其实没看懂，给右侧区间留空间？官方解答也很迷。

当确定了首个区间之后，所有与首个区间不重合的区间就组成了一个规模更小的子问题。由于我们已经在初始时将所有区间按照右端点排好序了，因此对于这个子问题，我们无需再次进行排序，只要找出其中与首个区间不重合并且右端点最小的区间即可。

Arrays.sort(intervals, new Comparator<int[]>(){
    public int compare(int[] o1, int[] o2){
        return o1[1] - o2[1];
    }
});

int n = intervals.length;
int right = intervals[0][1];
int ans = 1;
for(int i = 1; i < n; i++){
    if(intervals[i][0] >= right){
        right = intervals[i][1];
        ans++;
    }
}

452. 用最少数量的箭引爆气球虽然题目饶了一点，但也是区间问题。两个维度。贪心体现在：当两个区间不相交时，必然需要一直箭去引爆其中一个区间(换句话说，两个区间不可能被同时引爆)，我们在射出这只箭的同时引爆所有可能被引爆的区间(即做出局部最优选择)。

所以换句话说，这个题是不是还是在求不重叠区间。

这里遇到了一个测试用例问题。[ [-2147483646,-2147483645],[2147483646,2147483647] ]，相减的写法多半的越界了。

在排序时改变书写方式。

1	Arrays.sort(points, (p1, p2) -> p1[1] < p2[1] ? -1 : 1);

763. 划分字母区间字符串，贪心。

int n = s.length();
int[] last = new int[26];
for(int i = 0; i < n; i++){
    //字母最后出现的位置
    last[s.charAt(i) - 'a'] = i;
}

int start = 0, end = 0;
List<Integer> ans = new ArrayList<>();
for(int i = 0; i < n; i++){
    end = Math.max(end, last[s.charAt(i) - 'a']);
    if(end == i){
        ans.add(end - start + 1);
        start = end + 1;
    }
}

56. 合并区间以左端点排序，合并的区间是连续的。尝试了Arrays.sort()的ES6写法但是执行出错，不知道原因。

public int[][] merge(int[][] intervals) {
    int n = intervals.length;
    Arrays.sort(intervals, new Comparator<int[]>(){
        public int compare(int[] p1, int[] p2){
            return p1[0] - p2[0];
        }
    });
    List<int[]> ans = new ArrayList<>();

    for(int i = 0; i < n; i++){
        int L = intervals[i][0], R = intervals[i][1];
        if(ans.size() == 0 || ans.get(ans.size() - 1)[1] < L){
            ans.add(new int[]{L, R}); 
        }else{
            ans.get(ans.size() - 1)[1] = Math.max(R, ans.get(ans.size() - 1)[1]);
        }
    }
    return ans.toArray(new int[ans.size()][]);
}

738. 单调递增的数字没看懂官解，但是评论区的思路很清楚。

【思路】从左往右遍历各位数字，找到第一个开始下降的数字[i]，将[i]减1，然后将[i+1 …]各位数字全部置为9即可

char[] strN = Integer.toString(n).toCharArray();
int i = 1;
while(i < strN.length && strN[i] >= strN[i - 1]){
    i++;
}

if(i < strN.length){
    while(i > 0 && strN[i] < strN[i - 1]){
        strN[i - 1]--;
        i--;
    }

    for(i++; i < strN.length; i++){
        strN[i] = '9';
    }
}

return Integer.parseInt(new String(strN));

队列

leetcode 1606 处理请求最多的服务器