1. Toy模板网首页
  2. > Toy博客

【leetcode刷题之路】剑指Offer（3）——搜索与回溯算法

9月前 作者：小天才才 分类：Toy博客 阅读(55) 违法举报

这篇具有很好参考价值的文章主要介绍了【leetcode刷题之路】剑指Offer（3）——搜索与回溯算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

7 搜索与回溯算法

7.1 【BFS】剑指 Offer 32 - I - 从上到下打印二叉树

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/

  这里借助队列来实现广度优先遍历，由于需要访问每一层的节点，而且这一层访问才可以访问下一层，所以可以考虑队列的先进先出，先把每一层的节点加入队列，然后把这一层的节点访问的同时，也把它们的左右子树加入队列，这样每一层访问完之后紧接着就是下一层的节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> q;
        if(root!=nullptr) q.push(root);
        while(!q.empty())
        {
            int n = q.size();
            for(int i=0;i<n;i++)
            {
                TreeNode *tmp = q.front();
                q.pop();
                ans.push_back(tmp->val);
                if(tmp->left!=nullptr) q.push(tmp->left);
                if(tmp->right!=nullptr) q.push(tmp->right); 
            }
        }
        return ans;
    }
};
7.2【BFS】剑指 Offer 32 - II - 从上到下打印二叉树 II

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/

  这里借助队列来实现广度优先遍历，由于需要访问每一层的节点，而且这一层访问才可以访问下一层，所以可以考虑队列的先进先出，先把每一层的节点加入队列，然后把这一层的节点访问的同时，也把它们的左右子树加入队列，这样每一层访问完之后紧接着就是下一层的节点。以上一题不同的是每层的数要存放为一个向量，最后返回多个向量。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        if(root!=nullptr) q.push(root);
        while(!q.empty())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i=0;i<n;i++)
            {
                TreeNode *node = q.front();
                q.pop();
                tmp.push_back(node->val);
                if(node->left!=nullptr) q.push(node->left);
                if(node->right!=nullptr) q.push(node->right); 
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};
7.3 【BFS】【双端队列】剑指 Offer 32 - III - 从上到下打印二叉树 III

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/

  这里借助双端队列来实现广度优先遍历，由于需要访问每一层的节点，而且这一层访问才可以访问下一层，对于奇数层来说，访问的顺序是从左到右，而偶数层是从右到左，所以可以做如下操作：

  • 奇数层：从左往右取队列元素，但是每个元素先取其左子树再取右子树，然后从队列末尾插入；
  • 偶数层：从右往左取队列元素，但是每个元素先取其右子树再取左子树，然后从队列头部插入。

  这样就可以保证每一层的顺序连在一起时之字形顺序了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        deque<TreeNode*> q;
        if(root!=nullptr) q.push_back(root);
        bool flag = true;
        while(!q.empty())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i=0;i<n;i++)
            {
                TreeNode *node;
                if(flag)
                {
                    node = q.front();
                    q.pop_front();
                    if(node->left!=nullptr) q.push_back(node->left);
                    if(node->right!=nullptr) q.push_back(node->right);
                }
                else
                {
                    node = q.back();
                    q.pop_back();
                    if(node->right!=nullptr) q.push_front(node->right);
                    if(node->left!=nullptr) q.push_front(node->left);
                }
                tmp.push_back(node->val);
            }
            flag = !flag;
            ans.push_back(tmp);
        }
        return ans;
    }
};
7.4 【BFS】剑指 Offer 26 - 树的子结构

https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/

  这里把A的每个结点与B进行比较，如果结点相同则看它们的左右子树是否相同即可，这里借助自定义函数来判断A和B是否为包含关系，也就是A包含B，函数定义如下：

  • 如果B为空，说明此时B的所有结点遍历完了，B为A的子树；
  • 如果B不为空A为空，说明此时A的所有结点遍历完了但是B还有结点，则B不是A的子树；
  • 如果此时A和B的结点相同，还要判断它们的左右子树是否相同。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool is_contain(TreeNode* A, TreeNode* B) {
        if(B==nullptr) return true;
        if(A==nullptr) return false;

        if(A->val==B->val) return is_contain(A->left,B->left) && is_contain(A->right,B->right);
        else return false;
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==nullptr || B==nullptr) return false;

        if(A->val==B->val && is_contain(A,B)) return true;
        else return isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
};
7.5 【递归】剑指 Offer 27 - 二叉树的镜像

