LEETCODE 1010. Pairs of Songs With Total Durations Divisible by 60 解题思路分析

题目大意:

总持续时间可被 60 整除的歌曲

在歌曲列表中,第 i 首歌曲的持续时间为 time[i] 秒。

返回其总持续时间(以秒为单位)可被 60 整除的歌曲对的数量。形式上,我们希望索引的数字  i < j 且有 (time[i] + time[j]) % 60 == 0。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE常见算法之二分查找超详细白话讲解

说起二分查找(Binary Search),我想大家都不会陌生,该算法在理解上不存在任何难度,但在刷题过程中,即使很简单的二分查找题目,经常会花费大量时间来调试边界条件,因此,本篇文章我们着重总结一下所有二分查找的边界问题。

首先来看下常见的二分查找题型:

  1. 基础版本:查找数组中某个数值的下标。
  2. 查找第一个大于等于(小于等于)某个数的下标
  3. 查找第一个大于(小于)某个数的下标

接下来,我们逐一来分析。


一. 基础版本:查找数组中某个数值的下标。

这种类型的二分查找是最为简单的,通常用于判断一个已排序好的数组中是否存在某个target数值问题。模板如下:

public int binarySearch(int[] a, int target) {
	int low = 0;
	int high = a.length - 1;
	int mid = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		if (target == a[mid]) {
			return mid;
		} else if (target < a[mid]) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	return -1;
}

这是最为基础的一种写法,当mid值等于target时,直接返回mid。当mid小于target时,我们要增加区间内的取值,因此,令low等于mid加一,反之令high等于mid减一。


二. 查找第一个大于等于某个数的下标

这个查找就变得稍微复杂一些。因为大于等于target的数值可能存在多个,这时我们必须找到第一个大于等于target的数值。相应的,代码会做出两处改变:

