當前位置:網站首頁>【恒生電子專場】力扣第 244 場周賽(1950 / 4429)

【恒生電子專場】力扣第 244 場周賽(1950 / 4429)

2022-01-27 02:33:12 愛敲代碼的小黃

這場周賽有點菜,第二題浪費了太多的時間了

第一題

題目鏈接

5776. 判斷矩陣經輪轉後是否一致

題目簡介

給你兩個大小為 n x n 的二進制矩陣 mat 和 target 。現 以 90 度順時針輪轉 矩陣 mat 中的元素 若幹次 ,如果能够使 mat 與 target 一致,返回 true ;否則,返回 false 。
在這裏插入圖片描述

題目解析

  • 模擬題目,對 mat 數組進行 90度 旋轉,來是否能和 target 一樣

題目代碼

class Solution {
    
    public boolean findRotation(int[][] mat, int[][] target) {
    
        for(int i = 0; i < 4; i++){
    
            if(isSame(mat, target)){
    
                return true;
            }
            xuan(mat);
        }
        return false;
    }


    public void xuan(int[][] mat){
    
        int n = mat.length;
        for (int i = 0; i < n / 2; ++i) {
    
            for (int j = 0; j < (n + 1) / 2; ++j) {
    
                int temp = mat[i][j];
                mat[i][j] = mat[n-1-j][i];
                mat[n-1-j][i] = mat[n-1-i][n-1-j];
                mat[n-1-i][n-1-j] = mat[j][n-1-i];
                mat[j][n-1-i] = temp;
            }
        }
    }
    public boolean isSame(int[][] mat, int[][] target){
    
        for(int i = 0; i < mat.length; i++){
    
            for(int j = 0; j < mat[0].length; j++){
    
                if(mat[i][j] != target[i][j]){
    
                    return false;
                }
            }
        }

        return true;
    }
}

第二題

題目鏈接

5777. 使數組元素相等的减少操作次數

題目簡介

給你一個整數數組 nums ,你的目標是令 nums 中的所有元素相等。完成一次减少操作需要遵照下面的幾個步驟:

  • 找出 nums 中的 最大 值。記這個值為 largest 並取其下標 i (下標從 0 開始計數)。如果有多個元素都是最大值,則取最小的 i 。
  • 找出 nums 中的 下一個最大 值,這個值 嚴格小於 largest ,記為 nextLargest 。
  • 將 nums[i] 减少到 nextLargest 。

返回使 nums 中的所有元素相等的操作次數。
在這裏插入圖片描述

題目解析

  • 剛開始以為是個模擬題,模擬了一下,發現出現超時錯誤
  • 後來發現規律:如數組nums[1,2,3,4,3,2]
    • 將所有的4變成3,需要1次操作
    • 將所有的3變成2,需要3次操作
    • 再將所有的2變成1,需要5次操作
    • 總共需要:1 + 3 + 5 = 8 次操作
  • 所以,我們能找到一個規律:從最大值開始,依次進行减少,所以我們只需要枚舉 最大~最小 出現的次數,加起來就可以了

題目代碼

class Solution {
    
    public int reductionOperations(int[] nums) {
    
        int[] num = new int[100000];
        int min = 100000;
        int max = 0;
        for(int i = 0; i < nums.length; i++){
    
            num[nums[i]]++;
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        int sum = 0;
        int cnt = 0;
        for(int i = max; i > min; i--){
    
            if(num[i] != 0){
    
                cnt += num[i];
                sum += cnt;
            }
        }
        return sum;
    }
}

第三題

題目鏈接

5778. 使二進制字符串字符交替的最少反轉次數

題目簡介

給你一個二進制字符串 s 。你可以按任意順序執行以下兩種操作任意次:

  • 類型 1 :删除 字符串 s 的第一個字符並將它 添加 到字符串結尾。
  • 類型 2 :選擇 字符串 s 中任意一個字符並將該字符 反轉 ,也就是如果值為 ‘0’ ,則反轉得到 ‘1’ ,反之亦然。

請你返回使 s 變成 交替 字符串的前提下, 類型 2 的 最少 操作次數 。

我們稱一個字符串是 交替 的,需要滿足任意相鄰字符都不同。

  • 比方說,字符串 “010” 和 “1010” 都是交替的,但是字符串 “0100” 不是。
    在這裏插入圖片描述

題目解析

  • 這個題目,一開始我使用的N^2的方法做的,發現超時,後來也沒想到優化的辦法
  • 對於我們字符串來說,我們最後肯定要變成下方的樣子
    • 如果是偶數:
      • 第一種情况:01010101
      • 第二種情况:10101010
    • 如果是奇數:
      • 第一種情况:1010101
      • 第二種情况:0101010
      • 第三種情况:0100101
      • 第四種情况:1011010
  • 這四種情况我們使用滑動窗口來解决:
    • 最原始的N^2的做法:每次進行删除後,重新計算當前字符串與目標串的不同比特置,最後返回一個min
    • 優化思路:我們想想,對於 當前字符串與目標串的不同比特置 可不可以通過 O(1) 的時間得到?我們可以想到,原字符串不斷的進行删除放置末尾,也就相當於使用滑動窗口對於 s+s 進行遍曆,如下圖所示:
      在這裏插入圖片描述
  • 每次滑動窗口的大小都為:s.length()
  • 每次滑動的距離為:1
  • 在滑動的過程中,需要判斷當前的值和目標值是否相等,若不等,則增加
  • i >= len,證明進入删除放置末尾的操作了,滑動的時候需要判斷丟弃的元素是不是不等的
  • 最後返回即可

題目代碼

class Solution {
    
    public int minFlips(String str) {
    
        // 字符串的模式
        // 01010101
        // 10101010
        int len = str.length();
        String s = str + str;

        StringBuffer sb1 = new StringBuffer();
        StringBuffer sb2 = new StringBuffer();

        for(int i = 0; i < len; i++){
    
            sb1.append("01");
            sb2.append("10");
        }

        int num1 = 0;
        int num2 = 0;

        int ans = 10000000;
        for(int i = 0; i < len * 2; i++){
    
            if(s.charAt(i) != sb1.charAt(i)){
    
                num1++;
            }
            if(s.charAt(i) != sb2.charAt(i)){
    
                num2++;
            }

            if(i >= len){
    
                if(s.charAt(i - len) != sb1.charAt(i-len)){
    
                    num1--;
                }
                if(s.charAt(i - len) != sb2.charAt(i-len)){
    
                    num2--;
                }
                ans = Math.min(ans, Math.min(num1, num2));
            }
        }

        return ans;
    }
}

版權聲明
本文為[愛敲代碼的小黃]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201270233123749.html

隨機推薦