Daily question brushing record (10)

The first question is : The finger of the sword Offer II 072. take a square root

LeetCode: The finger of the sword Offer II 072. take a square root

describe :
Given a nonnegative integer x , Calculate and return x The square root of , I.e. implementation int sqrt(int x) function .

There are two square roots of a positive number , Output only the square root of the positive number .

If the square root is not an integer , The output retains only the integer part , The decimal part will be removed .

Their thinking :

1. Here we use dichotomy
2. Every comparison mid * mid Less than or equal to x
   • If the current value is less than or equal to x, Give Way left = mid+1;
   • If the current value is greater than x, Give Way right = mid -1;
3. Eventually return left-1;

Code implementation :

class Solution {
    
    public int mySqrt(int x) {
    
        int left = 0;
        int right = x;
        while(left <= right) {
    
            int mid = left + (right - left) / 2;
            if ((long)mid * mid <= x) {
    
                left = mid + 1;
            }else {
    
                right = mid - 1;
            }
        }
        return left-1;
    }
}

The second question is : The finger of the sword Offer II 074. Merge range

LeetCode: The finger of the sword Offer II 074. Merge range

describe :
In array intervals Represents a set of intervals , The single interval is intervals[i] = [starti, endi] . Please merge all overlapping intervals , And return a non overlapping interval array , The array needs to cover exactly all the intervals in the input .

Their thinking :

1. First, sort according to the left boundary .
2. If the left boundary of the next range , Larger than the right boundary of the current range , Just put the current record left and right Add to the result set . And mark the current left Is the left boundary of the next range
3. Give Way right Mark , Current right boundary , And the maximum value of the right boundary of the next range ,
4. The result set is returned after traversal

Code implementation :

class Solution {
    
    public int[][] merge(int[][] intervals) {
    
    	//  Prioritize 
        Arrays.sort(intervals,(o1,o2)->o1[0]-o2[0]);
        List<int[]> res = new ArrayList<>();
        //  First record left and right
        int left = intervals[0][0];
        int right = intervals[0][1];
        for(int i = 1; i < intervals.length; i++) {
    
            if (right < intervals[i][0]) {
    
                //  When the left boundary of the next range is greater than the boundary of the previous range ,  Add result set ,  And re mark the position of the left boundary .
                res.add(new int[]{
    left,right});
                left = intervals[i][0];
            }
            //  Record the position of the maximum right boundary 
            right = Math.max(intervals[i][1],right);
        }
        //  You need to add one more time ,  I didn't join in the last time 
        res.add(new int[]{
    left,right});
        int[][] ans = new int[res.size()][];
        for(int i = 0; i < res.size(); i++) {
    
            ans[i] = res.get(i);
        }
        return ans;
    }
}

Third question : The finger of the sword Offer II 075. Array relative sort

LeetCode: The finger of the sword Offer II 075. Array relative sort
describe :
Given two arrays ,arr1 and arr2,

• arr2 The elements in are different
• arr2 Every element in appears in arr1 in

Yes arr1 The elements in are sorted , send arr1 The relative order of the middle terms and arr2 The relative order in is the same . Not in arr2 The elements that appear in should be placed in ascending order arr1 At the end of .

Their thinking :

• First use an array tmp , Record arr1 The number of occurrences of each element in .
• Re traversal arr2 Array , see tmp The number of occurrences of this element in , Then add it to the result array res
• And then go through tmp. see tmp The rest of the elements in , Add to res in , Because it is added according to coordinates , So automatic sorting .

Code implementation :

class Solution {
    
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
    
    	//  Use here tmp Array to record the number of occurrences of each element 
        int[] tmp = new int[1001];
        for (int val : arr1) {
    
            tmp[val]++;
        }
        int index = 0;
        int[] res = new int[arr1.length];
        //  according to arr2 The order of ,  Add elements to the result array ,  Appear several times and join several 
        for(int val : arr2) {
    
            while(tmp[val]-- != 0) {
    
                res[index++] = val;
            }
        }
        //  The remaining elements ,  Is what needs to be added .
        for(int i = 0; i < 1001; i++) {
    
            if(tmp[i] != 0) {
    
                while(tmp[i]-- > 0) {
    
                    res[index++] = i;
                }
            }
        }
        return res;
    }
}

