《剑指offer》---字符串的全排列
本文算法使用python3实现
1.问题一
1.1 题目描述:
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。(输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母)
时间限制:1s;空间限制:32768K
1.2 思路描述:
大致思路:按照我们人工手写全排列的方法,会先固定一个的字符,然后对剩余字符进行全排列,然后换一个字符固定,对其后面的剩余字符进行全排列。而每次对剩余字符进行全排列时,仍旧按照固定一个字符,全排列剩余字符的方法。因此这就是一个子问题,而结束的条件就是,只剩一个字符的时候。
1.3 程序代码:
(1)方法一
class Solution:
def Permutation(self, ss):
if ss == [] or len(ss) == 1:
return ss
res = []
for i in range(len(ss)):
for j in self.Permutation(ss[:i]+ss[i+1:]):
res.append(ss[i] + j)
return sorted(list(set(res)))
2.问题二
2.1 问题描述
原题:[leetcode]https://oj.leetcode.com/problems/next-permutation/
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
2.2 解题思路
输出字典序中的下一个排列。比如123生成的全排列是:123,132,213,231,312,321。那么321的next permutation是123。下面这种算法据说是STL中的经典算法。在当前序列中,从尾端往前寻找两个相邻升序元素,升序元素对中的前一个标记为partition。然后再从尾端寻找另一个大于partition的元素,并与partition指向的元素交换,然后将partition后的元素(不包括partition指向的元素)逆序排列。比如14532,那么升序对为45,partition指向4,由于partition之后除了5没有比4大的数,所以45交换为54,即15432,然后将partition之后的元素逆序排列,即432排列为234,则最后输出的next permutation为15234。
2.3 程序代码:
class Solution:
def nextPermutation(self, num):
len_num = len(num)
if len_num <= 1:
return num
partition = -1
for i in range(len_num-2, -1, -1):
if num[i] < num[i+1]:
partition = i
break
if partition == -1:
num.reverse()
return num
else:
for i in range(len_num-1, partition, -1):
if num[i] > num[partition]:
num[partition], num[i] = num[i], num[partition]
break
num[partition+1:len_num] = num[partition+1:len_num][::-1]
return num
最新文章
- CSS浮动、定位
- 新浪云SAE搭建python环境 问题拾遗
- JavaScript的前世今生
- AxureRP7.0各类交互效果汇总帖(转)
- RDLC系列之七 条码打印
- Scrapy安装介绍
- sql注入在线检测(sqlmapapi)
- ORA-15005: name ";orcl"; is already used by an existing alias
- 多项分布(multinominal distribution)
- mysql 账户操作
- Java导入证书失败Keystore was tampered with, or password was incorrect
- 高级PHP工程师所应该具备一些技能
- Java经典23种设计模式之创造型模式(一)
- 《Thinking in Java》 And 《Effective Java》啃起来
- Linux中nginx手动安装
- python:发送消息给微信企业号
- 初识maven及其安装步骤!!
- 【一天一道Leetcode】#190.Reverse Bits
- 既然还看不到未来之光,那就从骄阳开始的地方--IT携行
- 从零开始学安全(十五)●DHCP服务