c语言闯算法--常用技巧

双指针

类别：

同向快慢指针
异常情况，慢指针才动

双向指针
视情况，左右指针动

最长无重复子串

int max(int a, int b){if(a < b){return b;}else{return a;}
}
int lengthOfLongestSubstring(char* s) {int count[300];for(int i = 0; i < 300; i++){count[i] = 0;}int l = 0;// printf("%d", strlen(s));int res = 0;int len = strlen(s);for(int i = 0; i < len; i++){count[s[i] - ' ']++;while(count[s[i] - ' '] > 1){count[s[l] - ' ']--;l++;// printf("%d---\n", l);}// printf("%d\n", i - l + 1);res = max(res, i - l + 1);}return res;
}

字符串字母异位词

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* findAnagrams(char* s, char* p, int* returnSize) {//有返回，先定义int lenS = strlen(s);int* res = malloc(lenS * sizeof(int));*returnSize = 0;//字母异位词就是：找词频一样的int cntP[26];int cntS[26];for(int i = 0; i < 26; i++){cntP[i] = 0;cntS[i] = 0;}//先统计p中的词频int lenP = strlen(p);for(int i = 0; i < lenP; i++){cntP[p[i] - 'a']++;}for(int i = 0; i < 26; i++){printf("%d ",cntP[i]);}//滑动窗口统计s中的int l = 0;for(int r = 0; r < lenS; r++){cntS[s[r] - 'a']++;if(r - l + 1 == lenP){//现在窗口大小一致bool flag = true;for(int i = 0; i < 26; i++){if(cntP[i] != cntS[i]) flag = false;}if(flag){res[(*returnSize)++] = l;}}// cntS[s[l] - 'a']--;//只有窗口大小超过才需要减掉左边if(r - l + 1 >= lenP){cntS[s[l] - 'a']--;l++;}}return res;}

最长不重复子序列

#include<stdio.h>
#include<stdlib.h>#define N 100010int cnt[N];//模拟哈希表，记录词频int max(int a, int b){if(a > b){return a;}else{return b;}
}int main(){int n; scanf("%d", &n);int* tmp = malloc((n + 1) * sizeof(int));int x;for(int i = 0; i < n; i++){scanf("%d", &x);tmp[i] = x;}int l = 0; int r = 0;int res = 0;for(; r < n; r++){cnt[tmp[r] - 1]++;while(l <= r && cnt[tmp[r] - 1] > 1){cnt[tmp[l] - 1]--;l++;}res = max(res, r - l + 1);}printf("%d", res);return 0;
}

数组元素的目标和

#include<stdio.h>
#include<stdlib.h>int main(){int n, m, x;scanf("%d %d %d", &n, &m, &x);int* A = malloc((n + 1) * sizeof(int));int* B = malloc((m + 1) * sizeof(int));int tmp;for(int i = 0; i < n; i++){scanf("%d", &tmp);A[i] = tmp;}for(int i = 0; i < m; i++){scanf("%d", &tmp);B[i] = tmp;}int l = 0; int r = m - 1;int sum;while(l < n && r >= 0){sum = A[l] + B[r];if(sum > x){r--;}else if(sum < x){l++;}else{printf("%d %d", l , r);break;}}return 0;
}

判断子序列

#include<stdio.h>
#include<stdlib.h>int main(){int n, m;scanf("%d %d", &n, &m);int* a = malloc((n + 1) * sizeof(int));int* b = malloc((m + 1) * sizeof(int));int x;for(int i = 0; i < n; i++){scanf("%d", &x);a[i] = x;}for(int i = 0; i < m; i++){scanf("%d", &x);b[i] = x;}int cnt = 0;//b数组更长for(int i = 0; i < m; i++){if(cnt < n && b[i] == a[cnt]){cnt++;}}if(cnt == n){printf("Yes");}else{printf("No");}return 0;
}

并查集

合并集合

#include<stdio.h>
#include<stdlib.h>#define N 100010int f[N];int find(int a){if(a != f[a]) f[a] = find(f[a]);return f[a];
}int main(){int n, m;scanf("%d %d", &n, &m);//并查集初始化for(int i = 1; i <= n; i++){f[i] = i;}for(int i = 0; i < m; i++){char op[2];scanf("%s", op);if(op[0] == 'M'){int a, b;scanf("%d %d", &a, &b);int f1 = find(a);int f2 = find(b);if(f1 != f2){f[f1] = f2;}}else{int a, b;scanf("%d %d", &a, &b);if(find(a) != find(b)){printf("No\n");}else{printf("Yes\n");}}}return 0;
}

