数组元素循环右移问题、柱状图中最大的矩形、解数独

数组元素循环右移问题、柱状图中最大的矩形、解数独

• 2022年4月28日

• 目录

  • • 数组元素循环右移问题、柱状图中最大的矩形、解数独
    • 1、数组元素循环右移问题
    • 2、柱状图中最大的矩形
    • 3、解数独

1、数组元素循环右移问题

题目描述

一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入

一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输出

在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

样例输入

6 2
1 2 3 4 5 6

样例输出

5 6 1 2 3 4

以下程序实现了这一功能，请你填补空白处内容：

#include <stdio.h>
int main()
{int n, m, a[1000];scanf("%d %d", &n, &m);m = m % n; //判断移动单位m是否超过序列长度n，若是，则需要取余确定在数组上实际移动单位,本题m还是2int count = m;______________;//原序列的第n-m个整数之前、从第1个整数开始，直到第n-m个整数，向右移动m个单位for (int i = 0; i < count; i++) //从原序列的第n-m+1个整数开始，直到序列末尾位置n，向左移动n-m个单位scanf("%d", &a[i]);int first = 1;for (int i = 0; i < n; i++){if (!first)printf(" ");printf("%d", a[i]);first = 0;}
}

答案

while (m<n)
{scanf("%d",&a[m]);m++;
}

一个备注
思路讲解参考：数组元素循环右移问题(PAT).

1. 判断移动单位M是否超过序列长度N，若是，则需要取余确定在数组上实际移动单位。例如：N=6，M=7，实际是向右移动(M%N=1)个单位，故M=M%N;
2. 从原序列的第N-M个整数开始，直到序列末尾位置N，想左移动N-M个单位。例如题例，5和6都向前移动4个单位，这4个单位也就是不需要移动的1、2、3、4四个的单位长度，这样就使得整体数组向右移动两个单位。

2、柱状图中最大的矩形

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

输入

输入柱状图给定的高度

输出

输出柱状图能达到的最大矩形面积

样例输入

2 1 5 6 2 3

样例输出

10

以下程序实现了这一功能，请你填补空白处内容：

# include <stdio.h>
# include <stdlib.h>
static int largestRectangleArea (int *heights,int heightsSize)
{int *indexes = malloc(heightsSize * sizeof(int)); int *left = malloc(heightsSize * sizeof(int));int *right = malloc(heightsSize * sizeof(int)); int i , pos =0;for (i =0; i < heightsSize; i++){while ( pos >0 && heights[indexes[pos-1]] >= heights[i]) {pos--;}left[i] = pos == 0 ? -1 : indexes[pos - 1 ];indexes [pos++]= i;}pos = 0;for (i = heightsSize -1; i >= 0; i--){while (pos >0 && heights[indexes[pos - 1]] >= heights[i]){pos--;}right[i] = pos == 0 ? heightsSize : indexes[pos - 1];indexes [ pos ++]= i;}int max _ area =0;_________________;return max _ area;
}
int main (void)
{int nums[]={2,1,5,6,2,3};int count = sizeof(nums) / sizeof(*nums); printf("%d\n", largestRectangle(nums,count));return 0;
}

答案

for(i=0;i<heightsSize;i++)
{int area = heights[i] * (right[i] - left[i] - 1);max_area = area > max_area ? area:max_area;
}

一个备注
这题看大家评论说是运用了单调栈，但我并不是很清楚代码含义，之后补上。另外，放一下其他讲解。
力扣讲解：第一个和第二个

3、解数独

题目描述

编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
1．数字1-9在每一行只能出现一次。
2．数字1-9在每一列只能出现一次。
3．数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用＇.＇表示。
示例：

输入

一个二维数组board[i][j]表示数独棋盘

输出

一个数独的填法矩阵

样例输入

board =
[[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”],
[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”],
[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”],
[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”],
[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”],
[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”],
[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”],
[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”],
[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]

样例输出

[[“5”,“3”,“4”,“6”,“7”,“8”,“9”,“1”,“2”],
[“6”,“7”,“2”,“1”,“9”,“5”,“3”,“4”,“8”],
[“1”,“9”,“8”,“3”,“4”,“2”,“5”,“6”,“7”],
[“8”,“5”,“9”,“7”,“6”,“1”,“4”,“2”,“3”],
[“4”,“2”,“6”,“8”,“5”,“3”,“7”,“9”,“1”],
[“7”,“1”,“3”,“9”,“2”,“4”,“8”,“5”,“6”],
[“9”,“6”,“1”,“5”,“3”,“7”,“2”,“8”,“4”],
[“2”,“8”,“7”,“4”,“1”,“9”,“6”,“3”,“5”],
[“3”,“4”,“5”,“2”,“8”,“6”,“1”,“7”,“9”]]
解释：输出的数独如上图所示，唯一有效的解决方案如下所示：

提示

• board . length ==9
• board [ i ]. length ==9
• board [ i ][ j ］是一位数字或者＇.＇
• 题目数据保证输入数独仅有一个解

以下程序实现了这一功能，请你填补空白处的内容：

#include <bits/stdc++.h>
using namespace std;class Solution {public :void solveSudoku ( vector < vector < char >> &board){int size = board.size();vector<vector<bool>> rows(size, vector<bool>(10));vector<vector<bool>> cols(size, vector<bool>(10)); vector<vector<bool>> boxes(size, vector<bool>(10));for (int i = 0; i < size; i++){for (int j = 0; j < size ; j++){ if (board[i][j] != '.'){int num = board[i][j] - '0';int idx = i / 3 * 3 + j / 3;rows[i][num] = true; cols[j][num] = true;boxes[idx][num] = true;}}}dfs(board, 0, rows, cols, boxes);}private :bool valid(int num, int row, int col, int idx, vector<vextor<bool>> &rows,vector<vector<bool>> &cols, vector<vector<bool>> &boxes){ return !rows[row][num] && !cols[col][num] && !boxes[idx][num]; }bool dfs(vector<vector<char>> &board, int size, vector<vector<bool>> &rows, vector<vector<bool>> &cols, vector<vector<bool>> &boxes) {if(size == 9 * 9){return true;}else {bool ok = false;int row = size / 9;int col = size % 9;int idx = row / 3 * 3 + col / 3; if (board[row][col] =='.'){for (int i = 1; i <= 9; i++){if (valid (i, row, col, idx, rows, cols, boxes)){board[row][col] = i + '0';rows[row][i] = true;cols[col][i] = true;boxes[idx][i] = true;___________________________;if( !ok){rows[row][i] = false;cols[col][i] = false;boxes[idx][i] = false;board[row][col] = '.';}}}}else{ok = dfs(board, size + 1, rows, cols, boxes);}return ok;}}
};

答案

ok = dfs(board, size + 1, rows, cols, boxes);

一个备注
我真的会谢，我看不懂代码，过几日研究了补上解析。