Leetcode第1题至第10题 思路分析及C++实现

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## Leetcode第1题至第10题 思路分析及C++实现

(笔者目前已刷 40 题，已更新解法 10 题，最近一段时间会频繁更新)可以点击下方链接，直达gitbook：
https://codernie.gitbooks.io/leetcode-solutions/content/

# 1. Two Sum 【easy】

### 实现代码：

``````// 1. Two Sum
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> myMap;
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
if (myMap.find(target - nums[i]) == myMap.end()) {
myMap[nums[i]] = i;
} else {
result = {myMap[target - nums[i]], i};
break;
}
}
return result;
}
``````

### 问题描述：

Given an array of integers, return **indices **of the two numbers such that they add up to a specific target.

You may assume that each input would have _**exactly **_one solution, and you may not use the_same_element twice.

Example:

``````Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
``````

### 解题思路：

1.进位的的处理：carry表示进位，当最后一位还有进位时，即使 l1 和 l2 均为NULL的情况下，还需要生成一个新的结点，所以while的条件中加入了 carry != 0 判断项。

2.返回头结点：当头结点为NULL的时候记录头结点，并且让p等于头结点；后续情况让 p->next 等于新的结点，并让 p 指向 p->next。

### 实现代码：

``````// 2. Add Two Numbers
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carry = 0, sum;
while (l1 != NULL || l2 != NULL || carry != 0) {
sum = 0;
if (l1 != NULL) {
sum += l1->val;
l1 = l1->next;
}
if (l2 != NULL) {
sum += l2->val;
l2 = l2->next;
}
sum += carry;
carry = sum / 10;
sum %= 10;
ListNode *newNode = new ListNode(sum);
p = newNode;
} else {
p->next = newNode;
p = p->next;
}
}
}
``````

### 问题描述：

You are given two non-empty linked lists representing two non-negative integers. The digits are stored inreverse orderand each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

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

Example

``````Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
``````

# 3. Longest Substring Without Repeating Characters【medium】

### 实现代码：

``````// 3. Longest Substring Without Repeating Characters
// 暴力解法
int lengthOfLongestSubstring_bruteForce(string s) {
int res = 0, sum;
for (int i = s.size() - 1; i >= 0; i--) {
sum = 1;
for (int j = i - 1; j >= 0; j--) {
bool flag = true;
for (int k = i; k > j; k--) {
if (s[j] == s[k]) {
flag = false;
break;
}
}
if (flag) {
sum++;
} else {
break;
}
}
res = max(res, sum);
}
return res;
}
// 头尾标记法
int lengthOfLongestSubstring(string s) {
map<char, int> myMap;
int res = 0;
for (int i = 0, j = 0; j < s.size(); j++){
if (myMap.find(s[j]) != myMap.end()) {
i = max(i, myMap[s[j]] + 1);
}
myMap[s[j]] = j;
res = max(res, j - i + 1);
}
return res;
}
``````

### 问题描述：

Given a string, find the length of thelongest substringwithout repeating characters.

Examples:

Given`"abcabcbb"`, the answer is`"abc"`, which the length is 3.

Given`"bbbbb"`, the answer is`"b"`, with the length of 1.

Given`"pwwkew"`, the answer is`"wke"`, with the length of 3. Note that the answer must be asubstring,`"pwke"`is asubsequenceand not a substring.

# 4. Median of Two Sorted Arrays【hard】

### 解题思路：

#### 二分查找法 O(log(min(m, n)))：

``````          left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
``````

• A[i - 1] <= B[j] 且 B[j - 1] <= A[i] ：这不正是我们要找的 i 吗？可以直接返回答案
• A[i - 1] > B[j] 且 B[j - 1] > A[i] ：根据有序数列的性质，再利用反证法不难证明这种情况不可能存在
• A[i - 1] <= B[j] 且 B[j - 1] > A[i]：为了使情况更加接近我们的答案，也就是情况1。也就是要使 B[j - 1] <= A[i]，因为现在 B[j - 1] > A[i]，所以我们要想办法缩小 B[j - 1]，扩大A[i]，所以当然是让我们的 i 增大，否则情况会越来越远离我们的正确答案。
• A[i - 1] > B[j] 且 B[j - 1] <= A[i]：与情况3恰恰相反，这里我们应该缩小我们的 i。