连通块的数量

#include<stdio.h>#define N 100010int f[N];
int cnt[N];int find(int a){if(a != f[a]) f[a] = find(f[a]);return f[a];
}int main(){int n, m;scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++){f[i] = i;cnt[i] = 1;}for(int i = 0; i < m; i++){char op[3];scanf("%s", op);if(op[0] == 'C'){int a, b;scanf("%d %d", &a, &b);int f1 = find(a);int f2 = find(b);if(f1 != f2){cnt[f2] += cnt[f1];f[f1] = f2;}}else if(op[0] == 'Q' && op[1] == '1'){int a, b;scanf("%d %d", &a, &b);int f1 = find(a);int f2 = find(b);if(f1 != f2){printf("No\n");}else{printf("Yes\n");}}else{int a;scanf("%d", &a);printf("%d\n", cnt[find(a)]);}}return 0;
}

Tire树

Trie字符串统计

#include<stdio.h>#define N 200100//模拟树
int t[N][26];
int idx;//记录单词数
int cnt[N];//记录每次的字符串
char str[N];void insert(){int p = 0; //表示根节点for(int i = 0; str[i] != '\0'; i++){//遍历整个字符串int x = str[i] - 'a';if(!t[p][x]) t[p][x] = ++idx;//节点不存在，创建p = t[p][x];//让指针往下走，遍历完字符串}//到达最终的节点cnt[p]++;//表示以此节点为结束的字符串个数
}void query(){int p = 0;for(int i = 0; str[i] != '\0'; i++){int x = str[i] - 'a';// if(!t[p][x]) break;//不存在if(!t[p][x]) {//不能break,否则还是会输出打印printf("0\n");return;}p = t[p][x];}//最终找到了printf("%d\n", cnt[p]);
}int main(){int n;scanf("%d", &n);char op[2];for(int i = 0; i < n; i++){scanf("%s", op);scanf("%s", str);if(op[0] == 'I'){insert();}else{query();}}return 0;
}

异或最大值

//trie树不仅可以存字符串，还可以存二进制数#include<stdio.h>#define  N 100010int a[N];//模拟树
int t[N * 32][2];
int idx;int max(int a, int b){if(a > b){return a;}else{return b;}
}void insert(int a){int p = 0; for(int i = 31; i >= 0; i--){//存二进制需要从高位开始int x = a >> i & 1;if(!t[p][x]) t[p][x] = ++idx;p = t[p][x];}
}int query(int a){int p = 0; int res = 0;for(int i = 31; i >= 0; i--){int x = a >> i & 1;if(t[p][!x]){//要求异或值最大，所以每一次都需要找相反值p = t[p][!x];res += 1 << i;//有相反值，异或得1}else{p = t[p][x];//不存在相反之，异或得0}}return res;
}int main(){int n; scanf("%d", &n);int x;for(int i = 0; i < n; i++){scanf("%d", &x);a[i] = x;insert(a[i]);}int res = 0; //遍历每一个数的异或值，取最大for(int i = 0; i < n; i++){res = max(res, query(a[i]));}printf("%d", res);return 0;
}

实现trie

#define N 100010typedef struct {int t[N][26];bool flag[N];int idx;
} Trie;Trie* trieCreate() {Trie* t = malloc(sizeof(Trie));memset(t, 0, sizeof(Trie));  // 初始化所有值为 0return t;
}void trieInsert(Trie* obj, char* word) {int p = 0;for(int i = 0; word[i] != '\0'; i++){int x = word[i] - 'a';if(!(obj->t[p][x])) obj->t[p][x] = ++(obj->idx);p = obj->t[p][x];}obj->flag[p] = true;
}bool trieSearch(Trie* obj, char* word) {int p = 0;for(int i = 0; word[i] != '\0'; i++){int x = word[i] - 'a';if(!obj->t[p][x]) return false;p = obj->t[p][x];}return obj->flag[p];
}bool trieStartsWith(Trie* obj, char* prefix) {int p = 0;for(int i = 0; prefix[i] != '\0'; i++){int x = prefix[i] - 'a';if(!obj->t[p][x]) return false;p = obj->t[p][x];}return true;
}void trieFree(Trie* obj) {free(obj);
}/*** Your Trie struct will be instantiated and called as such:* Trie* obj = trieCreate();* trieInsert(obj, word);* bool param_2 = trieSearch(obj, word);* bool param_3 = trieStartsWith(obj, prefix);* trieFree(obj);
*/