「剑指Offer」Day16：排序（简单）

题目描述

输入: [3,30,34,5,9] 输出: "3033459"

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

思路

• 若拼接字符串x+y > y+x  ，则 x “大于” y ；
• 反之，若 x+y < y+x ，则 x “小于” y；
  

参考题解：链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/

方法一：快速排序

class Solution {
    public String minNumber(int[] nums) {
        int length = nums.length;
        String[] strs = new String[length];
        for(int i = 0; i < length; i++){ //将整数转换为字符串存入一个字符串数组
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs, 0, length - 1);
        StringBuilder sbr = new StringBuilder();
        for(String str : strs){ //遍历拼接
            sbr.append(str);
        }
        return sbr.toString();
    }
    public void quickSort(String[] strs, int start, int end){ //快速排序
        if(start >= end){
            return;
        }
        int left = start;
        int right = end;
        String pivot = strs[start]; //确定基准元素
        while(left != right){
            //拼接基准元素，比较并交换
            while(left < right && (strs[right] + pivot).compareTo(pivot + strs[right]) >= 0){
                right--;
            }
            while(left < right && (strs[left] + pivot).compareTo(pivot + strs[left]) <= 0){
                left++;
            }
            if(left < right){
                String temp = strs[left];
                strs[left] = strs[right];
                strs[right] = temp;
            }
        }
        strs[start] = strs[left];
        strs[left] = pivot;
        int pivotIndex = left;
        quickSort(strs, start, pivotIndex - 1); //对左边继续进行分治
        quickSort(strs, pivotIndex + 1, end); //对右边继续进行分治
    }
}

方法二：调用内置函数

调用内置函数，根据排序判断规则进行排序，

class Solution {
    public String minNumber(int[] nums) {
        int length = nums.length;
        String[] strs = new String[length];
        for(int i = 0; i < length; i++){ //将整数转换为字符串存入一个字符串数组
            strs[i] = String.valueOf(nums[i]);
        }
        //调用内置函数，根据排序判断规则进行排序
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder sbr = new StringBuilder();
        for(String str : strs){ //遍历拼接
            sbr.append(str);
        }
        return sbr.toString();
    }
}

剑指 Offer 61. 扑克牌中的顺子

题目描述

输入: [0,0,1,2,5] 输出: True
说明：大、小王为 0 ，可以看成任意数字，有两个0，2到5之间刚好缺少3，4，可使用0代替

思路

1. 除大小王外，所有牌无重复 ；
2. 设此 5 张牌中最大的牌为 max，最小的牌为 min （大小王除外），则需满足：max-min < 5

代码实现

class Solution {
    public boolean isStraight(int[] nums) {
        int joker = 0; //大小王的数量
        Arrays.sort(nums); //排序
        for(int i = 0; i < 4; i++){
            if(nums[i] == 0){ //为大小王就累加数量
                joker++;
                continue;
            }
            if(nums[i] == nums[i+1]){ //有重复直接返回false
                return false;
            }
        }
        //此时joker标识的是最小值，要求最大值-最小值小于5，才为顺子
        return nums[4] - nums[joker] < 5;
    }
}