「每日LeetCode」2020年9月3日

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

169.多数元素

Category Difficulty Likes Dislikes
algorithms Easy (64.40%) 723 -

Tags
array | divide-and-conquer | bit-manipulation
Companies
adobe | zenefits
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于** ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例  1:

1
2
输入: [3,2,3]
输出: 3

示例  2:

1
2
输入: [2,2,1,1,1,2,2]
输出: 2

Discussion | Solution

思路

1.排序计数

对数组进行排序，遍历排序后的数组，对相同的元素计数，若大于数组长度的一半则返回元素。
实际上直接返回数组的第 1/2 个下标的元素即可

1
return nums.sort()[parseInt(nums.length / 2)];

2.map

遍历数组加入 map，当计数大于 n/2 时返回。

3.摩尔投票

摩尔投票法基于这样一个事实，当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。
算法步骤：
1.count = 0； num = nums[0]; 表示从此时开始计算投票。 2.遍历数组，如果接下来出现的数字与 num 相同，count 加 1。如果不同，count 减 1。 3.如果 count == 0，表示之前出现的所有数字中 num 都是可以凑成不同的数对，一起抵消。大于 1/2 n 的数还会在后面出现。 4.如果 count < 0，表示之前 num 中的数字没有到一半，所以此时完全不用考虑前面存储的元素，“删除”他们。直接从现在的新的元素开始计数，并令 count = 0。

解答

1.排序计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * @lc app=leetcode.cn id=169 lang=javascript
 *
 * [169] 多数元素
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  //let numSort = nums.sort();
  //let count = 0;
  //for (let i = 0; i < numSort.length; i++) {
  //  count++;
  //  if(count>numSort.length/2) return numSort[i]
  //  if(numSort[i]!==numSort[i+1]){
  //    count=0;
  //  }
  //}
  return nums.sort()[parseInt(nums.length / 2)];
};
// @lc code=end
1
2
3
4
Accepted
46/46 cases passed (92 ms)
Your runtime beats 46.89 % of javascript submissions
Your memory usage beats 5.9 % of javascript submissions (41.8 MB)

2.map

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=169 lang=javascript
 *
 * [169] 多数元素
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  const map = new Map();
  for (const num of nums) {
    map.set(num, map.has(num) ? map.get(num) + 1 : 1);
    if (map.get(num) > nums.length / 2) {
      return num;
    }
  }
};
// @lc code=end
1
2
3
4
Accepted
46/46 cases passed (100 ms)
Your runtime beats 26.29 % of javascript submissions
Your memory usage beats 37.3 % of javascript submissions (40.2 MB)

3.摩尔投票

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
/*
 * @lc app=leetcode.cn id=169 lang=javascript
 *
 * [169] 多数元素
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  let count = 0;
  let num = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] != num) {
      count--;
      if (count < 0) {
        count = 0;
        num = nums[i];
      }
    } else count++;
  }
  return num;
};
// @lc code=end
1
2
3
4
Accepted
46/46 cases passed (72 ms)
Your runtime beats 96.22 % of javascript submissions
Your memory usage beats 72.81 % of javascript submissions (39.6 MB)

168.Excel 表列名称

Category Difficulty Likes Dislikes
algorithms Easy (38.25%) 261 -

Tags
math
Companies
facebook | microsoft | zenefits
给定一个正整数，返回它在 Excel 表中相对应的列名称。
例如，

1
2
3
4
5
6
7
8
1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB
    ...

示例 1:

1
2
输入: 1
输出: "A"

示例  2:

1
2
输入: 28
输出: "AB"

示例  3:

1
2
输入: 701
输出: "ZY"

Discussion | Solution

思路

类 26 进制

类似 26 进制，但是没有 0。使用对象存储对应数字的值。判断是否取余为 0，是的话使 n–，再取对象里的 key 为 26 的值。

解答

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
/*
 * @lc app=leetcode.cn id=168 lang=javascript
 *
 * [168] Excel表列名称
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string}
 */
var convertToTitle = function (n) {
  let res = "";
  const obj = {
    1: "A",
    2: "B",
    3: "C",
    4: "D",
    5: "E",
    6: "F",
    7: "G",
    8: "H",
    9: "I",
    10: "J",
    11: "K",
    12: "L",
    13: "M",
    14: "N",
    15: "O",
    16: "P",
    17: "Q",
    18: "R",
    19: "S",
    20: "T",
    21: "U",
    22: "V",
    23: "W",
    24: "X",
    25: "Y",
    26: "Z",
  };
  while (n > 0) {
    if (n % 26 === 0) {
      n--;
      res = obj[26] + res;
    } else {
      res = obj[n % 26] + res;
    }
    n = Math.floor(n / 26);
  }
  return res;
};
// @lc code=end
1
2
3
4
Accepted
18/18 cases passed (88 ms)
Your runtime beats 16.89 % of javascript submissions
Your memory usage beats 5.44 % of javascript submissions (37.8 MB)

171.Excel 表列序号

Category Difficulty Likes Dislikes
algorithms Easy (67.99%) 171 -

Tags
math
Companies
给定一个 Excel 表格中的列名称，返回其相应的列序号。
例如，

1
2
3
4
5
6
7
8
A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28
    ...

示例 1:

1
2
输入: "A"
输出: 1

示例  2:

1
2
输入: "AB"
输出: 28

示例  3:

1
2
输入: "ZY"
输出: 701

致谢：
特别感谢 @ts 添加此问题并创建所有测试用例。

Discussion | Solution

思路

类 26 进制

类似 26 进制，转数组，对每一位进行求值相加，指数刚好是数组出队以后的长度。

