今天的题目真是给我做恶心了
134. 加油站
暴力方法很容易写出来，但在力扣上运行会超时。
class Solution {
int[] gas;
int[] cost;
public int canCompleteCircuit(int[] gas, int[] cost) {
this.gas = gas;
this.cost = cost;
for(int i = 0; i < gas.length; i++){
if(gas[i] < cost[i]) continue;
if(isVaild(i)) return i;
}
return -1;
}
public boolean isVaild(int index){
int oil = 0;
for(int i = index; i < index + gas.length; i++){
int ind = i % gas.length;
oil = oil + gas[ind] - cost[ind];
if(oil < 0) return false;
}
return true;
}
}
这个解法有点太优雅了，太难想到。gas = [1,2,3,4,5] cost = [3,4,5,1,2]对于这两个我们可以求其差值，dif = [-2,-2,-2,3,3]，其实本题的题意就是要使得从某个位置出发，dif的累加和始终大于等于0。然而我们可以发现，无论从哪个位置开始累加，累加和的曲线是完全平行的，但是上下会有差别（这个我不知道怎么证明，全凭感觉）。所以，无论从哪个点出发，最小值出现的位置并不会发生改变。因此，就从0出发，找到累加和最小值的位置，其下一个点就是出发点（亏空最严重的一个点必须放在最后一步走，等着前面剩余的救助）。当然这里还需要考虑dif总和小于0，说明不存在出发点。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0;
int minIndex = 0;
int minValue = Integer.MAX_VALUE;
for(int i = 0; i < gas.length; i++){
sum += gas[i] - cost[i];
if(sum <= minValue){
minIndex = i;
minValue = sum;
}
}
return sum < 0 ? -1 : (minIndex+1) % gas.length;
}
}
135. 分发糖果
努力去理解了，但还是理解不了，只能靠背了。但是背只能记忆怎么去做的步骤，为什么能保证正确性其实是不明白的。
思路就看题解吧
class Solution {
/**
分两个阶段
1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
*/
public int candy(int[] ratings) {
int len = ratings.length;
int[] candyVec = new int[len];
candyVec[0] = 1;
for (int i = 1; i < len; i++) {
candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
}
for (int i = len - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
}
}
int ans = 0;
for (int num : candyVec) {
ans += num;
}
return ans;
}
}
860. 柠檬水找零
也就只能做这个题了，今天的题目放它就是为了不把人完全打击至死吧我觉得。
class Solution {
public boolean lemonadeChange(int[] bills) {
int[] map = new int[3];
for(int num : bills){
if(num == 5) map[0]++;
if(num == 10) {
map[1]++;
if(--map[0] < 0) return false;
}
if(num == 20){
map[2]++;
if(map[1] > 0){
map[1]--;
if(--map[0] < 0) return false;
}else{
map[0] -= 3;
if(map[0] < 0) return false;
}
}
}
return true;
}
}
406. 根据身高重建队列
我只能想到暴力解法，但时间复杂度很高。先简单叙述思路，也能帮助对题解的理解。
根据身高对原数组升序排序，相同身高的则根据k升序。用res数组存储最终的结果，用两层循环去遍历，第一层循环代表将要填充的为位置，第二层对people进行遍历，若符合条件（res中已存元素中，身高大于等于当前person的数量恰好等于将要插入的k）就插入。填充满了就返回结果。由于插入每次都能保证是唯一且正确的，所以不会出现错误的情况。这里的贪心就在于，(5，0)和(7, 0)尽管都能放在第一个位置，但由于排序，先进行填充的一定是(5, 0)。
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> {
if(a[0] - b[0] == 0) return a[1] - b[1];
return a[0] - b[0];
});
int[][] res = new int[people.length][];
boolean[] visited = new boolean[people.length];
for(int i = 0; i < people.length; i++){
for(int j = 0; j < people.length; j++){
if(visited[j]) continue;
if(isValid(res, people[j], i)) {
visited[j] = true;
res[i] = people[j];
break;
}
}
}
return res;
}
public boolean isValid(int[][] res, int[] person, int len){
int h = person[0]; int k = person[1];
for(int i = 0; i < len; i++){
if(res[i][0] >= h) k--;
}
return k == 0;
}
}