Skip to content

Commit ce9f06b

Browse files
BlankjBlankj
committed
fix: 更新题目
1 parent 7100e36 commit ce9f06b

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

48 files changed

+888
-182
lines changed

‎README.md

+1-1
Original file line numberDiff line numberDiff line change
@@ -69,7 +69,7 @@
6969
| :--- | :--------------------------------------- | :------------------------------- |
7070
| 2 | [Add Two Numbers][002] | Linked List, Math |
7171
| 3 | [Longest Substring Without Repeating Characters][003] | Hash Table, Two Pointers, String |
72-
| 5 | [Longest Palindromic Substring][005] | String |
72+
| 5 | [Longest Palindromic Substring][005] | String, Dynamic Programming |
7373
| 6 | [ZigZag Conversion][006] | String |
7474
| 8 | [String to Integer (atoi)][008] | Math, String |
7575
| 11 | [Container With Most Water][011] | Array, Two Pointers |

‎note/005/README.md

+3-3
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@
44

55
Given a string **s**, find the longest palindromic substring in **s**. You may assume that the maximum length of **s** is 1000.
66

7-
**Example:**
7+
**Example 1:**
88

99
```
1010
Input: "babad"
@@ -14,15 +14,15 @@ Output: "bab"
1414
Note: "aba" is also a valid answer.
1515
```
1616

17-
**Example:**
17+
**Example 2:**
1818

1919
```
2020
Input: "cbbd"
2121
2222
Output: "bb"
2323
```
2424

25-
**Tags:** String
25+
**Tags:** String, Dynamic Programming
2626

2727

2828
## 思路 0

‎note/006/README.md

+20-2
Original file line numberDiff line numberDiff line change
@@ -15,10 +15,28 @@ And then read line by line: `"PAHNAPLSIIGYIR"`
1515
Write the code that will take a string and make this conversion given a number of rows:
1616

1717
```
18-
string convert(string text, int nRows);
18+
string convert(string s, int numRows);
1919
```
2020

21-
`convert("PAYPALISHIRING", 3)` should return `"PAHNAPLSIIGYIR"`.
21+
**Example 1:**
22+
23+
```
24+
Input: s = "PAYPALISHIRING", numRows = 3
25+
Output: "PAHNAPLSIIGYIR"
26+
```
27+
28+
**Example 2:**
29+
30+
```
31+
Input: s = "PAYPALISHIRING", numRows = 4
32+
Output: "PINALSIGYAHRPI"
33+
Explanation:
34+
35+
P I N
36+
A L S I G
37+
Y A H R
38+
P I
39+
```
2240

2341
**Tags:** String
2442

‎note/008/README.md

+53-13
Original file line numberDiff line numberDiff line change
@@ -2,23 +2,62 @@
22

33
## Description
44

5-
Implement atoi to convert a string to an integer.
5+
Implement `atoi` which converts a string to an integer.
66

7-
**Hint:** Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
7+
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
88

9-
**Notes:** It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
9+
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
1010

11-
**Spoilers:**
11+
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
1212

13-
**Requirements for atoi:**
13+
If no valid conversion could be performed, a zero value is returned.
1414

15-
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
15+
**Note:**
1616

17-
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
17+
- Only the space character `' '` is considered as whitespace character.
18+
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2<sup>31</sup>, 2<sup>31</sup> − 1]. If the numerical value is out of the range of representable values, INT_MAX (2<sup>31</sup> − 1) or INT_MIN (−2<sup>31</sup>) is returned.
1819

19-
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
20+
**Example 1:**
21+
22+
```
23+
Input: "42"
24+
Output: 42
25+
```
26+
27+
**Example 2:**
28+
29+
```
30+
Input: " -42"
31+
Output: -42
32+
Explanation: The first non-whitespace character is '-', which is the minus sign.
33+
Then take as many numerical digits as possible, which gets 42.
34+
```
35+
36+
**Example 3:**
37+
38+
```
39+
Input: "4193 with words"
40+
Output: 4193
41+
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
42+
```
43+
44+
**Example 4:**
2045

21-
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
46+
```
47+
Input: "words and 987"
48+
Output: 0
49+
Explanation: The first non-whitespace character is 'w', which is not a numerical
50+
digit or a +/- sign. Therefore no valid conversion could be performed.
51+
```
52+
53+
**Example 5:**
54+
55+
```
56+
Input: "-91283472332"
57+
Output: -2147483648
58+
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
59+
Thefore INT_MIN (−2^31) is returned.
60+
```
2261

2362
**Tags:** Math, String
2463

@@ -37,12 +76,13 @@ class Solution {
3776
}
3877
for (; i < len; ++i) {
3978
int tmp = str.charAt(i) - '0';
40-
if (tmp < 0 || tmp > 9)
41-
break;
42-
if (ans > Integer.MAX_VALUE / 10 || ans == Integer.MAX_VALUE / 10 && Integer.MAX_VALUE % 10 < tmp)
79+
if (tmp < 0 || tmp > 9) break;
80+
if (ans > Integer.MAX_VALUE / 10
81+
|| (ans == Integer.MAX_VALUE / 10 && (sign == 1 && tmp > 7 || sign == -1 && tmp > 8))) {
4382
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
44-
else
83+
} else {
4584
ans = ans * 10 + tmp;
85+
}
4686
}
4787
return sign * ans;
4888
}

