leetcode 1016. 子串能表示从 1 到 N 数字的二进制串
给定一个二进制字符串 S（一个仅由若干 ‘0’ 和 ‘1’ 构成的字符串）和一个正整数 N，如果对于从 1 到 N 的每个整数 X，其二进制表示都是 S 的子串，就返回 true，否则返回 false。
1
2
3
4
5
6
7
8
| 示例 1：
输入：S = "0110", N = 3
输出：true
示例 2：
输入：S = "0110", N = 4
输出：false
|
- 1 <= S.length <= 1000
- 1 <= N <= 10^9
思路：暴力即可，因为要在S中找的是子串，不是子序列，S的长度最大为1000，可表示的数字有限。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
bool queryString(string S, int N) {
for(int i=1;i<=N;i++){
int x = i;
string t = "";
while(x){
if(x & 1) t+='1';
else t+='0';
x>>=1;
}
reverse(t.begin(), t.end());
if(S.find(t) == -1) return false;
}
return true;
}
};
|
1306. 跳跃游戏 III
这里有一个非负整数数组 $arr$，你最开始位于该数组的起始下标 $start$ 处。当你位于下标 $i$ 处时，你可以跳到 $i + arr[i]$ 或者 $i - arr[i]$。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意，不管是什么情况下，你都无法跳到数组之外。
1
2
3
4
5
6
7
8
| 示例 1：
输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案：
下标 5 -> 下标 4 -> 下标 1 -> 下标 3
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
|
1
2
3
4
5
6
7
| 示例 2：
输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案：
下标 0 -> 下标 4 -> 下标 1 -> 下标 3
|
1
2
3
4
5
| 示例 3：
输入：arr = [3,0,2,1,2], start = 2
输出：false
解释：无法到达值为 0 的下标 1 处。
|
- $1 <= arr.length <= 5 * 10^4$
- $0 <= arr[i] < arr.length$
- $0 <= start < arr.length$
思路：按照能到的位置bfs即可，设置一个标记数组标记已经访问过的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
bool canReach(vector<int>& arr, int start) {
int n = arr.size();
bool vis[n+1];
memset(vis,0,sizeof vis);
queue<int> q;
q.push(start);
while(!q.empty()){
auto p = q.front();
q.pop();
if(vis[p]) continue;
vis[p]=1;
if(arr[p]==0) return true;
if(p-arr[p] >= 0 && !vis[p-arr[p]]) q.push(p-arr[p]);
if(p+arr[p] < n && !vis[p+arr[p]]) q.push(p+arr[p]);
}
return false;
}
};
|
1371. 每个元音包含偶数次的最长子字符串
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ ，在子字符串中都恰好出现了偶数次。
1
2
3
4
5
| 示例 1：
输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
|
1
2
3
4
5
| 示例 2：
输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
|
1
2
3
4
5
| 示例 3：
输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
|
- $1 <= s.length <= 5 x 10^5$
- $s 只包含小写英文字母。$
思路：因为此题要找的是元音出现偶数次的最长子串，根据异或的性质可知，我们可以用一个int来标记所有出现的元音，所有元音第一次出现时对应二进制位标记为1，以后再出现时将其对应二进制位与其二进制位异或即可判断出现的所有元音的奇偶情况。
举例：amntyyaw,通过标记位标记位表示为：1 1 1 1 1 1 0 0
如果当前元音标记int为0，说明0-i的字串是满足要求的，因为如果当前字串中有元音出现奇数次那么标记位中一定有1存在。
如果当前元音标记int不为0，假设为x，那么从x首次出现的后一位到以x结尾这段字串是符合要求的，理由显而易见。
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
| class Solution {
public:
int findTheLongestSubstring(string s) {
int n = s.size(), res = 0, bitmask = 0;
int hash[32];
fill(hash,hash + 32,-1);
for(int i=0;i<n;i++){
if(s[i]=='a')
bitmask = !i ? 1<<0 : bitmask ^ (1<<0);
else if(s[i]=='e')
bitmask = !i ? 1<<1 : bitmask ^ (1<<1);
else if(s[i]=='i')
bitmask = !i ? 1<<2 : bitmask ^ (1<<2);
else if(s[i]=='o')
bitmask = !i ? 1<<3 : bitmask ^ (1<<3);
else if(s[i]=='u')
bitmask = !i ? 1<<4 : bitmask ^ (1<<4);
else bitmask = !i ? 0 : bitmask;
if(!bitmask) res = max(res,i + 1);
if(hash[bitmask] == -1) hash[bitmask] = i;
res = max(res, i - hash[bitmask]);
}
return res;
}
};
|