[summary of leetcode weekly competition] the 83rd fortnight competition of leetcode (7.23)

Topic 1   6128. The best poker hand

Ideas

Use array as hash table , Record decor and deck , Then judge from big to small according to the rules , Then directly return the string .

Code

class Solution {
    public String bestHand(int[] ranks, char[] suits) {
        int[] countSuits = new int[4];
        int[] countRanks = new int[14];
        for(char c:suits){
            countSuits[c-'a']++;
        }
        for(int i=0;i<4;i++){
            if(countSuits[i]==5){
                return "Flush";
            }
        }
        for(int i=0;i<5;i++){
            countRanks[ranks[i]]++;
        }
        boolean flag = false;
        for(int i=1;i<=13;i++){
            if(countRanks[i]>=3){
                return "Three of a Kind";
            }
            if(countRanks[i]==2){
                flag = true;
            }
        }
        if(flag){
            return "Pair";
        }else{
            return "High Card";
        }
    }
}

Topic two  6129. whole 0 The number of subarrays

Ideas

Count each one 0 The number of subarrays at the end of , Simultaneously count each 0 Continuous on the left 0 The number of left,

Every 0 The number of subarrays at the end of = left + 1

for example ： 1 ,0 , 0, 0,1

count        1     1+1   1+2

Code

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long res = 0;
        int left = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){
                res += (1+left);
                left++;
            }else{
                left = 0;
            }

        }
        return res;
    }
}

Topic three  6130. Design digital container system

Ideas

According to the meaning , It needs to be found in a small time complexity num The corresponding minimum idx, I thought I could maintain two hash mappings , At first, I was wrong to use the linked list ,numToIdx It can be used TreeSet

TreeSet The bottom layer is TreeMap, Use red black tree to achieve , The time complexity of insert delete search is O(logn)

Map<Integer,TreeSet<Integer>> numToIdx;

Map<Integer,Integer> idxToNum;

void change(int index, int number) In subscript  index  Fill in  number . If the subscript  index  There are already numbers at , Then use number  Replace this number .

change The operation may modify three data structures ,

1、oldNumber If there is , Delete numToIdx in oldNumber Of idx

2、number Add numToIdx Medium idx（ Pay attention to writing , Don't actually add it to the hash table ）

3、 Update hash table idxToNum

 int find(int number)  Returns the given number  number  The minimum subscript in the system . If there is no  number , Then the return  -1 .

return -1 The situation of , May be number Not in the hash table , It could be number Corresponding set The size is 0.

Code

class NumberContainers {
    Map<Integer,TreeSet<Integer>> numToIdx;
    Map<Integer,Integer> idxToNum;
    public NumberContainers() {
        numToIdx = new HashMap<>();
        idxToNum = new HashMap<>();
    }
    
    public void change(int index, int number) {
        int oldNum = idxToNum.getOrDefault(index,-1); //idx The original num
        idxToNum.put(index,number);
        if(oldNum!=-1){
            numToIdx.get(oldNum).remove(index);
        }
        TreeSet<Integer> tmp = numToIdx.getOrDefault(number,new TreeSet<Integer>());
        tmp.add(index);
        numToIdx.put(number,tmp);
        
    }
    
   public int find(int number) {
        if(numToIdx.containsKey(number) && !numToIdx.get(number).isEmpty()){
            return numToIdx.get(number).first();
        }else{
            return -1;
        }
    }
}