剑指 Offer 45. 把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:
输入: [10,2] 输出: “102”
示例 2:
输入: [3,30,34,5,9] 输出: “3033459”

提示:

  • 0 < nums.length <= 100

说明:

  • 输出结果可能非常大，所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

思路：
a, b的最小排列为：
若ab < ba => a < b
否则b < a

  1. class Solution {
  2.     public String minNumber(int[] nums) {
  3.         List<Integer> res = new ArrayList<>();
  4.         for (int x : nums) res.add(x);
  5.         Collections.sort(res, this::compare);
  6.         StringBuilder sb = new StringBuilder();
  7.         for (int x : res) sb.append(x);
  8.         return sb.toString();
  9.     }
  11.     int compare(Integer a, Integer b) {
  12.         String s = a + "" + b, t = b + "" + a;
  13.         return s.compareTo(t);
  14.     }
  15. }

761. 特殊的二进制序列

难度困难116收藏分享切换为英文接收动态反馈
特殊的二进制序列是具有以下两个性质的二进制序列：

  • 0 的数量与 1 的数量相等。
  • 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)
在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？
示例 1:
输入: S = “11011000” 输出: “11100100” 解释: 将子串 “10” （在S[1]出现） 和 “1100” （在S[3]出现）进行交换。 这是在进行若干次操作后按字典序排列最大的结果。
说明:

  1. S 的长度不超过 50。
  2. S 保证为一个满足上述定义的特殊 的二进制序列。

思路：
将字符串分割成一个个子特殊字符串，递归处理每个子特殊字符串
将所有特殊字符串按最大字典序排列

  1. class Solution {
  2.     public String makeLargestSpecial(String s) {
  3.         if (s.length() == 0) return "";
  4.         StringBuilder sb = new StringBuilder();
  5.         List<String> res = new ArrayList<>();
  6.         Deque<Character> stk = new ArrayDeque<>();
  8.         for (int i = 0; i < s.length(); i++) {
  9.             char c = s.charAt(i);
  10.             sb.append(c);
  11.             if (c == '1')
  12.                 stk.push(c);
  13.             else {
  14.                 stk.pop();
  15.                 if (stk.isEmpty()) {
  16.                     res.add("1" + makeLargestSpecial(sb.substring(1, sb.length() - 1)) + "0");
  17.                     sb.delete(0, sb.length());
  18.                 }
  19.             }
  20.         }
  22.         Collections.sort(res, (o1, o2) -> ((o2 + o1).compareTo(o1 + o2)));
  23.         StringBuilder t = new StringBuilder();
  24.         for (String v : res) {
  25.             t.append(v);
  26.         }
  27.         return t.toString();
  28.     }
  29. }