https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/

  直接交换每个结点的左右子树，然后递归返回即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==nullptr) return nullptr;
        swap(root->left,root->right);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};
7.6 【递归】【双指针】剑指 Offer 28 - 对称的二叉树

https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/

  利用双指针分别从树的左右子树往下判断是否对称，这里需要注意的是双指针最后必须同时为空才行，如果有一个先为空说明这棵二叉树是不对称的，同时双指针也要对称着向下移动，比如l左移r右移、l右移r左移。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* l, TreeNode* r) {
        if(l==nullptr && r==nullptr) return true;
        if(l==nullptr || r==nullptr) return false;
        return l->val==r->val && check(l->left,r->right) && check(l->right,r->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root,root);
    }
};
7.7 【DFS】【回溯】【剪枝】剑指 Offer 12 - 矩阵中的路径

https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/

  这里我们首先找到矩阵中和字符串的第一个字符对应的位置，然后从这个位置开始分别向上下左右深度搜索，直到找到与字符串完成对应的一条搜索路径即可，但是这里需要设置一些剪枝规则提前终止不必要的搜索：

  • 如果访问越界了，需要提前终止搜索；
  • 如果当前在矩阵中访问到的字符与目前在字符串中遍历到的字符不一样，需要提前终止搜索。

  这里为了防止矩阵中的元素被重复使用，访问过的元素统一赋值为空，当这一轮搜索结束之后再用字符串赋值回去，避免影响判断。

class Solution {
private:
    int row,col;
public:
    bool exist(vector<vector<char>>& board, string word) {
        row = board.size();
        col = board[0].size();
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(dfs(board,word,i,j,0)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
        //矩阵访问越界and当前访问字符不一致时，需要提前终止搜索，返回false
        if(i>=row || i<0 || j>=col || j<0 || board[i][j]!=word[k]) return false;
        //字符串遍历到最后一个字符，说明找到了一条路径，返回true
        if(k==word.size()-1) return true;
        //避免矩阵重复访问，已访问的赋值为空
        board[i][j] = ' ';
        //上下左右深度搜索
        bool flag = dfs(board,word,i-1,j,k+1) || dfs(board,word,i+1,j,k+1) || 
                    dfs(board,word,i,j-1,k+1) || dfs(board,word,i,j+1,k+1);
        //此轮搜索结束，已访问过的再赋值回去
        board[i][j] = word[k];
        return flag;
    }
};
7.8 【DFS】剑指 Offer 13 - 机器人的运动范围

https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

  利用DFS解题，虽然机器人可以上下左右移动，但是最后算的是机器人可以到达多少个格子，所以可以把上下左右简化为下和右两个行动，并且设置一个数组visit来记录每个格子是否被访问过。这道题的难点在于行坐标和列坐标的位数之和如何快速计算，这里我们可以发现一个规律，假设坐标为18,19,20,21,22时，数位和分别为9,10,2,3,4，这里如果坐标不是10的倍数，那么数位和随着坐标数的增加依次加1，而当来到20时，数位和直接变成了2，比19的数位和少8，同理坐标29,30,31的数位和分别是11,3,4，所以可以总结出这样的规律：

  • 如果坐标不是10的倍数，数位和较之前的坐标加1；
  • 如果坐标是10的倍数。数位和较之前的坐标减8.
class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visit(m,vector<bool>(n,false));
        return dfs(0,0,0,0,visit,m,n,k);
    }

    int dfs(int i, int j, int si, int sj, vector<vector<bool>> &visit, int m, int n, int k) {
        if(i<0 || i>=m || j<0 || j>=n || si+sj>k || visit[i][j]) return 0;
        visit[i][j] = true;
        int new_si = (i+1)%10 != 0 ? si+1 : si-8;
        int new_sj = (j+1)%10 != 0 ? sj+1 : sj-8;
        return 1 + dfs(i,j+1,si,new_sj,visit,m,n,k) + dfs(i+1,j,new_si,sj,visit,m,n,k);
    }
};
7.9 【DFS】【递归】剑指 Offer 34 - 二叉树中和为某一值的路径

