[weekly replay] game 80 of leetcode

1、 Strong password verifier II

1） Title Description

If a password meets all of the following conditions , We call it a strong password ：
It has at least 8 Characters .
Include at least A lowercase English Letter .
Include at least A capital English Letter .
Include at least A number .
Include at least A special character . The special characters are ："[email protected]#$%^&*()-+" One of them .
it No contain 2 Consecutive identical characters （ For example "aab" Does not meet this condition , however "aba" Meet this condition ）.
Give you a string password, If it is a strong password , return true, Otherwise return to false .

2） Original link

Original link ：LeetCode.6095： Strong password verifier II

3） Thinking analysis

• $(1)$ A relatively simple simulation problem , Use one for each request boolean Variable representation , Each match turns it into true, Whether the final interpretation is all true.

4） Template code

class Solution {
    
    public boolean strongPasswordCheckerII(String password) {
    
         int n=password.length();
        if (n<8) return false;
        boolean f1=false,f2=false,f3=false,f4=false;
        Set<Character> set=new HashSet<>();
        String s="[email protected]#$%^&*()-+";
        for(int i=0;i<s.length();++i) set.add(s.charAt(i));
        for (int i = 0; i < n; i++) {
    
            char c=password.charAt(i);
             if (i>0&&c==password.charAt(i-1)) return false;
            if (c>='a'&&c<='z') f1=true;
            else if (c>='A'&&c<='Z') f2=true;
            else if (c>='0'&&c<='9') f3=true;
            else if (set.contains(c)) f4=true;
        }
        return f1&&f2&&f3&&f4;
    }
}

5） Algorithm and time complexity

   Algorithm ： simulation
   Time complexity ： Traverse the string once , The time complexity is $O(n)$.

2、 The number of successful spells and potions

1） Title Description

Here are two arrays of positive integers spells and potions , The lengths are n and m, among spells[i] It means the first one i The energy intensity of a spell ,potions[j] It means the first one j The energy intensity of the bottle of potion .
I'll give you an integer at the same time success . The energy intensity of a spell and potion Multiply If Greater than or equal to success , Then they are regarded as a pair success The combination of .
Please return a length of n Array of integers for pairs, among pairs[i] Yes, I can i A successful combination of spells Potion number .

2） Original link

Original link ：LeetCode.6096： The number of successful spells and potions

3） Thinking analysis

• $(1)$ For a spell x, We need to find a potion y, bring xy>=success. Because they are all positive integers and are not multiplied , We know , If the energy intensity is y Your potion meets , Is greater than y Your potion must also be satisfied .
• $(2)$ We can consider sorting the potions , Then make a dichotomy , Find one that matches xy>=success The smallest of y, Then all the potions on its right are also satisfied , All the potions on the left are not satisfied , It has two stages .

4） Template code

class Solution {
    
 public int[] successfulPairs(int[] spells, int[] potions, long success) {
    
        int n=spells.length;
        int m=potions.length;
        int[] ans=new int[n];
        Arrays.sort(potions);
        for (int i = 0; i < n; i++) {
    
            int l=0;
            int r=m-1;
            while (l<r){
    
                int mid=l+r>>1;
                // Be aware that it may explode int
                if ((long)spells[i]*potions[mid]>=success) r=mid;
                else l=mid+1;
            }
            // There may be no solution , That is to say, a potion does not conform to , So we need to judge 
            if ((long)spells[i]*potions[r]>=success) ans[i]=m-r;
            else ans[i]=0;
        }
        return ans;
    }
}

5） Algorithm and time complexity

   Algorithm ： Two points 、 Sort
   Time complexity ： The world complexity of sorting is $O(nlogn)$, The time complexity of traversal plus dichotomy is $O(nlogn)$, The overall complexity is $O(nlogn)$.

3、 Match after replacing characters

1） Title Description

Here are two strings s and sub . Also give you a two-dimensional character array mappings , among mappings[i] = [oldi, newi] It means that you can replace sub Any number of oldi Characters , Replace with newi .sub Every character in You can't Replaced more than once .
If you use mappings Replace 0 Or several characters , Can be sub become s A substring of , Please return true, Otherwise return to false .
One Substring Is a sequence of consecutive non empty characters in a string .

