Leetcode 244 week competition - post competition supplementary question solution [broccoli players]

Problem A- Judge whether the matrix is consistent after rotation

The question ： With 90 Degree clockwise rotation matrix mat The elements in Several times , If mat Matrix and target Agreement , return true, Otherwise return to false

Ideas ： Direct simulation is OK , When doing this problem, I also worked hard to write an in-situ Algorithm ,y God said it was unnecessary , Directly open a two-dimensional array .

Code ：

Java You cannot directly judge whether the contents of two two-dimensional arrays are the same , nausea ！

class Solution {
    
    public boolean findRotation(int[][] mat, int[][] target) {
    
        int n = mat.length, num = 3;
        boolean flag = false;
        for (int i = 0; i < n; i++){
    
            for (int j = 0; j < n; j++){
    
                if (mat[i][j] != target[i][j]) {
    
                    flag = true; break;
                }
            }
            if (flag)break;
        }
        if (!flag)return true;

        while(num-- > 0) {
    
            for(int i=0; i<n/2; i++) {
    
                 for(int j=i; j<n-i-1; j++) {
    
                     int t = mat[i][j];
                     mat[i][j] = mat[n-j-1][i];
                     mat[n-j-1][i] = mat[n-i-1][n-j-1];
                     mat[n-i-1][n-j-1] = mat[j][n-i-1];
                     mat[j][n-i-1] = t;
                 }
            }
            
            flag = false;
            for (int i = 0; i < n; i++){
    
                for (int j = 0; j < n; j++){
    
                    if (mat[i][j] != target[i][j]) {
    
                        flag = true; break;
                    }
                }
                if (flag)break;
            }
            if (!flag)return  true;
        }
        return false;
    }
}

Problem B- Making the elements of an array equal reduces the number of operations

Ideas ： Every element a Need experience t The three stages finally become equal minimum ,t Is the ratio element in the array a Small element types and . So first sort the array , Then count ( The element type smaller than him in front of the element can )

Code ：

class Solution {
    
    public int reductionOperations(int[] nums) {
    
        int len = nums.length;
        Arrays.sort(nums);
        int pre[] = new int[len + 1];
        int count = 0;
        pre[0] = 0;
        for (int i = 1; i < len; i++) {
    
            if ((nums[i] - nums[i-1]) != 0) {
    
                pre[i] = pre[i - 1] + 1;
            } else {
    
                pre[i] = pre[i - 1];
            }
        }
        //  The accumulation below can be put in the first for In circulation 
        int res = 0;
        for (int i = 1; i < len; i++) {
    
            res += pre[i];
        }
        return res;
    }
}

Problem C- The minimum number of inversions to alternate binary string characters

Ideas ： Two types of operations , Let's count the minimum number of operations of the second type . The particularity of the first type of operation , It makes me think of splicing the two original strings together , Then slide the window , Take the minimum number of the second operation . There are two final strings ：“0101010101…” or "1010101010…", Compare the number of two strings of different elements .

Code ：

class Solution {
    
    public int minFlips(String s) {
    
        int len = s.length(), t = 2, res = Integer.MAX_VALUE;
        String time = s + s;
        
        t = 2;
        while (t-- > 0) {
    
            int count = 0, j = t;
            for (int k = 0; k < len; j ^= 1, k++) {
    
                count += (time.charAt(k) ==  (j +'0')) ? 0:1;
            }
            res = Math.min(res, count);

            for (int k = len, p = t; k < len*2; j ^= 1, p ^= 1, k++) {
    
                count -= (time.charAt(k - len) ==  (p +'0')) ? 0:1;
                count += (time.charAt(k) ==  (j +'0')) ? 0:1;
                res = Math.min(res, count);
            }
        }
        return res;
    }
}

Problem D- Minimum waste of space for packing

Ideas ： Traverse supplier, Give Way box Two points package, To calculate the supplier Total volume required , Finally, take the smallest volume , subtract packages The sum of . If traversal package, Give Way package Two points box, Will timeout .

Code ：

class Solution {
    
    final long mod = (long)(1e9 + 7);
    final long inf = (long)1e18;

    public int minWastedSpace(int[] packages, int[][] boxes) {
    
        int supplierNum = boxes.length, packagesNum = packages.length;

        long res = inf, sum = 0;
        //  Total package 
        for (int i = 0; i < packagesNum; i++) {
    
            sum += packages[i];
        }
		
        Arrays.sort(packages);

        for (int i = 0; i < supplierNum; i++) {
    
            int len = boxes[i].length, left = -1, right = packagesNum - 1, last = -1;
            long count = -sum;

            Arrays.sort(boxes[i], 0, len);
            if (packages[packagesNum - 1] > boxes[i][len - 1]) continue;
			//  Statistics box Total volume 
            for (int j = 0; j < len; j ++) {
    
                left = upperBound(packages, left, right, boxes[i][j]);

                if (left == last) continue;
                count += ((long)(left - last) * boxes[i][j]);
                last = left;
            }
            res = Math.min(res, count);
        }
        if (res == inf) return -1;
        return (int)(res % mod);
    }

    public int upperBound(int[] a, int left, int right, int key) {
    
        int mid;
        while (left < right) {
    
            mid = (left + right + 1) >> 1;
            if (a[mid] > key) {
    
                right = mid - 1;
            } else {
    
                left = mid;
            }
        }
        return left;
    }
}