【算法题解】 Day6 BFS | DFS

sidiot

发布于 2023-08-31 13:37:49

31000

代码可运行

文章被收录于专栏：技术大杂烩技术大杂烩

运行总次数：0

代码可运行

每日一题

题目

921. 使括号有效的最少添加难度：medium

只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串 s ，移动N次，你就可以在字符串的任何位置插入一个括号。

例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。

返回 为使结果字符串 s 有效而必须添加的最少括号数。

示例 1：

输入： s = "())"
输出： 1

示例 2：

输入： s = "((("
输出： 3

提示：

1 <= s.length <= 1000
s 只包含 '(' 和 ')' 字符。

方法一：贪心

思路

根据题意，这题自然而然的优先使用「贪心」算法，刚好可以巩固一下昨天所学的【算法题解】 Day5 贪心；

每个左括号必须对应一个右括号，而且左括号必须在对应的右括号之前。

对于括号匹配的题目，常用的做法是使用栈进行匹配，栈具有后进先出的特点，因此可以保证右括号和最近的左括号进行匹配。其实，这道题可以使用计数代替栈，进行匹配时每次都取距离当前位置最近的括号，就可以确保平衡。

从左到右遍历字符串，在遍历过程中维护左括号的个数以及添加次数。

如果遇到左括号，则将左括号的个数加 1。

如果遇到右括号，则需要和前面的左括号进行匹配，具体做法如下：

如果左括号的个数大于 0，则前面有左括号可以匹配，因此将左括号的个数减 1，表示有一个左括号和当前右括号匹配；
如果左括号的个数等于 0，则前面没有左括号可以匹配，需要添加一个左括号才能匹配，因此将添加次数加 1。

遍历结束后，需要检查左括号的个数是否为 0。如果不为 0，则说明还有剩下的左括号没有匹配，对于每个剩下的左括号都需要添加一个右括号才能匹配，此时需要添加的右括号个数为剩下的左括号个数，将需要添加的右括号个数加到添加次数。

无论是哪种添加的情况，都是在遇到括号无法进行匹配的情况下才进行添加，因此上述做法得到的添加次数是最少的。

解题

Python：

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = cnt = 0
        for c in s:
            if c == '(':
                cnt += 1
            elif cnt > 0:
                cnt -= 1
            else:
                ans += 1
        return ans + cnt

Java：

class Solution {
    public int minAddToMakeValid(String s) {
        int ans = 0;
        int leftCount = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftCount++;
            } else {
                if (leftCount > 0) {
                    leftCount--;
                } else {
                    ans++;
                }
            }
        }
        ans += leftCount;
        return ans;
    }
}

589. N 叉树的前序遍历

题目

589. N 叉树的前序遍历难度：easy

给定一个 n 叉树的根节点 root ，返回 其节点值的 前序遍历 。

n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：

输入： root = [1,null,3,2,4,null,5,6]
输出： [1,3,5,6,2,4]

示例 2：

输入： root = [1]
输出： [[1]]

示例 3：

输入： root = []
输出： []

方法一

思路

递归思路比较简单，每次递归时，先访问根节点，然后依次递归访问每个孩子节点即可。

解题

Python：

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        ans = []
        def dfs(node: 'Node'):
            if node is None:
                return
            ans.append(node.val)
            for ch in node.children:
                dfs(ch)
        dfs(root)
        return ans

Java：

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public void helper(Node root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        for (Node ch : root.children) {
            helper(ch, res);
        }
    }
}

方法二：迭代

思路

方法一中利用递归来遍历树，实际的递归中隐式调用了栈，在此我们可以直接模拟递归中栈的调用。在前序遍历中，我们会先遍历节点本身，然后从左向右依次先序遍历该每个以子节点为根的子树。

解题

Python：

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if root is None:
            return []
        ans = []
        st = [root]
        while st:
            node = st.pop()
            ans.append(node.val)
            st.extend(reversed(node.children))
        return ans

Java：

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<Node> stack = new ArrayDeque<Node>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            res.add(node.val);
            for (int i = node.children.size() - 1; i >= 0; --i) {
                stack.push(node.children.get(i));
            }
        }
        return res;
    }
}

102. 二叉树的层序遍历

题目

102. 二叉树的层序遍历难度：medium

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：

输入： root = [3,9,20,null,null,15,7]
输出： [[3],[9,20],[15,7]]

示例 2：

输入： root = [1]
输出： [[1]]

示例 3：

输入： root = []
输出： []

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

方法一：BFS

思路

我们可以用广度优先搜索解决这个问题。

首先根元素入队
当队列不为空的时候
- 求当前队列的长度 si
- 依次从队列中取 si 个元素进行拓展，然后进入下一次迭代