1.如果不存在满足条件二的情况会怎么样呢？也就是 i 走到了数组A的尽头，依旧没法满足条件二，这个时候我们不难知道如果 i 走到数组A的最左端，那么它一定是在不断地经历情况4，而这时 A[0] > B[j]，那么我们不难知道这时left_part的最大值就是B[j - 1]；反之我们也可以推出 i 到了A的最右端、j 到了B的最左端或者最右端的情况。

2.m + n 为奇数。这个时候我们不难推出 left_part 的最大值就是中位数。

3.A或B为空数组，因为当数组空的时候无法对数组进行下标访问，所以我们在进行二分查找前就应该对该情况进行特殊处理，处理方式也是很简单的啦。

### 实现代码：

``````// 4. Median of Two Sorted Arrays
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 使得 nums1 短于 nums2
int m = nums1.size();
int n = nums2.size();
if (m > n) {
vector<int> temp = nums1;
nums1 = nums2;
nums2 = temp;
m = m + n;
n = m - n;
m = m - n;
}
// 考虑数组长度为0的边界情况
if (m == 0) {
if (n == 0) {
return 0;
} else {
if (n % 2 == 1) {
return nums2[n / 2];
} else {
return (double)(nums2[n / 2] + nums2[n / 2 - 1]) / 2;
}
}
}
int iMin = 0, iMax = m, sizeSum = (m + n + 1) / 2, i, j;
while (iMin <= iMax) {
i = (iMax + iMin) / 2;
j = sizeSum - i;
if (nums2[j - 1] > nums1[i] && i < iMax) {
iMin = i + 1;
} else if (nums1[i - 1] > nums2[j] && i > iMin) {
iMax = i - 1;
} else {
int maxLeft, minRight;
if (i == 0) {
maxLeft = nums2[j - 1];
} else if (j == 0) {
maxLeft = nums1[i - 1];
} else {
maxLeft = max(nums1[i - 1], nums2[j - 1]);
}
if ((m + n) % 2 == 1) {
return maxLeft;
}
if (i == m) {
minRight = nums2[j];
} else if (j == n) {
minRight = nums1[i];
} else {
minRight = min(nums1[i], nums2[j]);
}
return (double)(maxLeft + minRight) / 2;
}
}
return 0;
}
``````

### 问题描述：

There are two sorted arrays **nums1 **and **nums2 **of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

``````nums1 = [1, 3]
nums2 = [2]

The median is 2.0
``````

Example 2:

``````nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5
``````

# 5. Longest Palindromic Substring【medium】

### 实现代码：

``````// 5. Longest Palindromic Substring (动态规划)
string longestPalindrome(string s) {
int length = s.size();
if (length == 0) return s;
int resI = 0, resJ = 0;
bool dp[length + 1][length + 1];
for (int i = 0; i <= length; i++)
dp[i][i] = true;
for (int i = 0; i < length; i++) {
if (s[i] == s[i + 1]) {
dp[i][i + 1] = true;
if (resJ - resI < 1) {
resI = i;
resJ = i + 1;
}
} else {
dp[i][i + 1] = false;
}
}
for (int gap = 2; gap < length; gap++) {
for (int i = 0; i + gap < length; i++) {
int j = i + gap;
if (s[i] == s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
if (resJ - resI < j - i) {
resI = i;
resJ = j;
}
} else {
dp[i][j] = false;
}
}
}
return s.substr(resI, resJ - resI + 1);
}
``````

### 问题描述：

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

Example 1:

``````Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
``````

Example 2:

``````Input: "cbbd"
Output: "bb"
``````

# 6. ZigZag Conversion【medium】

### 实现代码：

``````// 6. ZigZag Conversion
string convert(string s, int numRows) {
if (numRows == 1) return s;
string res;
bool shouldIncrease = true;
string strArr[numRows];
int point = 0;
for (char c : s) {
strArr[point] += c;
if (point == numRows - 1) {
shouldIncrease = false;
} else if (point == 0) {
shouldIncrease = true;
}
if (shouldIncrease) {
point++;
} else {
point--;
}
}
for (string str: strArr) {
res += str;
}
return res;
}
``````

### 问题描述：

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
``````

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"
``````

Example 2:

``````Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"

Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I
``````

# 7. Reverse Integer【easy】

### 实现代码：

