leetcode 12-04 retro

797. All Paths From Source to Target

basic dfs to find the end node note the backtracking won’t include the root node. so either add it first in the ans, move the mark/unmark to the scope of dfs

Note, we know it is a DGA, so we don’t need visited

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {   
        vector<vector<int>> res;
        vector<int> path;
        dfs(0,path,graph,res);
        return res;
    }
    
    void dfs(int cur, vector<int>& path, vector<vector<int>>& graph, vector<vector<int>>& res) {
        path.push_back(cur);
        if (cur == graph.size() - 1) {
            res.push_back(vector<int>(path));
        } else {
            for (int child: graph[cur]) {
                dfs(child, path, graph, res);
            }
        }
        path.pop_back();
    }
};

side note, the similarity of n-arry tree vs graph traverse

/* n-array tree */
void traverse(TreeNode root) {
    if (root == null) return;

    for (TreeNode child : root.children) {
        traverse(child);
    }
}


/* Graph */

boolean[] visited; // 记录被遍历过的节点
boolean[] visiting; // 记录从起点到当前节点的路径, !backtracking!
void traverse(Graph graph, int s) {
    if (visited[s]) return;
    // 经过节点 s，标记为已遍历
    visited[s] = true;
    // 做选择：标记节点 s 在路径上
    visiting[s] = true;
    for (int neighbor : graph.neighbors(s)) {
        traverse(graph, neighbor);
    }
    // 撤销选择：节点 s 离开路径
    visiting[s] = false;
}

721. Accounts Merge

ofc using Union Find, but how to find the range? scan all the emails
then how to assign id to each email? increment on each new email
connect emails and keep a map of email->name
from (email, name) pair and UF to find the groupID, build a map of groupID->{name, email1, email2…}, push name if it is empty.
map/set insert() for the first of

class UnionFind {
public:
    UnionFind(int n) {
        id = 0;
        father.resize(n);
        iota(father.begin(), father.end(), 0);
    }
    
    int find(int x) {
        if (father[x] == x) {
            return x;
        }
        father[x] = find(father[x]);
        return father[x];
    }
    
    void connect(int a, int b) {
        father[find(a)] = find(b);
    }
    
    
    int getID(string email){
        if (!emailToID.count(email)) {
            // cout << x << " id: " << id << endl;
            emailToID.insert({email,id++});
        }
        return emailToID[email];
    }
    
    int find(string x) {
        return find(getID(x));
    }
    
    void connect(string a, string b) {
        connect(getID(a), getID(b));
    }
    
public:
private:
    vector<int> father;
    map<string, int> emailToID;
    int id = 0;
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int numberOfEmails = 0;
        for (auto const& account: accounts) {
            numberOfEmails += (account.size() - 1);
        }
        UnionFind uf(numberOfEmails);
        map<string, string> emailToName;
        
        int id = 0;
        for (const vector<string>& account: accounts) {
            string name = account[0];
            for (int j = 1; j < account.size(); j++) {
                string email = account[j];
                emailToName[email] = name;
                uf.connect(account[1], email);
            }
        }
        
        map<int, vector<string>> groupByID;
        for (auto [email, name]: emailToName) {
            int groupID = uf.find(email);
            if (groupByID[groupID].empty()) groupByID[groupID].push_back(name);
            groupByID[groupID].push_back(email);
        }
        
        vector<vector<string>> ans;
        for (auto [key, emails]: groupByID) {
            ans.push_back(emails);
        }
        return ans;
    }
};

85. Maximal Rectangle

converts the problem in to 1D Histogram
it smells like DP problem TODO

from top to bottom, scan line by line, accumulate 1 and reset if see 0. then the problem reduce to 84. Largest Rectangle in Histogram

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<int> dp(n);
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[j] = matrix[i][j] == '1' ? dp[j] + 1: 0;
            }
            int curRowMax = maxAreaHistogram(dp);
            ans = max(ans, curRowMax);
        }
        return ans;
    }
    
    int maxAreaHistogram(vector<int>& heights) {
        stack<int> mono;//inc
        mono.push(-1);
        heights.push_back(-1);
        int ans = 0;
        for (int i = 0; i < heights.size(); i++) {
            while(mono.top()>= 0 && heights[mono.top()] > heights[i]) {
                int h = heights[mono.top()]; mono.pop();
                int w = i - mono.top() - 1;
                ans = max(ans, h * w);
            }
            mono.push(i);
        }
        heights.pop_back();
        return ans;
    }
};

198. House Robber

simple DP, dp[i] = max(dp[i-2]+cur, dp[i-1])
base case for i < 2
const space for dp, only need last two.

class Solution {
public:
//     int rob(vector<int>& nums) {
//         int n = nums.size();
//         if (n == 0) return 0;
//         if (n == 1) return nums[0];
//         vector<int> dp(n);
//         dp[0] = nums[0];
//         dp[1] = max(nums[0], nums[1]);
//         for (int i = 2; i < n; i++) {
//             dp[i] = max(dp[i-1],dp[i-2]+ nums[i]);
//         }
//         return dp[n-1];
//     }
    
    int rob(vector<int>& nums) {
        int t2 = 0, t1 = 0;
        for (int i = 0; i < nums.size(); i++) {
            int cur = max(t1, t2+ nums[i]);
            // t2, t1 = t1, cur;
            t2 = t1;
            t1 = cur;
        }
        return t1;
    }
};

