Leetcode 001-100
1. Two Sum (Easy)¶
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].
思路
建立一个HashMap，这样O(n)时间可解
c++11中的unordered_map是Hash的实现，这里用unordered_map来搞HashMap
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, vector<int>> dict;
for (int i = 0; i < nums.size(); i ++) dict[nums[i]].push_back(i);
for (int i = 0; i < nums.size(); i ++) {
if (dict.count(target - nums[i])) {
for (auto p : dict[target - nums[i]]) {
if (p != i) return {i, p};
}
}
}
return {};
}
--
2. Add Two Number (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 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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
思路
解法就是两个链表一起扫一遍，可以注意的是进位carriage一定是1，拿上限999+999举个例子就可以发现。
然后用( ? : )的写法，和if(listNode*)的判断可以写起来方便一些。
NULL需要#include \<iostream>
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* list = NULL;
ListNode* tail;
int v = 0;
ListNode* node;
while (1) {
int temp = l1->val + l2->val + v;
v = temp / 10;
temp %= 10;
ListNode* n = new ListNode(temp);
if (list == NULL) {
tail = n;
list = n;
} else {
tail->next = n;
tail = n;
}
l1 = l1->next;
l2 = l2->next;
if (l1 == NULL) { node = l2; break; }
if (l2 == NULL) { node = l1; break; }
}
while (v != 0 || node != NULL) {
int temp;
if (node == NULL) temp = v;
else temp = node->val + v;
v = temp / 10;
temp %= 10;
ListNode* n = new ListNode(temp);
tail->next = n;
tail = n;
if (node != NULL) node = node->next;
}
return list;
}
};
--
3. Longest Substring Without Repeating Characters (Medium)¶
Given a string, find the length of the longest substring without 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 a substring, "pwke" is a subsequence and not a substring.
思路
先扫一遍字符串，知道每个位置的字符上一次出现是在哪里。这里可以用unordered_map实现，但取巧可以直接用256位的vector，然后直接用char转int来访问。
再扫一遍字符串，对每个位置的字符，看前一次重复和之前的重复组左边数的rank哪个更大，然后做减法就是以这个字符为终点的最大不重复子串。
注意¶
- 可以用vector 256位来存储，用char直接访问；
- 以上两遍可以写在一个循环里，刚开始写两次循环，200多ms，改成一次循环，只有20多ms。
int lengthOfLongestSubstring(string s) {
std::vector<int> dict(256, -1);
int res = 0;
int lastRepeat = -1;
for (size_t i = 0; i < s.size(); i ++) {
lastRepeat = (dict[s[i]] > lastRepeat) ? dict[s[i]] : lastRepeat;
dict[s[i]] = i;
res = (i - lastRepeat > res) ? i - lastRepeat : res;
}
return res;
}
--
4. Median of Two Sorted Arrays (Hard)¶
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)).
思路
对于长度为奇数或偶数的数组，中位数都可以统一为(\frac{n+1}{2}+\frac{n+2}{2})/2，那么本题就是求两个数组中第\frac{m+n+1}{2}和第\frac{m+n+2}{2}个数，再除以2即可。
求两个sorted数组的第K个数，可以每次比较两个数组第\frac{k}{2}个数，将较小的\frac{k}{2}个数扔去。
- 需要注意的是如果一个数组长度小于\frac{k}{2}，那么保留这个数组，直接从另一个数组扔，因为第k个数一定在另一个数组\frac{k}{2}后
- 如果一个数组为空，直接返回另一个数组第k个数
- 如果k为1，直接比较两个数组第一个数，不然会扔不了数
编程：INT_MAX的使用
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
return double(findKthNumber(nums1, nums2, (n + m + 1)/2) + findKthNumber(nums1, nums2, (n + m + 2)/2))/2;
}
int findKthNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int i = 0, j = 0;
while (k > 0) {
if (i >= nums1.size()) return nums2[j + k - 1];
if (j >= nums2.size()) return nums1[i + k - 1];
if (k == 1) return (nums1[i] < nums2[j]) ? nums1[i] : nums2[j];
int mid = k / 2;
int mid1 = (i + mid - 1 < nums1.size()) ? nums1[i + mid - 1] : INT_MAX;
int mid2 = (j + mid - 1 < nums2.size()) ? nums2[j + mid - 1] : INT_MAX;
if (mid1 < mid2) i += mid;
else j += mid;
k -= mid;
}
}
5. Longest Palindromic Substring (Medium)¶
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"
DP
P[i][j]为1/0值，表示i-j是不是回文串。
P[i][j] = P[i+1][j-1] && s[i] == s[j]
考虑只有两位时，只需要比较两个数是否相等，需要特殊判断
string longestPalindrome(string s) {
int n = s.length();
string res = "";
int* P = new int[n]();
memset(P, 0, n);
for (int i = n - 1; i >= 0; i --) {
for (int j = n - 1; j >= i; j --) {
P[j] = s[i] == s[j] && (j - i < 3 || P[j - 1]);
if (P[j] && j - i + 1 > res.length()) {
res = s.substr(i, j - i + 1);
}
}
}
return res;
}
8. String to Integer atoi (Medium)¶
将string转int，如果超出int范围则返回INT_MAX或INT_MIN，如果开头有空格跳过，数字不间断
Input: " -42" Output: -42 Input: "4193 with words" Output: 4193 Input: "words and 987" Output: 0
int myAtoi(string str) {
int iter = 0;
for (iter = 0; str[iter] == ' ' && iter < str.size(); iter ++) {}
if (iter == str.size()) return 0;
int sign = 1;
if (str[iter] == '-') {
sign = -1;
iter ++;
} else if (str[iter] == '+')
iter ++;
long long res = 0;
for (; str[iter] >= '0' && str[iter] <= '9'; iter ++) {
res *= 10;
res += (str[iter] - '0');
if (sign * res > INT_MAX) return INT_MAX;
if (sign * res < INT_MIN) return INT_MIN;
}
res *= sign;
return res;
}
10. Regular Expression Matching (Hard)¶
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.
给定一个字符串s和正则表达式p，看s是否符合p
思路
动态规划，记s长度为m，p长度为n，开一个m+1*n+1的二维数组match，match[i][j]表示s的前i位和p的前j位是否吻合
初始化时，match[0][0]=1，而match[1-m][0]=0，因为空的模式串匹配不了任何字符串
然后依次计算match[i][j]，分p[j-1]是不是*
- 不是，看s和p的当前位是否一样(考虑.)，然后与上match[i-1][j-1]即可
- 是，分两种情况，第一是match[i][j-2]，即这里*什么都不匹配，另一种是匹配，同样看s和p的上一位是否一样，再看match[i-1][j]
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
bool** match = new bool* [m+1];
for (int i = 0; i < m + 1; i ++) match[i] = new bool[n+1];
for (int i = 1; i < m + 1; i ++) match[i][0] = 0;
match[0][0] = 1;
for (int i = 0; i < m + 1; i ++) {
for (int j = 1; j < n + 1; j ++) {
if (p[j-1] != '*') match[i][j] = i > 0 && match[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
else match[i][j] = match[i][j-2] || (i > 0 && match[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'));
}
}
return match[m][n];
}
11. Container With Most Water (Medium)¶
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container and n is at least 2.
Example: Input: [1,8,6,2,5,4,8,3,7] Output: 49
即对数组A=\{n_1,n_2,...,n_k\}，max_{i,j \sim [1,k]}(j-i)min(n_j, n_i)
Solution 1¶
暴力求解，O(N^2)，leetcode上可以通过，但肯定不是理想解法
int maxArea(vector<int>& height) {
int result = -1;
for (int i = 0; i < height.size(); i ++) {
for (int j = i + 1; j < height.size(); j ++) {
int temp = min(height[i], height[j]) * (j - i);
if (temp > result) result = temp;
}
}
return result;
}
Solution 2¶
O(N)算法，思路为逐步将数组规模缩小，每次都按数组首尾元素来计算面积，最大面积一定会在这个过程被计算出来
以[1,8,6,2,5,4,8,3,7]为例，选择首尾，面积为1 \times 8，如果接下来保留1，那么最大面积一定小于这个8，所以1不会对更大的面积有贡献，可以从数组中去除
这个解法还是简化这个问题，然后缩小规模来求，应该有这个直觉，有关数组题，考虑端点情况，看能不能减治
int maxArea(vector<int>& height) {
if (height.size() < 2) return 0;
int l = 0, r = height.size() - 1;
int mx = 0;
while (l < r) {
mx = max(mx, min(height[l], height[r]) * (r - l));
if (height[l] < height[r]) {
int temp = height[l];
while (l < r && height[l] <= temp) l ++;
} else {
int temp = height[r];
while (l < r && height[r] <= temp) r --;
}
}
return mx;
}
这个解法没用到的一个思路是，对于左端点来说，如果一个数比它更靠左且更大，这个数一定优于这个数，因此左端点备选范围就是从第一个元素开始，递增到达最大元素的集合，对于上例即[1, 8]，右端点备选集合是从最靠右的最大元素递减达到最右元素的集合，即[8, 7]
12. Integer to Roman (Medium)¶
十进制转罗马数字
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 num范围为[1, 3999]
思路
就是从从1000到1开始除num，结果可能是0-9，对于4和9特判一下，然后大于5的减去5，之后将1对应的罗马数字累加即可
string intToRoman(int num) {
char romans[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
int nums[4] = {1, 10, 100, 1000};
string res = "";
for (int i = 3; i >= 0; i --) {
if (num == 0) return res;
int n = num / nums[i];
num %= nums[i];
if (n == 9) {
res += romans[i*2]; res += romans[i*2+2];
continue;
}
if (n >= 5) {
res += romans[i*2+1]; n -= 5;
}
if (n == 4) {
res += romans[i*2]; res += romans[i*2+1];
}
else
for (int j = n; j > 0; j --) res += romans[i*2];
}
return res;
}
13. Roman to Integer (Easy)¶
罗马数字转十进制
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
注意，1/10/100在 5 10/50 100/500 1000前面时，表示 4 9/40 90/400 900，写的时候判断一下
int romanToInt(string s) {
int nums[100];
int rank[100];
nums['I' - 'A'] = 1; rank['I' - 'A'] = 0;
nums['V' - 'A'] = 5; rank['V' - 'A'] = 1;
nums['X' - 'A'] = 10; rank['X' - 'A'] = 2;
nums['L' - 'A'] = 50; rank['L' - 'A'] = 3;
nums['C' - 'A'] = 100; rank['C' - 'A'] = 4;
nums['D' - 'A'] = 500; rank['D' - 'A'] = 5;
nums['M' - 'A'] = 1000; rank['M' - 'A'] = 6;
int result = 0;
for (int i = 0; i < s.size(); i ++) {
int r = rank[s[i] - 'A'];
if (i < s.size() - 1 && r % 2 == 0) {
int delta = rank[s[i + 1] - 'A'] - r;
if (delta > 0 && delta < 3) {
result += nums[s[i+1]-'A'];
result -= nums[s[i] - 'A'];
i ++;
continue;
}
}
result += nums[s[i] - 'A'];
}
return result;
}
14. Longest Common Prefix (Easy)¶
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 "".
对一些字符串找到最长公共前缀，思路就是拿当前已有最长公共前缀(一开始初始化为第一个字符串)和后来的字符串依次比较，最后所得结果即最长公共前缀。
在求两个字符串的最长公共前缀时，可以用二分的思路来找，即找出从左到右第一个不相等的位，开始l初始化为0，然后r初始化为两个字符串较短者长度，看str[l, mid]是否一样，如果一样，l=mid+1，继续找，如果不一样，r=mid-1，再找。
注意退出条件:
- 两个字符串l位置字符不一样，此时l前字符一定都一样
- l大于r，即l和r在上一个循环中相等，在这个循环中，要比较的部分已经为空
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) return "";
string res = strs[0];
for (int i = 1; i < strs.size(); i ++) {
int r = (strs[i].size() > res.size()) ? res.size()-1 : strs[i].size()-1;
// Binary search
int l = 0;
while (r >= l) {
if (res[l] != strs[i][l]) break;
int mid = (r + l) / 2;
if (res.substr(l, mid-l+1) == strs[i].substr(l, mid-l+1)) l = mid + 1;
else r = mid - 1;
}
res = res.substr(0, l);
}
return res;
}
这里可以改进的是，先找出最短的字符串，然后对这个字符串二分查找l位，时间复杂度不变，但常数会降低，不过leetcode运行结果也是4ms
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) return "";
string shortestStr = strs[0];
for (int i = 1; i < strs.size(); i ++)
shortestStr = (strs[i].size() > shortestStr.size()) ? strs[i] : shortestStr;
int l = 0, r = shortestStr.size() - 1;
while (r >= l) {
int mid = (r + l) / 2;
bool commonPrefix = true;
string prefix = shortestStr.substr(0, mid + 1);
for (int i = 0; i < strs.size(); i ++)
if (strs[i].substr(0, mid + 1) != prefix) {
commonPrefix = false;
break;
}
if (commonPrefix) l = mid + 1;
else r = mid - 1;
}
return shortestStr.substr(0, l);
}
15. 3 Sum (medium)¶
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Solution 1
先对vector排序，然后用hashmap来记录每个数存在不存在，然后O(n^2)遍历vector，判断第三个数字在不在unordered_map中
注意：
- 因为要去重，所以i和j循环时跳过重复值，且k要不小于nums[j]
- unordered_map里面存的应该是次数，因为有可能一个数出现多次
vector<vector<int> > threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
unordered_map<int, int> map;
vector<vector<int> > result;
for (int i = 0; i < nums.size(); i ++) {
if (map.find(nums[i]) == map.end()) map[nums[i]] = 0;
map[nums[i]] ++;
}
int prev_i, prev_j;
for (int i = 0; i < nums.size(); i ++) {
if (i > 0 && nums[i] == prev_i) continue;
for (int j = i + 1; j < nums.size(); j ++) {
if (j > i + 1 && nums[j] == prev_j) continue;
int k = 0 - nums[i] - nums[j];
if (k < nums[j]) continue;
int num = 1;
if (k == nums[i]) num ++;
if (k == nums[j]) num ++;
if (map.find(k) != map.end() && map.find(k)->second >= num) {
vector<int> v;
v.push_back(nums[i]);
v.push_back(nums[j]);
v.push_back(k);
result.push_back(v);
}
prev_j = nums[j];
}
prev_i = nums[i];
}
return result;
}
Solution 2
先对vector进行排序，然后从左到右去重来取出nums[i]，那么就变成从i+1开始、target为-nums[i]的2 Sum问题。
2 Sum问题可以从l和r开始，判断当前和是否大于target，如果大于，说明最右端已经用不到，左移右指针；如果小于，说明左端已经用不到，右移左指针。
这样复杂度仍为O(n^2)，但没有unordered_map的初始化过程，所以时间会短一些。leetcode上solution 1时间为120ms，solution 2时间为60ms
vector<vector<int> > threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int> > results;
int prev_i = 0;
for (int i = 0; i < nums.size(); i ++) {
if (i > 0 && nums[i] == prev_i) continue;
int target = 0 - nums[i];
prev_i = nums[i];
int l = i + 1, r = nums.size() - 1;
vector<int> result;
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == target) {
int tempArray[3] = {nums[i], nums[l], nums[r]};
vector<int> result(tempArray, tempArray+3);
results.push_back(result);
while (nums[l+1] == nums[l]) l ++; l++;
while (nums[r-1] == nums[r]) r--; r--;
} else if (sum < target) {
while (nums[l+1] == nums[l]) l ++; l++;
} else {
while (nums[r-1] == nums[r]) r--; r--;
}
}
}
return results;
}
16. 3 Sum Closest (Medium)¶
Given an array nums of n integers 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:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
对于一个数组，找出三个数，和与给定target相差最小
思路: 预先给vector里每个数乘3，然后减去target，再找三个数加起来离0最近的值，代码和3 Sum一样，而且在遇到等于target的时候可以直接返回，同样是O(n^2)复杂度
int threeSumClosest(vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); i ++) nums[i] = 3 * nums[i] - target;
sort(nums.begin(), nums.end());
int prev_i = 0;
int delta = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.size(); i ++) {
if (i > 0 && prev_i == nums[i]) continue;
int l = i + 1, r = nums.size() - 1;
// nums[i] + nums[l] + nums[r] -> 0
while (r > l) {
int sum = nums[l] + nums[r] + nums[i];
if (sum == 0) return target;
else if (sum > 0) {
delta = (delta*delta > sum*sum) ? sum : delta;
while (nums[r-1] == nums[r]) r --; r --;
} else if (sum < 0) {
delta = (delta*delta > sum*sum) ? sum : delta;
while (nums[l+1] == nums[l]) l ++; l ++;
}
}
}
return delta / 3 + target;
}
17. Letter Combinations of a Phone Number (Medium)¶
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
就是9宫格打字，给出对应全排列
2 - abc
3 - def
4 - ghi
5 - jkl
6 - mno
7 - pqrs
8 - tuv
9 - wxyz
思路: 递增进位法，维持一个中介数，每一位表示这个数字的第几个字母，然后对这个中介数累加，并逐一输出
vector<string> letterCombinations(string digits) {
int n = digits.size();
vector<string> result;
if (n == 0) return result;
char letter[8] = {'a', 'd', 'g', 'j', 'm', 'p', 't', 'w'};
int radix[8] = {3, 3, 3, 3, 3, 4, 3, 4};
int* nums = new int[digits.size()]();
string str = "";
int sum = 1;
for (int i = 0; i < digits.size(); i ++) {
nums[i] = digits[i] - '2';
str += letter[nums[i]];
sum *= radix[nums[i]];
}
result.push_back(str);
for (int i = 0; i < sum - 1; i ++) {
str[n-1] ++;
for (int j = n-1; j >= 0; j --) {
int num = str[j] - letter[nums[j]];
if (num >= radix[nums[j]]) {
str[j] = letter[nums[j]];
str[j-1] += 1;
}
else break;
}
result.push_back(str);
}
return result;
}
18. 4 Sum (Medium)¶
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
思路
和3sum一样，循环确定前两个数，然后用2sum的办法确定后两个数，需要在增减l和r的时候不能越界
vector<vector<int> > fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int> > results;
if (nums.size() < 4) return results;
for (int first = 0; first < nums.size() - 3; first ++) {
if (first > 0 && nums[first] == nums[first - 1]) continue;
for (int second = first + 1; second < nums.size() - 2; second ++) {
if (second > first + 1 && nums[second] == nums[second - 1]) continue;
int t = target - nums[first] - nums[second];
int l = second + 1, r = nums.size() - 1;
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == t) {
results.push_back({nums[first], nums[second], nums[l], nums[r]});
while (l < nums.size() - 1 && nums[l + 1] == nums[l]) l ++; l ++;
while (r > 0 && nums[r - 1] == nums[r]) r --; r --;
} else if (sum < t) {
while (l < nums.size() - 1 && nums[l + 1] == nums[l]) l ++; l++;
} else {
while (r > 0 && nums[r - 1] == nums[r]) r --; r --;
}
}
}
}
return results;
}
19. Remove Nth Node From End of List (Medium)¶
Given a linked list, remove the n-th node from the end of list and return its head.
Example:
给定n一定合法Given linked list: 1->2->3->4->5, and n = 2 After removing the second node from the end, the linked list becomes 1->2->3->5.
思路
双指针，前一个指针到达链尾时，后一个指针指在node处，再执行删除操作即可
先将第一个指针向后移动n位，然后同时移动两个指针，并记录后一个指针的前一个位置，知道第一个指针指向空
如果后一个指针的前一个指针为空，那么直接将头指针指到第二个指针下一位即可，否则需要修改第二个指针的前一位，来跳过第二个指针
之后delete已经删除的节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (n == 0) return head;
ListNode *first = head, *second = head, *prev = nullptr;
for (int i = 0; i < n; i++) first = first->next;
while (first != nullptr) {
prev = second;
second = second->next;
first = first->next;
}
if (prev == nullptr) head = second->next;
else prev->next = second->next;
delete second;
return head;
}
20. Valid Parentheses (Easy)¶
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Note that an empty string is also considered valid.
匹配括号
思路
维护一个栈即可
bool isValid(string s) {
vector<char> v;
for (int i = 0; i < s.size(); i ++) {
char c = s[i];
if (c == '[' || c == '(' || c == '{') v.push_back(c);
else if (v.size() > 0 && c - v[v.size() - 1] <= 2 && c - v[v.size() - 1] > 0)
v.pop_back();
else return false;
}
return v.size() == 0;
}
21. Merge Two Sorted Lists (Easy)¶
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
思路
逐个比较，加入新链即可
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
ListNode* head = (l1->val < l2->val) ? l1 : l2;
if (l1->val < l2->val) l1 = l1->next;
else l2 = l2->next;
ListNode* tail = head;
while (l1 != NULL && l2 != NULL) {
tail->next = (l1->val < l2->val) ? l1 : l2;
tail = tail->next;
if (l1->val < l2->val) l1 = l1->next;
else l2 = l2->next;
}
if (l1 == NULL) tail->next = l2;
else if (l2 == NULL) tail->next = l1;
return head;
}
22. Generate Parentheses (Medium)¶
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
思路
解法比较简单，就是写一个递归，保证任意前缀中左括号数量都大于右括号
vector<string> generateParenthesis(int n) {
vector<string> res;
recursion(n, n, "", res);
return res;
}
void recursion(int left, int right, string s, vector<string>& res) {
if (left == 0 && right == 0) {
res.push_back(s);
return;
}
if (left < right) recursion(left, right - 1, s + ')', res);
if (left > 0) recursion(left - 1, right, s + '(', res);
}
一个典型的卡特兰数问题。
23. Merge k Sorted Lists (Hard)¶
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
思路一
利用priority_queue，重定义一下compare函数，然后每次取最小的一个node，建堆复杂度为O(N)，之后每次删除复杂度为O(logN)，总复杂度为O(NlogN)
ListNode* mergeKLists0(vector<ListNode*>& lists) {
auto comp = [](ListNode* a, ListNode* b) -> bool { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> pq(comp);
for (auto v : lists)
while (v != NULL) {
pq.push(v);
v = v->next;
}
if (pq.size() == 0) return NULL;
ListNode* head = pq.top();
ListNode* tail = head;
pq.pop();
while (!pq.empty()) {
tail->next = pq.top();
tail = pq.top();
pq.pop();
}
tail->next = NULL;
return head;
}
思路二
分治来做，每次将lists两两合并，规模缩小一半，一共执行logN次，每次都会把所有元素比较一遍，时间复杂度也是O(NlogN)
ListNode* merge(ListNode* a, ListNode* b) {
if (a == nullptr) return b;
if (b == nullptr) return a;
ListNode* head = nullptr, *tail = nullptr;
while (a != nullptr && b != nullptr) {
ListNode* temp = (a->val < b->val) ? a : b;
if (head == nullptr) {
head = temp;
tail = head;
} else {
tail->next = temp;
tail = temp;
}
if (a->val < b->val) a = a->next;
else b = b->next;
}
if (a == nullptr) tail->next = b;
else tail ->next = a;
return head;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size() == 0) return nullptr;
while (lists.size() > 1) {
int i, j;
for (i = 0, j = lists.size() - 1; j > i; i ++, j --)
lists[i] = merge(lists[i], lists[j]);
lists.resize((i == j) ? i + 1 : i);
}
return lists[0];
}
24. Swap Nodes in Pairs (Medium)¶
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Given 1->2->3->4, you should return the list as 2->1->4->3.
思路
挨个交换即可，注意用prev来保存前一个node
ListNode* swapPairs(ListNode* head) {
if (head == NULL) return NULL;
ListNode* result = (head->next == NULL) ? head : head->next;
ListNode* prev = NULL;
while (head != NULL && head->next != NULL) {
ListNode *n0 = head, *n1 = head->next;
n0->next = n1->next;
n1->next = n0;
head = n0->next;
if (prev != NULL) prev->next = n1;
prev = n0;
}
return result;
}
25. Reverse Nodes in k-Group (Hard)¶
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
思路Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5
思路也简单，就是直接交换，难度在于写法。
需要注意的就是reverse这一部分，prev应该从nullptr开始，因为要把末尾node的next设为nullptr
reverse的写法就是维持now prev next三个变量，每次将now->next改为prev，然后把now赋成next继续
ListNode* reverse(ListNode* head) {
if (head == nullptr) return head;
ListNode *prev = nullptr, *cur = head, *next = nullptr;
while(cur != nullptr) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == NULL || k == 1) return head;
ListNode* prev = nullptr, * first = head, *second = head;
while (second != nullptr) {
int length = 1;
while (second->next != nullptr && length < k) {
second = second->next;
length++;
}
if (length < k) break;
ListNode* next = second->next;
second->next = nullptr;
ListNode* temp = reverse(first);
if (first == head) head = temp;
if (prev != nullptr) prev->next = temp;
first->next = next;
prev = first;
first = second = next;
}
return head;
}
26. Remove Duplicates from Sorted Array (Easy)¶
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
对sorted array进行去重，最后vector前n位就是所有unqiue元素，并返回不重复元素个数
思路
直接求解就行，需要注意的是在while循环去除重复元素时要保证i没有超过vector的size
int removeDuplicates(vector<int>& nums) {
if (nums.size() == 0) return 0;
int result = 1, prev = nums[0];
for (int i = 1; i < nums.size(); i ++) {
while (i < nums.size() && nums[i] == prev) i ++;
if (i < nums.size()) {
nums[result ++] = nums[i];
prev = nums[i];
}
}
return result;
}
27. Remove Element (Easy)¶
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
在一个vector中去除某个元素，并返回剩余元素个数
思路
扫描一遍即可
int removeElement(vector<int>& nums, int val) {
if (nums.size() == 0) return 0;
int result = nums.size();
int ptr = 0;
for (int i = 0; i < nums.size(); i ++) {
if (nums[i] == val) result --;
else nums[ptr ++] = nums[i];
}
return result;
}
28. Implement strStr() (Easy)¶
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
思路
int* buildNext(const string& p) {
int n = p.size();
int* next = new int[n];
next[0] = -1;
int t = -1, j = 0;
while (j < n - 1) {
if (t < 0 || p[t] == p[j]) {
t ++; j ++;
next[j] = (p[t] == p[j]) ? next[t] : t;
}
else t = next[t];
}
return next;
}
int strStr(string haystack, string needle) {
if (needle == "") return 0;
if (haystack == "") return -1;
int m = haystack.size(), i = 0;
int n = needle.size(), j = 0;
int* next = buildNext(needle);
while (i < m && j < n) {
if (j < 0 || haystack[i] == needle[j]) {
i ++; j ++;
}
else j = next[j];
}
delete[] next;
if (i == m && j < n) return -1;
return i - j;
}
29. Divide Two Integers (Medium)¶
两个数相除，如果溢出则返回INT_MAX
思路
二分运算，二倍增加到最接近divident，然后减去，再重复，需要注意对一些特殊情况的判断
int divide(int divident, int divisor) {
if (divident == INT_MIN && divisor == -1) return INT_MAX;
if (divisor == -1) return 0 - divident;
if (divisor == 1) return divident;
int sign = ((divident > 0) ^ (divisor > 0)) ? -1 : 1;
int result = 0;
long long d = labs(divident);
long long s = labs(divisor);
while (d >= s) {
long long temp = s;
int num = 1;
while (d >= (temp << 1)) {
temp <<= 1;
num <<= 1;
}
d -= temp;
result += num;
}
return (sign == 1) ? result : 0 - result;
}
¶
int divide(int divident, int divisor) {
if (divident == INT_MIN && divisor == -1) return INT_MAX;
if (divisor == -1) return 0 - divident;
if (divisor == 1) return divident;
int sign = ((divident > 0) ^ (divisor > 0)) ? -1 : 1;
int result = 0;
long long d = labs(divident);
long long s = labs(divisor);
while (d >= s) {
long long temp = s;
int num = 1;
while (d >= (temp << 1)) {
temp <<= 1;
num <<= 1;
}
d -= temp;
result += num;
}
return (sign == 1) ? result : 0 - result;
}
30. Substring with Concatenation of All Words (Hard)¶
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively. The output order does not matter, returning [9,0] is fine too.
思路
用hashmap来做，一个hashmap存words表，格式是word-出现次数；然后扫描时再开一个hashmap，比较两个hashmap的次数是否一样即可，这样从0到s.size() - words.size() - length扫一遍就可以得到答案。
但有更快的方法，做法是不再一个一个进位，而是起始位置从0到length-1遍历，之后以length为单位来进，因为在扫描过程中会有这几种情况
- 失败，有不属于words的单词，这时前面扫描过的部分可以全部丢掉，因为这部分肯定匹配不到
- 失败，属于words的单词次数超了，这时就逐次进位length，直到次数等于words里的次数为止
- 成功，这时进位length，开始下一次扫描
前两种进位方法都可以减少很多不必要的扫描，因此会快很多 (228ms->24ms)
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> result;
if (words.size() == 0) return result;
int length = words[0].size();
if (s.size() < words.size() * length) return result;
unordered_map<string, int> wordMap;
for (auto word : words) wordMap[word] ++;
for (int i = 0; i < length; i ++) {
int start = i;
while (start <= s.size() - words.size() * length) {
unordered_map<string, int> map;
int count = 0;
while (count < words.size()) {
string substr = s.substr(start + count * length, length);
if (wordMap.count(substr)) {
map[substr] ++;
count ++;
while (map[substr] > wordMap[substr]) {
string step = s.substr(start, length);
map[step] --;
count --;
start += length;
}
} else {
start = start + count * length + length;
count = 0;
break;
}
}
if (count == words.size()) {
result.push_back(start);
start += length;
}
}
}
return result;
}
31. Next Permutation (Medium)¶
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
字典序法
即字典序法找下一个排列
- 从右到左找第一个降序对，如123，第一个降序对是23
- 将降序对中较小的数与后面刚好比它大的那个数互换，就是2和3互换
- 把后缀升序排列
注意最后一行，对于最大字典序的vector，要单独变成最小串
inline void swap(int& x, int& y) {
int t = x;
x = y;
y = t;
}
void nextPermutation(vector<int>& nums) {
int length = nums.size();
int i = length - 2;
int j;
while (i >= 0) {
if (nums[i] < nums[i + 1]) {
for (j = length - 1; j >= i + 1; j --)
if (nums[j] > nums[i]) break;
swap(nums[i], nums[j]);
i ++;
for (j = length - 1; j > i; j --, i ++)
swap(nums[i], nums[j]);
return;
}
else i --;
}
for (i = 0, j = length - 1; j > i; j --, i ++) swap(nums[i], nums[j]);
}
32. Longest Valid Parantheses (Hard)¶
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"
思路
合法的括号对就是能对一个stack完成入栈出栈操作最后使栈为空，左括号入栈、右括号出栈
所以用stack来记录左括号位置，遇见右括号出栈，需要注意的是当出栈后栈为空时，为得到括号对长度应该记录一下开始位置
int longestValidParentheses(string s) {
stack<int> v;
int result = 0;
int start = -1;
for (int i = 0; i < s.size(); i ++) {
if (s[i] == ')') {
if (!v.empty()) {
v.pop();
int length = v.empty() ? i - start : i - v.top();
result = (length > result) ? length : result;
}
else start = i;
}
else v.push(i);
}
return result;
}
33. Search in Rotated Sorted Array (Medium)¶
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
思路
直接二分求解，分为高低区两部分，先判断高低区，然后再判断是增加l还是r
int search(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] <= nums[nums.size() - 1]) {
if (target > nums[mid] && target <= nums[nums.size() - 1]) l = mid + 1;
else r = mid - 1;
} else if (nums[mid] > nums[nums.size() - 1]) {
if (target < nums[mid] && target >= nums[0]) r = mid - 1;
else l = mid + 1;
}
}
return -1;
}
34. Find First and Last Position of Element in Sorted Array (Medium)¶
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
思路
用LowerBound和UpperBound算出两个界即可，判断一下该元素是否存在
vector<int> searchRange(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
vector<int> result;
while (l <= r) {
int m = (l + r) / 2;
if (target <= nums[m]) r = m - 1;
else l = m + 1;
}
if (l < nums.size() && nums[l] == target) result.push_back(l);
else return {-1, -1};
l = 0, r = nums.size() - 1;
while (l <= r) {
int m = (l + r) / 2;
if (target >= nums[m]) l = m + 1;
else r = m - 1;
}
result.push_back(r);
return result;
}
35. Search Insert Position (Easy)¶
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Input: [1,3,5,6], 5 Output: 2
思路
计算元素插入位置，直接使用LowerBound即可
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = (l + r) / 2;
if (target <= nums[m]) r = m - 1;
else l = m + 1;
}
return l;
}
36. Valid Sudoku (Medium)¶
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
思路
每行，每列，每个盒子都维护一个bool数组，判断是否重复即可
bool isValidSudoku(vector<vector<char> >& board) {
bool rows[9][9];
bool cols[9][9];
bool boxes[9][9];
for (int i = 0; i < 9; i ++)
for (int j = 0; j < 9; j ++) {
rows[i][j] = 0;
cols[i][j] = 0;
boxes[i][j] = 0;
}
bool result = 1;
for (int i = 0; i < 9; i ++)
for (int j = 0; j < board[i].size(); j ++) {
char c = board[i][j];
if (c == '.') continue;
if (rows[i][c - '1']) return 0; rows[i][c - '1'] = 1;
if (cols[j][c - '1']) return 0; cols[j][c - '1'] = 1;
if (boxes[(i/3)*3 + j/3][c - '1']) return 0; boxes[(i/3)*3 + j/3][c - '1'] = 1;
}
return 1;
}
37. Sudoku Solver (Hard)¶
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
思路
就是深搜式的回溯，选一个点就递归下一次，失败就返回false然后重置，应该是很典型的回溯
bool rows[9][9];
bool cols[9][9];
bool boxes[9][9];
bool fill(vector<vector<char> >& board, int i, int j) {
while (i < 9 && j < 9 && board[i][j] != '.') {
j ++;
if (j == 9) { i ++; j = 0; }
}
if (i == 9) return true;
for (int n = 0; n < 9; n ++) {
if (rows[i][n] || cols[j][n] || boxes[(i/3)*3 + j/3][n]) continue;
board[i][j] = ('1' + n);
rows[i][n] = cols[j][n] = boxes[(i/3)*3 + j/3][n] = 1;
if (fill(board, i, j)) return true;
board[i][j] = '.';
rows[i][n] = cols[j][n] = boxes[(i/3)*3 + j/3][n] = 0;
}
return false;
}
void solveSudoku(vector<vector<char> >& board) {
for(int i = 0; i < 9; i ++)
for (int j = 0; j < 9; j ++) {
char c = board[i][j];
if (c == '.') continue;
else rows[i][c-'1'] = cols[j][c-'1'] = boxes[(i/3)*3 + j/3][c-'1'] = 1;
}
fill(board, 0, 0);
}
38. Count and Say (Easy)¶
The count-and-say sequence is the sequence of integers with the first five terms as following:
1. 1 2. 11 3. 21 4. 1211 5. 111221
思路
从最开始数即可，c++11中引入了std::to_string()，可以直接使用
string countAndSay(int n) {
string res = "1";
for (int i = 2; i <= n; i ++) {
string newString = "";
int times = 1, rank = 1;
char prev = res[0];
while (1) {
if (rank < res.size() && res[rank] == prev) times ++;
else {
newString += to_string(times);
newString += prev;
if (rank >= res.size()) break;
prev = res[rank];
times = 1;
}
rank ++;
}
res = newString;
}
return res;
}
39. Combination Sum (Medium)¶
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
思路
回溯，逐步分割，和37题类似。
这种枚举类可以解决的题目，都可以尝试拿回溯来做。
void search(int begin, vector<vector<int> >& results, vector<int>& factors, vector<int> candidates, int target) {
for (int i = begin; i < candidates.size(); i ++) {
if (candidates[i] > target) break;
factors.push_back(candidates[i]);
if (target == candidates[i]) results.push_back(factors);
else search(i, results, factors, candidates, target - candidates[i]);
factors.pop_back();
}
}
vector<vector<int> > combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int> > results;
vector<int> factors;
search(0, results, factors, candidates, target);
return results;
}
40. Combination Sum II (Medium)¶
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
思路
和39基本类似，区别在于要去除重复元素，所以改两处
- search时传i+1，即下次递归时不能使用之前已经用过的元素
- 在循环处要跳过与本次递归中已经使用过元素相同的数，这里不太好想到，但如果不加下面这行，上例结果会变成
[[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]]，因为两次1开始的循环对后面来说是一样的。即这时得到的结果在之前一定已经出现过了
这里还挺难注意到的，要多思考
if (i > begin && candidates[i] == candidates[i-1]) continue;
void search(int begin, vector<vector<int> >& results, vector<int>& factors, vector<int> candidates, int target) {
for (int i = begin; i < candidates.size(); i ++) {
if (i > begin && candidates[i] == candidates[i-1]) continue;
if (candidates[i] > target) break;
factors.push_back(candidates[i]);
if (target == candidates[i]) results.push_back(factors);
else search(i + 1, results, factors, candidates, target - candidates[i]);
factors.pop_back();
}
}
vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int> > results;
vector<int> factors;
search(0, results, factors, candidates, target);
return results;
}
41. First Missing Positive (Hard)¶
Given an unsorted integer array, find the smallest missing positive integer.
Example 1: Input: [1,2,0] Output: 3
思路
解法其实很简单，这里要明白的是将一个数和它位置上的数交换不会影响到已经排列好的数，而且交换次数最多为n次，所以时间复杂度还是O(N)
从左到右扫描，遇见在nums.size()范围内的正整数，交换到其位置上即可
int firstMissingPositive(vector<int>& nums) {
int i = 0;
while (i < nums.size()) {
if (nums[i] > 0 && nums[i] <= nums.size() && nums[nums[i]-1] != nums[i])
swap(nums[i], nums[nums[i]-1]);
else i ++;
}
for (int i = 0; i < nums.size(); i ++)
if (nums[i] != i + 1) return i + 1;
return nums.size() + 1;
}
42. Trapping Raining Water (Hard)¶
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
思路
这里比较关键的是要明白一个柱上存水多少，取决于左边最高柱和右边最高柱的较小值，因此扫描两遍，确定每个位置左边最高柱和右边最高柱大小，然后累加每个柱上水量即可
注意要判断一下水量算出来是不是负数
int trap(vector<int>& height) {
vector<int> dp(height.size(), 0);
int mx = -1, result = 0;
for (int i = 0; i < height.size(); i ++) {
dp[i] = mx;
mx = (height[i] > mx) ? height[i] : mx;
}
mx = -1;
for (int i = height.size() - 1; i >= 0; i --) {
result += (min(dp[i], mx) - height[i] < 0) ? 0 : min(dp[i], mx) - height[i];
mx = (height[i] > mx) ? height[i] : mx;
}
return result;
}
43. Multiply Strings (Medium)¶
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
思路
两个数乘积位数一定不超过两个数之和，拿全是9的数想一下就知道
那么可以先用vector存每个位的乘积，然后再扫一遍进行进位，得到答案
善用find_first_not_of(char ch)函数
string multiply(string num1, string num2) {
vector<int> result(num1.size() + num2.size(), 0);
for (int i = 0; i < num1.size(); i ++) {
for (int j = 0; j < num2.size(); j ++) {
int n1 = num1[num1.size() - 1 - i] - '0';
int n2 = num2[num2.size() - 1 - j] - '0';
result[i + j] += n1 * n2;
}
}
string res = "";
int carry = 0;
for (int i = 0; i < result.size(); i ++) {
result[i] += carry;
carry = result[i] / 10;
char c = '0' + result[i] % 10;
res = c + res;
}
return (res.find_first_not_of('0') != string::npos) ? res.substr(res.find_first_not_of('0')) : "0";
}
44. Wildcard Matching (Hard)¶
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).
动态规划
和10. Regular Expression Matching一样的思路，改一下转移条件
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
bool** match = new bool* [m+1];
for (int i = 0; i < m + 1; i ++) match[i] = new bool[n+1]();
match[0][0] = 1;
for (int i = 0; i < m + 1; i ++) {
for (int j = 1; j < n + 1; j ++) {
if (p[j - 1] == '?') match[i][j] = i > 0 && match[i-1][j-1];
else if (p[j - 1] == '*') {
for (int k = 0; k <= i; k ++)
if (match[k][j-1]) {
match[i][j] = 1;
break;
}
}
else match[i][j] = (i > 0) && (s[i-1] == p[j-1]) && (match[i-1][j-1]);
}
}
return match[m][n];
}
线性时间
时间复杂度更低，用两个指针分别指向s和p，然后移动，关键在于遇到*时，记录位置，然后一开始默认匹配空串，继续向后匹配，失败后将匹配的串增加一位，直到最后
需要注意的是对结束条件的判断
bool isMatch(string s, string p) {
int i = 0, j = 0, iStarPosition = -1, jStarPosition = -1;
while (i < s.size()) {
if (s[i] == p[j] || p[j] == '?') {
i ++; j ++;
} else if (p[j] == '*') {
while (j < p.size() && p[j] == '*') j++;
if (j == p.size()) return true;
iStarPosition = i;
jStarPosition = j;
} else {
if (iStarPosition >= 0) {
i = ++iStarPosition;
j = jStarPosition;
}
else return false;
}
}
while (j < p.size() && p[j] == '*') j ++;
return j == p.size();
}
45. Jump Game II (Hard)¶
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
思路
这里其实扫描一遍即可得到答案，思路如下：找到一次跳跃中可以到达的最远边缘，这个边缘之内的点都可以在一次跳跃内到达，超过这个边缘的点则需要多一次跳跃，如此累加，直到边缘大于等于nums.size()-1为止，也就是i最远到达nums.size()-2
思想算是贪心，但其实这个思路应该要想到
int jump(vector<int>& nums) {
int edge = 0, steps = 0, nextEdge = 0;
for (int i = 0; i < nums.size() - 1; i ++) {
nextEdge = max(nextEdge, nums[i] + i);
if (i == edge) {
steps ++;
edge = nextEdge;
}
}
return steps;
}
46. Permutations (Medium)¶
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
从右向左找第一个比前一位大的数，即 mobile integer，然后把这个数和后缀中比它稍大的数换，之后把后缀最小化，即翻转。
需要注意的是第一个序列需要是从小到大排列，所以先用sort(vector.begin(), vector.end())进行排序
inline void swap(int& x, int& y) {
int t = x;
x = y;
y = t;
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
res.push_back(nums);
int length = nums.size();
int i = length - 2;
int j;
while (i >= 0) {
if (nums[i] < nums[i + 1]) {
for (j = length - 1; j >= i + 1; j --)
if (nums[j] > nums[i]) break;
swap(nums[i], nums[j]);
i ++;
for (j = length - 1; j > i; j --, i ++)
swap(nums[i], nums[j]);
res.push_back(nums);
i = length - 2;
} else
i --;
}
return res;
}
47. Permutations II (Medium)¶
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
字典序法
和46题完全一样，字典序法对于重复字符仍可以全排列
48. Rotate Image (Medium)¶
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
思路
从外层往里，一层层旋转即可
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n/2; i ++) {
for (int j = i; j < n-i-1; j ++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n-1-j][i];
matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
matrix[j][n-1-i] = temp;
}
}
}
49. Group Anagrams (Medium)¶
Given an array of strings, group anagrams together.
Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
思路
对每个string排序，然后用hashmap记录即可
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string> > results;
unordered_map<string, int> map;
int rank = 0;
for (auto str : strs) {
string s = str;
sort(s.begin(), s.end());
if (map.find(s) == map.end()) {
results.push_back({});
map[s] = rank ++;
}
results[map[s]].push_back(str);
}
return results;
}
50. Pow(x, n) (Medium)¶
Implement pow(x, n), which calculates x raised to the power n (x^n).
思路
将n可以拆分成n=2^a+2^b+...+2^c，所以从最初x开始，每次将x变为x^2，然后看n该位是不是1，来决定是否乘在结果上
double myPow(double x, int n) {
long long longN = labs(n);
double result = 1;
while (longN) {
if (longN & 1) result *= x;
longN >>= 1;
x *= x;
}
return n < 0 ? 1/result : result;
}
51. N-Queens (Hard)¶
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
思路
回溯法，注意斜线上也可以互相攻击，所以两个方向上都要去重
void search(vector<vector<string> >& results, vector<string>& board, int step, bool* cols, bool* xie0, bool* xie1, int n) {
for (int i = 0; i < n; i ++) {
if (cols[i] || xie0[step+n-1-i] || xie1[step+i]) continue;
board[step][i] = 'Q';
cols[i] = xie0[step+n-1-i] = xie1[step+i] = 1;
if (step == n - 1) results.push_back(board);
else search(results, board, step + 1, cols, xie0, xie1, n);
board[step][i] = '.';
cols[i] = xie0[step+n-1-i] = xie1[step+i] = 0;
}
}
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> > results;
vector<string> board;
string s(n, '.');
for (int i = 0; i < n; i ++) board.push_back(s);
bool *cols = new bool[n](), *xie0 = new bool[2*n-1](), *xie1 = new bool[2*n-1]();
search(results, board, 0, cols, xie0, xie1, n);
return results;
}
52. N-Queens II (Hard)¶
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
返回N皇后问题的答案个数
思路
与上题一样代码，最后返回results.size()即可，时间为8ms
leetcode上4ms的解法，是拿long long来做bitmap，记录cols和xie0/xie1，只是技巧上的提升
53. Maximum Subarray (Easy)¶
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
思路
动态规划，第i位表示以该位结尾，所得到的subarray最大和，那么
dp[i] = max(nums[i], nums[i] + dp[i-1])
扫描过程中记录最大值即可
int maxSubArray(vector<int>& nums) {
int mx = nums[0], prev = nums[0];
for (int i = 1; i < nums.size(); i ++) {
if (prev > 0) prev += nums[i];
else prev = nums[i];
mx = max(mx, prev);
}
return mx;
}
54. Spiral Matrix (Medium)¶
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5]
思路
逐层向里循环打印即可，需要注意的是判断一下矩阵是否只有一行/一列，即加上m-i-1>i和i<n-1-i的判断
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> result;
int m = matrix.size(), n = (matrix.size()) ? matrix[0].size() : 0;
for (int i = 0; i < (min(m, n)+1)/2; i ++) {
for (int c = i; c < n-i; c ++) result.push_back(matrix[i][c]);
for (int r = i+1; r < m-i; r ++) result.push_back(matrix[r][n-1-i]);
for (int c = n-2-i; c >= i && m-i-1>i; c --) result.push_back(matrix[m-i-1][c]);
for (int r = m-2-i; r >= i+1 && i<n-1-i; r --) result.push_back(matrix[r][i]);
}
return result;
}
55. Jump Game (Medium)¶
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
思路
和45. Jump Game II一样的思路，最后比较edge是否到达了末尾即可
bool canJump(vector<int>& nums) {
int edge = 0, nextEdge = 0;
for (int i = 0; i < nums.size() - 1; i ++) {
nextEdge = max(nextEdge, nums[i] + i);
if (i == edge) edge = nextEdge;
if (i > edge) break;
}
return edge >= nums.size() - 1;
}
56. Merge Intervals (Medium)¶
思路
首先对interval以start进行排序，然后扫描一遍，如果之前end大于等于现在的start，则更新end，继续扫描；小于现在的start，把之前的独立出来
注意这里用c++11的auto函数来完成排序
vector<Interval> merge(vector<Interval>& intervals) {
auto comp = [](Interval a, Interval b) -> bool { return a.start < b.start; };
sort(intervals.begin(), intervals.end(), comp);
int ptr = 0, prevEnd = (intervals.size() > 0) ? intervals[0].end : 0;
for (int i = 1; i < intervals.size(); i ++) {
if (prevEnd >= intervals[i].start) prevEnd = max(prevEnd, intervals[i].end);
else {
intervals[ptr ++].end = prevEnd;
intervals[ptr].start = intervals[i].start;
prevEnd = intervals[i].end;
}
}
if (intervals.size()) intervals[ptr ++].end = prevEnd;
intervals.resize(ptr);
return intervals;
}
57. Insert Interval (Hard)¶
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
思路
因为这里intervals本来就是有序的，所以扫描一遍即可，遇到在newInterval之前的就插入，重叠的就更新newInterval，之后的就先更新newInterval再插入
循环结束判断一下是否插入newInterval，如果没有则插入
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
bool insert = false;
vector<Interval> result;
for (auto i : intervals) {
if (i.end < newInterval.start) result.push_back(i);
else if (i.start > newInterval.end) {
if (!insert) result.push_back(newInterval);
insert = 1;
result.push_back(i);
} else {
newInterval.start = min(newInterval.start, i.start);
newInterval.end = max(newInterval.end, i.end);
}
}
if (!insert) result.push_back(newInterval);
return result;
}
58. Lenght of Last Word (Easy)¶
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
Input: "Hello World" Output: 5
思路
直接搜索空格即可，需要注意去除末尾的空格
int lengthOfLastWord(string s) {
s = s.substr(0, s.find_last_not_of(' ') + 1);
return s.size() - 1 - s.find_last_of(' ');
}
59. Spiral Matrix II (Medium)¶
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
思路
和54. Spiral Matrix一样，旋转填充即可
vector<vector<int> > generateMatrix(int n) {
vector<vector<int> > matrix;
for (int i = 0; i < n; i ++) matrix.push_back(vector<int>(n, 0));
int number = 1;
for (int i = 0; i < (n+1)/2; i ++) {
for (int c = i; c < n-i; c ++) matrix[i][c] = number ++;
for (int r = i+1; r < n-i; r ++) matrix[r][n-1-i] = number ++;
for (int c = n-2-i; c >= i && n-i-1>i; c --) matrix[n-i-1][c] = number ++;
for (int r = n-2-i; r >= i+1 && i<n-1-i; r --) matrix[r][i] = number ++;
}
return matrix;
}
60. Permutation Sequence (Medium)¶
The set [1,2,3,...,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
即返回字典序第k个序列，n范围为[1, 9]
思路
先找到中介数，然后转换成permutation即可
string getPermutation(int n, int k) {
int middle[10] = {0};
// k -> increment radix number
k -= 1;
for (int i = 2; i <= n; i ++) {
middle[i] = k % i;
k = k / i;
if (!k) break;
}
// middle number -> permutation
string res = "";
string num = "123456789";
for (int i = n; i > 0; i --) {
res += num[middle[i]];
num.erase(middle[i], 1);
}
return res;
}
61. Rotate List (Medium)¶
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL
思路
双指针，一个到达末尾时一个指在新的头部
需要注意的是对head为NULL判断，以及k大于length时需要先模length
ListNode* rotateRight(ListNode* head, int k) {
if (head == NULL) return head;
int length = 0;
ListNode* temp = head;
while (temp != NULL) {
length ++;
temp = temp->next;
}
k %= length;
ListNode *first = head, *second = head;
for (int i = 0; i < k; i ++) first = first->next;
while (first->next != NULL) {
first = first -> next;
second = second -> next;
}
first->next = head;
head = second->next;
second->next = NULL;
return head;
}
62. Unique Paths (Medium)¶
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
思路
开一个二维数组，然后遍历加即可
int uniquePaths(int m, int n) {
int** number = new int*[m];
for (int i = 0; i < m; i ++) number[i] = new int[n]();
if (m * n == 0) return 0;
number[0][0] = 1;
for (int i = 0; i < m; i ++)
for (int j = 0; j < n; j ++) {
if (i < m - 1) number[i+1][j] += number[i][j];
if (j < n - 1) number[i][j+1] += number[i][j];
}
return number[m-1][n-1];
}
63. Unique Paths II (Medium)¶
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
思路
可以动归，但其实直接算组合数即可，即C_{n+m-2}^{m-1}
int uniquePaths(int m, int n) {
double num = 1, denom = 1;
int small = m > n ? n : m;
for (int i = 1; i <= small - 1; ++i) {
num *= m + n - 1 - i;
denom *= i;
}
return (int)(num / denom);
}
64. Minimum Path Sum (Medium)¶
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
思路
正常动归即可，grid[i][j]上直接保存从左上角出发到这里的最短路径
int minPathSum(vector<vector<int>>& grid) {
for (int i = 0; i < grid.size(); i ++) {
for (int j = 0; j < grid[0].size(); j ++) {
if (i > 0 && j > 0) grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
else if (i > 0) grid[i][j] += grid[i-1][j];
else if(j > 0) grid[i][j] += grid[i][j-1];
}
}
if (!grid.size()) return 0;
return grid[grid.size()-1][grid[0].size()-1];
}
65. Valid Number (Hard)¶
Validate if a given string can be interpreted as a decimal number.
思路
设定一些规则然后扫描，基本包括
- 只有首尾可以出现空格
- 符号只有在一开始才能出现，不能出现在符号/.后面
- e不能首先出现，且只能出现一次
- .可以首先出现，但只能出现一次，且不能出现在e后面
- 不能出现其它字符
bool isNumber(string s) {
bool afterE = false, sign = false, afterPoint = false;
int length = 0;
if (s.find_first_not_of(' ') == -1) return false;
s = s.substr(s.find_first_not_of(' '), s.find_last_not_of(' ')-s.find_first_not_of(' ')+1);
for (auto c : s) {
if (c == ' ') return false;
if ((sign || afterPoint) && (c == '+' || c == '-')) return false;
if (c == 'e' && (afterE || length == 0)) return false;
if (c == '.' && (afterPoint || afterE)) return false;
if (!length && (c == '+' || c == '-')) sign = 1;
else if (c == 'e') {
afterE = 1; sign = 0; afterPoint = 0; length = 0;
}
else if (c == '.') afterPoint = 1;
else if (c >= '0' && c <= '9') length ++;
else return false;
}
if (afterE && !length) return false;
if (afterPoint && !length) return false;
return length > 0;
}
66. Plus One (Easy)¶
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123.
思路
直接加一即可，如果最后还有进位，需要重新构造一个vector
vector<int> plusOne(vector<int>& digits) {
int offer = 1;
for (int i = digits.size() - 1; i >= 0 && offer > 0; i --) {
digits[i] += offer;
offer = digits[i] / 10;
digits[i] %= 10;
}
if (offer) {
vector<int> result;
result.push_back(offer);
for (auto i : digits) result.push_back(i);
return result;
}
return digits;
}
67. Add Binary (Easy)¶
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
思路
直接加就好
string addBinary(string a, string b) {
int ptr = 0, offer = 0;
string result = "";
while (ptr < a.size() || ptr < b.size()) {
int n0 = (ptr < a.size()) ? a[a.size() - 1 - ptr]-'0' : 0;
int n1 = (ptr < b.size()) ? b[b.size() - 1 - ptr]-'0' : 0;
int r = n0 + n1 + offer;
char c = '0' + r % 2;
offer = r / 2;
result = c + result;
ptr ++;
}
if (offer) result = "1" + result;
return result;
}
68. Text Justification (Hard)¶
Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
大概就是将单词居中排列，除过最后一行外空格在单词间正常分布，如果不能整除，则保证左边空格数最多
思路
从左到右扫描即可，注意细节
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> result;
string temp = "";
int prevPos = 0, length = 0, number = 0;
for (int i = 0; i < words.size(); i ++) {
string s = words[i];
bool add = false;
if (length + s.size() + number <= maxWidth) {
length += s.size();
number ++;
if (i == words.size() - 1) {
add = true;
i ++;
}
}
else add = true;
if (add) {
int spaceNum = maxWidth - length;
int eachNum = (number > 1) ? spaceNum / (number - 1) : 0;
for (int j = prevPos; j < i; j ++) {
temp += words[j];
if (j == i - 1) break;
int midNum = eachNum;
if (eachNum * (i - j - 1) < spaceNum) midNum = eachNum + 1;
if (i == words.size()) midNum = 1;
temp += string(midNum, ' ');
spaceNum -= midNum;
}
if (temp.size() < maxWidth) temp += string(maxWidth - temp.size(), ' ');
result.push_back(temp);
length = number = 0;
temp = "";
prevPos = i;
i --;
}
}
return result;
}
69. Sqrt(x) (Easy)¶
求非负整数x平方根
思路
牛顿迭代法
从某点(x_k,f(x_k))开始，作切线，与x轴相交即为x_{k+1}，切线方程为
则x_{k+1}为
求平方根即求x^2-c=0的解，一开始取起始点在平方根右边，则x_k会一直变小，到两次x_k整数部分相同即得到最后答案
int mySqrt(int x) {
int lastResult = x;
double xk = (x > 0) ? x : 1;
while (1) {
xk = xk - (xk*xk-x)/(2*xk);
if (int(xk) == lastResult) return lastResult;
lastResult = int(xk);
}
}
70. Climbing Stairs (Easy)¶
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
思路
正常DP即可
int climbStairs(int n) {
if (!n) return 0;
vector<int> v(n+1, 0);
v[0] = 1;
for (int i = 0; i < n; i ++) {
v[i + 1] += v[i];
if (i + 2 < v.size()) v[i + 2] += v[i];
}
return v[n];
}
71. Simplify Path (Medium)¶
Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.
In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix
Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.
即简化UNIX-style的路径
思路
用一个stack来存储目录名，要注意的就是如何提取目录名，要考虑的细节有
- 可能有连续/，这时候要判断一下，把指针提前
- 可能最后有/也可能没有，需要扫到最后判断一下
string simplifyPath(string path) {
stack<string> s;
int prevPos = 0;
for (int i = 0; i < path.size(); i ++) {
char c = path[i];
if (c == '/' || i == path.size() - 1) {
if (prevPos == i && c == '/') { prevPos = i + 1; continue; }
string name = path.substr(prevPos, i - prevPos);
if (i == path.size() - 1 && c != '/') name = path.substr(prevPos);
if (name == "..") { if (!s.empty()) s.pop(); }
else if (name != ".") s.push(name);
prevPos = i + 1;
}
}
string res = "";
while (!s.empty()) {
res = "/" + s.top() + res;
s.pop();
}
if (!res.size()) return "/";
return res;
}
72. Edit Distance (Hard)¶
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
思路
动态规划，match[i][j]表示word1[0:i]和word2[0:j]匹配需要的步骤数，一开始可以对match[0][0-n-1]和match[0-m-1][0]初始化
转移关系就看末尾字符word1[i]和word2[j]是否相等
- 相等，那么直接去掉这个字符，步骤数和match[i-1][j-1]一样
- 不相等，那么等于1+min(match[i-1][j-1], match[i][j-1], match[i-1][j]);
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
if (m == 0) return n;
if (n == 0) return m;
int** match = new int*[m];
for (int i = 0; i < m; i ++) match[i] = new int[n]();
int find = 0;
for (int i = 0; i < n; i ++) {
if (word2[i] == word1[0]) find = 1;
match[0][i] = i + 1 - find;
}
find = 0;
for (int i = 0; i < m; i ++) {
if (word1[i] == word2[0]) find = 1;
match[i][0] = i + 1 - find;
}
for (int i = 1; i < m; i ++) {
for (int j = 1; j < n; j ++) {
if (word1[i] == word2[j]) match[i][j] = match[i-1][j-1];
else match[i][j] = min(min(match[i][j-1], match[i-1][j]), match[i-1][j-1]) + 1;
}
}
return match[m-1][n-1];
}
73. Set Matrix Zeroes (Medium)¶
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
思路
先扫一遍，记录有0的行和列的rank
再扫一遍，把有0的行和列全部置0
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size() == 0) return;
int* row = new int[matrix.size()]();
int* col = new int[matrix[0].size()]();
for (int i = 0; i < matrix.size(); i ++)
for (int j = 0; j < matrix[i].size(); j ++)
if (matrix[i][j] == 0) row[i] = col[j] = 1;
for (int i = 0; i < matrix.size(); i ++)
for (int j = 0; j < matrix[i].size(); j ++)
if (row[i] || col[j]) matrix[i][j] = 0;
}
74. Search a 2D Matrix (Medium)¶
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true
思路
即二分搜索
最后要判断l是否超出matrix范围
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0 || matrix[0].size() == 0) return false;
int m = matrix.size(), n = matrix[0].size();
int l = 0, r = m * n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (target <= matrix[mid/n][mid%n]) r = mid - 1;
else l = mid + 1;
}
return l < m * n && matrix[l/n][l%n] == target;
}
75. Sort Colors (Medium)¶
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
思路
先数一遍各颜色数量，然后再改
void sortColors(vector<int>& nums) {
int n0 = 0, n1 = 0, n2 = 0;
for (auto i : nums) {
if (i == 0) n0 ++;
else if (i == 1) n1 ++;
else if (i == 2) n2 ++;
}
for (int i = 0; i < nums.size(); i ++) {
if (i < n0) nums[i] = 0;
else if (i < n1 + n0) nums[i] = 1;
else nums[i] = 2;
}
}
76. Minimum Window Substring (Hard)¶
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"
思路
滑动窗口，即一直双指针维护一个窗口，算法进行中移动两个指针
对本题来说，前面的指针指在子串开头的地方，后面的指针指在结尾，同时用hashmap(本题中因为是char，只有256位，用数组也可以)记录一下T中各字符出现次数，这样可以边扫描边统计当前窗口内是否包括T，具体操作为记录每个字符出现次数，然后窗口内出现一次次数减一，同时cnt加一，当cnt和T长度一样时即包括T，这里需要注意的是如果次数减为负数，cnt不增加
之后向右移动左边指针，减小窗口直到不包含T，这里可以用一个数组记录T中字符的位置，然后左边指针直接移动过去，而不是逐次移动
写的时候注意数组访问不能越界，跑了好几次Runtime Error，最后发现是while循环句中ptr会越界
string minWindow(string s, string t) {
int *charNum = new int[256](), *charInT = new int[256](), *ranks = new int[s.size()]();
if (s.size() == 0 || t.size() == 0) return "";
for (auto c : t) {
charNum[int(c)] ++;
charInT[int(c)] ++;
}
int cnt = 0, minLen = s.size() + 1, l = 0, begin = 0, ptr = 0, tail = 0;
for (int i = 0; i < s.size(); i ++) {
char c = s[i];
if (charInT[int(c)]) ranks[tail ++] = i;
if (charNum[int(c)] -- > 0) cnt ++;
while (cnt == t.size()) {
if (i + 1 - l < minLen) {
minLen = i + 1 - l;
begin = l;
}
while (ptr < tail && l == ranks[ptr]) ptr ++;
if (++ charNum[int(s[l])] > 0) cnt --;
if (ptr >= tail) break;
l = ranks[ptr ++];
}
}
if (minLen > s.size()) return "";
return s.substr(begin, minLen);
}
77. Combinations (Medium)¶
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
思路
就是回溯，可以改进的地方是fill里for循环的终止位置从n改为n - k + temp.size() + 1，可以从96ms提升到72ms(99.51%)
void fill(vector<vector<int> >& result, vector<int>& temp, int begin, int n, int k) {
for (int i = begin; i < n - k + temp.size() + 1; i ++) {
temp.push_back(i + 1);
if (temp.size() == k) result.push_back(temp);
else fill(result, temp, i + 1, n, k);
temp.pop_back();
}
}
vector<vector<int> > combine(int n, int k) {
vector<vector<int> > result;
if (n < 1 || k == 0) return result;
vector<int> temp;
fill(result, temp, 0, n, k);
return result;
}
78. Subsets (Medium)¶
Given a set of distinct integers, nums, return all possible subsets (the power set).
Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
解法一. 递归
递归来做，时间为12ms (48.34%)
void fill (vector<vector<int> >& result, vector<int>& temp, vector<int> nums, int i) {
if (i == nums.size()) result.push_back(temp);
else {
fill(result, temp, nums, i + 1);
temp.push_back(nums[i]);
fill(result, temp, nums, i + 1);
temp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > result;
vector<int> temp;
fill(result, temp, nums, 0);
return result;
}
解法二. 二分
思路就是一开始result里只有[]，对nums中每个数将result拷贝一倍，然后将该数填入后一半中，时间更快 8ms(100%)
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > result;
result.push_back(vector<int>());
for (auto i : nums) {
int size = result.size();
for (int j = 0; j < size; j ++) {
result.push_back(result[j]);
result.back().push_back(i);
}
}
return result;
}
79. Word Search (Medium)¶
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = "ABCCED", return true. Given word = "SEE", return true. Given word = "ABCB", return false.
思路
解法就是深搜，没什么难度
注意要传递引用，这样空间和时间都快
bool dfs(vector<vector<char> >& board, string& word, int ptr, int m, int n, int i, int j) {
if (ptr == word.size() - 1) return true;
board[i][j] = '*';
if (i > 0 && board[i-1][j] == word[ptr + 1] && dfs(board, word, ptr + 1, m, n, i - 1, j)) return true;
if (i < m - 1 && board[i+1][j] == word[ptr + 1] && dfs(board, word, ptr + 1, m, n, i + 1, j)) return true;
if (j > 0 && board[i][j-1] == word[ptr + 1] && dfs(board, word, ptr + 1, m, n, i, j - 1)) return true;
if (j < n - 1 && board[i][j+1] == word[ptr + 1] && dfs(board, word, ptr + 1, m, n, i, j + 1)) return true;
board[i][j] = word[ptr];
return false;
}
bool exist(vector<vector<char> >& board, string word) {
if (word == "") return true;
if (board.size() == 0 || board[0].size() == 0) return false;
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j ++) {
if (board[i][j] == word[0]) {
if (dfs(board, word, 0, m, n, i, j)) return true;
}
}
}
return false;
}
80. Remove Duplicates from Sorted Array II (Medium)¶
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Given nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It doesn't matter what you leave beyond the returned length.
思路
扫描一遍即可
int removeDuplicates(vector<int>& nums) {
if (nums.size() == 0) return 0;
int ptr = 0, times = 0, prev = nums[0];
for (int i = 0; i < nums.size(); i ++) {
if (nums[i] == prev) times ++;
else { times = 1; prev = nums[i]; }
if (times <= 2) nums[ptr ++] = nums[i];
}
return ptr;
}
81. Search in Rotated Sorted Array II (Medium)¶
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true
思路
和 33. Search in Rotated Sorted Array思路一样
不过这里会遇到nums[mid] == nums[-1]的情况，这时候无法知道二分方向，只能降为线性查找，即r=r-1，相应，这里要判断一下nums[r]是否等于target
bool search(vector<int>& nums, int target) {
if (nums.size() == 0) return 0;
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return 1;
else if (nums[r] == target) return 1;
else if (l == r) break;
else if (nums[mid] < nums[nums.size() - 1]) {
if (target > nums[mid] && target <= nums[nums.size() - 1]) l = mid + 1;
else r = mid - 1;
} else if (nums[mid] > nums[nums.size() - 1]) {
if (target < nums[mid] && target >= nums[0]) r = mid - 1;
else l = mid + 1;
}
else r --;
}
return 0;
}
82. Remove Duplicates from Sorted List II (Medium)¶
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Input: 1->2->3->3->4->4->5 Output: 1->2->5
思路
扫描一遍，注意这几点
- 循环结束后可能还有指针要加上去
- 最后要把末尾的next设为NULL
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) return head;
ListNode *ptr = NULL, *temp = head, *pos = head, *result = NULL;
int times = 0, prev = head->val;
while (1) {
if (temp != NULL && temp->val == prev) times ++;
else {
if (times == 1) {
if (ptr == NULL) {
result = ptr = pos;
}
else {
ptr->next = pos;
ptr = pos;
}
}
if (temp == NULL) break;
times = 1;
pos = temp;
prev = temp->val;
}
temp = temp->next;
}
if (ptr != NULL) ptr->next = NULL;
return result;
}
83. Remove Duplicates from Sorted List (Easy)¶
Given a sorted linked list, delete all duplicates such that each element appear only once.
Input: 1->1->2 Output: 1->2
思路
扫描去重即可
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) return head;
ListNode *temp = head, *ptr = NULL, *result = NULL, *pos = head;
int times = 0, prev = head->val;
while (1) {
if (temp != NULL && temp->val == prev) times ++;
else {
if (ptr == NULL) result = ptr = pos;
else {
ptr->next = pos;
ptr = pos;
}
if (temp == NULL) break;
times = 1;
prev = temp->val;
pos = temp;
}
temp = temp->next;
}
if (ptr != NULL) ptr->next = NULL;
return result;
}
84. Largest Rectangle in Histogram (Hard)¶
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Input: [2,1,5,6,2,3] Output: 10
思路
显然O(N^2)可以暴力求解，但更优应考虑O(N)算法
问题实质就是求每个点相邻不小于它的柱数量，可以用栈来解决，刚开始想到的是下面第一个方法，扫两遍，一次统计一个数右边不比其小的柱数量，一个统计左边，相加得解，时间是24ms(25.75%)
而这样的求解其实可以一遍完成，这里要注意的是多个连续相等的柱子，其值是一样的，计算最边上一个就行，同时，一个元素到栈顶，其前面一个元素小于等于它，如前所述，最靠边的元素左边元素比其小，所以直接用i减去左边的秩(栈空时即为i本身)即可，时间是16ms(98.25%)
int largestRectangleArea(vector<int>& heights) {
int result = 0, n = heights.size();
if (n == 0) return result;
int* num = new int[n]();
stack<int> s;
for (int i = 0; i <= heights.size(); i ++) {
while (!s.empty() && (i == n || heights[s.top()] > heights[i])) {
num[s.top()] = i - 1 - s.top();
s.pop();
}
s.push(i);
}
stack<int> s0;
for (int i = 0; i <= n; i ++) {
while (!s0.empty() && (i == n || heights[n-1-s0.top()] > heights[n-1-i])) {
num[n-1-s0.top()] += (i - 1 - s0.top());
s0.pop();
}
s0.push(i);
}
int mx = 0;
for (int i = 0; i < n; i ++) mx = max(mx, heights[i] * (num[i]+1));
return mx;
}
int largestRectangleArea(vector<int>& heights) {
heights.push_back(0);
stack<int> s;
int i = 0, mx = 0;
while (i < heights.size()) {
if (s.empty() || heights[i] >= heights[s.top()]) s.push(i ++);
else {
int height = heights[s.top()];
s.pop();
mx = max(mx, height * (s.empty() ? i : i - 1 - s.top()));
}
}
return mx;
}
85. Maximal Rectangle (Hard)¶
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Input: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] Output: 6
思路
和上题解法一样，对每行得到一个height，即该位及往上有多少个连续的1，然后对这个height求最大面积即可
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix.size() ? matrix[0].size() : 0;
if (m == 0 || n == 0) return 0;
vector<vector<int> > heights;
for (int i = 0; i < m; i ++) heights.push_back(vector<int>(n, 0));
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j ++)
heights[i][j] = (matrix[i][j] == '1') ? 1 + (i > 0 ? heights[i-1][j] : 0) : 0;
heights[i].push_back(0);
}
int mx = 0;
for (int i = 0; i < m; i ++) {
stack<int> s;
int ptr = 0;
while (ptr < n + 1) {
if (s.empty() || heights[i][ptr] >= heights[i][s.top()]) s.push(ptr ++);
else {
int height = heights[i][s.top()];
s.pop();
mx = max(mx, height * (s.empty() ? ptr : ptr - 1 - s.top()));
}
}
}
return mx;
}
86. Partition List (Medium)¶
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5
ListNode* partition(ListNode* head, int x) {
ListNode *firstTail = NULL, *secondHead = NULL, *secondTail = NULL, *ptr = head;
while (ptr != NULL) {
if (ptr->val < x) {
if (firstTail == NULL) head = firstTail = ptr;
else {
firstTail->next = ptr;
firstTail = ptr;
}
} else {
if (secondTail == NULL) secondHead = secondTail = ptr;
else {
secondTail->next = ptr;
secondTail = ptr;
}
}
ptr = ptr->next;
}
if (firstTail == NULL || secondTail == NULL) return head;
firstTail->next = secondHead;
secondTail->next = NULL;
return head;
}
87. Scramble String (Hard)¶
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
To scramble the string, we may choose any non-leaf node and swap its two children.great / \ gr eat / \ / \ g r e at / \ a tFor example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
We say that "rgeat" is a scrambled string of "great".rgeat / \ rg eat / \ / \ r g e at / \ a tGiven two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
思路
递归求解
bool isScramble(string s1, string s2) {
if (s1 == s2) return true;
string a = s1, b = s2;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a != b) return false;
for (int i = 1; i < s1.size(); i ++) {
if (isScramble(s1.substr(0, i), s2.substr(0, i)) &&
isScramble(s1.substr(i), s2.substr(i)))
return true;
if (isScramble(s1.substr(0, i), s2.substr(s1.size()-i)) &&
isScramble(s2.substr(0, s1.size()-i), s1.substr(i)))
return true;
}
return false;
}
88. Merge Sorted Array (Easy)¶
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]
思路
为了防止覆盖，从末尾开始合并
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int ptr = m + n - 1, ptr1 = m - 1, ptr2 = n - 1;
while (ptr >= 0) {
if (ptr == ptr1) break;
if (ptr2 < 0 || (ptr1 >= 0 && nums1[ptr1] > nums2[ptr2])) nums1[ptr --] = nums1[ptr1 --];
else nums1[ptr --] = nums2[ptr2 --];
}
}
89. Gray Code (Medium)¶
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
Input: 2 Output: [0,1,3,2] Explanation: 00 - 0 01 - 1 11 - 3 10 - 2
思路
要求连续两个数的01串只差一位，和全排列的project相似，具体来说，从0-2^n-1，两个相邻的前面n-1位相同的串一定只差一位，则可以分为2^{n-1}块，相邻块第一个01串之间同样只差一位，最后一个01串也同样只差一位，首尾相连，即可构成n-2前缀相等的2^{n-2}个块，这些块继续首尾相连...这样操作直到最后，就可以得到一个gray code序列
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
要生成这个sequence，可以从最开始只有全为0的串开始，每次将已有序列复制一份并反向加在后面即可
vector<int> grayCode(int n) {
vector<int> result = {0};
for (int i = 0; i < n; i ++) {
int delta = (1 << i);
int size = result.size();
for (int j = size - 1; j >= 0; j --) result.push_back(delta + result[j]);
}
return result;
}
90. Subsets II (Medium)¶
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路
和78. Subsets思路一样，需要注意的是如果访问到重复元素，只把上个元素增加的subsets再拷贝一份，而不是全部拷贝，时间为8ms(100%)
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int> > result;
result.push_back(vector<int>());
if (nums.size() == 0) return result;
sort(nums.begin(), nums.end());
int beginPos = 0, prevNum = 0, lastRange = 0;
for (int i = 0; i < nums.size(); i ++) {
int size = result.size(), range = result.size();
if (i > 0 && nums[i] == prevNum) range = lastRange;
lastRange = range;
prevNum = nums[i];
for (int j = 0; j < range; j ++) {
result.push_back(result[size-range+j]);
result.back().push_back(nums[i]);
}
}
return result;
}
91. Decode Ways (Medium)¶
A message containing letters from A-Z is being encoded to numbers using the following mapping:
Given a non-empty string containing only digits, determine the total number of ways to decode it.'A' -> 1 'B' -> 2 ... 'Z' -> 26Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).
思路
DP即可，需要注意
- s为"0"时，特判一下
- s[i]为0时，只能和前面构成两位数
- 两位数两种情况，1x和2x，2开头则x只能从0到6
int numDecodings(string s) {
int *nums = new int[s.size()+1]();
nums[0] = 1;
nums[1] = (s[0] == '0') ? 0 : 1;
for (int i = 1; i < s.size(); i ++) {
if (s[i-1] == '1' || (s[i-1] == '2' && s[i] < '7')) nums[i+1] += nums[i-1];
if (s[i] != '0') nums[i+1] += nums[i];
}
return nums[s.size()];
}
92. Reverse Linked List II (Medium)¶
Reverse a linked list from position m to n. Do it in one-pass.
Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL
思路
扫描即可
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head == NULL) return head;
ListNode *before = NULL, *prev = NULL, *node = head, *localHead = NULL;
int ptr = 0;
while (node != NULL) {
ptr ++;
if (ptr == m - 1) before = node;
if (ptr == m) localHead = node;
ListNode* next = node->next;
if (ptr > m && ptr <= n) node->next = prev;
if (ptr == n) {
if (m == 1) head = node;
else before->next = node;
localHead->next = next;
}
prev = node;
node = next;
}
return head;
}
93. Restore IP Addresses (Medium)¶
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"]
思路
回溯即可，需要注意的是一个segment除过0外不能以0开头
void recursive(vector<string>& result, string s, string ip, int segment) {
if (4-segment > s.size() || (4-segment)*3 < s.size()) return;
if (ip != "") ip = ip + ".";
for (int i = 1; i <= 3; i ++) {
if (i > s.size()) continue;
string num = s.substr(0, i);
if (stoi(num) > 255) continue;
if (i > 1 && num[0] == '0') continue;
if (segment == 3 && i == s.size()) {
result.push_back(ip + num);
return;
}
recursive(result, s.substr(i), ip + num, segment + 1);
}
}
vector<string> restoreIpAddresses(string s) {
vector<string> result;
recursive(result, s, "", 0);
return result;
}
94. Binary Tree Inorder Traversal (Medium)¶
Given a binary tree, return the inorder traversal of its nodes' values.
Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2]
思路
用一个栈来存储已有节点，需要注意的是，要保证每个节点的left只入栈一次，做法是在else分支里面循环将没有右分支的节点pop出去
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
if (root == NULL) return result;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
if (s.top()->left != NULL) s.push(s.top()->left);
else {
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
result.push_back(node->val);
if (node->right != NULL) {
s.push(node->right);
break;
}
}
}
}
return result;
}
解法二Morris
只用O(1)空间复杂度
思路是从root出发，将它的前继节点的右指针指向它
vector<int> inorderTraversal(TreeNode* root) {
TreeNode *cur = root, *prev = nullptr;
vector<int> v;
while (cur != nullptr) {
if (cur->left == nullptr) {
v.push_back(cur->val);
cur = cur->right;
} else {
prev = cur->left;
while (prev->right != nullptr && prev->right != cur) prev = prev->right;
if (prev->right == nullptr) {
prev->right = cur;
cur = cur->left;
} else {
prev->right = NULL;
v.push_back(cur->val);
cur = cur->right;
}
}
}
return v;
}
95. Unique Binary Search Trees II (Medium)¶
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] Explanation: The above output corresponds to the 5 unique BST's shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
思路
递归来做，和22. Generate Parentheses思路相近，这里同样答案数量是Catalan数
vector<TreeNode*> recursion(int n, int base) {
if (n == 0) return {NULL};
vector<TreeNode*> result;
for (int i = 0; i < n; i ++) {
vector<TreeNode*> leftNodes = recursion(i, base);
vector<TreeNode*> rightNodes = recursion(n-1-i, base+i+1);
for (int j = 0; j < leftNodes.size(); j ++)
for (int k = 0; k < rightNodes.size(); k ++) {
TreeNode* root = new TreeNode(i + 1 + base);
root->left = leftNodes[j];
root->right = rightNodes[k];
result.push_back(root);
}
}
return result;
}
vector<TreeNode*> generateTrees(int n) {
if (n == 0) return {};
return recursion(n, 0);
}
96. Unique Binary Search Trees (Medium)¶
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
思路
直接计算Catalan数
int numTrees(int n) {
int* num = new int[n + 1]();
if (n < 2) return 1;
num[0] = num[1] = 1;
for (int i = 2; i <= n; i ++)
for (int j = 0; j < i; j ++)
num[i] += (num[j] * num[i-1-j]);
return num[n];
}
97. Interleaving String (Hard)¶
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true
思路
DP，dp[i][j]表示s1的前i位和s2的前j位能否拼成s3的前i+j位
- 初始化: i=0，只比较s2和s3就行，同样j=0，只比较s1和s3
- 转移: 如果s1[i-1]==s3[i+j-1]，看dp[i-1][j]，同样如果s2[j-1]==s3[i+j-1]，看dp[i][j-1]
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if (s3.size() != m + n) return false;
int** dp = new int*[m+1];
for (int i = 0; i <= m; i ++) dp[i] = new int[n+1]();
int match = 1;
dp[0][0] = 1;
for (int i = 1; i <= m; i ++) {
if (s1[i-1] != s3[i-1]) match = 0;
dp[i][0] = match;
}
match = 1;
for (int i = 1; i <= n; i ++) {
if (s2[i-1] != s3[i-1]) match = 0;
dp[0][i] = match;
}
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
char c = s3[i + j -1];
if ((c == s1[i-1] && dp[i-1][j]) || (c == s2[j-1] && dp[i][j-1])) dp[i][j] = 1;
}
}
return dp[m][n];
}
98. Validate Binary Search Tree (Medium)¶
Given a binary tree, determine if it is a valid binary search tree (BST).
Input: 2 / \ 1 3 Output: true
思路
递归判断即可
bool isValid(TreeNode* root, bool upper, int upperBound, bool lower, int lowerBound) {
if (root == NULL) return true;
int val = root->val;
if ((upper && val >= upperBound) || (lower && val <= lowerBound)) return false;
return isValid(root->left, 1, val, lower, lowerBound) &&
isValid(root->right, upper, upperBound, 1, val);
}
bool isValidBST(TreeNode* root) {
return isValid(root, 0, 0, 0, 0);
}
99. Recover Binary Search Tree (Hard)¶
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Input: [1,3,null,null,2] 1 / 3 \ 2 Output: [3,1,null,null,2] 3 / 1 \ 2
思路
递归中序遍历来找到两个比前一个点小的点，即要交换的两个点，然后交换即可
void dfs(TreeNode* root, TreeNode*& prev, TreeNode*& first, TreeNode*& second) {
if (root == NULL) return;
dfs(root->left, prev, first, second);
if (prev != NULL && root->val < prev->val) {
if (first == NULL) first = prev;
second = root;
}
prev = root;
dfs(root->right, prev, first, second);
}
void recoverTree(TreeNode* root) {
TreeNode *prev = NULL, *first = NULL, *second = NULL;
dfs(root, prev, first, second);
if (second == NULL) return;
swap(first->val, second->val);
}
100. Same Tree (Easy)¶
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Input: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] Output: true
思路
递归比较即可
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL) return true;
if ((p == NULL && q != NULL) || (p != NULL && q == NULL)) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}