``````// 7. Reverse Integer
int reverse(int x) {
long result = 0, longX = abs((long)x);
while (longX > 0) {
result = result * 10 + longX % 10;
longX /= 10;
}
result = (x > 0) ? result : -result;
if (result > INT32_MAX || result < INT32_MIN) {
return 0;
} else {
return (int)result;
}
}
``````

### 问题描述：

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

``````Input: 123
Output: 321
``````

Example 2:

``````Input: -123
Output: -321
``````

Example 3:

``````Input: 120
Output: 21
``````

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

# 8. String to Integer (atoi)【medium】

### 解题思路：

(1) 空格：如果为开头空格则continue，否则跳出循环

(2) 正负号：如果为开头正负号则设置isNeg的值，否则跳出循环

(3) 数字：将 isInit 置为true，累加结果

(4) 其他符号：跳出循环

### 实现代码：

``````// 8. String to Integer (atoi)
int myAtoi(string str) {
long result = 0;
bool isInit = false;
bool isNeg = false;
for (char c : str) {
if (c == ' ') {
if (isInit) {
break;
} else {
continue;
}
} else if (c == '-' || c == '+') {
if (!isInit) {
isInit = true;
} else {
break;
}
isNeg = (c == '-');
} else if (c >= 48 && c <= 57) {
isInit = true;
result = result * 10 + (c - 48);
if (result > INT32_MAX) {
return isNeg ? INT32_MIN : INT32_MAX;
}
} else {
break;
}
}
return (int)(isNeg ? -result : result);
}
``````

### 问题描述：

Implement`atoi`which converts a string to an integer.

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.

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.

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.

If no valid conversion could be performed, a zero value is returned.

Note:

• Only the space character`' '`is considered as whitespace character.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. If the numerical value is out of the range of representable values, INT_MAX (2^31 − 1) or INT_MIN (−2^31) is returned.

Example 1:

``````Input: "42"
Output: 42
``````

Example 2:

``````Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.
``````

Example 3:

``````Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
``````

Example 4:

``````Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.
``````

Example 5:

``````Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.
``````

# 9. Palindrome Number【medium】

### 实现代码：

``````// 9. Palindrome Number
int reverse(int x) {
long result = 0, longX = abs((long)x);
while (longX > 0) {
result = result * 10 + longX % 10;
longX /= 10;
}
result = (x > 0) ? result : -result;
if (result > INT32_MAX || result < INT32_MIN) {
return 0;
} else {
return (int)result;
}
}
bool isPalindrome(int x) {
if (x < 0) {
return false;
} else {
return (x == reverse(x));
}
}
``````

### 问题描述：

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

``````Input: 121
Output: true
``````

Example 2:

``````Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
``````

Example 3:

``````Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
``````

Coud you solve it without converting the integer to a string?

# 10. Regular Expression Matching【hard】

### 解题思路：

• 匹配零位：则 dp[i][j] = dp[i][j - 2]
• 匹配一位：则 dp[i][j] = dp[i - 1][j - 2] && (满足最后一位匹配)
• 匹配多位：则一位一位匹配，dp[i][j] = dp[i - 1][j] && (满足最后一位匹配)

### 实现代码：

``````// 10. Regular Expression Matching
bool isMatch(string s, string p) {
int n = s.size();
int m = p.size();
// initial
bool dp[n + 1][m + 1];
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < m + 1; j++) {
dp[i][j] = false;
}
}
// start
dp[0][0] = true;
for (int i = 1; i < n + 1; i++) {
dp[i][0] = false;
}
for (int j = 1; j < m + 1; j++) {
if (j % 2 == 0) {
dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
} else {
dp[0][j] = false;
}
}
// trans
bool compare;
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
if (p[j - 1] != '*') {
dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
} else {
compare = (s[i - 1] == p[j - 2] || p[j - 2] == '.');
dp[i][j] = dp[i][j - 2] || (dp[i - 1][j - 2] && compare) || (dp[i - 1][j] && compare);
}
}
}
return dp[n][m];
}
``````

### 问题描述：

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

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

The matching should cover theentireinput string (not partial).

Note:

• `s`could be empty and contains only lowercase letters`a-z`
• `p`could be empty and contains only lowercase letters`a-z`, and characters like `.` or `*`.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

``````Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
``````

Example 5:

``````Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
``````

+ 关注