镇江网站关键字优化如何,微网站开发费用,广州网站优化地址,深圳最近一个星期新闻代码随想录第三十五天 Leetcode 860. 柠檬水找零Leetcode 406. 根据身高重建队列Leetcode 452. 用最少数量的箭引爆气球 Leetcode 860. 柠檬水找零
题目链接: 柠檬水找零 自己的思路:我的垃圾思路#xff01;#xff01;#xff01;#xff01;#xff01;#xff01;复… 代码随想录第三十五天 Leetcode 860. 柠檬水找零Leetcode 406. 根据身高重建队列Leetcode 452. 用最少数量的箭引爆气球 Leetcode 860. 柠檬水找零
题目链接: 柠檬水找零 自己的思路:我的垃圾思路复杂度超高不过好歹是自己想出来的哈哈哈哈哈sh使用就是记录之前出现的5和10的个数其实两个数就可以记录了当出现10或者20的时候将对应的钱找给他
代码:
class Solution {public boolean lemonadeChange(int[] bills) {MapInteger,Integer map new HashMap();for (int i 0;ibills.length;i){map.put(bills[i],map.getOrDefault(bills[i],0)1);if (bills[i]10){if (map.get(5)null||map.get(5)0){return false;}else{map.put(5,map.get(5)-1); }}if (bills[i]20){if (map.get(5)null||map.get(5)0){return false;}else if (map.get(5)!nullmap.get(5)!0map.get(10)!nullmap.get(10)!0){map.put(5,map.get(5)-1); map.put(10,map.get(10)-1); }else if (map.get(10)null||map.get(10)0map.get(5)!nullmap.get(5)!0){map.put(5,map.get(5)-3);if (map.get(5)0){return false;} }}}return true;}
}复杂度分析 时间复杂度 O ( n ) \mathcal{O}(n) O(n) 空间复杂度 O ( n ) \mathcal{O}(n) O(n)
正确思路:和我的思路是一样的只是我是用Map存的个数我是智障正确的应该使用两个数字来存储个数就可以
代码:
class Solution {public boolean lemonadeChange(int[] bills) {int five 0;int ten 0;for (int bill:bills){if (bill5) five;else if (bill10){if (five0) return false;else {five--;ten;}}else{if (ten0five0){ten--;five--;}else if (five3){five - 3;}else return false;}}return true;}
}Leetcode 406. 根据身高重建队列
题目链接: 根据身高重建队列 自己的思路:想不到呀
正确思路:这种有两个维度重新排列的一般都是第一个维度从大到小排序第二个维度从小到大排序或者反过来这样可能会使问题变简单这道题的思路先按身高从大到小进行排序如果k相同的则按照k从小到大排序排完序之后新建一个数组来存放新的数据然后遍历之前的数组取出数组中的元素numnum应该是一个数组第二个维度表示k把k当做索引将[k,num]按k的索引插入到新数组中去感觉这道题只能背过做法记住这种思考方式就行
代码:
class Solution {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];});ArrayListint[] queue new ArrayList();for (int[] num:people){//向指定索引插入元素queue.add(num[1],num);}return queue.toArray(new int[people.length][]);}
}Leetcode 452. 用最少数量的箭引爆气球
题目链接: 用最少数量的箭引爆气球 自己的思路:没想到
正确思路:贪心贪在少射几支箭先按从小到大的顺序将每个气球的左边界排序这样就比较好比较了我们可以比较当前气球的左边界和上一个气球的右边界如果当前气球的左边界大于上一个气球的右边界说明一定不重叠而且不挨着索引我们需要再加一支弓箭否则我们需要更新我们的右边界来看一下后面还有没有气球是可以一起射下来的当前数组的右边界更新为当前数组的右边界和上一个数组右边界的最小值然后遍历整个数组就可以了
代码:
class Solution {public int findMinArrowShots(int[][] points) {if (points.length0) return 0;//将气球左边界从小到大排序Arrays.sort(points,(a,b)-Integer.compare(a[0], b[0]));//至少需要一支弓箭int result 1;for (int i 1;ipoints.length;i){//如果当前气球左边界上一个气球右边界那么一定再需要一支箭if (points[i][0]points[i-1][1]){result;}else{//更新右边界看看后面可不可以//右边界选取两个之间的最小值points[i][1] Math.min(points[i-1][1],points[i][1]);}}return result;}
}
