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

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

前言

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


习题

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;
    }

}

后言

上面是回溯算法的余下习题,下一篇会讲解回溯算法的其他相关力扣习题,希望有所帮助,一同进步,共勉!   


http://www.kler.cn/a/371684.html

相关文章:

  • APP如何提升关键词排名?
  • Linux——常见指令及其权限理解(正在更新中)
  • 鸿蒙生态开发以及技术栈介绍
  • 【YOLOv11[基础]】实例分割 + 跟踪
  • 鸿蒙开发融云demo发送图片消息
  • ts 中 enum 作为对象的 key
  • Android——metaData
  • EJB项目如何升级SpringCloud
  • 二、ARMv8寄存器之系统寄存器
  • jjycheng字符签名
  • BGP路由优选
  • 【Python爬虫实战】网络爬虫完整指南:网络协议OSI模型
  • 嵌入式学习(6)-Stm32F4xx裸机移植FlashDB(三)
  • 2025考研各省市网上确认时间汇总!
  • Gitlab 官方推荐自动化cache服务器Minio的安装
  • 淘宝API接口( item_get- 淘宝商品详情查询)
  • 数据结构 之 二叉树的遍历------先根遍历(五)
  • 绘制线性可分支持向量机决策边界图 代码解析
  • 使用Docker Compose简化微服务部署
  • 5G中NG接口
  • Cisco Packet Tracer 8.0 路由器静态路由配置
  • 设计模式---模版模式
  • 【机器学习】过拟合与欠拟合
  • 用哈希表封装unordered_map与unordered_set
  • sklearn机器学习实战
  • C++ 二叉树进阶:相关习题解析