Sword finger offer 45.61 Sort (simple)

45.

subject :

The finger of the sword Offer 45. Make the array the smallest number https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

  idea : Custom sort . First convert to a string array , Then arrange the string order by quick sort .

Reference resources : Power button k god

  Code :

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]);
        //  Quick sort 
        quickSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
    // Quick line up 
    private String[] quickSort(String[] strs, int low, int high) {
        if (low < high) {
            // Use datum , Each express train will low-high In two parts 
            int base = partition(strs, low, high);
            quickSort(strs, low, base - 1);
            quickSort(strs, base + 1, high);
        }
        return strs;
    }
    //  Partition , Returns the size boundary 
    public int partition(String[] strs, int low, int high) {
        int base = low;
        String baseValue = strs[low];
        while (low < high) {
            //  Compare   Increasing 
            //  Be careful to move first high Move back low
            while(low < high &&(strs[high] + strs[base]).compareTo(strs[base] + strs[high]) >= 0)
                high--;
            while(low < high && (strs[low] + strs[base]).compareTo(strs[base] + strs[low]) <= 0)
                low++;
            //  The top two while It also limits low<high, So there won't be low>high
            String tmp = strs[low];
            strs[low] = strs[high];
            strs[high] = tmp;
        }
        strs[base] = strs[low];
        strs[low] = baseValue;
        // Return to the new dividing line 
        return low;
    }
}

result :

 

61.

subject :

The finger of the sword Offer 61. Shunzi in playing cards https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/

 

  idea : This question has nothing to do with playing cards , Is whether it can form shunzi , as well as 0 Can replace other cards .

         I wrote it : Insert sort first , Secondly, count the spacing of cards gap Quantity and sum 0 The number of , Judge the situation again .

         Reference resources k god : Just judge the interval between the largest and smallest cards . The biggest one is the last one , The smallest subscript is joker Number .

Code :

// I :
class Solution {
    public boolean isStraight(int[] nums) {
        int pre,cur;
        // Insertion sort 
        for(int i=1;i<nums.length;i++){
            pre=i-1;
            cur=nums[i];
            while(pre>=0 && nums[pre]>cur){
                nums[pre+1]=nums[pre];
                pre--;
            }
            nums[pre+1]=cur;
        }
        // Traverse 
        int zeros=0;
        int gaps=0;
        if(nums[0]==0)
            zeros++;
        for(int i=1;i<nums.length;i++){
            if(nums[i]==0)
                zeros++;
            else if(nums[i]==nums[i-1])
                return false;
            else if(nums[i-1]!=0)
                gaps=gaps+nums[i]-nums[i-1]-1;
        }
        if(gaps<=zeros||gaps==0)
            return true;
        else
            return false;
    }
}

// Reference resources :
class Solution {
    public boolean isStraight(int[] nums) {
        int joker = 0;
        Arrays.sort(nums); //  Array sorting 
        for(int i = 0; i < 4; i++) {
            if(nums[i] == 0) joker++; //  Count the number of size Kings 
            else if(nums[i] == nums[i + 1]) return false; //  If there's a repetition , Return early  false
        }
        return nums[4] - nums[joker] < 5; //  Top brand  -  The smallest card  < 5  Then it can form shunzi 
    }
}

result :