解答

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
/*
 * @lc app=leetcode.cn id=171 lang=javascript
 *
 * [171] Excel表列序号
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var titleToNumber = function (s) {
  let count = 0;
  let sArr = s.split("");
  const obj = {
    A: 1,
    B: 2,
    C: 3,
    D: 4,
    E: 5,
    F: 6,
    G: 7,
    H: 8,
    I: 9,
    J: 10,
    K: 11,
    L: 12,
    M: 13,
    N: 14,
    O: 15,
    P: 16,
    Q: 17,
    R: 18,
    S: 19,
    T: 20,
    U: 21,
    V: 22,
    W: 23,
    X: 24,
    Y: 25,
    Z: 26,
  };
  while (sArr.length > 0) {
    count += obj[sArr.shift()] * Math.pow(26, sArr.length);
  }
  return count;
};
// @lc code=end
1
2
3
4
Accepted
1000/1000 cases passed (96 ms)
Your runtime beats 70.06 % of javascript submissions
Your memory usage beats 9.65 % of javascript submissions (39.9 MB)

237.删除链表中的节点

Category Difficulty Likes Dislikes
algorithms Easy (82.74%) 745 -

Tags
linked-list
Companies
adobe | apple | microsoft
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 – head = [4,5,1,9]，它可以表示为:

示例 1：

1
2
3
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2：

1
2
3
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

提示：

  • 链表至少包含两个节点。
  • 链表中所有节点的值都是唯一的。
  • 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
  • 不要从你的函数中返回任何结果。

Discussion | Solution

思路

阅读游戏

题目的意思是删除输入的节点。使当前节点等于下一个节点的 val 和 next 即可。

解答

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=237 lang=javascript
 *
 * [237] 删除链表中的节点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function (node) {
  node.val = node.next.val;
  node.next = node.next.next;
};
// @lc code=end
1
2
3
4
Accepted
41/41 cases passed (84 ms)
Your runtime beats 72.29 % of javascript submissions
Your memory usage beats 14.59 % of javascript submissions (39.8 MB)

551.学生出勤记录 I

Category Difficulty Likes Dislikes
algorithms Easy (51.69%) 49 -

Tags
string
Companies
google
给定一个字符串来代表一个学生的出勤记录，这个记录仅包含以下三个字符：

  1. ‘A’ : Absent，缺勤
  2. ‘L’ : Late，迟到
  3. ‘P’ : Present，到场

如果一个学生的出勤记录中不超过一个’A’(缺勤)**并且不超过两个连续的’L’(迟到),那么这个学生会被奖赏。
你需要根据这个学生的出勤记录判断他是否会被奖赏。
**示例 1:

1
2
输入: "PPALLP"
输出: True

示例 2:

1
2
输入: "PPALLL"
输出: False

Discussion | Solution

思路

正则

/^(?!.*LLL)(?!.*(A).*\1)/
解析：
._(A).\1 表示允许 A 重复 例如 cAbA
?! 表示断言不包含，不占用字符串长度
(?!.(A)._\1) 表示断言不允许 A 重复

.*LLL 表示以 LLL 结尾 ABCLLL
(?!.*LLL)表示不以 LLL 结尾

image.png

遍历字符串

indexOf LLL，存在则返 false。计数 A，如果大于 1 则返 false

解答

正则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * @lc app=leetcode.cn id=551 lang=javascript
 *
 * [551] 学生出勤记录 I
 */

// @lc code=start
/**
 * @param {string} s
 * @return {boolean}
 */
var checkRecord = function (s) {
  return /(?!.*(A).*\1)^(?!.*LLL)/.test(s);
};
// @lc code=end
1
2
3
4
Accepted
113/113 cases passed (80 ms)
Your runtime beats 53.02 % of javascript submissions
Your memory usage beats 25 % of javascript submissions (37.9 MB)

遍历字符串

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=551 lang=javascript
 *
 * [551] 学生出勤记录 I
 */

// @lc code=start
/**
 * @param {string} s
 * @return {boolean}
 */
var checkRecord = function (s) {
  let count = 0;
  if (s.indexOf("LLL") !== -1) return false;
  for (const arr of s) {
    if (arr === "A") count++;
    if (count > 1) return false;
  }
  return true;
};
// @lc code=end
1
2
3
4
Accepted
113/113 cases passed (80 ms)
Your runtime beats 53.02 % of javascript submissions
Your memory usage beats 13.09 % of javascript submissions (38.1 MB)

541.反转字符串 II

Category Difficulty Likes Dislikes
algorithms Easy (55.04%) 89 -

Tags
string
Companies
google
给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

1
2
输入: s = "abcdefg", k = 2
输出: "bacdfeg"

提示：

  1. 该字符串只包含小写英文字母。
  2. 给定字符串的长度和 k 在 [1, 10000] 范围内。

Discussion | Solution

思路

字符串分割为数组，遍历，步长为 2k。将前 k 个数组删除，并反转后再插入，将数组转回字符串。

解答

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=541 lang=javascript
 *
 * [541] 反转字符串 II
 */

// @lc code=start
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function (s, k) {
  s = s.split("");
  for (let i = 0; i < s.length; i = i + 2 * k) {
    const reverseArr = s.slice(i, i + k).reverse();
    s.splice(i, k, ...reverseArr);
  }
  return s.join("");
};
// @lc code=end
1
2
3
4
Accepted
60/60 cases passed (92 ms)
Your runtime beats 38.27 % of javascript submissions
Your memory usage beats 28.95 % of javascript submissions (40.8 MB)

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！