L 1135. Connecting Cities With Minimum Cost ----M ~~~~~练习MST的Kruskal实现

There are N cities numbered from 1 to N.

You are given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together.  (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1.)

Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together.  The cost is the sum of the connection costs used. If the task is impossible, return -1.

 

Example 1:

Input: N = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: 
Choosing any 2 edges will connect all cities so we choose the minimum 2.

Example 2:

Input: N = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation: 
There is no way to connect all cities even if all edges are used.

 

Note:

1. 1 <= N <= 10000
2. 1 <= connections.length <= 10000
3. 1 <= connections[i][0], connections[i][1] <= N
4. 0 <= connections[i][2] <= 10^5
5. connections[i][0] != connections[i][1]

 A:

就是经典的minimum spanning tree,   用Prim   or   Kruskal 

但是没有用Union_by rank .而只是随机union了

class Solution {
public:
    int minimumCost(int N, vector<vector<int>>& connections) {
        sort(connections.begin(), connections.end(),
            [](const vector<int>& a, const vector<int>& b)
            {
                return a[2] < b[2];
            });
        // make set
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
        int res = 0;
        int edgeCount = 0;
        for (auto edge : connections) {
            int city1 = edge[0];
            int city2 = edge[1];
            if (find_set(city1) != find_set(city2)) {
                union_set(city1, city2); // merge their parent
                edgeCount++;
                res += edge[2]; // cost
            }
            if (edgeCount == N - 1) {
                return res;
            }
        }
        return -1;
    }
private:
    unordered_map<int, int> parent;
    int find_set(int city) {
        if (parent[city] != city) {
            parent[city] = find_set(parent[city]);
        }
        return parent[city];
    }
    void union_set(int city1, int city2) {
        parent[find_set(city1)] = parent[find_set(city2)];
    }
};

这个题，以前没有做过，需要多多熟悉

L 272. Closest Binary Search Tree Value II -----------H ~~~~~！！！！！！！！！

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

• Given target value is a floating point.
• You may assume k is always valid, that is: k ≤ total nodes.
• You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up:

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)? 

A:

首先想到都弄到一个数组里，然后全部排序。  然而不是optimal

思路是找到k个比他小的， 和k个比他大的。 然后前后两头儿检查 删除一个。

O（ k + log N ) time,  O(k) space

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        deque<int> res;
        // find up to k values, that smaller than(or equal to) target
        find_k_smallerEq(root, target, k, res);
        deque<int> resBigger;
        find_k_bigger(root, target, k, resBigger);
        for (auto v : resBigger) {
            res.push_back(v);
        }

        while (res.size() > k) {
            if (abs(res.front() - target) >= abs(res.back() - target)) {
                res.pop_front();
            }
            else {
                res.pop_back();
            }
        }
        return vector<int>(res.begin(), res.end());
    }
private:
    void find_k_smallerEq(TreeNode* root, double target, const int k, deque<int>& res) {
        if (not root || res.size() >= k)
            return;
        if (root->val > target) {
            find_k_smallerEq(root->left, target, k, res);
            return;
        }
        find_k_smallerEq(root->right, target, k, res);
        if (res.size() < k)
            res.push_front(root->val);
        find_k_smallerEq(root->left, target, k, res);
    }
    void find_k_bigger(TreeNode* root, double target, const int k, deque<int>& res) {
        if (not root || res.size() >= k) {
            return;
        }
        if (root->val <= target) {
            find_k_bigger(root->right, target, k, res);
            return;
        }
        find_k_bigger(root->left, target, k, res);
        if (res.size() < k)
            res.push_back(root->val);
        find_k_bigger(root->right, target, k, res);
    }
};

Faster than 95.75%的

Mistakes：

要注意root value不是先插入的

***********上面思路的简化版本***********

L 311. Sparse Matrix Multiplication ---------M

 Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

Input:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

Output:

     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

 

Constraints:

• 1 <= A.length, B.length <= 100
• 1 <= A[i].length, B[i].length <= 100
• -100 <= A[i][j], B[i][j] <= 100

A:

实现题

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int m = A.size();
        if (m == 0) {
            return vector<vector<int>>();
        }
        int n = A[0].size();
        int k = B[0].size();
        vector<vector<int>> res(m, vector<int>(k, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k; j++) {
                for (int t = 0; t < n; t++) {
                    res[i][j] += A[i][t] * B[t][j];
                }
            }
        }
        return res;
    }
};

L 379. Design Phone Directory ---------M