https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

  利用DFS解题，顺着根结点先往一个子结点方向遍历，然后再去遍历另一个，这里的难点在于精准判断是否达到目标和，一共需要以下几个条件：

  • 截止目前的路径上的val之和等于target；
  • 目前结点是叶子结点，也就是该结点的左右结点都为空。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        vector<int> path;
        dfs(root,target,path);
        return ans;
    }

    void dfs(TreeNode* root, int target, vector<int> path) {
        if(root==nullptr) return;
        path.push_back(root->val);
        if(root->val==target && root->left==nullptr && root->right==nullptr)
        {
            ans.push_back(path);
            return;
        }
        dfs(root->left,target-root->val,path);
        dfs(root->right,target-root->val,path);
    }
};
7.10 【DFS】【递归】【双指针】剑指 Offer 36 - 二叉搜索树与双向链表

https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

  这道题其实就是把给出的这个二叉树变成中序遍历的结果输出，然后在中序遍历的过程中改变左右子树的指向即可，使之变成双向循环链表，这里借助双指针来构造循环链表，head指向循环链表的开始，pre指向中序遍历过程中访问到的每个结点的前序结点，按照中序遍历的过程进行DFS，遍历到最下面的左子树时，开始构造链表，此时左子树应该是当前root的前驱，这样就构造出了一个循环，然后依次往上返回构造其他循环，最后要把头尾连接起来。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node *head=nullptr, *pre=nullptr;

    Node* treeToDoublyList(Node* root) {
        if(root==nullptr) return root;
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }

    void dfs(Node* root) {
        if(root==nullptr) return;
        dfs(root->left);
        if(pre!=nullptr) pre->right = root;
        else head = root;
        root->left = pre;
        pre = root;
        dfs(root->right);
    }
};
7.11 【DFS】剑指 Offer 54 - 二叉搜索树的第k大节点

https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

  这道题是找第k大的结点，二叉搜索树的中序遍历结果是从小到大排序，所以其实就是对二叉搜索树进行倒过来的中序遍历，每遍历一个元素k–，当k为0时就是最终结果。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    int kthLargest(TreeNode* root, int k) {
        dfs(root,k);
        return ans;
    }

    void dfs(TreeNode* root,int &k) {
        if(root==nullptr) return;
        dfs(root->right,k);
        k--;
        if(k==0) ans = root->val;
        dfs(root->left,k);
    }
};
7.12 【DFS】剑指 Offer 55 - I - 二叉树的深度

https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/

  考察深度优先遍历，从上往下深度搜索，没找到一个节点就把当前的深度dpt加1，最后取最大的那个dpt即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int depth = 1;
    int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        dfs(root,0);
        return depth;
    }
    
    void dfs(TreeNode* root, int dpt) {
        if(root==nullptr)
        {
            depth = max(depth,dpt);
            return;
        }
        dpt++;
        dfs(root->left,dpt);
        dfs(root->right,dpt);
    }
};
7.13 【DFS】剑指 Offer 55 - II - 平衡二叉树

https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/

  采用自底向上的方法，首先判断最下面的节点是否满足平衡二叉树的条件，不满足就把当前高度赋值为-1，这样一步步从下往上递增，最后只需看根结点的高度是多少即可，如果采用自顶向下的话则会存在某些节点多次计算高度，会增加时间复杂度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(depth(root)!=-1) return true;
        else return false;
    }

    int depth(TreeNode* root) {
        if(root==nullptr) return 0;
        int left_depth = depth(root->left);
        int right_depth = depth(root->right);
        if(left_depth == -1 || right_depth == -1 || abs(left_depth - right_depth) > 1)
        {
            return -1;
        }
        else return max(left_depth,right_depth) + 1;
    }
};
7.14 【位运算】剑指 Offer 64 - 求1+2+…+n

https://leetcode.cn/problems/qiu-12n-lcof/

  求和公式为sum=n*(n+1)/2，这里为什么用bool呢，其实用char也行，因为它们都占用一个字节，意思就是构造了一个n*(n+1)的数组，然后先计算这个数组一共多少字节，对于除2操作直接位运算就行了。

class Solution {
public:
    int sumNums(int n) {
        bool ans[n][n+1];
        return sizeof(ans)>>1;
    }
};
7.15 【DFS】【递归】剑指 Offer 68 - I - 二叉搜索树的最近公共祖先

https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

  这道题需要明白一点，就是x的值一定是在p和q之间的，所以在深度遍历时只需比较当前根节点的值和p、q的值的大小即可，如果当前节点的值比p和q都大，说明最近公共祖先在左子树，如果当前节点的值比p和q都小，说明最近公共祖先在右子树，如果都不满足说明目前找到的就是最近公共祖先了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if(root->val > p->val && root->val > q->val)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else if(root->val < p->val && root->val < q->val)
        {
            return lowestCommonAncestor(root->right,p,q);
        }
        else return root;
    }
};
7.16 【DFS】剑指 Offer 68 - II - 二叉树的最近公共祖先

