0-20题解

# 1.Two Sum (opens new window)

两数之和：

给定一个整数数组 nums 和一个整数目标值 target ，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

# Description

Difficulty: Easy

Given an array of integers nums and an integer target , return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

1
2
3

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

1
2

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

1
2

Constraints:

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

# Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const hash = {};
  const hit = (n) => {
    const i = hash[target - n];
    return [i !== undefined, i];
  };

  for (let i = 0; i < nums.length; i++) {
    const n = nums[i],
      [isHit, i0] = hit(n);
    if (isHit) return [i0, i];
    hash[n] = i;
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 2.Add Two Numbers (opens new window)

两数相加：

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

# Description

Difficulty: Medium

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

1
2
3

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

1
2

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

1
2

Constraints:

The number of nodes in each linked list is in the range [1, 100] .
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

# Solution

Language: JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  let v1 = null,
    v2 = null,
    n = 0,
    v = 0;
  (head = new ListNode()), (current = head), l1, l2;
  while (l1 !== null || l2 !== null || n !== 0) {
    [v1, v2] = [l1, l2].map((p) => p?.val ?? 0);
    [l1, l2] = [l1, l2].map((p) => p?.next ?? null);
    [v, n] = [(v1 + v2 + n) % 10, ((v1 + v2 + n) / 10) | 0];
    current = current.next = new ListNode(v);
  }
  return head.next;
};

    v = 0;

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

# 3. Longest Substring Without Repeating Characters (opens new window)

无重复字符的最长子串：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。

# Description

Difficulty: Medium

Given a string s , find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

1
2
3

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

1
2
3

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

1
2
3
4

Constraints:

0 <= s.length <= 5 * 10⁴
s consists of English letters, digits, symbols and spaces.

# Solution

Language: JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const len = s.length;
  if (!len) return 0;
  let w = "",
    max = 0,
    l = 0,
    r = l;

  while (l < len) {
    const c = s.charAt(r),
      idx = w.indexOf(c);
    if (idx !== -1) {
      w = w.slice(idx + 1);
      l += idx + 1;
    }
    w += c;
    r++;
    max = Math.max(max, w.length);
  }
  return max;
};

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

# 4. Median of Two Sorted Arrays (opens new window)

寻找两个正序数组的中位数：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2 。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

# Description

Difficulty: Hard

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)) .

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

1
2
3

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

1
2
3

Constraints:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10⁶ <= nums1[i], nums2[i] <= 10⁶

# Solution

Language: JavaScript

var findMedianSortedArrays = function (nums1, nums2) {
  let prev,
      cur,
      i = 0;
  const mid = (nums1.length + nums2.length + 1) / 2;

  while (nums1.length || nums2.length) {
    prev = cur;
    i++;
    const [n1, n2] = [nums1[0], nums2[0]];
    const [nums, n] = n2 === undefined || n1 <= n2 ? [nums1, n1] : [nums2, n2];
    nums.shift();
    cur = n;
    if (i >= mid) break;
  }

  return i === mid ? cur : (prev + cur) / 2;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 5. Longest Palindromic Substring (opens new window)

最长回文子串：

给你一个字符串 s ，找到 s 中最长的回文子串。

# Description

Difficulty: Medium

Given a string s , return the longest palindromic substring in s .

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

1
2
3

Example 2:

Input: s = "cbbd"
Output: "bb"

1
2

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

# Solution

Language: JavaScript

var longestPalindrome = function (s) {
  const len = s.length,
        dp = new Array(len).fill(null).map(r => new Array(len).fill(null));
  let lp = "";

  for (let i = len - 1; i >= 0; i--) {
    for (let j = 0; j < len; j++) {
      const isLP = dp[i][j] = s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1]);

      if (isLP && j - i + 1 >= lp.length) {
        lp = s.substring(i, j + 1);
      }
    }
  }

  return lp;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 6. Zigzag Conversion (opens new window)

Z 字形变换：

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

# Description

Difficulty: Medium

Related Topics: String (opens new window)

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

1
2
3

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

1
2

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

1
2
3
4
5
6
7

Example 3:

Input: s = "A", numRows = 1
Output: "A"

1
2

Constraints:

1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ',' and '.' .
1 <= numRows <= 1000

# Solution

Language: JavaScript