‎note/009/README.md

+22-7
Original file line numberDiff line numberDiff line change
@@ -2,19 +2,34 @@
22

33
## Description
44

5-
Determine whether an integer is a palindrome. Do this without extra space.
5+
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
66

7-
**Spoilers:**
7+
**Example 1:**
88

9-
**Some hints:**
9+
```
10+
Input: 121
11+
Output: true
12+
```
13+
14+
**Example 2:**
15+
16+
```
17+
Input: -121
18+
Output: false
19+
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
20+
```
1021

11-
Could negative integers be palindromes? (ie, -1)
22+
**Example 3:**
1223

13-
If you are thinking of converting the integer to string, note the restriction of using extra space.
24+
```
25+
Input: 10
26+
Output: false
27+
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
28+
```
1429

15-
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
30+
**Follow up:**
1631

17-
There is a more generic way of solving this problem.
32+
Coud you solve it without converting the integer to a string?
1833

1934
**Tags:** Math
2035

‎note/010/README.md

+54-12
Original file line numberDiff line numberDiff line change
@@ -2,25 +2,67 @@
22

33
## Description
44

5-
Implement regular expression matching with support for `'.'` and `'*'`.
5+
Given an input string (`s`) and a pattern (`p`), implement regular expression matching with support for `'.'` and `'*'`.
66

77
```
88
'.' Matches any single character.
99
'*' Matches zero or more of the preceding element.
10+
```
11+
12+
The matching should cover the **entire** input string (not partial).
13+
14+
**Note:**
15+
16+
- `s` could be empty and contains only lowercase letters `a-z`.
17+
- `p` could be empty and contains only lowercase letters `a-z`, and characters like `.` or `*`.
18+
19+
**Example 1:**
20+
21+
```
22+
Input:
23+
s = "aa"
24+
p = "a"
25+
Output: false
26+
Explanation: "a" does not match the entire string "aa".
27+
```
28+
29+
**Example 2:**
30+
31+
```
32+
Input:
33+
s = "aa"
34+
p = "a*"
35+
Output: true
36+
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
37+
```
38+
39+
**Example 3:**
40+
41+
```
42+
Input:
43+
s = "ab"
44+
p = ".*"
45+
Output: true
46+
Explanation: ".*" means "zero or more (*) of any character (.)".
47+
```
1048

11-
The matching should cover the entire input string (not partial).
49+
**Example 4:**
1250

13-
The function prototype should be:
14-
bool isMatch(const char *s, const char *p)
51+
```
52+
Input:
53+
s = "aab"
54+
p = "c*a*b"
55+
Output: true
56+
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
57+
```
1558

16-
Some examples:
17-
isMatch("aa", "a") → false
18-
isMatch("aa", "aa") → true
19-
isMatch("aaa", "aa") → false
20-
isMatch("aa", "a*") → true
21-
isMatch("aa", ".*") → true
22-
isMatch("ab", ".*") → true
23-
isMatch("aab", "c*a*b") → true
59+
**Example 5:**
60+
61+
```
62+
Input:
63+
s = "mississippi"
64+
p = "mis*is*p*."
65+
Output: false
2466
```
2567

2668
**Tags:** String, Dynamic Programming, Backtracking

‎note/012/README.md

+58-2
Original file line numberDiff line numberDiff line change
@@ -2,9 +2,65 @@
22

33
## Description
44

5-
Given an integer, convert it to a roman numeral.
5+
Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.
66

7-
Input is guaranteed to be within the range from 1 to 3999.
7+
```
8+
Symbol Value
9+
I 1
10+
V 5
11+
X 10
12+
L 50
13+
C 100
14+
D 500
15+
M 1000
16+
```
17+
18+
For example, two is written as `II` in Roman numeral, just two one's added together. Twelve is written as, `XII`, which is simply `X` + `II`. The number twenty seven is written as `XXVII`, which is `XX` + `V` + `II`.
19+
20+
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:
21+
22+
- `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.
23+
- `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.
24+
- `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.
25+
26+
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.
27+
28+
**Example 1:**
29+
30+
```
31+
Input: 3
32+
Output: "III"
33+
```
34+
35+
**Example 2:**
36+
37+
```
38+
Input: 4
39+
Output: "IV"
40+
```
41+
42+
**Example 3:**
43+
44+
```
45+
Input: 9
46+
Output: "IX"
47+
```
48+
49+
**Example 4:**
50+
51+
```
52+
Input: 58
53+
Output: "LVIII"
54+
Explanation: C = 100, L = 50, XXX = 30 and III = 3.
55+
```
56+
57+
**Example 5:**
58+
59+
```
60+
Input: 1994
61+
Output: "MCMXCIV"
62+
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
63+
```
864

965
**Tags:** Math, String
1066

0 commit comments

Comments
 (0)