leetCode周赛94解题报告 javascript

比赛地址

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

 

872. Leaf-Similar Trees

考虑一个二叉树的所有叶子。这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，给定一个如上图所示的树，其叶值序列为 (6, 7, 4, 9, 8) 。

如果两个二叉树的叶值序列相同，我们就认为它们是 叶相似的。

如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，返回 true；否则返回 false 。

 

提示：

• 给定的两个树会有 1 到 100 个结点。

 

题解：按序求出所有叶子节点，比较两棵树的叶子。

 

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var leafSimilar = function(root1, root2) {
    var dfs = function(node, arr) {
        if (node.left) {
            dfs(node.left, arr);
        }
        if (node.right) {
            dfs(node.right, arr);
        }
        if (!node.left && !node.right) {
            arr.push(node.val);
        }
    }
    var l1 = [];
    if (root1) {
        dfs(root1, l1);
    }
    var l2 = [];
    if (root2) {
        dfs(root2, l2);
    }
    if (l1.length != l2.length) {
        return false;
    }
    for (var i = 0; i < l1.length; i++) {
        if (l1[i] != l2[i]) {
            return false;
        }
    }
    return true;
};

 

 

 

 

 

874. Walking Robot Simulation

无限网格上的机器人从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令：

• -2：向左转 90 度
• -1：向右转 90 度
• 1 <= x <= 9：向前移动 x 个单位长度

有一些网格方块被视作障碍物。 

第 i 个障碍物位于网格点  (obstacles[i][0], obstacles[i][1])

如果机器人试图走到障碍物上方，那么它将停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。

返回从原点到机器人的最大欧式距离的平方。

 

示例 1：

输入: commands = [4,-1,3], obstacles = []
输出: 25
解释: 机器人将会到达 (3, 4)

示例 2：

输入: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出: 65
解释: 机器人在左转走到 (1, 8) 之前将被困在 (1, 4) 处

 

提示：

1. 0 <= commands.length <= 10000
2. 0 <= obstacles.length <= 10000
3. -30000 <= obstacle[i][0] <= 30000
4. -30000 <= obstacle[i][1] <= 30000
5. 答案保证小于 2 ^ 31

 

题解：简单模拟，题意有坑：求的是行走过程中的最大距离。

 

/**
 * @param {number[]} commands
 * @param {number[][]} obstacles
 * @return {number}
 */
var robotSim = function(commands, obstacles) {
    var g = {};
    for (var i = 0; i < obstacles.length; i++) {
        if (!g[obstacles[i][0]]) {
            g[obstacles[i][0]] = new Set();
        }
        g[obstacles[i][0]].add(obstacles[i][1]);
    }
    var dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    var d = 0;
    var curi = 0;
    var curj = 0;
    var ans = 0;
    for (var i = 0; i < commands.length; i++) {
        if (commands[i] == -1) {
            d = (d + 1) % 4;
        }
        else if (commands[i] == -2) {
            d = (d + 3) % 4;
        }
        else { 
            for (var j = 0; j < commands[i]; j++) {
                var nexti = curi + dir[d][0];
                var nextj = curj + dir[d][1];
                if (g[nexti] && g[nexti].has(nextj)) {
                    break;
                }
                curi = nexti;
                curj = nextj;
            }
        }
        ans = Math.max(ans, curi * curi + curj * curj);
    }
    return ans;
};

 

 

 

 

 

875. Koko Eating Bananas

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

 

示例 1：

输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2：

输入: piles = [30,11,23,4,20], H = 5
输出: 30

示例 3：

输入: piles = [30,11,23,4,20], H = 6
输出: 23

 

提示：

• 1 <= piles.length <= 10^4
• piles.length <= H <= 10^9
• 1 <= piles[i] <= 10^9

 

题解：求耗时不超过H的最小吃香蕉速度，二分法求解。

 

/**
 * @param {number[]} piles
 * @param {number} H
 * @return {number}
 */
var minEatingSpeed = function(piles, H) {
    var cal = function(h) {
        var ans = 0;
        for (var i = 0; i < piles.length; i++) {
            ans += Math.ceil(piles[i] / h);
        }
        return ans;
    }
    var f = 1;
    var r = piles[0];
    for (var i = 1; i < piles.length; i++) {
        r = Math.max(r, piles[i]);
    }
    while(f < r) {
        var m = f + ((r - f) >> 1);
        if (cal(m) > H) {
            f = m + 1;
        }
        else {
            r = m;
        }
    }
    return r;
};

 

 

 

 

 

873. Length of Longest Fibonacci Subsequence

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。

（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

 

示例 1：

输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为：[1,2,3,5,8] 。

示例 2：

输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 。

 

提示：

• 3 <= A.length <= 1000
• 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
• （对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）

 

题解：用集合缩短查找时间。

 

/**
 * @param {number[]} A
 * @return {number}
 */
var lenLongestFibSubseq = function(A) {
    var s = new Set(A);
    var ans = 0;
    var n = A.length;
    for (var i = 0; i < n; i++) {
        for (var j = i + 1; j < n; j++) {
            for (var a = A[i], b = A[j], sum = a + b, cur = 2; s.has(sum); cur++) {
                a = b;
                b = sum;
                sum = a + b;
            }
            ans = Math.max(ans, cur);
        }
    }
    return ans > 2 ? ans : 0;
};