leetcode刷题日记

2022/11/13 #20 有效的括号#

这道题目的核心思想理解栈的数据结构

1
var isValid = function (s) {
2
  const dict = new Map([
3
    ["(", ")"],
4
    ["{", "}"],
5
    ["[", "]"],
6
  ])
7
  const stack = []
8
  const pres = [...dict.keys()]
9
  const ends = [...dict.values()]
10
  for (let i = 0; i < s.length; i++) {
11
    const char = s[i]
12
    if (pres.includes(char)) {
13
      stack.push(char)
14
    } else if (ends.includes(char)) {
15
      if (dict.get(stack.pop()) !== char) return false
16
    }
17
  }
18
  return !stack.length
19
};

2022/11/14 #1 两数之和#

两个数字相亲记~

1
var twoSum = function (nums, target) {
2
  const map = new Map()
3
  for (let i = 0; i < nums.length; i++) {
4
    const n = nums[i]
5
    const theHalf = target - n
6
    if (!map.has(theHalf)) {
7
      map.set(n, i)
8
    } else {
9
      return [map.get(theHalf), i]
10
    }
11
  }
12
};

2022/11/15 #9 回文数#

其实就是两个指针靠近,直到两人亲上都还能没发生不同,那就是一个回文数

1
var isPalindrome = function (x) {
2
  const n = "" + x;
3
  if (n.length === 1) return true;
4
  let p1 = 0,
5
    p2 = n.length - 1;
6
  while (p1++ < p2--) {
7
    if (n[p1-1] !== n[p2+1]) return false;
8
  }
9
  return true;
10
};

2022/11/16 #13 罗马数字#

这道题我最开始写出来是这样的,能明显感觉到不是很优雅

1
var romanToInt = function (s) {
2
  const dict = new Map([
3
    ['I', 1],
4
    ['V', 5],
5
    ['X', 10],
6
    ['L', 50],
7
    ['C', 100],
8
    ['D', 500],
9
    ['M', 1000],
10
  ]);
11
  let flag = false
12
  const nums = s.split('')
13
  return nums.reduce((p, n, i) => {
14
    if (dict.get(nums[i + 1]) > dict.get(n)) {
15
      flag = true
16
      return p + 0
17
    }
18
    if (flag) {
19
      flag = false
20
      return p + dict.get(n) - dict.get(nums[i - 1])
21
    }
22
    return p + dict.get(n)
23
  }, 0)
24
};

通过观察我们可以看出来,当右边不小于左边的时候是正常的的转换逻辑,当右边比左边大的就需要用右边减去左边,那我们可以先减再加,我们可以这样改

1
var romanToInt = function (s) {
2
  const dict = new Map([
3
    ['I', 1],
4
    ['V', 5],
5
    ['X', 10],
6
    ['L', 50],
7
    ['C', 100],
8
    ['D', 500],
9
    ['M', 1000],
10
  ]);
11
  return s.split('').reduce((p, n, i, ns) => {
12
    if (dict.get(ns[i + 1]) > dict.get(n)) {
13
      return p - dict.get(n)
14
    } else {
15
      return p + dict.get(n)
16
    }
17
  }, 0)
18
};

2022/11/17 #14 最长公共前缀#

1
var longestCommonPrefix = function (strs) {
2
  let p = 0
3
  while (p > -1) {
4
    const uniPicks = [...new Set(strs.map((str) => str[p]))]
5
    if (uniPicks.includes(undefined) || uniPicks.length != 1) {
6
      return strs[0].substring(0, p)
7
    }
8
    p++
9
  }
10
};

2022/11/18 #26 删除有序数组中的重复项#

1
var removeDuplicates = function (nums) {
2
  const uniNums = [...new Set(nums)]
3
  nums.length = uniNums.length
4
  uniNums.forEach((n, i) => {
5
    nums[i] = n
6
  })
7
  return nums.length
8
};

2022/11/19 #27 移除元素#

1
var removeElement = function (nums, val) {
2
  let i = 0;
3
  while (i < nums.length) {
4
    if (nums[i] === val) {
5
      nums.splice(i, 1)
6
    } else {
7
      i++
8
    }
9
  }
10
  return nums.length
11
};

2022/11/21 #35 搜索插入位置 | #58 最后一个单词的长度#

1
// #35 搜索插入位置
2
var searchInsert = function (nums, target) {
3
  for (let i = 0; i < nums.length; i++) {
4
    // case1 相等
5
    if (nums[i] === target) return i;
6
    // case2 在某个节点大于它之前
7
    if (nums[i] > target) return i;
8
  }
9
  // case3 插入末尾
10
  return nums.length;
11
};
12

