文章目录
前言
第一周主要讲述了C语言的基础语法，内容也较为简单；但作业有几题较有挑战性，本文主要记录本周的上课内容及较为有挑战的作业，以作课后的自我总结。
一、2021/12/28——Day1
Day1讲述环境安装等写代码前各类准备。
二、2021/12/29——Day2
Day2讲述数据类型、进制转换以及标准输入相关内容。
1.找出n个升序数组中的公共元素
分析：只需找出两数组的公共元素，并保存在数组result中；再寻找result数组与其他数组的公共元素；直到result为空或与其他数组都比较过。就可以将问题分解为找出两个升序数组的公共元素问题。
找出两个升序数组a,b的公共元素：用两指针pointA和pointB分别指向a,b的首个元素。若a[pointA] < b[pointB]，pointA+1；若a[pointA] = b[pointB]，将a[pointA]存储至result数组中；若a[pointA] > b[pointB]，pointB+1。直至遍历完数组a或b，result数组中存储的就是a和b的公共元素。
找出两个升序数组a,b的公共元素代码如下：
//count为result数组的长度
int count = 0;
//返回值为公共元素组成的数组
int* FindPublic(int a[], int b[], int NumA, int NumB) {
int pointA = 0, pointB = 0;
int* result = (int*)malloc(sizeof(int) * NumA);
count = 0;
while (pointA < NumA && pointB < NumB) {
if (a[pointA] < b[pointB])
pointA++;
else if (a[pointA] > b[pointB])
pointB++;
else {
result[count] = a[pointA];
pointA++;
pointB++;
count++;
}
}
return result;
}
找出n个升序数组的公共元素代码如下：
result = FindPublic(a , b , numA , numB);
for(int i = 0; i < n - 2;i++){
numA = count;
if(numA == 0){
break;
}
printf("Please Input the arrLen:");
scanf("%d", &numB);
printf("Please Input the %dth array:", i);
for(int j = 0; j < numB; j++){
scanf("%d", &b[j]);
}
result = FindPublic(result, b, count, numB);
}
2.给定一个n个整型元素的数组a，其中有一个元素出现次数超过n/2，求这个元素
分析：
思路一：先排序，再寻找。但排序效率很低；
思路二：通过哈希表保存不同元素出现次数。只需要遍历一次数组a，遍历一次哈希表。时间复杂度O(n)；空间复杂度和数组a中的不同元素个数有关；
思路三：利用选举时候选人思想；若存在票数大于n/2的候选人，则该候选人的票数比其他候选人的票数之和还要多。
candidate存储当前占优势的候选人，prior代表当前候选人的优势为多少；设置candidate的初始值为a[0]，prior的初始值为0；从a[0]开始遍历整个数组。
遍历结束的条件为：（1）遍历完整个数组 或 （2）prior的值大于 n/2 。
若当前得到的数组元素a[k] != candidate，则原候选人的优势变小，prior-1；否则prior+1。当prior=-1时，说明当前候选人已失去票数优势，则更新候选人candidate=a[k]，并设置prior=1。
该方法只需要遍历一边数组a，且只需要常数级的额外空间，时间复杂度为O(n)，空间复杂度为O(1)。
代码如下：
void Find_candidate() {
int* A, NumA;
int candidate, prior;
printf("Please Input the arrlen:");
scanf("%d", &NumA);
A = (int*)malloc(sizeof(int) * NumA);
printf("Please Input the arry elem:");
for (int i = 0; i < NumA; i++)
scanf("%d", &A[i]);
int i = 0;
prior = 0;
candidate = A[0];
while (i < NumA && prior <= NumA / 2) {
if (A[i] == candidate) {
prior++;
}
else {
prior--;
if (prior == -1) {
candidate = A[i];
prior = 1;
}
}
i++;
}
if (prior >= 1) {
printf("The Element is %d\n", candidate);
}
else {
printf("No such Element\n");
}
}
三、2021/12/30——Day3
Day3讲述各类输入输出函数（scanf、getchar、printf、putchar）；讲述各类运算符的运算方式、优先级；讲述选择循环语法。
1.从键盘上输入字符，分别统计一下其中字母，数字，其他字符的个数；将统计的字母，数字，其他字符的个数以柱状图的形式打印。
这题暂时不会，只会统计各类字符个数，如何打印还没讲。等待更新~
2.有101个整数，其中有50个数出现了两次，1个数出现了一次， 找出出现了一次的那个数。
分析：利用异或操作：两相同的数字异或结果为0；任何数字a与0异或的结果都是它本身。将数组中的数依次异或，得到的结果就是只出现了一次的那个数。
代码如下：
void AppearOnce() {
int a[101];
int num = 0;
printf("Please Enter 101 Numbers:");
for (int i = 0; i < 101; i++) {
scanf("%d", &a[i]);
num = num ^ a[i];
}
printf("Number %d is the Only Appear Once\n", num);
}
3.有102个整数，其中有50个数出现了两次，2个数出现了一次， 找出出现了一次的那两个数。
分析：将102个数进行分堆，将两个只出现了一次的数a，b分到两堆中。
分成什么样的两堆：将x，y两数分在不同的两堆heapA，heapB中，并且令同样的数分在同一堆中。就可以将该问题分解为两个问题21。
如何分堆：
- 将数组a依次异或，得到数m。数m实质是由x和y相互异或得到的，且m != 0；
- 根据异或的规律，m在二进制表示下“1”所在的位，x和y对应的值是不同的。例如：x = (1001 0010)B，y = (1010 1010)B，m = x ^ y = (0011 1000)B，在二进制下，m的第4,5,6三位为1，即证明x和y的4,5,6三位互不相同；
- 因此只需要找到m的最低位“1”所在，根据数组a中各个数在该位的值进行分堆。就能够实现：（1）将所有相同的数分在同一堆；（2）将x和y分在不同堆
代码如下：
void AppearOnce() {
int a[102];
int num = 0;
printf("Please Enter 102 Numbers:");
for (int i = 0; i < 102; i++) {
scanf("%d", &a[i]);
num = num ^ a[i];
}
//寻找num中最低位的1
int cmp = 1;
while ( !(cmp & num)) {
cmp = cmp << 1;
}
int num1 = 0, num2 = 0;
for (int i = 0; i < 102; i++) {
if (a[i] & cmp) {
num1 = num1 ^ a[i];
}
else {
num2 = num2 ^ a[i];
}
}
printf("Number %d and %d are the Only Appear Once\n", num1, num2);
}
4.有103个整数，其中有50个数出现了两次，三个数出现了一次， 找出出现了一次的那三个数。
分析：将103个数分成两堆
分成什么样的两堆：将x，y，z两数分在不同的两堆heapA，heapB中，并且令同样的数分在同一堆中。其中使得一堆中存在x，y，z中的两个数，另一堆中存在x，y，z中的一个数。就可以将该问题分解为一个问题21，一个问题32。
如何分堆（暴力分堆，最多分堆32次）：
- 从count = 1开始，将数组a中 a&count 结果为真的分到heapA，a&count 结果为假的数分到heapB。随后将count左移一位。
- 由于将奇数个数分为两堆，必定存在一堆个数为偶数个，另一堆的数个数为奇数个。接下来需在偶数堆中判断，是否将x，y分入此堆。判断方法为：将偶数堆中的所有数依次异或，若得到结果为0，说明x，y，z都在奇数堆中，需要将count左移一位，重新进行分堆。
代码如下（只包含分堆代码）：
void Divide_Heap() {
int a[103], Heapa[103], Heapb[103];
int HeapaLen = 0;
int HeapbLen = 0;
printf("Please Enter 103 Numbers:");
for (int i = 0; i < 103; i++) {
scanf("%d", &a[i]);
}
int count = 1;
//划分
for (int i = 0; i < 32; i++) {
for (int j = 0; j < 103; j++) {
if (a[j] & count) {
Heapa[HeapaLen] = a[j];
HeapaLen++;
}
else {
Heapb[HeapbLen] = a[j];
HeapbLen++;
}
}
int numa = 0;
int numb = 0;
for (int j = 0; j < HeapaLen - 1; j++) {
numa = numa ^ Heapa[j];
}
for (int j = 0; j < HeapbLen - 1; j++) {
numb = numb ^ Heapb[j];
}
if (numa != 0 && numb != 0) {
break;
}
i++;
count = count << 1;
}
}
四、2021/12/31——Day4
Day4讲述一维数组、二维数组、字符数组极其性质。跨年夜题较为简单，非常银杏化。
五、2022/1/1——Day5
Day5讲述指针、指针的传递及性质；在函数中的形参和实参。
1.大整数加法。 实现任意范围的两个整数的加法（ 整数的范围用 int 型的变量无法表示,50位）
分析：用字符串存储大整数a，b，再从低位到高位依次相加，存入空字符串c中即可（注意c中存储的内容和结果相反，应该将c翻转，从而得到正确答案）
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
//将a[left]到a[right]内容翻转
void Flip(char a[], int left, int right) {
char c;
while (left < right) {
c = a[left];
a[left] = a[right];
a[right] = c;
left++;
right--;
}
}
int main() {
while (1) {
char a[51], b[51],sum[52];
printf("请输入大整数a（不超过50位）:");
gets(a);
printf("请输入大整数b（不超过50位）:");
gets(b);
int lenA = strlen(a);
int lenB = strlen(b);
int i = lenA - 1;
int j = lenB - 1;
int add = 0;
int numA, numB;
//c=0代表无低位进位，c=1代表有低位进位
int c = 0;
while (i >= 0 && j >= 0) {
numA = a[i] - '0';
numB = b[j] - '0';
int k = numA + numB + c;
if (k >= 10) {
c = 1;
sum[add] = k - 10 + '0';
}
else {
sum[add] = k + '0';
c = 0;
}
i--;
j--;
add++;
}
while (i >= 0) {
numA = a[i] - '0';
int k = numA + c;
if (k >= 10) {
c = 1;
sum[add] = k - 10 + '0';
}
else {
c = 0;
sum[add] = k + '0';
}
i--;
add++;
}
while (j >= 0) {
numB = b[j] - '0';
int k = numB + c;
if (k >= 10) {
c = 1;
sum[add] = k - 10 + '0';
}
else {
c = 0;
sum[add] = k + '0';
}
j--;
add++;
}
sum[add] = 0;
Flip(sum, 0, add - 1);
printf("a+b=");
puts(sum);
}
return 0;
}
思考：是否可以参照组成原理中CLA四位加法器，不需要从低到高一位一位生成进位位，而是一次性生成四位进位位？