贪心算法——最低字典序，从头到尾利用贪心算法求解

package com.harrison.class09;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
public class Code01_LowestLexicography {
  // strs 放着所有的字符串
  // use  已经使用过的字符串的下标，在use里登记过了，不要再使用了
  // path 之前已经使用过的字符串，拼接成了path
  // all  收集所有可能拼接的结果
  public static void process1(
      String[] strs, HashSet<Integer> use,String path,ArrayList<String> all) {
    // 所有字符串都已经使用过了，path就是拼接的一种结果
    if(use.size()==strs.length) {
      all.add(path);
    }else {// strs里的字符串还没有使用完，遍历strs中所有的字符串
      for(int i=0; i<strs.length; i++) {
        if(!use.contains(i)) {// 如果当前的字符串是没有使用过的，将其加入到use里
          use.add(i);
          // 每一个没有使用过的字符串都这么处理
          process1(strs, use, path+strs[i], all);
          // 恢复现场！！！（深度优先遍历的常见做法）
          use.remove(i);
        }
      }
    }
  }
  // 暴力解：全排列
  public static String lowestLexicography1(String[] strs) {
    if(strs==null || strs.length==0) {
      return "";
    }
    ArrayList<String> all=new ArrayList<>();
    HashSet<Integer> use=new HashSet<>();
    process1(strs, use, "", all);
    String lowest=all.get(0);
    for(int i=1; i<all.size(); i++) {
      if(all.get(i).compareTo(lowest)<0) {
        lowest=all.get(i);
      }
    }
    return lowest;
  }
  public static class Comparator implements java.util.Comparator<String>{
    @Override
    public int compare(String a, String b) {
      return (a+b).compareTo(b+a);
    }
  }
  public static String lowestLexicography2(String[] strs) {
    if(strs==null || strs.length==0) {
      return "";
    }
    Arrays.sort(strs, new Comparator());
    String ans="";
    for(int i=0; i<strs.length; i++) {
      ans+=strs[i];
    }
    return ans;
  }
  public static String generateRandomString(int strLen) {
    char[] ans = new char[(int) (Math.random() * strLen) + 1];
    for (int i = 0; i < ans.length; i++) {
      int value = (int) (Math.random() * 5);
      ans[i] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);
    }
    return String.valueOf(ans);
  }
  public static String[] generateRandomStringArray(int arrLen, int strLen) {
    String[] ans = new String[(int) (Math.random() * arrLen) + 1];
    for (int i = 0; i < ans.length; i++) {
      ans[i] = generateRandomString(strLen);
    }
    return ans;
  }
  public static String[] copyStringArray(String[] arr) {
    String[] ans = new String[arr.length];
    for (int i = 0; i < ans.length; i++) {
      ans[i] = String.valueOf(arr[i]);
    }
    return ans;
  }
  public static void main(String[] args) {
    int arrLen = 6;
    int strLen = 5;
    int testTimes = 10000;
    System.out.println("test begin");
    for (int i = 0; i < testTimes; i++) {
      String[] arr1 = generateRandomStringArray(arrLen, strLen);
      String[] arr2 = copyStringArray(arr1);
      if (!lowestLexicography1(arr1).equals(lowestLexicography2(arr2))) {
        for (String str : arr1) {
          System.out.print(str + ",");
        }
        System.out.println();
        System.out.println("Oops!");
      }
    }
    System.out.println("finish!");
  }
}