题解 | #蛇形矩阵#
蛇形矩阵
https://www.nowcoder.com/practice/f228a074c5274619b26be544962375e1
动态内存的方法解题
本题难点在于算法相通算法同类题目迎刃而解
申请内存空间 -- 放数字 -- 打印释放内存
算法思路如下
*********************************************************************
用指针ptr表示首地址，p表示光标移动轨迹，根据偏移量(p-ptr)确定光标的具体地址
光标移动过程中，可以将移动轨迹粗分为两种 flag 1代表右上移动 2代表左下移动
右上移动和左下移动的算法比较好理解 现坐标加n为向下移动一行在减1则表示左下移动 反之 现坐标减n为向上移动一行在加1则表示右上移动
那么光标在移动过程中如何变换方向呢？ 其实不难发现 光标如果不遇到边界(上下左右)，就不会改变方向一直移动下去
所以 光标移动方向的改变与边界密切相连 - 只要不遇到边界就不需要改变flag
光标在遇到边界后 下一次进入循环则对其进行判断 - 针对特殊情况采用特殊的算法
如果遇到上/下边界就向右移(p+1)然后光标移动轨迹变为左下/右上
如果遇到左/右边界就向下移(p+n)然后光标移动轨迹变为右上/左下
最后的问题在于如何判断四个边界
上边界:p-ptr的偏移量 < n 则为上边界 - 有一种特殊情况 在偏移量为n-1时 (右上角)这个坐标既可以看作上边界也可以看作右边界 但根据逻辑要求,右上角的坐标归类为右边界,所以上边界的判断条件为 偏移量<n-1 ;
下边界:p-ptr的偏移量 >= n*(n-1) 则为下边界 - 有一种特殊情况 在偏移量为n*n-n时 (左下角)这个坐标既可以看作下边界也可以看作左边界 但根据逻辑要求,左下角的坐标归类为下边界,所以下边界的判断条件为 偏移量>=n*(n-1) ;
右边界:偏移量+1为n的整数倍(包含右上角);
左边界:偏移量正好为n的整数倍 - 排除左下角也就是要小于(或不等于)偏移量的n-1倍;
最后按序打印即可
***********************************************************************
代码如下
#include <stdio.h>
#include <stdlib.h>
int main() {
int n = 0;
scanf("%d", &n);
int* ptr = (int*)calloc(n * n, sizeof(int));
if (ptr == NULL) {
perror("main");
return 1;
}
//放数字
int count = 1;
int flag = 1;//1表示右上 2表示左下
int* p = ptr;
*p = count;
while (++count <= n * n) {
if (flag == 1) {
if ((p - ptr) < (n - 1)) { //上边界
p += 1;
*p = count;
flag = 2;
} else if ((p + 1 - ptr) % n == 0) { //右边界
p += n;
*p = count;
flag = 2;
} else {
p = p - n + 1;
*p = count;
}
} else if (flag == 2) {
if (((p - ptr) % n == 0)&&((p - ptr) / n < n-1)) { //左边界
p += n;
*p = count;
flag = 1;
} else if ((p-ptr)>=(n*n-n)) { //下边界
p += 1;
*p = count;
flag = 1;
} else {
p = p + n - 1;
*p = count;
}
}
}
//打印
int i = 0, j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
printf("%d ", *(ptr + i * n + j));
}
printf("\n");
}
//释放内存
free(ptr);
ptr = NULL;
return 0;
}
查看23道真题和解析
投递OPPO等公司10个岗位 >