408代码题汇总

#include<stdio.h> //数组算法题 //10年 void fun1(int r[], int l, int r) { int a = l, j = r; while(a < b) { int temp = r[a]; r[a] = r[b]； r[b] = temp; a++;b--; } } void fun2(int r[], int n, int p) { if(p > 0 && p < n) { fun1(r,0,n-1); fun1(r,0,n-p-1); fun1(r,n-p,n-1); } } //11年 int fun(int A[],int B[],int n){ int i = j = count = 0; while(1){ count++; if(A[i] > B[j]) j++; else i++; if(count == (n - 1) / 2) break; } if(A[i] > B[j]) return B[j]; else return A[i]; } //13年 找主元素 int fun(int A[], int n){ int i, count = 1, temp = A[0]; for(i = 1; i < n; i ++ ) { if(count == 0) temp = A[i]; else { if(A[i] == temp) count ++; else count --; } } count = 0; for(i = 0; i <= n - 1; i ++ ) if(A[i] == temp)count ++; if(count > n / 2)return temp; else return -1; } //16年 void quickSort(int arr[],int l,int r)//left和right的首字母 { if(l>=r) return; int base,temp;int i=l,j=r; base = arr[l]; //取最左边的数为基准数 while(i<j){ while(arr[j]>=base&&i<j)j--;//顺序很重要 while(arr[i]<=base&&i<j) i++; if(i < j) {temp = arr[i];arr[i] = arr[j];arr[j] = temp;} }//基准数归位 arr[l]=arr[i];arr[i]=base; quickSort(arr,l,i-1);//递归左边 quickSort(arr,i+1,r);//递归右边 } int fun(int A[], int n){ quickSort(A, 0, n - 1); int i, s1 = s2 = 0, t = n / 2; for(i = 0; i < n; i ++ ) { if(i < t) s1 += A[i]; else s2 += A[i]; } return s2 - s1; } //18年 int fun(int A[], int n){ int i, *B; B = (int *)malloc(sizeof(int)*(n+1)); //申请辅助空间； memset(B,0,sizeof(int)*(n+1)); //初始化数组 for(i = 0; i < n; i ++ ){ if(A[i] > 0 && A[i] <= n) B[A[i]] = 1; } for(i = 1; i <= n; i ++ ) if(B[i] == 0) break; return i; } //20年---三元组 #define INT_MAX 0x7fffffff int abs(int a){ if(a < 0)return -a; else return a; } int fun(int A[], int a, int B[], int b, int C[], int c) { int i = j = k = 0, D, Dmin = INT_MAX; while(i < a && j < b && k < c && Dmin > 0) { D = abs(A[i] - B[j]) + abs(A[i] - C[k]) + abs(B[j] - C[k]); if(D < Dmin)Dmin = D; if(A[i] <= B[j] && A[i] <= C[k]) i ++; else if(B[j] <= A[i] && B[j] <= C[k]) j ++; else k++; } return Dmin; } //25年 void fun(int A[], int res[],int n){ int i, max, min; max = min = A[n - 1]; for(i = n - 1; i >= 0; i -- ) { if(A[i] > max) max = A[i]; else if(A[i] < min) min = A[i]; if(A[i] > 0) res[i] = A[i] * max; else res[i] = A[i] * min; } } //链表题 //09---倒数k个 typedef struct Node{ int data; struct Node *link; }Node; int fun(Node *head, int k){ Node *temp = head -> link; int length = 0, i; while(temp != Null) { //求表长。 length ++; temp = temp -> link; } if(length < k) return 0; Node *ans = head -> link; for(i = 0; i <= length - k; i ++){ ans = ans -> link; } printf("%d", ans -> data); return 1; } //12年---找公共后缀 typedef struct Node{ int data; struct Node *next; }Node; int len(LNode *head) { int length = 0; while (head -> next != NULL) { length ++ ; head = head -> next; } return length; } Node* fun(Node *str1, Node *str2){ //返回类型为节点。 int m,n; Node *p, *q; m = len(str1); n = len(str2); for(p = str1; m > n; m--) p = p -> next; for(q = str2; m < n; n--) q = q -> next; while(p -> next != NULL && q -> != NULL) { p = p -> next; q = q -> next; } return p -> next; } //15年---删除绝对值相同的点 typedef struct Node{ int data; struct Node *link; }Node; void fun(Node *head, int n){ int *q, m; q = (int *)malloc(sizeof(int)*(n+1)); memset(q,0,sizeof(int)*(n+1)); Node *p = head, *r; while(p -> link != NULL){ int temp = abs(p -> link -> data); if(q[temp] == 0) { q[temp] = 1; p = p -> link; } else { r = p -> link; p -> link = r -> link; free(r); } } free(q); } //19年---链表逆置 + 快慢指针 typedef struct Node{ int data; struct Node *next; }Node; void fun(Node *head){ Node *l, *r, *temp; l = r = h; while(r -> next != NULL) { l = l -> next; r = r -> next; if(r -> next != NULL) r = r -> next; } r = l -> next; //r为后半段的首节点。 l -> next = NULL; while(r -> next != NULL){ //链表后半段逆置 temp = r -> next; r -> next = l -> next; l -> next = r; r = temp; }//最后r指针指向尾巴节点 Node *first = head -> next; while(r != NULL){ Node *temp1 = first -> next; Node *temp2 = r -> next; first -> next = r; r -> next = temp1; first -> next = temp1; r -> next = temp2; } } //树 //14年---求WPL typedef struct node{ int weight; struct *left, *right; }Tree; int func(Tree *tree, int h){ if(tree -> left == NULL && tree -> right == NULL) return (tree -> weight * h); else return (func(tree -> left, h + 1) + func(tree -> right, h + 1)); } int wpl(Tree *tree){ return func(tree, 0); } //17年中缀表达式 typedef struct node{ char data[10]; struct node *left, *right; }Tree; void func(Tree *root, int h){ if(root == NULL) return; if(root -> left == NULL && root -> right == NULL){ printf("%s", root -> data); return; } if(h > 1) printf("("); func(root -> left, h + 1); printf("%s", root -> data); func(root -> right, h + 1); if(h > 1) printf(")"); } //22年---二叉搜索树的判定---太难了。 //图 //21年---EL路径 int func(MGraph G){ int i, j, degree, count; for(i = 0; i < G.numVertices; i ++ ){ degree = 0; for(j = 0; j < G.numVertices; j ++ ){ if(G.Edge[i][j] == 1) degree ++; } if(degree % 2 == 1) count ++; } if(count == 0 || count == 2) return 1; else return 0; } //23年 int func(MGraph G){ int i, j, in, out, count; for(i = 0; i < G.numVertices; i ++){ in = out = 0; for(j = 0; j < G.numVertices; j ++){ if(G.Edge[i][j] == 1) out ++; if(G.Edge[j][i] == 1) in ++; } if(out > in) { printf("%s", G.VerticesLit[i]); count ++; } } return count; } //24年---拓扑排序---太难了。 int func(MGraph G){ int *degree, i, j, n = G.numVertices; degree = (int*)malloc(sizeof(int)*n); for(i = 0; i < n; i ++) for(j = 0; j < n; j ++) degree[i] += G.Edge[i][j]; }