东莞网站设计评价,小程序推广代理商,特产网站建设的目的,17zwd一起做网店潮汕站刷题记录 *134. 加油站*135. 分发糖果860. 柠檬水找零*406. 根据身高重建队列 *134. 加油站
leetcode题目地址
当前站点可以剩余油量gas[i] - cost[i]; 将每站的剩余油量求和计算累计剩余油量#xff0c;总剩余油量小于0#xff0c;则无法行驶一周。 若在到达某一站时累计剩… 刷题记录 *134. 加油站*135. 分发糖果860. 柠檬水找零*406. 根据身高重建队列 *134. 加油站
leetcode题目地址
当前站点可以剩余油量gas[i] - cost[i]; 将每站的剩余油量求和计算累计剩余油量总剩余油量小于0则无法行驶一周。 若在到达某一站时累计剩余油量为负时则起始位置为i1。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// java
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum 0;int totalSum 0;int start 0;for(int i0; igas.length; i){curSum gas[i] - cost[i];totalSum gas[i] - cost[i];if(curSum 0){curSum 0;start i1;}}if(totalSum0) return -1;return start;}
}*135. 分发糖果
leetcode题目地址
需要从左右两侧分别考虑而不是同时考虑。 额外开辟一个数组记录每个人的糖果数。
先从左向右查看右侧比左侧大的赋值比左侧的糖果多1。 再从右向左查看左侧比右侧大的赋值比右侧的糖果多1。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
// java
class Solution {public int candy(int[] ratings) {int[] candies new int[ratings.length];Arrays.fill(candies, 1);for(int i1; iratings.length; i){if(ratings[i]ratings[i-1]) candies[i] candies[i-1]1;}int sum candies[ratings.length-1];for(int iratings.length-2; i0; i--){if(ratings[i]ratings[i1]) candies[i] Math.max(candies[i1]1, candies[i]);sum candies[i];}return sum;}
}860. 柠檬水找零
leetcode题目地址
题目要求是立即为顾客找零不可以等待。也就是说只能第一个顾客收5元第二个收10元不允许第一个收10元第二个收5元。
因此只需要分别记录三种面值的数量在收到一份钱后立刻找零若某种面值出现负值则说明找不开返回false。若全程没有出现负值则在最后返回true。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// java
class Solution {public boolean lemonadeChange(int[] bills) {int five0, ten0, twenty0;for(int i0; ibills.length; i){if(bills[i] 5) five;else if(bills[i] 10) {five--;ten;}else{if(ten0){ten--;five--;}else{five-3;}twenty;}if(five0 || ten0 || twenty0) return false;}return true;}
}*406. 根据身高重建队列
leetcode题目地址
共有两个维度h和k分两次考虑先考虑身高对其由高向低排序再考虑k对其由小到大排序。
排序操作O(nlogn)单元素插入指定位置操作O(n)n个元素O(n2)。
时间复杂度 O ( n l o g n n 2 ) O(nlognn^2) O(nlognn2) 空间复杂度 O ( n ) O(n) O(n)
// java
class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, (a, b) - {if(a[0] b[0]) return a[1]-b[1];return b[0]-a[0];});LinkedListint[] que new LinkedList();for (int[] p : people){// 将元素p插入p[1]位置que.add(p[1], p);}return que.toArray(new int[people.length][]);}
}
