当前位置：首页 > article >正文

回溯算法习题其三-Java【力扣】【算法学习day.16】

article 2024/10/30 14:51:21

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.N皇后

题目链接:51. N 皇后 - 力扣（LeetCode）

题面:

基本分析:回溯遍历，然后维护一个数组来判断这个位置能不能下

代码:

class Solution {
    List<List<String>> list = new ArrayList<>();
    List<String> stack = new ArrayList<>();
    int len;
    public List<List<String>> solveNQueens(int n) {
        len = n-1;
        int[][] arr = new int[n][n];
        recursion(arr,0);
        return list;
    }
    public void recursion(int[][] arr,int l){
        if(l==len+1){
            list.add(new ArrayList<>(stack));
            return;
        }

        for(int i = 0;i<=len;i++){
            if(arr[l][i]==0){
                String str="";
                for(int j = 0;j<=len;j++){
                    if(j==i)str+="Q";
                    else str+=".";
                }
                stack.add(str);
                addStop(l,i,arr,1);
                recursion(arr,l+1);
                stack.removeLast();
                addStop(l,i,arr,-1);
            }
        }
        return;
    }

    public void addStop(int x,int y,int[][] arr,int blo){
        for(int i = 0;i<=len;i++){
            arr[x][i]+=blo;
            arr[i][y]+=blo;
        }
        int count = 1;
        while(x+count<=len&&y+count<=len){
            arr[x+count][y+count]+=blo;
            count++;
        }
        count = 1;
        while(x+count<=len&&y-count>=0){
            arr[x+count][y-count]+=blo;
            count++;
        }
         count = 1;
          while(x-count>=0&&y+count<=len){
            arr[x-count][y+count]+=blo;
            count++;
        }
         count = 1;
          while(x-count>=0&&y-count>=0){
            arr[x-count][y-count]+=blo;
            count++;
        }
    }
}

2.解数独

题目链接:37. 解数独 - 力扣（LeetCode）

题面:

基本分析:回溯遍历，只不过判断的条件复杂点而已

代码:

class Solution {
    int[][] arr = new int[9][9];
    public void solveSudoku(char[][] board) {
        for(int i = 0;i<=8;i++){
            for(int j = 0;j<=8;j++){
              char c  =  board[i][j];
            if(c>='0'&&c<='9'){
                arr[i][j] = c-'0';
            }
        }
    }
        try {
             recursion(board,0,0);
        } catch (RuntimeException e) {
    
        }
    }

    public void recursion(char[][] board,int x,int y){
        if(y==9){
            y = 0;
            x+=1;
        }
        if(x==9){
            throw new RuntimeException();
        }
        int count = 1;
        if(board[x][y]!='.')recursion(board,x,y+1);
        else{
            for(int i =1;i<=9;i++){
            if(rowAndColJudge(i,x,y)&&bitJudge(i,x,y)){
                arr[x][y]=i;
                board[x][y] =(char)('0'+i);
                recursion(board,x,y+1);
                arr[x][y]=0;
                board[x][y] = '.';
            }
        }
        }
    }

    public boolean rowAndColJudge(int count,int x,int y){
        for(int i =0;i<=8;i++){
            if(arr[x][i]==count||arr[i][y]==count)return false;
        }
        return true;
    }

    public boolean bitJudge(int count,int x,int y){
        x = x/3+1;
        y = y/3+1;
        for(int i = (x-1)*3;i<=x*3-1;i++){
            for(int j = (y-1)*3;j<=y*3-1;j++){
                if(arr[i][j]==count)return false;
            }
        }
        return true;
    }

}