上述属于优化的广度优先搜索，它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取 si 个元素。在上述过程中的第 i 次迭代就得到了二叉树的第 i 层的 si 个元素。

为什么这么做是对的呢？我们观察这个算法，可以归纳出这样的循环不变式：第 i 次迭代前，队列中的所有元素就是第 i 层的所有元素，并且按照从左向右的顺序排列。证明它的三条性质（你也可以把它理解成数学归纳法）：

初始化：i = 1 的时候，队列里面只有 root，是唯一的层数为 1 的元素，因为只有一个元素，所以也显然满足「从左向右排列」；
保持：如果 i=k 时性质成立，即第 k 轮中出队 sk 的元素是第 k 层的所有元素，并且顺序从左到右。因为对树进行广度优先搜索的时候由低 k 层的点拓展出的点一定也只能是 k + 1 层的点，并且 k + 1 层的点只能由第 k 层的点拓展到，所以由这 sk 个点能拓展到下一层所有的 sk+1 个点。又因为队列的先进先出（FIFO）特性，既然第 k 层的点的出队顺序是从左向右，那么第 k + 1 层也一定是从左向右。至此，我们已经可以通过数学归纳法证明循环不变式的正确性。
终止：因为该循环不变式是正确的，所以按照这个方法迭代之后每次迭代得到的也就是当前层的层次遍历结果。至此，我们证明了算法是正确的。

解题

Python：

class Solution(object):
	def levelOrder(self, root):
		"""
		:type root: TreeNode
		:rtype: List[List[int]]
		"""
		if not root:
			return []
		res = []
		queue = [root]
		while queue:
			# 获取当前队列的长度，这个长度相当于 当前这一层的节点个数
			size = len(queue)
			tmp = []
			# 将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
			# 如果节点的左/右子树不为空，也放入队列中
			for _ in xrange(size):
				r = queue.pop(0)
				tmp.append(r.val)
				if r.left:
					queue.append(r.left)
				if r.right:
					queue.append(r.right)
			# 将临时list加入最终返回结果中
			res.append(tmp)
		return res

Java：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}

方法二：DFS

思路

用广度优先处理是很直观的，可以想象成是一把刀横着切割了每一层，但是深度优先遍历就不那么直观了。

我们开下脑洞，把这个二叉树的样子调整一下，摆成一个田字形的样子。田字形的每一层就对应一个 list。

按照深度优先的处理顺序，会先访问节点 1，再访问节点 2，接着是节点 3。之后是第二列的 4 和 5，最后是第三列的 6。

每次递归的时候都需要带一个 index(表示当前的层数)，也就对应那个田字格子中的第几行，如果当前行对应的 list 不存在，就加入一个空 list 进去。

动态演示如下：

解题

Python：

class Solution(object):
	def levelOrder(self, root):
		"""
		:type root: TreeNode
		:rtype: List[List[int]]
		"""
		if not root:
			return []
		res = []
		def dfs(index,r):
			# 假设 res 是[ [1],[2,3] ]， index 是3，就再插入一个空 list 放到 res 中
			if len(res)<index:
				res.append([])
			#  将当前节点的值加入到 res 中，index 代表当前层，假设 index 是3，节点值是99
			# res 是[ [1],[2,3] [4] ]，加入后 res 就变为 [ [1],[2,3] [4,99] ]
			res[index-1].append(r.val)
			# 递归的处理左子树，右子树，同时将层数index+1
			if r.left:
				dfs(index+1,r.left)
			if r.right:
				dfs(index+1,r.right)
		dfs(1,root)
		return res

Java：

class Solution {
	public List<List<Integer>> levelOrder(TreeNode root) {
		if(root==null) {
			return new ArrayList<List<Integer>>();
		}
		// 用来存放最终结果
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		dfs(1,root,res);
		return res;
	}
	
	void dfs(int index,TreeNode root, List<List<Integer>> res) {
		// 假设 res 是[ [1],[2,3] ]， index 是3，就再插入一个空 list 放到 res 中
		if(res.size()<index) {
			res.add(new ArrayList<Integer>());
		}
		// 将当前节点的值加入到 res 中，index 代表当前层，假设 index 是3，节点值是99
		// res 是[ [1],[2,3] [4] ]，加入后 res 就变为 [ [1],[2,3] [4,99] ]
		res.get(index-1).add(root.val);
		// 递归的处理左子树，右子树，同时将层 index+1
		if(root.left!=null) {
			dfs(index+1, root.left, res);
		}
		if(root.right!=null) {
			dfs(index+1, root.right, res);
		}
	}
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-04，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs