「每日LeetCode」2020年9月9日

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

Lt441.排列硬币、Lt500.键盘行、Lt506.相对名次

441.排列硬币

Category Difficulty Likes Dislikes
algorithms Easy (41.34%) 73 -

Tags
math | binary-search
Companies
Unknown
你总共有 n *枚硬币，你需要将它们摆成一个阶梯形状，第 *k *行就必须正好有 *k *枚硬币。
给定一个数字 _n_，找出可形成完整阶梯行的总行数。
*n *是一个非负整数，并且在 32 位有符号整型的范围内。
*示例 1:**

1
2
3
4
5
6
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.

示例 2:

1
2
3
4
5
6
7
n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.

Discussion | Solution

思路

循环减，直到个数小于 0，当当前剩下的个数大于该行需要的个数时另行数加一，将总数减去相应的数量。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * @lc app=leetcode.cn id=441 lang=javascript
 *
 * [441] 排列硬币
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function (n) {
  let i = n;
  let row = 0;
  while (i > 0) {
    if (i >= row + 1) {
      row++;
    }
    i -= row;
  }
  return row;
};
// @lc code=end
1
2
3
4
Accepted
1336/1336 cases passed (144 ms)
Your runtime beats 11.42 % of javascript submissions
Your memory usage beats 56.41 % of javascript submissions (39.6 MB)

500.键盘行

Category Difficulty Likes Dislikes
algorithms Easy (69.78%) 105 -

Tags
hash-table
Companies
mathworks
给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。

示例：

1
2
输入: ["Hello", "Alaska", "Dad", "Peace"]
输出: ["Alaska", "Dad"]

注意：

  1. 你可以重复使用键盘上同一字符。
  2. 你可以假设输入的字符串将只包含字母。

Discussion | Solution

思路

哈希

使用数组建立哈希表。循环确认每一个字母是否都属于同一行。

正则

使用 test 和正则循环判断加入结果数组即可。

解答

哈希

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*
 * @lc app=leetcode.cn id=500 lang=javascript
 *
 * [500] 键盘行
 */

// @lc code=start
/**
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function (words) {
  const rowMap = {
    q: 1,
    w: 1,
    e: 1,
    r: 1,
    t: 1,
    y: 1,
    u: 1,
    i: 1,
    o: 1,
    p: 1,
    Q: 1,
    W: 1,
    E: 1,
    R: 1,
    T: 1,
    Y: 1,
    U: 1,
    I: 1,
    O: 1,
    P: 1,
    a: 2,
    s: 2,
    d: 2,
    f: 2,
    g: 2,
    h: 2,
    j: 2,
    k: 2,
    l: 2,
    A: 2,
    S: 2,
    D: 2,
    F: 2,
    G: 2,
    H: 2,
    J: 2,
    K: 2,
    L: 2,
    z: 3,
    x: 3,
    c: 3,
    v: 3,
    b: 3,
    n: 3,
    m: 3,
    Z: 3,
    X: 3,
    C: 3,
    V: 3,
    B: 3,
    N: 3,
    M: 3,
  };
  const res = [];
  for (const word of words) {
    const firstWordRow = rowMap[word[0]];
    let flag = true;
    for (const arr of word) {
      if (rowMap[arr] != firstWordRow) {
        flag = false;
        break;
      }
    }
    if (flag) res.push(word);
  }
  return res;
};
// @lc code=end
1
2
3
4
Accepted
22/22 cases passed (68 ms)
Your runtime beats 84.47 % of javascript submissions
Your memory usage beats 16.16 % of javascript submissions (37.8 MB)

正则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * @lc app=leetcode.cn id=500 lang=javascript
 *
 * [500] 键盘行
 */

// @lc code=start
/**
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function (words) {
  const regexp = /^([qwertyuiop]+|[asdfghjkl]+|[zxcvbnm]+)$/i;
  return words.filter((item) => regexp.test(item));
};
// @lc code=end
1
2
3
4
Accepted
22/22 cases passed (76 ms)
Your runtime beats 61.64 % of javascript submissions
Your memory usage beats 5.05 % of javascript submissions (38 MB)

506.相对名次

Category Difficulty Likes Dislikes
algorithms Easy (54.70%) 55 -

Tags
Unknown
Companies
google
给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（”Gold Medal”, “Silver Medal”, “Bronze Medal”）。
(注：分数越高的选手，排名越靠前。)
示例 1:

1
2
3
4
输入: [5, 4, 3, 2, 1]
输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
解释: 前三名运动员的成绩为前三高的，因此将会分别被授予 “金牌”，“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and "Bronze Medal").
余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。

提示:

  1. N 是一个正整数并且不会超过  10000。
  2. 所有运动员的成绩都不相同。

Discussion | Solution

思路

暴力

使用 map 给生成一个{sort:0,score:1}记录成绩和原来排序的对象数组，再根据成绩排序，再根据下标给每一个对象添加 medal 字段，再根据原来的排序排列回来，再将每一个对象的 medal 字段提取出来为一个数组返回。

哈希表

使用 hash 表存储原来的排序，只需要进行一次排序，且不需要添加字段。

解答

暴力

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
39
40
41
42
43
44
/*
 * @lc app=leetcode.cn id=506 lang=javascript
 *
 * [506] 相对名次
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {string[]}
 */
var findRelativeRanks = function (nums) {
  return nums
    .map((e, index) => {
      return {
        score: e,
        sort: index,
      };
    })
    .sort((a, b) => Number(b.score) - Number(a.score))
    .map((e, index) => {
      let medal;
      switch (index) {
        case 0:
          medal = "Gold Medal";
          break;
        case 1:
          medal = "Silver Medal";
          break;
        case 2:
          medal = "Bronze Medal";
          break;
        default:
          medal = index + 1 + "";
          break;
      }
      return Object.assign(e, {
        medal,
      });
    })
    .sort((a, b) => Number(a.sort) - Number(b.sort))
    .map((e) => e.medal);
};
// @lc code=end
1
2
3
4
Accepted
17/17 cases passed (108 ms)
Your runtime beats 68.71 % of javascript submissions
Your memory usage beats 22.37 % of javascript submissions (41.9 MB)

哈希表

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
39
40
41
/*
 * @lc app=leetcode.cn id=506 lang=javascript
 *
 * [506] 相对名次
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {string[]}
 */
var findRelativeRanks = function (nums) {
  const map = new Map();
  const res = new Array(nums.length);
  nums
    .map((e, index) => {
      map.set(e, index);
      return e;
    })
    .sort((a, b) => Number(b) - Number(a))
    .map((e, index) => {
      let medal;
      switch (index) {
        case 0:
          medal = "Gold Medal";
          break;
        case 1:
          medal = "Silver Medal";
          break;
        case 2:
          medal = "Bronze Medal";
          break;
        default:
          medal = index + 1 + "";
          break;
      }
      res[map.get(e)] = medal;
    });
  return res;
};
// @lc code=end
1
2
3
4
Accepted
17/17 cases passed (104 ms)
Your runtime beats 75.51 % of javascript submissions
Your memory usage beats 38.16 % of javascript submissions (41 MB)