Java教程

算法从入门到放弃——第六期 岛屿(II)

本文主要是介绍算法从入门到放弃——第六期 岛屿(II),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 算法从入门到放弃——第四期 岛屿_u014783007的博客-CSDN博客

之前有写了一篇岛屿的问题,今天来看一个岛屿的变种,N皇后

题目如下

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1: 


输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

这题在leetcode是困难,但是做过岛屿之后,明眼一看感受是能做, 虽然返回奇奇怪怪,但是本质还是岛屿问题,岛屿问题模板就是bfs岛屿块,脑海里两层循环有了,之后就是放“Q”,放第一个肯定放哪都行,放第二个就要验证能不能放了,而验证的方法需要考虑一下,这里如果我们是从左往右,从上到下放,那么我需要检测我的上方,左方,左上,右上四个角度是不是已经放过“Q”了即可,如果不满足条件就回溯。

好像结束了,没错,过程就是这么简单,然后只要代码实现就可以了

    public static void setChess(String[][] chess, int row, List<List<String>> result) {
        if (row == chess.length) {
            List<String> ss = new ArrayList<>();
            for (int i = 0; i < chess.length; i++) {
                String s = "";
                for (int j = 0; j < chess[0].length; j++) {
                    s+=chess[i][j];
                }
                ss.add(s);
            }
            result.add(new ArrayList<>(ss));
            ss.clear();
            return;
        }

        for (int col = 0; col < chess[0].length; col++) {
            if (positionIsValid(chess, row, col)) {
                chess[row][col] = "Q";
                setChess(chess, row + 1, result);
                chess[row][col] = ".";
            }
        }
    }

    public static boolean positionIsValid(String[][] chess, int row, int col) {
        //注意外层是从上到下,从左到右遍历的
        //那么对于当前节点而言,有可能填过Q区域,只能在上,左,右上,左上四个方向上
        for (int i = 0; i < row; i++) {
            if (chess[i][col].equals("Q")) {
                return false;
            }
        }
        for (int i = 0; i < col; i++) {
            if (chess[row][i].equals("Q")) {
                return false;
            }
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < chess[0].length; i--, j++) {
            if (chess[i][j].equals("Q")) {
                return false;
            }
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chess[i][j].equals("Q")) {
                return false;
            }
        }
        return true;
    }

这种题目一般不会作为面试出现,总体而言为了考察递归和回溯,但是需要很多额外的方法去体现算法,这不太符合面试的要求,当然熟练掌握回溯做这道题应该也不会有难度

这篇关于算法从入门到放弃——第六期 岛屿(II)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!