210. Course Schedule II -M

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

A:

------------就是  Toplogical sort (  但是因为不是tree 格式，所以我们用数组做-------------

------------each round, extract the index with 0 out-going dependence, ------------ PASS, but still a little bit slow ----------less memory -------------------

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> res;
        vector<int> outCount(numCourses, 0); // number of out dependence
        for(auto& V:prerequisites )
            ++outCount[V[0]];
        
        bool foundLastRound = true;
        while(foundLastRound)
        {
            foundLastRound = false;
            for(int i =0;i<numCourses;++i)
            {
                if(outCount[i] ==0)
                {
                    res.push_back(i);
                    outCount[i] = -1; // will never be called
                    foundLastRound = true;
                    break;
                }
            }
            if(foundLastRound)
            {
                for(auto& V:prerequisites )
                    if(V[1] == res.back())
                        --outCount[V[0]];
            }
        }
        if(res.size()<numCourses)
            res.clear();
        return res;
    }
};

-----------

378. Kth Smallest Element in a Sorted Matrix -M ！！！！！！！！！

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

You must find a solution with a memory complexity better than O(n2).

 

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

Example 2:

Input: matrix = [[-5]], k = 1
Output: -5

 

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -109 <= matrix[i][j] <= 109
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
• 1 <= k <= n2

 

Follow up:

• Could you solve the problem with a constant memory (i.e., O(1) memory complexity)?
• Could you solve the problem in O(n) time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.

A:

1 : 全部放到一个vector, 然后sort，
2： PriorityQueue 
---------------------------Using max heap ------   但是没有利用到每行每列是排列好 的---------

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();        
        priority_queue<int, vector<int>> Q; // default is the max-heap
        for(auto & line:matrix)
        {
            for(auto v:line)
            {
                Q.push(v);
                if(Q.size()>k)
                {
                    Q.pop();
                }
            }
        }
        return Q.top();        
    }
};

3:  按照左上角，歇着 用这个方向  /    切，  每次消掉一定数目。直到不能再切了

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        // cut like / , first chop top left, then along the diagonal
        int xl = 0, yl = 0, xr = 0, yr = 0;
        while(k>  xl - xr +1) // resutl not in current diagnal, need go next level
        {
            k -= xl - xr +1;
            if(xl < m-1)
                xl++;
            else
                yl++;
            if(yr < n-1)
                yr++;
            else
                xr++;
        }
        // result are in current /  
        vector<int> vec;
        while(xl >=0 and yl<n)   // forget to check boundary of xl, fuuuuuuuuck
        {
            vec.push_back(matrix[xl--][yl++]);
        }
        sort(vec.begin(), vec.end());
        return vec[k-1];
    }
};

-----------------------操，这个思路是不对的，为啥呢？  看这个例子：
[[1,3,5],[6,7,12],[11,14,14]]
3

-------------改正后呢，每次寻找当前一个斜切最小的。然后放进Min-heap里， 每次找到当前最小值以后，将其右边和下边的的位置放进min-heap------------

class Solution {       // beat only 6% of C++
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        priority_queue<vector<int>, vector<vector<int>>, greater<>> minHeap;
        set<string> found; // use i;j to mark if a node has been added to heap
        minHeap.push(vector<int>{matrix[0][0],0,0});
        found.insert("0;0"); 
        int val, i,j;
        while(k>0){
            auto c = minHeap.top();
            --k;
            minHeap.pop();
            val = c[0],i = c[1],j=c[2];
            found.erase(to_string(i)+";"+to_string(j));         
            
            if(i+1 < n){//check right 
                string key = to_string(i+1)+";"+to_string(j);
                if(found.find(key) == found.end()){
                    found.insert(key);
                    minHeap.push(vector<int>{matrix[i+1][j],i+1,j});
                }
            }
            if(j+1 < n){//check down
                string key = to_string(i)+";"+to_string(j+1);
                if(found.find(key) == found.end()){
                    found.insert(key);
                    minHeap.push(vector<int>{matrix[i][j+1],i,j+1});
                }
            }            
        }
        return val;
    }
};

        priority_queue<vector<int>, vector<vector<int>>, greater<>> minHeap;

Better solution : binary search according to matrix values. here.

------Mistakes:

1:  又一次不会写priority_queue.   这次错在， <  >    写成了 (  )

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>& T) {
        int n = T.size();
        vector<int> res(n, 0);
        list<pair<int, int> > mylist; // save <temperator, index>, the list should be increasing order
        for(int i = T.size()-1; i>=0;--i)
        {    // first find next warmer index
            for(auto iter = mylist.begin(); iter != mylist.end(); ++iter)
            {
                if(iter->first<= T[i])
                {
                    iter = mylist.erase(iter);
                    --iter; // re-visit this value
                }else{
                    res[i] = iter->second - i;
                    break;
                }
            }
            // now insert current value
            mylist.push_front(make_pair(T[i], i));
        }
        return res;
    }
};

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