「每日LeetCode」2020年9月11日

本文最后更新于：2023年3月19日 晚上

Lt53.最大子序和、Lt112.路径总和、Lt299.猜数字游戏

53.最大子序和

Category Difficulty Likes Dislikes
algorithms Easy (52.25%) 2408 -

Tags
array | divide-and-conquer | dynamic-programming
Companies
bloomberg | linkedin | microsoft
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

Discussion | Solution

思路

// Kadane 算法扫描一次整个数列的所有数值，
// 在每一个扫描点计算以该点数值为结束点的子数列的最大和（正数和）。
// 该子数列由两部分组成：以前一个位置为结束点的最大子数列、该位置的数值。
// 因为该算法用到了“最佳子结构”（以每个位置为终点的最大子数列都是基于其前一位置的最大子数列计算得出,
// 该算法可看成动态规划的一个例子。
// 状态转移方程：sum[i] = max{sum[i-1]+a[i],a[i]}  
// 其中(sum[i]记录以 a[i]为子序列末端的最大序子列连续和)

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 * @lc app=leetcode.cn id=53 lang=javascript
 *
 * [53] 最大子序和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let pre = 0,
    maxAns = nums[0];
  for (const num of nums) {
    pre = Math.max(pre + num, num);
    maxAns = Math.max(maxAns, pre);
  }
  return maxAns;
};
// @lc code=end
1
2
3
4
Accepted
202/202 cases passed (96 ms)
Your runtime beats 36.77 % of javascript submissions
Your memory usage beats 27.3 % of javascript submissions (39.8 MB)

112.路径总和

Category Difficulty Likes Dislikes
algorithms Easy (51.10%) 425 -

Tags
tree | depth-first-search
Companies
microsoft
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，

1
2
3
4
5
6
7
5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

Discussion | Solution

思路

递归思想要看树最小规模，例：只看根节点及左右节点 5-4-8。如果根节点没有值，则返回 false；如果不是叶子节点，则去判断左边路径或者右边路径的和是否符合需求，传入左节点及 sum-root.val。如果没有左右节点，则直接判断值是否等于 sum。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
 * @lc app=leetcode.cn id=112 lang=javascript
 *
 * [112] 路径总和
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function (root, sum) {
  if (!root) return false;
  if (!root.left && !root.right) return sum === root.val;
  return (
    hasPathSum(root.left, sum - root.val) ||
    hasPathSum(root.right, sum - root.val)
  );
};
// @lc code=end
1
2
3
4
Accepted
114/114 cases passed (100 ms)
Your runtime beats 33.48 % of javascript submissions
Your memory usage beats 25.29 % of javascript submissions (41.5 MB)

299.猜数字游戏

Category Difficulty Likes Dislikes
algorithms Easy (48.45%) 94 -

Tags
hash-table
Companies
Unknown
你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

  1. 你写出一个秘密数字，并请朋友猜这个数字是多少。
  2. 朋友每猜测一次，你就会给他一个提示，告诉他的猜测数字中有多少位属于数字和确切位置都猜对了（称为“Bulls”, 公牛），有多少位属于数字猜对了但是位置不对（称为“Cows”, 奶牛）。
  3. 朋友根据提示继续猜，直到猜出秘密数字。

请写出一个根据秘密数字和朋友的猜测数返回提示的函数，返回字符串的格式为 xAyB ，x 和 y 都是数字，A 表示公牛，用 B 表示奶牛。

  • xA 表示有 x 位数字出现在秘密数字中，且位置都与秘密数字一致。
  • yB 表示有 y 位数字出现在秘密数字中，但位置与秘密数字不一致。

请注意秘密数字和朋友的猜测数都可能含有重复数字，每位数字只能统计一次。

示例 1:

1
2
3
输入: secret = "1807", guess = "7810"
输出: "1A3B"
解释: 1 公牛和 3 奶牛。公牛是 8，奶牛是 0, 1 和 7。

示例 2:

1
2
3
输入: secret = "1123", guess = "0111"
输出: "1A1B"
解释: 朋友猜测数中的第一个 1 是公牛，第二个或第三个 1 可被视为奶牛。

**说明: **你可以假设秘密数字和朋友的猜测数都只包含数字，并且它们的长度永远相等。

Discussion | Solution

思路

先遍历两个字符串，求得完全一样的数的个数，并将其移出数组，同时将不同的数及其个数存入 map。再遍历猜测的字符串，如果在 map 中，则奶牛数+1，并把 map 中的数量减一，相当于互相抵消。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
 * @lc app=leetcode.cn id=299 lang=javascript
 *
 * [299] 猜数字游戏
 */

// @lc code=start
/**
 * @param {string} secret
 * @param {string} guess
 * @return {string}
 */
var getHint = function (secret, guess) {
  const map = new Map();
  secret = secret.split("");
  guess = guess.split("");
  let bullsCount = 0;
  let cowsCount = 0;
  for (let i = 0; i < secret.length; i++) {
    if (secret[i] === guess[i]) {
      secret.splice(i, 1);
      guess.splice(i, 1);
      bullsCount++;
      i--;
    } else {
      map.set(secret[i], map.get(secret[i]) ? map.get(secret[i]) + 1 : 1);
    }
  }
  for (let i = 0; i < secret.length; i++) {
    if (map.has(guess[i])) {
      if (map.get(guess[i]) === 1) map.delete(guess[i]);
      else map.set(guess[i], map.get(guess[i]) - 1);
      cowsCount++;
    }
  }
  return `${bullsCount}A${cowsCount}B`;
};
// @lc code=end
1
2
3
4
Accepted
152/152 cases passed (100 ms)
Your runtime beats 45.97 % of javascript submissions
Your memory usage beats 17.36 % of javascript submissions (40.6 MB)