395. Longest Substring with At Least K Repeating Characters -M ！！

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

A:

就是挨个数，如果某个字母不满足，则将其前后分开。递归  （pass）

class Solution {
public:
    int longestSubstring(string s, int k) {
        if(s.length()<k)
            return 0;        // return 0 if does not contains such a string
        vector<int> C(26,0);
        for(auto ch : s)
            C[ch-'a']++;
        for(int i =0;i<s.length();++i)
        {
            int count = C[s[i]-'a'];
            if((count>0 and count < k)) // if not include this letter, exclude it and 
            {
                int tmp = longestSubstring(s.substr(0, i), k ); // will omit the last substring
                int tmp2 = longestSubstring(s.substr(i+1), k ); // will omit the last substring
                return max(tmp, tmp2);
            }
        }
        return s.length();
    }
};

• Time complexity:O(N*lg(N))

改进算法： 

Approach 2 : Sliding Window

Complexity

• Time complexity:O(N)

• Space complexity:O(1)

454. 4Sum II -M

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

A:

-----------------用map --------------------

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int,int> AB;
        for(auto a:A)
            for(auto b:B)
                AB[a+b]++;
        
        unordered_map<int,int> CD;
        for(auto c: C)
            for(auto d: D)
                CD[c+d]++;
        int res=0;
        for(auto const& v:AB)
            res += v.second * CD[-v.first];
        return res;
    }
};

--------------改进一点儿------------  CD 那里不保存了。而只是-------

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int,int> AB;
        for(auto a:A)
            for(auto b:B)
                AB[a+b]++;
        
        int res = 0;
        for(auto c: C)
            for(auto d: D)
                res += AB[-c -d];
        return res;
    }
};

739. Daily Temperatures -M

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

A:

就是一个数组，找到其后比他高的数字里最近的那个。
思路是：保持一个increasing list, 然后每次

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0);
        stack<pair<int, int>> S; // <temperature, index>
        S.push({temperatures[n - 1], n - 1});
        for (int i = temperatures.size() - 1; i >= 0; i--) {
            int val = temperatures[i];
            while (!S.empty() && S.top().first <= temperatures[i]) {
                S.pop();
            }
            if (!S.empty()) {
                res[i] = S.top().second - i;
            }
            S.push( {temperatures[i], i});
        }
        return res;
    }
};

Error:

    忘了是距离， 因此需要 - i

621. Task Scheduler -M

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

1. The number of tasks is in the range [1, 10000].
2. The integer n is in the range [0, 100].

A:

思路是：首先对每个出现的task 计算出先的次数。
然后每次有限安排出现次数最多的task. -------但是这样是最优的吗？？？？？？因此，不能直接减去res += (n+1) * V[n]   然后 V[i] -= V[n]  这样得不到最优解。因为一次减去的太多，下次可能已经不是最高的了。
如果task 数小于n+1， 则按照最多的那个，计算， （最后一次可能不满，因此要分开单独计算）

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> M;
        for(auto ch: tasks)
            M[ch]++;
        vector<int> V;
        for(auto& t:M)
            V.push_back(t.second);
        int res = 0;
        sort(V.begin(), V.end(), greater<>());
        while(not V.empty())
        {
            if(V.size() >= n+1)
            {
                res += n+1;//!!!!!!!!!!!!!This is the key, need to update one-by-one
                for(int i =0;i<= n; ++i)
                    V[i] -= 1;
                
                sort(V.begin(), V.end(), greater<>() );// default is in assending order
                while(not V.empty() and V.back()==0)
                    V.pop_back();
            }else{
                res += (n+1) * (V[0]-1); // all iteration round (with idle)
                res++; // add first v[0]
                for(int i =1; i<V.size(); ++i)
                {
                    if(V[i] == V[0])
                        res++;
                    else
                        break;
                }
                V.clear();
            }   
        }
        return res;
    }
};

----------更优的解法 看https://leetcode.com/problems/task-scheduler/solution/  解法3

对每个task， 看其idle 个数。 （也就是上面的else 里的情况）

Learned:

1:  local variable must be clearly initialized . 
       int res;   一开始没有初始化，在remote 编译器里，就总是fail

