有趣的自定义排序算法

连接二进制表示可形成的最大数值

给你一个长度为 3 的整数数组 nums。

现以某种顺序 连接 数组 nums 中所有元素的 二进制表示 ，请你返回可以由这种方法形成的 最大 数值。

注意 任何数字的二进制表示 不含 前导零。

想到了一点排序，但是不知道怎么排，就暴力做了，很蠢的先把每个数转化为二进制字符串，再依次连接比较大小

class Solution {
    public int maxGoodNumber(int[] nums) {
        String[] s = new String[3];
        for (int i = 0; i < 3; ++ i) {
            s[i] = Integer.toBinaryString(nums[i]);
            // System.out.print(s[i] + " ");
        }
        int res = Math.max(Integer.parseInt(s[0] + s[1] + s[2], 2), Math.max(Integer.parseInt(s[0] + s[2] + s[1], 2), Math.max(Integer.parseInt(s[1] + s[2] + s[0], 2), Math.max(Integer.parseInt(s[1] + s[0] + s[2], 2), Math.max(Integer.parseInt(s[2] + s[0] + s[1], 2), Integer.parseInt(s[2] + s[1] + s[0], 2))))));
        return res;
    }
}

排序，自定义的排序逻辑是两个数字一前一后拼接，比如ab和ba，谁大谁排前面

class Solution {
    public int maxGoodNumber(int[] nums) {
        Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, (a, b) -> {
            int lenA = 32 - Integer.numberOfLeadingZeros(a);
            int lenB = 32 - Integer.numberOfLeadingZeros(b);
            return (b << lenA | a) - (a << lenB | b);
        });
        int res = 0;
        for (int x : arr) {
            res = res << (32 - Integer.numberOfLeadingZeros(x)) | x;
        }
        return res;
    }
}

破解闯关密码

闯关游戏需要破解一组密码，闯关组给出的有关密码的线索是：

• 一个拥有密码所有元素的非负整数数组 password
• 密码是 password 中所有元素拼接后得到的最小的一个数

请编写一个程序返回这个密码。

示例 1:

输入: password = [15, 8, 7]
输出: "1578"

示例 2:

输入: password = [0, 3, 30, 34, 5, 9]
输出: "03033459"

class Solution {
    public String crackPassword(int[] password) {
        String[] arr = Arrays.stream(password).mapToObj(String::valueOf).toArray(String[]::new);
        Arrays.sort(arr, (a, b) -> {
            return (a + b).compareTo(b + a);
        });
        String res = "";
        for (String s : arr) {
            res += s;
        }
        return res;
    }
}

最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

跟上面那题一模一样，注意处理一下特殊为0的情况

class Solution {
    public String largestNumber(int[] nums) {
        String[] arr = Arrays.stream(nums).mapToObj(String::valueOf).toArray(String[]::new);
        Arrays.sort(arr, (a, b) -> {
            return (b + a).compareTo(a + b);
        });
        if (arr[0].equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        for (String t : arr) {
            sb.append(t);
        }
        return sb.toString();
    }
}

有趣的来了，快排 + 数学

比如：int x = 12; int y = 345
x 拼接 y = 12345 = 12 * 1000 + 345 = x * 1000 + y;
y 拼接 x = 34512 = 345 * 100 + 12 = y * 100 + x;
上面的1000是哪里来的？因为y是3位数。上面的100是哪里来的？因为x是2位数；明白这个思想就能写出代码了

class Solution {
    public String largestNumber(int[] nums) {
        quick_sort(nums, 0, nums.length - 1);
        StringBuilder sb = new StringBuilder();
        if (nums[0] == 0) {
            return "0";
        }
        for (int t : nums) {
            sb.append(t);
        }
        return sb.toString();
    }

    private void quick_sort(int[] nums, int low, int high) {
        if (high <= low) {
            return;
        }
        int pivot = nums[high];
        int i = low;
        for (int j = low; j < high; j++) {
            long x = 10, y = 10;
            while (nums[j] >= x) x *= 10; //计算nums[j]排后面时前面那个数需要乘的进位
            while (pivot >= y) y *= 10;
            if (nums[j] * y + pivot > pivot * x + nums[j]) {//逆序，大的在前面
                swap(nums, i, j);
                i ++;
            }
        }
        swap(nums, i, high);
        quick_sort(nums, low, i - 1);
        quick_sort(nums, i + 1, high);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

快排 + 字符串拼接 跟上面思想是一样的，就不写了