题目:
代码:
class NeighborSum {private int n;private int[][] grid;private int[][] adjacent_sum;private int[][] diagonal_sum;private int[][] index_map;public NeighborSum(int[][] grid) {this.grid=grid;n=grid.length;adjacent_sum=new int[n][n];diagonal_sum=new int[n][n];index_map=new int[n*n][2];//int count=0;//以为是按顺序排列的 实际顺序可能打乱for(int i=0;i<n;i++){for(int j=0;j<n;j++){index_map[grid[i][j]][0]=i;index_map[grid[i][j]][1]=j;}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==0&&j==0){//考虑左上角顶点adjacent_sum[i][j]=grid[i+1][j]+grid[i][j+1];diagonal_sum[i][j]=grid[i+1][j+1];}else if(i==n-1&&j==n-1){//考虑右下角顶点adjacent_sum[i][j]=grid[i-1][j]+grid[i][j-1];diagonal_sum[i][j]=grid[i-1][j-1];}else if(i==0&&j==n-1){//考虑右上角顶点adjacent_sum[i][j]=grid[i+1][j]+grid[i][j-1];diagonal_sum[i][j]=grid[i+1][j-1];}else if(i==n-1&&j==0){//考虑左下角顶点adjacent_sum[i][j]=grid[i-1][j]+grid[i][j+1];diagonal_sum[i][j]=grid[i-1][j+1];}else if(i==0){//第一行除了左上右上顶点的数adjacent_sum[i][j]=grid[i+1][j]+grid[i][j+1]+grid[i][j-1];diagonal_sum[i][j]=grid[i+1][j+1]+grid[i+1][j-1];}else if(i==n-1){//最后一行除了左下右下顶点的数adjacent_sum[i][j]=grid[i-1][j]+grid[i][j+1]+grid[i][j-1];diagonal_sum[i][j]=grid[i-1][j-1]+grid[i-1][j+1];}else if(j==0){//第一列除了左上左下顶点的数adjacent_sum[i][j]=grid[i-1][j]+grid[i+1][j]+grid[i][j+1];diagonal_sum[i][j]=grid[i+1][j+1]+grid[i-1][j+1];}else if(j==n-1){//最后一列除了右上右下顶点的数adjacent_sum[i][j]=grid[i-1][j]+grid[i+1][j]+grid[i][j-1];diagonal_sum[i][j]=grid[i+1][j-1]+grid[i-1][j-1];}else{//非顶点、非第一行、非第一列、非最后一行、非最后一列的数adjacent_sum[i][j]=grid[i-1][j]+grid[i+1][j]+grid[i][j-1]+grid[i][j+1];diagonal_sum[i][j]=grid[i-1][j-1]+grid[i-1][j+1]+grid[i+1][j-1]+grid[i+1][j+1];}}}}public int adjacentSum(int value) {return adjacent_sum[index_map[value][0]][index_map[value][1]];}public int diagonalSum(int value) {return diagonal_sum[index_map[value][0]][index_map[value][1]];}
}/*** Your NeighborSum object will be instantiated and called as such:* NeighborSum obj = new NeighborSum(grid);* int param_1 = obj.adjacentSum(value);* int param_2 = obj.diagonalSum(value);*/
总结:
方法为If-Else大法,算法上不是最优,优化该代码可采用预处理。
时间复杂度:初始化 O(n^2),其余 O(1) (n为grid的行数和列数)
空间复杂度:初始化 O(n^2),其余 O(1)。