专栏首页Java小白成长之路字符串排序---字典序

字符串排序---字典序

本周我们分享一个获取全排列的算法。这道题当时也是花了蛮久的时间才跟着题解写出来!小白经历了这道题目的“煎熬”之后,就为大家保驾护航,一起轻松拿下此题吧!


我们先来介绍一下此次运用的这道题目的核心思想:字典序排列

字典序

算法示意图

我们先把算法图摆出来给大家参考一下!

整个算法的核心就是按照我们的整体的从小到大的顺序来进行全排列,比如:123-->132-->213-->231-->312-->321

完成这段全排列流程的步骤主要有以下几步

  1. 需要对给定的序列进行排序,得到一个有序数组(一般认为是从小到大的)
  2. 从右向左开始寻找一个第一个A[i]<A[i+1]
  3. 继续从左向右寻找都一个满足A[i]>A[j]关系的元素,交换A[i]A[j]
  4. 对A[i]之后的元素进行翻转(也就是从小到大排序),得到一个新的排列。重复2~4
  5. 当无法再进行找到满足A[i]<A[i+1]关系的数据时,整个全排列便已经被全部找完了。

经过上面的步骤,我们每次得到的排列组合也将会是一个从小到大排序的全排列组合!

字符串的排列

《剑指offer》--------- 字符串的排列 题目描述

题目描述

简言之就是找到一个给定字符串的全排列。

1、解决思路

根据我们上面介绍的字典序排列算法,就可以轻松的解决我们此次的问题啦!

2、代码实现

import java.util.ArrayList;
import java.util.Arrays;
//字典序
public class Solution {
    public ArrayList<String> Permutation(String str) {

        ArrayList<String> ans = new ArrayList<>();
        if(str == null || str.length() == 0) return ans;
        if(str.length() == 1) {
            ans.add(str);
            return ans;
        }

        char[] ch = str.toCharArray();
        Arrays.sort(ch);
        String s = new String(ch);
        ans.add(str);//此处是为了防止重复的字符串
        while(true){
            s = dic(s);
            if(!s.equals("stop")){
                ans.add(s);
            }else{
                break;
            }
        }
        return ans;
    }
    private String dic(String s){
        char[] ch = s.toCharArray();
        int len = ch.length;
        int left = len - 2;
        //从右向左寻找第一个小于右边元素的索引
        for(;left >=0;left--){
            if(ch[left] < ch[left +1]){
                break;
            }
        }
        //判断是否已经越界
        if(left == -1){
            return "stop";
        }
        //从右边寻找大于left的最小元素
        int right = len - 1;
        for(;right > left ; right--){
            if(ch[left] < ch[right]){
                break;
            }
        }
        //交换left和right位置
        char temp = ch[left];
        ch[left] = ch[right];
        ch[right] = temp;
        //翻转left后面的字符串
        for(int a = left+1,b=len-1;a < b ;a++,b--){
            temp = ch[a];
            ch[a] = ch[b];
            ch[b] = temp;
        }
        return new String(ch);
    }
}

本文分享自微信公众号 - Java小白成长之路(Java_xiaobai),作者:鹏程万里

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 逆序对-----归并排序

    本周遇到了一道蛮有意思的题目,分享给大家欣赏一下!这道题使用归并排序。原来在力扣上刷题时,也遇到过一次归并的思路,不过当时一知半解,就跳过去了,心想着以后遇到了...

    鹏-程-万-里
  • 第52次文章:AJAX & json

    新年快乐呀!时间太快,好好抓紧时间学习吧!哈哈!这周我们看一下同步和异步的技术点~

    鹏-程-万-里
  • 第14次文章:网络编程完善+注解

    小白这周把网络编程最后的一部分给结束了,然后接触了注解的内容。开始下一阶段的内容学习。fighting!!!

    鹏-程-万-里
  • 百家号爬取(3)

    Centy Zhao
  • 未能加载文件或程序集“log4net, Version=2.0.8.0

    System.IO.FileLoadException HResult=0x80131040 Message=未能加载文件或程序集“log4net, Ver...

    静心物语313
  • 『深度思考』对CenterNet的一些思考与质疑·测试对比CenterNet与U版YoloV3速度与精度

    笔者很喜欢CenterNet极简的网络结构,CenterNet只通过FCN(全卷积)的方法实现了对于目标的检测与分类,无需anchor与nms等复杂的操作高效的...

    小宋是呢
  • LeetCode 605. 种花问题

    假设你有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花卉不能种植在相邻的地块上,它们会争夺水源,两者都会死去。

    Michael阿明
  • go语言数组的拷贝

    go语言的数组与c语言的数据有一点不太一样的地方,go语言的赋值是值拷贝 package main import "fmt" func main...

    李海彬
  • 重构到什么时候可以停止了?

    重构会优化代码内部结构,也就是让代码设计变得更好。所以要回答这个问题?也就要搞清楚,什么设计是恰到好处的?

    袁慎建@ThoughtWorks
  • 每日两题 T20

    数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

    合一大师

扫码关注云+社区

领取腾讯云代金券