1.有一个整数数组，请求出两两之差绝对值最小的值,
1)若采用暴力则n^2
2)qsort 则nlgn
3)鸽笼原理 分成桶 n
2.写一个函数，检查字符是否是整数，如果是，返回其整数值。
（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）
atoi
3.给出一个函数来输出一个字符串的所有排列。
采用排列数的方法
#include <stdio.h> void swap(char*str,int i,int k) { char temp=str[i]; str[i]=str[k]; str[k]=temp; } void PaiLie(char*str,int k,int r) { if(k==r){ printf("%s\n",str); return ; } for(int i=k;i<=r;i++) { swap(str,i,k); PaiLie(str,k+1,r); swap(str,i,k); } } int main() { char s[]="ABC"; PaiLie(s,0,2); return 0; }
4.（a）请编写实现malloc()内存分配函数功能一样的代码。
（b）给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠
5.怎样编写一个程序，把一个有序整数数组放到二叉树中？
二叉树排序的方式
6.怎样从顶部开始逐层打印二叉树结点数据？请编程。
层序遍历
7.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？
利用栈的方式好不好？
8.请编写能直接实现int atoi(const char * pstr)函数功能的代码。
这个难度不大吧 主要翻译然后权值依次乘上10+当前这位数
#include <stdio.h> #include <string.h> int __atoi(const char * pstr) { int plen=strlen(pstr); int sum=0; for(int i=0;i<plen;i++) { if(pstr[i]<='9'&&pstr[i]>='0') { sum*=10; sum+=pstr[i]-'0'; } else return -1; } return sum; } int main() { char ss[]="234567"; int ans=__atoi(ss); printf("%d\n",ans); return 0; }
9.编程实现两个正整数的除法
编程实现两个正整数的除法，当然不能用除法操作符。
// return x/y.
int div(const int x, const int y)
{
….
}
//1.第一种思路 减法的思路
//2. 移位操作
10.在排序数组中，找出给定数字的出现次数
比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。
1）.基数排序 O（n）感觉已经落后了
2）.二分查找 找到最低位置和最高位置 lg（n）时间
#include<stdio.h> #include<stdlib.h> int arr[] = {0,1,1,2,2,2,2,4,4,4}; //测试数组 int size = sizeof(arr) / sizeof(*arr); //数组元素个数 int getUpper(int arr[], int key){//获取某个元素最后出现位置 int low = 0, high = size - 1; while(low < high){ int mid = (low + high + 1) / 2; if(arr[mid] <= key) low = mid; else high = mid - 1; } return low; } int getLower(int arr[], int key){//获取某个元素第一次出现位置 int low = 0, high = size - 1; while(low < high){ int mid = (low + high) / 2; if(arr[mid] >= key) high = mid; else low = mid + 1; } return low; } int main() { for(int i = 0; i < size; i ++) printf("%d 出现 %d 次\n",arr[i],getUpper(arr,arr[i]) - getLower(arr,arr[i]) + 1); getchar(); }
11.平面上N个点，每两个点都确定一条直线，
求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑）。时间效率越高越好。