Design a Phone Directory which supports the following operations:

 

1. get: Provide a number which is not assigned to anyone.
2. check: Check if a number is available or not.
3. release: Recycle or release a number.

 

Example:

// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
PhoneDirectory directory = new PhoneDirectory(3);

// It can return any available phone number. Here we assume it returns 0.
directory.get();

// Assume it returns 1.
directory.get();

// The number 2 is available, so return true.
directory.check(2);

// It returns 2, the only number that is left.
directory.get();

// The number 2 is no longer available, so return false.
directory.check(2);

// Release number 2 back to the pool.
directory.release(2);

// Number 2 is available again, return true.
directory.check(2);

 

Constraints:

• 1 <= maxNumbers <= 10^4
• 0 <= number < maxNumbers
• The total number of call of the methods is between [0 - 20000]

 

A:

就是用一个 set 来保存所有的数据。

class PhoneDirectory {
public:
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers) {
        for(int i =0;i<maxNumbers; i++){
            mySet.insert(i);
        }
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        if(mySet.empty()){
            return -1;
        }
        int res = *(mySet.begin());
        mySet.erase(res);
        return res;        
    }
    
    /** Check if a number is available or not. */
    bool check(int number) {
        return mySet.find(number) != mySet.end();
    }
    
    /** Recycle or release a number. */
    void release(int number) {
        mySet.insert(number);
    }
private:
    unordered_set<int> mySet;
};

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory* obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj->get();
 * bool param_2 = obj->check(number);
 * obj->release(number);
 */

1585. Check If String Is Transformable With Substring Sort Operations ------ H ~~~

 Given two strings s and t, you want to transform string s into string t using the following operation any number of times:

• Choose a non-empty substring in s and sort it in-place so the characters are in ascending order.

For example, applying the operation on the underlined substring in "14234" results in "12344".

Return true if it is possible to transform string s into string t. Otherwise, return false.

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

 

Example 1:

Input: s = "84532", t = "34852"
Output: true
Explanation: You can transform s into t using the following sort operations:
"84532" (from index 2 to 3) -> "84352"
"84352" (from index 0 to 2) -> "34852"

Example 2:

Input: s = "34521", t = "23415"
Output: true
Explanation: You can transform s into t using the following sort operations:
"34521" -> "23451"
"23451" -> "23415"

Example 3:

Input: s = "12345", t = "12435"
Output: false

Example 4:

Input: s = "1", t = "2"
Output: false

 

Constraints:

• s.length == t.length
• 1 <= s.length <= 105
• s and t only contain digits from '0' to '9'.

A：

稍微试了几个， 找到了原理， 就是 每次找t中的下一个char , 然后在s中 查找， 在找到该char之前的所有的char，不能比他小，否则就 sort不过来。  

sol 1:  每次找到一个，  用类似bubble sort的方式 float up 

class Solution {
public:
    bool isTransformable(string s, string t) {
        int n = s.length();
        //idea: switch to make the first char, by switch one by one, to keep order
        for(int start =0; start < n; start++){
            int targetIndex = start;
            while(targetIndex < n && s[targetIndex] != t[start]){
                targetIndex++;
            }
            if(targetIndex >= n){
                return false;
            }
            // bubble sort to float up the target char
            for(int i =targetIndex; i> start;i--){
                if(s[i-1] < t[start]){  // make sure all can be floated up
                    return false;
                }
                s[i] = s[i-1];
            }
        }
        return true;
    }
};

逻辑是正确的。   然而LTE了。  上面太多的move操作，而且重复了。

现在，去掉重复move, 改用一个数组来flag一个char 是否visited了

class Solution {
public:
    bool isTransformable(string s, string t) {
        int n = s.length();
        vector<bool> visited(n, false);
        //idea: switch to make the first char, by switch one by one, to keep order
        int startS = 0;
        for(int it =0; it < n; it++){
            char targetChar = t[it];
            int is=startS;
            while(is< n && (visited[is] ||  s[is] > targetChar ) ){
                is++;
            }
            if(is >= n || s[is] != targetChar){
                return false;
            }
            visited[is] = true;
            while(startS < n && visited[startS]){// amortized time complexity is O(1)
                startS++;
            }
        }
        return true;
    }
};

我XXXXXXX ，竟然还    LTE

看了下结果， 是0--9 可能一个位置，有太多重复的了。看这个例子。

所以，优化只能是第一个while

