首页 > 编程语言 >C++学习随笔——算法题:全排列问题

C++学习随笔——算法题:全排列问题

时间:2024-08-28 10:15:19浏览次数:10  
标签:字符 right 复杂度 C++ 算法 字符串 随笔 permute left

算法题:输入一个不存在重复字符的字符串,打印出字符串中字符的全部排列组合。

代码实现:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // std::swap

void permute(std::string str, int left, int right) {
    if (left == right) {
        std::cout << str << std::endl;
    } else {
        for (int i = left; i <= right; i++) {
            // 交换字符
            std::swap(str[left], str[i]);
            
            // 递归调用,生成剩余字符的排列
            permute(str, left + 1, right);
            
            // 交换回来,以便下一次的排列
            std::swap(str[left], str[i]);
        }
    }
}

int main() {
    std::string input = "123";
    int n = input.size();
    permute(input, 0, n - 1);
    return 0;
}

解释:

  1. permute 函数

    • 这个递归函数生成所有字符的排列组合。
    • 参数 str 是输入字符串,left 是当前正在考虑的字符位置,right 是字符串的最后一个字符位置。
  2. 递归基准情况

    • left == right 时,表示所有字符都已经排列完毕,直接打印当前的排列。
  3. 递归过程

    • 通过交换 str[left]str[i],不同字符被置于当前考虑的位置。
    • 然后,递归调用 permute 函数来生成剩余字符的排列组合。
    • 最后,交换字符回到原始位置,以便继续生成其他可能的排列。
  4. 主函数 main

    • 调用 permute 函数,从字符串的第一个字符开始生成排列。

复杂度分析:

  • 时间复杂度:生成所有排列组合的时间复杂度为 O(n!),其中 n 是字符串的长度。每个排列都需要 O(n) 的时间来生成和打印。
  • 空间复杂度:递归调用栈的空间复杂度为 O(n)。

标签:字符,right,复杂度,C++,算法,字符串,随笔,permute,left
From: https://www.cnblogs.com/kitanoki/p/18384070

相关文章

  • C++学习随笔——C++STL中binary_search的使用方法
    std::binary_search是C++标准模板库(STL)中的一个算法,用于在有序范围内查找某个值是否存在。它基于二分查找算法,时间复杂度为O(logn)。std::binary_search的基本用法:  boolbinary_search(ForwardIteratorfirst,ForwardIteratorlast,constT&value);first:指......
  • C++学习随笔——什么是迭代器
    迭代器是C++标准模板库(STL)中用于遍历容器元素的对象或概念。它们提供了一种通用的方式来访问容器中的元素,而不需要了解容器的底层实现。迭代器在设计上类似于指针,但功能更为强大和灵活。 1.迭代器是什么?迭代器是一个抽象概念,它为容器(如vector、list等)提供了一种统......
  • CSEC:香港城市大学提出SOTA曝光矫正算法 | CVPR 2024
    在光照条件不佳下捕获的图像可能同时包含过曝和欠曝。目前的方法主要集中在调整图像亮度上,这可能会加剧欠曝区域的色调失真,并且无法恢复过曝区域的准确颜色。论文提出通过学习估计和校正这种色调偏移,来增强既有过曝又有欠曝的图像。先通过基于UNet的网络推导输入图像的增亮和变暗......
  • QT/C++中的GDAL多线程应用(读取):发生的问题以及解决方案
    1.引言在使用GDAL库对TIF文件进行切割和创建瓦片金字塔时,为了提高创建效率,不得不考虑使用多线程处理。然而,在实际实现过程中,我遇到了许多问题。通过不断的尝试和优化,最终找到了有效的解决方案。本文将详细记录这一过程中的问题和解决方法。2.初始多线程尝试与问题2.1......
  • VTK随笔七:VTK图像处理(图像基本操作)
    VTK图像基本操作一、图像信息的访问与修改1、利用vtkImageData的方法 vtkSmartPointer<vtkBMPReader>reader=vtkSmartPointer<vtkBMPReader>::New();reader->SetFileName("D:/data/lena.bmp");reader->Update();intdims[3];reader......
  • 南沙C++陈老师讲题:1078:求分数序列和
    ​【题目描述】【输入】输入有一行,包含一个正整数n(n≤30)n(n≤30)。【输出】输出有一行,包含一个浮点数,表示分数序列前nn项的和,精确到小数点后44位。【输入样例】2【输出样例】3.5000#include<iostream>#include<stdio.h>usingnamespacestd;intmain()......
  • STL所有常用算法(全网最详细,一文全掌握,建议收藏)
    目录1.分类和介绍2.遍历算法2.1for_each算法(遍历执行)2.2transform算法(搬运)3.查找算法3.1find算法(具体查找)3.2find_if算法(条件查找)3.3 adjacent_find(查找相邻重复元素)3.4 binary_search(二分查找有序序列中元素是否存在)3.5 count(统计元素出现次数)3.6 coun......
  • 主成分分析结合遗传算法优化的随机森林通用代码
    importpandasaspdfromsklearn.preprocessingimportStandardScalerfromsklearn.decompositionimportPCAfromsklearn.ensembleimportRandomForestClassifier,RandomForestRegressorfromsklearn.metricsimportaccuracy_score,mean_squared_error,mean_abso......
  • 二叉树的层序遍历 C++
    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。(即逐层地,从左到右访问所有节点)。示例1:输入:root=[3,9,20,null,null,15,7]输出:[[3],[9,20],[15,7]]示例2:输入:root=[1]输出:[[1]]示例3:输入:root=[]输出:[]classSolution{public:vector<vect......
  • 根据二叉树创建字符串 C++
    给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。空节点使用一对空括号对 "()" 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。示例1:输入:root=[1,2,3,4]输出:"1......