题解 | #下棋#
下棋
http://www.nowcoder.com/practice/ddb95ccacada4024905e5a4f740c56a1
题目描述
题目难度：中等
通过率：24.02%
知识点：模拟
题目分析
这是一个典型的代码模拟现实的题目，通过数据结构抽象模拟出棋盘，并根据规则计算出答案；
读完题干提炼出以下内容：
- 题目围绕一个n*n的正方形棋盘展开；
- 棋盘的构成是按照数字螺旋递增构成，数字从1开始；
- 牛牛每次投掷骰子，结果作为步长，即会前进1-6步；
- 假设现在的数字是i, 走j步后数字的计算公式为
(i+j-1)%(n*n) +1，说直接点就是数字走到n*n之后就回到1开始继续走，例如3*3的棋盘，走到9的下一步就是1； - 题目中给出的计算公式转成文字描述就是以当前节点为中心，横竖一个步长的范围内的数据总和。
针对第五点举个例子：
假设是一个4*4 的矩阵，当前走到了14
若本次投掷为步长为1，则该公式需要累加的范围如下图所示：
若投掷步长为2，则对应累加范围是：
假设当前坐标为 i,j 步长为k，则累加范围是：
i-k+1 到 i+k-1 行的所有数字（边界上限制是n-1列，下线为0）
加上
j-k+1 到 j+k-1 列的所有数字（边界上限制是n-1列，下线为0）
但是同一个数字只会加一次，不会重复加。
拿示例的例子来说
输入：
4,[1,2,5,6,2]
复制
返回值：
[48,138,274,410,510]
棋盘数字如下图所示：
第一步1，走到了数字2，坐标为(0,1)，由于步长为1 ，所以计算范围是第0行和第1列的所有数字之和，如图所示：
所以累计分数为：0(题干说初始在1的分数为0）+1+2+3+4+13+16+9 = 48第二步,步长为2，即从2走到了4，此时计算范围是
所以本次累计和为： 48（上次结果）+ 1+2+3+4+12+13+14+5+15+6+8+7 = 138；
- 第三步，步长为5，从4走到9，计算范围是全部数字（因为计算后的区域覆盖了全棋盘）
所以本次累计和为： 138（上次结果）+ 1+2+3+..+16 = 274；
第四步，步长为6，从9走到了15，计算范围仍然覆盖了全部数字，
所以本次累计和为： 274（上次结果）+ 1+2+3+..+16 = 410；第五步，步长为2，从15 走一步到16 再走一步到 1，计算范围是：
所以本次累计和为： 410（上次结果）+ 1+2+3+4+12+13+14+5+11+16+10+9 = 510；
所以返回结果是[48,138,274,410,510]。
解题步骤：
我们把解题步骤大致分两步，
- 画出棋盘
- 计算范围并求和
画出棋盘
直接上代码了，这个比较简单
(index是我为了快速获取某个数字对应的下标所建的一个索引结构。这里可以先忽略)
public static int[][] drawChessboard(int n){
int[][] chessboard = new int[n][n];
// 当前未填充的棋盘边界，
int max_j = n-1, max_i = n-1, min_i = 0, min_j = 0;
int count = 1;// 从1开始填充数字
// 当还有空间可以填充，则继续填充
while ((min_i<=max_i)||(min_j<=max_j)){
for(int j=min_j;j<=max_j;j++){
chessboard[min_i][j] = count;
index[count] = new int[]{min_i,j};//记录对应count的坐标
count++;
}
min_i++;// min_i行已经填充完
for(int i=min_i;i<=max_i;i++){
chessboard[i][max_j] = count;
index[count] = new int[]{i,max_j};
count++;
}
max_j--;// max_j列已经填充完
for(int j=max_j;j>=min_j;j--){
chessboard[max_i][j] = count;
index[count] = new int[]{max_i,j};
count++;
}
max_i--;// max_i行已经填充完
for(int i=max_i;i>=min_i;i--){
chessboard[i][min_j] = count;
index[count] = new int[]{i,min_j};
count++;
}
min_j++;// min_j行已经填充完
}
return chessboard;
}计算范围并求和的方法：
暴力法
按照常规的思路去遍历累加棋盘的数字，相关计算的关键代码如：
// chessboard表示已填充好的棋盘， fi,fj表示当前所在坐标，scope代表步长
private int calculateScope(int[][] chessboard, int fi,int fj, int scope) {
int sum = 0;
int n = chessboard.length;
// 每个数字只能累加一次，所以这里记录下是否加过了
int[][] visited = new int[n][n];
for(int i=Math.max(0,fi-scope+1);i<=Math.min(n-1,fi+scope-1);i++){
//累加范围内行的所有数字
for(int j=0;j<n;j++){
sum+=chessboard[i][j];
visited[i][j] = 1;
}
}
for(int j=Math.max(0,fj-scope+1);j<=Math.min(n-1,fj+scope-1);j++){
//累加范围内列的所有数字
for(int i=0;i<n;i++){
// 确保每个数只加一次
if(visited[i][j]!=1){
sum+=chessboard[i][j];
}
}
}
return sum;
}但是这个在时间耗时较多，提交会出现计算超时的问题。
预计算法
我们发现，计算的范围都是正行整列，暴力法中涉及很多重复计算，其实棋盘n并不大，我们完全可以提前将每一列和行的和计算出来，但是在具体计算时会涉及减去交叉的部分，但是由于步长1-6分布，所以交叉的部分最大也就是6*6的规模，相对来说就可以忽略了。
所以需要一个预计算的函数，这里需要特别注意取模，防止越界（暴力法中忽略了这个点）
public Map<String,Integer> preCalculate2(int[][] chessboard){
int n = chessboard.length;
Map<String,Integer> preSums = new HashMap<>(n*2);
// 计算每一行的和
for(int i=0;i<n;i++){
long lineSum = 0;
for(int j=0;j<n;j++){
lineSum+=chessboard[i][j];
preSums.put("line:"+i,(int)(lineSum%1000000007));
}
}
// 计算每一列的和
for(int j=0;j<n;j++){
long colomnSum = 0;
for(int i=0;i<n;i++){
colomnSum+=chessboard[i][j];
preSums.put("colomn:"+j,(int)(colomnSum%1000000007));
}
}
return preSums;
}计算好之后我们再看下计算范围的函数应该怎么写：
private int calculateScope2(int[][] chessboard, int fi,int fj, int scope, Map<String, Integer> preSums) {
long sum = 0;
int n = chessboard.length;
// 直接加上范围行的和
for(int i=Math.max(0,fi-scope+1);i<=Math.min(n-1,fi+scope-1);i++){
sum+=preSums.get("line:"+i);
}
// 直接加上范围列的和
for(int j=Math.max(0,fj-scope+1);j<=Math.min(n-1,fj+scope-1);j++){
sum+=preSums.get("colomn:"+j);
}
// 减去交叉部分的数字
for(int i=Math.max(0,fi-scope+1);i<=Math.min(n-1,fi+scope-1);i++){
for(int j=Math.max(0,fj-scope+1);j<=Math.min(n-1,fj+scope-1);j++){
sum-=chessboard[i][j];
}
}
// 同样要注意和的范围别越界
return (int)(sum%1000000007);
}完整代码：
这里包含了一些无用代码，但可以体现出整个题目的优化过程，所以保留下来了并做了注释。
import java.util.*;
public class Solution {
/**
* 求每一步后的总分数，所有分数都对1,000,000,007取模
* @param n int整型 棋盘大小
* @param query int整型一维数组 每次掷出的点数的列表
* @return int整型一维数组
*/
// 因为一开始是用map结果保存坐标信息的，但是这样会遇到内存超出范围的问题，所以后续优化成了int[][]来记录下标
//public static Map<Integer,String> index = new HashMap<>();
public static int[][] index;
public int[] getScores (int n, int[] nums) {
int[] re =new int[nums.length];
int n2 = n*n;
index = new int[n * n + 1][2];
// 画棋盘
int[][] chessboard = drawChessboard(n);
// 预计算，计算出整列和整行的和
Map<String,Integer> preSums2 = preCalculate2(chessboard);
// 当前走到的数字
int cur_num = 1;
// 当前的累计和，为了防止越界先用long记录，后面取模
long cur_sum = 0;
for(int i=0;i<nums.length;i++){
int adder = nums[i];// 步长
cur_num = cur_num+adder;// 当前所在数字
cur_num = cur_num % n2==0 ? n2:cur_num%n2;// 走到上限从1开始
cur_sum += calculateScope(chessboard,cur_num,adder,preSums2);//累积求和
cur_sum = cur_sum%1000000007;//计算当前值
re[i] = (int)cur_sum;//保存该步累积求和数据
}
return re;
}
// 暴力法遍历求和
private int calculateScope(int[][] chessboard, int fi,int fj, int scope) {
int sum = 0;
int n = chessboard.length;
int[][] visited = new int[n][n];
for(int i=Math.max(0,fi-scope+1);i<=Math.min(n-1,fi+scope-1);i++){
for(int j=0;j<n;j++){
sum+=chessboard[i][j];
visited[i][j] = 1;
}
}
for(int j=Math.max(0,fj-scope+1);j<=Math.min(n-1,fj+scope-1);j++){
for(int i=0;i<n;i++){
if(visited[i][j]!=1){
sum+=chessboard[i][j];
}
}
}
return sum;
}
// 预计算法求和
private int calculateScope2(int[][] chessboard, int fi,int fj, int scope, Map<String, Integer> preSums) {
long sum = 0;
int n = chessboard.length;
for(int i=Math.max(0,fi-scope+1);i<=Math.min(n-1,fi+scope-1);i++){
sum+=preSums.get("line:"+i);
}
for(int j=Math.max(0,fj-scope+1);j<=Math.min(n-1,fj+scope-1);j++){
sum+=preSums.get("colomn:"+j);
}
for(int i=Math.max(0,fi-scope+1);i<=Math.min(n-1,fi+scope-1);i++){
for(int j=Math.max(0,fj-scope+1);j<=Math.min(n-1,fj+scope-1);j++){
sum-=chessboard[i][j];
}
}
return (int)(sum%1000000007);
}
private int calculateScope(int[][] chessboard, int cur_num, int scope, Map<String, Integer> preSums) {
// 按照map记录下标对应的处理代码
// String[] ijs = index.get(cur_num+"").split(",");
// int fi = Integer.parseInt(ijs[0]);
// int fj = Integer.parseInt(ijs[1]);
int fi = index[cur_num][0];
int fj = index[cur_num][1];
//pre1 return preSums.get(fi+","+fj+","+scope);
return calculateScope2(chessboard, fi, fj,scope, preSums);
}
// 画棋盘
public static int[][] drawChessboard(int n){
int[][] chessboard = new int[n][n];
int max_j = n-1, max_i = n-1, min_i = 0, min_j = 0;
int count = 1;
while ((min_i<=max_i)||(min_j<=max_j)){
for(int j=min_j;j<=max_j;j++){
chessboard[min_i][j] = count;
index[count] = new int[]{min_i,j};
//index.put(count+"",min_i+","+j);
count++;
}
min_i++;
for(int i=min_i;i<=max_i;i++){
chessboard[i][max_j] = count;
index[count] = new int[]{i,max_j};
//index.put(count+"",i+","+max_j);
count++;
}
max_j--;
for(int j=max_j;j>=min_j;j--){
chessboard[max_i][j] = count;
index[count] = new int[]{max_i,j};
//index.put(count+"",max_i+","+j);
count++;
}
max_i--;
for(int i=max_i;i>=min_i;i--){
chessboard[i][min_j] = count;
index[count] = new int[]{i,min_j};
//index.put(count+"",i+","+min_j);
count++;
}
min_j++;
}
return chessboard;
}
//预计算之前还想了一个办法，就是对每个节点从步长1-6都预计算出来和，这样都不用按行按列加了，直接取值就行，但是这样时间会超时，于是后面优化成上面提到的那种办法
public Map<String,Integer> preCalculate(int[][] chessboard){
int n = chessboard.length;
Map<String,Integer> preSums = new HashMap<>();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=1;k<=6;k++){
String key = i+","+j+","+k;
preSums.put(key,calculateScope(chessboard,i,j,k));
}
}
}
return preSums;
}
// 预计算出各行列的和
public Map<String,Integer> preCalculate2(int[][] chessboard){
int n = chessboard.length;
Map<String,Integer> preSums = new HashMap<>(n*2);
for(int i=0;i<n;i++){
long lineSum = 0;
for(int j=0;j<n;j++){
lineSum+=chessboard[i][j];
preSums.put("line:"+i,(int)(lineSum%1000000007));
}
}
for(int j=0;j<n;j++){
long colomnSum = 0;
for(int i=0;i<n;i++){
colomnSum+=chessboard[i][j];
preSums.put("colomn:"+j,(int)(colomnSum%1000000007));
}
}
return preSums;
}
}时间复杂度：，n表示棋盘大小，m为查询长度。
空间复杂度：，棋盘空间
投递牛客等公司10个岗位 >