13
// #58 最后一个单词的长度
14
var lengthOfLastWord = function (s) {
15
  return s.trim().split(" ").at(-1).length;
16
};

2022/11/22 #66 加一#

1
var plusOne = function (digits) {
2
  let carry = false;
3
  digits[digits.length - 1] = digits.at(-1) + 1;
4
  for (let i = digits.length - 1; i >= 0; i--) {
5
    let n = digits[i]
6
    if (carry) {
7
      n++;
8
      carry = false;
9
    }
10
    if (n >= 10) {
11
      carry = true;
12
      digits[i] = n % 10;
13
    } else {
14
      digits[i] = n;
15
    }
16
  }
17
  if (carry) {
18
    digits.unshift(1)
19
  }
20
  return digits;
21
};

想了想,其实所有工作都可以在for循环里完成

1
var plusOne = function (digits) {
2
  digits[digits.length - 1] = digits.at(-1) + 1;
3
  for (let i = digits.length - 1; i >= 0; i--) {
4
    if (digits[i] >= 10) {
5
      digits[i] = digits[i] % 10;
6
      // 防止下标越界
7
      if (i === 0) {
8
        digits.unshift(1);
9
      } else {
10
        digits[i - 1] = digits[i - 1] + 1;
11
      }
12
    }
13
  }
14
  return digits;
15
};

2022/11/23 #67 二进制求和#

这道题和昨天的题神似,不过换成二进制的n+n,昨天是十进制的n+1

1
var addBinary = function (a, b) {
2
  const r = [];
3
  const sameLen = a.length === b.length;
4
  // 长组
5
  const l = sameLen ? a : a.length > b.length ? a : b
6
  const lt = l.split("");
7
  const li = lt.length - 1;
8
  // 短组
9
  const s = sameLen ? b : a.length < b.length ? a : b
10
  const st = s.split("");
11
  let si = st.length - 1;
12
  // 长短差
13
  const di = li - si;
14
  // 公共进制位
15
  while (si >= 0) {
16
    const n = +lt[di + si] + +st[si]
17
    // 需要进位
18
    if (n >= 2) {
19
      r.unshift(n % 2);
20
      // 相同长度下防止下标越界
21
      if (si === 0 && sameLen) {
22
        r.unshift(1)
23
      } else {
24
        lt[si + di - 1] = +lt[si + di - 1] + 1;
25
      }
26
    }
27
    // 无需进位
28
    else {
29
      r.unshift(n);
30
    }
31
    si--
32
  }
33
  // 长组余下进制位,其实和上边的逻辑相似,只是不用考虑加法
34
  if (di) {
35
    let i = di - 1;
36
    while (i >= 0) {
37
      const n = lt[i];
38
      if (n >= 2) {
39
        r.unshift(n % 2)
40
        if (i === 0) {
41
          r.unshift(1)
42
        } else {
43
          lt[i - 1] = +lt[i - 1] + 1;
44
        }
45
      } else {
46
        r.unshift(n)
47
      }
48
      i--
49
    }
50
  }
51
  return r.join('');
52
};

看到评论区有同学说,长度不一样的情况下可以直接补齐之后再计算,一想的确有道理啊,但是效率应该不会有多大提升,该循环的次数一次没少,不过简洁一些

1
var addBinary = function (a, b) {
2
  const r = [];
3
  const sameLen = a.length === b.length;
4
  // 长组
5
  const l = sameLen ? a : a.length > b.length ? a : b
6
  const lt = l.split("");
7
  let li = lt.length - 1;
8
  // 短组
9
  const s = sameLen ? b : a.length < b.length ? a : b
10
  const st = s.split("");
11
  const si = st.length - 1;
12
  // 长短差
13
  const di = li - si;
14
  // 补齐短组
15
  const ft = sameLen ? st : [...new Array(di).fill(0), ...st];
16
  // 公共进制位
17
  while (li >= 0) {
18
    const n = +lt[li] + +ft[li]
19
    // 需要进位
20
    if (n >= 2) {
21
      r.unshift(n % 2);
22
      // 相同长度下防止下标越界
23
      if (li === 0) {
24
        r.unshift(1)
25
      } else {
26
        lt[li - 1] = +lt[li - 1] + 1;
27
      }
28
    }
29
    // 无需进位
30
    else {
31
      r.unshift(n);
32
    }
33
    li--
34
  }
35
  return r.join('');
36
};

确实少了很多代码哈.

2022/11/27 #69 X的平方根 | #70 爬楼梯 | # 83 删除排序链表中的重复元素#

