前言
😽俩道比较锻炼编程思维和逻辑思维的基础题目，使用C语言实现
一. 找单身狗
1. 题目内容：
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次；找出这两个只出现一次的数字。
2. 解题思路
思路1：暴力求解，将数组中的每个数字与数组中的所有数字比较一次，并记录数组中的数字与其相等的次数，如果相等的次数为1，便是只出现一次的数字。
思路2：
找出一个只出现过一次的数字的问题处理方法就是找一个数字把里面所有的数字都异或一遍，相同的数字异或结果为0，所以把所有的数字都异或在一起得到的结果就是仅有的俩个不同的数字异或的结果。
得到的这个结果肯定不是0（要不然就全都配对了），所以里面一定至少有一个二进制位是1。
找出值为1的这一位，以这一位的值将结果分为两组，值为1的分为一组，值为0的分为一组，分组后这俩个数字在各自的组中只有一个单独的数字。
所以分别将俩组中的数字异或在一起，便可得到这俩个单独的数字
3. 代码实现
//方法一 #include<stdio.h> int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,7,9,10 }; int count = 0; int sz = sizeof(arr) / sizeof(arr[0]); int i = 0; int j = 0; for (i = 0; i < sz; i++) { for (j = 0, count = 0; j < sz; j++) { if (arr[i] == arr[j]) { count++; } } if (count == 1) { printf("%d ", arr[i]); } } printf("\n"); return 0; } //方法二 #include<stdio.h> void Find_single_num(int arr[], int sz, int* num1, int* num2) { int i = 0; int ret = 0; //首先将所有数字异或 for (i = 0; i < sz; i++) { ret ^= arr[i]; } //找出异或后的结果第几位出现1 int pos = 0; for (pos = 0; pos < 32; pos++) { if (((ret >> pos) & 1) == 1) { break; } } //分组异或 for (i = 0; i < sz; i++) { if (((arr[i] >> pos)&1) == 1) { *num1 ^= arr[i]; } else { *num2 ^= arr[i]; } } } int main() { int arr[] = { 1,2,3,4,5,1,2,3,4,6 }; int sz = sizeof(arr) / sizeof(arr[0]); int num1 = 0; int num2 = 0; Find_single_num(arr, sz, &num1, &num2); printf("%d %d\n", num1, num2); return 0; }
二. 喝汽水
1. 题目内容：
喝汽水，1瓶汽水1元，2个空瓶可以换一瓶汽水，给20元，可以喝多少汽水。
2. 解题思路
思路1：20元首先可以喝20瓶，此时手中有20个空瓶子
在20瓶的基础上加上空瓶换的汽水数数即可，每次的空瓶数/2是可兑换的汽水数
两个空瓶子可以喝一瓶，喝完之后，空瓶子剩余：empty/2(两个空瓶子换的喝完后产生的瓶子) + empty%2(不够换的瓶子)
如果瓶子个数超过1个，可以继续换，即重复2
思路2：
- 按照上述喝水和用瓶子换的规则的话，可以发现，其实就是个等差数列：money*2-1
3. 代码实现
//方法一: #include<stdio.h> int main() { int money = 0; int total = 0; int empty = 0; scanf("%d", &money); total = money; empty = money; while (empty > 1) { total += empty / 2; empty = empty / 2 + empty % 2; } printf("total = %d\n", total); return 0; } //方法二 #include<stdio.h> int main() { int money = 0; int total = 0; int empty = 0; scanf("%d", &money); if (money <= 0) { total = 0; } else { total = money * 2 - 1; } printf("total = %d\n", total); return 0; }
