406

题目：

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

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

1
2
3
4
5
6
7
8
9
10
>输入：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]] 是重新构造后的队列。

示例 2：

1
2
>输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

  • 1 <= people.length <= 2000
  • 0 <= hi <= 106
  • 0 <= ki < people.length
  • 题目数据确保队列可以被重建

思路：

大致意思就是 people.length个人， 每个人的身高为people[i][0]（i 为第i个人） ，与此同时在他前面有people[i][1]个人身高更高或者相同的人。 但是这些人是被打乱顺序的 ，这里需要我们按照每个人的升高和 在他前面的人个数 ， 给他们重新排序。使得排序后的people符合测试用例的result。

仅仅是这样， 我的理解，我这边也看网上有个各种比喻。 比喻来比喻去也就那样， 测试用例中还有hi == 0 的，这个升高为 0的人你怎么比喻？ 所以理解题意即可。

​ 首先，需要给这些人进行排序， 因为题目中要求 编号为i的人 ，身高更高或者相同的人有people[i][1]个。 所以先按照身高进行排序 ， 如果身高相同， 那么就按照后面的身高相同或更高的人的个数进行排序。

1
2
3
4
5
6
7
8
9
Arrays.sort(people, new Comparator<int[]>() {
    public int compare(int[] person1, int[] person2) {
        if (person1[0] != person2[0]) {
            return person2[0] - person1[0];
        } else {
            return person1[1] - person2[1];
        }
    }
});

得到的结果就是按照身高列成有序的二位数组， 这个顺序就是按照身高和 个数结合的，但是还不完整， 这个结合只是争对身高相同的人。对于身高不同的需要继续处理。

以题目中的案例一为例：

[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

排序之后的队列应该是：

[[7,0],[7,1] ,[6,1] ,[5,0], [5,2] , [4,4] ]

当然这只是初步处理，还需要达到：返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第j个人的属性（queue[0] 是排在队列前面的人）。 这个要求 。

所以就需要对排序好的队列 做入队出队 处理 ，这要得到的结果才是题目要求的 result

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
                if (person1[0] != person2[0]) {
                    return person2[0] - person1[0];
                } else {
                    return person1[1] - person2[1];
                }
            }
        });
        List<int[]> ans = new ArrayList<int[]>();
        for (int[] person : people) {
            ans.add(person[1], person);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

860

题目

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

  • 输入：[5,5,5,10,20]
  • 输出：true
  • 解释：
    • 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
    • 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
    • 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
    • 由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

  • 输入：[5,5,10]
  • 输出：true

示例 3：

  • 输入：[10,10]
  • 输出：false

示例 4：

  • 输入：[5,5,10,10,20]
  • 输出：false
  • 解释：
    • 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
    • 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
    • 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
    • 由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

  • 0 <= bills.length <= 10000
  • bills[i] 不是 5 就是 10 或是 20

思路

就是按照题目中的给的用例给用户找零钱， 但是刚开始 你手中是没钱的 ，只有水。当用户给你钱你找不起的时候， 就是返回false的时候 。而且你只有三种钱5,10,20 所以，即使你有钱，但是没有零钱， 也得返回false。

按照这个思路， 直接一路写下来就好。没什么好的思路….

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public boolean lemonadeChange(int[] bills) {
        
        int ten = 0;  // 10 元的数量
        int five = 0 ; // 5元的数量
        int twenty = 0; //20 的数量
       for(int i= 0 ; i< bills.length ; i++){
           if(bills[i] == 5){
               five++;
           }
           if(bills[i] == 10){
               //需要先减少一个5 元， 然后再加一个10 元的数量
                if(five <= 0){
                    return false;
                }
                ten++;
                five--;

           }
           if(bills[i] == 20){
               //先判断10 元的数量够不够 或者 5 元的数量够不够 ，如果不够就false                
               if(five > 0 && ten > 0){
                   five--;
                   ten--;
                   twenty++;
               }
               //需要减少一个5 元的数量 && 一个 10 元的数量 
                else if(five >= 3 ){
                    //直接减少3 个5 元的数量
                    five -= 3;
                    twenty++;
                }else{
                    return false;
                }
           }
       }
       return true;
    }
}

53

题目：

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

子数组 是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

思路

这道题的解法有很多中， 可以使用贪心， 也可以使用暴力 还可以使用动态规划。

这里主要以贪心算法为主学习。

​ 题目要求：具有最大和的连续子数组（子数组最少包含一个元素） 。我们这里使用滑动窗口的方式 累加，如果遇到累加的结果 小于 0， 那么直接跳到下一个位置 重新开始累加。

53.最大子序和

这里参考卡哥的《代码随想录》学习

地址： 代码随想录 (programmercarl.com)

同理， 如果这里遇到刚开始就有负数的情况，需要直接跳到有正数的位置开始， 因为和有负数， 那就不可能达到最大和的要求。

通过sum = Math.max(sum, count); 来实现不断的更新最大的累加和。

实现

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