2020年1月20日 旋转右螺旋

问题描述

> 第一种解法：依次完成上下左右
> While(执行n/2向上取整次){
>         Up(arr,row,from,to,num);       
>          完成上面一行，row行 从form到to，
>         Right(arr,col,from,to,num);
>         完成右边一列，col列 从from到to，     
>         Down(arr,row,from,to,num);   
>         完成下边一行，row行 从to回到from
>         Left(arr,col,from,to,num);        
>         完成左边一列，col列 从to回到from
> }

第二种算法：直接用算法找规律
将矩阵分为4大块：
上【红】下【蓝】左【绿】右【黑】
上：行数<=n/2向上取整
                判断一下是否在列的取值范围：
                行数row,m+1-row
下：行数>n/2

例如说：20行22列
给定第一个数：5行6列，只需要找到起始的位置273，根据第六列可以算出276
给定第二个数：15行8列，先找到对应的圈数：20-15+1=6，起始位置361，算出根据第8列可算出350
给定第三个数：15行1列，找到圈数算出80，根据行数15可算出67
给定第四个数：15行22列，找到圈数算出22，根据行数15算出36

实例代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class G {
    public static void main(String[] args) {
        try {

            //1、输入四个数据m、n、row、col
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String str = null;
            str = br.readLine();
            String[] values = str.split(" ");
            int n = Integer.parseInt(values[0]);
            int m = Integer.parseInt(values[1]);
            str = br.readLine();
            values = str.split(" ");
            int row = Integer.parseInt(values[0]);
            int col = Integer.parseInt(values[1]);
            //方法1：
            System.out.println("方法1矩阵：");
            long start1 = System.currentTimeMillis();
            fun2(n,m,row,col);
            long end1 = System.currentTimeMillis();
            System.out.println("方法1执行时间"+(end1-start1)+"ms");

            System.out.println("---------------------------------------------");
            //方法2：
            System.out.print("方法2查询结果：");
            long start2 = System.currentTimeMillis();
            fun(n,m,row,col);
            long end2 = System.currentTimeMillis();
            System.out.println();
            System.out.println("方法2执行时间："+(end2-start2)+"ms");
            System.out.println("方法2矩阵：");
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    fun(n,m,i,j);
                }
                System.out.println();
            }
            //2、计算值

        } catch (IOException e) {
            e.printStackTrace();
        }

    }
        public static void fun(int n,int m,int row,int col) {
            try {
                if(row<=n/2+(n%2==0?0:1) && col>=row&&col<=m+1-row){//1 - m     2 - m-1
                // 上
                    int pos_up = getPos_up(n, m, row, col);
                    System.out.print(pos_up+"\t");
                }else if (row>n/2+(n%2==0?0:1) && col>=n+1-row&&col<=m-n+row){
                // 下
                    int pos_down = getPos_down(n, m, row, col);
                    System.out.print(pos_down+"\t");
                }else if(col<=m/2+(m%2==0?0:1)){
                // 左
                    int pos_left = getPos_left(n, m, row, col);
                    System.out.print(pos_left+"\t");
                }else{
                // 右
                    int pos_right = getPos_right(n, m, row, col);
                    System.out.print(pos_right+"\t");
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    public static int getPos_up(int n,int m,int row,int col){//20行20列 5行6列
        int quan = row;//行数即圈数
        int s=0;
        int time = 0;
        int M = m;
        while(time<quan-1){
            s+=(M+n)*2-4;
            M-=2;n-=2;
            time++;
        }
        s=s+col-quan+1;
        return s;
    }
    public static int getPos_left(int n,int m,int row,int col){
        int quan = col;
        int s=0;
        int time = 0;
        int M = m;
        while(time<=quan-1){
            s+=(M+n)*2-4;
            M-=2;n-=2;
            time++;
        }
        s-=(row-1-quan);
        return s;
    }
    public static int getPos_right(int n,int m,int row,int col){
        int quan = m + 1 - col;
        int s=0;
        int time = 0;
        int M = m;
        while(time<quan-1){
            s+=(M+n)*2-4;
            M-=2;n-=2;
            time++;
        }
        s+=(m-(quan-1)*2);
        s+=(row-quan);
        return s;
    }
    public static int getPos_down(int n,int m,int row,int col) {// 2 5
        int time = 0;
        int s=0;
        int M = m;
        //圈数：
        int quan = n-row+1;//20-19
        while(time<quan-1){
            s+=(M+n)*2-4;
            M-=2;n-=2;
            time++;
        }
        s += (M+n)-2;
        s+=(m+1-col-quan+1);
        return s;
    }



    public static void fun2(int n,int m,int row,int col){
        //1、初始化为0
        int[][] arr= new int[n+1][m+1];
        //2、上下左右
        int num = 1 ;
        for (int i = 1; i <= m/2+(m%2==0?0:1); i++) {//35 37
            // 上
            num = up(arr,i,i,m+1-i,num);//  10 10,22
            // 下
            num = right(arr,m+1-i,i+1,n-i,num);
            // 左
            num = down(arr,n+1-i,m+1-i,i,num);
            // 右
            num = left(arr,i,n-i,i+1,num);
        }
        display(arr);
        System.out.println("方法1查询结果："+arr[row][col]);
    }

    private static int left(int[][] arr, int c, int to, int from,int num) {
        for (int i = to; i >= from ; i--) {
            if(arr[i][c]==0)arr[i][c]=num++;
        }
        return num;
    }

    private static int down(int[][] arr, int r, int to, int from, int num) {
        for (int i = to; i >= from; i--) {
            if(arr[r][i]==0)arr[r][i]=num++;
        }
        return num;
    }

    private static int right(int[][] arr, int c, int from, int to, int num) {
        for (int index = from; index <= to; index++) {
            if(arr[index][c]==0)arr[index][c]=num++;
        }
        return num;
    }

    private static void display(int[][] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                System.out.print(arr[i][j]+"\t");
            }
            System.out.println();
        }
    }

    public static int up(int[][] arr,int r,int from,int to,int num){
        for (int i = from; i <= to; i++) {
            if(arr[r][i]==0)arr[r][i] = num++;
        }
        return num;
    }
}