https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

  这题为一般二叉树中找最近公共祖先，首先要明确公共祖先的判断标准，共有以下三点：

  • (1)p和q在二叉树两侧（也就是一个在左子树一个在右子树），则找最近的root结点；
  • (2)p和q在二叉树同侧（也就是同在左子树或者右子树），则找p或者q；

  下面定义双指针left和right来判断目前节点的左右子树中是否有p和q，并给出以下判断标准：

  • (1)如果left和right均不为空，说明p和q一个在左子树一个在右子树，返回当前root节点；
  • (2)如果left为空，right不为空，说明p和q都在右子树中，返回right；
  • (3)如果left不为空，right为空，说明p和q都在左子树中，返回left。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr || root==p || root==q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(left==nullptr) return right;
        if(right==nullptr) return left;
        return root;
    }
};
7.17 【DFS】【模拟】剑指 Offer 37 - 序列化二叉树

https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/

  本题主要实现两个功能，分别是二叉树的序列化和反序列化，也就是给定字符串变成二叉树，或者给定二叉树变成字符串，下面分开来介绍实现思路：
（1）二叉树->字符串
  这个其实就是对二叉树进行中序遍历即可，然后把每个节点的值保存到字符串中，难点在于如何把整数转变成字符串，因为这里的数值可能是多位数或者负数，所以这里定义了一个函数int_to_str()来实现将整数转变为字符串，同时在函数tree_to_str()中实现将二叉树转为字符串，这里注意每个数值后面要加上逗号’,‘。
（2）字符串->二叉树
  这个就比较难了，首先要把字符串中的字符转为数字，这里通过自定义函数str_to_int()来实现，接下来就是为每一个生成的数值构造一个节点，按照中序遍历的情况依次构造二叉树，当上述准备工作完成之后，下面就是要对给定的字符串进行切割，分割标准为逗号’,'，遍历是每遇到逗号说明是一个节点，然后把这个节点通过上述两步操作插入到二叉树中即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
private:
        string int_to_str(int num) {
        bool flag = true;
        string ans;
        if(num < 0)
        {
            num = -num;
            flag = false;
        }
        while(num)
        {
            ans.insert(ans.begin(), num % 10 + '0');
            num /= 10;
        }
        if(flag==false) ans.insert(ans.begin(),'-');
        return ans;
    }

    int str_to_int(string s) {
        int idx = 0;
        bool flag = true;
        int ans = 0;
        if(s[idx]=='-')
        {
            flag = false;
            idx++;
        }
        while(idx < s.size())
        {
            ans = s[idx] - '0' + ans * 10;
            idx++;
        }
        if(flag==false) ans = -ans;
        return ans;
    }

    void tree_to_str(TreeNode* root, string& str) {
        if(root==nullptr)
        {
            str += "/,";
            return;
        }
        str += int_to_str(root->val);
        str += ",";
        tree_to_str(root->left, str);
        tree_to_str(root->right, str);
    }

    TreeNode* str_to_tree(vector<string>& s, int& idx) {
        if(s[idx]=="/") return nullptr;
        int val = str_to_int(s[idx]);
        TreeNode* root = new TreeNode(val);
        root->left = str_to_tree(s, ++idx);
        root->right = str_to_tree(s, ++idx);
        return root;
    }

public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans;
        tree_to_str(root,ans);
        return ans;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> s;
        int idx = 0;
        while(idx < data.size())
        {
            int tmp = idx;
            while(data[idx]!=',') idx++;
            string now = data.substr(tmp, idx - tmp);
            s.push_back(now);
            idx++;
        }
        idx = 0;
        TreeNode* root = str_to_tree(s, idx);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
7.18 【DFS】【回溯】【模拟】剑指 Offer 38 - 字符串的排列

https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/

  这题难点在于如何保证字符不重复遍历，同时也要保证最后得到的字符串里面没有重复的字符串，这里考虑到可能原始的字符串里会有一些重复字符，所以先对原始的字符串进行排序，然后定义一个数组visited来保存每一位是否被访问过，而在深度遍历的时候，对于每次访问的字符，也要判断它是否为重复的字符，防止重复的字符被多次访问，但最后其实都是得到的同一个字符串，最后本次遍历完之后还要把临时字符串tmp和visited置回原来的状态。文章来源地址https://www.toymoban.com/news/detail-547195.html

