一、什么是深度优先遍历（DFS）
以“深度”为第一关键词，每次都沿路径到不能再前进时，才退回到最近的岔路口，然后继续按同样的逻辑搜索。
二、题目与解答
题目：
Leetcode 695. 岛屿的最大面积
解答思路：
首先要遍历数组，当发现（i,j）对应为陆地时，进行如下步骤：
（1）递归解法
递归解法最重要的是首先要确定递归边界。（设计递归函数时，我们必须为它设置一个结束递归的“出口”，否则函数会一直调用自身（死循环），直至运行崩溃。）
该题有两个递归边界：
一个是矩阵尺寸限制，
一个是碰到了水域
一般来说，深度优先搜索类型的题可以分为主函数和辅函数，
主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果可以即在辅函数进行搜索。
辅函数则负责深度优先搜索的递归调用
本题中主函数为：int maxAreaOfIsland(vector<vector<int>>& grid);
辅函数为：int LandDFS(vector<vector<int>>& grid, int i, int j); 其中i, j 代表当前坐标。
class Solution {
public:
// 辅函数
int LandDFS(vector<vector<int>>& grid, int i, int j)
{
// 在矩阵尺寸范围内
if((i < grid.size()) && (i >= 0) && (j < grid[0].size()) && (j >= 0)) {
if (grid[i][j] == 0) { // 碰到水
return 0;
}
else {
grid[i][j] = 0;
return 1 + LandDFS(grid, i-1, j) + LandDFS(grid, i+1, j) +
LandDFS(grid, i, j-1) + LandDFS(grid, i, j+1);
}
}
else {
return 0;
}
}
// 主函数
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
ans = max(ans, LandDFS(grid, i, j)); // 这里LandDFS(grid, i, j)返回的是含(i,j)的岛屿的面积
}
}
return ans;
}
};
（2）栈解法
我们也可以使用栈（stack）实现深度优先搜索，但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时推荐使用递归式写法，同时也方便进行回溯（见下节）。
不过在实际工程上，直接使用栈可能才是最好的选择，一是因为便于理解，二是更不易出现递归栈满的情况。
class Solution {
private:
vector<int> direction {-1, 0, 1, 0, -1}; // 每相邻两位即为上下左右四个方向之一
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int localArea, area = 0, x, y;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j]) { // 进入岛屿
localArea = 1;
grid[i][j] = 0; // 抹除
stack<pair<int, int>> IsLand; // 存放土地的堆栈
IsLand.push({i, j}); // 往堆中加入当前土地（该岛第一块土地）
while (!IsLand.empty()) {
auto [r, c] = IsLand.top(); // 从堆中取出元素，并访问
IsLand.pop(); // 从堆中取出元素，并访问
for (int k = 0; k < 4; k++) { // 上下左右
x = r + direction[k];
y = c + direction[k+1];
if ( x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
++localArea;
grid[x][y] = 0;
IsLand.push({x, y}); // 往堆中加入当前土地 ( (i,j)土地的领接土地节点 )
}
}
}
}
area = max(area, localArea);
}
}
return area;
}
};
参考视频：
https://leetcode.cn/problems/max-area-of-island/solution/dao-yu-de-zui-da-mian-ji-by-leetcode-solution/
在以下示例中，我无法理解Ruby运算符的优先级:x=1&&y=2由于&&的优先级高于=，我的理解是类似于+和*运算符:1+2*3+4解析为1+(2*3)+4它应该等于:x=(1&&y)=2但是，所有Ruby源代码(包括内部语法解析器Ripper)都将其解析为x=(1&&(y=2))为什么？编辑[08.01.2016]让我们关注一个子表达式:1&&y=2根据优先规则，我们应该尝试将其解析为:(1&&y)=2这没有意义，因为=需要特定的LHS(变量、常量、[]数组项等)。但是既然(1&&y)是一个正确的表达式，那么解析器应该如何处理呢？我试过咨询Ruby的parse.y，但它太像意大利面条
题目描述小张买了 n 件白色的衣服，他觉得所有衣服都是一种颜色太单调，希望对这些衣服进行染色，每次染色时，他会将某种颜色的所有衣服寄去染色厂，第 i 件衣服的邮费为 ai 元，染色厂会按照小张的要求将其中一部分衣服染成同一种任意的颜色，之后将衣服寄给小张，请问小张要将 n 件衣服染成不同颜色的最小代价是多少？输入描述第一行为一个整数 n ，表示衣服的数量。第二行包括 n 个整数a1,a2...an 表示第 i 件衣服的邮费为 ai 元。（1≤n≤10^5,1≤ai≤10^9 ）输出描述输出一个整数表示小张所要花费的最小代价。输入输出样例输入551321输出25 思考🤔：题意：意思是
1.深度优先搜索(DFS)深度优先遍历主要思路是从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成。例题P1605迷宫题目描述给定一个N×MN\timesMN×M方格的迷宫，迷宫里有TTT处障碍，障碍处不可通过。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。输入格式第一行为三个正整数N,M,TN,M,TN,M,T，分别表示迷宫的长宽和障碍总数。第二行为四个正整数SX,S
本篇讲的是常见的搜索模板，搜索题的解法时比较固定的，只要把模板记熟，加上自己找几道习题练习体会后，相信各位下次遇到这类题一定能拿下！！下面我将已典型的题目为例子介绍几种常见的搜索方式。 1.二分搜索二分搜索代码模板：例题：#includeusingnamespacestd;doublen;constdoubleeps=1e-12;//二分搜索intmain(){ intt; cin>>t; while(t--){ cin>>n; doublel=0,r=100000,res=-1; while(ln)r=mid-0.0001; elseif(mid*mid*mid二分搜索是只能对有
这里有两个测试:if[1,2,3,4].include?2&&nil.nil?puts:helloend#=>和if[1,2,3,4].include?(2)&&nil.nil?puts:helloend#=>hello上面告诉我&&比方法参数有更高的优先级，所以它逻辑上和2&&nil.nil?是真的，并将它作为参数传递给include？但是，有这个测试:if[1,2,3,4].include?2andnil.nil?puts:helloend#=>hello所以这告诉我方法参数和“and”具有相同的优先级(或者方法参数高于“and”)因为它传递了2以包含？在处理“和”之前。注意:我知
是否可以使用Amazon简单排队服务创建优先级队列？最初我找不到关于这个主题的任何内容，这就是我创建两个队列的原因。一个普通队列和一个优先队列。我正在根据我定义的规则将消息排入此队列，但在出列消息时会出现困惑。如何对队列进行长时间轮询，使我的队列组合表现得像一个优先级队列？ 最佳答案 我认为您通过创建两个队列走在正确的轨道上-一个普通队列和一个优先级队列。在这种情况下，您不一定需要长时间轮询。由于优先队列中的消息优先于普通队列中的消息，您可以采用如下方法:轮询优先级队列，直到没有更多消息为止。轮询普通队列并在普通队列中的每条消息后重
运算符优先级的一些信息来源likethis表示!、~、+、-等一元运算符具有更高优先级比赋值=。但是，以下表达式是可能的:!a=true#=>false(withwarning)a#=>true~a=1#=>-2a#=>1+a=1#=>1a#=>1-a=1#=>-1a#=>1考虑到这些结果，我能想到的唯一可能的解释是这些一元运算符的优先级低于赋值。如果是这样的话，那就意味着我上面提到的信息是错误的。哪个是正确的？有不同的解释吗？ 最佳答案 我的编程ruby书(第2版)也将一元运算符列为具有比赋值更高的优先级。一元运算符被赋予最高
我将向您展示来自rubykoans的代码片段教程。考虑下一个代码:classMyAnimalsLEGS=2classBird实际上问题在评论中(我用星号突出显示了它(尽管它打算以粗体显示))。有人可以解释一下吗？提前致谢! 最佳答案 这里有答案:Ruby:explicitscopingonaclassdefinition.但也许它不是很清楚。如果您阅读链接的文章，它将帮助您找到答案。基本上，Bird是在MyAnimals的范围内声明的，在解析常量时具有更高的优先级。Oyster位于MyAnimals命名空间中，但未在该范围内声明。将
查看下面的作业，我假设该作业在low_priority队列上运行。classGuestsCleanupJob我同意这一点，但这只是队列的名称对吗？它实际上与优先级无关。例如，如果我创建了一个队列名为:my_queue的作业，它将被视为具有与:low_priority队列相同的优先级。从文档中我无法找到任何表明我可以对排队的作业进行优先排序的信息。我知道delayed_jobs有这个功能，但我在active_job中没有找到它。 最佳答案 优先级取决于实际的QueueAdapter以及此适配器的配置方式。如果您的适配器不支持优先级或未
以前的答案answer类似question是错误的。Ruby中均未提及方法调用documentation也不在communitywiki.不带括号的方法调用高于或or似乎比没有括号的方法调用具有更低的优先级:putsfalseortrue相当于(putsfalse)ortrue并显示false。注意:我知道不应该使用or。尽管如此，这仍然是一个很好的例子，表明某些运算符的优先级确实低于方法调用。低于||putsfalse||true相当于puts(false||true)并显示true。带括号的方法调用用于方法调用的括号don'tseem进行分组:puts(falseortrue)#S