c 做网站设计,免费ip代理服务器,尚城装修公司官网,如何宣传商务网站下面介绍四道题目和解法 1.杨氏矩阵
算法#xff1a;右上角计算
题目#xff1a;有一个数字矩阵#xff0c;矩阵的每行从左到右是递增的#xff0c;矩阵从上到下是递增的#xff0c;请编写程序在这样的矩阵中查找某个数字是否存在。
要求#xff1a;时间复杂度小于O(N…
下面介绍四道题目和解法 1.杨氏矩阵
算法右上角计算
题目有一个数字矩阵矩阵的每行从左到右是递增的矩阵从上到下是递增的请编写程序在这样的矩阵中查找某个数字是否存在。
要求时间复杂度小于O(N);
代码
#includestdio.h
int Find_arr(int arr[3][3],int r, int c, int k)
{int x 0;int y c - 1;while (xry0){if (arr[x][y] k){x;}else if (arr[x][y] k){y--;}elsereturn 1;}return 0;
}int main()
{int arr[3][3] {1,2,3,4,5,6,7,8,9};int k 0;printf(输入需要查找的数字:);scanf(%d,k);int ret 0;retFind_arr(arr,3,3,k);if (ret 1)printf(找到了\n);elseprintf(找不到\n);return 0;
} 【关键代码部分解析】
杨氏矩阵的特点矩阵的每行从左到右是递增的矩阵从上到下是递增的 代码思路从右上角或者左下角开始遍历我们这里从右上角开始
假设要找的值是5
第一次遍历与右上角的元素比较也就是与3比较。
第二次遍历与4比较。
第三次遍历与5比较相等得出结果。 【第二种代码】
要求找到了并且返回该元素的下标
返回双参数代码写法
#includestdio.h
#includeassert.h
int Find_arr(int arr[3][3], int* px, int* py, int k)
{assert(pxpy);int x 0;int y *py-1;while (x*px*py0){if (arr[x][y] k){x;}else if (arr[x][y] k){y--;}else{*px x;*py y;return 1;}}*px -1;*py -1;return 0;
}int main()
{int arr[3][3] { 1,2,3,4,5,6,7,8,9 };int k 0;printf(输入需要查找的数字:);scanf(%d, k);int ret 0;int x 3;int y 3;ret Find_arr(arr, x,y, k);if (ret 1){printf(找到了\n);printf(下标是%d %d\n, x, y);}else{printf(找不到\n);printf(下标是%d %d\n, x, y);}return 0;
}
返回双参数思路
将下标的地址作为参数不需要返回两个下标即可达到带回参数的目的。 2.杨辉三角
我们想要打印出下面的图案并且符号性质需要怎么做呢 1图形讲解
我们可以创建一个二维数组刚开始都赋值0。
然后可以打印出下半部分就行。
代码
#includestdio.h
int main()
{int arr[10][10] { 0 };//创建二维数组并初始化成0//打印下半部分int i 0;for (i0;i10;i){int j 0;for (j0;ji;j)//打印三角形的关键{printf(%d ,arr[i][j]);}printf(\n);}return 0;
}
运行结果 2赋值讲解
现在知道了杨辉三角的形状是怎么样打印出来的接下来需要对其赋值成为真正的杨辉三角。
杨辉三角从第三行和第二列开始每个数字的值其上方的数字左上角的数字 空白的默认为0其他部分默认赋值1。
代码
#includestdio.h
int main()
{int arr[10][10] { 0 };//创建二维数组并初始化成0//对杨辉三角赋值二维数组int i 0;for (i 0; i 10; i){int j 0;for (j 0; j i; j){if (j 0 || i j)arr[i][j] 1;if (i 2 j 1)//第三行和第二列开始//关系arr[i][j] arr[i - 1][j - 1] arr[i - 1][j];}}//打印下半部分i 0;for (i0;i10;i){int j 0;for (j0;ji;j)//打印三角形的关键{printf(%5d ,arr[i][j]);}printf(\n);}return 0;
}
运行结果 赋值解析 其实这就是杨辉三角了要是打出类似等腰三角形的性质则需要控制打印的格式属于打印的知识这里暂时不介绍 等腰三角的杨辉三角暂时不做解析
#includestdio.hint main()
{int arr[10][10] { 0 };//初始化int i 0;for (i 0; i 10; i){int j 0;for (j 0; j i; j){if (j 0 || i j)arr[i][j] 1;if (i 2 j 1)//第三行和第二列开始arr[i][j] arr[i - 1][j - 1] arr[i - 1][j];}}//打印i 0;int k 10;for (i 0; i 10; i){for (int k 0; k 26 - (6 * i / 2); k)//打印一行前面的空格{printf( );}int j 0;for (j 0; j i; j){printf(%5d , arr[i][j]);}printf(\n);}return 0;
}运行结果 3.单身狗1
题目一个数组中只有一个数字单独出现其他的数字都成对出现请找出这个单身狗
如123451234只有5只出现了一次所以需要找出5
【思路】
1利用异或操作符^二进制对应位相同为0相异为1。
2如a^a0a^00。
3并且支持交换律所以我们可以将所有的数据和0异或在一起最终的结果就是“单身狗”。
代码解法
#includestdio.h
int Find_dog_arr(int arr[],int sz)
{int tmp 0;int i 0;for (i 0; i sz; i){tmp tmp ^ arr[i];//全部异或在一起}return tmp;
}
int main()
{int arr[] { 1,2,3,4,5,1,2,3,4 };int sz sizeof(arr) / sizeof(arr[0]);int retFind_dog_arr(arr,sz);printf(%d\n,ret);return 0;
} tmp的最终结果就是5。 4.单身狗2
题目
一个数组中只有两个数字是出现一次其他所有数字都出现了两次。
编写一个函数找出这两个只出现一次的数字。
例如
有数组的元素是1234512346
只有5和6只出现1次要找出5和6。
【思路】
1这是单身狗1的升级版显然直接异或是不行的。
2所以我们可以先进行分类将两个单身狗分在两个不同的组再进行异或操作。
3怎么分类找出分类依据。 利用异或操作分类将所有数字异或起来的结果其实就是两个单身狗异或起来的结果再根据结果的二进制也就是根据某一位二进制是否为1进行分类。两个单身狗肯定有不同的二进制位结果肯定为1 【分类操作】
void Find_dog2_arr(int arr[], int sz, int* p1, int* p2)
{int tmp 0;int i 0;//1.全部异或在一起结果为两个单身狗异或在一起的结果for (i 0; i sz; i){tmp ^ arr[i];}//2.找出分组的依据i 0;int r 0;for (i 0; i 32; i){r arr[i];if ((tmp i) 1 1){r i;}}
} 1tmp是两个单身狗异或在一起的结果 2(tmpi)11的意思是找出tmp的二进制位为1的位也就是分组的关键 【思路刨析】 【整体代码】
#includestdio.h
void Find_dog2_arr(int arr[], int sz, int* p1, int* p2)
{int tmp 0;int i 0;//1.全部异或在一起结果为两个单身狗异或在一起的结果for (i 0; i sz; i){tmp ^ arr[i];}//2.找出分组的依据i 0;int r 0;for (i 0; i 32; i){r arr[i];if ((tmp i) 1 1){r i;}}//3.分组int u1 0;int u2 0;for (i 0; i sz; i){if ((arr[i] r) 1 1)//按位与{u1 ^ arr[i];}else{u2 ^ arr[i];}}*p1 u1;*p2 u2;
}
int main()
{int arr[] { 1,2,3,4,5,1,2,3,4,10 };int sz sizeof(arr) / sizeof(arr[0]);int s1 0;int s2 0;Find_dog2_arr(arr, sz, s1, s2);printf(单身狗1%d\n单身狗2%d, s1, s2);return 0;
}