var convert = function (s, numRows) {
  if (!s || numRows <= 0) return "";
  if (numRows === 1) return s;
  const len = s.length,
        size = 2 * numRows - 2;
  let rst = "";

  for (let i = 0; i < numRows; i++) {
    for (let j = i; j < len; j += size) {
      rst += s.charAt(j);

      if (![0, numRows - 1].includes(i)) {
        const index = size - 2 * i + j;
        if (index < len) rst += s.charAt(index);
      }
    }
  }

  return rst;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 7. Reverse Integer (opens new window)

整数反转：

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2³¹, 2³¹− 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

# Description

Difficulty: Medium

# Solution

Language: JavaScript

var reverse = function (x) {
  let t = 0;

  while (x !== 0) {
    t = t * 10 + x % 10;
    x = ~~(x / 10);
  }

  if (t > Math.pow(2, 31) - 1 || t < -Math.pow(2, 31)) return 0;
  return t;
};

1
2
3
4
5
6
7
8
9
10
11
12

或者：

var reverse = function (x) {
  const max = Math.pow(2, 31),
        isMinus = x < 0;
  if (Math.abs(x) < 10) return x;
  const n = Number(Math.abs(x).toString().split("").reverse().join(""));
  if (n < -max || n > max - 1) return 0;
  return isMinus ? -n : n;
};

1
2
3
4
5
6
7
8

# 8. String to Integer (atoi) (opens new window)

字符串转换整数：

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−2³¹, 2³¹− 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2³¹ 的整数应该被固定为 −2³¹ ，大于 2³¹− 1 的整数应该被固定为 2³¹− 1 。
返回整数作为最终结果。

注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

# Description

Difficulty: Medium

Related Topics: String (opens new window)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is '-' or '+' . Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. "123" -> 123 , "0032" -> 32 ). If no digits were read, then the integer is 0 . Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-2³¹, 2³¹ - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2³¹ should be clamped to -2³¹, and integers greater than 2³¹ - 1 should be clamped to 2³¹ - 1.
Return the integer as the final result.

Note:

Only the space character ' ' is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1:

Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.

1
2
3
4
5
6
7
8
9
10
11

Example 2:

Input: s = "   -42"
Output: -42
Explanation:
Step 1: "   -42" (leading whitespace is read and ignored)
            ^
Step 2: "   -42" ('-' is read, so the result should be negative)
             ^
Step 3: "   -42" ("42" is read in)
               ^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.

1
2
3
4
5
6
7
8
9
10
11

Example 3:

Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
         ^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
             ^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.

1
2
3
4
5
6
7
8
9
10
11

Constraints:

0 <= s.length <= 200
s consists of English letters (lower-case and upper-case), digits ( 0-9 ), ' ' , '+' , '-' , and '.' .

# Solution

Language: JavaScript

var myAtoi = function (s) {
  const max = Math.pow(2, 31);
  let n = parseInt(s.trim());
  if (isNaN(n)) n = 0;
  if (n < -max) return -max;
  if (n > max - 1) return max - 1;
  return n;
};

1
2
3
4
5
6
7
8
9

# 9. Palindrome Number (opens new window)

回文数：

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

# Description

Difficulty: Easy

# Solution

Language: JavaScript

var isPalindrome = function (x) {
  return String(x).split("").reverse().join("") === String(x);
};

1
2
3
4

# 10. Regular Expression Matching (opens new window)

正则表达式匹配：

给你一个字符串 s 和一个字符规律 p ，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

# Description

Difficulty: Hard

Given an input string s and a pattern p , implement regular expression matching with support for '.' and '*' where:

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

1
2
3

Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

1
2
3

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

1
2
3

Constraints:

1 <= s.length <= 20
1 <= p.length <= 30
s contains only lowercase English letters.
p contains only lowercase English letters, '.' , and '*' .
It is guaranteed for each appearance of the character '*' , there will be a previous valid character to match.

# Solution

Language: JavaScript

var isMatch = function (s, p) {
  const m = s.length,
        n = p.length,
        dp = new Array(m + 1).fill(null).map(r => new Array(n + 1).fill(false));
  dp[0][0] = true;

  for (let i = 0; i <= m; ++i) {
    for (let j = 1; j <= n; ++j) {
      if (j > 1 && p[j - 1] === "*") {
        dp[i][j] = dp[i][j - 2] || i > 0 && (s[i - 1] === p[j - 2] || p[j - 2] === ".") && dp[i - 1][j];
      } else {
        dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] === p[j - 1] || p[j - 1] === ".");
      }
    }
  }

  return dp[m][n];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 11. Container With Most Water (opens new window)