647. Palindromic Substrings -M

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

 

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

 

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

A:

---------------遍历所有的奇数和偶数长度--------

class Solution {
public:
    int countSubstrings(string s) {
        // for odd length
        int count = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            count++; // count this char only,
            int step = 1;
            while (i - step >= 0 && i + step < n &&
                   s[i - step] == s[i + step]) {
                count++;
                step++;
            }
        }
        // for even length
        int r, step;
        for (int l = 0; l < n - 1; l++) {
            r = l + 1;
            step = 0;
            while (l - step >= 0 && r + step < n &&
                   s[l - step] == s[r + step]) {
                count++;
                step++;
            }
        }
        return count;
    }
};

-------------上面的精简 代码-----------

class Solution {
public:
    int countSubstrings(string s) {        
        vector<pair<int, int> > V; // for all number of P
        for(int i=0;i< s.length() ;++i)  // search odd length
            V.push_back(make_pair(i,i));  // start and end, inclusive        
        
        for(int i=0;i+1< s.length();++i)  // search even length
            if(s[i] == s[i+1])                
                V.push_back(make_pair(i,i+1));  // start and end, inclusive
                
        for(int i =0;i<V.size();++i)
            if(V[i].first>0 and V[i].second+1< s.length() and s[V[i].first-1] == s[V[i].second+1])
                V.push_back(make_pair(V[i].first-1, V[i].second+1));
        return V.size();
    }
};

560. Subarray Sum Equals K --------M

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

A:

--------就是按照 和的长度，一个个加起来，看是否是结果。

-------------这个用的空间最小----------------

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int res = 0;
        vector<int> curSum(n,0);
        for(int curLen = 1; curLen <= n; curLen++)
        {
            for(int i = 0; i+curLen <= n; ++i)
            {
                curSum[i] += nums[i+curLen-1];
                if(curSum[i] == k)
                    ++res;
            }
        }
        return res;
    }
};

------------------------ 这个最快--------------

class Solution {

public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> m = {{0, 1}}; // initialize with m[0] = 1
        int count = 0, sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (m.find(sum - k) != m.end()) {
                count += m[sum - k];
            }
            m[sum]++;
        }
        return count;
    }
};

438. Find All Anagrams in a String -M

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

A:

就是两个pointer 一边跑一边看， 数其是否找到足够的anagram。  同时，数其是否找到足够char数目的match

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        int nP = p.length(), nS = s.length();
        if(nS < nP)
            return res;
        unordered_map<char,int> pM;
        for(auto ch : p)
            pM[ch]++;
        int pCharCount = pM.size();
        
        unordered_map<char,int> pFound;        
        int matchedChar = 0;
        
        int left =0, right = 0;
        while(left + nP <= nS)
        {
            // run till right pointer till nP length on string s
            for(; right<left+nP; right++)
            {
                char ch = s[right];
                if(pM.find(ch) == pM.end())
                {// not found
                    pFound.clear();
                    matchedChar=0;
                    left = right+1;
                    right++ ;
                    break;
                }else{
                    if(pFound[ch] == pM[ch])
                    {
                        matchedChar--;
                    }
                    pFound[ch]++;
                    if(pFound[ch] == pM[ch])
                    {
                        matchedChar++;
                    }
                    if(matchedChar == pCharCount)
                    {
                        res.push_back(left);
                    }
                    // if right is the last place, we need also remove the left char
                    if(right +1 == left+nP)
                    {
                        char delChar = s[left];
                        if(pFound[delChar] == pM[delChar])
                            matchedChar--;
                        pFound[delChar]--;
                        if(pFound[delChar] == pM[delChar] )
                            matchedChar++;
                        left++;
                    }
                }                
            }
        }
        return res;
    }
};

改进了一下， 利用全是English lowercase letter， 来用array， 或者vector来计算

但是利用了vector对比。 （而不需要计数。  虽然理论上我们的更快）

https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/528625/C%2B%2B-94

也可以直接利用unordered_map == 

https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/510208/C%2B%2B-unordered-map-Solution

Learned:

we can user vector ==,  (or map ==)