LeetCode Weekly Contest 150

a.cpp

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) 
    {
        map<char, int> m;
        for(auto x : chars)
        {
            m[x]++;
        }
        
        int n = words.size(), res = 0;
        for(int i = 0; i < n; i++)
        {
            map<char, int> m2;
            for(auto x : words[i])
            {
                m2[x]++;
            }
            int ok = 1;
            auto it = m2.begin();
            while(it != m2.end())
            {
                if(it -> second > m[it -> first])
                {
                    ok = 0; 
                    break;
                }
                else
                {
                    it++;
                }
            }
            if(ok)
            {
                res += words[i].size();
            }
        }
        return res;
    }
};

b.cpp

/**
 * 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:
    
    int maxLevelSum(TreeNode* root) 
    {
        queue<TreeNode*> q;
        q.push(root);
        int lv = 1, max_lv = 1, cur_sum = 0, max_sum = INT_MIN;

        while(q.size())
        {
            cur_sum = 0;
            int sz = q.size();

            while(sz--)
            {
                root = q.front();
                q.pop();
                cur_sum += root -> val;
                if(root -> left)
                {
                    q.push(root -> left);
                }
                if(root -> right)
                {
                    q.push(root -> right);
                }
            }
            if(cur_sum > max_sum)
            {
                max_sum = cur_sum;
                max_lv = lv;
            }
            lv++;
        }    
        return max_lv;
    }
};

c.cpp

int dir[4][2]  = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // u d l r
class Solution 
{
public:
    int maxDistance(vector<vector<int>>& grid) 
    {
        int res = 0, has_0 = 0;
        int row = grid.size(), col = grid[0].size();
        int dp [100][100] = {0};
        
        queue<pair<int, int>> q;
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(grid[i][j] == 1)
                {
                    q.push({i, j});
                }
                else
                {
                    has_0 = 1;
                }
            }
        }
             
        if(has_0 == 0 || q.size() == col * row) // all 1 or all 0
        {
            return -1;
        }
        
        int cur_row, cur_col;
        while(q.size())
        {
            cur_row = q.front().first;
            cur_col = q.front().second;
            res = max(res, dp[cur_row][cur_col]);
            q.pop(); // finish dealing that node
            
            int n_row, n_col;
            for(int i = 0; i < 4; i++) // dir
            {
                n_row = cur_row + dir[i][0];
                n_col = cur_col + dir[i][1];
                if(n_row >= 0 && n_row < row && n_col >= 0 && n_col < col && grid[n_row][n_col] == 0 && dp[n_row][n_col] == 0) // in the grid and is water and unvisited 
                {
                    dp[n_row][n_col] = dp[cur_row][cur_col] + 1; // update dist for touched part
                    q.push({n_row, n_col}); // push node that can be visited
                }
            }
        }
       
        return res == 0 ? -1 : res;
    }
};

d.cpp

class Solution 
{
public:
    string lastSubstring(string s) 
    {
        int cand_pos = 0; // position that can be the start of candidate
        int max_pos = 0; // position where max character lies
        int n = s.size();
        int first_find = 0; // if this is the first kind of such substring starting at position i
        int offset = 1; // string offset for lexicographical comparison
        char max_char = 0;

        for(int i = 0; i < n; i++)
        {
            if(s[i] > max_char) // if this char is greater than the previous, use this
            {
                max_char = s[i]; // update max character
                max_pos = i; // update max pos
                first_find = 1; // the string starting at this position is currently the first and the only one
                offset = 1;
            }
            else if(first_find == 0) // compare the candidates
            {
                if(max_pos + offset < n) // lies in the legal position
                {
                    if(s[i] > s[max_pos + offset]) // check if another greater char exists
                    {
                        max_pos = i - offset; // if so, update the max position
                        first_find = 1; // give up the old 
                    }
                    else if(s[i] == s[max_pos + offset]) // increment
                    {
                        offset++;
                    }
                    else
                    {
                        first_find = 1; // give up such result if encounter a smaller one and keep the old
                    }
                }
            }
            else if(s[i] == max_char) // else if this char is equal, which means find the second one (i.e. string startin start with same char) to compare
            {
                offset = 1; // reset offset
                first_find = 0; // mark as false for not the first one
            }
        }
        return s.substr(max_pos);
    }    
};