队列&栈-04

今天发现总结的比我学的慢，说明学的有点心急了，不慌慢慢来。

栈和深度优先搜索

与 BFS 类似，深度优先搜索（DFS）也可用于查找从根结点道目标结点的路径。

1.结点的处理顺序是什么？

在下图中，从根结点 A 开始。首先选择结点 B 的路径，并进行回溯，直到到达结点 E，无法更进一步。然后回溯到 A 并选择第二条路径到结点 C。从 C 开始，我们尝试第一条路径到 E 但是 E 已被访问过。所以我们回到 C 并尝试从另一条路径到 F。最后找到 G。

总的来说，在我们到达最深的结点之后，我们只会回溯并尝试另一条路径。

因此我们在 DFS 中找到的第一条路径不一定就是最短的路径。例如，在上面的例子中，我们成功找出了路径 A->C->F->G 并停止了 DFS。但这不是从 A 到 G 的最短路径。

2.栈的入栈和退栈顺序是什么？
如上面图示，首先将根结点推入到栈中；然后我们尝试第一个邻居 B 并将结点 B 推入到栈中；等等等等。当我们到达最深的结点 E 时，我们需要回溯。当我们回溯时，我们将从栈中弹出最深的结点，这实际上是推入到栈中的最后一个结点。

结点的处理顺序是完全相反的顺序，就像它们被添加到栈中一样，它是后进先出（LIFO）。这就是我们在 DFS 中使用栈的原因。

DFS-模版-1

在大多数情况下，我们在能使用 BFS 时也可以使用 DFS。但是有一个重要的区别：遍历顺序

与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在 DFS 中找到的第一条路径可能不是最短路径。
以下是 DFS 的递归模板(JAVA)，帮助我们更好的理解：

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
  return true if cur is target;
  for (next : each neighbor of cur) {
    if (next is not in visited) {
      add next to visted;
      return true if DFS(next, target, visited) == true;
    }
  }
  return false;
}

当我们递归地实现 DFS 时，似乎不需要使用任何栈。但实际上，我们使用的是由系统提供的隐式栈，也称为调用栈（Call Stack）

题目：岛屿数量

岛屿数量又来了，大多数情况下，能用 BFS 解决的问题，也能被 DFS 解决。问题具体见。岛屿问题

代码如下(C++):

class Solution {
  private:
  void dfs(vector<vector<char>> & grid,int r,int c){    // 深度优先算法，感觉就是个递归
    int nr = grid.size();   // 岛屿大小
    int nc = grid[0].size();

    grid[r][c] = '0';       // 将当前位置置0
    if(r-1 >=0 && grid[r-1][c] == '1') dfs(grid,r-1,c); // 判断上下左右，如果有的话，继续递归
    if(r+1 <nr && grid[r+1][c] == '1') dfs(grid,r+1,c);
    if(c-1 >=0 && grid[r][c-1] == '1') dfs(grid,r,c-1);
    if(c+1 <nc && grid[r][c+1] == '1') dfs(grid,r,c+1);
  }
public:
  int numIslands(vector<vector<char>>& grid) {
    int nr = grid.size();
    if(!nr) return 0;
    int nc = grid[0].size();

    int num_island = 0;

    for(int r = 0; r < nr; ++r){
      for(int c = 0; c < nc; ++c){
        if(grid[r][c] == '1'){
          ++num_island;     // 如果遇到 1 就 +1
          dfs(grid,r,c);    // 然后递归就完了
        }
      }
    }
    return num_island;
  }
};

题目：克隆图

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）
图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）

class Node {
  public int val;
  public List<Node> neighbors;
}

说白了，看了半天没懂，大概意思就是说？？？拷贝一个图？参考了别人的代码，自己还是没理解。等再看看。
感觉拿着 dfs 框架套上去就行了。

代码如下(C++):

class Solution {
public:
  Node* cloneGraph(Node* node) {
    unordered_map<Node*,Node*> mp;  // 无序图
    return dfs(node,mp);            // 直接深度遍历，克隆
  }

  Node* dfs(Node* node,unordered_map<Node*,Node*> &mp){
    if(!node) return NULL;
    if(mp.count(node)) return mp[node];
    Node* tmp = new Node(node -> val);
    mp[node] = tmp;
    for(Node* neighbor: node -> neighbors){
      tmp -> neighbors.push_back(dfs(neighbor,mp));
    }
    return tmp;
  }
};

目标和

给定一个非负整数数组，a1,a2,…,an,和一个目标数 S。现在你有两个符号+和-。对于数组中的任意一个整数，你都可以从+或-中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。

提示：

数组非空，且长度不会超过 20
初始的数组的和不会超过 1000
保证返回的最终结果能被 32 位整数存下

使用递归，枚举出所有可能的情况。具体地，当我们处理到第 i 个数时，我们可以将它添加+或-，递归地搜索这两种情况。当我们处理完所有的 N 个数时，我们计算出所有数的和，并判断是否等于 S。

代码如下(C++):

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        return dfs(nums,S,0);   // 深度优先搜索，枚举出所有结果。
    }
    int dfs(vector<int> &nums,uint target,int left){
        if(target == 0 && left == nums.size()) return 1;    // 目标为0并且遍历完了，返回一种方式
        if(left >= nums.size()) return 0;       // left大于数组长度，说明都遍历完了，但结果不对，返回0
        int ans = 0;
        ans += dfs(nums,target-nums[left],left+1);    // 给第一个数添加减号，然后递归
        ans += dfs(nums,target+nums[left],left+1);    // 给第一个数添加加号，然后递归
        return ans;   // 得到所有方法
    }
};

DFS-模版-2

递归解决方案的优点是它更容易实现。但是，存在一个很大的缺点：如果递归的深度太高，你将遭受堆栈溢出。在这种情况下，您可能会希望使用 BFS，或使用显式栈实现 DFS。

模版(JAVA)：

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> s;
    add root to s;
    while (s is not empty) {
        Node cur = the top element in s;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to s;
                add next to visited;
            }
        }
        remove cur from s;
    }
    return false;
}

该逻辑与递归解决方案完全相同。但使用了 while 循环和栈来模拟递归期间的系统调用栈。

二叉树的中序遍历

给定一个二叉树，返回它的中序遍历。

首先得知道什么是中序遍历：

二叉树的遍历方式有前序，中序，后序，层序
前序遍历：先访问根节点，然后左子树，然后右子树
中序遍历：先访问左子树，然后根节点，然后右子树
后序遍历：先访问左子树，然后右子树，然后根节点
层序遍历：把一棵树从上到下，从左到右依次写出来

接下来就好理解了，左根右，递归。

代码如下(C++)：

class Solution {
public:
    vector<int> ans;        // 输出
    vector<int> inorderTraversal(TreeNode* root) {
        if(root != NULL){   // 如果有根
            inorderTraversal(root -> left);     // 根的左
            ans.push_back(root -> val);         // 根的值
            inorderTraversal(root -> right);    // 根的右
        }
        return ans;             // 这玩意吧，拿纸画一下就行。开始我也不懂，画着画着就懂了。
    }
};

声明：本文为学习记录，参考之处较多，如果有侵权内容，请联系我立即删除。

BTW: 端午节快乐～