366. Find Leaves of Binary Tree

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:

Input: [1,2,3,4,5]
  
          1
         / \
        2   3
       / \     
      4   5    

Output: [[4,5,3],[2],[1]]

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

          1
         / 
        2          

2. Now removing the leaf [2] would result in this tree:

          1          

3. Now removing the leaf [1] would result in the empty tree:

          []         

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> ans;

        while (root != NULL) {
            ans.push_back(helper(root));
        }
        return ans;
    }
   
    vector<int> helper(TreeNode*& root) {
        vector<int> ans;
        if (root == NULL) {
            return ans;
        }

        queue<pair<TreeNode *, TreeNode *>> q;
        q.push({root, NULL});
        while (!q.empty()) {
            pair<TreeNode *, TreeNode *> node = q.front(); q.pop();
            if (node.first -> left == NULL && node.first -> right == NULL) {
                ans.push_back(node.first->val);
                if (node.second != NULL) {
                    if (node.second -> left == node.first) {
                        node.second -> left = NULL;
                    } else if (node.second -> right == node.first) {
                        node.second -> right = NULL;
                    }
                } else {
                    root = NULL;
                }
            } else {
                if (node.first -> left != NULL) {
                    q.push({node.first -> left, node.first});
                }
                if (node.first -> right != NULL) {
                    q.push({node.first -> right, node.first});
                }
            }
        }
        return ans;
    }
};

698. Partition to K Equal Sum Subsets

698. Partition to K Equal Sum Subsets

Medium

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

• 1 <= k <= len(nums) <= 16.
• 0 < nums[i] < 10000.

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        for (auto num : nums) {
            sum += num;
        }
        if (sum % k != 0) {
            return false;
        }
        vector<bool> visited(nums.size(), false);
        return helper(nums, k, sum/k, 0, 0, visited);
    }
   
    bool helper(vector<int>& nums, int k, int target, int start, int curSum,
                vector<bool>&  visited) {
        if (k == 1) {
            return true;
        }
        if (curSum > target) {
            return false;
        }
        if (target == curSum) {
            return helper(nums, k - 1, target, 0, 0, visited);
        }
 
        for (int i = start; i < nums.size(); i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            if (helper(nums, k, target, i + 1, curSum + nums[i], visited)) {
                return true;
            }
            visited[i] = false;
        }
        return false;
    }
};

Time complexity: O(n!)
space: o(n)

256. Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Example:

Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. 
             Minimum cost: 2 + 5 + 3 = 10.

class Solution {

public:

    /*

    int minCost(vector<vector<int>>& costs) {

        if (costs.size() == 0) {

            return 0;

        }

        int size = costs[0].size();

        vector<int> helper = costs[0];

        for (int i = 1; i < costs.size(); i++) {

            vector<int> tmp(size, 0);

            tmp[0] = costs[i][0] + min(helper[1], helper[2]);

            tmp[1] = costs[i][1] + min(helper[0], helper[2]);

            tmp[2] = costs[i][2] + min(helper[1], helper[0]);

            helper = tmp;

            tmp.clear();

        }

        

        int ans = INT_MAX;

        for (auto num : helper) {

            ans = min(ans, num);

        }

        return ans;

    }

    */

    int minCost(vector<vector<int>>& costs) {

        if (costs.size() == 0) {

            return 0;

        }

        int size = costs[0].size();

        for (int i = 1; i < costs.size(); i++) {

            vector<int> tmp(size, 0);

            costs[i][0] = costs[i][0] + min(costs[i-1][1], costs[i-1][2]);

            costs[i][1] = costs[i][1] + min(costs[i-1][0], costs[i-1][2]);

            costs[i][2] = costs[i][2] + min(costs[i-1][1], costs[i-1][0]);

        }

        

        int ans = INT_MAX;

        for (auto num : costs[costs.size() - 1]) {

            ans = min(ans, num);

        }

        return ans;

    }

};

class Solution {
public:
 int minCost(vector<vector<int>>& costs) {
  if(costs.empty()) return 0;
  int red=costs[0][0];
  int blue=costs[0][1];
  int green=costs[0][2];
  for(int i=1;i<costs.size();i++){
   int t_red=red;
   int t_blue=blue;
   int t_green=green;
   red=min(t_blue,t_green)+costs[i][0];
   blue=min(t_red,t_green)+costs[i][1];
   green=min(t_red,t_blue)+costs[i][2];

  }
  return min(green,min(red,blue));   
 }
};

