滑动窗口
209. 长度最小的子数组
int min(int a, int b) {
return a > b ? b : a;
}
int minSubArrayLen(int target, int *nums, int numsSize) {
int res = 0x7fffffff;
for (int l = 0, r = 0, sum = 0; r = target) {
sum -= nums[l];
l++;
}
// 记录所有位置结尾中的最短数组
if (sum >= target) res = min(res, r - l + 1);
}
return res == 0x7fffffff ? 0 : res;
}
3. 无重复字符的最长子串
int max(int a, int b) {
return a > b ? a : b;
}
int lengthOfLongestSubstring(char *s) {
int len = strlen(s);
if (len
int max(int a, int b) {
return a > b ? a : b;
}
int lengthOfLongestSubstring(char *s) {
int len = strlen(s);
int res = 0;
// 记录每个字符上次出现的位置
int last[128];
memset(last, -1, sizeof(int) * 128);
for (int l = 0, r = 0; r
76. 最小覆盖子串
// 题目默认如果存在则唯一
char *minWindow(char *s, char *t) {
int lenS = strlen(s);
int lenT = strlen(t);
if (lenS 0) {
map[s[l]]--;
l++;
}
if (r - l + 1
134. 加油站
// O(n^2)超时
int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
// 从每个位置开始尝试
for (int i = 0; i 0) {
// 先加上油
cur += gas[pos];
// 油量不够到下个加油站
if (cost[pos] > cur) break;
// 消耗汽油到下个加油站
cur -= cost[pos];
pos = (pos + 1) % gasSize;
count--;
}
if (count == 0) return i;
}
return -1;
}
// O(n^2)超时
int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
int arr[gasSize];
// 记录余量
for (int i = 0; i 0) {
// 先加上油
prefix += arr[pos];
// 油量不够到下个加油站
if (prefix
// O(n^2)超时
int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
// 从每个位置开始尝试
for (int i = 0; i 0) {
// 余量
prefix += gas[pos] - cost[pos];
// 油量不够到下个加油站
if (prefix
// O(n)
int canCompleteCircuit(int *gas, int gasSize, int *cost, int costSize) {
// 余量前缀和
int prefixSum = 0;
// 当前窗口大小
int len = 0;
// 从每个位置开始尝试
for (int left = 0, right; left = 0) {
if (len == gasSize) return left;
// 计算窗口右边界
right = (left + len) % gasSize;
// 窗口扩大,right移入窗口
len++;
prefixSum += gas[right] - cost[right];
}
// 窗口缩小,left移除窗口
len--;
prefixSum -= gas[left] - cost[left];
}
return -1;
}
1234. 替换子串得到平衡字符串
int min(int a, int b) {
return a > b ? b : a;
}
bool ok(int *counts, int len, int require) {
for (int i = 0; i require) return false;
// 用长度len的窗口补齐每个字符缺失的个数require - counts[i]
len -= require - counts[i];
}
// 窗口刚好用完
return len == 0;
}
int balancedString(char *s) {
int lenS = strlen(s);
// 最多调整整个数组
int res = lenS;
// 每种字符必须出现的次数
int require = lenS / 4;
// Q W E R转换成0123
int arr[lenS];
// 统计窗口外字符出现次数
int counts[4] = {0};
for (int i = 0; i
992. K 个不同整数的子数组
int counts[20001];
// 返回nums的所有子数组中,数字种类不超过k的子数组个数
int lower(int *nums, int numsSize, int k) {
memset(counts, 0, sizeof(int) * 20001);
int res = 0;
for (int l = 0, r = 0, types = 0; r k) {
// 词频减一
counts[nums[l]]--;
// 刚好把这个字符全部移除
if (counts[nums[l]] == 0) types--;
l++;
}
res += r - l + 1;
}
return res;
}
int subarraysWithKDistinct(int *nums, int numsSize, int k) {
return lower(nums, numsSize, k) - lower(nums, numsSize, k - 1);
}
395. 至少有 K 个重复字符的最长子串
int max(int a, int b) {
return a > b ? a : b;
}
int longestSubstring(char *s, int k) {
int len = strlen(s);
int counts[256];
int res = 0;
// 至少有require个重复字符的最长子串
for (int require = 1; require require) {
if (counts[s[l]] == 1) types--;
if (counts[s[l]] == k) satisfy--;
// 窗口左侧移出字符
counts[s[l]]--;
l++;
}
// 子串以r位置结尾,且种类总数不超过require的最大长度
if (satisfy == require) res = max(res, r - l + 1);
}
}
return res;
}
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net