分类 深度优先搜索 下的文章

组合总和 II

问题描述

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii

思路

本题分为两步

简单的回溯算法
对未完全剪枝的ret进行去重。

去重的方法有两种，效率都比较低

  • sort(ret.begin(), ret.end());ret.erase(unique(ret.begin(), ret.end()), ret.end())
  • set<vector<int>> sets(ret.begin(), ret.end());ret=vector<vector<int>>(sets.begin(),sets.end())

题解

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ret;
    int n;

    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        n = candidates.size();
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, 0, target);
        sort(ret.begin(), ret.end());
        ret.erase(unique(ret.begin(), ret.end()), ret.end());
        return ret;
    }

    void dfs(vector<int> vec, int sum, int location, int target) {
        if (sum >= target || location == n) {
            if (sum == target) {
                ret.push_back(tmp);
            }
            return;
        }
        for (int i = location; i < n; i++) {
            tmp.push_back(vec[i]);
            sum += vec[i];
            dfs(vec, sum, i + 1, target);
            sum = sum - vec[i];
            tmp.pop_back();
        }
    }
};

岛屿数量

问题描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:
输入:
11110
11010
11000
00000

输出: 1

示例 2:
输入:
11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands

思路

最开始的时候，将所有的小岛的 访问位 置为0；
i从0到grid.size(),j从0到grid[0].size()遍历，如果vis[i][j] && grid[i][j] == '1' 将visi置为true;将其邻接位置的1的 访问位 置为0；
返回结果ans++；
最后返回ans即可。

题解

class Solution {
public:
    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, n, m, ans = 0;
    vector<vector<bool>> vis;
    bool check(int x, int y, const vector<vector<char>> &grid) {
        return x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '1' && !vis[x][y];
    }
    void dfs(int x, int y, const vector<vector<char>> &grid) {
        vis[x][y] = true;
        for (int k = 0; k < 4; k++) {
            if (check(x + next[k][0], y + next[k][1], grid)) dfs(x + next[k][0], y + next[k][1], grid);
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        n = grid.size(), m = grid[0].size();
        vis.resize(n);
        for (int i = 0; i < n; i++) vis[i].resize(m, false);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!vis[i][j] && grid[i][j] == '1') {
                    dfs(i, j, grid);
                    ans++;
                }
            }
        }
        return ans;
    }
};

二叉树的锯齿形层次遍历

问题描述

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal

思路

题解

class Solution {
public:
    vector<vector<int>> ret;
    vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
        dfs(root, 0);
        int n=ret.size();
        for(int i=0;i<n;i++){
            if(i%2!=0){
                reverse(ret[i].begin(),ret[i].end());
            }
        }
           return ret; 
    }
    void dfs(TreeNode *node, int level) {
        if (node == nullptr) return;
        if (level + 1 > ret.size()) ret.push_back(vector<int>());
        ret[level].push_back(node->val);
        if (node->left != nullptr)dfs(node->left, level + 1);
        if (node->right != nullptr) dfs(node->right, level + 1);
    }
};

组合总和 III

问题描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。 

示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii

思路

这个题比较简单，用到的是回溯算法。
要解决的问题是在1~9之间选择k个数字，使得他们的和为n。每次选择的数字是1~9，因为不能重复，所以每次递归从上一次的位置加1开始，将每次递归的结果存到一个tmp数组里面，当tmp的size到k时，判断他们的和是否为n，如果为n，将tmp插入到ret，不管sum是否等于n，都要返回到上一层。返回到上一层后，千万别忘记，将sum减i，并且在tmp中弹出i；

题解

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ret;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k,n,0,1);
        return ret;
    }
    void dfs(int k,int n,int sum,int location){
        if(tmp.size()==k){
            if(sum==n){
                ret.push_back(tmp);
            }
            return;
        }
        for(int i=location;i<=9;i++){
            tmp.push_back(i);
            sum=sum+i;
            dfs(k,n,sum,i+1);
            sum=sum-i;
            tmp.pop_back();
        }

    }
};

从二叉搜索树到更大和树

问题描述

给出二叉搜索树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

示例：
tree.png

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree

思路

深度优先搜索

题解

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector <int> ret;
    int sum=0;
    TreeNode *bstToGst(TreeNode *root) {
        dfs(root);
        return root;
    }
    void dfs(TreeNode *node){
        if(node== nullptr) return;
        dfs(node->right);
        sum+=node->val;
        node->val=sum;
        dfs(node->left);
    }
};
  1. 1
  2. 2
  3. 3
  4. 4
  5. 5