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;
}
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;
}
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;
}
转自:https://www.jianshu.com/p/746495327da6
收起阅读 »