盛最多水的容器：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

** 说明：** 你不能倾斜容器。

# Description

Difficulty: Medium

You are given an integer array height of length n . There are n vertical lines drawn such that the two endpoints of the i^th line are (i, 0) and (i, height[i]) .

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

1
2
3

Example 2:

Input: height = [1,1]
Output: 1

1
2

Constraints:

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

# Solution

Language: JavaScript

var maxArea = function (height) {
  if (!height || height.length < 2) return 0;
  let i = 0,
      j = height.length - 1,
      max = 0;

  while (i < j) {
    const cur = (j - i) * Math.min(height[i], height[j]);
    if (cur > max) max = cur;
    if (height[i] <= height[j]) i++;else j--;
  }

  return max;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 12. Integer to Roman (opens new window)

整数转罗马数字：

罗马数字包含以下七种字符： I ， V ， X ， L ， C ， D 和 M 。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

1
2
3
4
5
6
7
8

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII , 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII ，而是 IV 。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX 。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

# Description

Difficulty: Medium

Roman numerals are represented by seven different symbols: I , V , X , L , C , D and M .

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

1
2
3
4
5
6
7
8

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII , which is simply X + II . The number 27 is written as XXVII , which is XX + V + II .

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII . Instead, the number four is written as IV . Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX . There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

1
2
3

Example 2:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

1
2
3

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

1
2
3

Constraints:

1 <= num <= 3999

# Solution

Language: JavaScript

var intToRoman = function (num) {
  const special = {
    4: "IV",
    9: "IX",
    40: "XL",
    90: "XC",
    400: "CD",
    900: "CM"
  };
  const base = [{
    b: 1,
    c: "I"
  }, {
    b: 5,
    c: "V"
  }, {
    b: 10,
    c: "X"
  }, {
    b: 50,
    c: "L"
  }, {
    b: 100,
    c: "C"
  }, {
    b: 500,
    c: "D"
  }, {
    b: 1000,
    c: "M"
  }];
  if (special[String(num)]) return special[String(num)];
  return base.reverse().reduce((rst, {
    b,
    c
  }) => {
    const hb = String(num)[0] + "0".repeat(String(num).length - 1);

    if (special[hb]) {
      rst += special[hb];
      num = num - Number(hb);
    } else {
      rst += c.repeat(~~(num / b));
      num = num % b;
    }

    return rst;
  }, "");
};

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

或者：

const values = {
  M: 1000,
  CM: 900,
  D: 500,
  CD: 400,
  C: 100,
  XC: 90,
  L: 50,
  XL: 40,
  X: 10,
  IX: 9,
  V: 5,
  IV: 4,
  I: 1
};
const orders = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];

var intToRoman = function (num) {
  let roman = "";

  for (const symbol of orders) {
    while (num >= values[symbol]) {
      roman += symbol;
      num -= values[symbol];
    }
  }

  return roman;
};

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

# 13. Roman to Integer (opens new window)

罗马数字转整数：

罗马数字包含以下七种字符: I ， V ， X ， L ， C ， D 和 M 。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

1
2
3
4
5
6
7
8

例如，罗马数字 2 写做 II ，即为两个并列的 1 。 12 写做 XII ，即为 X + II 。 27 写做 XXVII , 即为 XX + V + II 。

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

# Description

Difficulty: Easy

Roman numerals are represented by seven different symbols: I , V , X , L , C , D and M .

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

1
2
3
4
5
6
7
8

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII , which is simply X + II . The number 27 is written as XXVII , which is XX + V + II .

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

1
2
3

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

1
2
3

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

1
2
3

Constraints:

1 <= s.length <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M') .
It is guaranteed that s is a valid roman numeral in the range [1, 3999] .

# Solution

Language: JavaScript

const values = {
  M: 1000,
  CM: 900,
  D: 500,
  CD: 400,
  C: 100,
  XC: 90,
  L: 50,
  XL: 40,
  X: 10,
  IX: 9,
  V: 5,
  IV: 4,
  I: 1
};
const orders = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];

var romanToInt = function (s) {
  let num = 0;

  for (let symbol of orders) {
    while (s.startsWith(symbol)) {
      num += values[symbol];
      s = s.replace(symbol, "");
    }
  }

  return num;
};

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

# 14. Longest Common Prefix (opens new window)

最长公共前缀：

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 "" 。

# Description

Difficulty: Easy

