每日OJ题_牛客_JZ38字符串的排列_DFS_C++_Java

目录

牛客_JZ38字符串的排列_DFS

题目解析

C++代码

Java代码


牛客_JZ38字符串的排列_DFS

字符串的排列_牛客题霸_牛客网

描述:

输入一个长度为 n 字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围:n<10
要求:空间复杂度 O(n!),时间复杂度 O(n!)

输入描述:

输入一个字符串,长度不超过10,字符只包括大小写字母。


题目解析

        这是一个典型的排列问题,形如“给定一组数据,求这些数据所有的排列情况”,在这里一组数据就是字符串的字符。字符串的排列情况就是,每次需要选择一个字符(不能重复选择),按照顺序将选择的字符连接起来。

        针对排列问题,就是做选择的过程,我们需要进行n次选择,每次需要记录选择的数据且不能重复选择,具体过程如下:

  1. 遍历字符串中的字符,选择一个下标未加入过的字符(因为有重复不能比较字符值)加入记录中;
  2. 重复1过程,直到字符串中的字符都加入到了记录中;
  3. 撤销上一次的选择,选择上一次选择的下一个字符,并重复1,2;
  4. 直到上一次选择的下一个字符为空,选择过程结束。

C++代码

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param str string字符串 * @return string字符串vector*/vector<string> ret;string path;bool vis[11] = { false };string s;int n;vector<string> Permutation(string str) {  // Day33_3_全排列// vector<string> ret;// sort(str.begin(), str.end());// do// {//     ret.push_back(str);// }while (next_permutation(str.begin(), str.end()));// return ret;sort(str.begin(), str.end());s = str;n = s.size();dfs(0);return ret;}void dfs(int pos){if(pos == n){ret.push_back(path);return;}for(int i = 0; i < n; ++i){if(vis[i] || (i > 0 && s[i] == s[i - 1] && !vis[i - 1]))continue;path += s[i];vis[i] = true;dfs(pos + 1);vis[i] = false;path.pop_back();}}
};

Java代码

