1. 一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。找出这两个数字,编程实现。
使用位操作符:
首先把全部的数异或一遍,最后得到的是那两个只出现一次的数异或在一起的值。可知这两个数肯定不同,所以这个异或后的值32位中至少有一位是1。此时用1左移的方法找出最近第几位是1,然后可知在数组中,这一位是1的所有数全部异或在一起就是一个只出现一次的数,这一位是0的所有数异或在一起就是另一个只出现一次的数。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void find2NumsAppearOnce(int* arr, int size, int* num1, int* num2) {
int tmp = 0;
for (int i = 0; i < size; i++) {
tmp ^= arr[i];
}
int one = 1;
// 此时tmp等于num1异或num2
for (int i = 0; i < 32; i++) {
if ((tmp & one) == 1) {
break;
}
else {
one <<= 1;
}
}
int tmp1 = 0, tmp2 = 0;
for (int i = 0; i < size; i++) {
if ((arr[i] & one) == 1) {
tmp1 ^= arr[i];
}
else if ((arr[i] & one) == 0) {
tmp2 ^= arr[i];
}
}
*num1 = tmp1;
*num2 = tmp2;
}
int main() {
int arr[] = { 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7 };
int num1 = -1, num2 = -1;
find2NumsAppearOnce(arr, 12, &num1, &num2);
printf("%d %d\n", num1, num2);
system("pause");
return 0;
}
使用哈希表
把全部数据加入哈希表中,然后再依次在哈希表中查找哪个数只出现了一次
#define HTCAPACITY 5000
int hash(int key) {
int index;
index = key % HTCAPACITY;
index = (index >= 0) ? index : index + HTCAPACITY;
return index;
}
void hashInsert(int* value, int* status, int val) {
int index = hash(val);
while (status[index] != 0) {
index++;
}
value[index] = val;
status[index] = 1;
}
int isAppearOnce(int* value, int* status, int val) {
int count = 0;
int index = hash(val);
while (status[index] != 0) {
if (value[index] == val) {
count++;
}
index++;
}
return (count == 1) ? 1 : 0;
}
void find2NumsAppearOnce_hash(int* arr, int size, int* num1, int* num2) {
int value[HTCAPACITY] = { 0 };
int status[HTCAPACITY] = { 0 };
// memset(status, -1, sizeof(int) * HTCAPACITY);
int count = 0;
for (int i = 0; i < size; i++) {
hashInsert(value, status, arr[i]);
}
for (int i = 0; i < size; i++) {
if (isAppearOnce(value, status, value[i])) {
if (!count) {
*num1 = value[i];
count++;
}
else {
*num2 = value[i];
}
}
}
}
int main() {
int arr[] = { 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7 };
int num1 = -1, num2 = -1;
find2NumsAppearOnce_hash(arr, 12, &num1, &num2);
printf("%d %d\n", num1, num2);
system("pause");
return 0;
}
2. 喝汽水,1瓶汽水1元,2个空瓶可以换一瓶汽水,给20元,可以多少汽水。编程实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int drink_soda(int money) {
int bottle = money;
int total = 0;
int emptyBottle = 0;
while (1) {
// 喝完bottle瓶汽水
emptyBottle += bottle;
total += bottle;
bottle = 0;
if (emptyBottle < 2) {
break;
}
// 用emptyBottle汽水换汽水
bottle += emptyBottle / 2;
emptyBottle %= 2;
}
return total;
}
int main() {
printf("%d\n", drink_soda(20));
system("pause");
return 0;
}
3. 模拟实现strcpy
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
char* Strcpy(char* destination, const char* source) {
assert(destination != NULL && source != NULL);
int i;
for (i = 0; source[i] != '\0'; i++) {
destination[i] = source[i];
}
destination[i] = '\0';
return destination;
}
int main() {
char a[1024] = "Hello";
char b[1024] = "hello, world";
Strcpy(a, b);
printf("%s\n", a);
system("pause");
return 0;
}
4. 模拟实现strcat
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* Strcat(char* destination, const char* source) {
int destPtr = -1, srcPtr = 0;
while (destination[++destPtr] != '\0');
while (destination[destPtr++] = source[srcPtr++]);
return destination;
}
int main() {
char a[1024] = "Hello";
char b[1024] = "hello, world";
Strcat(a, b);
printf("%s\n", a);
system("pause");
return 0;
}