209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
1
2
3
| 输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
|
思路：这个问题其实很容易就能想到在O(n2)的时间复杂度下解决问题，但是这里采用了一种O(nlogn)的做法去解决这个问题。
首先，我们先求解sums数组，表示从头加到当前位置的和。
然后从i = 1到n枚举
上Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int minSubArrayLen2(int s, vector<int>& nums) {
int n = nums.size();
if(n == 0) {
return 0;
}
int ans = INT_MAX;
vector<int> sums(n + 1, 0);
for(int i = 1;i <= n;i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
for(int i = 1;i <= n;i++) {
int to_find = s + sums[i - 1];
auto bound = lower_bound(sums.begin(), sums.end(), to_find);
if(bound != sums.end()) {
ans = min(ans, static_cast<int> (bound - (sums.begin() + i - 1)));
}
}
return (ans != INT_MAX) ? ans : 0;
}
|
关于lower_bound && upper_bound的测试
1
2
3
4
5
6
7
8
| int a[] = {0, 1, 2, 2,3};
vector<int> num(a, a + 5);
for(int i = 0;i < num.size();i++) {
cout << num[i] << " ";
}
cout << endl;
cout << static_cast<int> (lower_bound(num.begin(), num.end(), 2) - num.begin()) << endl;
cout << static_cast<int> (upper_bound(num.begin(), num.end(), 2) - num.begin()) << endl;
|
128. 最长连续序列
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
1
2
3
| 输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
|
思路：
哈希表 + 线性空间的构造
我们先将所有元素放进一个Hash set中，然后遍历num_set中的每一个元素，如果它前面一个数字没有在num_set中，那么它一定不是一个连续数组的开始，则跳过。如果是连续数组的开始，那么就需要一种往后找连续的元素是否存在，然后记录下最长的数列长度。
上Code：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
set<int> num_set;
int maxLength = 0;
for(int num : nums) {
num_set.insert(num);
}
for(int num : num_set) {
if(num_set.find(num - 1) == num_set.end()) {
int currentNum = num;
int currentLen = 1;
while(num_set.find(currentNum + 1) != num_set.end()) {
currentNum += 1;
currentLen += 1;
}
maxLength = max(maxLength, currentLen);
}
}
return maxLength;
}
};
|
这里虽然看上去复杂度挺高，但实际上是O(n)复杂度的，因为每个数字只会遍历到一次，因为如果不是连续数字开头的，就直接跳过了，而是连续数字开头的，就一直遍历到连续数字的末尾，所以总的时间复杂度是O(n)的。
126. 单词接龙II
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
1
2
3
4
5
6
7
8
9
10
| 输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
|
示例 2:
1
2
3
4
5
6
7
| 输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
|
思路：双向BFS
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
| class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_map<string,int> freqs;
for(const auto &word:wordList)
freqs[word]=0;
if(freqs.count(endWord)==0) return 0;
queue<string> q1({beginWord}), q2({endWord});
int step=1;
for(freqs[beginWord]|=1,freqs[endWord]|=2; q1.size() && q2.size(); ++step){
bool first=q1.size()<q2.size();
queue<string> &q=first?q1:q2;
int flag=first?1:2;
for(int size=q.size(); size--; q.pop()){
string &word=q.front();
if(freqs[word]==3) return step;
for(int i=0; i<word.length(); ++i){
for(char ch='a'; ch<='z'; ++ch){
string s=word;
if(s[i]==ch) continue;
s[i]=ch;
if(freqs.count(s)==0 || freqs[s]&flag) continue;
freqs[s]|=flag;
q.push(s);
}
}
}
}
return 0;
}
};
|