716. Max Stack

Design a max stack that supports push, pop, top, peekMax and popMax.

1. push(x) -- Push element x onto stack.
2. pop() -- Remove the element on top of the stack and return it.
3. top() -- Get the element on the top.
4. peekMax() -- Retrieve the maximum element in the stack.
5. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

Example 1:

MaxStack stack = new MaxStack();
stack.push(5); 
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5

Note:

1. -1e7 <= x <= 1e7
2. Number of operations won't exceed 10000.
3. The last four operations won't be called when stack is empty.

class MaxStack {

private:

    stack<int> st, maxSt;

public:

    /** initialize your data structure here. */

    MaxStack() {

        

    }

    

    void push(int x) {

        if (maxSt.empty() || maxSt.top() < x) {

            maxSt.push(x);

        } else {

            maxSt.push(maxSt.top());

        }

        st.push(x);

    }

    

    int pop() {

        int val = st.top();

        st.pop();

        maxSt.pop();

        return val;

    }

    

    int top() {

        return st.top();

    }

    

    int peekMax() {

        if (maxSt.empty()) {

            int ans;

            return ans;

        }

        return maxSt.top();

    }

    

    int popMax() {

        int ans = maxSt.top();

        stack<int> tmp;

        while (st.top() != ans) {

            tmp.push(st.top());

            st.pop();

            maxSt.pop();

        }

        st.pop();

        maxSt.pop();

        while (!tmp.empty()) {

            st.push(tmp.top());

            int temp = maxSt.empty() ? tmp.top() : max(maxSt.top(), tmp.top());

            maxSt.push(temp);

            tmp.pop();

        }

        return ans;

    }

};

==============

class MaxStack {
public:
    /** initialize your data structure here. */
    MaxStack() {}
    
    void push(int x) {
        v.insert(v.begin(), x);
        m[x].push_back(v.begin());
    }
    
    int pop() {
        int x = *v.begin();
        m[x].pop_back();
        if (m[x].empty()) m.erase(x);
        v.erase(v.begin());
        return x;
    }
    
    int top() {
        return *v.begin();
    }
    
    int peekMax() {
        return m.rbegin()->first;
    }
    
    int popMax() {
        int x = m.rbegin()->first;
        auto it = m[x].back();
        m[x].pop_back();
        if (m[x].empty()) m.erase(x);
        v.erase(it);
        return x;
    }

private:
    list<int> v;
    map<int, vector<list<int>::iterator>> m;
};

=========

class MaxStack {
public:
    list<int> v;
    map<int, vector<list<int>::iterator>> mp;
    
    MaxStack() { 
    }
    
    void push(int x) {
        v.insert(v.begin(),x);
        mp[x].push_back(v.begin());
    }
    
    int pop() {
        int x = *v.begin();
        mp[x].pop_back();
        if (mp[x].empty()) mp.erase(x);
        v.erase(v.begin());
        return x;
    }
    
    int top() {
        return *v.begin();
    }
    
    int peekMax() {
        return mp.rbegin()->first;
    }
    
    int popMax() {
        int x = mp.rbegin()->first;
        auto it = mp[x].back();
        mp[x].pop_back();
        if (mp[x].empty()) mp.erase(x);
        v.erase(it);
        return x;
    }
};

739. Daily Temperatures

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].

class Solution {public:    vector<int> dailyTemperatures(vector<int>& T) {        vector<int> ans(T.size());        if (T.size() == 0) {            return ans;        }        stack<int> st;        for (int i = T.size() - 1; i >= 0; i--) {            while (!st.empty() && T[st.top()] <= T[i]) {                st.pop();            }            if (!st.empty()) {                int top = st.top();                ans[i] = top - i;            } else {                ans[i] = 0;            }            st.push(i);        }
        return ans;    }};

339. Nested List Weight Sum

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:

Input: [[1,1],2,[1,1]]
Output: 10 
Explanation: Four 1's at depth 2, one 2 at depth 1.

Example 2:

Input: [1,[4,[6]]]
Output: 27 
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27.

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        if (nestedList.size() == 0) {
            return 0;
        }
        queue<NestedInteger> q;
        for (auto entry : nestedList) {
            q.push(entry);
        }
        int ans = 0;
        int height = 0;
        while (!q.empty()) {
            int size = q.size();
            height++;
            for (int i = 0; i < size; i++) {
                NestedInteger entry = q.front(); q.pop();
                if (entry.isInteger()) {
                    ans += height * entry.getInteger();
                } else {
                    for (auto node : entry.getList()) {
                        q.push(node);
                    }
                }
            }
        }
        return ans;
    }
};