class Solution {
public:
    vector<string> ans;
    vector<int> visited;

    void dfs(string &s, int i, int length, string &tmp) {
        if(i==length)
        {
            ans.push_back(tmp);
            return;
        }

        for(int j=0;j<length;j++)
        {
            if(visited[j] || (j>0 && !visited[j-1] && s[j-1]==s[j])) continue;

            visited[j] = 1;
            tmp.push_back(s[j]);

            dfs(s,i+1,length,tmp);
            tmp.pop_back();
            visited[j] = 0;
        }
    }

    vector<string> permutation(string s) {
        int length = s.size();
        visited.resize(length);
        string tmp;

        sort(s.begin(),s.end());
        dfs(s,0,length,tmp);

        return ans;
    }
};

到了这里，关于【leetcode刷题之路】剑指Offer（3）——搜索与回溯算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 剑指 Offer ！！13. 机器人的运动范围(回溯算法)

    剑指 Offer 13. 机器人的运动范围 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能

    2024年02月11日
    浏览(38)
  • 剑指offer(C++)-JZ12：矩阵中的路径(算法-回溯)

    剑指offer(C++)-JZ12：矩阵中的路径(算法-回溯)

    作者：翟天保Steven 版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处 题目描述： 请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以

    2024年02月11日
    浏览(43)
  • 剑指offer(C++)-JZ13：机器人的运动范围(算法-回溯)

    剑指offer(C++)-JZ13：机器人的运动范围(算法-回溯)

    作者：翟天保Steven 版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处 题目描述： 地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，

    2024年02月12日
    浏览(46)
  • 剑指 Offer 12. 矩阵中的路径 / LeetCode 79. 单词搜索（深度优先搜索）

    剑指 Offer 12. 矩阵中的路径 / LeetCode 79. 单词搜索（深度优先搜索）

    链接：剑指 Offer 12. 矩阵中的路径；LeetCode 79. 单词搜索 难度：中等 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相

    2024年02月02日
    浏览(41)
  • (搜索) 剑指 Offer 12. 矩阵中的路径 ——【Leetcode每日一题】

    (搜索) 剑指 Offer 12. 矩阵中的路径 ——【Leetcode每日一题】

    难度：中等 给定一个 m * n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许

    2024年02月12日
    浏览(40)
  • (搜索) 剑指 Offer 38. 字符串的排列 ——【Leetcode每日一题】

    (搜索) 剑指 Offer 38. 字符串的排列 ——【Leetcode每日一题】

    难度：中等 输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面 不能有重复元素 。 示例: 输入：s = “abc” 输出：[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”] 限制 ： 1 = s 的长度 = 8 💡思路：回溯 可以直接 暴力穷举 ，但

    2024年02月12日
    浏览(49)
  • (搜索) 剑指 Offer 13. 机器人的运动范围 ——【Leetcode每日一题】

    (搜索) 剑指 Offer 13. 机器人的运动范围 ——【Leetcode每日一题】

    难度：中等 地上有一个 m 行 n 列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如，当 k 为18时，机器人能够进入方格

    2024年02月11日
    浏览(55)

  • 【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表

    剑指 Offer 36. 二叉搜索树与双向链表 后序遍历、二叉搜索树 二叉搜索树中的任一节点的 直接前驱为其左子树的最右侧节点，直接后继为其右子树的最左侧节点 。因此，可以通过这个关系来操作原来的二叉树。 为了不影响深度较大的节点的判断，使用后序遍历。 Step1. 后序遍

    2024年02月13日
    浏览(41)
  • 《剑指offer》（5）搜索算法、位运算、模拟

    《剑指offer》（5）搜索算法、位运算、模拟

    方法一： class Solution:     def GetNumberOfK(self , nums: List[int], k: int) - int:         #从两边开始找，找到之后记录当前位置         left = 0         right = len(nums) - 1         if k not in nums:             return 0         start = len(nums) - 1         end = 0         while left = right:      

    2024年02月14日
    浏览(79)
  • 【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=＞记忆化搜索=＞动态规划】

    【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=＞记忆化搜索=＞动态规划】

    🍎作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭：人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯🎯 剑指 Offer 60. n个骰子的点

    2023年04月19日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包