秦怀杂货店

General Store

  • 首页
  • 文章归档
  • 标签
  • 分类
  • 关于页面

  • 搜索
随便聊聊 数据结构 小游戏 数据库 Docker Springboot 系统设计 雪花算法 分布式 海量ip 最长回文子串 算法 面试题 线程池 多线程 线程 java学习 布隆过滤器 github 架构设计 docsify Git JVM LeetCode 杂货思考 设计模式 Lambda native isAssignableFrom 反射 剑指Offer mybatis SPI JDBC 编程工具 Java基础 集合

剑指Offer【27】-- 字符串的排序

发表于 2020-12-26 | 分类于 剑指Offer | 0 | 阅读次数 274

[toc]

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路以及解析

使用回溯,通过交换字符实现,主要重复元素需要跳过。步骤:

  • 将字符串分为两部分,首字符和剩下字符。
  • 将首字符和其他的字符进行交换,并以剩下的元素组成的字符串进行递归全排列。
  • 直到交换完最后一个元素的时候,结束。
import java.util.ArrayList;
import java.util.Comparator;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> results = new ArrayList<>();
        if (str != null && str.length() > 0) {
            char[] chars = str.toCharArray();
            process(chars, results, 0);
        }
        results.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });
        return results;
    }

    private void process(char[] chars, ArrayList<String> results, int index) {
        if (index == chars.length - 1) {
            if (!results.contains(new String(chars))) {
                results.add(new String(chars));
                return;
            }
        } else {
            for (int j = index; j < chars.length; j++) {
                swap(chars, index, j);
                process(chars, results, index + 1);
                swap(chars, index, j);
            }
        }
    }

    // 交换
    private void swap(char[] str, int i, int j) {
        if (i != j) {
            char t = str[i];
            str[i] = str[j];
            str[j] = t;
        }
    }
}

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

技术之路不在一时,山高水长,纵使缓慢,驰而不息。

公众号:秦怀杂货店

  • 本文作者: 秦怀杂货店
  • 本文链接: http://aphysia.cn/archives/jianzhioffer27
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 随便聊聊 # 数据结构 # 小游戏 # 数据库 # Docker # Springboot # 系统设计 # 雪花算法 # 分布式 # 海量ip # 最长回文子串 # 算法 # 面试题 # 线程池 # 多线程 # 线程 # java学习 # 布隆过滤器 # github # 架构设计 # docsify # Git # JVM # LeetCode # 杂货思考 # 设计模式 # Lambda # native # isAssignableFrom # 反射 # 剑指Offer # mybatis # SPI # JDBC # 编程工具 # Java基础 # 集合
设计模式【1】-- 单例模式到底几种写法?
设计模式【1.1】-- 你想如何破坏单例模式?
  • 文章目录
  • 站点概览
秦怀杂货店

秦怀杂货店

纵然缓慢,驰而不息。

145 日志
19 分类
37 标签
Github E-mail
Creative Commons
0%
© 2022 秦怀杂货店
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4