蛇形添补n阶方阵、石子移动题目
目次一、蛇形添补n阶方阵
题目形貌
测试样例
解题思绪：
终极代码：
运行效果：
二、石子移动题目
题目形貌
测试样例
解题思绪：
题目明确
数据布局选择
算法步调
关键点
终极代码：
运行效果：
一、蛇形添补n阶方阵
题目形貌
小U面对一个风趣的任务：在一个 n×nn×n 的方阵中填入 11 到 n×nn×n 这些数字，并要求按照蛇形次序从右上角开始，沿着方阵的边界顺时针举行添补。蛇形添补的特殊分列方式使得每一层数字出现出波浪形的分列方式。
比方，当 n=4n=4 时，方阵应如下所示：
10 11 121
9 16 132
8 15 143
7654
你须要编写步调输出添补后的方阵，确保格式的整齐性。
测试样例
样例1：
输入：n = 4
输出：[, , , ]
样例2：
输入：n = 5
输出：[, , , , ]
样例3：
输入：n = 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 = num++;
int nx = x + dx;
int ny = y + dy;
if (nx < 0 || nx >= n || ny < 0 || ny >= n || matrix != 0) {
direction = (direction + 1) % 4;
nx = x + dx;
ny = y + dy;
}
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;
} 运行效果：
https://i-blog.csdnimg.cn/direct/04d63881696c40aa82a2c84db5bd8fc2.png
二、石子移动题目
题目形貌
小S正在玩一个关于石子的游戏，给定了一些石子，它们位于一维数轴的差别位置，位置用数组 stones 表现。如果某个石子处于最小或最大的一个位置，我们称其为端点石子。
在每个回合，小S可以将一颗端点石子移动到一个未占用的位置，使其不再是端点石子。游戏继承，直到石子的位置变得连续，无法再举行任何移动利用。
你须要资助小S找到可以移动的最大次数。
测试样例
样例1：
输入：stones =
输出：2
样例2：
输入：stones =
输出：3
样例3：
输入：stones =
输出：0
解题思绪：
题目明确
你有一个数组 stones，表现石子在一维数轴上的位置。游戏的目的是通过移动端点石子（即位于最小或最大位置的石子），使得全部石子的位置变得连续，而且无法再举行任何移动利用。你须要盘算出可以移动的最大次数。
数据布局选择
[*]由于我们须要对石子的位置举行排序和比力，利用数组是一个公道的选择。
[*]我们可以对数组举行排序，以便更容易找到端点石子。
算法步调
[*]排序：起首对 stones 数组举行排序，如许我们可以更容易地找到端点石子。
[*]盘算最大移动次数：
[*]最大移动次数可以通过盘算当前石子分布与理想连续分布之间的差距来确定。
[*]理想环境下，石子应该占据 这个区间。
[*]盘算当前分布与理想分布之间的最大差距，并减去已经占据的位置数。
[*]盘算最小移动次数：
[*]利用滑动窗口来盘算最小移动次数。
[*]滑动窗口的巨细为 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 - stones, stones - stones) - (n - 2);
// 计算最小移动次数，使用滑动窗口
int minMoves = INT_MAX;
int j = 0;
for (int i = 0; i < n; i++) {
// 确保窗口内最多有 n 个石子
while (j < n && stones - stones + 1 <= n) {
j++;
}
// 如果窗口内有 n - 1 个石子，且空位为 1，则需要特殊处理
int alreadyInPlace = j - i;
if (alreadyInPlace == n - 1 && stones - stones + 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://i-blog.csdnimg.cn/direct/d76f3c152d07421e8e9609caaea10146.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]