首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法:深度、广度优先搜索算法与剪枝-实战

算法:深度、广度优先搜索算法与剪枝-实战

作者头像
营琪
发布2019-11-04 16:34:07
5850
发布2019-11-04 16:34:07
举报
文章被收录于专栏:营琪的小记录营琪的小记录

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_43126117/article/details/100548551


leetcode:102. 二叉树的层次遍历

题解:一看就是搜索问题,根据层次遍历出所有元素。用广度优先搜索算法简单。

方法一:BFS

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();     
        if (root == null) return lists;

        Queue<TreeNode> queue = new LinkedList<>();            //使用队列保存同一层节点
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();                          //得到队列中同一层 有N个
            List<Integer> list = new ArrayList<>();

            for (int i = 0; i < size; i++) {                  //遍历N次,即取出队列中同一层节点             

                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) queue.add(node.left);  //下一层节点先保存到队列中
                if (node.right != null) queue.add(node.right);
            }
            lists.add(list);
        }
        return lists;
    }

方法二:DFS

深度优先搜索也是可以的,只需要携带层次信息,在存储时选择合适位置即可。

    List<List<Integer>> result = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder2(TreeNode root) {
        if (root == null) return result;
        DFS(root, 0);
        return result;
    }

    public void DFS(TreeNode node, int level) {
        if (result.size() == level) result.add(new ArrayList<>());
        if (node.left != null) DFS(node.left, level + 1);
        if (node.right != null) DFS(node.right, level + 1);  
        result.get(level).add(node.val);            //选择合适的层次list
    }

leetcode:104. 二叉树的最大深度

题解:也是搜索问题,只是搜索结束条件要看清楚,是当前节点没有左右节点时为最大深度。也就是一个深度优先搜索算法。

方法一:DFS

    //一开始做的dfs,通过当前节点没有左右节点时保存 当前层次
    private int max = 0;
    public int maxDepth2(TreeNode root) {
        if (root == null) return 0;
        DFS(root, 1);
        return max;
    }
    public void DFS(TreeNode node, int level) {
        if (node.left != null) DFS(node.left, level + 1);
        if (node.right != null) DFS(node.right, level + 1);
        if (level > max) max = level;            //当前层数与之前最大层数相比较
    }

    //下面这个解法比较简洁,是通过 循环计算左右节点层数 从0开始依此加1,再左右比较,保留最大+1。
//并不需要考虑左右节点
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;                    /递归出口
        int left_height = maxDepth(root.left);
        int right_height = maxDepth(root.right);
        return java.lang.Math.max(left_height, right_height) + 1;
    }

方法二:BFS

跟上一题很像,走完一层就加一,直到最后一层

   public int maxDepth3(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            level++;      //队列中同层已经出完,加一
        }
        return level;
    }

leetcode:111. 二叉树的最小深度

方法一:DFS

这个和上一题有区别在于,max改为min也不行,当9有左节点没有右节点的时候 ,还会返回1。当前节点只有一侧节点时,上一题解法就错误了。下面做法保证当前节点没有左右节点才输出。

    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        // 左孩子为空,只考虑右孩子的方向
        if (root.left == null) return minDepth(root.right) + 1;
        // 右孩子为空,只考虑左孩子的方向
        if (root.right == null) return minDepth(root.left) + 1;

        int left_height = minDepth(root.left);
        int right_height = minDepth(root.right);

        return java.lang.Math.min(left_height, right_height) + 1;
    }

方法二:BFS

最先一层的某个节点没有左右节点时,即返回。这样算法效率应该更高。

public int minDepth2(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
                if (node.left == null && node.right == null) return level;  //第一个没有左右节点,即返回
            }
        }
        return level;
    }

leetcode:22. 生成正确括号

题解:也是搜索的问题,假如用穷举得到所有结果,再从中找正确的结果。也是可行的,但是写的会特别复杂。这里可以利用剪枝的概念,先去掉不必要的解,比如左括号在第一位,左右括号数应该相等,左括号先写入再写右括号等。

方法一:搜索加剪枝

public List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<>();
    prun("", list, n, n);
    return list;
}

public void prun(String str, List<String> list, int leftsize, int rightsize) {//第一步剪枝:左右括号个数相同
    if (leftsize > 0) prun(str + "(", list, leftsize - 1, rightsize);//第二步剪枝:保证左括号先写入
    if (leftsize < rightsize) prun(str + ")", list, leftsize, rightsize - 1);//第三步剪枝:保证写入左右括号相同
    if (rightsize == 0) list.add(str);

}

