1、 实现二分查找算法
int binarySearchWithoutRecursion(int array[], int low, int high, int target) {while (low <= high) { int mid = low + (high - low) / 2; if (array[mid] > target) { high = mid - 1; } else if (array[mid] < target) { low = mid + 1; } else { //找到目标 return mid; } } return -1;}递归实现
int binarySearch(const int arr[], int low, int high, int target){ int mid = low + (high - low) / 2; if(low > high) { return -1; } else{ if(arr[mid] == target) { return mid; } else if(arr[mid] > target) { return binarySearch(arr, low, mid-1, target); } else { return binarySearch(arr, mid+1, high, target); } }}2、 对以下一组数据进行降序排序（冒泡排序）。“24，17，85，13，9，54，76，45，5，63”
int main(int argc, char *argv[]) { int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63}; int num = sizeof(array)/sizeof(int); for(int i = 0; i < num - 1; i++) { int exchanged = 0; for(int j = 0; j < num - 1 - i; j++) { if(array[j] < array[j+1]) { array[j] = array[j]^array[j+1]; array[j+1] = array[j+1]^array[j]; array[j] = array[j]^array[j+1]; exchanged = 1; } } if (exchanged == 0) { break; } } for(int i = 0; i < num; i++) { printf("%d ", array[i]); }}3、 对以下一组数据进行升序排序（选择排序）。“86, 37, 56, 29, 92, 73, 15, 63, 30, 8”
void sort(int a[],int n){ int i, j, min; for(i = 0; i < n - 1; i++) { min = i; for(j = i + 1; j < n; j++) { if(a[min] > a[j]) { min = j; } } if(min != i) { a[i] = a[i] ^ a[min]; a[min] = a[min] ^ a[i]; a[i] = a[i] ^ a[min]; } }}int main(int argc, const char * argv[]) { int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8}; sort(numArr, 10); for (int i = 0; i < 10; i++) { printf("%d, ", numArr[i]); } return 0;}4、 快速排序算法
void sort(int *a, int left, int right) { if(left >= right) { return ; } int i = left; int j = right; int key = a[left]; while (i < j) { while (i < j && key >= a[j]) { j--; } if (i < j) { a[i] = a[j]; } while (i < j && key < a[i]) { i++; } if (i < j) { a[j] = a[i]; } } a[i] = key; sort(a, left, i-1); sort(a, i+1, right);}5、 归并排序
void merge(int sourceArr[], int tempArr[], int startIndex, int midIndex, int endIndex) { int i = startIndex; int j = midIndex + 1; int k = startIndex; while (i != midIndex + 1 && j != endIndex + 1) { if (sourceArr[i] >= sourceArr[j]) { tempArr[k++] = sourceArr[j++]; } else { tempArr[k++] = sourceArr[i++]; } } while (i != midIndex + 1) { tempArr[k++] = sourceArr[i++]; } while (j != endIndex + 1) { tempArr[k++] = sourceArr[j++]; } for (i = startIndex; i <= endIndex; i++) { sourceArr[i] = tempArr[i]; }}void sort(int souceArr[], int tempArr[], int startIndex, int endIndex) { int midIndex; if (startIndex < endIndex) { midIndex = (startIndex + endIndex) / 2; sort(souceArr, tempArr, startIndex, midIndex); sort(souceArr, tempArr, midIndex + 1, endIndex); merge(souceArr, tempArr, startIndex, midIndex, endIndex); }}int main(int argc, const char * argv[]) { int numArr[10] = {86, 37, 56, 29, 92, 73, 15, 63, 30, 8}; int tempArr[10]; sort(numArr, tempArr, 0, 9); for (int i = 0; i < 10; i++) { printf("%d, ", numArr[i]); } return 0; }假如你正在跳槽或者者正准备跳槽不妨动动小手，增加一下咱们的交流群1012951431来获取一份详细的大厂面试资料为你的跳槽多添一份保障。
6、 二叉树的先序遍历为FBACDEGH,中序遍历为：ABDCEFGH,请写出这个二叉树的后序遍历结果。
ADECBHGF
先序+中序遍历复原二叉树：先序遍历是：ABDEGCFH 中序遍历是：DBGEACHF
首先从先序得到第一个为A，就是二叉树的根，回到中序，可以将其分为三部分：
左子树的中序序列DBGE，根A，右子树的中序序列CHF
接着将左子树的序列回到先序可以得到B为根，这样回到左子树的中序再次将左子树分割为三部分：
左子树的左子树D，左子树的根B，左子树的右子树GE
同样地，可以得到右子树的根为C
相似地将右子树分割为根C，右子树的右子树HF，注意其左子树为空
假如只有一个就是叶子不用再进行了，刚才的GE和HF再次这样运作，即可以将二叉树复原了。
7、 实现一个字符串“how are you”的逆序输出（编程语言不限）。如给定字符串为“hello world”,输出结果应当为“world hello”，进阶：去掉首尾空格，每个单词间只保留一个空格。
void reverse(char *start, char *end) { if (start == NULL || end == NULL) { return; } //翻转字符 while (start < end) { char tmp = *start; *start = *end; *end = tmp; start++; end--; }}char *reverseStrings(char * s){ if (s == NULL) { return '\0'; } //去除多余空格 char *str = s; //去除首部空格 while(*str != '\0') { if (*str != ' ') { s = str; break; } str++; } str = s; int i,j; i = 0; j = 0; //去除中间或者尾部空格 while(*(str+i) != '\0') { if (*(str+j) == ' ') { if (*(str+j+1) == ' ') { j++; continue; } else if (*(str+j+1) == '\0' ) { //去掉尾部空格 *(str+i) = '\0'; break; } } else if (*(str+j) == '\0' ) { //去掉尾部空格 *(str+i) = '\0'; break; } if (*(str+i) != *(str+j)) { *(str+i) = *(str+j); } i++; j++; } char *start,*end; start = s; end = s; while(*end != '\0') { end++; } end--; reverse(start,end); //翻转单词 start = s; end = s; while (*start != '\0') { if (*start == ' ') { start++; end++; } else if (*end == ' ' || *end == '\0'){ end--; reverse(start,end); start = ++end; } else { end++; } } return s;}int main(int argc, const char * argv[]) { char *str = reverseStrings("have a brilliant future"); while (*str != '\0') { printf("%c", *str++); } return 0;}8、字符串匹，输出子串第一次出现的下标，具体要求如下：
给定主串“ababcabc”,模式串“abc”，输出结果为：2
给定主串 “aaaa”,模式串“bb”，输出结果为：-1
当模式串为空串的时候，输出结果应为：0
请实现findStringIndex函数。
int findStringIndex(char * inputs, char * matchs){ if (inputs == NULL || matchs == NULL) { return -1; } if (*matchs == '\0') { return 0; } int i = 0,j = 0; while (*(inputs + i) != '\0' && *(matchs + j) != '\0') { if (*(inputs + i) == *(matchs + j)) { i++; j++; } else { i = i-j+1; j = 0; } } //模式串到串尾说明匹配成功，返回下标 if (*(matchs + j) == '\0') { return i-j; } return -1;}int main(int argc, const char * argv[]) { printf("index = %d", findStringIndex("ababcabc", "abc")); return 0;}9、字符串匹配进阶，KMP算法：
void generateNextArr(char *s,int *next) { //初始化 int k = -1,j = 0; //next[0]初始化成-1 *next = -1; while (j < strlen(s) - 1) { if (k == -1 || *(s + j) == *(s + k)) { j++; k++; //s[j]==s[next[k]]必然会失配 if (*(s + j) != *(s+k)) { *(next + j) = k; } else { *(next + j) = *(next + k); } } else { k = *(next + k); } }}int kmpMatch(char *inputs, char *matchs) { if (inputs == NULL || matchs == NULL) { return -1; } //模式串为空串时返回0 if (*matchs == '\0') { return 0; } int inputLen = strlen(inputs); int len = strlen(matchs); int *next = (int *)malloc(len*sizeof(int)); //生成next数组：失配时模式串下标跳转的位置 generateNextArr(matchs, next); int i = 0,j = 0; while (i < inputLen && j < len) { if (j == -1 || *(inputs + i) == *(matchs + j)) { i++; j++; } else { j = *(next + j); } } if (*(matchs + j) == '\0') { return i-j; } free(next); return -1;}int main(int argc, const char * argv[]) { printf("index = %d", kmpMatch("aabcbbabcb", "abc")); return 0;}10、如何实现一个数组每个元素依次向右移动k位，后面的元素依次往前面补。比方: [1, 2, 3, 4, 5] 移动两位变成[4, 5, 1, 2, 3]。
思路：三次反转
后K位反转：12354
前部分反转：32154
整体一律反转：45123
int * reverse1(int *arr, int start, int end) { while (start < end) { arr[start] = arr[start] ^ arr[end]; arr[end] = arr[end] ^ arr[start]; arr[start] = arr[start] ^ arr[end]; start++; end--; } return arr;}int * moveK(int *arr, int numSize, int k) { reverse1(arr, numSize - k, numSize-1); reverse1(arr, 0, numSize-k-1); reverse1(arr, 0, numSize-1); return arr;}int main(int argc, const char * argv[]) { int arr[5] = {1,2,3,4,5}; int numSize = sizeof(arr) / sizeof(int); moveK(arr, numSize, 2); for (int i = 0; i < numSize; i++) { printf("%d ",arr[i]); } return 0;}11、 给定一个字符串，输出本字符串中只出现一次并且最靠前的那个字符的位置？如“abaccddeeef”,字符是b,输出应该是2。
char findChar(char *s){ if (s == NULL) { return ' '; } int hashTable[256]; memset(hashTable, 0, sizeof(hashTable)); char *p = s; while(*p != '\0') { hashTable[*p]++; p++; } p = s; while(*p != '\0') { if (hashTable[*p] == 1) { return *p; } p++; } return ' ';}int main(int argc, const char * argv[]) { char *inputStr = "abaccddeeef"; char ch = findChar(inputStr); printf("%c \n", ch); return 0;}假如你正在跳槽或者者正准备跳槽不妨动动小手，增加一下咱们的交流群1012951431来获取一份详细的大厂面试资料为你的跳槽多添一份保障。
12、 如何实现链表翻转（链表逆序）？
思路：每次把第二个元素提到最前面来。
#include <stdio.h>#include <stdlib.h>typedef struct NODE { struct NODE *next; int num;}node;node *createLinkList(int length) { if (length <= 0) { return NULL; } node *head,*p,*q; int number = 1; head = (node *)malloc(sizeof(node)); head->num = 1; head->next = head; p = q = head; while (++number <= length) { p = (node *)malloc(sizeof(node)); p->num = number; p->next = NULL; q->next = p; q = p; } return head;}void printLinkList(node *head) { if (head == NULL) { return; } node *p = head; while (p) { printf("%d ", p->num); p = p -> next; } printf("\n");}node *reverseFunc1(node *head) { if (head == NULL) { return head; } node *p,*q; p = head; q = NULL; while (p) { node *pNext = p -> next; p -> next = q; q = p; p = pNext; } return q;}int main(int argc, const char * argv[]) { node *head = createLinkList(7); if (head) { printLinkList(head); node *reHead = reverseFunc1(head); printLinkList(reHead); free(reHead); } free(head); return 0;}13、删除链表中的重复元素，每个重复元素需要出现一次，如给定链表 1->2->2->3->4->5->5，输出结果应当为 1->2->3->4->5。请实现下面的deleteRepeatElements函数：
typedef struct NODE { struct NODE *next; int num;} node;node *deleteRepeatElements(node *head) { if (head == NULL) { return head; } struct ListNode* pNode = head; while (pNode && pNode->next) { if (pNode->val == pNode->next->val) { struct ListNode *tempNode = pNode->next; pNode->next = pNode->next->next; free(tempNode); } else { pNode=pNode->next; } } return head;}14、删除链表中重复的元素，只保留不重复的结点。如：1->1->2->3->4->4->5，输出结果：2->3->5，请实现下面的deleteRepeatElements函数。
typedef struct NODE { struct NODE *next; int num;} node;node *deleteRepeatElements(node *head) { if (head == NULL) { return head; } //头结点有可能会被删除,先创立一个头结点 node *pHead = (node *)malloc(sizeof(node)); pHead->next = head; node *current = pHead; while(current->next && current->next->next) { if (current->next->val == current->next->next->val) { node *tempNode = current->next; while(tempNode && tempNode->next && tempNode->val == tempNode->next->val) { tempNode = tempNode->next; } current->next = tempNode->next; } else { current = current->next; } } return pHead->next;}15、 打印2-100之间的素数。
判断素数思路：通过分析我们可知5以上的自然数都可以用6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5来代替,又因6x,6x+2=2(3x+1),6x+3=3(2x+1),6x+4=2*(3x+2)以上都不可能是素数，所以只要要判断6x-1,6x+1,6x+5（6x两侧的数）就可。
int main(int argc, const char * argv[]) { for (int i = 2; i < 100; i++) { int r = isPrime(i); if (r == 1) { printf("%ld ", i); } } return 0;}int isPrime(int n){ if(n == 2 || n == 3) { return 1; } if(n % 6 != 1 && n % 6 != 5) { return 0; } for(int i = 5; (i * i) <= n; i += 6) { if(n % i == 0 || n % (i + 2) == 0) { return 0; } } return 1;}16、计算100以内素数的个数
int countPrime(int n) { int i,j,count = 0; //开拓空间 int *prime = (int *)malloc(sizeof(int) * n); //初始默认所有数为素数 memset(prime, 1, sizeof(int) * n); for (i = 2; i < n; i++) { if (prime[i]) { count++; for (j = i + i; j < n; j += i) { //标记不是素数 prime[j] = 0; } } } return count;}17、 求两个整数的最大公约数。
int gcd(int a, int b) { while (a != b) { if (a > b) { a = a - b; } else { b = b - a; } } return a;}假如你正在跳槽或者者正准备跳槽不妨动动小手，增加一下咱们的交流群1012951431来获取一份详细的大厂面试资料为你的跳槽多添一份保障。
