当前位置:首页 » JAVA技术教程

leetCode周赛97解题报告 javascript

2018-08-12 14:22 本站整理 浏览(5)

比赛地址:

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;
};