Fourth question : The finger of the sword Offer II 076. The... In the array k Big numbers

LeetCode: The finger of the sword Offer II 076. The... In the array k Big numbers

describe :
Given an array of integers nums And integer k, Please return the... In the array k The biggest element .

Please note that , What you need to look for is the number after array sorting k The biggest element , Not the first. k A different element .

Their thinking :

1. Priority queues are used here . Create a size of k Small roots .
2. When the queue size is smaller than k When , Directly into the reactor
3. When the queue size is greater than or equal to k When , Compare the size of the element with that of the top of the heap .
   • When the element is larger than the top of the heap , Out of the top element . Then put the element on the heap

Code implementation :

class Solution {
    
    public int findKthLargest(int[] nums, int k) {
    
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        for(int i = 0; i < k; i++) {
    
            pq.offer(nums[i]);
        }
        for(int i = k; i < nums.length; i++) {
    
            if(nums[i] > pq.peek()) {
    
                pq.poll();
                pq.offer(nums[i]);
            }
        }
        return pq.peek();
    }
}

Fifth question : The finger of the sword Offer II 035. Minimum time difference

LeetCode: The finger of the sword Offer II 035. Minimum time difference

describe :
Given a 24 hourly （ Hours : minute “HH:MM”） Time list for , Find the minimum time difference between any two times in the list and express it in minutes .

Their thinking :

1. First, convert the time string into minutes
2. And then sort it ,
3. Note here , 00:01 and 23:59, The time difference , Will be omitted , terms of settlement Is to add the minimum time 24*60.
4. Then they calculate the time difference , Record the minimum time difference

Code implementation :

class Solution {
    
    public int findMinDifference(List<String> timePoints) {
    
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < timePoints.size(); i++) {
    
            list.add(getMin(timePoints.get(i)));
        }
        Collections.sort(list);
        list.add(list.get(0) + 24*60);
        int res = Integer.MAX_VALUE;
        for(int i = 1; i < list.size(); i++) {
    
            res = Math.min(res,list.get(i)-list.get(i-1));
        }
        return res;
    }
    public int getMin(String str) {
    
        String[] time = str.split(":");
        return Integer.parseInt(time[0])*60 +Integer.parseInt(time[1]);
    }
}

Sixth question : The finger of the sword Offer II 034. Whether alien languages are sorted

LeetCode: The finger of the sword Offer II 034. Whether alien languages are sorted

describe :
Some alien languages also use small letters in English , But it may be in order order Different . The order of the alphabet （order） It's an arrangement of small letters .

Given a set of words written in alien language words, And the order of its alphabet order, Only when given words are arranged in dictionary order in this alien language , return true; otherwise , return false.

Their thinking :

1. according to order The order in which strings appear , Use an array arr To record .
2. Compare two strings , First, compare the order of occurrence of each position element
   • If left<rigth, Indicates that the conditions are met , Continue to compare the next two strings
   • If left>right, Directly return if the condition is not met false
   • If the previous strings are equal , for example ww and www, Then compare the length of two strings .

Code implementation :

class Solution {
    
    public boolean isAlienSorted(String[] words, String order) {
    
        int[] arr = new int[26];
        for(int i = 0; i < order.length(); i++) {
    
            arr[order.charAt(i)-'a'] = i;
        }
        for(int i = 1; i < words.length; i++) {
    
            boolean flg = true;
            for(int j = 0; j < words[i-1].length() && j < words[i].length() ; j++) {
    
                int left = arr[words[i-1].charAt(j)-'a'];
                int right = arr[words[i].charAt(j)-'a'];
                if (left < right) {
    
                    flg = false;
                    break;
                }else if (left > right) {
    
                    return false;
                }
            }
            if (flg) {
    
                if (words[i-1].length() > words[i].length()){
    
                    return false;
                }
            }
        }
        return true;
    }
}