Strong Password Checker II

A password is said to be strong if it satisfies all the following criteria:

• It has at least 8 characters.
• It contains at least one lowercase letter.
• It contains at least one uppercase letter.
• It contains at least one digit.
• It contains at least one special character. The special characters are the characters in the following string: "!@#$%^&*()-+".
• It does not contain 2 of the same character in adjacent positions (i.e., "aab" violates this condition, but "aba" does not).

Given a string password, return true if it is a strong password. Otherwise, return false.

Example 1:

Input: password = "IloveLe3tcode!"
Output: true
Explanation: The password meets all the requirements. Therefore, we return true.

这就多开几个bool，判断一下就行了

class Solution {
public:
    bool strongPasswordCheckerII(string s) {
        string a="!@#$%^&*()-+";
        bool len=s.size()>=8;
        bool lower=false;
        bool upper=false;
        bool num=false;
        bool sp=false;
        bool lx=true;
        for(int i = 0 ; i<s.size();i++){
            if(i!=0&&s[i]==s[i-1]){
                lx=false;
            }
            if(s[i]>='a'&&s[i]<='z'){
                lower=true;
            }
            if(s[i]>='A'&&s[i]<='Z'){
                upper=true;
            }
            if(s[i]>='0'&&s[i]<='9'){
                num=true;
            }
            if(a.find(s[i])!=a.npos){
                sp=true;
            }
        }
        return len&&lower&&upper&&num&&sp&&lx;
    }
};

Successful Pairs of Spells and Potions

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith sp

Example 1:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.

预处理一下potions，然后二分一下最大的右边就好了

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<long long >n;
        for(int i = 0 ;i< potions.size();i++){
            long long add=success/potions[i];
            if(success%potions[i]!=0){
                add++;
            }
            n.push_back(add);
        }
        sort(n.begin(),n.end());
        vector<int> ans;
        for(int i = 0;i<spells.size();i++){
            ans.push_back(upper_bound(n.begin(),n.end(),spells[i])-n.begin());
        }
        return ans;
    }
};

Match Substring After Replacement

You are given two strings s and sub. You are also given a 2D character array mappings where mappings[i] = [oldi, newi] indicates that you may replace any number of oldi characters of sub with newi. Each character in sub cannot be replaced more than once.

Return true if it is possible to make sub a substring of s by replacing zero or more characters according to mappings. Otherwise, return false.

A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
Output: true
Explanation: Replace the first 'e' in sub with '3' and 't' in sub with '7'.
Now sub = "l3e7" is a substring of s, so we return true.

数据范围1e5模拟就行把

class Solution {
public:
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
        map<char,map<char,bool>> m;
        for(auto & i : mappings){
            m[i[0]][i[0]]=1;
            m[i[0]][i[1]]=1;
        }
        int l = sub.size();
        for(int i = 0;i+l<=s.size();i++){
            string t = s.substr(i,l);
            for(int j = 0 ;j<l;j++){
                if(t[j]!=sub[j]){
                    if(m[sub[j]][t[j]]){
                        t[j]=sub[j];
                    }else{
                        break;
                    }
                }
            }
            if(t==sub){
                return true;
            }
        }
        return false;
    }
};

为啥出现的内部错误。。。

Count Subarrays With Score Less Than K

The score of an array is defined as the product of its sum and its length.

• For example, the score of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.

Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [2,1,4,3,5], k = 10
Output: 6
Explanation:
The 6 subarrays having scores less than 10 are:
- [2] with score 2 * 1 = 2.
- [1] with score 1 * 1 = 1.
- [4] with score 4 * 1 = 4.
- [3] with score 3 * 1 = 3. 
- [5] with score 5 * 1 = 5.
- [2,1] with score (2 + 1) * 2 = 6.

二分一眼丁真

class Solution {
public:
    vector<long long > pre;
    long long kk;
    bool check(int begin,int end){
        return (pre[end]-pre[begin-1])*(end-begin+1)<kk;
    }
    long long countSubarrays(vector<int>& nums, long long k) {
        kk=k;
        pre=vector<long long > (nums.size()+1,0);
        pre[1]=nums[0];
        for(int i = 2;i<nums.size()+1;i++){
            pre[i]=pre[i-1]+nums[i-1];
        }
        long long ans=0;
        for(int i = 1;i<nums.size()+1;i++){
            if(nums[i-1]>=k){
                continue;
            }
            int l = i ;
            int r= pre.size()-1;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(check(i,mid)){
                    l=mid;
                }else{
                    r=mid-1;
                }
            }
            ans+=l-i+1;
        }
        return ans;
    }
};