那么，我们用一个数组来记录每个char的位置， 这样就不用挨个查了。(最多查9个，所以还是O(1)的复杂度）

class Solution {
public:
    bool isTransformable(string s, string t) {
        int n = s.length();
        vector<vector<int>> Pos(10, vector<int>());
        for (int i = n - 1; i >= 0; i--) {
            Pos[s[i] - '0'].push_back(i);
        }
        for (int i = 0; i < n; i++) {
            int val = t[i] - '0';
            // check that no values smaller than val, is ahead of it.            
            if (Pos[val].empty()) {
                return false;
            }
            int valPos = Pos[val].back();
            for (int v = 0; v < val; v++) {
                if (!Pos[v].empty() && Pos[v].back() < valPos) {
                    return false;
                }
            }
            Pos[val].pop_back();
        }
        return true;
    }
}

L 333. Largest BST Subtree ------M

 Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties:

• The left subtree values are less than the value of their parent (root) node's value.
• The right subtree values are greater than the value of their parent (root) node's value.

Note: A subtree must include all of its descendants.

Follow up: Can you figure out ways to solve it with O(n) time complexity?

 

Example 1:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

Example 2:

Input: root = [4,2,7,2,3,5,null,2,null,null,null,null,null,1]
Output: 2

 

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -104 <= Node.val <= 104

A:

这个一开始理解错误， 以为是要 root value with largest mean of BST呢

其实挺简单的。 就是利用 C++ 的 pass by reference 来update 最终结果

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */


class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        if (not root) // shall never hit
            return 0;
        int largestCount = 0;

        int minVal = INT_MAX, maxVal = INT_MIN;
        int count = 0;
        helper(root, minVal, maxVal, count, largestCount);
        return largestCount;
    }
private:
    bool helper(TreeNode* root, int& minValue, int& maxValue, int& count, int& largestCount) {
        if (not root) {
            return true;
        }
        int leftMin = INT_MAX, leftMax = INT_MIN;
        int leftCount = 0;
        bool isLeftBST = helper(root->left, leftMin, leftMax, leftCount,  largestCount);

        int rightMin = INT_MAX, rightMax = INT_MIN;
        int rightCount = 0;
        bool isRightBST = helper(root->right, rightMin, rightMax, rightCount, largestCount);

        if (isLeftBST && isRightBST && root->val > leftMax && root->val < rightMin) {
            count = 1 + leftCount + rightCount;
            if (count > largestCount) {
                largestCount = count;
            }
            minValue = root->left ? leftMin : root->val;
            maxValue = root->right? rightMax : root->val;
            return true;
        }
        return false;
    }
};

467. Unique Substrings in Wraparound String ------M ~~~~~~

 Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

Input: "a"
Output: 1

Explanation: Only the substring "a" of string "a" is in the string s.

Example 2:

Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

A:

首先，就是从每一个start index, 然后往后看，后面的是不是substring of s

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        int n = p.length();
        unordered_set<string> mySet;
        for(int start =0; start <n; start++){// both start and end are inclusive 
            for(int end = start;end<n;end++){ // both start and end are inclusve                
                if(end == start || p[end] == p[end-1] +1 || ( p[end]=='a' && p[end-1] == 'z') ){
                    mySet.insert(p.substr(start,  end-start+1));
                }else{
                    break;
                }
            }
        }
        return mySet.size();
    }
};

然而LTE了

究其原因，如果p 是duplicated. 那么我们有太多重复计算的了。  （而且  len(p) > 10,000.  然而我们的字母只有26个）

很显然， 改进应该是在里面的这个for Loop

考虑这样的p   

"zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghifklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...".

这样就会每个都跑到最后去了

因此，我的idea是，对于每一个字母，例如'a', 找出其从他开始最长的串儿。

其长度，就是以 ‘a' 开始的字符串的数目

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        int n = p.length();
        vector<int> maxLen(26,0);// maxLength of maxLen[ch-'a'] that it can reach
        for(int start =0; start <n; ){
            int end = start+1; // keep going untill we find non-fit position
            for(;end<n;end++){
                if( p[end] != p[end-1] +1 &&  not (p[end]=='a' && p[end-1] == 'z') ){
                    break;
                }
            }
            for(int i =start;i<min(end, start+26);i++){
                int index  = int(p[i]) - 'a';
                maxLen[index] = max(maxLen[index], end - i);
            }
            start = end;
        }
        return accumulate(maxLen.begin(), maxLen.end(), 0);
    }
};