附加:回溯

    //这个递归是有一个回溯的过程的,这里隐藏了,下面这种做法可看出来。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        StringBuffer str = new StringBuffer();
        prun(str, list, n, n);
        return list;
    }

    public void prun(StringBuffer str, List<String> list, int leftsize, int rightsize) {
        if (leftsize > 0) {
            str.append("(");
            prun(str, list, leftsize - 1, rightsize);
            str.deleteCharAt(str.length() - 1);                //递归返回字符串需要保持原有的,即回溯
        }
        if (leftsize < rightsize) {
            str.append(")");
            prun(str, list, leftsize, rightsize - 1);
            str.deleteCharAt(str.length() - 1);
        }
        if (rightsize == 0) list.add(str.toString());
    }
}

leetcode:51. n皇后问题

题解:皇后不能相互攻击,即如图画红线的位置不能有另外一个皇后,这个解法也就是把四条红线用代码表示出来。

下面这个解法是比较容易理解的

方法一:搜索加剪枝

class Solution51 {
    int n;
    int row[];          //行列
    int hills[];        //撇
    int dales[];        //捺
    int queens[];       //皇后位置
    List<List<String>> lists = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        row = new int[n];
        hills = new int[2 * n];  //2n作用:保证有存储的数组。
        dales = new int[4 * n];
        queens = new int[n];
        DFS(0);
        return lists;
    }

    public void DFS(int num) {
        for (int i = 0; i < n; i++) {//填第num行i个皇后所处的位置queens[0]=0,表明第1行的皇后位于第1列
            if (row[i] + hills[num + i] + dales[num - i + 2 * n] == 0) {//检测当前填入的皇后与之前的所有皇后是否冲突
                placeQueen(num, i, true);       //更改四条红线状态
                if (num + 1 == n) addQueen();     //找到其中一个解法
                else DFS(num + 1);          //递归,下一行
                placeQueen(num, i, false);      //回溯,还原四条红线状态
            }
        }
    }
    
    private void addQueen() {
        List<String> list = new ArrayList<>();
        for (int i : queens) {
            StringBuffer str = new StringBuffer();
            for (int j = 0; j < i; j++) str.append(".");
            str.append("Q");
            for (int j = i+1; j < n ; j++) str.append(".");
            list.add(str.toString());
        }
        lists.add(list);
    }

    private void placeQueen(int num, int i, boolean b) {
        if (b) {
            queens[num] = i;
            row[i] = 1;
            hills[num + i] = 1;
            dales[num - i + 2 * n] = 1;
        } else {
            queens[num] = 0;
            row[i] = 0;
            hills[num + i] = 0;
            dales[num - i + 2 * n] = 0;
        }
    }

}

方法二:搜索+剪枝(化简)

public List<List<String>> solveNQueens(int n) {
        List<List<String>> lists = new ArrayList<>();
        helper(0, new Boolean[n], new Boolean[2 * n], new Boolean[2 * n], new String[n], lists);
        return lists;
    }

    private void helper(int row, Boolean[] col, Boolean[] hills, Boolean[] dales, String[] str, List<List<String>> lists) {
        if (row  == str.length){
            List<String> list = new ArrayList<>();
            for (int i = 0 ; i < str.length ; i++) {
                list.add(str[i].toString());
            }
            lists.add(list);
        }else{
            for (int i = 0; i < str.length; i++) {
                int hills_size = 2*str.length - (row + i)-1;
                int dales_size = row - i + str.length;
                if (col[i]==null&&hills[hills_size]==null&&dales[dales_size]==null){
                    char[] c = new char[str.length];
                    Arrays.fill(c,'.');c[i] = 'Q';
                    str[row] = new String(c);
                    col[i] =false;hills[hills_size] = false; dales[dales_size] = false;
                    helper(row+1,col,hills,dales,str,lists);
                    col[i] = null; hills[hills_size] = null; dales[dales_size] = null;
                }
            }
        }
    }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-09-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • leetcode:102. 二叉树的层次遍历
    • 方法一:BFS
      • 方法二:DFS
      • leetcode:104. 二叉树的最大深度
        • 方法一:DFS
          • 方法二:BFS
          • leetcode:111. 二叉树的最小深度
            • 方法一:DFS
              • 方法二:BFS
              • leetcode:22. 生成正确括号
                • 方法一:搜索加剪枝
                  • 附加:回溯
                  • leetcode:51. n皇后问题
                    • 方法一:搜索加剪枝
                      • 方法二:搜索+剪枝(化简)
                      领券
                      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档