Leetcode1.Two Sum
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:1
2
3
4
5Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
也十分简单,不知道啥时候做的了,现在补上。就是找一对数,使二者之和等于target,可以暴力,也可以用巧妙的方法,下边有巧妙方法,是从solution中找的。
我的方法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
int length = nums.size(),j=-1;
for(int i=0;i<length;i++){
for(j=i+1;j<length;j++)
if(nums[j]==target-nums[i]){
result.push_back(i);
result.push_back(j);
return result;
}
}
return result;
}
};
跟我一样的方法,用java实现:1
2
3
4
5
6
7
8
9
10
11
12
13public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}
第三种方法:One-pass Hash Table
It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.1
2
3
4
5
6
7
8
9
10
11public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
反正都是很简单的。。。
Leetcode2. Add Two Numbers
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.
Example:1
2
3Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
非常简单,给两个链表,相当于两个数,不过是倒着的,然后求这两个数的和再转换成链表。只是第一次用类的方法做题,不太习惯,然后对链表的使用也快忘光了,这是一个良好的开始吧。
1 | class Solution { |
Leetcode3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:1
2
3Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:1
2
3Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:1
2
3
4Input: "pwwkew"
Output: 3
Explanation: 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.
给了我们一个字符串,让求最长的无重复字符的子串,注意这里是子串,不是子序列,所以必须是连续的。先不考虑代码怎么实现,如果给一个例子中的例子 “abcabcbb”,让你手动找无重复字符的子串,该怎么找。博主会一个字符一个字符的遍历,比如 a,b,c,然后又出现了一个a,那么此时就应该去掉第一次出现的a,然后继续往后,又出现了一个b,则应该去掉一次出现的b,以此类推,最终发现最长的长度为3。所以说,需要记录之前出现过的字符,记录的方式有很多,最常见的是统计字符出现的个数,但是这道题字符出现的位置很重要,所以可以使用 HashMap 来建立字符和其出现位置之间的映射。进一步考虑,由于字符会重复出现,到底是保存所有出现的位置呢,还是只记录一个位置?我们之前手动推导的方法实际上是维护了一个滑动窗口,窗口内的都是没有重复的字符,需要尽可能的扩大窗口的大小。由于窗口在不停向右滑动,所以只关心每个字符最后出现的位置,并建立映射。窗口的右边界就是当前遍历到的字符的位置,为了求出窗口的大小,需要一个变量 left 来指向滑动窗口的左边界,这样,如果当前遍历到的字符从未出现过,那么直接扩大右边界,如果之前出现过,那么就分两种情况,在或不在滑动窗口内,如果不在滑动窗口内,那么就没事,当前字符可以加进来,如果在的话,就需要先在滑动窗口内去掉这个已经出现过的字符了,去掉的方法并不需要将左边界 left 一位一位向右遍历查找,由于 HashMap 已经保存了该重复字符最后出现的位置,所以直接移动 left 指针就可以了。维护一个结果 res,每次用出现过的窗口大小来更新结果 res,就可以得到最终结果啦。
这里可以建立一个 HashMap,建立每个字符和其最后出现位置之间的映射,然后需要定义两个变量 res 和 left,其中 res 用来记录最长无重复子串的长度,left 指向该无重复子串左边的起始位置的前一个,由于是前一个,所以初始化就是 -1,然后遍历整个字符串,对于每一个遍历到的字符,如果该字符已经在 HashMap 中存在了,并且如果其映射值大于 left 的话,那么更新 left 为当前映射值。然后映射值更新为当前坐标i,这样保证了 left 始终为当前边界的前一个位置,然后计算窗口长度的时候,直接用 i-left 即可,用来更新结果 res。
这里解释下程序中那个 if 条件语句中的两个条件 m.count(s[i]) && m[s[i]] > left,因为一旦当前字符 s[i] 在 HashMap 已经存在映射,说明当前的字符已经出现过了,而若 m[s[i]] > left 成立,说明之前出现过的字符在窗口内,那么如果要加上当前这个重复的字符,就要移除之前的那个,所以让 left 赋值为 m[s[i]],由于 left 是窗口左边界的前一个位置(这也是 left 初始化为 -1 的原因,因为窗口左边界是从0开始遍历的),所以相当于已经移除出滑动窗口了。举一个最简单的例子 “aa”,当 i=0 时,建立了 a->0 的映射,并且此时结果 res 更新为1,那么当 i=1 的时候,发现a在 HashMap 中,并且映射值0大于 left 的 -1,所以此时 left 更新为0,映射对更新为 a->1,那么此时 i-left 还为1,不用更新结果 res,那么最终结果 res 还为1。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> m;
int left = -1, res = 0;
for(int i = 0; i < s.length(); i ++) {
if(m.count(s[i]) && m[s[i]] > left) {
left = m[s[i]];
}
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};
Leetcode4. Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:1
2
3Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:1
2
3Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:1
2Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Example 4:1
2Input: nums1 = [], nums2 = [1]
Output: 1.00000
Example 5:1
2Input: nums1 = [2], nums2 = []
Output: 2.00000
给出两个有序数组,要求找出这两个数组合并以后的有序数组中的中位数。要求时间复杂度为 O(log (m+n))。
这一题最容易想到的办法是把两个数组合并,然后取出中位数。但是合并有序数组的操作是 O(m+n) 的,不符合题意。看到题目给的 log 的时间复杂度,很容易联想到二分搜索。
由于要找到最终合并以后数组的中位数,两个数组的总大小也知道,所以中间这个位置也是知道的。只需要二分搜索一个数组中切分的位置,另一个数组中切分的位置也能得到。为了使得时间复杂度最小,所以二分搜索两个数组中长度较小的那个数组。
关键的问题是如何切分数组 1 和数组 2 。其实就是如何切分数组 1 。先随便二分产生一个 midA,切分的线何时算满足了中位数的条件呢?即,线左边的数都小于右边的数,即,nums1[midA-1] ≤ nums2[midB] && nums2[midB-1] ≤ nums1[midA] 。如果这些条件都不满足,切分线就需要调整。如果 nums1[midA] < nums2[midB-1],说明 midA 这条线划分出来左边的数小了,切分线应该右移;如果 nums1[midA-1] > nums2[midB],说明 midA 这条线划分出来左边的数大了,切分线应该左移。经过多次调整以后,切分线总能找到满足条件的解。
假设现在找到了切分的两条线了,数组 1 在切分线两边的下标分别是 midA - 1 和 midA。数组 2 在切分线两边的下标分别是 midB - 1 和 midB。最终合并成最终数组,如果数组长度是奇数,那么中位数就是 max(nums1[midA-1], nums2[midB-1])。如果数组长度是偶数,那么中间位置的两个数依次是:max(nums1[midA-1], nums2[midB-1]) 和 min(nums1[midA], nums2[midB]),那么中位数就是 (max(nums1[midA-1], nums2[midB-1]) + min(nums1[midA], nums2[midB])) / 2。
1 | class Solution { |
Leetcode5. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:1
2
3Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:1
2Input: "cbbd"
Output: "bb"
使用动态规划:dp[i][i]=1;
//单个字符是回文串
dp[i][i+1]=1 if s[i]=s[i+1];//连续两个相同字符是回文串
1 | class Solution { |
另一种区间dp方法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
string longestPalindrome(string s) {
int len = s.length();
int start = 0, max_len = 1;
vector<vector<bool>> dp(len, vector<bool>(len, false));
for (int i = 0; i < len; i ++)
dp[i][i] = true;
for (int l = 2; l <= len; l ++) {
for (int i = 0; i+l <= len; i ++) {
int j = i+l-1;
if (s[i] == s[j]) {
dp[i][j] = (dp[i+1][j-1] && (s[i] == s[j])) || l == 2;
if (dp[i][j]) {
max_len = l;
start = i;
}
}
}
}
return s.substr(start, max_len);
}
};
马拉车方法:
这个马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法,由一个叫 Manacher 的人在 1975 年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性,这是非常了不起的。对于回文串想必大家都不陌生,就是正读反读都一样的字符串,比如 “bob”, “level”, “noon” 等等,那么如何在一个字符串中找出最长回文子串呢,可以以每一个字符为中心,向两边寻找回文子串,在遍历完整个数组后,就可以找到最长的回文子串。但是这个方法的时间复杂度为 O(n*n),并不是很高效,下面我们来看时间复杂度为 O(n)的马拉车算法。
由于回文串的长度可奇可偶,比如 “bob” 是奇数形式的回文,”noon” 就是偶数形式的回文,马拉车算法的第一步是预处理,做法是在每一个字符的左右都加上一个特殊字符,比如加上 ‘#’,那么
bob —> #b#o#b#
noon —> #n#o#o#n#
这样做的好处是不论原字符串是奇数还是偶数个,处理之后得到的字符串的个数都是奇数个,这样就不用分情况讨论了,而可以一起搞定。接下来我们还需要和处理后的字符串t等长的数组p,其中 p[i] 表示以 t[i] 字符为中心的回文子串的半径,若 p[i] = 1,则该回文子串就是 t[i] 本身,那么我们来看一个简单的例子:1
2# 1 # 2 # 2 # 1 # 2 # 2 #
1 2 1 2 5 2 1 6 1 2 3 2 1
为啥我们关心回文子串的半径呢?看上面那个例子,以中间的 ‘1’ 为中心的回文子串 “#2#2#1#2#2#” 的半径是6,而未添加#号的回文子串为 “22122”,长度是5,为半径减1。这是个普遍的规律么?我们再看看之前的那个 “#b#o#b#”,我们很容易看出来以中间的 ‘o’ 为中心的回文串的半径是4,而 “bob”的长度是3,符合规律。再来看偶数个的情况 “noon”,添加#号后的回文串为 “#n#o#o#n#”,以最中间的 ‘#’ 为中心的回文串的半径是5,而 “noon” 的长度是4,完美符合规律。所以我们只要找到了最大的半径,就知道最长的回文子串的字符个数了。只知道长度无法定位子串,我们还需要知道子串的起始位置。
我们还是先来看中间的 ‘1’ 在字符串 “#1#2#2#1#2#2#” 中的位置是7,而半径是6,貌似 7-6=1,刚好就是回文子串 “22122” 在原串 “122122” 中的起始位置1。那么我们再来验证下 “bob”,”o” 在 “#b#o#b#” 中的位置是3,但是半径是4,这一减成负的了,肯定不对。所以我们应该至少把中心位置向后移动一位,才能为0啊,那么我们就需要在前面增加一个字符,这个字符不能是#号,也不能是s中可能出现的字符,所以我们暂且就用美元号吧,毕竟是博主最爱的东西嘛。这样都不相同的话就不会改变p值了,那么末尾要不要对应的也添加呢,其实不用的,不用加的原因是字符串的结尾标识为 ‘\0’,等于默认加过了。那此时 “o” 在 “$#b#o#b#” 中的位置是4,半径是4,一减就是0了,貌似没啥问题。我们再来验证一下那个数字串,中间的 ‘1’ 在字符串 “$#1#2#2#1#2#2#” 中的位置是8,而半径是6,这一减就是2了,而我们需要的是1,所以我们要除以2。之前的 “bob” 因为相减已经是0了,除以2还是0,没有问题。再来验证一下 “noon”,中间的 ‘#’ 在字符串 “$#n#o#o#n#” 中的位置是5,半径也是5,相减并除以2还是0,完美。可以任意试试其他的例子,都是符合这个规律的,最长子串的长度是半径减1,起始位置是中间位置减去半径再除以2。
那么下面我们就来看如何求p数组,需要新增两个辅助变量 mx 和 id,其中 id 为能延伸到最右端的位置的那个回文子串的中心点位置,mx 是回文串能延伸到的最右端的位置,需要注意的是,这个 mx 位置的字符不属于回文串,所以才能用 mx-i 来更新 p[i] 的长度而不用加1,由 mx 的更新方式 mx = i + p[i] 也能看出来 mx 是不在回文串范围内的,这个算法的最核心的一行如下:1
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
可以这么说,这行要是理解了,那么马拉车算法基本上就没啥问题了,那么这一行代码拆开来看就是
如果 mx > i, 则p[i] = min( p[2 * id - i] , mx - i )
否则,p[i] = 1
当mx - i > P[j]
的时候,以 S[j] 为中心的回文子串包含在以 S[id] 为中心的回文子串中,由于 i 和 j 对称,以 S[i] 为中心的回文子串必然包含在以 S[id] 为中心的回文子串中,所以必有P[i] = P[j]
,其中j = 2*id - i
,因为 j 到 id 之间到距离等于 id 到 i 之间到距离,为 i - id,所以j = id - (i - id) = 2*id - i
。
当P[j] >= mx - i
的时候,以 S[j] 为中心的回文子串不一定完全包含于以 S[id] 为中心的回文子串中,但是基于对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以 S[i] 为中心的回文子串,其向右至少会扩张到 mx 的位置,也就是说P[i] = mx - i
。至于 mx 之后的部分是否对称,就只能老老实实去匹配了,这就是后面紧跟到 while 循环的作用。
对于 mx <= i 的情况,无法对 P[i] 做更多的假设,只能 P[i] = 1,然后再去匹配了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class Solution {
public:
string longestPalindrome(string s) {
int len = s.length(), lens = len*2+2, id = 0, maxx = 0, reslen = 0;
int start;
vector<int> p(lens, 0);
string ss(lens, ' ');
ss[0] = '$';
ss[1] = '#';
for (int i = 0; i < len; i ++) {
ss[i*2+2] = s[i];
ss[i*2+3] = '#';
}
for (int i = 1; i < lens; i ++) {
if (maxx > i)
p[i] = min(p[2*id - i], maxx - i);
else
p[i] = 1;
while(ss[i+p[i]] == ss[i-p[i]])
p[i] ++;
if (p[i]+i > maxx) {
maxx = p[i] + i;
id = i;
}
if (p[i] > reslen) {
reslen = p[i];
start = i;
}
}
return s.substr((start-reslen)/2, reslen-1);
}
};
Leetcode6. ZigZag Conversion
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)1
2
3P 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:1
2Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:1
2
3
4
5
6
7
8Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
建立一个大小为 numRows 的字符串数组,为的就是把之字形的数组整个存进去,然后再把每一行的字符拼接起来,就是想要的结果了。顺序就是按列进行遍历,首先前 numRows 个字符就是按顺序存在每行的第一个位置,然后就是 ‘之’ 字形的连接位置了,可以发现其实都是在行数区间 [1, numRows-2] 内,只要按顺序去取字符就可以了,最后把每行都拼接起来即为所求1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
string convert(string s, int numRows) {
if (numRows <= 1) return s;
string res;
int i = 0, n = s.size();
vector<string> vec(numRows);
while(i < n) {
for (int pos = 0; pos < numRows && i < n; ++pos)
vec[pos] += s[i++];
for (int pos = numRows - 2; pos >= 1 && i < n; --pos)
vec[pos] += s[i++];
}
for (auto &a : vec) res += a;
return res;
}
};
Leetcode7. Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:1
2Input: 123
Output: 321
Example 2:1
2Input: -123
Output: -321
Example 3:1
2Input: 120
Output: 21
Note:
- Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
翻转数字问题需要注意的就是溢出问题,看了许多网上的解法,由于之前的 OJ 没有对溢出进行测试,所以网上很多人的解法没有处理溢出问题也能通过 OJ。现在 OJ 更新了溢出测试,所以还是要考虑到。为什么会存在溢出问题呢,由于int型的数值范围是 -2147483648~2147483647, 那么如果要翻转 1000000009 这个在范围内的数得到 9000000001,而翻转后的数就超过了范围。博主最开始的想法是,用 long 型数据,其数值范围为 -9223372036854775808~9223372036854775807, 远大于 int 型这样就不会出现溢出问题。但实际上 OJ 给出的官方解答并不需要使用 long,一看比自己的写的更精简一些,它没有特意处理正负号,仔细一想,果然正负号不影响计算,而且没有用 long 型数据,感觉写的更好一些,那么就贴出来吧:
解法一:1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int reverse(int x) {
int res = 0;
while (x != 0) {
if (abs(res) > INT_MAX / 10) return 0;
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
};
在贴出答案的同时,OJ 还提了一个问题 To check for overflow/underflow, we could check if ret > 214748364 or ret < –214748364 before multiplying by 10. On the other hand, we do not need to check if ret == 214748364, why? (214748364 即为 INT_MAX / 10)
为什么不用 check 是否等于 214748364 呢,因为输入的x也是一个整型数,所以x的范围也应该在 -2147483648~2147483647 之间,那么x的第一位只能是1或者2,翻转之后 res 的最后一位只能是1或2,所以 res 只能是 2147483641 或 2147483642 都在 int 的范围内。但是它们对应的x为 1463847412 和 2463847412,后者超出了数值范围。所以当过程中 res 等于 214748364 时, 输入的x只能为 1463847412, 翻转后的结果为 2147483641,都在正确的范围内,所以不用 check。
我们也可以用 long 型变量保存计算结果,最后返回的时候判断是否在 int 返回内,但其实题目中说了只能存整型的变量,所以这种方法就只能当个思路扩展了,参见代码如下:
1 | class Solution { |
Leetcode8. String to Integer (atoi)
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: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
Example 1:1
2Input: "42"
Output: 42
Example 2:1
2
3
4Input: " -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:1
2
3Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
Example 4:1
2
3
4Input: "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:1
2
3
4Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.
Example 6:1
2Input: "+1"
Output: 1
实现一个字符串转数字的函数。只需要返回位于字符串前缀最长的一个数字,如-12a就返回-12。除了正常情况还有很多的corner case,下面列举一下可能的情况:
- 忽略前缀空格;
- 一个数字前只能有一个单元运算符(负号或者正号);
- 读到非数字之后的余串忽略;
- 当数字不小于2147483647,认为正溢出,直接返回2147483647;
- 当数字不大于-2147483648,认为负溢出,直接返回-2147483648;
- 最好用long long存储数据避免溢出。
本来是直接处理的,没想到corner case太多了,所以学习人家的办法先过滤一下前缀再处理。
1 | int myAtoi(string str) { |
Leetcode9. Palindrome Number
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:1
2Input: 121
Output: true
Example 2:1
2
3Input: -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:1
2
3Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up: Could you solve it without converting the integer to a string?
回文数,如果是负数直接返回false,正数的话转成string再判断。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
bool isPalindrome(int x) {
int i=0;
if(x<0)
return false;
int length = 0;
int str[100000];
while(x>0){
str[i++]=(x%10);
x/=10;
}
int middle = i/2;
int j=0;
while(j<middle){
if(str[j]!=str[i-1-j])
return false;
j++;
}
return true;
}
};
Leetcode10. Regular Expression Matching
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 the entire input 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:1
2
3
4
5Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:1
2
3
4
5Input:
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:1
2
3
4
5Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:1
2
3
4
5Input:
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:1
2
3
4Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
这道求正则表达式匹配的题和那道 Wildcard Matching 的题很类似,不同点在于的意义不同,在之前那道题中,表示可以代替任意个数的字符,而这道题中的*表示之前那个字符可以有0个,1个或是多个,就是说,字符串 a*b,可以表示b或是 aaab,即a的个数任意,这道题的难度要相对之前那一道大一些,分的情况的要复杂一些,需要用递归 Recursion 来解,大概思路如下:
若p为空,若s也为空,返回 true,反之返回 false。
若p的长度为1,若s长度也为1,且相同或是p为 ‘.’ 则返回 true,反之返回 false。
若p的第二个字符不为*,若此时s为空返回 false,否则判断首字符是否匹配,且从各自的第二个字符开始调用递归函数匹配。
若p的第二个字符为*,进行下列循环,条件是若s不为空且首字符匹配(包括 p[0] 为点),调用递归函数匹配s和去掉前两个字符的p(这样做的原因是假设此时的星号的作用是让前面的字符出现0次,验证是否匹配),若匹配返回 true,否则s去掉首字母(因为此时首字母匹配了,我们可以去掉s的首字母,而p由于星号的作用,可以有任意个首字母,所以不需要去掉),继续进行循环。
返回调用递归函数匹配s和去掉前两个字符的p的结果(这么做的原因是处理星号无法匹配的内容,比如 s=
ab
, p=a*b
,直接进入 while 循环后,我们发现 “ab” 和 “b” 不匹配,所以s变成 “b”,那么此时跳出循环后,就到最后的 return 来比较 “b” 和 “b” 了,返回 true。再举个例子,比如 s=””, p=”a*”,由于s为空,不会进入任何的 if 和 while,只能到最后的 return 来比较了,返回 true,正确)。
1 | class Solution { |
上面的方法可以写的更加简洁一些,但是整个思路还是一样的,先来判断p是否为空,若为空则根据s的为空的情况返回结果。当p的第二个字符为号时,由于号前面的字符的个数可以任意,可以为0,那么我们先用递归来调用为0的情况,就是直接把这两个字符去掉再比较,或者当s不为空,且第一个字符和p的第一个字符相同时,再对去掉首字符的s和p调用递归,注意p不能去掉首字符,因为号前面的字符可以有无限个;如果第二个字符不为号,那么就老老实实的比较第一个字符,然后对后面的字符串调用递归,参见代码如下:1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
bool isMatch(string s, string p) {
if (p.empty()) return s.empty();
if (p.size() > 1 && p[1] == '*') {
return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p));
} else {
return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
}
}
};
我们也可以用 DP 来解,定义一个二维的 DP 数组,其中 dp[i][j] 表示 s[0,i) 和 p[0,j) 是否 match,然后有下面三种情况(下面部分摘自这个帖子):
- P[i][j] = P[i - 1][j - 1], if p[j - 1] != ‘*’ && (s[i - 1] == p[j - 1] || p[j - 1] == ‘.’);
- P[i][j] = P[i][j - 2], if p[j - 1] == ‘*’ and the pattern repeats for 0 times;
- P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == ‘.’), if p[j - 1] == ‘*’ and the pattern repeats for at least 1 times.
1 | class Solution { |
从视频里看来的dp做法,更加好懂1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38class Solution {
public:
bool isMatch(string s, string p) {
int slen = s.length(), plen = p.length();
vector<vector<bool> > f(slen+1, vector<bool>(plen+1, false));
s.insert(s.begin(), '0');
p.insert(p.begin(), '0');
f[0][0] = true;
for (int i = 1; i <= plen; i ++)
if (p[i] == '*') f[0][i] = f[0][i-1];
else if (i+1 > plen || p[i+1] != '*') break;
else f[0][i] = true; // p[i], *
for (int i = 1; i <= slen; i ++) {
for (int j = 1; j <= plen; j ++) {
if (p[j] == '*') {
f[i][j] = f[i][j-1];
continue;
}
if (j+1 <= plen && p[j+1] == '*') {
// s[i]可能有三种:
// 空
// 一个p[j]
// 若干个p[j]
f[i][j] = f[i][j-1] ||
`` (f[i-1][j-1] && (p[j] == '.' || s[i] == p[j])) ||
(f[i-1][j] && (p[j] == '.' || s[i] == p[j]));
}
else {
f[i][j] = f[i-1][j-1] && (p[j] == '.' || s[i] == p[j]);
}
}
}
return f[slen][plen];
}
};
Leetcode11. Container With Most Water
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.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
给定 n 个非负整数 (a1, a2, …, an),每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条竖直线,竖直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明: 你不能倾斜容器,且 n 的值至少为 2。
图中垂直线代表输入数组 [3,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
这道题在 LeetCode 中排序很靠前,相信你们都见过这道题目。题意理解起来很简单,但要做出来并不容易,尤其是得到O(n)时间复杂度的解法。即使看了答案知道了 O(n) 解法怎么做,也不一定能证明它的正确性。
双指针解法:和 Two Sum II 类似,这道题的搜索空间大小是 O(n^2) 数量级。暴力法一次考察搜索空间中的一个情况,时间复杂度自然也是 O(n^2) 。而我们希望用一种方法,一次排除多个情况,从而减少时间复杂度。
在一开始,我们考虑相距最远的两个柱子所能容纳水的面积。水的宽度是两根柱子之间的距离 d=8;水的高度取决于两根柱子之间较短的那个,即左边柱子的高度 h=3 。水的面积就是 8*3=24。
如果选择固定一根柱子,另外一根变化,水的面积会有什么变化吗?稍加思考可得:
- 当前柱子是最两侧的柱子,水的宽度 为最大,其他的组合,水的宽度都比这个小。
- 左边柱子较短,决定了水的高度为 3。如果移动左边的柱子,新的水面高度不确定,一定不会超过右边的柱子高度 7。
- 如果移动右边的柱子,新的水面高度一定不会超过左边的柱子高度 3,也就是不会超过现在的水面高度。
由此可见,如果固定左边的柱子,移动右边的柱子,那么水的高度一定不会增加,且宽度一定减少,所以水的面积一定减少。这个时候,左边的柱子和任意一个其他柱子的组合,其实都可以排除了。也就是我们可以排除掉左边的柱子了。
排除左边这个柱子的操作,对应于双指针解法的代码,就是指针向右移动一位。对应于搜索空间,就是削减了一行的搜索空间,如下图所示。
削减一行的搜索空间
可以看到,这个搜索空间的削减方式和 Two Sum II 问题中的形状如出一辙(其实就是我把上一篇文章里的图直接搬过来了),如果你理解了 Two Sum II 问题,那一定能秒懂这道题。
同样的道理,假设两根柱子是右边的较短,我们就可以排除掉右边的柱子,削减一列的搜索空间,如下图所示。
削减一列的搜索空间
这样,经过 步以后,我们就能排除所有的搜索空间,检查完所有的可能性。
那么,我们最终就写出了这样的双指针代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public int maxArea(int[] height) {
int res = 0;
int i = 0;
int j = height.length - 1;
while (i < j) {
int area = (j - i) * Math.min(height[i], height[j]);
res = Math.max(res, area);
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return res;
}
实话说,很少有人能在第一次接触到这一题的时候就立即想出这样巧妙的双指针解法,所以刷题提升的过程一定是伴随着“记答案”的。但是我们同时还要善于归纳和总结,因为死记硬背是个苦工夫,只有理解了思想,才能记得快、记得牢。
就比如 167 题的 Two Sum II 和这道题。两者都是用这样的双指针解法,从代码上看非常相似,但它们究竟为何相似呢?实际上,两道题就是因为削减搜索空间的原理相通,解题思路实际上是一模一样的。如果你能洞察这一点,那么距离举一反三也就不远了。
1 | class Solution { |
Leetcode12. Integer to Roman
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.1
2
3
4
5
6
7
8Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
- I can be placed before V (5) and X (10) to make 4 and 9.
- X can be placed before L (50) and C (100) to make 40 and 90.
- C can be placed before D (500) and M (1000) to make 400 and 900.
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.
Example 1:1
2Input: 3
Output: "III"
Example 2:1
2Input: 4
Output: "IV"
Example 3:1
2Input: 9
Output: "IX"
Example 4:1
2
3Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.
Example 5:1
2
3Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
例如整数 1437 的罗马数字为 MCDXXXVII, 我们不难发现,千位,百位,十位和个位上的数分别用罗马数字表示了。 1000 - M, 400 - CD, 30 - XXX, 7 - VII。所以我们要做的就是用取商法分别提取各个位上的数字,然后分别表示出来。可以分为四类,100 到 300 一类,400 一类,500 到 800 一类,900 最后一类。每一位上的情况都是类似的,代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
string intToRoman(int num) {
string res = "";
vector<char> roman{'M', 'D', 'C', 'L', 'X', 'V', 'I'};
vector<int> value{1000, 500, 100, 50, 10, 5, 1};
for(int i = 0; i < 7; i += 2) {
int temp = num / value[i];
num = num % value[i];
if(temp < 4)
for(int ii = 0; ii < temp; ii ++)
res = res + roman[i];
else if(temp == 4) {
res = res + roman[i] + roman[i-1];
}
else if(temp > 4 && temp < 9) {
res = res + roman[i-1];
for(int ii = 6; ii <= temp; ii ++)
res = res + roman[i];
}
else if(temp == 9)
res = res + roman[i] + roman[i-2];
}
return res;
}
};
Leetcode13. Roman to Integer
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol | Value |
---|---|
I | 1 |
V | 5 |
X | 10 |
L | 50 |
C | 100 |
D | 500 |
M | 1000 |
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
Example 1:1
2Input: "III"
Output: 3
Example 2:1
2Input: "IV"
Output: 4
Example 3:1
2Input: "IX"
Output: 9
Example 4:1
2
3Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:1
2
3Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
题目描述:通过给定Roman数字,得到我们的Integer
解题思路:首先给出Roman计数规则 计数规则: 相同的数字连写,所表示的数等于这些数字相加得到的数,例如:III = 3 小的数字在大的数字右边,所表示的数等于这些数字相加得到的数,例如:VIII = 8 小的数字,限于(I、X和C)在大的数字左边,所表示的数等于大数减去小数所得的数, 例如:IV = 4 正常使用时,连续的数字重复不得超过三次 在一个数的上面画横线,表示这个数扩大1000倍(本题只考虑3999以内的数,所以用不到这条规则)
罗马数字共有7个,即I(1)、V(5)、X(10)、L(50)、C(100)、D(500)和M(1000)。按照下述的规则可以表示任意正整数。需要注意的是罗马数字中没有“0”,与进位制无关。一般认为罗马数字只用来记数,而不作演算。
重复数次:一个罗马数字重复几次,就表示这个数的几倍。右加左减:在较大的罗马数字的右边记上较小的罗马数字,表示大数字加小数字。在较大的罗马数字的左边记上较小的罗马数字,表示大数字减小数字。左减的数字有限制,仅限于I、X、C。比如45不可以写成VL,只能是XLV但是,左减时不可跨越一个位数。比如,99不可以用IC()表示,而是用XCIX()表示。(等同于阿拉伯数字每位数字分别表示。)左减数字必须为一位,比如8写成VIII,而非IIX。右加数字不可连续超过三位,比如14写成XIV,而非XIIII。(见下方“数码限制”一项。)加线乘千:在罗马数字的上方加上一条横线或者加上下标的Ⅿ,表示将这个数乘以1000,即是原数的1000倍。同理,如果上方有两条横线,即是原数的1000000()倍。数码限制:同一数码最多只能出现三次,如40不可表示为XXXX,而要表示为XL。例外:由于IV是古罗马神话主神朱庇特(即IVPITER,古罗马字母里没有J和U)的首字,因此有时用IIII代替IV。
这道题好就好在没有让我们来验证输入字符串是不是罗马数字,这样省掉不少功夫。需要用到 HashMap 数据结构,来将罗马数字的字母转化为对应的整数值,因为输入的一定是罗马数字,那么只要考虑两种情况即可:
第一,如果当前数字是最后一个数字,或者之后的数字比它小的话,则加上当前数字。
第二,其他情况则减去这个数字。
1 | class Solution { |
1 | class Solution { |
Leetcode14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Example 1:1
2Input: ["flower","flow","flight"]
Output: "fl"
Example 2:1
2
3Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
- All given inputs are in lowercase letters a-z.
这道题让我们求一系列字符串的共同前缀,没有什么特别的技巧,无脑查找即可,定义两个变量i和j,其中i是遍历搜索字符串中的字符,j是遍历字符串集中的每个字符串。这里将单词上下排好,则相当于一个各行长度有可能不相等的二维数组,遍历顺序和一般的横向逐行遍历不同,而是采用纵向逐列遍历,在遍历的过程中,如果某一行没有了,说明其为最短的单词,因为共同前缀的长度不能长于最短单词,所以此时返回已经找出的共同前缀。每次取出第一个字符串的某一个位置的单词,然后遍历其他所有字符串的对应位置看是否相等,如果有不满足的直接返回 res,如果都相同,则将当前字符存入结果,继续检查下一个位置的字符,参见代码如下:
C++ 解法一:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
string res = "";
for (int j = 0; j < strs[0].size(); ++j) {
char c = strs[0][j];
for (int i = 1; i < strs.size(); ++i) {
if (j >= strs[i].size() || strs[i][j] != c) {
return res;
}
}
res.push_back(c);
}
return res;
}
};
我们可以对上面的方法进行适当精简,如果发现当前某个字符和第一个字符串对应位置的字符不相等,说明不会再有更长的共同前缀了,直接通过用 substr 的方法直接取出共同前缀的子字符串。如果遍历结束前没有返回结果的话,说明第一个单词就是公共前缀,返回为结果即可。代码如下:
1 | class Solution { |
我们再来看一种解法,这种方法给输入字符串数组排了个序,想想这样做有什么好处?既然是按字母顺序排序的话,那么有共同字母多的两个字符串会被排到一起,而跟大家相同的字母越少的字符串会被挤到首尾两端,那么如果有共同前缀的话,一定会出现在首尾两端的字符串中,所以只需要找首尾字母串的共同前缀即可。比如例子1排序后为 [“flight”, “flow”, “flower”],例子2排序后为 [“cat”, “dog”, “racecar”],虽然例子2没有共同前缀,但也可以认为共同前缀是空串,且出现在首尾两端的字符串中。由于是按字母顺序排的,而不是按长度,所以首尾字母的长度关系不知道,为了防止溢出错误,只遍历而这种较短的那个的长度,找出共同前缀返回即可,参见代码如下:
1 | class Solution { |
Leetcode15. 3Sum
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:1
2
3
4
5
6
7Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
给定一个数组A,要求从A中找出这么三个元素a,b,c使得a + b + c = 0,返回由这样的a、b、c构成的三元组,且要保证三元组是唯一的。(即任意的两个三元组,它们里面的元素不能完全相同)
题解:
我们知道3和问题是由2和问题演化而来的,所以说我们可以根据2和问题的求法,来间接求解三和问题。常见的2和问题的求解方法,主要包括两种那:利用哈希表或者两用双指针。而三和问题,我们可以看成是在2和问题外面加上一层for循环,所以3和问题的常用解法也是分为两种:即利用哈希表和利用双指针。下面具体介绍两种方法:
方法1:利用哈希表
这种方法的基本思想是,将数组中每个元素和它的下标构成一个键值对存入到哈希表中,在寻找的过程中对于数组中的某两个元素a、b只需在哈希表中判断是否存在-a-b即可,由于在哈希表中的查找操作的时间复杂度为O(1),在数组中寻找寻任意的找两个元素a、b需要O(n^2),故总的时间复杂度为O(N^2)。代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution
{
public:
vector<vector<int> > threeSum(vector<int> &num)
{
vector<vector<int>> rs;
int len = num.size();
if(len == 0)
return rs;
sort(num.begin(),num.end());//排序是为了不重复处理后续重复出现的元素
for(int i = 0; i < len; i++)
{
if(i != 0 && num[i] == num[i - 1])//i重复出现时不重复处理
continue;
unordered_map<int,int> _map;//注意建立_map的位置
for(int j = i + 1; j < len; j++)
{
if(_map.find(-num[i]-num[j]) != _map.end())
{
rs.push_back({num[i],num[j],-num[i]-num[j]});
while(j + 1 < len && num[j] == num[j + 1])//j重复出现时不重复处理
j++;
}
_map.insert({num[j],j});//注意_map插入的元素是根据j来的不是根据i来的
}
}
return rs;
}
};
这种方法先对数组nums进行排序,然后在双重for循环中对哈希表进行操作,时间复杂度为O(N*logN)+O(N^2),所以总的时间复杂度为O(N^2),空间复杂度为O(N),典型的以时间换空间的策略。但是,有几个重要的点一定要掌握:
1.为什么要事先对数组nums进行排序?这是因为由于题目要求的是返回的三元组必须是重复的,如果直接利用哈希表不进行特殊处理的话,最终的三元组一定会包含重复的情况,所以我们对数组进行排序是为了对最终的结果进行去重,其中去重包括i重复的情况和j重复的情况分,不注意两种情况的处理方式是不同的,i是判断与i-1是否相同;而j是判断与j+1是否相同。
2.关于对三元组进行去重,实际上有两种方式:
(1)按照本例中的形式,先对数组进行排序,在遍历的过程中遇到重复元素的情况就跳过。
(2)不对数组事先排序,在遍历过程中不进行特殊的处理,在得到整个三元组集合后,在对集合中的三元组进行去重,删去重复的三元组。(一个简单的思路是对集合中每个三元组进行排序,然后逐个元素进行比较来判断三元组是否重复)。(这种思路可能会比本例中的方法性能更优一些)
3.注意哈希表建立的位置,是首先确定i的位置后,才开始创建哈希表的;而不是先建立哈希表,再根据i和j进行遍历。此外,哈希表中存储的元素是根据j的位置来决定的,相当于每次先固定一个i,然后建立一个新的哈希表,然后在遍历j,并根据j判断哈希表。(这个过程并不难理解,自己举个例子,画个图应该就明白了)
然而,我利用这种方法(上述代码),在leetcode上提交居然超时了!!!即方法1在leetcode没通过啊。
方法2:利用两个指针
这种方法是最常用的方法(leetcode上AC的代码大多都是这种方法),主要的思想是:必须先对数组进行排序(不排序的话,就不能利用双指针的思想了,所以说对数组进行排序是个大前提),每次固定i的位置,并利用两个指针j和k,分别指向数组的i+1位置和数组的尾元素,通过判断num[j]+num[k]与-num[i]的大小,来决定如何移动指针j和k,和leetcode上最大容器的拿到题目的思想类似。具体代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37class Solution
{
public:
vector<vector<int> > threeSum(vector<int> &num)
{
vector<vector<int>> rs;
int len = num.size();
if(len == 0)
return rs;
sort(num.begin(),num.end());
for(int i = 0; i < len; i++)
{
int j = i + 1;
int k = len - 1;
if(i != 0 && num[i] == num[i - 1])//如果遇到重复元素的情况,避免多次考虑
continue;
while(j < k)//对于每一个num[i]从i之后的元素中,寻找对否存在三者之和为0的情况
{
if(num[i] + num[j] +num[k] == 0)//当三者之和为0的情况
{
rs.push_back({num[i],num[j],num[k]});
j++;//当此处的j,k满足时,别忘了向前/向后移动,判断下一个是否也满足
k--;
while(j < k && num[j] == num[j - 1])//如果遇到j重复的情况,也要避免重复考虑
j++;
while(j < k && num[k] == num[k + 1])//如果遇到k重复的情况,也要避免重复考虑
k--;
}
else if(num[i] + num[j] + num[k] < 0)//三者之和小于0的情况,说明num[j]太小了,需要向后移动
j++;
else//三者之和大于0的情况,说明num[k]太大了,需要向前移动
k--;
}
}
return rs;
}
};
该方法的时间复杂度为O(N*logN)+O(N^2)=O(N^2)和方法1实际上是一个数量级的,但是空间复杂度为O(1),所以说综合比较的话,还是方法2的性能更好一些。同样地,这种方法也有几个需要注意的点:
- 需要先对数组进行排序,一开始的时候也强调了,不排序的话整个思路就是错的;这种方法的一切都是建立在有序数组的前提下。
- 每次找到符合条件的num[j]和num[k]时,这时候,j指针要往前移动一次,同时k指针向后移动一次,避免重复操作,从而判断下个元素是否也符合
- 和方法1一样,都需要去重(且去重时,一般都是在找到满足条件的元素时才执行),由于该方法一定要求数组是有序的,所以就按照第一种去重方法来去重就好了。但是需要注意下与第1种方法去重的不同之处:
- (1)i指针的去重同方法1一样,都是判断当前位置的元素与前一个位置的元素是否相同,如果相同,就忽略。这是因为前一个位置的元素已经处理过了,如果当前位置的元素与之相同的话,就没必要处理了,否则就会造成重复。
- (2)j指针(还有k指针)的去重方法同方法1是不同的。先分析下方法1:
如果num[j]是符合条件的元素的话,并且下一个元素同num[j]相同的话,那么就没必要再去判断了,直接跳过就行了。那如果把nums[j] == num[j+1]
改成num[j] == num[j-1]
行吗?显然不行啊,举个例子就行,假如num[j] == 1
且此时1正好符合,那么对于序列1,1….的话,当判断第一个1时,会把结果存入数组;如果改成num[j] == num[j-1]
的话,判断第二个1的时候,会先把元素存入数组,然后再判断和前一个元素是否相同;即实际上这样已经发生重复操作了,如果是nums[j] == num[j+1]
就是直接判断下一个元素,就是先判断在存储,就不会重复操作了。(也可以这样理解:由于去重操作只在找到重复元素的时候才进行,当num[j]
满足时,如果num[j+1]
也满足,则一定不用再判断了;而如果num[j-1]与num[j]
相同的话,反而会把num[j-1]
和num[j]
都存进去了)
分析下方法2:
对于方法2中的j指针和k指针,就比较好理解了;由于在判断是满足条件的元素的话,就会j++,k—,此时j和k的位置都发生了变化,就不知道是不是满足了,所以要根据前一个元素来判断,如果现在的元素与前一个元素(对于j来说就是j-1,对于k来说就是K+1)相同的话,就直接跳过,从而避免了重复操作。
与方法1中的j是不同的,方法1中的j并没有执行j++操作(或者说是后执行的j++)。方法2最终在leetcode上AC了,以后还是优先使用这种的方法吧!
以上问题都是针对2sum和3sum,那么对于4sum。。。ksum,上述解法也是可行的。所以对于Ksum问题来讲,通常有两种思路:
- 利用双指针。
- 利用哈希表。
这两种方法的本质都是,在外层有k-2层循环嵌套,最内层循环中采用双指针或者哈希表,所以总的时间复杂度为O(N^k-1)。对于Ksum问题,如果题目要求结果不能重复的话,一定要考虑去重,去重方法,上面第一个例子也讲了。
实际上,对于4sum问题,还有更优的解法。主要是利用哈希表,其中哈希表类为<int,vector<pair<int,int>>>
型,其中key表示的是数组中任意两个元素的和,value表示的这两个元素对应下标构成的pair,即pair,由于对于两组不同的元素(共4个)可能存在重复的和,即key值相同,所以value对应的是一个pair构成的数组。这样的话,后面只需要两次循环找出hash[target - num[i] - num[j]]
即可,所以总的时间复杂为O(N^2)
,空间复杂度也为O(N^2)
。(由于pair<int,int>
本质就是个哈希表,所以这种方法的实质就是嵌套哈希表)
Leetcode16. 3Sum Closest
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的距离(可以用绝对值表示),然后将距离最小的一组的和输出即可。这种方法是超时的,简单分析一下,可以知道时间复杂度为O(n^3).
通过分析,我们可以想到一种时间复杂度为O(n^2)
的解法:假设数组中有len个元素,首先我们将数组中的元素按照从小到大的顺序进行排序。其次,看最终取出的三个数中的第一个数,若数组长度为n,那么有n种取法。假设取的第一个数是A[i]
,那么第二三两个数从A[i+1]~A[len]
中取出。找到“第一个数为A[i]
固定,后两个数在A[i]
后面元素中取。并且三数之和离target最近的情况。”这时,我们用两个指针j,k分别指向A[i+1]
和A[len]
,如果此时三数之和A[i]+A[j]+A[k]<target
,说明三数之和小了,我们将j后移一格;反之,若和大于target,则将k前移一格;直到j和k相遇为止。在这期间,保留与target最近的三数之和。一旦发现有“和等于target的情况”,立即输出即可。
由于取的第一个数可以是A[0]
,A[1]
,A[2]
,……, A[len-1]
,所以需要重复以上步骤n次。
为什么第一个数取了A[i]
之后,第二三两个数只能在A[i+1]~A[len]
中取呢? 因为这样可以避免重复。假设第二个数取了A[i-2]
,那么这样情况势必会包含在第一个数取A[i-2]
的情况中。因为取出的三个数之间是没有顺序关系的。
1 | class Solution { |
Leetcod17. Letter Combinations of a Phone Number
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.
Example:
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
这道题让我们求电话号码的字母组合,即数字2到9中每个数字可以代表若干个字母,然后给一串数字,求出所有可能的组合。这里可以用递归 Recursion 来解,需要建立一个字典,用来保存每个数字所代表的字符串,然后还需要一个变量 level,记录当前生成的字符串的字符个数,实现套路和上述那些题十分类似。在递归函数中首先判断 level,如果跟 digits 中数字的个数相等了,将当前的组合加入结果 res 中,然后返回。我们通过 digits 中的数字到 dict 中取出字符串,然后遍历这个取出的字符串,将每个字符都加到当前的组合后面,并调用递归函数即可,参见代码如下:
简单深度优先搜索,别忘了调用完dfs之后还原就行………………1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class Solution {
public:
vector<string> dict;
void work(string digits, vector<string>& result, int cur, string& temp) {
if(cur == digits.length()) {
result.push_back(temp);
return;
}
for(int i=0;i<dict[digits[cur]-'0'].length();i++) {
temp+=dict[digits[cur]-'0'][i];
work(digits, result, cur+1, temp);
temp.erase(temp.length() - 1);
}
}
vector<string> letterCombinations(string digits) {
vector<string> result;
dict.push_back("");
dict.push_back("");
dict.push_back("abc");
dict.push_back("def");
dict.push_back("ghi");
dict.push_back("jkl");
dict.push_back("mno");
dict.push_back("pqrs");
dict.push_back("tuv");
dict.push_back("wxyz");
if(digits.length() == 0) {
return result;
}
string temp="";
work(digits, result, 0, temp);
return result;
}
};
Leetcode18. 4Sum
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. The solution set must not contain duplicate quadruplets.
Example:1
2
3
4
5
6
7Given 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]
]
题意
中文描述 给定一个数列 S ,包含 n 个整数.在 S 中找到四个元素 a, b, c, d 使得 a + b + c + d = target . 找到所有的独特的满足上述条件的四元组. 注意: 结果集包含的四元组不重复.
题解
算法及复杂度(45 ms) 本题与第 15 题 (3Sum) 比较类似,第 15 题是求三个数的和,本题是求四个数的和.建议先去练习第 15 题. 首先,为了避免结果的重复,先对数列进行排序.依照在 15 题中提到的: 在一段数列上找到和为固定值的两个数的复杂度可以为 O(n).于是,很简单的思路是: 先固定前两个数 nums[l1], nums[l2](使用两重循环),这样后两个数的和是固定的 target - nums[l1] - nums[l2] ,只需要在 (l2, len) 上进行和为固定值的两个数的寻找就可以了. 需要注意的是: 在算法运行过程中注意保证求出的结果不重复,控制方法参考AC代码。其实可以看出,即使求出的结果重复也可以在求出所有的结果后很容易找出所有不重复的结果,原因是根据求出的四元组的有序性。 在实现过程中,在一段数列上找到和为固定值的两个数直接使用了第 15 题中的 twoSum 函数。 时间复杂度: O(n ^ 3) . n 是数列的长度的, 排序时间复杂度为 O(nlogn) , 求解过程中:前两个数两重循环复杂度为 O(n ^ 2) , 后两个数查找过程复杂度为 O(n) , 总的时间复杂度为 O(nlogn) + O(n ^ 2) * O(n) , 即 O(n ^ 3) .
算法正确性
正确性证明 算法的正确性等同于枚举的正确性。 举个例子
1 | // 给定数列和target |
之后的步骤和之前类似1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int len = nums.size();
for(int i=0;i<len-3;i++) {
for(int j=i+1;j<len-2;j++) {
int left = j+1, right = len-1;
while(left < right){
int sum = nums[i]+nums[j]+nums[right]+nums[left];
if(sum == target) {
vector<int> out{nums[i], nums[j], nums[left], nums[right]};
res.push_back(out);
left ++;
right--;
while(left<right && nums[left]==nums[left-1]) left++; // 很重要的去重!
while(left<right && nums[right]==nums[right+1]) right--;// 很重要的去重!
} else if(sum > target) {
right --;
} else {
left ++;
}
}
while(j+1<len-2 && nums[j]==nums[j+1]) j++;
}
while(i+1<len-3 && nums[i]==nums[i+1]) i++;
}
return res;
}
};
Leetcode19. Remove Nth Node From End of List
Given a linked list, remove the n-th node from the end of list and return its head.
Example:1
2Given 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.
Note: Given n will always be valid.
Follow up: Could you do this in one pass?
这道题让我们移除链表倒数第n个节点,限定n一定是有效的,即n不会大于链表中的元素总数。还有题目要求一次遍历解决问题,那么就得想些比较巧妙的方法了。比如首先要考虑的时,如何找到倒数第n个节点,由于只允许一次遍历,所以不能用一次完整的遍历来统计链表中元素的个数,而是遍历到对应位置就应该移除了。那么就需要用两个指针来帮助解题,pre 和 cur 指针。首先 cur 指针先向前走N步,如果此时 cur 指向空,说明N为链表的长度,则需要移除的为首元素,那么此时返回 head->next
即可,如果 cur 存在,再继续往下走,此时 pre 指针也跟着走,直到 cur 为最后一个元素时停止,此时 pre 指向要移除元素的前一个元素,再修改指针跳过需要移除的元素即可,pre相当于计数器了,参见代码如下:
1 | class Solution { |
Leetcode20. Valid Parentheses
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.
Example 1:1
2Input: "()"
Output: true
Example 2:1
2Input: "()[]{}"
Output: true
Example 3:1
2Input: "(]"
Output: false
Example 4:1
2Input: "([)]"
Output: false
Example 5:1
2Input: "{[]}"
Output: true
算法及复杂度 (3 ms) 本题就是验证括号的顺序是否能保证正确匹配,通过自己简单的模拟就会发现:在括号的匹配过程中,右括号才是最重要的.每个右括号能且只能对应前边的一个左括号,因此每个右括号对应的左括号一定在前边出现,并且位置是确定的.
因此就萌生了一种模拟的思路: 遇到左括号就存起来,遇到右括号就进行匹配. 本题为什么想到用stack进行实现?在左括号的存储过程有很多结构进行实现,主要仔细分析右括号的匹配过程.不妨举个例子 s = “((()))”, 先用某种方式把左括号存起来,那么存储结果是 “(((“, 遇到第一个右括号,与前一个符号进行比对,发现是左括号(如果不是对应的左括号,就可以直接return false了,原因根据正确括号序列的定义),这样就进行了匹配,匹配成功之后,显然这一对括号已经没有作用了,因此就可以把这对括号覆盖掉或者删除掉,这里使用stack通过弹出顶部元素(即对应左括号)达到这个效果.
时间复杂度: O(n). n 表示括号序列的长度,只需要一次遍历就可以完成,因此是 O(n) 的复杂度.
正确性证明 模拟的思想,根据题目提供的方法在进行操作,提供的已知条件保证了算法的正确性. 举个例子1
2
3
4
5
6
7
8
9
10
11
12
13//输入序列
s = "([{)"
//分析s[0],左括号,入栈st
st = "("
//分析s[1],左括号,入栈st
st = "(["
//分析s[2],左括号,入栈st
st = "([{"
//分析s[3],右括号,尝试匹配st.top(),返现不匹配,返回false1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41class Solution {
public:
bool isValid(string s) {
if(s[0] == ')' || s[0] == '}' || s[0] == ']') {
return false;
} else if(s.length() == 0) {
return true;
}
stack<char>st;
st.push(s[0]);
for(int i = 1; i < s.length(); i ++) {
if(s[i] == ')') {
if(!st.empty() && st.top() == '(') {
st.pop();
} else {
return false;
}
}else if(!st.empty() && s[i] == '}') {
if(st.top() == '{') {
st.pop();
} else {
return false;
}
}else if(!st.empty() && s[i] == ']') {
if(st.top() == '[') {
st.pop();
} else {
return false;
}
} else {
st.push(s[i]);
}
}
if(st.size() == 0) {
return true;
}
return false;
}
};
Leetcode21. Merge Two Sorted Lists
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
1 | class Solution { |
Leetcode22. Generate Parentheses
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:1
2
3
4
5
6
7[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
这道题给定一个数字n,让生成共有n个括号的所有正确的形式,对于这种列出所有结果的题首先还是考虑用递归 Recursion 来解,由于字符串只有左括号和右括号两种字符,而且最终结果必定是左括号3个,右括号3个,所以这里定义两个变量 left 和 right 分别表示剩余左右括号的个数。
如果在某次递归时,左括号的个数大于右括号的个数,说明此时生成的字符串中右括号的个数大于左括号的个数,即会出现 ‘)(‘ 这样的非法串,所以这种情况直接返回,不继续处理。
如果 left 和 right 都为0,则说明此时生成的字符串已有3个左括号和3个右括号,且字符串合法,则存入结果中后返回。如果以上两种情况都不满足,若此时 left 大于0,则调用递归函数,注意参数的更新,若 right 大于0,则调用递归函数,同样要更新参数,参见代码如下:
1 | class Solution { |
Leetcode23. Merge k Sorted Lists
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:1
2
3
4
5
6
7
8
9
10Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:1
2Input: lists = []
Output: []
Example 3:1
2Input: lists = [[]]
Output: []
借助分治的思想,把 K 个有序链表两两合并即可。相当于是第 21 题的加强版。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* ans = NULL;
if (lists.size() == 0)
return NULL;
ans = new ListNode(-1);
for (int i = 0; i < lists.size(); i ++) {
ListNode* l1 = ans, *l2 = lists[i];
while(l2) {
ListNode* tmp = l2->next;
while(l1 && l1->next && l1->next->val < l2->val)
l1 = l1->next;
l2->next = l1->next;
l1->next = l2;
l2 = tmp;
}
}
return ans->next;
}
};
这里就需要用到分治法 Divide and Conquer Approach。简单来说就是不停的对半划分,比如k个链表先划分为合并两个 k/2 个链表的任务,再不停的往下划分,直到划分成只有一个或两个链表的任务,开始合并。举个例子来说比如合并6个链表,那么按照分治法,首先分别合并0和3,1和4,2和5。这样下一次只需合并3个链表,再合并1和3,最后和2合并就可以了。代码中的k是通过 (n+1)/2 计算的,这里为啥要加1呢,这是为了当n为奇数的时候,k能始终从后半段开始,比如当 n=5 时,那么此时 k=3,则0和3合并,1和4合并,最中间的2空出来。当n是偶数的时候,加1也不会有影响,比如当 n=4 时,此时 k=2,那么0和2合并,1和3合并,完美解决问题,参见代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return NULL;
int n = lists.size();
while (n > 1) {
int k = (n + 1) / 2;
for (int i = 0; i < n / 2; ++i) {
lists[i] = mergeTwoLists(lists[i], lists[i + k]);
}
n = k;
}
return lists[0];
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(-1), *cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) cur->next = l1;
if (l2) cur->next = l2;
return dummy->next;
}
};
Leetcode24. Swap Nodes in Pairs
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.
Example: Given 1->2->3->4, you should return the list as 2->1->4->3.
1 | class Solution { |
1 | class Solution { |
Leetcode25. Reverse Nodes in k-Group
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.
Example:
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
Note:
Only constant extra memory is allowed.
You may not alter the values in the list’s nodes, only nodes itself may be changed.
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
把一个很长的链表分成很多个小链表,每一份的长度都是 k (最后一份的长度如果小于 k 则不需要反转),然后对每个小链表进行反转,最后将所有反转后的小链表按之前的顺序拼接在一起。
- 第一,在反转子链表的时候,上一个子链表的尾必须知道
- 第二,下一个子链表的头也必须知道
- 第三,当前反转的链表的头尾都必须知道
1 | class Solution { |
Leetcode26. Remove Duplicates from Sorted Array
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.
Example 1:1
2
3
4
5Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:1
2
3
4
5Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:1
2
3
4
5
6
7
8// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
真的是非常简单的一道题,但是因为某种原因WA了好几次。。。去掉重复的数并返回去重之后的长度。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int length=nums.size();
if(length==0)
return 0;
int j=0;
for(int i=1;i<length;i++){
if(nums[i]!=nums[j]){
j++;
nums[j]=nums[i];
}
}
return j+1;
}
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0)
return 0;
int prev = nums[0];
int res = 1;
for(int i = 1; i < nums.size(); i ++) {
if(prev != nums[i]) {
prev = nums[i];
nums[res] = nums[i];
res ++;
}
}
return res;
}
};
Leetcode27. Remove Element
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.
Example 1:1
2
3Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length.
Example 2:1
2Given nums = [0,1,2,2,3,0,4,2], val = 2,
Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
Note that the order of those five elements can be arbitrary.
It doesn’t matter what values are set beyond the returned length.
Clarification: Confused why the returned value is an integer but your answer is an array? Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:1
2
3
4
5
6
7
8// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
双指针做法,两个指针分别指向要被删除的值。1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int cur = 0, size = nums.size();
for(int i = 0; i < size; i ++) {
if(val != nums[i])
nums[cur++] = nums[i];
}
return cur;
}
};
Leetcode28. Implement strStr()
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:1
2Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:1
2Input: haystack = "aaaaa", needle = "bba"
Output: -1
1 | class Solution { |
Leetcode29. Divide Two Integers
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.
Example 1:1
2
3Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.
Example 2:1
2
3Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.
一开始我用被除数一次一次地减除数,这样太慢了,遇到被除数为2147483648除数为1的情况就挂了。可以用被除数不断地减除数的1倍、2倍、4倍、8倍…这样就快了。使用位运算,被除数与除数同号时商为正,异号时商为负。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
int divide(int dividend, int divisor) {
if(divisor == 0 || (dividend == INT_MIN && divisor == -1))
return INT_MAX;
int sign = ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) ? 1 : -1;
long dd = labs(dividend);
long ds = labs(divisor);
long q = 0;
while(dd >= ds) {
long k = 0, temp = ds;
while(dd >= temp) {
q += (1 << k);
dd -= temp;
temp = temp << 1;
k += 1;
}
}
return q * sign;
}
};
这道题让我们求两数相除,而且规定不能用乘法,除法和取余操作,那么这里可以用另一神器位操作 Bit Manipulation,思路是,如果被除数大于或等于除数,则进行如下循环,定义变量t等于除数,定义计数p,当t的两倍小于等于被除数时,进行如下循环,t扩大一倍,p扩大一倍,然后更新 res 和m。这道题的 OJ 给的一些 test case 非常的讨厌,因为输入的都是 int 型,比如被除数是 -2147483648,在 int 范围内,当除数是 -1 时,结果就超出了 int 范围,需要返回 INT_MAX,所以对于这种情况就在开始用 if 判定,将其和除数为0的情况放一起判定,返回 INT_MAX。然后还要根据被除数和除数的正负来确定返回值的正负,这里采用长整型 long 来完成所有的计算,最后返回值乘以符号即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == INT_MIN && divisor == -1) return INT_MAX;
long m = labs(dividend), n = labs(divisor), res = 0;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
if (n == 1) return sign == 1 ? m : -m;
while (m >= n) {
long t = n, p = 1;
while (m >= (t << 1)) {
t <<= 1;
p <<= 1;
}
res += p;
m -= t;
}
return sign == 1 ? res : -res;
}
};
Leetcode30. Substring with Concatenation of All Words
You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.
You can return the answer in any order.
Example 1:1
2
3
4Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:1
2Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Example 3:1
2Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
这道题让我们求串联所有单词的子串,就是说给定一个长字符串,再给定几个长度相同的单词,让找出串联给定所有单词的子串的起始位置,还是蛮有难度的一道题。假设 words 数组中有n个单词,每个单词的长度均为 len,那么实际上这道题就让我们出所有长度为 nxlen 的子串,使得其刚好是由 words 数组中的所有单词组成。那么就需要经常判断s串中长度为 len 的子串是否是 words 中的单词,为了快速的判断,可以使用 HashMap,同时由于 words 数组可能有重复单词,就要用 HashMap 来建立所有的单词和其出现次数之间的映射,即统计每个单词出现的次数。
遍历s中所有长度为 nxlen 的子串,当剩余子串的长度小于 nxlen 时,就不用再判断了。所以i从0开始,到 (int)s.size() - nxlen 结束就可以了,注意这里一定要将 s.size() 先转为整型数,再进行解法。一定要形成这样的习惯,一旦 size() 后面要减去数字时,先转为 int 型,因为 size() 的返回值是无符号型,一旦减去一个比自己大的数字,则会出错。对于每个遍历到的长度为 nxlen 的子串,需要验证其是否刚好由 words 中所有的单词构成,检查方法就是每次取长度为 len 的子串,看其是否是 words 中的单词。为了方便比较,建立另一个 HashMap,当取出的单词不在 words 中,直接 break 掉,否则就将其在新的 HashMap 中的映射值加1,还要检测若其映射值超过原 HashMap 中的映射值,也 break 掉,因为就算当前单词在 words 中,但若其出现的次数超过 words 中的次数,还是不合题意的。在 for 循环外面,若j正好等于n,说明检测的n个长度为 len 的子串都是 words 中的单词,并且刚好构成了 words,则将当前位置i加入结果 res 即可,具体参见代码如下:
1 | class Solution { |
这道题还有一种 O(n) 时间复杂度的解法,设计思路非常巧妙,但是感觉很难想出来,博主目测还未到达这种水平。这种方法不再是一个字符一个字符的遍历,而是一个词一个词的遍历,比如根据题目中的例子,字符串s的长度n为 18,words 数组中有两个单词 (cnt=2),每个单词的长度 len 均为3,那么遍历的顺序为 0,3,6,8,12,15,然后偏移一个字符 1,4,7,9,13,16,然后再偏移一个字符 2,5,8,10,14,17,这样就可以把所有情况都遍历到,还是先用一个 HashMap m1 来记录 words 里的所有词,然后从0开始遍历,用 left 来记录左边界的位置,count 表示当前已经匹配的单词的个数。然后一个单词一个单词的遍历,如果当前遍历的到的单词t在 m1 中存在,那么将其加入另一个 HashMap m2 中,如果在 m2 中个数小于等于 m1 中的个数,那么 count 自增1,如果大于了,则需要做一些处理,比如下面这种情况:s = barfoofoo, words = {bar, foo, abc},给 words 中新加了一个 abc ,目的是为了遍历到 barfoo 不会停止,当遍历到第二 foo 的时候,m2[foo]=2
,而此时m1[foo]=1
,这时候已经不连续了,所以要移动左边界 left 的位置,先把第一个词t1=bar
取出来,然后将m2[t1]
自减1,如果此时m2[t1]<m1[t1]
了,说明一个匹配没了,那么对应的 count 也要自减1,然后左边界加上个 len,这样就可以了。如果某个时刻 count 和 cnt 相等了,说明成功匹配了一个位置,将当前左边界 left 存入结果 res 中,此时去掉最左边的一个词,同时 count 自减1,左边界右移 len,继续匹配。如果匹配到一个不在 m1 中的词,说明跟前面已经断开了,重置 m2,count 为0,左边界 left 移到 j+len,参见代码如下:
解法二:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
if (s.empty() || words.empty()) return {};
vector<int> res;
int n = s.size(), cnt = words.size(), len = words[0].size();
unordered_map<string, int> m1;
for (string w : words) ++m1[w];
for (int i = 0; i < len; ++i) {
int left = i, count = 0;
unordered_map<string, int> m2;
for (int j = i; j <= n - len; j += len) {
string t = s.substr(j, len);
if (m1.count(t)) {
++m2[t];
if (m2[t] <= m1[t]) {
++count;
} else {
while (m2[t] > m1[t]) {
string t1 = s.substr(left, len);
--m2[t1];
if (m2[t1] < m1[t1]) --count;
left += len;
}
}
if (count == cnt) {
res.push_back(left);
--m2[s.substr(left, len)];
--count;
left += len;
}
} else {
m2.clear();
count = 0;
left = j + len;
}
}
}
return res;
}
};
Leetcode31. Next Permutation
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
31,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
这道题让我们求下一个排列顺序,由题目中给的例子可以看出来,如果给定数组是降序,则说明是全排列的最后一种情况,则下一个排列就是最初始情况,可以参见之前的博客 Permutations。再来看下面一个例子,有如下的一个数组1 2 7 4 3 1
,下一个排列为:1 3 1 2 4 7
。
那么是如何得到的呢,我们通过观察原数组可以发现,如果从末尾往前看,数字逐渐变大,到了2时才减小的,然后再从后往前找第一个比2大的数字,是3,那么我们交换2和3,再把此时3后面的所有数字转置一下即可,步骤如下:1
2
3
41 2 7 4 3 1
1 2 7 4 3 1
1 3 7 4 2 1
1 3 1 2 4 71
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
void nextPermutation(vector<int>& nums) {
for(int i = nums.size()-2; i >= 0; i --) {
if(nums[i] < nums[i+1]) {
int j;
for(j = nums.size()-1; j > i; j --)
if(nums[j] > nums[i])
break;
swap(nums[i], nums[j]);
reverse(nums.begin()+i+1, nums.end());
return;
}
}
reverse(nums.begin(), nums.end());
}
};
Leetcode32. Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example 1:1
2
3Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
Example 2:1
2
3Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
Example 3:1
2Input: s = ""
Output: 0
这道求最长有效括号比之前那道 Valid Parentheses 难度要大一些,这里还是借助栈来求解,需要定义个 start 变量来记录合法括号串的起始位置,遍历字符串,如果遇到左括号,则将当前下标压入栈,如果遇到右括号,如果当前栈为空,则将下一个坐标位置记录到 start,如果栈不为空,则将栈顶元素取出,此时若栈为空,则更新结果和 i - start + 1 中的较大值,否则更新结果和 i - st.top() 中的较大值,参见代码如下:
解法一:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int longestValidParentheses(string s) {
int res = 0, start = 0, n = s.size();
stack<int> st;
for (int i = 0; i < n; ++i) {
if (s[i] == '(') st.push(i);
else if (s[i] == ')') {
if (st.empty()) start = i + 1;
else {
st.pop();
res = st.empty() ? max(res, i - start + 1) : max(res, i - st.top());
}
}
}
return res;
}
};
还有一种利用动态规划 Dynamic Programming 的解法,可参见网友喜刷刷的博客。这里使用一个一维 dp 数组,其中 dp[i] 表示以 s[i-1] 结尾的最长有效括号长度(注意这里没有对应 s[i],是为了避免取 dp[i-1] 时越界从而让 dp 数组的长度加了1),s[i-1] 此时必须是有效括号的一部分,那么只要 dp[i] 为正数的话,说明 s[i-1] 一定是右括号,因为有效括号必须是闭合的。当括号有重合时,比如 “(())”,会出现多个右括号相连,此时更新最外边的右括号的 dp[i] 时是需要前一个右括号的值 dp[i-1],因为假如 dp[i-1] 为正数,说明此位置往前 dp[i-1] 个字符组成的子串都是合法的子串,需要再看前面一个位置,假如是左括号,说明在 dp[i-1] 的基础上又增加了一个合法的括号,所以长度加上2。但此时还可能出现的情况是,前面的左括号前面还有合法括号,比如 “()(())”,此时更新最后面的右括号的时候,知道第二个右括号的 dp 值是2,那么最后一个右括号的 dp 值不仅是第二个括号的 dp 值再加2,还可以连到第一个右括号的 dp 值,整个最长的有效括号长度是6。所以在更新当前右括号的 dp 值时,首先要计算出第一个右括号的位置,通过 i-3-dp[i-1] 来获得,由于这里定义的 dp[i] 对应的是字符 s[i-1],所以需要再加1,变成 j = i-2-dp[i-1],这样若当前字符 s[i-1] 是左括号,或者j小于0(说明没有对应的左括号),或者 s[j] 是右括号,此时将 dp[i] 重置为0,否则就用 dp[i-1] + 2 + dp[j] 来更新 dp[i]。这里由于进行了 padding,可能对应关系会比较晕,大家可以自行带个例子一步一步执行,应该是不难理解的,参见代码如下:
1 | class Solution { |
此题还有一种不用额外空间的解法,使用了两个变量 left 和 right,分别用来记录到当前位置时左括号和右括号的出现次数,当遇到左括号时,left 自增1,右括号时 right 自增1。对于最长有效的括号的子串,一定是左括号等于右括号的情况,此时就可以更新结果 res 了,一旦右括号数量超过左括号数量了,说明当前位置不能组成合法括号子串,left 和 right 重置为0。但是对于这种情况 “(()” 时,在遍历结束时左右子括号数都不相等,此时没法更新结果 res,但其实正确答案是2,怎么处理这种情况呢?答案是再反向遍历一遍,采取类似的机制,稍有不同的是此时若 left 大于 right 了,则重置0,这样就可以 cover 所有的情况了,参见代码如下:
1 | class Solution { |
Leetcode33. Search in Rotated Sorted Array
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).
Example 1:1
2Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:1
2Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
这道题让在旋转数组中搜索一个给定值,若存在返回坐标,若不存在返回 -1。我们还是考虑二分搜索法,但是这道题的难点在于不知道原数组在哪旋转了。
二分搜索法的关键在于获得了中间数后,判断下面要搜索左半段还是右半段。如果中间的数小于最右边的数,则右半段是有序的,若中间数大于最右边数,则左半段是有序的,我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内,这样就可以确定保留哪半边了。
1 | class Solution { |
Leetcode34. Find First and Last Position of Element in Sorted Array
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].
Example 1:1
2Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:1
2Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
这道题让我们在一个有序整数数组中寻找相同目标值的起始和结束位置,而且限定了时间复杂度为 O(logn),这是典型的二分查找法的时间复杂度,所以这里也需要用此方法,思路是首先对原数组使用二分查找法,找出其中一个目标值的位置,然后向两边搜索找出起始和结束的位置。我以为要用什么高级算法呢,没想到只是一个简单的二分。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0)
return {-1, -1};
if(nums.size() == 1)
if(nums[0] == target)
return {0, 0};
else
return {-1, -1};
int n1 = -1, n2 = -1;
int len = nums.size();
int left = 0, right = len-1, mid;
while(left <= right) {
mid = left + (right - left) / 2;
if(nums[mid] > target)
right = mid - 1;
else if(nums[mid] < target)
left = mid + 1;
else
break;
}
if(nums[mid] != target)
return {-1, -1};
int i, j;
for(i = mid; i < len-1; i ++) {
if(nums[i+1] != nums[mid])
break;
}
for(j = mid; j >= 1; j --) {
if(nums[j-1] != nums[mid])
break;
}
return {j, i};
}
};
Leetcode35. Search Insert Position
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.
Example 1:1
2Input: [1,3,5,6], 5
Output: 2
Example 2:1
2Input: [1,3,5,6], 2
Output: 1
Example 3:1
2Input: [1,3,5,6], 7
Output: 4
Example 4:1
2Input: [1,3,5,6], 0
Output: 0
只是搜索需要插入的位置罢了,很简单,遍历或者二分都行。1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(target <= nums[0])
return 0;
for(int i = 1; i < nums.size(); i ++) {
if(target <= nums[i])
return i;
}
return nums.size();
}
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(target <= nums[0])
return 0;
int l = 0, r = nums.size(), mid;
while(l < r) {
mid = (l + r) / 2;
if(nums[mid] >= target)
r = mid;
else
l = mid + 1;
}
return r;
}
};
Leetcode36. Valid Sudoku
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.
Example 1:1
2
3
4
5
6
7
8
9
10
11
12
13Input:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: true
Example 2:1
2
3
4
5
6
7
8
9
10
11
12
13Input:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
The given board contain only digits 1-9 and the character ‘.’.
The given board size is always 9x9.
横向、纵向不能存在重复的,而这道题目还加上了每一个3*3
的九宫格也不能存在重复元素。根据上述分析,比较自然的可以想到创建三个列表储存目标数据,然而进行比较是否存在重复元素,进而进行相关判断。其中对于3*3的九宫格的索引值计算是一个需要思考的点。
1 | class Solution { |
Leetcode37. Sudoku Solver
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 digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
The ‘.’ character indicates empty cells.
Input:1
2
3
4
5
6
7
8
9board = [["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
Output:1
2
3
4
5
6
7
8
9[["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]
一种实现形式是递归带上横纵坐标,由于是一行一行的填数字,且是从0行开始的,所以当i到达9的时候,说明所有的数字都成功的填入了,直接返回 ture。当j大于等于9时,当前行填完了,需要换到下一行继续填,则继续调用递归函数,横坐标带入 i+1。否则看若当前数字不为点,说明当前位置不需要填数字,则对右边的位置调用递归。若当前位置需要填数字,则应该尝试填入1到9内的所有数字,让c从1遍历到9,每当试着填入一个数字,都需要检验是否有冲突,使用另一个子函数 isValid 来检验是否合法,假如不合法,则跳过当前数字。若合法,则将当前位置赋值为这个数字,并对右边位置调用递归,若递归函数返回 true,则说明可以成功填充,直接返回 true。不行的话,需要重置状态,将当前位置恢复为点。若所有数字都尝试了,还是不行,则最终返回 false。检测当前数组是否合法的原理跟之前那道 Valid Sudoku 非常的相似,但更简单一些,因为这里只需要检测新加入的这个数字是否会跟其他位置引起冲突,分别检测新加入数字的行列和所在的小区间内是否有重复的数字即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
helper(board, 0, 0);
}
bool helper(vector<vector<char>>& board, int i, int j) {
if(i == 9)
return true;
if (j == 9)
return helper(board, i+1, 0);
if (board[i][j] != '.')
return helper(board, i, j+1);
for (int k = '1'; k <= '9'; k ++) {
if (isValid(board, i, j, k)) {
board[i][j] = k;
if (helper(board, i, j+1))
return true;
board[i][j] = '.';
}
}
return false;
}
bool isValid(vector<vector<char>>& board, int i, int j, char val) {
for (int k = 0; k < 9; k ++)
if (board[i][k] == val)
return false;
for (int k = 0; k < 9; k ++)
if (board[k][j] == val)
return false;
i /= 3; i *= 3;
j /= 3; j *= 3;
for (int k = 0; k < 3; k ++)
for (int kk = 0; kk < 3; kk ++)
if (board[i+k][j+kk] == val)
return false;
return true;
}
};
Leetcode38. Count and Say
The count-and-say sequence is the sequence of integers with the first five terms as following:
- 1
- 11
- 21
- 1211
- 111221
- 1 is read off as “one 1” or 11.
- 11 is read off as “two 1s” or 21.
- 21 is read off as “one 2, then one 1” or 1211.
Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:1
2
3Input: 1
Output: "1"
Explanation: This is the base case.
Example 2:1
2
3Input: 4
Output: "1211"
Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and value = 2, the same way "1" is read as "11", so the answer is the concatenation of "12" and "11" which is "1211".
题意是n=1时输出字符串1;n=2时,数上次字符串中的数值个数,因为上次字符串有1个1,所以输出11;n=3时,由于上次字符是11,有2个1,所以输出21;n=4时,由于上次字符串是21,有1个2和1个1,所以输出1211。依次类推,写个countAndSay(n)函数返回字符串。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
string countAndSay(int n) {
if(n == 1)
return "1";
string str = countAndSay(n-1) + ' ';
int count = 1;
string s = "";
for(int i = 0; i < str.length() - 1; i ++){
if(str[i] == str[i+1]){
count++;
}
else {
s = s + to_string(count) + str[i];
count = 1;
}
}
return s;
}
};
Leetcode39. Combination Sum
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.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:1
2
3
4
5
6Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:1
2
3
4
5
6
7Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
本题采用回溯算法。
- 基本思路是先排好序,这样做的目的是为了对数组后面不可能出现的情况进行排除,有利于减少查找时间,即剪枝操作
- 外层循环对数组元素依次进行遍历,依次将 nums 中的元素加入中间集,一旦满足条件,就将中间集加入结果集
- 然后每次递归中把剩下的元素一一加到结果集合中,并且把目标减去加入的元素,然后把剩下元素(包括当前加入的元素)放到下一层递归中解决子问题。
1 | class Solution { |
Leetcode40. Combination Sum II
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.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
Example 1:1
2
3
4
5
6
7
8Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:1
2
3
4
5
6Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
我的dfs,一开始没有剪枝,所以很慢,首先排序,然后在dfs的时候,如果有必要就return,如果碰到相同的跳过。排序很重要:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution{
public:
vector<vector<int> > result;
void dfs(vector<int> candidates, int i, int length, vector<int> res, int current){
if(current == 0) {
result.push_back(res);
return;
}
else if(current < 0)
return;
for(int ii = i; ii < length; ii ++){
if(ii > i && candidates[ii] == candidates[ii-1])
continue;
res.push_back(candidates[ii]);
dfs(candidates, ii+1, length, res, current - candidates[ii]);
res.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target){
sort(candidates.begin(), candidates.end());
dfs(candidates, 0, candidates.size(), vector<int>{}, target);
return result;
}
};
大佬的做法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution{
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> current;
sort(candidates.begin(),candidates.end());
backTracking(candidates.begin(),current,res,candidates,target);
return res;
}
void backTracking(vector<int>::iterator n, vector<int>& current, vector<vector<int>>& res, const vector<int>& candidates, int target){
if(!target)
res.push_back(current);
else if(target > 0){
for( ; n != candidates.end() && *n <= target; ++ n){
current.push_back(*n);
backTracking(n+1, current, res, candidates, target-*n);
current.pop_back();
while(n + 1 != candidates.end() && *(n+1) == *n)
++n;
}
}
}
};
Leetcode41. First Missing Positive
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:1
2Input: [1,2,0]
Output: 3
Example 2:1
2Input: [3,4,-1,1]
Output: 2
Example 3:1
2Input: [7,8,9,11,12]
Output: 1
Note:
Your algorithm should run in O(n) time and uses constant extra space.
把出现的数值放到与下标一致的位置,再判断什么位置最先出现不连续的数值,就是答案了。
在判断的时候,只要是已经到位了的元素即:A[i] - 1 == i
了,那么判断如果有重复元素两个位置交换就最好考虑好两个位置出现的可能情况。考虑问题全面,两个条件都考虑好。
增加i!=A[i]表示i位置没到位,A[A[i]-1] != A[i]表示A[i]-1位置没到位,两个位置都判断也很好的。
1 | class Solution { |
Leetcode42. Trapping Rain Water
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.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
给你n个非负整数表示n个连续区域各自的海拔,每个区域宽度为1,问一场足够大的雨后有多少单位的水能储存在里面。也可以理解成在一个有若干黑块和白块的矩形中,有多少个白块的左边和右边(不一定相邻)都至少有一个黑块。
解题思路(1):
可以开个二维矩阵存每个位置是黑块还是白块,然后一行一行扫描,记下最左和左右的黑块位置l、r和总黑块数cnt,这一行的答案就为r-l-cnt+2,最终答案就是每一行的答案和。这种方法时空复杂度都为O(n*max(height)),当数据很大的时候这种方法是不能接受的。
解题思路(2):
开两个栈,一个栈s存海拔,另一个栈id存该海拔对应的位置。对n个海拔从左往右扫描,对第i个海拔为height[i]的区域,初始化之前海拔变量pre为0,检查栈顶,当栈不空且s栈的栈顶海拔s.top()<=height[i]
的时候,重复下列操作:答案增加(i-id.top()-1)*(s.top()-pre)
,然后pre更新为s.top()
,弹出两个栈的栈顶。需要注意的是退出来后如果栈不空则还要增加答案(i-id.top()-1)*(height[i]-pre)
,然后再把height[i]
和i分别压入s和id栈。这个思路时空复杂度均为O(n),完全可以接受。
算法正确性:
算法的关键点在于栈的存储和答案计算的部分。关于栈的存储,由于扫描是从左往右进行的,因此如果出现一个高海拔区域会把左边所有低海拔区域都挡住,后面的计算就不需要用到这些低海拔的区域了,所以从栈底到栈顶海拔逐渐减小。关于答案计算,可以理解为从低到高依次计算一个小矩形的面积,长为当前区域和栈顶区域的距离,宽为栈顶或当前区域与上次计算区域的高度差。
下面举一个简单例子走一遍算法帮助理解:[2,1,0,4,2,3]。初始时s栈和id栈均为空,答案ans为0。
第一步:height[0]=2,pre置为0,检查栈顶,栈s为空,直接将2压入s栈,0压入id栈;
第二步:height[1]=1,pre置为0,检查栈顶,s.top()=2>1,直接将1压入s栈,1压入id栈;
第三步:height[2]=0,pre置为0,检查栈顶,s.top()=1>0,直接将0压入s栈,2压入id栈;
第四步:height[3]=4,pre置为0,检查栈顶,s.top()=0<4,ans增加(i-id.top()-1)(s.top()-pre)=0
,pre=s.top()=0
,弹出s和id栈的栈顶,继续;
检查栈顶,s.top()=1<4
,ans增加(i-id.top()-1)(s.top()-pre)=1
,pre=s.top()=1
,弹出s和id栈的栈顶,继续;
检查栈顶,s.top()=2<4
,ans增加(i-id.top()-1)(s.top()-pre)=2
,pre=s.top()=2
,弹出s和id栈的栈顶,继续;
检查栈顶,栈s为空,直接将4压入s栈,3压入id栈;
第五步:height[4]=2,pre置为0,检查栈顶,s.top()=4>2,直接将2压入s栈,4压入id栈;
第六步:height[5]=3,pre置为0,检查栈顶,s.top()=2<3,ans增加(i-id.top()-1)(s.top()-pre)=0
,pre=s.top()=0
,弹出s和id栈的栈顶,继续;
检查栈顶,s.top()=4<3,跳出,ans增加(i-id.top()-1)*(s.top()-pre)=1
,pre=s.top()=2
,将3压入s栈,5压入id栈。
最终ans为4。
1 | int trap(vector<int>& height) |
这种方法是基于动态规划 Dynamic Programming 的,维护一个一维的 dp 数组,这个 DP 算法需要遍历两遍数组,第一遍在 dp[i] 中存入i位置左边的最大值,然后开始第二遍遍历数组,第二次遍历时找右边最大值,然后和左边最大值比较取其中的较小值,然后跟当前值 A[i] 相比,如果大于当前值,则将差值存入结果,参见代码如下:
1 | class Solution { |
Leetcode43. Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:1
2Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:1
2Input: num1 = "123", num2 = "456"
Output: "56088"
大数乘法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class Solution {
public:
string multiply(string num1, string num2) {
int xx = 0;
int len1 = num1.length(), len2 = num2.length();
vector<int> res(len1*len2+2, 0);
int i;
for(i = len1-1; i >= 0; i --) {
for(int j = len2-1; j >= 0; j --) {
int ii = len1-1-i;
int jj = len2-1-j;
res[ii + jj] += (num1[i] - '0') * (num2[j] - '0');
xx = ii + jj;
int k = 0;
while(res[ii + jj + k] > 9) {
res[ii + jj + 1 + k] = (res[ii + jj + 1 + k] + res[ii + jj + k] / 10);
res[ii + jj + k] %= 10;
xx = ii + jj + 1 + k;
k ++;
}
}
}
string ress(xx+1, '0');
for(i = len1*len2+1; i >= 0; i --)
if(res[i] != 0)
break;
if(i == -1)
return "0";
for(int kk = 0; i >= 0; i --, kk ++)
ress[kk] = res[i] + '0';
return ress;
}
};
大佬的做法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59class Solution {
public:
// The key idea is based on how we compute the product.
// For emaple, 1234 x 123
// 1) we first compute 1234 x 3 and save the results to the string,
// 2) then we compute 1234 x 2, and notice that we will start from update
// the results from 10th
// 3) now 1234 x 1, update from 100th.
// To make the code simple, we reverse the input string so that we can use
// k = 0, 1 (10th), 2 (100th), 3 (1,000th), ... to update the results.
// In the end we just reverse the string.
// Time : O(len(num1) * len(num2))
string multiply(string num1, string num2) {
if( num1 == "0" || num2 == "0") return "0";
if( num1 == "1") return num2;
if( num2 == "1") return num1;
std::reverse(num1.begin(), num1.end());
std::reverse(num2.begin(), num2.end());
string ans="";
ans.reserve(num1.size() * num2.size());
int k = 0;
for(size_t i=0;i<num2.size();++i,++k){
multiply(num1, num2[i], ans, k);
}
std::reverse(ans.begin(), ans.end());
return ans;
}
int toNumber(char c) { return int(c - '0');}
// multiple a char to a string and updat the result in the resultant string
// k: the starting postion that we start to update the resultant string
void multiply(const string& num, const char c, std::string& res, int k){
int remain = 0;
for(size_t i=0;i<num.size();++i){
int prod = toNumber(num[i]) * toNumber(c) + remain;
if(res.size()<=k) {
remain = prod / 10;
res.push_back((prod - remain * 10)+'0');
}
else{
prod += int(res[k] - '0');
remain = prod / 10;
res[k] = prod - remain * 10 +'0';
}
++k;
}
if (remain != 0){
for(size_t i=k;i<res.size();++i){
int sum = int(res[i]-'0') + remain;
remain = sum / 10;
res[i] = sum - remain * 10+'0';
if (remain == 0){
break;
}
}
if (remain != 0) res.push_back(remain+'0');
}
}
};
Leetcode44. Wildcard Matching
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’ where:
- ‘?’ Matches any single character.
- ‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Example 1:1
2
3Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:1
2
3Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:1
2
3Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:1
2
3Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:1
2Input: s = "acdcb", p = "a*c?b"
Output: false
动态规划 Dynamic Programming 是一大神器,因为字符串跟其子串之间的关系十分密切,正好适合 DP 这种靠推导状态转移方程的特性。那么先来定义dp数组吧,使用一个二维 dp 数组,其中 dp[i][j] 表示 s中前i个字符组成的子串和p中前j个字符组成的子串是否能匹配。大小初始化为 (m+1) x (n+1),加1的原因是要包含 dp[0][0] 的情况,因为若s和p都为空的话,也应该返回 true,所以也要初始化 dp[0][0] 为 true。还需要提前处理的一种情况是,当s为空,p为连续的星号时的情况。由于星号是可以代表空串的,所以只要s为空,那么连续的星号的位置都应该为 true,所以先将连续星号的位置都赋为 true。然后就是推导一般的状态转移方程了,如何更新 dp[i][j],首先处理比较 tricky 的情况,若p中第j个字符是星号,由于星号可以匹配空串,所以如果p中的前 j-1 个字符跟s中前i个字符匹配成功了( dp[i][j-1] 为true)的话,则 dp[i][j] 也能为 true。或者若p中的前j个字符跟s中的前i-1个字符匹配成功了( dp[i-1][j] 为true )的话,则 dp[i][j] 也能为 true(因为星号可以匹配任意字符串,再多加一个任意字符也没问题)。若p中的第j个字符不是星号,对于一般情况,假设已经知道了s中前 i-1 个字符和p中前 j-1 个字符的匹配情况(即 dp[i-1][j-1] ),现在只需要匹配s中的第i个字符跟p中的第j个字符,若二者相等( s[i-1] == p[j-1] ),或者p中的第j个字符是问号( p[j-1] == ‘?’ ),再与上 dp[i-1][j-1] 的值,就可以更新 dp[i][j] 了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
bool isMatch(string s, string p) {
int len1 = s.length(), len2 = p.length();
bool dp[len1+1][len2+1];
memset(dp, 0, sizeof(bool)*(len1+1)*(len2+1));
dp[0][0] = true;
for (int i = 1; i <= len2; i ++)
if (p[i-1] == '*')
dp[0][i] = dp[0][i-1];
for (int i = 1; i <= len1; i ++)
for (int j = 1; j <= len2; j ++) {
if (p[j-1] == '*')
dp[i][j] = dp[i-1][j] || dp[i][j-1];
else
dp[i][j] = (s[i-1] == p[j-1] || p[j-1] == '?') && dp[i-1][j-1];
}
return dp[len1][len2];
}
};
Leetcode45. Jump Game II
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.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
关键的问题1:到底什么时候总步数+1呢?
- 回答:假设到遍历到数组index=i的位置,在此之前jump到的位置为k;在位置k最远可以到达的范围是
[k,reach]
,如果reach<i
,说明[k-reach]
之间必须再jump一次,这样才能保证i在可以reach的范围内!
关键问题2:那究竟在[k-reach]
的哪个位置再次jump呢?
- 回答:根据贪心算法,应该挑可以reach范围最远的那个点,如果需要求jump game的最短次数的jump路径,就需要记录这个点了。
定义两个变量,一个是reach,记下来可以到达的最远距离,另一个是lastreach,是上一步到达的最远距离。对每一个i,代表可以到达的位置,这个位置一定是小于reach的,如果i比上次能够到达的位置大了,就更新。在更新当前的i能够到达的最远位置。
1 | class Solution { |
Leetcode46. Permutations
Given a collection of distinct integers, return all possible permutations.
Example:1
2
3
4
5
6
7
8
9
10Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
是一道典型的组合题,而此题是求全排列问题,还是用递归 DFS 来求解。这里需要用到一个 visited 数组来标记某个数字是否访问过,然后在 DFS 递归函数从的循环应从头开始。为啥这里的 level 要从0开始遍历,因为这是求全排列,每个位置都可能放任意一个数字,这样会有个问题,数字有可能被重复使用,由于全排列是不能重复使用数字的,所以需要用一个 visited 数组来标记某个数字是否使用过。
1 | class Solution { |
Leetcode47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:1
2
3
4
5
6
7Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
这道题是之前那道 Permutations 的延伸,由于输入数组有可能出现重复数字,如果按照之前的算法运算,会有重复排列产生,我们要避免重复的产生,在递归函数中要判断前面一个数和当前的数是否相等,如果相等,且其对应的 visited 中的值为1,当前的数字才能使用(下文中会解释这样做的原因),否则需要跳过,这样就不会产生重复排列了。只是在上一题的基础上加上一个去重的判断。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35class Solution {
public:
vector<vector<int>> res;
void dfs(vector<int>& nums, vector<int> out, int num, vector<bool> visited) {
if(num == nums.size()) {
res.push_back(out);
}
for(int i = 0; i < nums.size(); i++) {
if(visited[i] == true)
continue;
if(i > 0 && nums[i-1] == nums[i] && visited[i-1] == true) {
continue;
// 去重
}
visited[i] = true;
out.push_back(nums[i]);
dfs(nums, out, num+1, visited);
out.pop_back();
visited[i] = false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
res.clear();
vector<bool> visited(nums.size(), 0);
vector<int> out;
sort(nums.begin(), nums.end());
if(nums.size() == 0)
return res;
dfs(nums, out, 0, visited);
return res;
}
};
Leetcode48. Rotate Image
You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).
Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:1
2
3
4
5
6
7
8
9
10
11
12
13Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
对于90度的翻转有很多方法,一步或多步都可以解,先来看一种直接的方法,这种方法是按顺时针的顺序去覆盖前面的数字,从四个顶角开始,然后往中间去遍历,每次覆盖的坐标都是同理,如下:
(i, j) <- (n-1-j, i) <- (n-1-i, n-1-j) <- (j, n-1-i)
这其实是个循环的过程,第一个位置又覆盖了第四个位置,这里i的取值范围是 [0, n/2),j的取值范围是 [i, n-1-i),至于为什么i和j是这个取值范围,为啥i不用遍历 [n/2, n),若仔细观察这些位置之间的联系,不难发现,实际上j列的范围 [i, n-1-i) 顺时针翻转 90 度,正好就是i行的 [n/2, n) 的位置,这个方法每次循环换四个数字,如下所示:
1 | class Solution { |
Leetcode49. Group Anagrams
Given an array of strings, group anagrams together.
Example:1
2
3
4
5
6
7Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
这道题让我们群组给定字符串集中所有的错位词,所谓的错位词就是两个字符串中字母出现的次数都一样,只是位置不同,比如 abc,bac, cba 等它们就互为错位词,那么如何判断两者是否是错位词呢,可以发现如果把错位词的字符顺序重新排列,那么会得到相同的结果,所以重新排序是判断是否互为错位词的方法,以字母计数后转为字符串作为 key,将所有错位词都保存到字符串数组中,建立 key 和当前的不同的错位词集合个数之间的映射。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
int a[26] = {0};
unordered_map<string, vector<string>> m;
for(int i = 0; i < strs.size(); i ++) {
int a[26] = {0};
for(int j = 0; j < strs[i].length(); j ++) {
a[strs[i][j]-'a'] ++;
}
string t;
for (int ii = 0; ii < 26; ++ ii) {
if (a[ii] == 0) continue;
t += string(1, ii + 'a') + to_string(a[ii]);
}
m[t].push_back(strs[i]);
}
vector<vector<string>> res;
for(auto a : m)
res.push_back(a.second);
return res;
}
};
Leetcode50. Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (xn).
Example 1:1
2Input: 2.00000, 10
Output: 1024.00000
Example 2:1
2Input: 2.10000, 3
Output: 9.26100
Example 3:1
2
3Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
用递归来折半计算,每次把n缩小一半,这样n最终会缩小到0,任何数的0次方都为1,这时候再往回乘,如果此时n是偶数,直接把上次递归得到的值算个平方返回即可,如果是奇数,则还需要乘上个x的值。还有一点需要引起注意的是n有可能为负数,对于n是负数的情况,我可以先用其绝对值计算出一个结果再取其倒数即可,之前是可以的,但是现在 test case 中加了个负2的31次方后,这就不行了,因为其绝对值超过了整型最大值,会有溢出错误,不过可以用另一种写法只用一个函数,在每次递归中处理n的正负,然后做相应的变换即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
double myPow(double x, int n) {
if(n == 0)
return 1;
double half = myPow(x, n/2);
if(n % 2 == 0)
half = half * half;
else if(n > 0)
half = half * half * x;
else
half = half * half / x;
return half;
}
};
Leetcode51. N-Queens
The n-queens puzzle is the problem of placing n queens on an n × n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
方法是使用回溯法。类似于走迷宫,由于每一行都只能有一个皇后,所以可以先在第一行放一个皇后,然后在第二行….第N行放皇后,每次放置后确认是否有效,如果无效,则回退,在该行的下一列放置。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
vector<vector<string>> res;
solveNQueensHelper(n, 0, board, res);
return res;
}
void solveNQueensHelper(int n, int column, vector<string>& board, vector<vector<string>>& res){
if (column == n){// 容易错写成 column == n-1
// base case
res.push_back(board);
} else {
for (int row = 0; row < n; row++){
if (valid_queens(board, column, row)){
// choose
board[row][column] = 'Q';
// explore
solveNQueensHelper(n, column + 1, board, res);
// unchoose
board[row][column] = '.';
}
}
}
}
//确定棋盘上皇后位置是不是有效的
bool valid_queens(vector<string>& board, int column, int row){
int n = board.size();
//1)x = row (横向)
for(int i = 0; i < n; i++)
if (board[row][i]=='Q') return false;
//2) y = col(纵向):默认true
//3)col + row = y + x;(反对角线)
int s = column + row;
for( int i = column - 1; i >= 0 && s - i < n; i--)
if (board[s-i][i]=='Q') return false;
//4) col - row = y - x;(对角线)
s = column - row;
for (int i = column - 1; i >= 0 && i - s >= 0; i--)
if (board[i-s][i] == 'Q') return false;
return true;
}
Leetcode52. N-Queens II
输出上题中的结果个数。
Leetcode53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:1
2
3Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
这道题让求最大子数组之和,并且要用两种方法来解,分别是 O(n) 的解法,还有用分治法 Divide and Conquer Approach,这个解法的时间复杂度是 O(nlgn),那就先来看 O(n) 的解法,定义两个变量 res 和max_local,其中 res 保存最终要返回的结果,即最大的子数组之和,max_local 初始值为0,每遍历一个数字 num,比较 max_local + num 和 num 中的较大值存入 max_local,然后再把 res 和 max_local 中的较大值存入 res,以此类推直到遍历完整个数组,可得到最大子数组的值存在 res 中。1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = INT_MIN, sum = 0;
int size = nums.size();
int max_local = 0;
for(int i = 0; i < size; i ++) {
max_local = max(max_local+nums[i], nums[i]);
res = max(max_local, res);
}
return res;
}
};
题目还要求我们用分治法 Divide and Conquer Approach 来解,这个分治法的思想就类似于二分搜索法,需要把数组一分为二,分别找出左边和右边的最大子数组之和,然后还要从中间开始向左右分别扫描,求出的最大值分别和左右两边得出的最大值相比较取最大的那一个。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class Solution {
public:
int maxSubArray(vector<int>& nums) {
/* int res = INT_MIN, sum = 0;
int size = nums.size();
int max_local = 0;
for(int i = 0; i < size; i ++) {
max_local = max(max_local+nums[i], nums[i]);
res = max(max_local, res);
}
return res;
*/
if (nums.empty())
return 0;
return helper(nums, 0, nums.size()-1);
}
int helper(vector<int>& nums, int left, int right) {
if(left >= right)
return nums[left];
int mid = (left + right) / 2;
int lmax = helper(nums, left, mid - 1);
int rmax = helper(nums, mid + 1, right);
int mmax = nums[mid], t = mmax;
for (int i = mid - 1; i >= left; --i) {
t += nums[i];
mmax = max(mmax, t);
}
t = mmax;
for (int i = mid + 1; i <= right; ++i) {
t += nums[i];
mmax = max(mmax, t);
}
return max(mmax, max(lmax, rmax));
}
};
Leetcode54. Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:1
2
3
4
5
6
7Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:1
2
3
4
5
6
7Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
用顺时针的方式输出一个矩阵,有点烦人。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if(matrix.size() == 0)
return res;
int count = 0;
int x = 0, y = 1, i = 0, j = 0;
int m = matrix.size(), n = matrix[0].size(), size = m*n;
int left = 0, right = 0, up = 0, down = 0;
while(1) {
for(int i = left; i < n - right; i ++)
res.push_back(matrix[up][i]);
up ++;
for(int i = up; i < m - down; i ++)
res.push_back(matrix[i][n-right-1]);
right ++;
if(up < m - down) {
for(int i = n - right - 1; i >= left; i --) {
res.push_back(matrix[m - down - 1][i]);
}
}
down ++;
if(left < n - right) {
for(int i = m - down - 1; i >= up; i --)
res.push_back(matrix[i][left]);
}
left ++;
if(res.size() >= size)
break;
}
return res;
}
};
Leetcode55. Jump Game
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.
Example 1:1
2
3Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:1
2
3Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
Constraints:
1 <= nums.length <= 3 * 10^4
0 <= nums[i][j] <= 10^5
给出一串n个非负数的序列nums,其中nums[i]表示你当前在第i个数时最多能前进num[i]步,初始时你在第1个数,问:最后能否到第n个数?举例说明:A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false.
解题思路:
根据题意可知,对于点i,在该点能到达的最远位置为i+nums[i],前提是,能到达点i。这样我们可以从左到右遍历,维护一个当前所能到达的最大边界reach,始终保持当前遍历的点i <= reach,这样点i都是可以到达的,再根据nums[i]+i来更新reach的大小。若最后能遍历到点n,返回true,否则返回false。
算法正确性:
每次遍历都是在已经能到达的范围内,接着计算的结果可以更新边界。保证走出的每一步都是可以到达的,故算法正确。算法复杂度O(n)。
1 | class Solution { |
Leetcode56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
一些区间,要求合并重叠的区间,返回一个vector保存结果。
Example 1:1
2
3Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:1
2
3Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
贪心思路,将初始区间序列ins按照左端点的从小到大排序,接着遍历ins。 一开始将第一个区间ins[0]放入结果区间序列res,接着每次遍历到一个新的区间[l,r],将其与当前合并后的最后一个区间[L,R]比较:
若l <= R,说明新区间与当前最有一个区间有重叠,应该将这两个区间合并,也就需要修改当前最后一个区间为[L,max(r,R)]。
若l > R,说明新区间与当前最后一个区间没有重叠,所以不需要合并,直接将新区间加入结果序列res,成为新的最后一个区间。
算法正确性:
在上述贪心思路中,只考虑了新区间的左端点与最后一个区间的右端点的大小比较,最后只会对最后区间的右端点进行修改,却不会修改左端点。之所以不考虑左端点,是因为初始化时已经将ins按照左端点排序,保证后遍历的左端点l >= 之前遍历过的左端点L。 算法复杂度为O(nlogn)。
我的代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution {
public:
static bool comp(const Interval &a, const Interval &b) {
return a.start < b.start;
}
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> answer;
if(intervals.size() == 0)
return answer;
sort(intervals.begin(), intervals.end(), comp);
Interval ttt(intervals[0].start, intervals[0].end);
vector<Interval>::iterator it = intervals.begin();
it ++;
for(; it != intervals.end(); it++){
if(ttt.end >= it->start){
if(ttt.end < it->end)
ttt.end = it->end;
}
else if(ttt.end < it->start){
answer.push_back(ttt);
ttt.start = it->start;
ttt.end = it->end;
}
}
answer.push_back(ttt);
return answer;
}
};
题解的代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
static bool cmp(const Interval &a, const Interval &b) {
return a.start < b.start;
}
vector<Interval> merge(vector<Interval>& ins) {
vector <Interval> res;
if (ins.empty()) return res;
sort(ins.begin(), ins.end(), cmp);
res.push_back(ins[0]);
int cnt = ins.size();
for (int i = 1; i < cnt; i++) {
if (ins[i].start <= res.back().end) {
res.back().end = max(res.back().end, ins[i].end);
}
else {
res.push_back(ins[i]);
}
}
return res;
}
};
Solution
Approach 1: Connected Components
Intuition
If we draw a graph (with intervals as nodes) that contains undirected edges between all pairs of intervals that overlap, then all intervals in each connected component of the graph can be merged into a single interval.
Algorithm
With the above intuition in mind, we can represent the graph as an adjacency list, inserting directed edges in both directions to simulate undirected edges. Then, to determine which connected component each node is it, we perform graph traversals from arbitrary unvisited nodes until all nodes have been visited. To do this efficiently, we store visited nodes in a Set, allowing for constant time containment checks and insertion. Finally, we consider each connected component, merging all of its intervals by constructing a new Interval with start equal to the minimum start among them and end equal to the maximum end.
This algorithm is correct simply because it is basically the brute force solution. We compare every interval to every other interval, so we know exactly which intervals overlap. The reason for the connected component search is that two intervals may not directly overlap, but might overlap indirectly via a third interval. See the example below to see this more clearly.
Components Example
Although (1, 5) and (6, 10) do not directly overlap, either would overlap with the other if first merged with (4, 7). There are two connected components, so if we merge their nodes, we expect to get the following two merged intervals:
(1, 10), (15, 20)
1 | class Solution { |
1 | class Solution: |
Leetcode57. Insert Interval
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.
Example 1:1
2Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:1
2
3Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
这道题让我们在一系列非重叠的区间中插入一个新的区间,可能还需要和原有的区间合并,可以对给定的区间集进行一个一个的遍历比较,那么会有两种情况,重叠或是不重叠,不重叠的情况最好,直接将新区间插入到对应的位置即可,重叠的情况比较复杂,有时候会有多个重叠,需要更新新区间的范围以便包含所有重叠,之后将新区间加入结果 res,最后将后面的区间再加入结果 res 即可。具体思路是,用一个变量 cur 来遍历区间,如果当前 cur 区间的结束位置小于要插入的区间的起始位置的话,说明没有重叠,则将 cur 区间加入结果 res 中,然后 cur 自增1。直到有 cur 越界或有重叠 while 循环退出,然后再用一个 while 循环处理所有重叠的区间,每次用取两个区间起始位置的较小值,和结束位置的较大值来更新要插入的区间,然后 cur 自增1。直到 cur 越界或者没有重叠时 while 循环退出。之后将更新好的新区间加入结果 res,然后将 cur 之后的区间再加入结果 res 中即可,参见代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int length = intervals.size();
vector<vector<int>> result;
int begin, end, last_end, i=0;
while(i < length && intervals[i][1] < newInterval[0]) {
result.push_back(intervals[i]);
i++;
}
while(i < length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(intervals[i][0],newInterval[0]);
newInterval[1] = max(intervals[i][1],newInterval[1]);
i++;
}
result.push_back(newInterval);
while(i < length) {
result.push_back(intervals[i]);
i++;
}
return result;
}
};
Leetcode58. Length of Last Word
Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word (last word means the last appearing word if we loop from left to right) in the string.
If the last word does not exist, return 0.
Note: A word is defined as a maximal substring consisting of non-space characters only.
Example:1
2Input: "Hello World"
Output: 5
找到一个字符串里的最后一个单词,有很多的特殊样例:比如" "
," "
,"a "
,""
等等吧,错了好几次。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
int lengthOfLastWord(string s) {
int size = s.length();
if(size == 0 || size == 1 && s[0] == ' ')
return 0;
int res = 0, i = size - 1;
while(i >= 0 && s[i] == ' ')
i--;
for(; i >= 0 && s[i] != ' '; i --) {
res ++;
}
return res;
}
};
Leetcode59. Spiral Matrix II
Given a positive integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.
Example:1
2
3
4
5
6
7Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
先清空矩阵,把数字从小到大填进去,那么就是一直往前走的一条线,每次这条线到尽头或者到一个填过的点就右转(初始在[0,0]位置方向向右)。那么就可以直接拿x方向的增量和y方向的增量来模拟,每次试着从上一次的增量方向前进,如果到了边界外或者到过的点,就修正方向(右转),并继续前进,直至填的数字大于n*n。
如n=2的情况,初始化:1
2[0, 0],
[0, 0]
当前位置[0,0],x增量0,y增量1,填的数字是1
填充,前进一步:1
2[1, 0],
[0, 0]
当前位置[0,1],x增量0,y增量1,填的数字是2
填充,试着前进一步,发现出了边界,修正方向为向下。重新前进一步:1
2[1, 2],
[0, 0]
当前位置[1,1],x增量1,y增量0,填的数字是3
填充,试着前进一步,发现出了边界,修正方向为向左。重新前进一步:1
2[1, 2],
[0, 3]
当前位置[1,0],x增量0,y增量-1,填的数字是4
填充,填完后填的数字变成了5,大于2*2,结束。1
2[1, 2],
[4, 3]
1 | class Solution { |
Leetcode60. Permutation Sequence
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:1
2
3
4
5
6"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
Example 1:1
2Input: n = 3, k = 3
Output: "213"
Example 2:1
2Input: n = 4, k = 9
Output: "2314"
这道题是让求出n个数字的第k个排列组合,由于其特殊性,我们不用将所有的排列组合的情况都求出来,然后返回其第k个,这里可以只求出第k个排列组合即可,那么难点就在于如何知道数字的排列顺序。首先要知道当 n = 3 时,其排列组合共有 3! = 6 种,当 n = 4 时,其排列组合共有 4! = 24 种,这里就以 n = 4, k = 17 的情况来分析,所有排列组合情况如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
241234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412 <--- k = 17
3421
4123
4132
4213
4231
4312
4321
可以发现,每一位上 1,2,3,4 分别都出现了6次,当最高位上的数字确定了,第二高位每个数字都出现了2次,当第二高位也确定了,第三高位上的数字都只出现了1次,当第三高位确定了,那么第四高位上的数字也只能出现一次,下面来看 k = 17 这种情况的每位数字如何确定,由于 k = 17 是转化为数组下标为 16:
最高位可取 1,2,3,4 中的一个,每个数字出现 3!= 6 次(因为当最高位确定了,后面三位可以任意排列,所以是 3!,那么最高位的数字就会重复 3!次),所以 k = 16 的第一位数字的下标为 16 / 6 = 2,在 “1234” 中即3被取出。这里的k是要求的坐标为k的全排列序列,定义 k’ 为当最高位确定后,要求的全排序列在新范围中的位置,同理,k’’ 为当第二高为确定后,所要求的全排列序列在新范围中的位置,以此类推,下面来具体看看:
第二位此时从 1,2,4 中取一个,k = 16,则此时的 k’ = 16 % (3!) = 4,注意思考这里为何要取余,如果对这 24 个数以6个一组来分,那么 k=16 这个位置就是在第三组(k/6 = 2)中的第五个(k%6 = 4)数字。如下所示,而剩下的每个数字出现 2!= 2 次,所以第二数字的下标为 4 / 2 = 2,在 “124” 中即4被取出。1
2
3
4
5
63124
3142
3214
3241
3412 <--- k' = 4
3421
第三位此时从 1,2 中去一个,k’ = 4,则此时的 k’’ = 4 % (2!) = 0,如下所示,而剩下的每个数字出现 1!= 1 次,所以第三个数字的下标为 0 / 1 = 0,在 “12” 中即1被取出。1
23412 <--- k'' = 0
3421
第四位是从2中取一个,k’’ = 0,则此时的 k’’’ = 0 % (1!) = 0,如下所示,而剩下的每个数字出现 0!= 1 次,所以第四个数字的下标为 0 / 1= 0,在 “2” 中即2被取出。1
3412 <--- k''' = 0
那么就可以找出规律了1
2
3
4
5
6
7
8
9
10
11
12a1 = k / (n - 1)!
k1 = k
a2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!
...
an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!
an = kn-1 / 0!
kn = kn-1 % 0!1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
string getPermutation(int n, int k) {
string res;
string num = "123456789";
vector<int> f(n, 1);
k --;
for(int i = 1; i < n; i ++) {
f[i] = f[i-1] * i;
}
for(int i = n; i >= 1; i --) {
int j = k / f[i-1];
k %= f[i - 1];
res.push_back(num[j]);
num.erase(j, 1);
}
return res;
}
};
Leetcode61. Rotate List
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:1
2
3
4
5Input: 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
Example 2:1
2
3
4
5
6
7Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
先遍历一次链表,将尾部和头部相连,再进行移动。注意右移k步相当于prehead travel len - k步。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head==NULL)
return head;
ListNode* cur_head = head, *tail;
int len = 1;
while(cur_head->next != NULL) {
cur_head = cur_head->next;
len ++;
}
tail = cur_head;
tail->next = head;
cur_head = head;
k =len - (len + (k % len)) % len;
while(k --) {
head = head->next;
}
while(cur_head->next != head) {
cur_head = cur_head->next;
}
cur_head->next = NULL;
return head;
}
};
Leetcode62. Unique Paths
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?
Example 1:1
2Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
- Right -> Right -> Down
- Right -> Down -> Right
- Down -> Right -> Right
Example 2:1
2Input: m = 7, n = 3
Output: 28
1 | class Solution { |
Leetcode63. Unique Paths II
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?
Note: m and n will be at most 100.
Example 1:1
2
3
4
5
6
7Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
- Right -> Right -> Down -> Down
- Down -> Down -> Right -> Right
第62题(Unique Paths)的升级版. 现在需要考虑如果表格中存在一些障碍,那么所要求的路径数还有多少条? 在表格表示中,1表示此位置有障碍,0表示没有. 例如在一个3 x 3的表格中存在一个障碍物,
[
[0,0,0],
[0,1,0],
[0,0,0]
]
求得最终的路径数为2. 注意:m 和 n 均不超过100.
题解
算法及复杂度(3 ms) 本题解法参考第62题(Unique Paths).本题和62题的唯一区别是存在了障碍物.但是这个对于算法是没有影响的. 在62题算法的基础上,在求解的过程中,每个点判断本点是否是障碍物,如果是则将dpi置0即可. 参考代码中与62题代码只添加了4行. 时间复杂度: O(mn),表格中每个位置进行一次计算即可. 代码参见本文件夹下solution.cpp
算法正确性
正确性证明 UniquePaths 举个例子
// 输入数据
obstacleGrid = [
[0,0,0],
[0,1,0],
[0,0,0]
]
//初始化m = 3, n = 3, p[0][0:n] = 0, dp[0:m][0] = 0, dp[1][1] = 1
//求解
dp[1][2] = dp[0][2] + dp[1][1] = 1
dp[1][3] = dp[0][3] + dp[1][2] = 1
dp[2][1] = dp[1][1] + dp[2][0] = 1
dp[2][2] = dp[1][2] + dp[2][1] = 2,由于obstacleGrid[1][1]位置为1,经过换算,也就是此位置为1,则dp[2][2] = 0
dp[2][3] = dp[1][3] + dp[2][2] = 1
dp[3][1] = dp[2][1] + dp[3][0] = 1
dp[3][2] = dp[2][2] + dp[3][1] = 1
dp[3][3] = dp[2][3] + dp[3][2] = 2
//return 2
1 | class Solution { |
Leetcode64. Minimum Path Sum
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.
Note: You can only move either down or right at any point in time.
Example:1
2
3
4
5
6
7
8Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
本来用的是dfs,但是会超时:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution {
public:
void dfs(vector<vector<int>>& grid, int x, int y, int cur, int& res) {
int dir[2][2] = {{1, 0}, {0, 1}};
if(x == grid.size() - 1 && y == grid[0].size()-1) {
res = min(res, cur);
return;
}
for(int i = 0; i < 2; i ++) {
int tmp_x = x + dir[i][0];
int tmp_y = y + dir[i][1];
if(!(0 <= tmp_x && tmp_x < grid.size() && 0 <= tmp_y && tmp_y < grid[0].size() ))
continue;
cur += grid[tmp_x][tmp_y];
if(cur >= res) {
cur -= grid[tmp_x][tmp_y];
continue;
}
dfs(grid, tmp_x, tmp_y, cur, res);
cur -= grid[tmp_x][tmp_y];
}
}
int minPathSum(vector<vector<int>>& grid) {
int res = 999999;
dfs(grid, 0, 0, grid[0][0], res);
return res;
}
};
看这情况要上dp了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for(int i = 1; i < m; i ++)
grid[i][0] += grid[i-1][0];
for(int i = 1; i < n; i ++)
grid[0][i] += grid[0][i-1];
for(int i = 1; i < m; i ++)
for(int j = 1; j < n; j ++)
grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
return grid[m-1][n-1];
}
};
Leetcode65. Valid Number
A valid number can be split up into these components (in order):
- A decimal number or an integer.
- (Optional) An ‘e’ or ‘E’, followed by an integer.
A decimal number can be split up into these components (in order):
- (Optional) A sign character (either ‘+’ or ‘-‘).
- One of the following formats:
- One or more digits, followed by a dot ‘.’.
- One or more digits, followed by a dot ‘.’, followed by one or more digits.
- A dot ‘.’, followed by one or more digits.
An integer can be split up into these components (in order):
- (Optional) A sign character (either ‘+’ or ‘-‘).
- One or more digits.
For example, all the following are valid numbers: [“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”], while the following are not valid numbers: [“abc”, “1a”, “1e”, “e3”, “99e2.5”, “—6”, “-+3”, “95a54e53”].
Given a string s, return true if s is a valid number.
corner case很多,慢慢调试。1488个样例,是有多齐全hhh。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40class Solution {
public:
bool isnum(char c) {
return c >= '0' && c <= '9';
}
bool isNumber(string s) {
if (s.length() == 0)
return false;
int idx = 0;
if (s[0] == '+' || s[0] == '-')
idx ++;
int num_num = 0, e_num = 0, dot_num = 0;
for (int i = idx; i < s.length(); i ++) {
if (isnum(s[i]))
num_num ++;
else if (s[i] == '.') {
if (dot_num > 0 || e_num > 0)
return false;
dot_num ++;
}
else if (s[i] == 'e' || s[i] == 'E') {
if (e_num > 0 || num_num == 0)
return false;
e_num ++;
if (i+1 >= s.length())
return false;
if (s[i+1] == '+' || s[i+1] == '-') {
if (i+2 >= s.length())
return false;
i ++;
}
}
else
return false;
}
return num_num > 0;
}
};
自动状态机yyds:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
bool isNumber(const char *s) {
enum InputType {
INVALID, // 0 Include: Alphas, '(', '&' ans so on
SPACE, // 1
SIGN, // 2 '+','-'
DIGIT, // 3 numbers
DOT, // 4 '.'
EXPONENT, // 5 'e' 'E'
};
int transTable[][6] = {
//0INVA,1SPA,2SIG,3DI,4DO,5E
-1, 0, 3, 1, 2, -1,//0初始无输入或者只有space的状态
-1, 8, -1, 1, 4, 5,//1输入了数字之后的状态
-1, -1, -1, 4, -1, -1,//2前面无数字,只输入了Dot的状态
-1, -1, -1, 1, 2, -1,//3输入了符号状态
-1, 8, -1, 4, -1, 5,//4前面有数字和有dot的状态
-1, -1, 6, 7, -1, -1,//5'e' or 'E'输入后的状态
-1, -1, -1, 7, -1, -1,//6输入e之后输入Sign的状态
-1, 8, -1, 7, -1, -1,//7输入e后输入数字的状态
-1, 8, -1, -1, -1, -1,//8前面有有效数输入之后,输入space的状态
};
int state = 0;
while (*s)
{
InputType input = INVALID;
if (*s == ' ') input = SPACE;
else if (*s == '+' || *s == '-') input = SIGN;
else if (isdigit(*s)) input = DIGIT;
else if (*s == '.') input = DOT;
else if (*s == 'e' || *s == 'E') input = EXPONENT;
state = transTable[state][input];
if (state == -1) return false;
++s;
}
return state == 1 || state == 4 || state == 7 || state == 8;
}
};
Leetcode66. Plus One
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.
Example 1:1
2
3Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:1
2
3Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
加一的操作。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
digits[digits.size() - 1] += 1;
for(int i = digits.size() - 1; i >= 1; i --) {
if(digits[i] == 10) {
digits[i] = 0;
digits[i-1] ++;
}
}
if(digits[0] == 10) {
digits.insert(digits.begin(), 1);
digits[1] = 0;
}
return digits;
}
};
Leetcode67. Add Binary
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.
Example 1:1
2Input: a = "11", b = "1"
Output: "100"
Example 2:1
2Input: a = "1010", b = "1011"
Output: "10101"
设置一个进位标志。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
string addBinary(string a, string b) {
string res = "";
int aa = a.length() - 1;
int bb = b.length() - 1;
int carry = 0;
int sum = 0;
while(aa >= 0 || bb >= 0 || carry) {
sum = carry;
if(aa >= 0)
sum += (a[aa--] - '0');
if(bb >= 0)
sum += (b[bb--] - '0');
res = to_string(sum%2) + res;
carry = sum / 2;
}
return res;
}
};
Leetcode68. Text Justification
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.
Note:
- A word is defined as a character sequence consisting of non-space characters only.
- Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
- The input array words contains at least one word.
Example 1:1
2
3
4
5
6
7Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
Example 2:1
2
3
4
5
6
7
8
9Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.
Example 3:1
2
3
4
5
6
7
8
9
10Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
由于返回的结果是多行的,所以我们在处理的时候也要一行一行的来处理,首先要做的就是确定每一行能放下的单词数,这个不难,就是比较n个单词的长度和加上n - 1个空格的长度跟给定的长度L来比较即可,找到了一行能放下的单词个数,然后计算出这一行存在的空格的个数,是用给定的长度L减去这一行所有单词的长度和。得到了空格的个数之后,就要在每个单词后面插入这些空格,这里有两种情况,比如某一行有两个单词”to” 和 “a”,给定长度L为6,如果这行不是最后一行,那么应该输出”to a”,如果是最后一行,则应该输出 “to a “,所以这里需要分情况讨论,最后一行的处理方法和其他行之间略有不同。最后一个难点就是,如果一行有三个单词,这时候中间有两个空,如果空格数不是2的倍数,那么左边的空间里要比右边的空间里多加入一个空格,那么我们只需要用总的空格数除以空间个数,能除尽最好,说明能平均分配,除不尽的话就多加个空格放在左边的空间里。
1 | class Solution { |
Leetcode69. Sqrt(x)
Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:1
2Input: 4
Output: 2
Example 2:1
2
3
4Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
二分求一个数的开方,做的恶心,垃圾题,浪费时间。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
int mySqrt(int x) {
int low = 0, high = x, mid;
if(x<2) return x; // to avoid mid = 0
while(low<high)
{
mid = (low + high)/2;
if(x/mid >= mid) low = mid+1;
else high = mid;
}
return high-1;
}
};
Leetcode70. Climbing Stairs
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.
Example 1:1
2
3
4
5Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:1
2
3
4
5
6Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
试着倒推想一下,就能发现这个问题可以被分解为一些包含最优子结构的子问题,它的最优解可以从其子问题
的最优解来有效地构建,因此我们可以使用动态规划解决这个问题.
第 i 阶可以由以下两种方法得到:
- 在第 (i - 1) 阶后向上爬 1 阶。
- 在第 (i - 2) 阶后向上爬 2 阶
- 所以到达第 i 阶的方法总数就是到第 (i - 1) 阶和第 (i - 2) 阶的方法数之和。
dp[i]
表示能到达第 i 阶的方法总数,那么DP推导公式就是:1
dp[i] = dp[i − 1] + dp[i − 2]
1 | class Solution { |
进一步优化:根据推导公式不难发现,我们要求的结果就是数组的最后一项,而最后一项又是前面数值叠加起来的,那么我们只需要两个变量保存 i - 1 和 i - 2 的值就可以了.1
2
3
4
5
6
7
8
9
10
11
12var climbStairs = function(n) {
if (n == 1) {
return 1;
}
let first = 1, second = 2;
for (let i = 3; i <= n; i++) {
let third = first + second;
first = second;
second = third;
}
return second;
}
复杂度分析
- 时间复杂度:O(n),单循环到 n。
- 空间复杂度:O(1),用到了常量的空间。
Leetcode71. Simplify Path
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.
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.
Example 1:1
2
3Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.
Example 2:1
2
3Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Example 3:1
2
3Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
Example 4:1
2Input: "/a/./b/../../c/"
Output: "/c"
Example 5:1
2Input: "/a/../../b/../c//.//"
Output: "/c"
Example 6:1
2Input: "/a//b////c/d//././/.."
Output: "/a/b/c"
算法及复杂度 (6 ms) :本题主要的处理对象分为: “.”, “..”, “/“, 普通文件或目录名.其中”.”的作用是保持当前的目录,”..”的作用是退回上一级目录,”/“的作用的分隔符, 普通文件或目录名不需要进行特殊处理. 很容易的思路(模拟),根据”/“对所有字符串进行分割,得到不同的三类字符串: “.”, “..”, 普通文件或目录名.分割过程是比较容易实现的,就是简单的读取字符串,然后分割. 由于”..”有回退的作用,因此可以考虑使用stack进行实现.在上一段中叙述的分割的过程中进行处理:
- 遇到普通目录名就进行压栈;
- 遇到”.”就跳过不处理;
- 遇到”..”就对栈进行弹出(保证栈不为空的情况下).
存在问题的几点:
- 输入字符串为空字符串,则返回空字符串,而不是根目录”/“;
- 输入字符串的第一个字符一定是’/‘,而不是任意的(leetcode的参考程序会报错);
- 存在”…”, “….”这样的路径,在本题中被认为是普通的目录或文件名.
时间复杂度: O(n). n 表示输入字符串的长度,只需要一次遍历就可以完成,因此是 O(n) 的复杂度.
1 | class Solution { |
Leetcode72. Edit Distance
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
Example 1:1
2
3
4
5
6Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:1
2
3
4
5
6
7
8Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
一道好久不做的dp题,过段时间闲下来复习下dp
给你word1、word2两个字符串,问最少需要几步才能把word1变成word2,下面每种操作都是一步:a)添加一个字符;b)添加一个字符;c)把一个字符用另一个字符代替。
解题思路:
动态规划。用dp[i][j]表示把word1的前i个字符变成word2的前j个字符所需的步数,word1的前i个字符变成word2的前j个字符可以由三种方法得到:
- word1先删去最后一个字符,然后把word1的前i-1个字符变成word2的前j个字符;
- word1的前i个字符先变成word2的前j-1个字符;然后word2最后添上一个字符;
- word1的前i-1个字符先变成word2的前j-1个字符;然后word1的最后一个字符和word2的最后一个字符匹配上。
因此有状态转移方程:
当word1[i-1]==word2[j-1]时dp[i][j]=dp[i-1][j-1],
否则dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)。
另外边界需要初始化:dp[0][0]=0,dp[i][0]=i对于i从1到len1,dp[0][i]=i对于i从1到len2,。
最终答案为dp[len1][len2],算法复杂度为O(len1*len2)。
算法正确性:
算法的关键点在于是否可以用动态规划的思想把问题拆分成一个个子问题。可以这么考虑:当你能确定用了若干步把word1的前i个字母变成word2的前j个字母后,接下来就可以处理相邻的状态。
对于删除字母,可以把word1的第i+1个字母先删掉,然后再执行那若干步,这样可以得到把word1的前i+1个字母变成word2的前j个字母的步数;
对于添加字母,可以先执行那若干步,再加上word2的第j+1个字母,这样可以得到把word1的前i个字母变成word2的前j+1个字母的步数;
对于代替字母,可以先执行那若干步,再把word1的第i+1个字母和word2的第j+1个字母匹配上,这样可以得到把word1的前i+1个字母变成word2的前j+1个字母的步数。因此上述算法是正确的。
下面举一个简单例子走一遍算法帮助理解:word1=”ad”,word2=”abc”。
初始化:
dp[0][0]=0,dp[1][0]=1,dp[2][0]=2,dp[0][1]=1,dp[0][2]=2,dp[0][3]=3;
i=1,j=1,word1[0]==word2[0],dp[1][1]=min(dp[0][1]+1,dp[1][0]+1,dp[0][0])=0;
i=1,j=2,word1[0]!=word2[1],dp[1][2]=min(dp[0][2]+1,dp[1][1]+1,dp[0][1]+1)=2;
i=1,j=3,word1[0]!=word2[2],dp[1][3]=min(dp[0][3]+1,dp[1][2]+1,dp[0][2]+1)=3;
i=2,j=1,word1[1]!=word2[0],dp[2][1]=min(dp[1][1]+1,dp[2][0]+1,dp[1][0]+1)=1;
i=2,j=2,word1[1]!=word2[1],dp[2][2]=min(dp[1][2]+1,dp[2][1]+1,dp[1][1]+1)=1;
i=2,j=3,word1[1]!=word2[2],dp[2][3]=min(dp[1][3]+1,dp[2][2]+1,dp[1][2]+1)=2;
最终结果为dp[2][3]=3。
1 | class Solution { |
Leetcode73. Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:1
2
3
4
5
6
7
8
9
10
11
12Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:1
2
3
4
5
6
7
8
9
10
11
12Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Follow up:
- A straight forward solution using O(mn) space is probably a bad idea.
- A simple improvement uses O(m + n) space, but still not the best solution.
- Could you devise a constant space solution?
我的慢出屎来的代码,如果一行中有0,那么这一行就都是0,如果一列中有0,那么这一列就都是0:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<int> flags(m, 0);
for(int i = 0; i < m; i ++) {
for(int j = 0; j < n; j ++) {
if(matrix[i][j] == 0) {
flags[i] = 1;
break;
}
}
}
vector<int> flags2(n, 0);
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
if(matrix[j][i] == 0) {
flags2[i] = 1;
break;
}
}
}
for(int i = 0; i < m; i ++)
if(flags[i] == 1)
for(int j = 0; j < n; j ++)
matrix[i][j] = 0;
for(int i = 0; i < n; i ++)
if(flags2[i] == 1)
for(int j = 0; j < m; j ++)
matrix[j][i] = 0;
}
};
Leetcode74. Search a 2D Matrix
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.
Example 1:1
2
3
4
5
6
7
8Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:1
2
3
4
5
6
7
8Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
这道题要求搜索一个二维矩阵,由于给的矩阵是有序的,所以很自然的想到要用二分查找法,可以在第一列上先用一次二分查找法找到目标值所在的行的位置,然后在该行上再用一次二分查找法来找是否存在目标值。如果是查找第一个不小于目标值的数,当 target 在第一列时,会返回 target 所在的行,但若 target 不在的话,有可能会返回下一行,不好统一。所以可以查找第一个大于目标值的数,这样只要回退一个,就一定是 target 所在的行。但需要注意的一点是,如果返回的是0,就不能回退了,以免越界,记得要判断一下。找到了 target 所在的行数,就可以再次使用二分搜索,此时就是总结帖中的第一类了,查找和 target 值相同的数,也是最简单的一类。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size(), n = matrix[0].size();
int left = 0, right = m;
while(left < right) {
int mid = left + (right - left) / 2;
if(matrix[mid][0] == target)
return true;
else if(matrix[mid][0] >= target)
right = mid;
else
left = mid + 1;
}
int right1 = right > 0 ? right - 1 : right;
left = 0, right = n;
while(left < right) {
int mid = left + (right - left) / 2;
if(matrix[right1][mid] == target)
return true;
else if(matrix[right1][mid] >= target)
right = mid;
else
left = mid + 1;
}
return false;
}
};
Leetcode75. Sort Colors
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.
Note: You are not suppose to use the library sort function for this problem.
Example:1
2Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:
- A rather straight forward solution is a two-pass algorithm using counting sort.
- First, iterate the array counting number of 0s, 1s, and 2s, then overwrite array with total number of 0s, then 1s and followed by 2s.
- Could you come up with a one-pass algorithm using only constant space?
这道题的本质还是一道排序的题,题目中给出提示说可以用计数排序,需要遍历数组两遍,那么先来看这种方法,因为数组中只有三个不同的元素,所以实现起来很容易。
- 首先遍历一遍原数组,分别记录 0,1,2 的个数。
- 然后更新原数组,按个数分别赋上 0,1,2。
1 | class Solution { |
题目中还要让只遍历一次数组来求解,那么就需要用双指针来做,分别从原数组的首尾往中心移动。
- 定义 red 指针指向开头位置,blue 指针指向末尾位置。
- 从头开始遍历原数组,如果遇到0,则交换该值和 red 指针指向的值,并将 red 指针后移一位。若遇到2,则交换该值和 blue 指针指向的值,并将 blue 指针前移一位。若遇到1,则继续遍历。
1 | class Solution { |
Leetcode76. Minimum Window Substring
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).
Example:
Input: S = “ADOBECODEBANC”, T = “ABC”
Output: “BANC”
这道题给了我们一个原字符串S,还有一个目标字符串T,让在S中找到一个最短的子串,使得其包含了T中的所有的字母,并且限制了时间复杂度为 O(n)。这道题的要求是要在 O(n) 的时间度里实现找到这个最小窗口字串,暴力搜索 Brute Force 肯定是不能用的,因为遍历所有的子串的时间复杂度是平方级的。那么来想一下,时间复杂度卡的这么严,说明必须在一次遍历中完成任务,当然遍历若干次也是 O(n),但不一定有这个必要,尝试就一次遍历拿下!那么再来想,既然要包含T中所有的字母,那么对于T中的每个字母,肯定要快速查找是否在子串中,既然总时间都卡在了 O(n),肯定不想在这里还浪费时间,就用空间换时间(也就算法题中可以这么干了,七老八十的富翁就算用大别野也换不来时间啊。依依东望,望的就是时间呐 T.T),使用 HashMap,建立T中每个字母与其出现次数之间的映射,那么你可能会有疑问,为啥不用 HashSet 呢,别急,讲到后面你就知道用 HashMap 有多妙,简直妙不可言~
目前在脑子一片浆糊的情况下,我们还是从简单的例子来分析吧,题目例子中的S有点长,换个短的 S = “ADBANC”,T = “ABC”,那么肉眼遍历一遍S呗,首先第一个是A,嗯很好,T中有,第二个是D,T中没有,不理它,第三个是B,嗯很好,T中有,第四个又是A,多了一个,礼多人不怪嘛,收下啦,第五个是N,一边凉快去,第六个终于是C了,那么貌似好像需要整个S串,其实不然,注意之前有多一个A,就算去掉第一个A,也没事,因为第四个A可以代替之,第二个D也可以去掉,因为不在T串中,第三个B就不能再去掉了,不然就没有B了。所以最终的答案就”BANC”了。通过上面的描述,你有没有发现一个有趣的现象,先扩展,再收缩,就好像一个窗口一样,先扩大右边界,然后再收缩左边界,上面的例子中右边界无法扩大了后才开始收缩左边界,实际上对于复杂的例子,有可能是扩大右边界,然后缩小一下左边界,然后再扩大右边界等等。这就很像一个不停滑动的窗口了,这就是大名鼎鼎的滑动窗口 Sliding Window 了,简直是神器啊,能解很多子串,子数组,子序列等等的问题,是必须要熟练掌握的啊!
下面来考虑用代码来实现,先来回答一下前面埋下的伏笔,为啥要用 HashMap,而不是 HashSet,现在应该很显而易见了吧,因为要统计T串中字母的个数,而不是仅仅看某个字母是否在T串中出现。统计好T串中字母的个数了之后,开始遍历S串,对于S中的每个遍历到的字母,都在 HashMap 中的映射值减1,如果减1后的映射值仍大于等于0,说明当前遍历到的字母是T串中的字母,使用一个计数器 cnt,使其自增1。当 cnt 和T串字母个数相等时,说明此时的窗口已经包含了T串中的所有字母,此时更新一个 minLen 和结果 res,这里的 minLen 是一个全局变量,用来记录出现过的包含T串所有字母的最短的子串的长度,结果 res 就是这个最短的子串。然后开始收缩左边界,由于遍历的时候,对映射值减了1,所以此时去除字母的时候,就要把减去的1加回来,此时如果加1后的值大于0了,说明此时少了一个T中的字母,那么 cnt 值就要减1了,然后移动左边界 left。你可能会疑问,对于不在T串中的字母的映射值也这么加呀减呀的,真的大丈夫(带胶布)吗?其实没啥事,因为对于不在T串中的字母,减1后,变-1,cnt 不会增加,之后收缩左边界的时候,映射值加1后为0,cnt 也不会减少,所以并没有什么影响啦,下面是具体的步骤啦:
先扫描一遍T,把对应的字符及其出现的次数存到 HashMap 中。
然后开始遍历S,就把遍历到的字母对应的 HashMap 中的 value 减一,如果减1后仍大于等于0,cnt 自增1。
如果 cnt 等于T串长度时,开始循环,纪录一个字串并更新最小字串值。然后将子窗口的左边界向右移,如果某个移除掉的字母是T串中不可缺少的字母,那么 cnt 自减1,表示此时T串并没有完全匹配。
1 | class Solution { |
Leetcode77. Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example:1
2
3
4
5
6
7
8
9
10Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
简单的dfs就可以过,但是成绩低。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
vector<vector<int>> res;
void dfs(int n, int k, int i, vector<int> temp) {
if(temp.size() == k) {
res.push_back(temp);
return;
}
printf("af");
for(int ii = i + 1; ii <= n; ii ++) {
int t = temp.size();
temp.push_back(ii);
dfs(n, k, ii, temp);
temp.erase(temp.begin()+t);
}
}
vector<vector<int>> combine(int n, int k) {
vector<int> temp(0);
dfs(n, k, 0, temp);
return res;
}
};
一样的做法,人家为啥就速度快。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
vector<int> buffer(k);
combineUtil(result,1,buffer,0,n);
return result;
}
void combineUtil(vector<vector<int>>& result,int startIndex,vector<int>& buffer,int bufferIndex,int n){
if(bufferIndex==buffer.size()){
result.push_back(buffer);
return;
}
for(int i=startIndex;i<=n;i++){
buffer[bufferIndex] = i;
combineUtil(result,i+1,buffer,bufferIndex+1,n);
}
return;
}
};
Leetcode78. Subsets
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:1
2
3
4
5
6
7
8
9
10
11
12Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
可以一位一位的叠加,比如对于题目中给的例子 [1,2,3] 来说,最开始是空集,那么我们现在要处理1,就在空集上加1,为 [1],现在我们有两个自己 [] 和 [1],下面我们来处理2,我们在之前的子集基础上,每个都加个2,可以分别得到 [2],[1, 2],那么现在所有的子集合为 [], [1], [2], [1, 2],同理处理3的情况可得 [3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > res;
res.push_back({});
for(int i = 0; i < nums.size(); i ++) {
int size = res.size();
for(int j = 0; j < size; j ++) {
vector<int> temp = res[j];
temp.push_back(nums[i]);
res.push_back(temp);
}
}
return res;
}
};
Leetcode79. Word Search
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.
Example:1
2
3
4
5
6
7
8
9
10board =
[
['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.
Constraints:
- board and word consists only of lowercase and uppercase English letters.
- 1 <= board.length <= 200
- 1 <= board[i].length <= 200
- 1 <= word.length <= 10^3
典型的深度优先遍历 DFS 的应用,原二维数组就像是一个迷宫,可以上下左右四个方向行走,我们以二维数组中每一个数都作为起点和给定字符串做匹配,我们还需要一个和原数组等大小的 visited 数组,是 bool 型的,用来记录当前位置是否已经被访问过,因为题目要求一个 cell 只能被访问一次。如果二维数组 board 的当前字符和目标字符串 word 对应的字符相等,则对其上下左右四个邻字符分别调用 DFS 的递归函数,只要有一个返回 true,那么就表示可以找到对应的字符串,否则就不能找到。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution {
public:
int m, n;
bool search(vector<vector<char>>& board, int i, int j, int k, string word, vector<vector<bool>>& visited) {
if(word.length() == k) {
return true;
}
int m = board.size(), n = board[0].size();
if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[k])
return false;
visited[i][j] = true;
bool res = search(board, i - 1, j, k + 1, word, visited)
|| search(board, i + 1, j, k + 1, word, visited)
|| search(board, i, j - 1, k + 1, word, visited)
|| search(board, i, j + 1, k + 1, word, visited);
visited[i][j] = false;
return res;
}
bool exist(vector<vector<char>>& board, string word) {
m = board.size(), n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n));
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++)
visited[i][j] = false;
for(int i = 0; i < m; i ++)
for(int j = 0; j < n; j ++)
if(search(board, i, j, 0, word, visited))
return true;
return false;
}
};
Leetcode80. Remove Duplicates from Sorted Array II
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.
Example 1: 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 not matter what you leave beyond the returned length.
Example 2: Given nums = [0,0,1,1,1,1,2,3,3], Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.
Clarification: Confused why the returned value is an integer but your answer is an array? Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well. Internally you can think of this:1
2
3
4
5
6
7
8// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
遍历一遍,记下来每次遍历开始的数,如果这个数的数量大于2了,一直i++。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() <= 2)
return nums.size();
int prev_i = 0, prev;
int count = 0;
for(int i = 0; i < nums.size();) {
count = 0;
nums[prev_i] = nums[i];
prev = nums[i];
while(count < 2 && i < nums.size() && prev == nums[i])
nums[prev_i++] = nums[i], count ++, i++;
while(i < nums.size() && prev == nums[i])
i ++;
}
return prev_i;
}
};
另一种方法是交换:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() < 3) {
return nums.size();
}
int arrow = 2;
for (int i = 2; i < nums.size(); i++) {
if (nums[arrow-2] != nums[i]) {
swap(nums[arrow], nums[i]);
arrow++;
}
}
return arrow;
}
};
Leetcode81. Search in Rotated Sorted Array II
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.
Example 1:1
2Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:1
2Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
本题采用二分法实现,但是比较挠头的是边界问题,而且元素有重复,相比纯粹递增的数组难度要大得多,要解决这个问题,首先要对所有可能情况进行分类,然后对每种可能的类别进行相应的处理。
暂且不考虑nums[mid] = nums[left]的情况,本题大致可以简化为两种情况,可能的情况划分出来,那么解决本题就比较容易了:
- 当 nums[mid] = nums[left] 时,这时由于很难判断 target 会落在哪,那么只能采取 left++
- 当 nums[mid] > nums[left] 时,这时可以分为两种情况,判断左半部比较简单(如果target不在左边这部分,那么我们是可以直接去掉左边这部分的)
- 当 nums[mid] < nums[left] 时,这时可以分为两种情况,判断右半部比较简单(如果target不在右边这部分,那么我们也是可以直接去掉右边这部分的)
1 | class Solution { |
Leetcode82. Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well.
Example 1:1
2Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:1
2Input: 1->1->1->2->3
Output: 2->31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
ListNode* res = new ListNode(-1);
res->next = head;
ListNode* temp = res, *tempn;
while(temp != NULL && temp->next != NULL) {
ListNode* tempn = temp->next;
if(tempn->next && tempn->next->val == tempn->val) {
ListNode* tempp;
while(tempn->next && tempn->next->val == tempn->val) {
tempp = tempn->next;
tempn->next = tempp->next;
}
temp->next = tempn->next;
}
else
temp = temp->next;
}
return res->next;
}
};
Leetcode83. Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:1
2Input: 1->1->2
Output: 1->2
Example 2:1
2Input: 1->1->2->3->3
Output: 1->2->3
删掉链表中重复多余的数字1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* temp = head;
ListNode* res = new ListNode(-1);
ListNode* cur = res;
if(temp != NULL && temp->next == NULL)
return head;
while(temp != NULL && temp->next != NULL) {
while(temp->next != NULL && temp->val == temp->next->val)
temp = temp->next;
cur->next = temp;
cur = cur->next;
temp = temp->next;
}
return res->next;
}
};
Leetcode84. Largest Rectangle in Histogram
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.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
Example:1
2Input: [2,1,5,6,2,3]
Output: 10
这里维护一个栈,用来保存递增序列,相当于上面那种方法的找局部峰值。我们可以看到,直方图矩形面积要最大的话,需要尽可能的使得连续的矩形多,并且最低一块的高度要高。有点像木桶原理一样,总是最低的那块板子决定桶的装水量。那么既然需要用单调栈来做,首先要考虑到底用递增栈,还是用递减栈来做。我们想啊,递增栈是维护递增的顺序,当遇到小于栈顶元素的数就开始处理,而递减栈正好相反,维护递减的顺序,当遇到大于栈顶元素的数开始处理。那么根据这道题的特点,我们需要按从高板子到低板子的顺序处理,先处理最高的板子,宽度为1,然后再处理旁边矮一些的板子,此时长度为2,因为之前的高板子可组成矮板子的矩形 ,因此我们需要一个递增栈,当遇到大的数字直接进栈,而当遇到小于栈顶元素的数字时,就要取出栈顶元素进行处理了,那取出的顺序就是从高板子到矮板子了,于是乎遇到的较小的数字只是一个触发,表示现在需要开始计算矩形面积了,为了使得最后一块板子也被处理,这里用了个小 trick,在高度数组最后面加上一个0,这样原先的最后一个板子也可以被处理了。由于栈顶元素是矩形的高度,那么关键就是求出来宽度,那么跟之前那道 Trapping Rain Water 一样,单调栈中不能放高度,而是需要放坐标。由于我们先取出栈中最高的板子,那么就可以先算出长度为1的矩形面积了,然后再取下一个板子,此时根据矮板子的高度算长度为2的矩形面积,以此类推,知道数字大于栈顶元素为止,再次进栈。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s;
int res = 0;
heights.push_back(0);
for(int i = 0; i < heights.size(); i ++) {
if(s.empty() || heights[s.top()] < heights[i])
s.push(i);
else {
int cur = s.top();
s.pop();
res = max(res, heights[cur]*(s.empty() ? i : (i - s.top() - 1)));
i --;
}
}
return res;
}
};
遍历数组,每找到一个局部峰值(只要当前的数字大于后面的一个数字,那么当前数字就看作一个局部峰值,跟前面的数字大小无关),然后向前遍历所有的值,算出共同的矩形面积,每次对比保留最大值。这里再说下为啥要从局部峰值处理,看题目中的例子,局部峰值为 2,6,3,我们只需在这些局部峰值出进行处理,为啥不用在非局部峰值处统计呢,这是因为非局部峰值处的情况,后面的局部峰值都可以包括,比如1和5,由于局部峰值6是高于1和5的,所有1和5能组成的矩形,到6这里都能组成,并且还可以加上6本身的一部分组成更大的矩形,那么就不用费力气去再统计一个1和5处能组成的矩形了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int res = 0;
for(int i = 0; i < heights.size(); i ++) {
if(i + 1 < heights.size() && heights[i] <= heights[i+1])
continue;
int minn = heights[i];
for(int k = i; k >= 0; k --) {
minn = min(heights[k], minn);
int area = minn * (i - k + 1);
res = max(res, area);
}
}
return res;
}
};
这种做法也是单调栈,不过是两遍单调栈,首先从左到右直到让这个柱子左边高的都弹出去,直到有比这个柱子矮的,那么此时这个矮柱子就是当前柱子能够生成最大矩形的限制条件。右边也是。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int res = -1, len = heights.size();
stack<int> st;
vector<int> ans(len, 1);
for (int i = 0; i < len; i ++) {
while (!st.empty() && heights[st.top()] >= heights[i])
st.pop();
if (st.empty()) // 比我大的都弹出去了,所以我是最矮的一个
ans[i] += i;
else
ans[i] += (i - 1 - st.top());
st.push(i);
}
while(!st.empty()) st.pop();
for (int i = len-1; i >= 0; i --) {
while(!st.empty() && heights[st.top()] >= heights[i])
st.pop();
if (st.empty())// 比我大的都弹出去了,所以我是最矮的一个
ans[i] += (len - 1 - i);
else
ans[i] += (st.top() - 1 - i);
// 现在我这个柱子形成了一个山峰,当前区间我是最高的
st.push(i);
res = max(res, ans[i]*heights[i]);
}
return res;
}
};
Leetcode85. Maximal Rectangle
Given a rows x cols binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Example:1
2
3
4
5
6
7
8Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
这里我们统计每一行的连续1的个数,使用一个数组 h_max, 其中 h_max[i][j] 表示第i行,第j个位置水平方向连续1的个数,若 matrix[i][j] 为0,那对应的 h_max[i][j] 也一定为0。统计的过程跟建立累加和数组很类似,唯一不同的是遇到0了要将 h_max 置0。这个统计好了之后,只需要再次遍历每个位置,首先每个位置的 h_max 值都先用来更新结果 res,因为高度为1也可以看作是矩形,然后我们向上方遍历,上方 (i, j-1) 位置也会有 h_max 值,但是用二者之间的较小值才能构成矩形,用新的矩形面积来更新结果 res,这样一直向上遍历,直到遇到0,或者是越界的时候停止,这样就可以找出所有的矩形了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.size() == 0)
return 0;
int res = 0;
int width = matrix.size();
int height = matrix[0].size();
vector<vector<int>> dp(width, vector<int>(height, 0));
for (int i = 0; i < width; i ++) {
for (int j = 0; j < height; j ++) {
if (matrix[i][j] == '1') {
dp[i][j] = (j == 0 ? 1 : dp[i][j-1]+1);
int length = dp[i][j];
for (int k = i; k >= 0; k --) {
length = min(length, dp[k][j]);
res = max(res, length*(i-k+1));
}
}
}
}
return res;
}
};
看一下这种方法,当成直方图来处理:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
int res = 0;
vector<int> height;
for (int i = 0; i < matrix.size(); ++i) {
height.resize(matrix[i].size());
for (int j = 0; j < matrix[i].size(); ++j) {
height[j] = matrix[i][j] == '0' ? 0 : (1 + height[j]);
}
res = max(res, largestRectangleArea(height));
}
return res;
}
int largestRectangleArea(vector<int>& height) {
int res = 0;
stack<int> s;
height.push_back(0);
for (int i = 0; i < height.size(); ++i) {
if (s.empty() || height[s.top()] <= height[i]) s.push(i);
else {
int tmp = s.top(); s.pop();
res = max(res, height[tmp] * (s.empty() ? i : (i - s.top() - 1)));
--i;
}
}
return res;
}
};
考虑这样一个算法,对于每个点,我们先不断向上直到遇到零,然后向两边扩展,直到某列出现0。这种方式构建的矩形中必然存在最大矩形。
我们通过定义三个数组height,left,right来记录每个点的高度,左边界和右边界,问题转化为如何更新每个数组。
- 对于height数组,new_height[j]=old_height[j]+1 if row[j]==‘1’。
- 对于left数组,new_left[j]=max(old_left[j],cur_left),其中cur_left是遇到的最右边的0的序号加1,向左扩展矩形时不能超过点,否则会遇到0。
- 对于right数组,new_right[j]=min(old_right[j],cur_right),cur_right表示我们遇到的最左边的0的序号。这里不减去1是因为这样就可以用height[j]*(right[j]-left[j])来计算矩形面积,也就是说矩形的底边由半开半闭区间[l,r)决定。为了记录正确的cur_right需要从右向左迭代,因此更新right时需要从右向左。C++代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44//解法3:动态规划2:时间复杂度O(NM)[],空间复杂度O(N)
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.size() == 0) return 0;
int m = matrix.size();
int n = matrix[0].size();
//分别存储每一行上元素对应的最大矩形的高度以及左右区间
vector<int> left(n, 0);//最大的左边界为左端
vector<int> right(n, n);//最大的有边界为右端
vector<int> height(n, 0);
int maxarea = 0;
for (int i = 0; i < m; i++) {
int cur_left = 0, cur_right = n;
//更新高度,最后存储在height数组的就是每一列‘1’的个数
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1')
height[j]++;
else
height[j] = 0;
}
//更新左边界,
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1')
left[j] = max(left[j], cur_left);
else {
left[j] = 0;
cur_left = j + 1;
}
}
//更新右边界
for (int j = n - 1; j >= 0; j--) {
if (matrix[i][j] == '1')
right[j] = min(right[j], cur_right);
else {
right[j] = n;
cur_right = j;
}
}
for (int j = 0; j < n; j++) {
maxarea = max(maxarea, (right[j] - left[j]) * height[j]);
}
}
return maxarea;
}
Leetcode86. Partition List
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.
Example:1
2Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
把链表分成两部分,一部分都大于k,另一部分都小于k。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if(head==nullptr)
return head;
ListNode *prehead = new ListNode(-1, head);
ListNode *l = head, *lprev = prehead;
while(l && l->val < x) {
lprev = l;
l = l->next;
}
if(l == NULL)
return head;
ListNode *r = l->next, *rprev = l;
while(r) {
if(r && r->val >= x) {
rprev = r;
r = r->next;
}
else {
rprev->next = r->next;
r->next = l;
lprev->next = r;
lprev = r;
r = rprev->next;
}
}
return prehead->next;
}
};
Leetcode88. Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。很简单
1 | class Solution { |
1 | class Solution { |
Leetcode89. Gray Code
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.
Example 1:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2
For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.
00 - 0
10 - 2
11 - 3
01 - 1
Example 2:1
2
3
4
5Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
Therefore, for n = 0 the gray code sequence is [0].
蓝色部分由于最高位加的是 0 ,所以它的数值和 n = 2 的所有解的情况一样。而橙色部分由于最高位加了 1,所以值的话,就是在其对应的值上加 4,也就是 [公式] ,即 [公式] ,也就是 1 << ( n - 1) 。所以我们的算法可以用迭代求出来了。
所以如果知道了 n = 2 的解的话,如果是 { 0, 1, 3, 2},那么 n = 3 的解就是 { 0, 1, 3, 2, 2 + 4, 3 + 4, 1 + 4, 0 + 4 },即 { 0 1 3 2 6 7 5 4 }。之前的解直接照搬过来,然后倒序把每个数加上 1 << ( n - 1) 添加到结果中即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res;
res.push_back(0);
if(n == 0) {
return res;
}
for(int i = 0; i < n; i ++) {
int add = 1 << i;
for(int j = res.size()-1; j >= 0; j --) {
res.push_back(res[j] + add);
}
}
return res;
}
};
Leetcode90. Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:1
2
3
4
5
6
7
8
9
10Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
由于数组事先已经过排序,因此不需要再用额外的unordered_set去判断重复元素,直接判断nums[i]和nums[i - 1]是否相等就行了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
void search(int start, vector<int>& sub, vector<vector<int>>& res, vector<int>& nums) {
res.push_back(sub);
for(int i = start; i < nums.size(); i ++) {
if(i == start || nums[i] != nums[i - 1]){
sub.push_back(nums[i]);
search(i + 1, sub, res, nums);
sub.pop_back();
}
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> res;
vector<int> sub;
sort(nums.begin(), nums.end());
search(0, sub, res, nums);
return res;
}
};
Leetcode91. Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:1
2
3
4'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:1
2
3Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:1
2
3Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
这道题要求解码方法,跟之前那道 Climbing Stairs 非常的相似,但是还有一些其他的限制条件,比如说一位数时不能为0,两位数不能大于 26,其十位上的数也不能为0,除去这些限制条件,跟爬梯子基本没啥区别,也勉强算特殊的斐波那契数列,当然需要用动态规划 Dynamci Programming 来解。建立一维 dp 数组,其中 dp[i] 表示s中前i个字符组成的子串的解码方法的个数,长度比输入数组长多多1,并将 dp[0] 初始化为1。现在来找状态转移方程,dp[i] 的值跟之前的状态有着千丝万缕的联系,就拿题目中的例子2来分析吧,当 i=1 时,对应s中的字符是 s[0]=’2’,只有一种拆分方法,就是2,注意 s[0] 一定不能为0,这样的话无法拆分。当 i=2 时,对应s中的字符是 s[1]=’2’,由于 s[1] 不为0,那么其可以被单独拆分出来,就可以在之前 dp[i-1] 的每种情况下都加上一个单独的2,这样 dp[i] 至少可以有跟 dp[i-1] 一样多的拆分情况,接下来还要看其能否跟前一个数字拼起来,若拼起来的两位数小于等于26,并且大于等于 10(因为两位数的高位不能是0),那么就可以在之前 dp[i-2] 的每种情况下都加上这个二位数,所以最终 dp[i] = dp[i-1] + dp[i-2],是不是发现跟斐波那契数列的性质吻合了。所以0是个很特殊的存在,若当前位置是0,则一定无法单独拆分出来,即不能加上 dp[i-1],就只能看否跟前一个数字组成大于等于 10 且小于等于 26 的数,能的话可以加上 dp[i-2],否则就只能保持为0了。具体的操作步骤是,在遍历的过程中,对每个数字首先判断其是否为0,若是则将 dp[i] 赋为0,若不是,赋上 dp[i-1] 的值,然后看数组前一位是否存在,如果存在且满足前一位是1,或者和当前位一起组成的两位数不大于 26,则当前 dp[i] 值加上 dp[i - 2]。最终返回 dp 数组的最后一个值即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int numDecodings(string s) {
if (s.empty() || s[0] == '0')
return 0;
int len = s.length();
vector<int> dp(len+1, 0);
dp[0] = 1;
for(int i = 1; i < len+1; i ++){
dp[i] = s[i-1] == '0' ? 0 : dp[i-1];
if(i > 1 && (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')))
dp[i] += dp[i-2];
}
return dp[len];
}
};
Leetcode92. Reverse Linked List II
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:1
2Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
对于链表的问题,根据以往的经验一般都是要建一个dummy node,连上原链表的头结点,这样的话就算头结点变动了,我们还可以通过dummy->next来获得新链表的头结点。这道题的要求是只通过一次遍历完成,就拿题目中的例子来说,变换的是2,3,4这三个点,我们需要找到第一个开始变换结点的前一个结点,只要让pre向后走m-1步即可,为啥要减1呢,因为题目中是从1开始计数的,这里只走了1步,就是结点1,用pre指向它。万一是结点1开始变换的怎么办,这就是我们为啥要用dummy结点了,pre也可以指向dummy结点。然后就要开始交换了,由于一次只能交换两个结点,所以我们按如下的交换顺序:
1 -> 2 -> 3 -> 4 -> 5 -> NULL
1 -> 3 -> 2 -> 4 -> 5 -> NULL
1 -> 4 -> 3 -> 2 -> 5 -> NULL
我们可以看出来,总共需要n-m步即可,第一步是将结点3放到结点1的后面,第二步将结点4放到结点1的后面。这是很有规律的操作,那么我们就说一个就行了,比如刚开始,pre指向结点1,cur指向结点2,然后我们建立一个临时的结点t,指向结点3(注意我们用临时变量保存某个结点就是为了首先断开该结点和前面结点之间的联系,这可以当作一个规律记下来),然后我们断开结点2和结点3,将结点2的next连到结点4上,也就是 cur->next = t->next,再把结点3连到结点1的后面结点(即结点2)的前面,即 t->next = pre->next,最后再将原来的结点1和结点2的连接断开,将结点1连到结点3,即 pre->next = t。这样我们就完成了将结点3取出,加入结点1的后方。第二步将结点4取出,加入结点1的后方,也是同样的操作,这里就不多说了,请大家自己尝试下吧,参见代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
int count = 0;
ListNode *res = new ListNode(-1, head);
ListNode *pre = res, *cur = pre;
for(count = 0; count < m; count ++) {
pre = cur;
cur = cur->next;
}
for(count = m; count < n; count ++) {
ListNode *temp = cur->next;
cur->next = temp->next;
temp->next = pre->next;
pre->next = temp;
}
return res->next;
}
};
Leetcode93. Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations. A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.
Example:1
2Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
这个题可以运用dfs,那么回溯算法的循环和终止条件是什么呢?IP地址由四部分构成,可以设置一个变量segment,当segment = 4时,可结束循环,将结果添加到列表中;每个部分数值均值0—-255之间,因此每次回溯最多需要判断3个元素,即当前元素i—-i+2这三位数字。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution {
public:
void dfs(string s, int segment, vector<string>& res, string ip, int len) {
if(segment == 4) {
if(s == "" && ip.length() == len + 4)
res.push_back(ip.substr(0, ip.length()-1));
return;
}
int temp = 0;
string t = "";
for(int i = 0; i < s.length() && i < 3; i ++) {
temp = temp * 10 + (s[i] - '0');
t += s[i];
if(i > 0 && temp == 0)
return;
else if(temp <= 255)
dfs(s.substr(i+1), segment + 1, res, ip + to_string(temp) + ".", len);
}
}
vector<string> restoreIpAddresses(string s) {
vector<string> res;
string temp = "";
dfs(s, 0, res, temp, s.length());
return res;
}
};
Leetcode94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes’ values.
Example:1
2
3
4
5
6
7Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
需要用栈来做,思路是从根节点开始,先将根节点压入栈,然后再将其所有左子结点压入栈,然后取出栈顶节点,保存节点值,再将当前指针移到其右子节点上,若存在右子节点,则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if(root == NULL)
return {};
vector<int> res;
stack<TreeNode*> q;
TreeNode* temp = root;
while(temp || !q.empty()) {
while(temp) {
q.push(temp);
temp = temp->left;
}
temp = q.top();
q.pop();
res.push_back(temp->val);
temp = temp->right;
}
return res;
}
};
Leetcode95. Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.
Example:1
2
3
4
5
6
7
8
9Input: 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
2
3
4
51 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
这种建树问题一般来说都是用递归来解,这道题也不例外,划分左右子树,递归构造。这个其实是用到了大名鼎鼎的分治法 Divide and Conquer,类似的题目还有之前的那道 Different Ways to Add Parentheses 用的方法一样,用递归来解,划分左右两个子数组,递归构造。刚开始时,将区间 [1, n] 当作一个整体,然后需要将其中的每个数字都当作根结点,其划分开了左右两个子区间,然后分别调用递归函数,会得到两个结点数组,接下来要做的就是从这两个数组中每次各取一个结点,当作当前根结点的左右子结点,然后将根结点加入结果 res 数组中即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> dfs(int start, int end) {
if(start > end) {
return {NULL};
}
vector<TreeNode*> res;
for(int i = start; i <= end; i ++) {
vector<TreeNode*> a = dfs(start, i-1);
vector<TreeNode*> b = dfs(i+1, end);
for(auto aa : a)
for(auto bb : b) {
TreeNode *temp = new TreeNode(i);
temp->left = aa;
temp->right = bb;
res.push_back(temp);
}
}
return res;
}
vector<TreeNode*> generateTrees(int n) {
if(n == 0)
return {};
return dfs(1, n);
}
};
我们可以使用记忆数组来优化,保存计算过的中间结果,从而避免重复计算。注意这道题的标签有一个是动态规划 Dynamic Programming,其实带记忆数组的递归形式就是 DP 的一种,memo[i][j] 表示在区间 [i, j] 范围内可以生成的所有 BST 的根结点,所以 memo 必须是一个三维数组,这样在递归函数中,就可以去 memo 中查找当前的区间是否已经计算过了,是的话,直接返回 memo 中的数组,否则就按之前的方法去计算,最后计算好了之后要更新 memo 数组。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31class Solution {
public:
vector<TreeNode*> dfs(int start, int end, vector<vector<vector<TreeNode*>>>& memo) {
if(start > end) {
return {NULL};
}
if(!memo[start - 1][end - 1].empty())
return memo[start - 1][end - 1];
vector<TreeNode*> res;
for(int i = start; i <= end; i ++) {
vector<TreeNode*> a = dfs(start, i-1, memo);
vector<TreeNode*> b = dfs(i+1, end, memo);
for(auto aa : a)
for(auto bb : b) {
TreeNode *temp = new TreeNode(i);
temp->left = aa;
temp->right = bb;
res.push_back(temp);
}
}
return memo[start - 1][end - 1] = res;
}
vector<TreeNode*> generateTrees(int n) {
if(n == 0)
return {};
vector<vector<vector<TreeNode*>>> memo(n, vector<vector<TreeNode*>>(n));
return dfs(1, n, memo);
}
};
Leetcode96. Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
Example:1
2
3
4
5
6
7
8
9
10Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
思路:对于选定结点的元素,左边的元素构成左子树,右边的元素构成右子树,左子树和右子树构成种树的乘积就是总的个数。考虑根节点,设对于任意根节点k,有f(k)种树的可能。比k小的k-1个元素构成k的左子树。则左子树有f(k-1)种情况。比k大的n-k个元素构成k的右子树。则右子树有f(n-k)种情况。
易知,左右子树相互独立,所以f(k)=f(k-1)*f(n-k)。综上,对于n,结果为k取1,2,3,…,n时,所有f(k)的和。
代码思路:根据上述思路可以用简单的递归方法快速解决。现在考虑动态规划求解算法,用数组记录每个f(i)的值,记f(0)=1,f(1)=1。根据公式:f(k)=f(k-1)*f(n-k),访问数组中的元素。循环求和,结果更新到数组中1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int numTrees(int n) {
if(n <= 1)
return 1;
int dp[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n ; i ++) {
dp[i] = 0;
for(int j = 1; j <= i; j ++)
dp[i] += dp[i - j] * dp[j - 1];
}
return dp[n];
}
};
Leetcode97. Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:1
2Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:1
2Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
这道求交织相错的字符串,只要是遇到字符串的子序列或是匹配问题直接就上动态规划 Dynamic Programming,其他的都不要考虑,什么递归呀的都是浮云(当然带记忆数组的递归写法除外,因为这也可以算是 DP 的一种),千辛万苦的写了递归结果拿到 OJ 上妥妥 Time Limit Exceeded,能把人气昏了,所以还是直接就考虑 DP 解法省事些。一般来说字符串匹配问题都是更新一个二维 dp 数组,核心就在于找出状态转移方程。那么我们还是从题目中给的例子出发吧,手动写出二维数组 dp 如下:1
2
3
4
5
6
7Ø d b b c a
Ø T F F F F F
a T F F F F F
a T T T T T F
b F T T F T F
c F F T T T T
c F F F T F T
首先,这道题的大前提是字符串 s1 和 s2 的长度和必须等于 s3 的长度,如果不等于,肯定返回 false。那么当 s1 和 s2 是空串的时候,s3 必然是空串,则返回 true。所以直接给 dp[0][0] 赋值 true,然后若 s1 和 s2 其中的一个为空串的话,那么另一个肯定和 s3 的长度相等,则按位比较,若相同且上一个位置为 True,赋 True,其余情况都赋 False,这样的二维数组 dp 的边缘就初始化好了。下面只需要找出状态转移方程来更新整个数组即可,我们发现,在任意非边缘位置 dp[i][j] 时,它的左边或上边有可能为 True 或是 False,两边都可以更新过来,只要有一条路通着,那么这个点就可以为 True。那么我们得分别来看,如果左边的为 True,那么我们去除当前对应的 s2 中的字符串 s2[j - 1] 和 s3 中对应的位置的字符相比(计算对应位置时还要考虑已匹配的s1中的字符),为 s3[j - 1 + i], 如果相等,则赋 True,反之赋 False。 而上边为 True 的情况也类似,所以可以求出状态转移方程为:1
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);
其中 dp[i][j] 表示的是 s2 的前 i 个字符和 s1 的前 j 个字符是否匹配 s3 的前 i+j 个字符,根据以上分析,可写出代码如下:
解法一:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
if(n1 + n2 != n3)
return false;
bool dp[n1+1][n2+1];
dp[0][0] = true;
for(int i = 1; i <= n1; i ++)
dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1];
for(int i = 1; i <= n2; i ++)
dp[0][i] = dp[0][i-1] && s2[i-1] == s3[i-1];
for(int i = 1; i <= n1; i ++)
for(int j = 1; j <= n2; j ++)
dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i-1+j]) ||
(dp[i][j-1] && s2[j-1] == s3[j-1+i]);
return dp[n1][n2];
}
};
我们也可以把for循环合并到一起,用if条件来处理边界情况,整体思路和上面的解法没有太大的区别,参见代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size()) return false;
int n1 = s1.size(), n2 = s2.size();
vector<vector<bool>> dp(n1 + 1, vector<bool> (n2 + 1, false));
for (int i = 0; i <= n1; ++i) {
for (int j = 0; j <= n2; ++j) {
if (i == 0 && j == 0) {
dp[i][j] = true;
} else if (i == 0) {
dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];
} else if (j == 0) {
dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1];
} else {
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
}
}
}
return dp[n1][n2];
}
};
Leetcode98. Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:1
2
3
4
5 2
/ \
1 3
Input: [2,1,3]
Output: true
Example 2:1
2
3
4
5
6
7
8 5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
可以利用它本身的性质来做,即左<根<右,也可以通过利用中序遍历结果为有序数列来做,下面我们先来看最简单的一种,就是利用其本身性质来做,初始化时带入系统最大值和最小值,在递归过程中换成它们自己的节点值,用long代替int就是为了包括int的边界条件。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
bool isvalid(TreeNode* root, long minn, long maxx) {
if(root == NULL)
return true;
if(!(minn < root->val && root->val < maxx))
return false;
return isvalid(root->left, minn, root->val) && isvalid(root->right, root->val, maxx);
}
bool isValidBST(TreeNode* root) {
if(root == NULL)
return true;
return isvalid(root, LONG_MIN, LONG_MAX);
}
};
Leetcode99. Recover Binary Search Tree
You are given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
Example 1:1
2
3Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
Example 2:1
2
3Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
这道题要求我们复原一个二叉搜索树,说是其中有两个的顺序被调换了。用双指针来代替一维向量的,但是这种方法用到了递归,也不是 O(1) 空间复杂度的解法,这里需要三个指针,first,second 分别表示第一个和第二个错乱位置的节点,pre 指向当前节点的中序遍历的前一个节点。这里用传统的中序遍历递归来做,不过再应该输出节点值的地方,换成了判断 pre 和当前节点值的大小,如果 pre 的大,若 first 为空,则将 first 指向 pre 指的节点,把 second 指向当前节点。这样中序遍历完整个树,若 first 和 second 都存在,则交换它们的节点值即可。这个算法的空间复杂度仍为 O(n),n为树的高度。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution {
public:
TreeNode *first, *second, *pre = NULL;
void recoverTree(TreeNode* root) {
helper(root);
swap(first->val, second->val);
}
void helper(TreeNode* root) {
if(root == NULL)
return ;
helper(root->left);
if (!pre)
pre = root;
else {
if (pre->val > root->val) {
if (!first)
first = pre;
second = root;
}
pre = root;
}
helper(root->right);
}
};
题目要求上说 O(n) 的解法很直观,这种解法需要用到递归,用中序遍历树,并将所有节点存到一个一维向量中,把所有节点值存到另一个一维向量中,然后对存节点值的一维向量排序,在将排好的数组按顺序赋给节点。
1 | // O(n) space complexity |
Leetcode100. Same Tree
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.
Example 1:1
2
3
4
5
6Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true
Example 2:1
2
3
4
5
6Input: 1 1
/ \
2 2
[1,2], [1,null,2]
Output: false
Example 3:1
2
3
4
5
6Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false
递归判断两个树是不是一样的,简单。1
2
3
4
5
6
7
8
9class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == NULL && q == NULL) return true;
if(p == NULL || q == NULL) return false;
if(p->val != q->val) return false;
else return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};