import java.util.*;
public class Solution
{boolean[] vis = new boolean[15]; // 标记当前位置是否已经使⽤过StringBuffer path = new StringBuffer();ArrayList<String> ret = new ArrayList<>(); // 收集叶⼦结点char[] s;int n;public ArrayList<String> Permutation (String str) {n = str.length();s = str.toCharArray();Arrays.sort(s);dfs(0);return ret;}public void dfs(int pos) // 填哪个位置{if(pos == n) // 收集结果{ret.add(path.toString());return;}// 填 pos 位置for(int i = 0; i < n; i++){if(vis[i])continue;if(i > 0 && s[i] == s[i - 1] && !vis[i - 1])continue;path.append(s[i]);vis[i] = true;dfs(pos + 1);// 恢复现场vis[i] = false;path.deleteCharAt(path.length() - 1);}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/469039.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

markdown常用语法

&#x1f353; 简介&#xff1a;java系列技术分享(&#x1f449;持续更新中…&#x1f525;) &#x1f353; 初衷:一起学习、一起进步、坚持不懈 &#x1f353; 如果文章内容有误与您的想法不一致,欢迎大家在评论区指正&#x1f64f; &#x1f353; 希望这篇文章对你有所帮助,欢…

CSS教程(二)- CSS选择器

1. 作用 匹配文档中的某些元素为其应用样式。根据不同需求把不同的标签选出来。 2. 分类 分类 基础选择器 包含 标签选择器、ID选择器、类选择器、通用选择器等 复合选择器 包含 后代选择器、子代选择器、伪类选择器等 1 标签选择器 介绍 又称为元素选择器&#xff0c;根…

第二十周学习周报

目录 摘要abstractTheory behind GANGAN训练目标GAN训练技巧 总结 摘要 本周的学习内容是GAN的基本理论&#xff0c;在训练GAN的时候&#xff0c;Generator的目标是希望生成的数据与真实的数据越相似越好&#xff0c;而Discriminator的目标是尽量将生成的数据与真实的数据区分…

2024年CRM系统对比:国内外十大CRM热门选择

在数字化转型的大潮中&#xff0c;CRM系统是企业提升客户关系管理、优化销售流程的重要工具。本文将从系统功能、优势、劣势、总体评价四个方面&#xff0c;对2024年国内外十大热门CRM系统进行全方位对比&#xff0c;帮助企业找到最适合的CRM解决方案。 1.纷享销客CRM 系统功…

VideoChat:开源的数字人实时对话系统,支持自定义数字人的形象和音色

❤️ 如果你也关注大模型与 AI 的发展现状&#xff0c;且对大模型应用开发非常感兴趣&#xff0c;我会快速跟你分享最新的感兴趣的 AI 应用和热点信息&#xff0c;也会不定期分享自己的想法和开源实例&#xff0c;欢迎关注我哦&#xff01; &#x1f966; 微信公众号&#xff…

[CKS] TLS Secrets创建与挂载

目前的所有题目为2024年10月后更新的最新题库&#xff0c;考试的k8s版本为1.31.1 BackGround 您必须使用存储在TLS Secret中的SSL文件&#xff0c;来保护Web 服务器的安全访问。 Task 在clever-cactus namespace中为名为clever-cactus的现有Deployment创建名为clever-cactu…

使用 wxPython 开发 Python 桌面应用程序的完整教程

使用 wxPython 开发 Python 桌面应用程序的完整教程 引言 在当今的软件开发领域&#xff0c;桌面应用程序仍然占据着重要的位置。Python 作为一种灵活且易于学习的编程语言&#xff0c;结合 wxPython 库&#xff0c;可以快速构建跨平台的桌面应用程序。本文将深入探讨 wxPyth…

自动驾驶系列—自动驾驶环境感知:Radar数据的应用与实践

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…

DimensionX:从单张图片生成高度逼真的 3D 和 4D 场景

❤️ 如果你也关注大模型与 AI 的发展现状&#xff0c;且对大模型应用开发非常感兴趣&#xff0c;我会快速跟你分享最新的感兴趣的 AI 应用和热点信息&#xff0c;也会不定期分享自己的想法和开源实例&#xff0c;欢迎关注我哦&#xff01; &#x1f966; 微信公众号&#xff…

蓝桥杯备考——算法

一、排序 冒泡排序、选择排序、插入排序、 快速排序、归并排序、桶排序 二、枚举 三、二分查找与二分答案 四、搜索&#xff08;DFS&#xff09; DFS&#xff08;DFS基础、回溯、剪枝、记忆化&#xff09; 1.DFS算法&#xff08;深度优先搜索算法&#xff09; 深度优先搜…

【网络面试篇】其他面试题——Cookie、Session、DNS、CDN、SSL/TLS、加密概念

目录 一、HTTP 相关问题 1. Cookie 和 Session 是什么&#xff1f; &#xff08;1&#xff09;Cookie &#xff08;2&#xff09;Session 2. Cookie 的工作原理&#xff1f; 3. Session 的工作原理&#xff1f; 4. Cookie 和 Session 有什么区别&#xff1f; 二、其他问…

隧道论文阅读2-采用无人融合扫描数据的基于深度学习的垂直型隧道三维数字损伤图

目前存在的问题&#xff1a; 需要开发新的无人测量系统测量垂直隧道图像数据量巨大&#xff0c;基于深度学习完成损伤评估跟踪获取图像位置的困难&#xff0c;对大型基础设施感兴趣区域(roi)的2d和3d地图建立进行了研究&#xff0c;对整个目标结构的损伤定位仍然具有挑战性。为…

CCF-A类 HPCA 2025 重磅揭晓:录取数据公布

近日&#xff0c;第31届国际计算机体系结构领域顶级会议HPCA (International Symposium on High Performance Computer Architecture) 正式发布了2025年会议的录用通知&#xff01;本届会议共收到了534 篇提交论文&#xff0c;其中&#xff0c;112篇论文被接收&#xff0c;整体…

Linux应用——线程池

1. 线程池要求 我们创建线程池的目的本质上是用空间换取时间&#xff0c;而我们选择于 C 的类内包装原生线程库的形式来创建&#xff0c;其具体实行逻辑如图 可以看到&#xff0c;整个线程池其实就是一个大型的 CP 模型&#xff0c;接下来我们来完成它 2. 整体模板 #pragma …

IDM扩展添加到Edge浏览器

IDM扩展添加到Edge浏览器 一般情况下&#xff0c;当安装IDM软件后&#xff0c;该软件将会自动将IDM Integration Module浏览器扩展安装到Edge浏览器上&#xff0c;但在某些情况下&#xff0c;需要我们手动安装&#xff0c;以下为手动安装步骤 手动安装IDM扩展到Edge浏览器 打…

docker 拉取MySQL8.0镜像以及安装

目录 一、docker安装MySQL镜像 搜索images 拉取MySQL镜像 二、数据挂载 在/root/mysql/conf中创建 *.cnf 文件 创建容器,将数据,日志,配置文件映射到本机 检查MySQL是否启动成功&#xff1a; 三、DBeaver数据库连接 问题一、Public Key Retrieval is not allowed 问题…

深入探索Waymo自动驾驶技术发展:从DARPA挑战赛到第五代系统的突破

引言 自动驾驶技术正引领着未来出行方式的革命&#xff0c;而Waymo作为全球自动驾驶领域的先锋&#xff0c;始终走在技术发展的最前沿。本文基于Waymo联席CEO德米特里多尔戈夫&#xff08;Dmitri Dolgov&#xff09;在No Priors节目中的访谈&#xff0c;全面介绍Waymo的技术发展…

鸿蒙移动应用开发-------初始arkts

一. 什么是arkts ArkTS是HarmonyOS优选的主力应用开发语言。 ArkTS围绕应用开发在TypeScript&#xff08;简称TS&#xff09;生态基础上做了进一步扩展&#xff0c;保持了TS的基本风格&#xff0c;同时通过规范定义强化开发期静态检查和分析&#xff0c;提升程序执行稳定性和…

c++ 输入三条边 绘制三角形

安装图形库 参考 #include "graphics.h" // 就是需要引用这个图形库 #include <conio.h> #include <stdio.h> #include <math.h>// 判断是否可以构成三角形 int isTriangle(int a, int b, int c) {return (a b > c) && (a c >…

A20红色革命文物征集管理系统

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…