Related Topics: String (opens new window)

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "" .

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

1
2

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

1
2
3

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.

# Solution

Language: JavaScript

var longestCommonPrefix = function (strs) {
  const len = strs.length;
  if (!len) return "";
  if (len === 1) return strs[0];

  const findLCP = (s1, s2) => {
    const s = [...s1].concat([...s2].reverse()),
          sLen = s.length;
    let i = 0,
        j = sLen - 1,
        lcp = "";

    while (i < s1.length, j >= s1.length) {
      if (s[i] !== s[j]) break;
      i++, j--;
    }

    if (i > 0) lcp = s1.substring(0, i);
    return lcp;
  };

  let rst = findLCP(strs[0], strs[1]);

  for (let i = 2; i < len; i++) {
    rst = findLCP(rst, strs[i]);
    if (!rst) break;
  }

  return rst;
};

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

# 15. 3Sum (opens new window)

三数之和：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j 、 i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

** 注意：** 答案中不可以包含重复的三元组。

# Description

Difficulty: Medium

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j , i != k , and j != k , and nums[i] + nums[j] + nums[k] == 0 .

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

1
2
3
4
5
6
7
8

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

1
2
3

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

1
2
3

Constraints:

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

# Solution

Language: JavaScript

function twoSum(nums, s, sum) {
  const len = nums.length,
        r = [];
  if (len - 2 - s < 0) return r;
  let i = s,
      j = len - 1;

  while (i < j) {
    const diff = nums[i] + nums[j];

    if (diff === sum) {
      r.push([nums[i], nums[j]]);

      while (nums[i] === nums[i + 1]) i++;

      while (nums[j] === nums[j - 1]) j--;

      i++, j--;
    } else if (diff < sum) i++;else j--;
  }

  return r;
}

var threeSum = function (nums) {
  const sNums = nums.sort((a, b) => a - b),
        len = sNums.length,
        r = [];
  if (len < 3) return r;

  for (let i = 0; i < len - 2; i++) {
    if (i !== 0 && nums[i] === nums[i - 1]) continue;
    const sub = twoSum(sNums, i + 1, -sNums[i]);
    if (sub.length) r.push(...sub.map(k => [sNums[i], ...k]));
  }

  return r;
};

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

# 16. 3Sum Closest (opens new window)

最接近的三数之和：

给你一个长度为 n 的整数数组 nums 和一个目标值 target 。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

# Description

Difficulty: Medium

Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target .

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2\. (-1 + 2 + 1 = 2).

1
2
3

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0\. (0 + 0 + 0 = 0).

1
2
3

Constraints:

3 <= nums.length <= 500
-1000 <= nums[i] <= 1000
-10⁴ <= target <= 10⁴

# Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  let sNums = nums.sort((a, b) => a - b),
    len = sNums.length,
    c = Number.MAX_SAFE_INTEGER;
  if (len < 2) return false;

  for (let i = 0; i < len - 2; i++) {
    let j = i + 1,
      k = len - 1;
    while (j < k) {
      const sum = sNums[i] + sNums[j] + sNums[k],
        diff = target - sum,
        pDiff = target - c;
      if (Math.abs(diff) < Math.abs(pDiff)) c = sum;
      if (diff === 0) break;
      if (diff > 0) {
        while (sNums[j] === sNums[j + 1]) j++;
        j++;
      } else {
        while (sNums[k] === sNums[k - 1]) k--;
        k--;
      }
    }
  }

  return c;
};

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

# 17. Letter Combinations of a Phone Number (opens new window)

电话号码的字母组合：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

# Description

Difficulty: Medium

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

1
2

Example 2:

Input: digits = ""
Output: []

1
2

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

1
2

Constraints:

0 <= digits.length <= 4
digits[i] is a digit in the range ['2', '9'] .

# Solution

Language: JavaScript

var letterCombinations = function (digits) {
  const len = digits.length,
        mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"],
        r = [];

  const resolve = (i = 0, s = "") => {
    if (s.length === len) {
      !!s && r.push(s);
      return;
    }

    for (let j = i; j < len; j++) {
      const d = digits.charAt(j),
            letters = [...mapping[d]];

      for (letter of letters) {
        s += letter;
        resolve(j + 1, s);
        s = s.slice(0, -1);
      }
    }
  };

  resolve();
  return r;
};

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

编辑

#TO_REVIEW

上次更新: 2022/11/03, 19:39:28

← 本章导读