专栏首页mathor给定一个字符串数组,按照字典顺序进行从小到大的排序

给定一个字符串数组,按照字典顺序进行从小到大的排序

 假设字符串数组是str[] = {"ab","cd","ef"},很明显答案就是”abcdef“最小,其实这是一道贪心问题,我的想法是将字符串数组进行内的字符串数组进行排序,这个大思路是没错的,但问题是怎么排序,str[i] < str[j]?这样其实不行,举个反例str[] = {"b","ba"},如果按照那个贪心策略排序,得到的答案是"bba",但实际上“bab”更小,后来仔细以想,贪心策略应该是str[i] + str[j] < str[j] + str[i],有兴趣的大家可以下去证明,还是比较好证的

import java.util.*;

public class Main {
    public static class MyCompara implements Comparator<String> {
        public int compare(String s1, String s2) {
            String tmp1 = s1 + s2;
            String tmp2 = s2 + s1;
            return tmp1.compareTo(s2);
        }
    }
    public static String minString(String[] str) {
        String res = "";
        Arrays.sort(str,new MyCompara());
        for(int i = 0;i < str.length;i++)
            res += str[i];
        return res;
    }
    public static void main(String[] args) {
        System.out.println(minString(new String[] {"ab","ef","cd"}));
    }
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Set

    mathor
  • 泛型

    mathor
  • File

    mathor
  • Java知识点——函数式接口

    用户7073689
  • 函数式接口小结

    如果说一个接口内有且只有一个方法,而且该方法是一个缺省属性为public abstract方法,该接口可以称之为是一个函数式接口。

  • 使用位运算、值交换等方式反转java字符串-共四种方法

    在本文中,我们将向您展示几种在Java中将String类型的字符串字母倒序的几种方法。

    字母哥博客
  • 【005期】JavaSE面试题(五):String类

    大家好,我是Java面试题库的提裤姐,本篇文章是面试系列文章的第五篇,主要介绍了JavaSE中String相关的面试题,在之后会顺着开篇的思维导图一直总结下去,...

    java进阶架构师
  • StringUtils的源码解析

    爱撒谎的男孩
  • 剑指Offer-左旋转字符串

    package String; /** * 左旋转字符串 * 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令...

    武培轩
  • js去掉字符串前后空格的五种方法

    第一种:循环检查替换 [javascript] //供使用者调用   function trim(s){   return trimRight(trimLeft...

    joshua317

扫码关注云+社区

领取腾讯云代金券