隨緣記錄 LeetCode第168場周賽 2019-12-22

5292. 劃分數組為連續數字的集合

給你一個整數數組 nums 和一個正整數 k，請你判斷是否可以把這個數組劃分成一些由 k 個連續數字組成的集合。
如果可以，請返回 True；否則，返回 False。

示例 1：
輸入：nums = [1,2,3,3,4,4,5,6], k = 4
輸出：true
解釋：數組可以分成 [1,2,3,4] 和 [3,4,5,6]。

**題目表述為集合，不是數組。 =__=**

輸入：nums = [3,3,2,2,1,1], k = 3
輸出：true

分析:

需要將數組按照k個一組劃分。所以一共有len / k 個集合。如果不能整除說明不符合條件。

因為考慮到是集合，所以先將數組進行排序。

• 首先用map統計每個數字才出現的次數。
• 然後遍曆數組的每個元素。
  • 從map中取出每個元素的出現次數。如果數量為0，說明該元素已經被包含到其他的集合啦，可以跳過了。
    • 每取出一個元素，就可以將保存的個數-1。
  • 然後就開始查詢符合條件的集合。
    • 從map中分別取出num+i的元素剩餘次數，i從1到len / k。
    • 如果次數為0，說明當前的這一個集合不符合條件。返回false
  • 寫到這裡已經可以得到結果。但是在後序的查詢過程中可能存在很多已經將數量減少到0的元素。
    • 為了減少後序操作，定義一個變數m。維護已經出現的符合條件的集合的次數。如果m等於len/k，說明已經找到了全部符合條件的集合返回true；

public boolean isPossibleDivide(int[] nums, int k) {
    int len = nums.length;
    if(len%k!=0){
        return false;
    }
    Arrays.sort(nums);
    Map<Integer,Integer> map = new HashMap<>();
    for(int num:nums){
        map.put(num,map.getOrDefault(num,0)+1);
    }
    int count = len/k;
    int m = 0;
    for(int num:nums){
        int start = map.get(num);
        if(start==0){
            //已經沒有了
            continue;
        }
        map.put(num,start-1);
        for(int i =1;i<k;i++){
            int temp = map.getOrDefault(num+i,0);
            if(temp==0){
                //當前序列不合法。
                return false;
            }
            map.put(num+i,temp-1);
        }
        m++;
        if(m==count){
            return true;
        }
    }
    return true;
}

5293. 子串的最大出現次數

給你一個字元串 s ，請你返回滿足以下條件且出現次數最大的 任意 子串的出現次數：

子串中不同字母的數目必須小於等於 maxLetters 。
子串的長度必須大於等於 minSize 且小於等於 maxSize 。

輸入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
輸出：2
解釋：子串 "aab" 在原字元串中出現了 2 次。
它滿足所有的要求：2 個不同的字母，長度為 3 （在 minSize 和 maxSize 範圍內）。

這道題需要尋找的是滿足條件的出現次數最大的任意子串的次數。

• 雖然給定了最大和最小長度，實際上只需要使用最小的長度就能計算處出現的最大次數。
• 在計算出現次數的基礎上，題目需要保證子串字母數量小於等於maxLetter，當然使用Set結合計算數量。如果不符合條件就捨棄當前子串。
• 為了保證在串s長度極長的情況下不會超時。可以使用Map保存每個串出現的次數。
• 在遍歷結束後，統計集合中出現的最大次數，即為結果。

public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
    char[] arr= s.toCharArray();
    Map<String,Integer> map = new HashMap<>();
    for(int i =0;i<=s.length()-minSize;i++){
        if(checkOut(arr,i,i+minSize-1)<=maxLetters){
            String key = String.valueOf(arr,i,minSize);
            map.put(key,map.getOrDefault(key,0)+1);
        }
    }
    int count = 0;
    for(Integer num : map.values()){
        count = count<num ?num:count;
    }
    return count;
}
public int checkOut(char[] arr,int start,int end){
    Set<Character> set = new HashSet<>();
    for(int i =start;i<=end;i++){
        set.add(arr[i]);
    }
    return set.size();
}