一些算法面试题目
前言也是从网上找一些面试的算法题目，这里分享一下自己的解题思路。原题目链接：http://www.ahathinking.com/archives/177.html
题目1、定长线段最多覆盖点的个数（ps：百度的面试题目，擦，我笔试答的感觉不错，竟然没有面试通知，蛋疼）。例如 1, 3, 7, 8, 9, 11这些坐标升序放在数组中，现在给一根绳子，长度为4，问绳子最多能覆盖的点数是多少？
思路：
（1）暴力破解法，求解每个点的最大覆盖数，然后求最大值，时间复杂度为O(n^2)
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 26#define N 1000typedef struct word {char str[100];} word;typedef struct trie {struct trie *next[MAX];word words[N];int count;} trie;int cmp(const void *p, const void *q){const char *a = p;const char *b = q;return *a - *b;}void initTrie(trie **root){int i;*root = (trie *)malloc(sizeof(trie));(*root)->count = 0;for (i = 0; i < MAX; i ++) {(*root)->next[i] = NULL;}}void insertTrie(trie *root, char *str, char *mirror){trie *tmp, *p = root;while (*str != '\0') {if (p->next[*str - 'a'] == NULL) {tmp = (trie *)malloc(sizeof(trie));if (*(str + 1) != '\0') {tmp->count = 0;} else {strcpy(tmp->words[tmp->count ++].str, mirror);}p->next[*str - 'a'] = tmp;p = tmp;} else {p = p->next[*str - 'a'];if (*(str + 1) == '\0') {strcpy(p->words[p->count ++].str, mirror);}}str ++;}}void searchTrie(trie *root, char *str, char *mirror){trie *p = root;int i, flag = 1;while (*str != '\0') {if (p->next[*str - 'a'] == NULL) {flag = 0;break;} else {p = p->next[*str - 'a'];}str ++;}if (flag) {for (i = 0; i < p->count; i ++) {if (strcmp(p->words[i].str, mirror) != 0) {puts(p->words[i].str);}}} else {printf("无兄弟单词\n");}}int main(void){int n;char *str, *mirror;trie *root;str = (char *)malloc(N);mirror = (char *)malloc(N);scanf("%d", &n);initTrie(&root);while (n --) {// 构造词典memset(mirror, '\0', N);scanf("%s", str);strcpy(mirror, str);qsort(str, strlen(str), sizeof(str[0]), cmp);insertTrie(root, str, mirror);}while (scanf("%s", str) != EOF) {strcpy(mirror, str);qsort(str, strlen(str), sizeof(str[0]), cmp);searchTrie(root, str, mirror);}return 0;}