1 模拟实现atoi
我们知道：atoi是将字符串中的数字转化成整形数字，但是有以下的情况需要特殊考虑：
1空指针
2空字符串
3遇到了非数字字符
4超出了范围
所以我们不妨用一种枚举类型state来判断当前的输入是否合法，符号的正负可以定义一个flag.
enum state { VALID, UNVALID, }; enum state s = VALID; int MyAtoi(const char* ps) { if (NULL == ps) { s = UNVALID; return 0; } int flag = 1; if (*ps == '+') { ps++; } else if (*ps == '-') { flag = -1; ps++; } while (isspace(*ps)) { ps++; } long long n = 0; while (isdigit(*ps)) { n = n * 10 + flag*(*ps - '0'); if (n > INT_MAX || n < INT_MIN) { s = UNVALID; return 0; } ps++; } if (*ps == '\0') return (int)n; else { s = UNVALID; return 0; } } int main() { const char* pc = "- a123456"; int ret = MyAtoi(pc); if (s == VALID) { printf("%d\n", ret); } else printf("格式错误，无法打印\n"); return 0; }
2 寻找单身狗
题目要求：一个整形数组中只有两个元素是单身的（只出现了一次），其他元素均出现了两次，请找出这两个单身元素。
我们知道：如果只有一个单身元素的话，只需要将数组中每一个元素互相^就能解决问题。那么有两个单身元素又该怎么办呢？
我i们不妨假设一个整形数组{1,1,2,2,3,3,4,4,5,6}，如果将数组中每个元素^就相当于5^6，得到的结果是3，解决该问题的关键在于如何将5和6分到不同的小组？
我们发现：将5^6的结果(3)二进制的每一位都&1(从右向左)，如果&1的结果==1，就记住第一次==1的位置，假设该位置记做pos，然后让数组中每一个元素都向右移动pos位，得到的结果如果==1，就分到一个数组，不为1就分到另外一个数组，这样就将5和6分到了不同的小组了。
//求一个数组中哪两个是单身元素（其余重复元素只有两个） void GudgSgle(int arr[], int len,int*p1,int*p2) { int ret = 0; int i = 0; int pos = 0; for (i = 0; i < len; i++) { ret ^= arr[i]; } for (i = 0; i < 32; i++) { if ((ret >> i & 1) == 1) { pos = i; break; } } for (i = 0; i <len; i++) { if ((arr[i] >> pos & 1) == 1) *p1 ^= arr[i]; else *p2 ^= arr[i]; } } int main() { int arr[12] = { 1,2,3,4,5,6,1,2,3,4 }; int len = sizeof(arr) / sizeof(int); int single1 = 0; int single2 = 0; GudgSgle(arr, len,&single1,&single2); printf("%d %d\n", single1, single2); return 0; }
3 用宏将一个二进制位的奇数位与偶数位交换
首先来看：如何将一个二进制位奇数位与偶数位交换？如果能拿到所有奇数位以及所有偶数位，再将所有奇数位向左移动一位，所有偶数位向右移动一位，然后再相加就能解决问题。关键在于如何拿到所有的奇数位和所有的偶数位：给定一个二进制数1111 1111 1111 1111 1111 1111 1111 1111，如果要得到奇数位就将该二进制数&0101 0101 0101 0101 0101 0101 0101 0101（0x55555555)
如果要得到偶数位就将该二进制数&1010 1010 1010 1010 1010 1010 1010 1010 (0xaaaaaaaa)
//写一个宏：将一个整数的二进制位奇数与偶数交换 #define SWAP(num) (((num&0x55555555)<<1)+((num&0xaaaaaaaa)>>1)) int main() { int num = 10; printf("%d\n", SWAP(num)); return 0; }
得到的结果是5 符合要求。
4 用宏模拟实现offsetof
offsetof是计算结构体中某变量相对于首地址的偏移量。为了计算的简便，我们不妨将0强转成一种结构体指针，再通过该指针引用结构体中的变量，取出它的地址，该地址再数值上就等于所求结构体变量的偏移量。
//写一个宏，自己实现offsetof struct state { char a; char b; short c; int d; }; #define OFFSETOF(stuname,memname) (int)&(((struct state*)0)->memname) int main() { printf("%d\n", OFFSETOF(struct state, a)); printf("%d\n", OFFSETOF(struct state, b)); printf("%d\n", OFFSETOF(struct state, c)); printf("%d\n", OFFSETOF(struct state, d)); return 0; }
得到的结果：
这里值得注意的是：将0强转成一种结构体指针并不是真正使用了0地址处的空间，只是模拟实现了计算偏移量而已，这里也可以将其他数字强转，只不过后面要再减去该数字。
下面这种写法也是正确的：
4 序列中整数去重
给定一个整形数组，去除其中重复出现的数字：例如{1,2,2,2,5,5,3,9},去重后变为{1,2,5,3,9},
解题的思路是：遍历数组中每一个元素，将该元素与后面其他所有数字比较，如果相等，就将该元素被后面一个元素覆盖（该元素其后的元素均向前移动一位）
#include<stdio.h> int main() { int n=0; scanf("%d",&n); int i=0; int arr[1000]={0}; for(i=0;i<n;i++) { scanf("%d",&arr[i]); } int j=0; int k=0; for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { if(arr[j]==arr[i]) { for(k=j+1;k<n;k++) arr[k-1]=arr[k]; n--; j--; } } } for(i=0;i<n;i++) { printf("%d ",arr[i]); } return 0; }
其中容易出错的是当覆盖了一个元素后j--,就拿{1,2,2,2,5,5,3,9}来说，当拿第二个元素与第3个元素相比时，就会把第二个元素覆盖，此时数组变为{1,2,2,5,5,3,9},j如果不--的话会直接跳到现在的第3位元素，会让第3位元素与后面的进行比较，也就忽略了覆盖元素，就会出错。
5 有序列合并
题目要求：将两个按升序排列的整形数组合并成一个按升序排列的整形数组。
解题思路：可以创建一个整形数组，一个一个比较另外两个数组，将其中的较小值放在创建的数组中。
#include<stdio.h> int main() { int m=0; int n=0; int arr1[1000]={0}; int arr2[1000]={0}; int arr3[3000]={0}; scanf("%d%d",&m,&n); int i=0; for(i=0;i<m;i++) { scanf("%d",&arr1[i]); } for(i=0;i<n;i++) { scanf("%d",&arr2[i]); } i=0; int j=0; int k=0; while(i<m && j<n) { if(arr1[i]>arr2[j]) { arr3[k++]=arr2[j]; j++; } else { arr3[k++]=arr1[i]; i++; } } if(i==m) for(;j<n;j++) arr3[k++]=arr2[j]; else for(;i<m;i++) arr3[k++]=arr1[i]; for(i=0;i<k;i++) printf("%d ",arr3[i]); return 0; }
如果其中一个数组遍历完了但是另一个数组还没有遍历完，就把没有遍历完的元素一 一赋给创建的数组。
