力扣每日一刷(2023.9.6)

简介: 力扣每日一刷(2023.9.6)

406

题目:

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


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


示例 1:

>输入: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:

>输入: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]个。 所以先按照身高进行排序 , 如果身高相同, 那么就按照后面的身高相同或更高的人的个数进行排序。

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


实现

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。


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


实现

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:

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

示例 2:

输入:nums = [1]
输出:1

示例 3:

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

提示:


1 <= nums.length <= 105

-104 <= nums[i] <= 104

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


思路

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


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


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


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


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


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


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


实现

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;
    }
}
目录
相关文章
|
算法 索引
力扣每日一刷(2023.9.5)
力扣每日一刷(2023.9.5)
57 1
力扣每日一刷(2023.9.24)(二)
力扣每日一刷(2023.9.24)
60 0
|
存储 图计算 索引
力扣每日一刷(2023.9.24)(一)
力扣每日一刷(2023.9.24)
54 0
力扣每日一刷(2023.9.21)
力扣每日一刷(2023.9.21)
53 0
|
算法 测试技术
力扣每日一刷(2023.9.19)
力扣每日一刷(2023.9.19)
59 0
力扣每日一刷(2023.9.14)
力扣每日一刷(2023.9.14)
52 0
力扣每日一刷(2023.9.12)
力扣每日一刷(2023.9.12)
45 0
|
机器人
力扣每日一刷(2023.9.11)
力扣每日一刷(2023.9.11)
69 0
|
监控
力扣每日一刷(2023.9.8)
力扣每日一刷(2023.9.8)
37 0
力扣每日一刷(2023.9.7)
力扣每日一刷(2023.9.7)
49 0