Day16_数组排序_剑指Offer

把数组排成最小的数

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

示例：

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

限制：

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

解题思路

返回凭借的最小字符（数值），按题目示例来看，我们需要将数组高位代表的值尽可能小的排字符前方，比如同样长度，以3开头一定小于以5开头，同时也需要后

几位尽可能的小，如 3 和 30 可以组合 330 和 303，30的个位0位于组合后的十位显然比位于组合都的个位更小

简而言之，需要我们自行给数组按特定要求排序

实现数与数的对比，能够量化一种标准判断排序要求

特定要求：xy > yx 时，y在前，x在后，判断返回大值

实现：构建StringBuilder类，实现 xy 与 yx ，考虑到数据过大，转为Long类型对比大小（tips：受教Java中的BigInteger或许可以更加安全的检验）

xy大时返回x，否则返回y

实现排序：相邻两两对比–可以使用冒泡排序

实现：遍历数组，使用冒泡排序将大值不断后送，缩短排序区间

Java代码

class Solution {
    public String minNumber(int[] nums) {
        StringBuilder ans = new StringBuilder();
        // 冒泡排序
        for(int i=nums.length-1; i>0; i--) {
            for(int j=0; j<i; j++) {
                if(findBigOne(nums[j],nums[j+1]) == nums[j])
                    swap(nums, j, j+1); 
            }
        }
        for(int num : nums)
            ans.append(num);
        return ans.toString();
    }

    // 返回相邻两个数中，组合位于前端时后会带来更大结果的值
    public int findBigOne(int m, int n) {
        StringBuilder a = new StringBuilder();
        StringBuilder b = new StringBuilder();
        a.append(m);
        a.append(n);
        b.append(n);
        b.append(m);
        return a;
        if(Long.valueOf(a.toString()).compareTo(Long.valueOf(b.toString())) == 1)
            return m;
        return n;
    }

    // 交换函数
    public void swap(int[] nums ,int i, int j) {
        int mid = nums[i];
        nums[i] = nums[j];
        nums[j] = mid;
    }
}

扑克牌中的顺子

Esay 原题连接：扑克牌中的顺子

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例：

输入: [1,2,3,4,5]
输出: True
输入: [0,0,1,2,5]
输出: True

提示：

数组长度为 5
数组的数取值为 [0, 13] .

解题思路

相邻且连续的五个值，且本身数值量不大（0-13），题目可以使用一点取巧的方式

既然是五个连续的值，那么最大值与最小值的差一定不会超过4
需要考虑到0的存在：已有最大最小，差为4，零用于补充中间；缺少最大或最小，差小于4，零用于补两边
保证数组中不存在相同的值，否则直接返回false

实现上就很好说了，找到最大和除去0的最小值，判断是否有重复值，判断差值是否大于4，都为否返回true，否则返回false

Java代码

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int min = 14;
        int max = nums[nums.length - 1];
        for(int i=0; i<nums.length-1; i++) {
            if(nums[i] != 0 && nums[i]<min) min = nums[i];
            if(nums[i] != 0 && nums[i] == nums[i+1]) return false;
        }
        if((max - min) > 4)return false;
        return true;
    }
}