12-25 leetcode retro

394. Decode String

  1. keep two stacks, one for int, one for all
  2. accumulate int/string
  3. [ => push k, decoded to stack
  4. ] => pop k, decoded, then wip string = decode+ str*k
class Solution {
public:
    string decodeString(string s) {
        stack<int> int_stack;
        stack<string> str_stack;//all decoded
        int num = 0;
        string str;
        for (char c: s) {
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            } else if (isalpha(c)) {
                str += c;
            } else if (c == '[') {
                int_stack.push(num);
                num = 0;
                str_stack.push(str);
                str = "";
            } else if (c == ']') {
                //decode  k[str] => 
                int k = int_stack.top(); int_stack.pop();
                string decoded = str_stack.top(); str_stack.pop();
                string ktmp;
                for (int i = 0; i < k; ++i) {
                    ktmp += str;
                }
                str = decoded + ktmp;
            }
        }
        return str;
    }
};

1200. Minimum Absolute Difference

find the mini abs diff, and pick out and pair match it

class Solution {
public:
    vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
        sort(begin(arr), end(arr));
        int min_diff = INT_MAX;
        for (int i = 1; i < arr.size(); i++) {
            min_diff = min(min_diff, abs(arr[i-1] - arr[i]));
        }
        vector<vector<int>> ans;
        for (int i = 1; i < arr.size(); i++) {
            if (abs(arr[i-1]-arr[i]) == min_diff) {
                ans.push_back({arr[i-1],arr[i]});
            }
        }
        return ans;
    }
};

231. Power of Two

  1. How to get / isolate the rightmost 1-bit : x & (-x).
  2. How to turn off (= set to 0) the rightmost 1-bit : x & (x - 1). ```cpp class Solution { public: bool isPowerOfTwo(int n) { if (n == 0) return false; long x = n; return (x & (-x)) == x; } };

class Solution { public: bool isPowerOfTwo(int n) { if (n == 0) return false; long x = n; return (x & (x - 1)) == 0; } };


## 143. Reorder List

basic linked list operations

```cpp
class Solution {
public:
    void reorderList(ListNode* head) {
        //find mid
        //reverse second half
        //merge two into one
        ListNode* mid = midRight(head);
        ListNode* second = reverse(mid);
        splice(head, second);
    }
    
    ListNode* midRight(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    
    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    
    ListNode* splice(ListNode* first, ListNode* second) {
        while (second->next) {
            ListNode* firstNext = first->next;
            first->next = second;
            first = firstNext;
            
            ListNode* secondNext = second->next;
            second->next = first;
            second = secondNext;
        }
        return first;
    }
};

210. Course Schedule II

topo order, checking order.size() for impossible courses(cycle)

 class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
        //graph and indegree
        //bfs with indegree 0
        //only enqueue if indegree 0
        //pop in order, ans is len(order) == n
        vector<vector<int>> graph(n);
        vector<int> indegree(n);
        for (auto e: prerequisites) {
            int to = e[0], from = e[1];
            graph[from].push_back(to);
            indegree[to]++;
        }
        
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> order;
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            order.push_back(cur);
            for (int next: graph[cur]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        if (order.size() != n) return {}; //<== need to check if topo order cover everyone
        return order;
    }
};

56. Merge Intervals

sort by starting, and merge overlapping ending

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ans;
        for (auto& e: intervals) {
            int start = e[0], end = e[1];
            if (ans.empty() || ans.back()[1] < e[0]){
                ans.push_back(e);
            } else {
                int newEnd = max(ans.back()[1],e[1]);
                ans.back()[1] = newEnd;
            }
        }
        return ans;
        
    }
};

227. Basic Calculator II

see Basic Calculator

1153. String Transforms Into Another String

TODO out degree of a node at most 1, one can mapping to two! size of set str1 > size of set str2 what about cycle? it is ok as long as we can a one unused node in s2

abcd, a->b->c->d, we could first do d->a, then do the following. bcdb, ^——-|

class Solution {
public:
    bool canConvert(string str1, string str2) {
        if (str1.size() != str2.size()) return false;
        if (str1 == str2) return true;
        unordered_map<char, char> mapping;
        int n= str1.size();
        for (int i = 0; i < n; i++) {
            char c1 = str1[i], c2 = str2[i];
            if (mapping.count(c1) && mapping[c1] != c2) {
                return false;
            }
            mapping[c1] = c2;
        }
        return set(str2.begin(), str2.end()).size() < 26;
    }
};
Written on December 25, 2021