网站开发薪水一般多少钱,黄山冬季旅游攻略,免费行情网站在线,wordpress 每页文章数量食用指南#xff1a;本文为作者刷题中认为有必要记录的题目 前置知识#xff1a;回溯法经典问题之全排列 ♈️今日夜电波#xff1a;带我去找夜生活—告五人 0:49 ━━━━━━️#x1f49f;──────── 4:59 … 食用指南本文为作者刷题中认为有必要记录的题目 前置知识回溯法经典问题之全排列 ♈️今日夜电波带我去找夜生活—告五人 0:49 ━━━━━━️──────── 4:59 ◀️ ⏸ ▶️ ☰ 关注点赞收藏您的每一次鼓励都是对我莫大的支持 目录 回溯法的理解 一、字符串的排列 二、字母大小写全排列 回溯法的理解 本文参考了一位大佬的题解详细的介绍了回溯法链接
上一篇刷题文 回溯法经典问题之子集 记住一句话for循环横向遍历递归纵向遍历回溯不断调整结果集。 这句话将从始至终贯穿我们对于以上问题的回溯解决办法。 一、字符串的排列
题目链接剑指 Offer 38. 字符串的排列
题目描述 输入一个字符串打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组但里面不能有重复元素。 示例:
输入s abc
输出[abc,acb,bac,bca,cab,cba]
限制
1 s 的长度 8 本题思路 首先采用经典的“回溯三部曲” 1、定义两个全局变量一个用来存放符合条件单一结果path一个用来存放符合条件结果的集合result。 2、回溯的主体回溯终止条件。path保存一组数据每次遍历到叶子节点再插入到result中并且回溯到上一个节点。 3、单层搜索的过程。for循环用来横向遍历递归的过程是纵向遍历。 根据题意我们做出一定的改动 由于本题是以string容器的形式传递的字符串对此我们的path也应当转变为相应的形式。题目以及例子很明确的表现了本题实际上跟 回溯法经典问题之全排列 第二小题是关系密切的。大家可参考。此题没有说明字符串内的元素是否会有相同的元素对此我们当做会有重复的元素于是我们建立一个bool类型的vector容器used来作为确定每一个节点是否使用过以此来解决重复插入问题。接着我们需要加入剪枝操作以此来解决重复选取问题。 一句话概括此题就是 只有当used[i]0时才去进行后续操作。 同一树枝上可以选取但是同一树层上不可以选取 即{i0s[i-1]s[i]used[i-1]0}才去进行后续操作。
class Solution {
private:
vectorstring result;void trackback(string s,string path,vectorbool used)
{if(path.size()s.size()){result.push_back(path);return;}for(int i0;is.size();i){if(i0s[i]s[i-1]used[i-1]0)continue;if (used[i] ! 1){path.push_back(s[i]);used[i] 1;trackback(s,path,used);used[i] 0;path.pop_back();}}
}
public:vectorstring permutation(string s) {if(s.size()0)return{};result.clear();vectorbool used;sort(s.begin(),s.end());//关键一步由于不知道是否重复所以必须要排序以找到重复的字母string path;used.resize(s.size());trackback(s,path,used);return result;}
}; 特别注意 这里的sort操作是关键的一步由于不知道是否重复所以必须要排序以找到重复的字母让他们相邻排列。 二、字母大小写全排列
题目链接784. 字母大小写全排列
题目描述 给定一个字符串 s 通过将字符串 s 中的每个字母转变大小写我们可以获得一个新的字符串。返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。 示例 1
输入s a1b2
输出[a1b2, a1B2, A1b2, A1B2]示例 2:
输入: s 3z4
输出: [3z4,3Z4]
提示:
1 s.length 12s 由小写英文字母、大写英文字母和数字组成 本题思路 同样的采用回溯三部曲但是我们这次不采用for循环遍历因为根据题意本题仅仅只是改变“字母的大小写转化”。如下 1、定义两个全局变量一个用来存放符合条件单一结果path一个用来存放符合条件结果的集合result。注意要记得用一个变量来记录遍历的位置。 2、回溯的主体回溯终止条件。path保存一组数据每次遍历到叶子节点再插入到result中并且回溯到上一个节点。 3、无需for循环横向遍历仅仅纵向遍历即递归的过程。 梳理一下判断的条件判断是否为字母如果是字母则不管他是否为大小写直接转化为小写插入path进行递归递归回来后再转化为大写插入path递归。如果不是字母则直接插入parh进行下一层的递归。 一图让你了解~以a1b2为例 class Solution {
private:
vectorstring result;void backtrack(string s,string path,int index)
{if(s.size()path.size()){result.push_back(path);return;}if(isalpha(s[index])){path.push_back(tolower(s[index]));backtrack(s,path,index1);path.pop_back();path.push_back(toupper(s[index]));backtrack(s,path,index1);path.pop_back();}else{path.push_back(s[index]);backtrack(s,path,index1);path.pop_back();}}
public:vectorstring letterCasePermutation(string s) {result.clear();string path;backtrack(s,path,0);return result;}
}; 感谢你耐心的看到这里ღ( ´ᴗ )比心如有哪里有错误请踢一脚作者o(╥﹏╥)o 给个三连再走嘛~
