leetCode周赛96解题报告 javascript

比赛地址：

https://leetcode-cn.com/contest/weekly-contest-96

 

887. Projection Area of 3D Shapes

887. 三维形体投影面积

在 N * N 的网格中，我们放置了一些与 x，y，z 三轴对齐的 1 * 1 * 1 立方体。

每个值 v = grid[i][j] 表示 v 个正方体叠放在单元格 (i, j) 上。

现在，我们查看这些立方体在 xy、yz 和 zx 平面上的投影。

投影就像影子，将三维形体映射到一个二维平面上。

在这里，从顶部、前面和侧面看立方体时，我们会看到“影子”。

返回所有三个投影的总面积。

 

示例 1：

输入：[[2]]
输出：5

示例 2：

输入：[[1,2],[3,4]]
输出：17
解释：
这里有该形体在三个轴对齐平面上的三个投影(“阴影部分”)。

示例 3：

输入：[[1,0],[0,2]]
输出：8

示例 4：

输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：14

示例 5：

输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：21

 

提示：

• 1 <= grid.length = grid[0].length <= 50
• 0 <= grid[i][j] <= 50

题解：使用两个数组分别记录x轴方向与y轴方向的最大值并累加，grid[i][j]非零俯视图也算作一格投影。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var projectionArea = function(grid) {
    if (!grid || grid.length == 0) {
        return 0;
    }
    var n = grid.length;
    var xs = new Array(n).fill(0);
    var ys = new Array(n).fill(0);
    var count = 0;
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            var h = grid[i][j];
            if (h !== 0) {
                count++;
            }
            xs[i] = Math.max(xs[i], h);
            ys[j] = Math.max(ys[j], h);
        }
    }
    for (var i = 0; i < n; i++) {
        count += xs[i] + ys[i];
    }
    return count;
};

 

 

 

 

885. Boats to Save People

885. 救生艇

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

 

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)

示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)

提示：

• 1 <= people.length <= 50000
• 1 <= people[i] <= limit <= 30000

题解：贪心算法，重量大的先上船，如果能同时载一个最轻的就载这两人，否则一次载一个重的。

/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function(people, limit) {
    people.sort((a,b)=>a-b);
    var ans = 0;
    for (var i = 0, j = people.length - 1; i <= j; j--) {
        if (people[i] + people[j] <= limit) {
            i++;
        }
        ans++;
    }
    return ans;
};

 

 

 

 

884. Decoded String at Index

884. 索引处的解码字符串

给定一个编码字符串 S。为了找出解码字符串并将其写入磁带，从编码字符串中每次读取一个字符，并采取以下步骤：

• 如果所读的字符是字母，则将该字母写在磁带上。
• 如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。

现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。

 

示例 1：

输入：S = "leet2code3", K = 10
输出："o"
解释：
解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。
字符串中的第 10 个字母是 "o"。

示例 2：

输入：S = "ha22", K = 5
输出："h"
解释：
解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。

示例 3：

输入：S = "a2345678999999999999999", K = 1
输出："a"
解释：
解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。

 

提示：

1. 2 <= S.length <= 100
2. S 只包含小写字母与数字 2 到 9 。
3. S 以字母开头。
4. 1 <= K <= 10^9
5. 解码后的字符串保证少于 2^63 个字母。

题解：遇到数字就将位置翻倍，如果大于目标位置则对其取模转换为规模较小的子问题，否则当前位置增一，到达目标位置即输出。

/**
 * @param {string} S
 * @param {number} K
 * @return {string}
 */
var decodeAtIndex = function(S, K) {
    var count = 0;
    for (var i = 0; i < S.length; i++) {
        var n = parseInt(S[i]);
        if (n) {
            if (count * n >= K) {
                return decodeAtIndex(S, (K - 1) % count + 1);
            }
            count *= n;
        }
        else {
            count++;
            if (count === K) {
                return S[i];
            }
        }
    }
};