leetcode51. N 皇后 (java)

这篇具有很好参考价值的文章主要介绍了leetcode51. N 皇后 (java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode 51 N 皇后

原题链接:
https://leetcode.cn/problems/n-queens/

题目描述

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例1:
leetcode51. N 皇后 (java)
输入:n = 4
输出:[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例2:
输入:n = 1
输出:[[“Q”]]

提示:
1 <= n <= 9

解题思路

我们用递归来解决这个问题:
我们一行一行的去验证哪列可以放置皇后,
(因此这个思路就推导出,需要循环加递归)

每到一行,我们只需要验证他前面皇后放的位置,来确定他哪里能放.
验证的方法:
同一列有的肯定不能放了
还有就是斜线位置怎么验证,
举个例子:
A 点(1,2) 和B 点 (2,3) 这两个点在一条斜线上,
那么 1-2 肯定等于 2 - 3 .,
也就是A 的行号 - B 的行号 等于A 的列号 - B 的列号.

代码演示

 /**
     * 主函数 leetcode 可以复制进去测试
     * @param n
     * @return
     */
    public static List<List<String>> solveNQueens(int n) {
        ArrayList<List<String>> ans = new ArrayList<>();
        String[][]que = init(n);
        int[] record = new int[n];
        process(0,n,record,que,ans);
        return ans;
    }

    /**
     *
     * @param N
     * @param index
     * @param record
     * @param ans
     * @param queens
     */
    public static void process(int N ,int index,int[]record,String[][]ans,List<List<String>> queens){
        //当考察到N 说明已经全部考察过了.是符合要求的.直接把答案加进去
        if (index == N ){
            queens.add(convert(ans));
            return;
        }
        // 开始考察当前所到的行,哪一列可以放置
        for (int row = 0; row < N;row++){
            if(check(record,index,row)){
                record[index] = row;
                ans[index][row] = "Q";
                process(N,index+1,record,ans,queens);
                //每次递归后要恢复原状,不然会影响下次判断如何放置Q
                ans[index][row] = ".";
            }
        }

    }


    /**
     * 考察哪一列 可与放置皇后
     * @param record
     * @param col
     * @param row
     * @return
     */
    public static boolean check(int[]record,int col,int row){
        //和之前放置过的皇后去做比较
        for (int i = 0; i < col;i++){
            if (record[i] == row || Math.abs(record[i] - row) == Math.abs(col - i) ){
                return false;
            }
        }
        return true;
    }

    /**
     * 初始化一个二维数组
     * @param N
     * @return
     */
    public static String[][] init(int N){
        String[][] ques = new String[N][N];
        for (int i = 0; i < N;i++){
           for (int j = 0; j < N;j++){
               ques[i][j] = ".";
           }
        }
        return ques;
    }

    /**
     *
     * @param ques
     * @return
     */
    public static List<String> convert(String[][]ques){
        ArrayList<String> que = new ArrayList<>();
        for (String[] ans : ques){
            String sb = "";
           for (String str : ans){
               sb += str;
           }
            que.add(sb);
        }
        return que;
    }

leetcode52 N 皇后II

Leetcode 52 N 皇后 II文章来源地址https://www.toymoban.com/news/detail-470143.html

到了这里,关于leetcode51. N 皇后 (java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode原题:变位词组(哈希)

    题目: 编写一种方法,对字符串数组进行排序,将所有变位词组合在一起。变位词是指字母相同,但排列不同的字符串。 示例: 输入: [\\\"eat\\\", \\\"tea\\\", \\\"tan\\\", \\\"ate\\\", \\\"nat\\\", \\\"bat\\\"], 输出: [   [\\\"ate\\\",\\\"eat\\\",\\\"tea\\\"],   [\\\"nat\\\",\\\"tan\\\"],   [\\\"bat\\\"] ] 解题思路: 本题是需要将相同的变位词放在一维数组中,

    2024年02月11日
    浏览(38)
  • leetcode原题: 峰与谷

    题目: 在一个整数数组中,“峰”是大于或等于相邻整数的元素,相应地,“谷”是小于或等于相邻整数的元素。例如,在数组{5, 8, 4, 2, 3, 4, 6}中,{8, 6}是峰, {5, 2}是谷。现在给定一个整数数组,将该数组按峰与谷的交替顺序排序。 示例: 输入: [5, 3, 1, 2, 3] 输出: [5, 1, 3,

    2024年02月11日
    浏览(55)
  • leetcode原题:节点间通路

    题目: 给定有向图,设计一个算法,找出两个节点之间是否存在一条路径。 示例:  输入:n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2  输出:true  解题思路: 本题借助队列,利用队列的先进先出的特点,保证访问每个节点的顺序不被破坏。 1. 建立邻接表map ,讲

    2024年02月13日
    浏览(52)
  • leetcode原题: 生存人数

    题目: 给定 N 个人的出生年份和死亡年份,第 i 个人的出生年份为 birth[i] ,死亡年份为 death[i] ,实现一个方法以计算生存人数最多的年份。 你可以假设所有人都出生于 1900 年至 2000 年(含 1900 和 2000 )之间。如果一个人在某一年的任意时期处于生存状态,那么他应该被纳入

    2024年02月10日
    浏览(46)
  • leetcode原题:绘制直线(位运算)

    题目: 已知一个由像素点组成的单色屏幕,每行均有 w 个像素点,所有像素点初始为 0 ,左上角位置为 (0,0) 。 现将每行的像素点按照「每 32 个像素点」为一组存放在一个 int 中,再依次存入长度为 length 的一维数组中。 我们将在屏幕上绘制一条从点 (x1,y) 到点 (x2,y) 的直线(

    2024年02月12日
    浏览(40)
  • leetcode原题: 堆箱子(动态规划实现)

    题目: 给你一堆n个箱子,箱子宽 wi、深 di、高 hi。箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法,搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。 输入使用数组 [wi, di, hi] 表示每个箱子。 示例:  输入:box

    2024年02月11日
    浏览(44)
  • leetcode原题:颜色填充(经典的递归问题)

    题目: 编写函数,实现许多图片编辑软件都支持的「颜色填充」功能。 待填充的图像用二维数组 image 表示,元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。 「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的

    2024年02月12日
    浏览(47)
  • 【力扣 51】N 皇后(回溯+剪枝+深度优先搜索)

    按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后

    2024年02月22日
    浏览(39)
  • java访问https链接下载图片

    // 文件下载存储路径 String savePath = “D:/zhxcmfs/myFiles”; // 文件命名 String fileName = “图片.png”; // https文件下载链接 String apiHttp = “https://gimg2.baidu.com/image_search/src=http%3A%2F%2Flmg.jj20.com%2Fup%2Fallimg%2F1114%2F040221103339%2F210402103339-8-1200.jpgrefer=http%3A%2F%2Flmg.jj20.comapp=2002size=f9999,10000q=a80n

    2023年04月08日
    浏览(46)
  • 关于岛屿的三道leetcode原题:岛屿周长、岛屿数量、统计子岛屿

    题1: 岛屿周长 给定一个 row x col 的二维网格地图 grid ,其中:gridi = 1 表示陆地, gridi = 0 表示水域。 网格中的格子 水平和垂直 方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。 岛屿

    2024年02月10日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包