1
// #69
2
var mySqrt = function (x) {
3
  if (x == 0 || x == 1) return x;
4
  let left = 1, right = x;
5
  // 只要左边没超过右边就需要一直去查找
6
  while (left < right) {
7
    // 如果只相隔1,直接返回左边
8
    if (right - left == 1) return left;
9
    // 向下取整中位数
10
    let mid = left + Math.floor((right - left) / 2);
11
    // 除以中位数
12
    let res = x / mid;
13
    // 如果刚好结果相等,中位数就是想要的数字
14
    if (res === mid) return mid;
15
    // 如果结果小于中位数,说明应该向左缩小范围
16
    if (res < mid) {
17
      right = mid;
18
    }
19
    // 如果结果大于中位数,说明应该向右缩小范围
20
    else {
21
      left = mid;
22
    }
23
  }
24
};
25

26
// #70 这是一道经典的动态规划的算法题目,你需要做的最关键的一点是总结出前后节点的规律,或者说是一个公式
27
var climbStairs = function (n) {
28
  if (n < 2) return 1;
29
  // 用来保存每个台阶的方法数目
30
  const dp = [1, 1];
31
  for (let i = 2; i <= n; i++) {
32
    dp[i] = dp[i - 1] + dp[i - 2];
33
  }
34
  return dp[n];
35
};
36

37
// #83
38
var deleteDuplicates = function (head) {
39
  let p = head;
40
  while (p && p.next) {
41
    // 下个节点
42
    const next = p.next;
43
    // 如果重复,将当前节点的next指向下个节点的next
44
    if (next.val === p.val) {
45
      p.next = next.next;
46
    } else {
47
      // 将当前指针往后移动
48
      p = p.next;
49
    }
50
  }
51
  return head;
52
};

2023/1/19 #88 合并两个有序数组#

这个题依然算是简单的指针题,两个指针在自己的合适的情况前进,直到走到目标位置即可

不知道为啥今天leetcode抽疯测试和提交出问题了,但是在本地测试是没问题的,没有测试所有测试用例,可能会有边角料问题,小case~

1
var merge = function (nums1, m, nums2, n) {
2
  const res = [];
3
  let i = 0, j = 0;
4
  while (i < m || j < n) {
5
    const n1 = nums1[i]
6
    const n2 = nums2[j]
7
    // 是否越界
8
    if (i >= m) {
9
      res.push(n2)
10
      j++
11
    }
12
    // 是否越界
13
    else if (j >= n) {
14
      res.push(n1)
15
      i++
16
    }
17
    // 判断大小
18
    else if (n1 < n2) {
19
      res.push(n1)
20
      i++
21
    } else if (n1 > n2) {
22
      res.push(n2)
23
      j++
24
    }
25
    // 相等
26
    else {
27
      res.push(n1, n2)
28
      i++
29
      j++
30
    }
31
  }
32
  return res
33
};

原来leetcode那天并没有抽风,其实是我没注意到题目,是合并到num1数组,不是返回一个新数组 =.=

1
var merge = function (nums1, m, nums2, n) {
2
  // 从后往前遍历，避免覆盖
3
  let i = m - 1, j = n - 1, k = m + n - 1;
4
  while (i >= 0 && j >= 0) {
5
    if (nums1[i] > nums2[j]) {
6
      nums1[k--] = nums1[i--];
7
    } else {
8
      nums1[k--] = nums2[j--];
9
    }
10
  }
11
  // nums2还有剩余
12
  while (j >= 0) {
13
    nums1[k--] = nums2[j--];
14
  }
15
  return nums1;
16
};

2023/1/19 #112 合并两个有序数组#

2023/4/11 #104 二叉树的最大深度#

1
var maxDepth = function (root) {
2
  if (root === null) return 0;
3
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
4
};

20230/6/7#

189 轮转数组#

1
var rotate = function (nums, k) {
2
  for (let i = 0; i < k; i++) {
3
    nums.unshift(nums.pop());
4
  }
5
};

724 寻找数组的中心下标#

这道题目难度是中等？我感觉就很简单啊~

1
var pivotIndex = function (nums) {
2
  let index = -1;
3
  for (let i = 0; i < nums.length; i++) {
4
    const leftSum = nums.slice(0, i).reduce((a, b) => a + b, 0);
5
    const rightSum = nums.slice(i + 1).reduce((a, b) => a + b, 0);
6
    if (leftSum === rightSum) {
7
      index = i;
8
      break;
9
    }
10
  }
11
  return index
12
};

音乐

音乐