leetCode周赛97解题报告 javascript

比赛地址：

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

 

888. 两句话中的不常见单词

888. Uncommon Words from Two Sentences

给定两个句子 A 和 B 。 （句子是一串由空格分隔的单词。每个单词仅由小写字母组成。）

如果一个单词在其中一个句子中只出现一次，在另一个句子中却没有出现，那么这个单词就是不常见的。

返回所有不常用单词的列表。

您可以按任何顺序返回列表。

 

示例 1：

输入：A = "this apple is sweet", B = "this apple is sour"
输出：["sweet","sour"]

示例 2：

输入：A = "apple apple", B = "banana"
输出：["banana"]

 

提示：

1. 0 <= A.length <= 200
2. 0 <= B.length <= 200
3. A 和 B 都只包含空格和小写字母。

题解：使用aCount、bCount分别记录两句话中每个单词数量，数量为1且不在另一句话中的单词即为不常见的。

/**
 * @param {string} A
 * @param {string} B
 * @return {string[]}
 */
var uncommonFromSentences = function(A, B) {
    var a = A.split(" ");
    var b = B.split(" ");
    var aCount = {};
    for (var i = 0; i < a.length; i++) {
        if (!aCount[a[i]]) {
            aCount[a[i]] = 0;
        }
        aCount[a[i]]++;
    }
    var bCount = {};
    for (var i = 0; i < b.length; i++) {
        if (!bCount[b[i]]) {
            bCount[b[i]] = 0;
        }
        bCount[b[i]]++;
    }
    var ans = [];
    for (var w in aCount) {
        if (aCount[w] == 1 && !bCount[w]) {
            ans.push(w);
        }
    }
    for (var w in bCount) {
        if (bCount[w] == 1 && !aCount[w]) {
            ans.push(w);
        }
    }
    return ans;
};

 

 

 

 

889. 螺旋矩阵 III

889. Spiral Matrix III

在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始

这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。

每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，我们到过网格的所有 R * C 个空间。

按照访问顺序返回表示网格位置的坐标列表。

 

示例 1：

输入：R = 1, C = 4, r0 = 0, c0 = 0
输出：[[0,0],[0,1],[0,2],[0,3]]

 

示例 2：

输入：R = 5, C = 6, r0 = 1, c0 = 4
输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

 

提示：

1. 1 <= R <= 100
2. 1 <= C <= 100
3. 0 <= r0 < R
4. 0 <= c0 < C

题解：根据示例2可见，只有朝东或朝西时移动长度会多一格，模拟螺旋移动，将矩阵内的位置按序输出。

/**
 * @param {number} R
 * @param {number} C
 * @param {number} r0
 * @param {number} c0
 * @return {number[][]}
 */
var spiralMatrixIII = function(R, C, r0, c0) {
    var ans = [[r0, c0]];
    var curi = r0;
    var curj = c0;
    var len = 0;
    while(true) {
        len++;
        for (var i = 0; i < len; i++) {
            curj++;
            if (0 <= curi && curi < R && 0 <= curj && curj < C) {
                ans.push([curi, curj]);
            }
        }
        for (var i = 0; i < len; i++) {
            curi++;
            if (0 <= curi && curi < R && 0 <= curj && curj < C) {
                ans.push([curi, curj]);
            }
        }
        len++;
        for (var i = 0; i < len; i++) {
            curj--;
            if (0 <= curi && curi < R && 0 <= curj && curj < C) {
                ans.push([curi, curj]);
            }
        }
        for (var i = 0; i < len; i++) {
            curi--;
            if (0 <= curi && curi < R && 0 <= curj && curj < C) {
                ans.push([curi, curj]);
            }
        }
        if (ans.length == R * C) {
            break;
        }
    }
    return ans;
};

 

 

 

 

890. 可能的二分法

890. Possible Bipartition

给定一组 N 人（编号为 1, 2, ..., N）， 我们想把每个人分进任意大小的两组。

每个人都可能不喜欢其他人，那么他们不应该属于同一组。

形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。

当可以用这种方法将每个人分进两组时，返回 true；否则返回 false。

 

示例 1：

输入：N = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]

示例 2：

输入：N = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false

示例 3：

输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false

 

提示：

1. 1 <= N <= 2000
2. 0 <= dislikes.length <= 10000
3. 1 <= dislikes[i][j] <= N
4. dislikes[i][0] < dislikes[i][1]
5. 对于 dislikes[i] == dislikes[j] 不存在 i != j

题解：以示例1分析，先将编号1加入集合a，然后将所有与1互斥的2、3加入集合b，再将所有与2、3互斥的4加入集合a，依次操作直到所有编号已经分配好或没有能分配的编号。

/**
 * @param {number} N
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function(N, dislikes) {
    var g = new Array(N + 1).fill().map(v=>new Array());
    for (var i = 0; i < dislikes.length; i++) {
        g[dislikes[i][0]].push(dislikes[i][1]);
        g[dislikes[i][1]].push(dislikes[i][0]);
    }
    var a = new Set();
    a.add(1);
    var b = new Set();
    var aAdded = [1];
    var bAdded = [];
    while(true) {
        for (var k = 0; k < aAdded.length; k++) {
            var num = aAdded[k];
            for (var i = 0; i < g[num].length; i++) {
                if (a.has(g[num][i])) {
                    return false;
                }
                if (!b.has(g[num][i])) {
                    b.add(g[num][i]);
                    bAdded.push(g[num][i]);
                }
            }
        }
        aAdded = [];
        for (var k = 0; k < bAdded.length; k++) {
            var num = bAdded[k];
            for (var i = 0; i < g[num].length; i++) {
                if (b.has(g[num][i])) {
                    return false;
                }
                if (!a.has(g[num][i])) {
                    a.add(g[num][i]);
                    aAdded.push(g[num][i]);
                }
            }
        }
        bAdded = [];
        if (a.size + b.size == N) {
            // 有可能最后一次添加到a集合的元素不合法，有必要再检查一次
            for (var num of a) {
                for (var i = 0; i < g[num].length; i++) {
                    if (a.has(g[num][i])) {
                        return false;
                    }
                }
            }
            return true;
        }
        else if (aAdded.length == 0) {
            // 已经没有新的添加元素
            return true;
        }
    }
};

  

 

 

 

891. 鸡蛋掉落

891. Super Egg Drop

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

 

示例 1：

输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

示例 2：

输入：K = 2, N = 6
输出：3

示例 3：

输入：K = 3, N = 14
输出：4

 

提示：

1. 1 <= K <= 100
2. 1 <= N <= 10000

题解：动态规划思路，dp[i][j]表示i个鸡蛋j次操作最多可以测量的楼层数，分析可得出转移方程：dp[i][j] = dp[i][j]+dp[i][j]+1，将题目转换为求满足dp[K][j]>=N最小的j，有K=2，N=1这样的特殊测试数据，打个补丁可过 if(N==1)return1;

/**
 * @param {number} K
 * @param {number} N
 * @return {number}
 */
var superEggDrop = function(K, N) {
    if (N == 1) {
        return 1;
    }
    var dp = new Array(K + 1).fill().map(v=>new Array(2).fill(1));
    for (var i = 1; i <= N; i++) {
        dp[1][i] = i;
    }
    for (var i = 2; i <= K; i++) {
        for (var j = 2; ; j++) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] + 1;
            if (dp[i][j] >= N) {
                break;
            }
        }
    }
    return dp[K].length - 1;
};