应聘IT公司笔试算法题目

20、快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等）
#include "stdafx.h"
#define N 10
int part(int list[], int low, int high) {  // 一趟排序，返回分割点位置
 int tmp = list[low];
 while(low<high) {
  while(low<high && list[high]>=tmp) --high;
  list[low] = list[high];
  while(low<high && list[low]<=tmp)  ++low;
  list[high] = list[low];
 }
 list[low] = tmp;
 return low;
}
void QSort(int list[], int low, int high) { // 应用递归进行快速排序
 if(low<high) {
  int mid = part(list, low, high);
  QSort(list, low, mid-1);
  QSort(list, mid+1, high);
 }
}
void show(int list[], int n) {    // 输出列表中元素
 for(int i=0; i<n; i++)
  printf("%d ", list);
 printf("\n");
}
int main(int argc, char* argv[]) {
 int list[N] = {23, 65, 26, 1, 6, 89, 3, 12, 33, 8};
 show(list, N);      // 输出排序前序列
 QSort(list, 0, N-1);     // 快速排序
 show(list, N);      // 输出排序后序列
}

21、20xx年11月23日慧通笔试题：写一函数判断某个整数是否为回文数，如12321为回文数。可以用判断入栈和出栈是否相同来实现（略微复杂些），这里是将整数逆序后形成另一整数，判断两个整数是否相等来实现的。
#include "stdafx.h"
int IsEchoNum(int num) {
 int tmp = 0;
 for(int n = num; n; n/=10)
  tmp = tmp *10 + n%10;
 return tmp==num;
}

int main(int argc, char* argv[]) {
 int num = 12321;
 printf("%d  %d\n", num, IsEchoNum(num));
}

22、删除字符串中的数字并压缩字符串（神州数码以前笔试题），如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为O(N)）
#include "stdafx.h"
void delNum(char *str) {
 int i, j=0;
// 找到串中第一个数字的位子
 for(i=j=0; str && (str<'0' || str>'9'); j=++i);
 
 // 从串中第一个数字的位置开始，逐个放入后面的非数字字符
 for(; str; i++)  
  if(str<'0' || str>'9')
   str[j++] = str;
 str[j] = '\0';
}

int main(int argc, char* argv[]) {
 char str[] = "abc123ef4g4h5";
 printf("%s\n", str);
 delNum(str);
 printf("%s\n", str);
}

23、求两个串中的第一个最长子串（神州数码以前试题）。如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。
#include "stdafx.h"
char *MaxSubString(char *str1, char *str2) {
 int i, j, k, index, max=0;
 for(i=0; str1; i++)
  for(j=0; str2[j]; j++) {
   for(k=0; str1[i+k]==str2[j+k] && (str2[i+k] || str1[i+k]); k++);
   if(k>max) {  // 出现大于当前子串长度的子串，则替换子串位置和程度
    index = j; max = k;
   }
  }
 char *strResult = (char *)calloc(sizeof(char), max+1);
 for(i=0; i<max; i++) 
  strResult = str2[index++];
 return strResult;
}

int main(int argc, char* argv[]) {

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]  下一页