class Solution { public: int depthSumRec(vector<NestedInteger>&nestedList, int dt) { int cur_sum = 0; for(auto &i : nestedList) { if(i.isInteger()) { cur_sum += (i.getInteger()) * dt; } else { cur_sum += depthSumRec(i.getList(), dt + 1); } } return cur_sum; } int depthSum(vector<NestedInteger>& nestedList) { return depthSumRec(nestedList, 1); } };

Nested List Weight Sum II

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Input: [[1,1],2,[1,1]]
Output: 8 
Explanation: Four 1's at depth 1, one 2 at depth 2.

Example 2:

Input: [1,[4,[6]]]
Output: 17 
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17.

class Solution {
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        if (nestedList.size() == 0) {
            return 0;
        }
        queue<NestedInteger> q;
        for (auto entry : nestedList) {
            q.push(entry);
        }
        int ans = 0;
        int helper = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                NestedInteger entry = q.front(); q.pop();
                if (entry.isInteger()) {
                    helper += entry.getInteger();
                } else {
                    for (auto node : entry.getList()) {
                        q.push(node);
                    }
                }
            }
            ans += helper;
        }
        return ans;
    }
};

class Solution {
private:
    int getMaxDepth(vector<NestedInteger>& nestedList) {
        int depth=1;
        for (NestedInteger& ni: nestedList) {
            if (!ni.isInteger()) {
                depth = max(depth, getMaxDepth(ni.getList())+1);
            }
        }
        return depth;
    }
    int depthSumHelper(vector<NestedInteger>& nestedList, int depth) {
        int sum = 0;
        for (NestedInteger& ni: nestedList) {
            if (ni.isInteger()) {
                sum += depth * ni.getInteger();
            } else {
                sum += depthSumHelper(ni.getList(), depth-1);
            }
        }
        return sum;
    }
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        int depth = getMaxDepth(nestedList);
        cout<<"depth is "<<depth << endl;
        return depthSumHelper(nestedList, depth);
    }
};

843. Guess the Word

25:00 https://www.youtube.com/watch?v=85pkve4pxTI

class Solution { public: void findSecretWord(vector<string>& wordlist, Master& master) { for (int i = 0, cnt = 0; i < 10 && cnt < 6; ++i) { string guess = wordlist[rand() % (wordlist.size())]; cnt = master.guess(guess); vector<string> t; for (string &word : wordlist) { if (match(guess, word) == cnt) { t.push_back(word); } } wordlist = t; } } int match(string& a, string& b) { int res = 0, n = a.size(); for (int i = 0; i < n; ++i) { if (a[i] == b[i]) ++res; } return res; } };

482. License Key Formatting

You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes.

Given a number K, we would want to reformat the strings such that each group contains exactly K characters, except for the first group which could be shorter than K, but still must contain at least one character. Furthermore, there must be a dash inserted between two groups and all lowercase letters should be converted to uppercase.

Given a non-empty string S and a number K, format the string according to the rules described above.

Example 1:

Input: S = "5F3Z-2e-9-w", K = 4

Output: "5F3Z-2E9W"

Explanation: The string S has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

Example 2:

Input: S = "2-5g-3-J", K = 2

Output: "2-5G-3J"

Explanation: The string S has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.

Note:

1. The length of string S will not exceed 12,000, and K is a positive integer.
2. String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
3. String S is non-empty.

class Solution {

public:

    string licenseKeyFormatting(string S, int K) {

        string res;

        

        int count = 0;

        for (auto it = S.rbegin() ; it != S.rend(); ++it)

        {

            if (*it != '-')

            {

                res += toupper((*it));

                if (++count == K)

                {

                    res +='-';

                    count = 0;

                }

            }

        }

        if (res.empty()) {

            return res;

        }

        

        if (res.back() == '-') res.pop_back();

        

        reverse(res.begin(), res.end());

        

        return res;

    }

};

========

string licenseKeyFormatting(string S, int K) { int c = 0; string ret = ""; ret.reserve(S.size()); for(auto itr = S.rbegin(); itr != S.rend(); ++itr) { if(*itr == '-') continue; if(c == K) { c = 0; ret.push_back('-'); } ret.push_back(toupper(*itr)); ++c; } reverse(ret.begin(), ret.end()); return ret; }