蛇形填充n阶方阵、石子移动问题
目录
一、蛇形填充n阶方阵
问题描述
小U面临一个有趣的任务：在一个 n×nn×n 的方阵中填入 11 到 n×nn×n 这些数字，并要求按照蛇形顺序从右上角开始，沿着方阵的边界顺时针进行填充。蛇形填充的特殊排列方式使得每一层数字呈现出波浪形的排列方式。
例如，当 n=4n=4 时，方阵应如下所示：
10 11 12 1
9 16 13 2
8 15 14 3
7 6 5 4
你需要编写程序输出填充后的方阵，确保格式的整齐性。
测试样例
样例1：
输入：
n = 4
输出：[[10, 11, 12, 1], [9, 16, 13, 2], [8, 15, 14, 3], [7, 6, 5, 4]]
样例2：
输入：
n = 5
输出：[[13, 14, 15, 16, 1], [12, 23, 24, 17, 2], [11, 22, 25, 18, 3], [10, 21, 20, 19, 4], [9, 8, 7, 6, 5]]
样例3：
输入：
n = 3
输出：[[7, 8, 1], [6, 9, 2], [5, 4, 3]]
解题思路：
-
理解问题：
- 你需要在一个
n x n的方阵中按照蛇形顺序填充数字。 - 填充顺序是从右上角开始，沿着方阵的边界顺时针进行填充。
- 每一层数字呈现出波浪形的排列方式。
- 你需要在一个
-
数据结构选择：
- 使用一个二维数组（矩阵）来存储填充的数字。
- 使用两个数组来表示移动的方向：一个用于行变化，一个用于列变化。
-
算法步骤：
- 初始化一个
n x n的二维数组，所有元素初始化为0。 - 定义一个变量
num用于记录当前要填充的数字，初始值为1。 - 定义两个数组
dx和dy分别表示四个方向的移动：右、下、左、上。 - 定义一个变量
direction用于记录当前的移动方向，初始值为0（表示向右）。 - 从右上角开始填充数字，每次填充后检查下一个位置是否越界或已经被填充过，如果是则改变方向。
- 重复上述步骤，直到所有数字都被填充。
- 初始化一个
最终代码：
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> solution(int n) {
vector<vector<int>> matrix(n, vector<int>(n, 0)); // 初始化n x n的矩阵，所有元素为0
int num = 1; // 当前要填充的数字
int dx[] = {0, 1, 0, -1}; // 右、下、左、上的方向变化
int dy[] = {1, 0, -1, 0};
int direction = 0; // 初始方向为向右（0代表向右，1代表向下，2代表向左，3代表向上）
int x = 0, y = n - 1; // 起始位置在右上角
while (num <= n * n) {
matrix[x][y] = num++;
int nx = x + dx[direction];
int ny = y + dy[direction];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || matrix[nx][ny] != 0) {
direction = (direction + 1) % 4;
nx = x + dx[direction];
ny = y + dy[direction];
}
x = nx;
y = ny;
}
return matrix;
}
int main() {
vector<vector<int>> a1 = solution(4);
cout << (a1 == vector<vector<int>>{{10, 11, 12, 1}, {9, 16, 13, 2}, {8, 15, 14, 3}, {7, 6, 5, 4}}) << endl;
vector<vector<int>> a2 = solution(5);
cout << (a2 == vector<vector<int>>{{13, 14, 15, 16, 1}, {12, 23, 24, 17, 2}, {11, 22, 25, 18, 3}, {10, 21, 20, 19, 4}, {9, 8, 7, 6, 5}}) << endl;
vector<vector<int>> a3 = solution(3);
cout << (a3 == vector<vector<int>>{{7, 8, 1}, {6, 9, 2}, {5, 4, 3}}) << endl;
return 0;
}运行结果：
二、石子移动问题
问题描述
小S正在玩一个关于石子的游戏，给定了一些石子，它们位于一维数轴的不同位置，位置用数组 stones 表示。如果某个石子处于最小或最大的一个位置，我们称其为端点石子。
在每个回合，小S可以将一颗端点石子移动到一个未占用的位置，使其不再是端点石子。游戏继续，直到石子的位置变得连续，无法再进行任何移动操作。
你需要帮助小S找到可以移动的最大次数。
测试样例
样例1：
输入：
stones = [7, 4, 9]
输出：2
样例2：
输入：
stones = [6, 5, 4, 3, 10]
输出：3
样例3：
输入：
stones = [1, 2, 3, 4, 5]
输出：0
解题思路：
问题理解
你有一个数组 stones，表示石子在一维数轴上的位置。游戏的目标是通过移动端点石子（即位于最小或最大位置的石子），使得所有石子的位置变得连续，并且无法再进行任何移动操作。你需要计算出可以移动的最大次数。
数据结构选择
- 由于我们需要对石子的位置进行排序和比较，使用数组是一个合理的选择。
- 我们可以对数组进行排序，以便更容易找到端点石子。
算法步骤
- 排序：首先对
stones数组进行排序，这样我们可以更容易地找到端点石子。 - 计算最大移动次数：
- 最大移动次数可以通过计算当前石子分布与理想连续分布之间的差距来确定。
- 理想情况下，石子应该占据
[min(stones), min(stones) + n - 1]这个区间。 - 计算当前分布与理想分布之间的最大差距，并减去已经占据的位置数。
- 计算最小移动次数：
- 使用滑动窗口来计算最小移动次数。
- 滑动窗口的大小为
n，确保窗口内最多有n个石子。 - 计算窗口内已经占据的位置数，并更新最小移动次数。
关键点
- 理解端点石子的概念及其在移动过程中的变化。
- 通过排序和滑动窗口来优化计算过程。
最终代码：
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
int solution(vector<int> &stones) {
// write code here
if (stones.size() == 1) {
return 0;
}
sort(stones.begin(), stones.end());
int n = stones.size();
// 计算最大移动次数
int maxMoves =
max(stones[n - 1] - stones[1], stones[n - 2] - stones[0]) - (n - 2);
// 计算最小移动次数，使用滑动窗口
int minMoves = INT_MAX;
int j = 0;
for (int i = 0; i < n; i++) {
// 确保窗口内最多有 n 个石子
while (j < n && stones[j] - stones[i] + 1 <= n) {
j++;
}
// 如果窗口内有 n - 1 个石子，且空位为 1，则需要特殊处理
int alreadyInPlace = j - i;
if (alreadyInPlace == n - 1 && stones[j - 1] - stones[i] + 1 == n - 1) {
minMoves = min(minMoves, 2);
} else {
minMoves = min(minMoves, n - alreadyInPlace);
}
}
return maxMoves;
}
int main() {
vector<int> v1 = {7, 4, 9};
vector<int> v2 = {6, 5, 4, 3, 10};
vector<int> v3 = {1, 2, 3, 4, 5};
cout << (solution(v1) == 2) << endl;
cout << (solution(v2) == 3) << endl;
cout << (solution(v3) == 0) << endl;
return 0;
}运行结果：
原文地址：https://blog.csdn.net/m0_73302939/article/details/144315609
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！