【剑指offer第16天】排序

【剑指offer第16天】排序
x+y > y+x 那么x>y x大于y那么x应排在y的右边,这里要重写快速排序算法。

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0;i < nums.length;i++){
            strs[i] = String.valueOf(nums[i]);
        }
        quicksort(strs,0,nums.length-1);
        StringBuilder res = new StringBuilder();
        for(int i = 0;i < nums.length;i++){
            res.append(strs[i]);
        }
        return res.toString();
    }
    void quicksort(String[] strs,int l,int r){
        if(l >= r){return;}
        int i = l;
        int j = r;
        String pivot = strs[i];
        while(i < j){
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            String tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[l] = strs[i];
        strs[i] = pivot;
        quicksort(strs, l, i - 1);
        quicksort(strs, i + 1, r);
    }
}

快排,要注意最后的将low值更新和找到pivot变量的正确位置i

    public static void quickSort(int[] arr, int low, int high) {
            if (low > high)     return;
            int i = low;
            int j = high;
            int pivot = arr[low];
            
            while (i < j) {
                while(arr[j] >= pivot && i < j)     -- j;
                while(arr[i] <= pivot && i < j)     ++ i;
                if (i < j) {
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }
            }
            arr[low] = arr[i];
            arr[i] = pivot;
            quickSort(arr, low, j - 1);
            quickSort(arr, j + 1, high);
    }

【剑指offer第16天】排序
只要最大值-最小值<5且没有重复数字就可以(大小王的0可以重复)

class Solution {
    public boolean isStraight(int[] nums) {
        int l = nums.length;
        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])return false;
        }
        return (nums[4] - nums[joker]) < 5;
    }
}
上一篇:LeetCode热题Hot-24 最长公共前缀


下一篇:截取url参数