2） Original link

Original link ：LeetCode.6097： Match after replacing characters

3） Thinking analysis

• $(1)$ The scope of this question is not large ,1 <= sub.length <= s.length <= 5000. Because the data is not big , about s Start enumerating at each location of the , Judge whether it can be successfully matched sub.
• $(2)$ use Map Store which characters can be replaced for each character , In the process of matching , If it can be replaced, we will continue to match , Otherwise, directly enumerate the next location .

4） Template code

class Solution {
    
     Map<Character,Set<Character>> map=new HashMap<>();
    public boolean matchReplacement(String s, String sub, char[][] mappings) {
    
        for (char[] c:mappings){
    
            add(c[0],c[1]);
        }
        int n=s.length();
        int m=sub.length();
        for (int i = 0; i+m-1<n; i++) {
    
            boolean f=true;
            for (int j = 0; j <m; j++) {
    
                if (s.charAt(i+j)==sub.charAt(j)) continue;
                else{
    
                    if (!map.containsKey(sub.charAt(j))){
    
                        f=false;
                        break;
                    }else{
    
                        Set<Character> set=map.get(sub.charAt(j));
                        if (!set.contains(s.charAt(i+j))){
    
                            f=false;
                            break;
                        }
                    }
                }
            }
            if (f) return true;
        }
        return false;
    }
    void add(char a,char c){
    
        if (!map.containsKey(a)) map.put(a,new HashSet<>());
        map.get(a).add(c);
    }
}

5） Algorithm and time complexity

   Algorithm ： Hash 、 simulation
   Time complexity ： about s Start simulation at each position of sub The length of , The worst time complexity is $O(5000\ast 5000)$, You can go through .

4、 The statistical score is less than K Number of subarrays of

1） Title Description

A digital fraction Defined as the sum of arrays multiply Length of array .
For example ,[1, 2, 3, 4, 5] The score of is (1 + 2 + 3 + 4 + 5) * 5 = 75 .
Here's an array of positive integers nums And an integer k , Please return nums Middle score Strictly less than k Of Number of non empty integer subarrays .
Subarray Is a sequence of consecutive elements in an array .

2） Original link

Original link ：LeetCode.6096： The statistical score is less than K Number of subarrays of

3） Thinking analysis

• $(1)$ It is not difficult to find out the meaning of the topic , For any qualified array , Then its subarray must also conform to . Because the length and sum of subarrays must be smaller than the array , The product must be smaller .
• $(2)$ For each location $i$ We think of it as the starting position of the subarray ( Left coordinate ), We can find the largest one on its right $j$, Make all $[i,j]$ The subarray formed by the right coordinates within the range conforms to the following formula ,$[j+1,n]$ Are not in line with the meaning of the topic .
  $$sum[i,j]\ast (j-i+1)<=k$$
• $(3)$ Obviously , enumeration $j$ The position of has two stages , We can use two points . find $j$ after , With each $i$ The number of subarrays that match the meaning of the question for the starting position is $j-i+1$, Enumerate each position and accumulate the answers . For enumerating the sum of subarrays , We use prefixes and arrays to find .

4） Template code

class Solution {
    
    public long countSubarrays(int[] nums, long k) {
    
        int n=nums.length;
        long ans=0;
        long[] s=new long[n+1];
        for(int i=0;i<n;++i) s[i+1]=s[i]+nums[i];
        for (int i = 1; i <=n; i++) {
    
            int l=i;
            int r=n;
            while (l<r){
    
                int mid=l+r+1>>1;
                if (check(s,i,mid,k)) l=mid;
                else r=mid-1;
            }
            if (check(s,i,r,k)){
    
                int len=r-i+1;
                ans+=len;
            }
        }
        return ans;
    }
    boolean check(long[] s,int i,int j,long k){
    
        long value=(s[j]-s[i-1])*(j-i+1);
        return value<k;
    }
}

5） Algorithm and time complexity

   Algorithm ： enumeration 、 The prefix and 、 Two points
   Time complexity ： The time complexity of enumeration is $O(n)$, The time complexity of dichotomy at each location is $O(logn)$, The overall time complexity is $O(nlogn)$.

5、 Weekly summary

   It's not very difficult , Attention to detail .