328. Odd Even Linked List

mark the oddHead, oddRunner, evenHead, evenRunner
zip two list togather, runner always jump two steps
oddRunner->evenHead

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return head;
        ListNode* oddHead = head;
        ListNode* odd = oddHead;
        ListNode* evenHead = head->next;
        ListNode* even = evenHead;
        
        while (even && even->next) {
            odd->next = odd->next->next;
            odd = odd->next;
            
            even->next = even->next->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
        
    }
};

152. Maximum Product Subarray

we can’t disgard the min value just in case we run into a negative number
ride along, update the local_max/local_min
trap, cache the previous max/min for the calculation

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int max_so_far = nums[0];
        int min_so_far = nums[0];
        int ans = max_so_far;
        
        for (int i = 1; i < n; i++) {
            int cur = nums[i];
            int temp_max = max({cur, cur*max_so_far, cur*min_so_far});
            int temp_min = min({cur, cur*max_so_far, cur*min_so_far});
            max_so_far = temp_max;
            min_so_far = temp_min;
            ans = max(ans, max_so_far);
        }
        return ans;
    }
};

1032. Stream of Characters

Reversing and searching dict {xyz, abs} input fooobar..xyz, match on z.

longest prefix matching…Trie
but it is not the prefix, it is the suffix matching
build and trie backward and search the trie backward
using unique_ptr for the root of the trie, the result is just delete
not the best in real world use-case? as we can’t hold on the stream in real-time, but in batch? TODO

class TrieNode {
public:
    ~TrieNode() {
        for (auto node: next_){
            delete node;
        }
    }
    void rinsert(const string& s, int i){
        if (i == -1){
            is_word_ = true;
            return;
        }
        const int idx = s[i] - 'a';
        if (!next_[idx]) next_[idx] = new TrieNode();
        next_[idx]->rinsert(s, i-1);
    }
    
    bool rsearch(const string& s, int i){
        if (i == -1 || is_word_) return is_word_;
        int idx = s[i] - 'a';
        if (!next_[idx]) return false;
        return next_[idx]->rsearch(s, i-1);
    }
    
private:
    bool is_word_ = false;
    TrieNode* next_[26] = {0};
};

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        root_ = make_unique<TrieNode>();
        for (const string& w: words){
            root_->rinsert(w, w.size()-1);
        }
    }
    
    bool query(char letter) {
        stream_ += letter;
        return root_->rsearch(stream_, stream_.size() -1);
    }
private:
    string stream_;
    unique_ptr<TrieNode> root_;
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */

333. Largest BST Subtree

postorder as we need information from sub-tree so many things to check.

is that subtree a valid BST? adding isBST
if both are valid BST, left + self + right still a valid BST? adding min/max
largest number of ndoes of BST, adding size
keep the default value of minVal/maxVal invalid so the default value can’t be pick up during the cmp

why we min() for the minVal? why not just use the left.min? because left could be null.

struct NodeValue {
 bool isBST = true;
 int size = 0;
 int minVal = INT_MAX;
 int maxVal = INT_MIN;
 void print(){
     cout << " " << isBST << " " << size << " " << minVal << " " << maxVal << endl;
 };
};
class Solution {
public:
 int largestBSTSubtree(TreeNode* root) {
     return helper(root).size;
 }
    
 NodeValue helper(TreeNode* root) {
     if (!root) return NodeValue();
        
     NodeValue left = helper(root->left);
     NodeValue right = helper(root->right);
     NodeValue ret;
     // not a BST
     if (!left.isBST || !right.isBST ||
         (left.maxVal >= root->val || right.minVal <= root->val)){
         ret.isBST = false;
         ret.size = max(left.size, right.size);
         return ret;
     }
     // isBST, both OK, or just one single path tree;
     ret.isBST = true;
     ret.size = left.size + right.size + 1;
     // ret.minVal = root->left ? left.minVal : root->val;
     // ret.maxVal = root->right ? right.maxVal: root->val;
     ret.minVal = min(left.minVal, root->val);
     ret.maxVal = max(right.maxVal, root->val);
     return ret;
 }
};

708. Insert into a Sorted Circular Linked List

analyze all 3 cases when search for the insert position
and what if it is a cycle?

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) {
            head = new Node(insertVal, nullptr);
            head->next = head;
            return head;
        }
        
        Node* prev = head;
        Node* runner = head->next;
        bool inserted = false;
        
        auto prevOnTail_runnerOnHead = [&](){
            return prev->val > runner->val;
        };
        
        // 1. prev <= insertVal <= next
        // 2. insertVal < min (insert at the tail)
        // 3. insertVal > max (insert at the tail)
        while(true) {
            if ((prev->val <= insertVal && insertVal <= runner->val)||
                (prevOnTail_runnerOnHead() && insertVal < runner->val)||
                (prevOnTail_runnerOnHead() && prev->val < insertVal) 
               ) {
                prev->next = new Node(insertVal, runner);
                inserted = true;
                break;
            }
            
            prev = prev->next;
            runner = runner->next;
            if (prev == head) break;
        }
        
        //
        if (!inserted) {
            prev->next = new Node(insertVal, runner);
        }
        return head;
    }
};

Written on December 4, 2021