30. 串联所有单词的子串
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
1
2
3
4
| 输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
|
解释：
从索引 0 和 9 开始的子串分别是 “barfoor” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
1
2
3
4
| 输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]
|
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
| class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
map<string,int> mp;
vector<int> wstart;
vector<int> ans;
if(s.size()==0||words.size()==0) return ans;
for(int i=0;i<(int)words.size();i++)
mp[words[i]]++;
int wlen=(int)words[0].length();
for(int i=0;i+wlen<=(int)s.size();i++){
string ss=s.substr(i,wlen);
int id=mp[ss];
if(id) wstart.push_back(i);
}
int wnum=(int)words.size();
for(int i=0;i+wnum<=(int)wstart.size();i++){
map<string,int> window;
int cnt=0;
for(int j=i;j<(int)wstart.size()&&wstart[j]<=wstart[i]+cnt*wlen&&cnt<wnum;j++)
if(wstart[j]==wstart[i]+cnt*wlen) {
++window[s.substr(wstart[j],wlen)];
++cnt;
}
bool valid=true;
for(auto it=mp.begin();it!=mp.end();it++)
if(window[it->first]!=it->second) {valid=false; break;}
if(valid) ans.push_back(wstart[i]);
}
return ans;
}
};
|
一开始的想法是滑动窗口，但是因为下面这个例子总是超时…
1
2
3
| 最后执行的输入：
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa..."
["a","a","a","a","a","a","a","a"....]
|
代码如下：
主要想法就是先遍历一遍s，然后把在words中的单词的首字母的索引记录在mask中
然后遍历mask，当前位置为index，然后再一层循环，先copy一份words，然后mask后面的单词如果再words中，就删除一个，知道删除为0为止，说明这个index是合法的，然后加入ans中，index++，重复。
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
| vector<int> findSubstring(string s, vector<string>& words) {
vector<string> cor;
vector<int> ans;
if(s.length() == 0 || words.size() == 0 || s.length() < words[0].length()) {
return ans;
}
int length = words[0].length();
vector<int> mask;
for(int i = 0;i <= s.length() - length;i++) {
vector<string>::iterator ret;
ret = find(words.begin(), words.end(), s.substr(i, length));
if(ret != words.end()) {
mask.push_back(i);
}
}
bool isTrue = false;
int index;
for(int i = 0;i < mask.size();i++) {
isTrue = true;
index = mask[i];
vector<string> wordcopy = words;
for(int j = 0;j < words.size();j++) {
vector<int>::iterator it;
it = find(mask.begin(), mask.end(), index + j * length);
if(it == mask.end()) {
break;
} else {
vector<string>::iterator iter=std::find(wordcopy.begin(),wordcopy.end(),s.substr(index + j * length, length));
if(iter != wordcopy.end()) {
wordcopy.erase(iter);
} else {
break;
}
}
}
if(wordcopy.empty()) {
ans.push_back(index - wordcopy[0].size() * wordcopy.size());
}
}
return ans;
}
|
31. 下一个排列
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1
2
3
| 1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,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
| class Solution {
public:
void nextPermutation(vector<int>& nums) {
if(nums.size() <= 1) {
return ;
}
int i = nums.size() - 1;
while(i - 1 >= 0 && nums[i] <= nums[i - 1]) {
i--;
}
if(i - 1 < 0) {
sort(nums.begin(), nums.end());
} else {
int minIndex = i;
int min = nums[i];
for(int j = i;j < nums.size();j++) {
if(nums[j] < min && nums[j] > nums[i - 1]) {
min = nums[j];
minIndex = j;
}
}
int temp = nums[i - 1];
nums[i - 1] = nums[minIndex];
nums[minIndex] = temp;
sort(nums.begin() + i, nums.end());
}
}
};
|
解释：大致的思路就是，从后往前遍历vector，后一个数字(index = i)必须比前一个数字(index = i - 1)小，如果不满足的话，就说明需要进行下一个排列
下一个排列的方法，在i及其后面寻找到一个最小的但是比i大的值，然后进行元素替换(i - 1和最小值)，剩下的就是对i及其后面的元素进行排序
如果已经到最前的数字了(即i=1)，说明已经是最大值了，则将全部元素进行sort即可。
32. 最长有效括号
给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
1
2
3
| 输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
|
示例 2:
1
2
3
| 输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
|
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
|
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
int longestValidParentheses(string s) {
int isValid[s.length()] = {0};
int max = 0;
vector<int> preLeft;
for(int i = 0;i < s.length();i++) {
if(s[i] == '(') {
preLeft.push_back(i);
isValid[i] = 1;
} else {
if(preLeft.size() == 0) {
isValid[i] = -1;
} else {
preLeft.pop_back();
int pre = preLeft.back();
isValid[pre] = 0;
}
}
}
for(int i = 0;i < s.length();i++) {
cout << isValid[i] << " ";
}
cout << endl;
for(int i = 0;i < s.length();i++) {
int count = 0;
while(i < s.length() && isValid[i] == 0) {
count++;
i++;
}
max = max > count ? max : count;
}
return max;
}
int main() {
string s = ")()())";
cout << longestValidParentheses(s);
}
|
解释：
preLeft用来保存上一次没有完成匹配的左括号
isValid[]用来标记已经匹配的括号，当isValid[k] = 1，则表明该左括号未完成匹配，如果isValid[k] = 0，则表明该括号（有可能是左，也有可能是右）已经完成匹配，如果isValid[k] = -1，表明该右括号未完成匹配
然后遍历s，当遇到左括号，isValid[i] = 1，并且preLeft.push_back[i]，保存未匹配的左括号，当遇到右括号，如果此时preLeft中还有未完成匹配的左括号，则通过preLeft``来获取其下标j，然后将isValid[j] = 0，表明该左括号已经完成匹配；如果此时preLeft.size() == 0，表明该右括号为非法的右括号，则令isValid[i] = -1
然后遍历isValid，求其中连续0最长的个数，返回即可。
第一次没有参考做出一道难题，很是开心哈哈哈哈！！