leetcode每天5题-Day53-贪心2

1.K 次取反后最大化的数组和

1005. K 次取反后最大化的数组和-简单

排序：按绝对值大小从大到小排序，当k大于0时遇到负数就取反。

var largestSumAfterKNegations = function(nums, k) {
    nums.sort((a, b) => Math.abs(b) - Math.abs(a));

    for(let i = 0; i < nums.length; i++) {
        if(nums[i] < 0 && k > 0) {
            nums[i] = - nums[i];
            k--;
        }
    }
    if(k > 0 && k % 2 === 1) {
        nums[nums.length - 1] *= -1;
    }
    let sum = nums.reduce((p, c) => {return p + c});
    return sum;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

优化：一遍遍历

var largestSumAfterKNegations = function(nums, k) {
    nums.sort((a, b) => Math.abs(b) - Math.abs(a)); // 排序
    let sum = 0;
    for(let i = 0; i < nums.length; i++) {
        if(nums[i] < 0 && k-- > 0) { // 负数取反（k 数量足够时）
            nums[i] = -nums[i];
        }
        sum += nums[i]; // 求和
    }
    if(k % 2 > 0) { // k 有多余的（k若消耗完则应为 -1）
        sum -= 2 * nums[nums.length - 1]; // 减去两倍的最小值（因为之前加过一次）
    }
    return sum;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总结：想到了排序，但没想到按绝对值大小排序。我想的是按大小排序，遇到负值就取反，然后k--，遇到0，直接把k置为0，大于0时就判断k的值，如果k不为0，再对当前的正数一直取反，直到k为0。这样做其实有很多没考虑到的情况，很不严谨。而且因为是遍历过程中判断元素大小，如果负数取反后比原数组的最小正数还小，那么我的这种办法就没办法了。

2.加油站

134. 加油站-中等
暴力

var canCompleteCircuit = function(gas, cost) {
    for(let i = 0; i < gas.length; i++) {
        // 记录剩余油量
        let rest = gas[i] - cost[i];
        //index是下一个加油站
        let index = Math.floor((i + 1) % gas.length);
        while(rest > 0 && index !== i) {
            rest += gas[index] - cost[index];
            index = Math.floor((index + 1) % gas.length); 
        }
        if(rest >= 0 && index == i) return i;
    }
    return -1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

全局最优

三种情况：

1. gas数组总和小于cost数组总和，无论从哪里出发，都无法行驶一周；
2. rest[i] = gas[i] - cost[i]为从第i个加油站出发到下一个加油站时剩的油量，i从0累加到最后一战，如果累加过程中没有出现负数，说明可以从0出发
3. 如果累加的最小值是负数，表示不能从0出发，从后向前遍历，看哪个加油站可以把这个负数填平，该加油站就可以作为出发点

var canCompleteCircuit = function(gas, cost) {
    let sum = 0;
    let min = Infinity;
    for(let i = 0; i < gas.length; i++) {
        let rest = gas[i] - cost[i];
        sum += rest;
        if(sum < min) min = sum;
    }
    if(sum < 0) return -1; // 情况1 总油量小于总耗油量
    if(min >= 0) return 0; // 情况2 油箱里油没断过
    // 情况3
    for(let i = gas.length - 1; i >= 0; i--) {
        let rest = gas[i] - cost[i];
        min += rest;
        if(min >= 0) return i;
    }
    return -1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时：O(n)
空：O(1)

局部最优
思路：在可以行驶一周的前提下，对rest[i]进行累加，当sum小于0时，就说明[0,i]区间都不能作为出发点，清空sum，再从i+1开始计算。

var canCompleteCircuit = function(gas, cost) {
    let curSum = 0, totalSum = 0, start = 0;
    for(let i = 0; i < gas.length; i++) {
        let rest = gas[i] - cost[i];
        curSum += rest;
        totalSum += rest;
        if(curSum < 0) {
            start = i + 1;
            curSum = 0;
        }
    }
    if(totalSum < 0) return -1;

    return start;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时：O(n)
空：O(1)

总结：我想的是判断对应加油站gas与cost值，一一比较，直到gas[i]大于等于cost[i]，说明可以从i出发，其实这种想法跟暴力法差不多。但我没想到可以直接累计这个差值，根据差值的和判断出发地点。

3. 分发糖果

135. 分发糖果-困难

思路：不能同时考虑两边，不然容易顾此失彼。两遍遍历，首先从前向后遍历（只比较右边孩子评分比左边大的情况），确定candy数组，再从后向前遍历（只比较左边孩子评分比右边大的情况），同时结合candy数组，最后确定需要的糖果数。
注：candy中数量不应该是加一或加二，而是根据相邻元素的值，即candy[i - 1]或者candy[i + 1]的值去确定。

var candy = function(ratings) {
    if(ratings.length === 1) return 1;
    const candy = new Array(ratings.length).fill(1);
    for(let i = 1; i < ratings.length; i++) {
        if(ratings[i] > ratings[i - 1]) {
            candy[i] = candy[i - 1] + 1;
        }
    }

    for(let i = ratings.length - 2; i >= 0; i--) {
        if(ratings[i] > ratings[i + 1]) {
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
        }
    return candy.reduce((p, c) => {return p + c;})

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 柠檬水找零

860. 柠檬水找零-简单
重点：给20元找零时，优先用10元和5元去找，没有10元，再用3张5元的找。

局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

var lemonadeChange = function(bills) {
    if(bills[0] === 10 || bills[0] === 20) return false;
    const nums = new Array(2).fill(0);
    for(let i = 0; i < bills.length; i++) {
        if(bills[i] === 5) {
            nums[0]++;
        }else if(bills[i] === 10) {
            if(nums[0] <= 0) return false;
            nums[0]--;
            nums[1]++;
        }else if(bills[i] === 20) {
            if(nums[0] > 0 && nums[1] > 0) {
                nums[0]--;
                nums[1]--;
            }else if(nums[0] >= 3) {
                nums[0] -= 3;
            }else{
                return false;
            }
        }
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5. 根据身高重建队列

406. 根据身高重建队列-中等

和上上题有点像，遇到两个维度时，不能同时考虑，要先确定一个维度，再确定另一个维度。

那么本题应该先考虑身高h还是个数k呢？
如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。如果按照身高h来排序，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。这样我们就能确定一个维度了，也就是身高。

var reconstructQueue = function(people) {
    let queue = [];
    people.sort((a, b) => {
        if(a[0] !== b[0]) {
            // 按身高从高到低排序
            return b[0] - a[0];
        }else{
            // 身高相同时 k值从小到大排序
            return a[1] - b[1];
        }
    });
    for(let i = 0; i < people.length; i++) {
        // people[i] 要放入索引为people[i][1] 的位置
        queue.splice(people[i][1], 0, people[i]);

    }
    return queue;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18