public int firstGreatOrEqual(int[] a, int target) {
	int low = 0;
	int high = a.length - 1;
	int mid = 0;
	while (low <= high) {
		mid = (low + high) / 2;
                // 这里大于和等于属于同一种情况
		if (a[mid] >= target) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
        // 返回值要做越界判断
	return low < a.length ? low : -1;
}

原则上,当mid大于等于target时,我们向左半区继续查找,反之向右半区查找。因为是求解大于等于target的数值,因此区间下限low是可能的返回结果。

二分查找的终止条件是当low大于high的时刻,因此终止前最后一步的状态一定是low与high两个指针重合的时刻,此时,mid实际上等于low,也等于high。如果mid指向的数值大于等于target时,high会减一,而low不变,此时low就是最终结果。反之,如果mid指向的数值小于target时,high不变,low会加一,理论上low应该是返回结果,但是low在加一操作后可能会出现越界,因此,当越界时,说明没有找到target值,这时应该返回-1.


三. 查找第一个小于等于某个数的下标

这与第二种二分查找的思路没有任何区别,你能尝试着自己写出来吗?看下代码:

public int firstSmallOrEqual(int[] a, int target) {
	int low = 0;
	int high = a.length - 1;
	int mid = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		if (a[mid] <= target) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return high >=0 ? high : -1;
}

我们求解的是小于等于某个数的下标 ,因此你要明确知道最终的high值是可能的返回结果。本题,小于与等于两个条件属于同一种情况,而最后的返回值high,要看他的坐标是否大于等于0,如果是,返回high,否则,说明数组中所有数字均大于target,返回-1。


四. 查找第一个大于某个数的下标

有了上面的基础,再看到这里,你应该会很快想出逻辑了吧?其实不难发现,我们要做的就是如何给大于,小于和等于三个条件分组,本题是求第一个大于某个数的下标,因此大于是一种分支,而小于和等于属于另一个分支:

public int firstGreat(int[] a, int target) {
	int low = 0;
	int high = a.length - 1;
	int mid = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		if (a[mid] > target) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	return low < a.length ? low : -1;
}

五. 查找第一个小于某个数的下标

不再废话,直接上代码:

public int firstSmall(int[] a, int target) {
	int low = 0;
	int high = a.length - 1;
	int mid = 0;
	while (low <= high) {
		mid = (low + high) / 2;
		if (a[mid] < target) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return high >=0 ? high : -1;
}

阶段总结:

我们不难发现,当列举出所有的二分查找场景之后,边界条件的判断变得清晰明确。我们总结一下:

  1. 无论什么情况下,二分查找的循环条件都是low<=high
  2. 当mid指向的值大于或者大于等于target时,我们需要减小mid,二分区间应变为low到mid-1,反之,二分区间变为mid+1到high。
  3. 当求某个特定值target的位置时,判断条件存在大于,等于,小于三个分支。若求大于等于某个target,或者小于某个target时,大于和等于属于一个分支,小于属于另一个分支。若求小于等于某个target,或者大于某个target时,小于和等于属于一个分支,而大于属于另一个分支。
  4. 当求某个特定值target的位置时,mid是最终解。当求大于或者大于等于target时,low是最终解,求小于或者小于等于target时,high是最终解。另外注意high与low超出数组边界时,代表没有找到符合条件的元素。

如果你对以上的总结仍然感到难以理解,你需要使用debug功能去一点一点的理解它的精髓。或者你可以直接记住上述逻辑,方便在编程时使用。


二分查找在Leetcode解题时的实际应用

当遇到题目时,如果你能够快速反应出该题的解题方式是二分查找的话,那么你将发现题目毫无难度。而关键问题在于很多题目你可能一上来无法想到要使用二分来解题。我们来看一道例题:

LEETCODE 69. Sqrt(x)

x 的平方根

实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x 是非负整数。由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

这就是一道经典的二分查找算法的使用场景。我们发现,题目不会明确的告诉你,要在一个递增数组中查找大于或者小于某个target的值,这需要我们自己来分析得出。如果将本题翻译成为二分查找思想的话,我们可以理解为,题目求的是,在1到x之间,找到一个数字n,保证n的平方是第一个小于等于x的数字。这样一来,你是否想到解法了呢?看下代码:

public int mySqrt(int x) {
    if(x<=1) return x;
    long low=1,high=x;
    while(low<=high){
        long mid=(low+high)/2;
        long n=mid*mid;
        if(n<=x){
            low=mid+1;
        }else{
            high=mid-1;
        }
    }
    return high>=0?(int)high:-1;
}

上述代码就是标准的第三类二分查找题型。

我们再举一个复杂一些的例子,比如我们给定了一个升序排序好的数组arr,求其中某个数字出现的次数。

这道题目要使用到多种二分查找的组合来解题。

  1. 首先我们使用第一类二分方法,返回数组中等于target值的任意下标,如果返回值为-1,说明数组中不存该值。否则数组中存在target。
  2. 找到第一个大于等于target的下标start。
  3. 找到第一个小于等于target的下标end。
  4. start到end区间即是target所在的范围。

总结:

本篇文章,我们重点分析总结了二分查找的边界问题,希望对你今后的解题能够提供帮助。

发表在 leetcode | 标签为 , , , | 一条评论

LEETCODE 1351. Count Negative Numbers in a Sorted Matrix 解题思路分析

题目大意:

统计有序矩阵中的负数

给你一个 m * n 的矩阵 grid,矩阵中的元素无论是按行还是按列,都以非递增顺序排列。 

请你统计并返回 grid 中 负数 的数目。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE 1352. Product of the Last K Numbers 解题思路分析

题目大意:

最后 K 个数的乘积

请你实现一个「数字乘积类」ProductOfNumbers,要求支持下述两种方法:

add(int num)

  • 将数字 num 添加到当前数字列表的最后面。

getProduct(int k)

  • 返回当前数字列表中,最后 k 个数字的乘积。
  • 你可以假设当前列表中始终 至少 包含 k 个数字。

题目数据保证:任何时候,任一连续数字序列的乘积都在 32-bit 整数范围内,不会溢出。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE 1353. Maximum Number of Events That Can Be Attended 解题思路分析

题目大意:

最多可以参加的会议数目

给你一个数组 events,其中 events[i] = [startDayi, endDayi] ,表示会议 i 开始于 startDayi ,结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意,一天只能参加一个会议。

请你返回你可以参加的 最大 会议数目。

继续阅读
发表在 leetcode | 标签为 , , , , , | 留下评论

LEETCODE 1354. Construct Target Array With Multiple Sums 解题思路分析

题目大意:

多次求和构造目标数组

给你一个整数数组 target 。一开始,你有一个数组 A ,它的所有元素均为 1 ,你可以执行以下操作:

  • 令 x 为你数组里所有元素的和
  • 选择满足 0 <= i < target.size 的任意下标 i ,并让 A 数组里下标为 i 处的值为 x 。
  • 你可以重复该过程任意次

如果能从 A 开始构造出目标数组 target ,请你返回 True ,否则返回 False 。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE常见算法之广度优先搜索BFS超详细白话讲解

前一篇的算法讲解中我们一起深入了解了深度优先搜索DFS在解题时的应用场景,本篇文章我们将一起探讨一下DFS的亲兄弟BFS算法。

bfs是 breadth first search 的英文缩写,中文名称为广度优先搜索。无论是bfs还是之前讲过的dfs,他们都是快速遍历节点的算法代表,相比于dfs以路径遍历所有节点而言,bfs则是采用逐层遍历的方式,从近到远逐渐覆盖整个区域。还记得我们曾经讲过的dfs的使用场景吗?实际上bfs的使用场景与dfs非常相似,我们一起来看:

  • 遍历树结构
  • 遍历图结构
  • 遍历二维数组

接下来我们使用一道二叉树的例子来做说明。这也是我们讲解dfs时用过的题目。


例:层数最深叶子节点的和

给你一棵二叉树,请你返回层数最深的叶子节点的和。

输入:root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
输出:15

原题链接:


如果看过我之前文章的话,你应该还记得dfs的解题方法吧!我们先求出最深层的层数,然后再dfs遍历二叉树中所有从根节点出发到每个叶子节点的路径,如果叶子节点的层数是最深层,我们就将其节点的数值累加至返回结果。

对于解二叉树的题目,bfs也是很好的选择之一,我们接下来来看下bfs的核心思想。上文提到过,bfs是以逐层遍历节点的方式来运行的,那么什么是层的概念?我们还是通过上面的二叉树来做个简单的说明,看下图:

其实层的概念并不难理解,处于同一水平线上的所有点都是同一层的节点,bfs的起点依旧是根节点,我们定义根节点的层数为1(定义为0也可以,看你喜好),那么第一层只有一个根节点1,而第二层有2,3两个节点,同理第三层存在4,5,6这三个节点。最后一层是7和8两个节点。按照层遍历即是从上到下,每次遍历一层中的所有节点,同时记录下该层节点所有的下层子节点,然后再遍历下一层子节点,直到遍历到最后一层为止。这就是bfs的核心遍历逻辑。

如果你觉得bfs的思想很简单,那我们再举个复杂一些的例子,看下图:

上图是一个矩阵,矩阵内存在一个红色区域,请你使用上面讲过的bfs思路,求出红色区域距离矩阵边缘的最短距离。

我们用肉眼很容易看出答案是3,如果使用bfs的话,我们该如何做,矩阵中哪个点是bfs的起点呢?因为是求红色区域距离边缘的最短距离,因此整个红色区域都是bfs的起点,它的下一层是距离红色区域1格的所有点,如下图黄色区域:

黄色区域即是我们bfs迈出的第一步,如果红色区域被定义为第一层的话,那么黄色区域就是bfs的第二层。接下来,你应该能够想到第三层的样子了吧?看下图蓝色区域:

同理,我们再画出第四层,如下图黑色区域:

我们发现,bfs到第四层时,已经存在接触到边缘的格子了,也就是说我们通过3次bfs从红色区域到达了矩阵的边缘,因此,红色区域与边缘的最小距离为3。

看到这里,我想你已经对bfs的思想非常了解,接下来该轮到代码出场了!bfs写法实际上已经有了非常规范的模板,我们来详细介绍一下。与dfs的递归方式不同,bfs采用Queue的方式存储每一层的节点,然后在必要的时候还会使用访问数组来记录已经遍历过的节点,避免重复遍历相同区域。

先看下Queue的使用,首先我们需要将bfs起始节点都加入到Queue中,比如二叉树的根节点,或者矩阵中红色区域的所有节点。这一步我们称之为对bfs进行初始化。初始化操作结束后开始进入bfs操作。首先我们需要确定当前Queue中元素个数size,接下来,我们循环size次,每次从Queue中取出一个节点元素,并且将该节点元素的子节点(根据题目也可能是下一个节点,比如矩阵当前位置的相邻元素)添加到Queue中,循环完size次之后,说明我们已经取出了所有初始化操作时添加进Queue的起始节点,当前Queue中剩余的节点元素应该都是起始节点的子节点。到此为止,我们可以记录当下进行了一步bfs操作。接下来,再次取得当前Queue中元素个数size,并且再循环size次,从Queue中取出size个元素,并将它们的子节点加入到Queue,重复上述步骤,直到遇见终止条件(例如到达矩阵边缘)或者Queue的size为0(例如到达二叉树最深层叶子节点,没有更多子节点)为止。

我们将上面的文字用代码来展示一下,代码以二叉树的题目为例:

public int bfs(TreeNode root) {
    // 定义bfs用的Queue
    Queue<TreeNode> q = new LinkedList<>();
    // 初始化bfs,将起始节点根节点加入Queue
    q.offer(root);
    // 如果Queue不为空,一直循环
    while(q.size()>0){
        // 取得当前Queue中元素个数
        int size=q.size();
        // 当前行的元素和
        int sum = 0;
        // 遍历当前行的所有元素(循环size次)
        while(size>0){
            // 从Queue中取出一个节点元素
            TreeNode n =q.poll();
            // 当前行元素个数减一
            size--;
            // 当前元素的值累加至sum
            sum+=n.val;
            // 如果左子节点不为空,添加至Queue
            if(n.left!=null) q.offer(n.left);
            // 如果右子节点不为空,添加至Queue
            if(n.right!=null) q.offer(n.right);
        }
        // 如果Queue为空,说明已到最深层,终止bfs,返回当前层的sum
        if(q.size()==0) return sum;
    }
    return 0;
}

上述就是bfs的模板代码,根据不同的题目,你需要对上述模板进行少许修正,再举一个例子,比如我们使用bfs来求解二叉树的最深层层数,代码应该变为:

public int bfs(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int deep=0; // 二叉树层数
    while(q.size()>0){
        int size=q.size();
        // bfs循环当前层
        while(size>0){
            TreeNode n =q.poll();
            size--;
            if(n.left!=null) q.offer(n.left);
            if(n.right!=null) q.offer(n.right);
        } // bfs当前层结束
        deep++; // 层数加一
    }
    return deep;
}

接下来我们再看访问数组的使用方法,其实关于访问数组,我们在dfs算法的讲解中已经很详细的介绍过,定义访问数组的目的是为了记录已经遍历过的节点,避免重复遍历,而二叉树问题中不需要设置访问数组的原因在于,二叉树遍历都是向下遍历,不会出现同一节点被遍历到2次的情况。而数组或者图形结构的题目就不同,比如上面矩阵那个例子中,如果我们不使用记忆数组的话,我们就很难保证每次dfs都只向外圈扩散一格。如果大家对访问数组或是dfs算法不太了解,建议你在理解完本篇bfs算法之后,参考一下LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(上)这篇文章。

进阶思考:

本文到此为止,实际上已经大致介绍完bfs的相关知识。不过如果你想对广度优先搜索进行进一步的了解,你需要考虑如下2个问题:

  1. bfs最擅长解决哪一类问题?
  2. bfs与dfs的效率哪个更好?

首先,bfs最擅长解决哪一类问题?我们知道,bfs是按照层来遍历节点的,也就是说他会从第一层遍历到第n层,这样一来,如果题目求某个条件下的最短路径时,他就可以最大限度的发挥出优势,比如矩阵那个例子中,最短路径为3,其实我们只需要bfs到第三层就可以得出答案,大于第三层额所有节点我们都无需考虑。如果改用dfs的话,我们不遍历完所有路径,是无法确定哪一条路径最短的。

另外,关于dfs与bfs的效率问题,只能说他们各有千秋,dfs在配合记忆数组的前提下与bfs的解题效率几乎没有差别,如果都是遍历所有节点的前提下,两者的时间复杂度均为O(n),n为总节点数量。而在二叉树遍历上,由于不会使用到记忆数组,虽然两者的时间复杂度相同,但dfs不需要使用到额外的存储空间(Queue),他在执行速度与空间复杂度上都会优于bfs(本题使用bfs解上述二叉树问题只是为了让大家理解广度优先搜索的算法而已)。总而言之,当遇到二叉树,图型题目(某些矩阵题目)的时候,你应该首先想到使用dfs或者bfs,知道了这一点,你就已经战胜大部分竞争者了。对于具体使用哪一种算法,这是你需要自己去体会总结的,最后祝大家刷题愉快!面试顺利。

bfs相关题目讲解: https://leetcode.jp/tag/bfs/

发表在 leetcode | 标签为 , , , , | 留下评论

LEETCODE 386. Lexicographical Numbers 解题思路分析

题目大意:

字典序排数

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如,

给定 n =1 3,返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE 588. Design In-Memory File System 解题思路分析

题目大意:

设计内存文件系统

设计一个内存文件系统,模拟以下功能:

ls: 以字符串的格式输入一个路径。如果它是一个文件的路径,那么函数返回一个列表,仅包含这个文件的名字。如果它是一个文件夹的的路径,那么返回该 文件夹内 的所有文件和子文件夹的名字。你的返回结果(包括文件和子文件夹)应该按字典序排列。

mkdir:输入一个当前不存在的 文件夹路径 ,你需要根据路径名创建一个新的文件夹。如果有上层文件夹路径不存在,那么你也应该将它们全部创建。这个函数的返回类型为 void 。

addContentToFile: 输入字符串形式的 文件路径 和 文件内容 。如果文件不存在,你需要创建包含给定文件内容的文件。如果文件已经存在,那么你需要将给定的文件内容 追加 在原本内容的后面。这个函数的返回类型为 void 。

readContentFromFile: 输入 文件路径 ,以字符串形式返回该文件的 内容 。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(下)

接上文:LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(上)

上一篇文章中,我们使用一道二叉树问题讨论了DFS算法在LEETCODE解题时的应用。本文,我们尝试挑战更复杂一点的题目,来看下深度优先搜索是如何解决某些矩阵难题的。

例2:


矩阵中的最长递增路径

给定一个整数矩阵,找出最长递增路径的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。

示例:

输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]

题目链接:


选择这道矩阵例题的原因是想区别于上篇文章讲过的二叉树问题,解题前,我们有必要讨论一下两道题的区别所在,这对于我们之后做题会有很大的帮助。如果你只是想快速查看本题的实现代码,那么我认为本篇文章并不适合于你,因为我们的初衷是想让大家充分理解DFS算法的应用,能够做到融会贯通,举一反三,这样再遇到类似问题时,能够快速想到使用DFS的解题方案。

本题是一道矩阵题目,其实矩阵也可以看做是多个节点构成的图形结构,矩阵上每一个点可以想象成为一个节点,当前节点能够走到的下一个点都是当前节点的子节点。相比于二叉树,它们之间具有如下区别:

  1. 题目给出了矩阵上每一点的值,而二叉树问题我们开始只能看到根节点。
  2. 二叉树在进行DFS递归时,最多只存在2个子节点分叉,而本题,矩阵上的每一点最多可以向四个方向进发,也就是说会出现4个分叉(有些更复杂的题目会出现更多的分叉)。
  3. 二叉树上的每一个点虽然存在0-2个子节点,但它的上一层父节点只有一个。而在矩阵中的每个点,不仅存在多个子节点,还有可能存在多个父节点(从多个节点到达当前节点)。
  4. 二叉树的每条路径不存在回路,但矩阵上每个点都可以向四个方向进发,这样一定会出现回路。

除了以上区别之外,本题还有另外一个特殊性,题目中没有给出dfs路径的起点和终点。还记得二叉树的例子吗?它的起点是根节点,终点是层数最大的叶子节点。但对于本题,dfs的起点与终点都有可能是矩阵上的任意一点。这就是本题的复杂之处,不过万变不离其宗,随着你对dfs题目理解的加深,上述问题都不是问题。

其实上面啰嗦了这么多的区别,总结成一句话就是,本题的矩阵问题相比于二叉树问题的路径会变得更多并且更复杂!首先,我们要明白一点,每个点上的分叉数量并不是本题复杂的关键所在!我们来复习一下上篇文章给出的dfs递归函数的模板代码:

void dfs(Node node){
    // 遇到叶子节点,递归终止
    if(node.left==null&&node.right==null) return;
    // 如果存在左子节点,dfs至左子节点
    if(node.left!=null) dfs(node.left);
    // 如果存在右子节点,dfs至右子节点
    if(node.right!=null) dfs(node.right);
}

虽然代码中是按照二叉树模板来写的,不过换成矩阵也大同小异,抛开递归终止条件先不提,变化的地方实际上只有子节点的数量而已,二叉树问题我们只是dfs递归了左右2个子节点,而本题不过是增加到4个而已,甚至说即使有1亿个子节点,我们都不畏惧,没有一个循环解决不了的事情。那么本题的难点在哪里呢?答案是回路!回路的定义很简单,即一条dfs路线上出现了圈,比如下图,我们随便在矩阵上画一条线路:

上图中S为DFS路径起点,红色格子代表了该路线,而箭头是该路线的行进方向。我们看到,最终路线的终点与自身的路径相交,这时就产生了回路。回路(交点)的产生,会导致我们的DFS路线无休止的循环下去,因此我们在这类问题中必须要考虑的一件事情即是如何处理回路。这也是DFS解题中经常遇到的问题。解决这个问题的常规做法是使用访问数组,访问数组通常是boolean型:

boolean[][] visited = new boolean[][];

其中visited[row][col],代表第row行第col列这个点是否已经访问过。当遇到已经访问过的点时,我们是没有必要再次访问的,因为该点在之前上层的dfs时(当前路线更早经过改点时)已经处理过,再次处理该点属于重复计算,因此当前dfs路线可以停止。换句话说,当遇到已经访问过的点时,是dfs递归的一个终止条件。我们将目前为止的叙述用代码来描述一下:

void dfs(int row, int col){
    // 遇到访问过的点,递归终止
    if(visited[row][col]) return;
    // 将当前点设置为已访问
    visited[row][col]=true;
    if(row+1<matrix.length){ // 如果下方没越界
        dfs(row+1, col); // 向下移动一格
    }
    if(row-1>=0){ // 如果上方没越界
        dfs(row-1, col); // 向上移动一格
    }
    if(col+1<matrix[0].length){ // 如果右方没越界
        dfs(row, col+1); // 向右移动一格
    }
    if(col-1>=0){ // 如果左方没越界
        dfs(row, col-1); // 向左移动一格
    }
}

上面的代码很容易理解,它与二叉树的写法大同小异,只是分叉的路线变成了4条,并且递归终止条件变成了已访问过的节点。为了复习上面的内容,这里给大家出两道小问题,可以自行思考一下:


小测验1:如果每一点的前进方向可以是上下左右,左上,左下,右上,右下八个方向时,你应该如何改进上述代码?

小测验2:如果每一点的前进方向是其所在行的下一行的所有点,你应该如何改进上述代码?


我们更进一步来思考一下dfs,对于本题,每一个点都会最多分叉出4条路径,因此,无论从任何一点出发,我们都可以dfs遍历到矩阵上的每一个点。另外,也会存在一条路径就能覆盖整个矩阵上所有点的情况,并且这种路径不仅仅存在一条。

难点还没有结束,我们接着向下分析。对于同一起点出发的不同路线,不论他们的长度或是终点是否相同,我们都认为他们不是同一条dfs路径(除非起点终点以及中间点都相同)。比如:

上图中红色路径以及黄色路径均是从S出发,蓝色区域代表了两条路径的相交点。虽然起点相同,但这两条路径明显不是同一路径。这时问题来了,我们在dfs红色路径时,已经将当前路径上的点都标记为已访问状态,那么当dfs黄色路径时,遇到红色路径已访问状态的点(蓝色节点)时是否应该结束递归呢?答案显然是不应该,如果结束的话,黄色路径就不能走到更远的目的地,但是当遇到黄色路线自身已访问过的节点(节点3,0)时,显然又必须结束递归。对于这个问题该如何解决?这就是我们接下来要讨论的话题,访问数组中访问状态的还原。

简单来说,访问数组存在的目的在于避免回路的出现,回路是针对某一条路径来说的,对于多条不同路径相交时,这并不能称之为回路。换句话说,访问数组中的已访问状态只对当前路径有效,在当前路径dfs结束之后,我们应该清除该路径上所有点的已访问状态,以便于不影响其他路径。清除当前路径上所有点的已访问状态,听起来是很复杂的操作,这在代码上该如何写?其实很简单,我们先看实现代码,代码依然在上面的模板基础上做出修改:

void dfs(int row, int col){
    // 遇到访问过的点,递归终止
    if(visited[row][col]) return;
    // 将当前点设置为已访问
    visited[row][col]=true;
    if(row+1<matrix.length){ // 如果下方没越界
        dfs(row+1, col); // 向下移动一格
    }
    if(row-1>=0){ // 如果上方没越界
        dfs(row-1, col); // 向上移动一格
    }
    if(col+1<matrix[0].length){ // 如果右方没越界
        dfs(row, col+1); // 向右移动一格
    }
    if(col-1>=0){ // 如果左方没越界
        dfs(row, col-1); // 向左移动一格
    }
    // 还原当前点的访问状态,设置为未访问
    visited[row][col]=false; // 添加这一行即可
}

上面的代码只在最后加了一行就解决了上面的问题。这里我们思考一下,为什么在这里添加这一行代码。首先代码走到最后一行时,意味着当前点向四个方向的分叉dfs递归都已经跑完,也就是说从当前点分叉出的所有路径都遍历结束,这时,当前递归结束,接下来会返回上层递归,上层dfs递归中任何其他三个方向分叉出的路径再次经过当前点时,都不在属于当前路径,也就是与当前路径不是同一条路径,这时,为了不影响其他路径的前进,我们需要在此时将访问状态还原。再换句话说,我们判断回路,可以理解为从经过某一点出发的路径再次回到该点的时刻,而未经过当前点出发的其他路径经过当前点时是不会发生回路的。因此,当从当前点之前出发的其他路径经过当前点时,我们不能影响到其他路径的前进,进而在该处应该清除访问状态。

对于这部分逻辑你可能会感觉很难理解,这需要你慢慢消化,我只能尽可能用我所理解的范畴为你作出解释,这需要大量做题来实践才能慢慢掌握。不过以上写法都是模板套路,即使你还不能完全掌握精髓,至少你要会学照猫画虎。

讲了这么多,我们该回到题目本身了。题目要求找最长递增路径的长度,那么我们需要考虑如下几点:

  1. 由于起点不确定,因此我们需要以每一个点为起点做dfs路径搜索。
  2. dfs递归时,我们向4个方向前进时,要判断下一个点的值是否要大于当前点,只有符合条件的方向才能继续向下dfs。
  3. 记忆数组。

对于前两个问题应该不难解决,而第三个问题你是否想到了答案呢?看到记忆数组几个字你想到了什么?还记得我们在之前文章讲过的动态规划算法吗?

LEETCODE常见算法之动态规划DP超详细白话讲解(上)

如果你还没看过之前的算法讲解也不要紧,我们在这里再次啰嗦几句。记忆数组的存在是为了减少不必要的重复计算,也许你还没意识到dfs中大量重复计算的存在。我们举例来说明。比如本题,我们通过某一条dfs路径得知了从节点X出发能够得到的最长递增路径,那么当我们再次从另外起点走到X点时,我们就没必要继续dfs下去,直接使用之前计算得出的结果返回即可,这样可以大幅减少递归次数,来达到提高代码效率的作用。如果你对记忆数组还是不能理解,强烈建议去看下上面链接中的文章。

分析到这里,如果你已经完全理解了上文的精髓,我想本题的解法你也大致有了思路。并且对于其他dfs题目,你也应该有自信去尝试解题。本文开头我们已经说过,本篇文章的初衷并非仅仅教会大家本题的解法,而是想让大家明白dfs的核心使用方法,从而到达触类旁通的目的,因此,关于本题的详细实现代码本文就不再阐述,可以作为习题让大家作为练习。如果你还不能写出代码,可以参考我对本题的详细分析:

LEETCODE 329. Longest Increasing Path in a Matrix 解题思路分析


总结:

我们使用了2篇文章的两个例子来介绍DFS算法在解题时的应用,无论是dfs二叉树还是二维数组,其原理的核心都是递归,不同之处在于二维数组在dfs时会出现回路,并且会出现重复计算问题。今后在做题或者面试时,如果我们想使用dfs递归思路来解题,应下意识的要考虑到题目中是否存在重复计算,当存在时千万不要忘记使用记忆数组来保存已经计算过的解。

最后我想我有必要再次解释一下,二叉树那道题目不需要使用记忆数组的原因。我们知道二叉树在分叉之后的所有路线是不会再次相交的,不出现相交也就是说不会再次出现同一个点的重复遍历,这也就是意味着任何分叉出来的路径上的每一点都是还没有遇到过的节点,这也就不存在重复计算的问题。而反观矩阵,分叉出的路径大概率会与其他路径再次相交,相交点之后的所有路径其实是完全相同的,这时我们就没有必要再次做重复劳动了。

最后的最后,我想再说句题外话,我在动态规划算法的讲解中提到过,所有DP题目都可以使用递归加记忆数组来解决,而DFS恰巧就是递归加记忆数组,因此,在我理解来看,DP与某些DFS实际上可以理解为同一类题型(二叉树这种不用记忆数组的除外)。在你刷了足够多的的题目之后,你会发现很多算法实际上是相通的,天下武功,唯快不破,而天下算法,为懂则不难,祝大家刷题愉快,面试成功!

链接:本博客介绍过的所有dfs题目 https://leetcode.jp/tag/dfs/

发表在 leetcode | 标签为 , , , , | 一条评论