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; } }