每日刷题|回溯法解决全排列问题第二弹之解决字符串、字母大小排列问题

食用指南:本文为作者刷题中认为有必要记录的题目
前置知识:回溯法经典问题之全排列
♈️今日夜电波:带我去找夜生活—告五人
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时才去进行后续操作。
同一树枝上可以选取,但是同一树层上不可以选取!
即{i>0&&s[i-1]==s[i]&&used[i-1]==0}才去进行后续操作。
class Solution {
private:
vector<string> result;void trackback(string& s,string& path,vector<bool>& used)
{if(path.size()==s.size()){result.push_back(path);return;}for(int i=0;i<s.size();i++){if(i>0&&s[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:vector<string> permutation(string s) {if(s.size()==0)return{};result.clear();vector<bool> 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:
vector<string> 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,index+1);path.pop_back();path.push_back(toupper(s[index]));backtrack(s,path,index+1);path.pop_back();}else{path.push_back(s[index]);backtrack(s,path,index+1);path.pop_back();}}
public:vector<string> letterCasePermutation(string s) {result.clear();string path="";backtrack(s,path,0);return result;}
};
感谢你耐心的看到这里ღ( ´・ᴗ・` )比心,如有哪里有错误请踢一脚作者o(╥﹏╥)o!
给个三连再走嘛~
相关文章:
每日刷题|回溯法解决全排列问题第二弹之解决字符串、字母大小排列问题
食用指南:本文为作者刷题中认为有必要记录的题目 前置知识:回溯法经典问题之全排列 ♈️今日夜电波:带我去找夜生活—告五人 0:49 ━━━━━━️💟──────── 4:59 …...
python循环遍历字典: title_content_list.append([key, value])print(ti
示例示例Python循环遍历字典的方法有以下几种:使用for...in循环: Python循环遍历字典的方法有以下几种: 1. 使用for...in循环: python dict {name:Tom, age:20, gender:male} # 遍历所有的键 for key in dict:print(key) # 遍…...
Redis List类型命令 - Set类型命令 - SortedSet类型命令
目录 List类型 什么是双向链表呢? List类型的特征: List的常用命令 LPUSH和RPUSH的区别: LPOP和RPOP的区别: LPUSH和RPUSH的使用 LPOP和RPOP的使用 LRANGE key star end:返回一段距离范围内所有的元素 BLPOP…...
等级保护 —— 安全控制点,安全要求
等级保护 —— 安全控制点,安全要求 安全物理环境: 物理位置选择 a)机房场地应选择在具有防震、防风和防雨等能力的建筑内; 1)核查是否有建筑物抗震设防审批文档。2)核查是否有雨水渗漏的痕迹。3&#…...
nginx-缓存
disk cache:磁盘缓存数据,有时间延迟,但是非常小,相对于直接请求服务器返回 对于用户来说基本无感知。 memory cache:磁盘缓存数据,基本上没有时间延迟 协商缓存(nginx自带功能, 不…...
layui使用富文本已经使用第三方插件Kz.layedit来优化layui的富文本
官方提供的编辑器功能太少 没有字体颜色,不能传图片,视频等扩展 官方文档说的很清楚,简易的富文本使用layui提供的的确十分方便,但是缺少的元素很多。像什么标题,元素,等简单的都没有。小编我当初页为此苦…...
某公司二面面试题总结
你们公司开发遵守怎么样的代码规范? 当编写Java代码时,遵守良好的代码规范对于代码的可读性和可维护性至关重要。以下是一些更详细的Java代码规范建议: 命名规范: 类名应该采用名词或名词短语,使用驼峰命名法…...
Ubuntu编译运行socket.io
本篇文章记录一下自己在ubuntu上编译运行socket.io的过程,客户端选用的是socket.io的c的库,编译起来倒不难,但是说到运行的话,对我来说确实是花了点功夫。毕竟程序要能运行起来才能更方便地去熟悉代码,因此今天我就记录…...
h5开发网站-页面内容不够高时,如何定位footer始终位于页面的最底部
一、问题描述: 在使用h5开发页面时,会遇到这个情况:当整个页面高度不足以占满显示屏一屏,页脚不是在页面最底部,影响用户视觉。想让页脚始终在页面最底部,我们可能会想到用: 1.min-height来控…...
手机也可以搭建个人博客?安卓Termux+Hexo搭建属于你自己的博客网站【cpolar实现公网访问】
文章目录 前言 1.安装 Hexo2.安装cpolar3.远程访问4.固定公网地址 前言 Hexo 是一个用 Nodejs 编写的快速、简洁且高效的博客框架。Hexo 使用 Markdown 解析文章,在几秒内,即可利用靓丽的主题生成静态网页。 下面介绍在Termux中安装个人hexo博客并结合…...
Support for password authentication was removed on August 13, 2021 解决方案
打开你的github,Setting 点击Developer settings。 点击generate new token 按照需要选择scope 生成token,以后复制下来。 给git设置token样式的remote url git remote set-url origin https://你的tokengithub.com/你的git用户名/仓库名称.git然后就可…...
MPP 与 SMP 的区别,终于有人讲明白了【文末送书】
文章目录 导读01 SMP1. SMP 的典型特征2. SMP的优缺点 02 分布式MPP计算架构1. MPP 架构核心原理2. MPP 典型特征3. MPP优缺点 写作末尾 导读 当今数据计算领域主要的应用程序和模型可大致分为在线事务处理(On-line Transaction Processing ,OLTP&#…...
华为OD机试真题【寻找最大价值的矿堆】
1、题目描述 【寻找最大价值的矿堆】 给你一个由 ‘0’(空地)、’1’(银矿)、’2’(金矿)组成的的地图, 矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿…...
Java Maven 项目读取项目版本号
java读取 pom.xml 文件中设置的版本号 1. 在 src/main/resources/下新建 app.properties 文件: app.version${project.version} 2. 在pom.xml 中增加 <build> <resources> <resource> <directory>src/main/resources</di…...
Lesson4-1:OpenCV图像特征提取与描述---角点特征
学习目标 理解图像的特征知道图像的角点 1 图像的特征 大多数人都玩过拼图游戏。首先拿到完整图像的碎片,然后把这些碎片以正确的方式排列起来从而重建这幅图像。如果把拼图游戏的原理写成计算机程序,那计算机就也会玩拼图游戏了。 在拼图时ÿ…...
C++ 基础(一)题目练习
一、使用输出运算符输出一个长方形, 如下图所示: #include <iostream> using namespace std; int main() {cout << "*******" << endl;cout << "*******" << endl;cout << "*******"…...
Webpack5入门到原理
Webpack5学习 尚硅谷Webpack5新版视频教程 B站直达:https://www.bilibili.com/video/BV14T4y1z7sw 百度网盘:https://pan.baidu.com/s/114lJRGua2uHBdLq_iVLOOQ 提取码:yyds 阿里云盘:https://www.aliyundrive.com/s/UMkmCzdWsGh&…...
地形有通挂支隘险远六种情况
地形有通、挂、支、隘、险、远六种情况 【安志强趣讲《孙子兵法》第34讲】 第十一篇:地形篇 【全文大白话】 地形有各种情况,行军有各种情况,用好地形获得交战的主动权。 【原文】 孙子曰:地形有通者,有挂者࿰…...
C++多态案例-设计计算器类
1.前置知识点 多态是面向对象的三大特性之一 多态分为两类 静态多态:函数重载和运算符重载都属于静态多态,复用函数名动态多态:派生类和虚函数实现运行时多态 静态多态和动态多态的区别 静态多态的函数地址早绑定-----编译阶段确定函数地…...
复制tr的一行数据或者复制数据使用,使用jq和php
效果图: 2.Html <!--复制的tr数据,s----------------------------------------------------------------------------------------------->{foreach from$arrs keykk itemvv} <tr><td style"text-align:center;" >1</t…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
