## 198. House Robber (2024/01/21)

### Topic
Dynamic Programming

### Solution

#### Recursive relationship
P(k): the max profit we can get from robbing all the way to the k-th house securely.
C(k): the amount of the cash stashed at house k.
_P(k) = MAX(P(k-1), P(k-2) + C(k))_

### Code

class Solution {
public:
    int rob(vector<int>& nums) {
        auto len_nums = nums.size();
        if (len_nums == 1) {
            return nums[0];
        }
        vector<int> profits(len_nums);
        profits[0] = nums[0];
        profits[1] = max(nums[1], nums[0]);
        for (int i = 2; i < len_nums; i++) {
            profits[i] = max(profits[i-2]+nums[i], profits[i-1]);
        }
        return profits[len_nums-1];
    }
};

## 645. Set Mismatch (2024/01/22)

### Topic
Hash Table

### Solution
* Note: The ordering is **NOT** guaranteed
* The first loop finds duplication.
* The second loop finds out the missing value.

#### Better solution
* Use the input array for storage since the range of the input is already known.

### Code

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        unordered_map<int, bool> exists;
        auto len_nums = nums.size();
        vector<int> res(2, 0);

        for (int i = 0; i < len_nums; i++) {
            if (exists.find(nums[i]) == exists.end()) {
                exists[nums[i]] = true;
            } else {
                res[0] = nums[i];
            }
        }
        for (int i = 1; i <= len_nums; i++) {
            if (!exists[i]) {
                res[1] = i;
            }
        }

        return res;
    }
};

## 1239. Maximum Length of a Concatenated String with Unique Characters (2024/01/23)

### Topic
Backtracking

### Solution
* Brute force to calculate every combination.
* When the newly concatenated string violates the rule, stop iteration.

### Code

class Solution {
public:
    int maxLength(vector<string>& arr) {
        array<bool, 26> mask = {false};
        recurse(arr, mask, 0, 0);
        auto max_len = 0;
        for (auto length : result) {
            max_len = max(max_len, length);
        }
        return max_len;
    }

    void recurse(vector<string>& arr, array<bool, 26> mask, int index, int curr) {
        if (index >= arr.size()) {
            result.push_back(curr);
            return;
        }
        recurse(arr, mask, index+1, curr);
        auto curr_str = arr[index];
        for (auto curr_char : curr_str) {
            int ascii = curr_char - 97;
            if (mask[ascii]) {
                return;
            }
            mask[ascii] = true;
        }
        curr += curr_str.length();
        recurse(arr, mask, index+1, curr);
    }

    vector<int> result;
};

## 457. Pseudo-Palindromic Paths in a Binary Tree (2024/01/24)

### Topic
DFS, Bit manipulation

### Solution
* At most 1 odd frequency of number is allowed. Walk through each path through DFS to check if the path is pseudo-palindromic.
* Since only 1 to 9 are possible values, bit manipulation could reduce memory usage significantly.

### Code

/**
 * 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 pseudoPalindromicPaths (TreeNode* root) {
        count = 0;
        uint16_t odds = 0;
        dfs(root, odds);
        return count;
    }

    void dfs(TreeNode* root, uint16_t odds) {
        auto val = root->val;
        odds ^= (0x01 << val);
        if (!root->left && !root->right) {
            if (odds == 0 || std::popcount(odds) == 1) {
                ++count;
            }
            return;
        }
        if (root->left) {
            dfs(root->left, odds);
        }
        if (root->right) {
            dfs(root->right, odds);
        }
    }

    int count;
};

## 1143. Longest Common Subsequence (2024/01/25)

### Topic
Dynamic Programming

### Solution

#### Recursive relationship
Define function D(i, j) is the longest common subsequence length at the i-th character of text1 and j-th character of text2.
* _D(i, j) = D(i-1, j-1) + 1_, if character _text1(i) = text2(j)_
* _D(i, j) = MAX(D(i-1, j), D(i, j-1))_, otherwise

Our target is to get _D(text1.length-1, text2.length-1)_.

### Code

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        auto length1 = text1.length();
        auto length2 = text2.length();
        vector<vector<int>> dp(length1, vector<int>(length2));
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                if (text1[i] == text2[j]) {
                    dp[i][j] = 1;
                    if (i - 1 >= 0 && j - 1 >= 0) {
                        dp[i][j] += dp[i-1][j-1];
                    }
                } else {
                    auto from_row = 0;
                    auto from_col = 0;
                    if (i - 1 >= 0) {
                        from_col = dp[i-1][j];
                    }
                    if (j - 1 >= 0) {
                        from_row = dp[i][j-1];
                    }
                    dp[i][j] = max(from_col, from_row);
                }
            }
        }
    return dp[length1 - 1][length2 - 1];
    }
};

## 232. Implement Queue using Stacks (2024/01/29)

### Topic
Stack

### Solution
Use a stack _A_ to store incoming data and another stack _B_ to store reversed values from stack _A_.
* push: Push to _A_.
* pop: Load elements of _A_ into _B_, if _B_ is empty. Then, pop the top element of _B_.
* peak: Like pop, but not remove the top element.
* empty: Use an external counter to calculate pushes and pops.

**Note: Actually, there is no need to keep the original status of _A_ when loading the elements into _B_.**

### Code

class MyQueue {
public:
    MyQueue() {
        q_size = 0;
        push_since_last_reload = 0;
    }
    
    void push(int x) {
        reverse_q.push(x);
        q_size++;
        push_since_last_reload++;
    }
    
    int pop() {
        if (need_reload_q()) {
            reload_q();
        }
        auto res = q.top();
        q.pop();
        q_size--;
        return res;
    }
    
    int peek() {
        if (need_reload_q()) {
            reload_q();
        }
        return q.top();
    }
    
    bool empty() {
        return q_size == 0;
    }

    bool need_reload_q() {
        return q.size() == 0 && reverse_q.size() != 0;
    }

    void reload_q() {
        stack<int> tmp(reverse_q);
        for(int i = 0; i < push_since_last_reload; i++) {
            q.push(reverse_q.top());
            reverse_q.pop();
        }
        reverse_q = tmp;
        push_since_last_reload = 0;
    }

    stack<int> reverse_q;
    stack<int> q;
    int q_size;
    int push_since_last_reload;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

## 150. Evaluate Reverse Polish Notation (2024/01/30)

### Topic
Stack

### Solution
A very good example of the application of stack.

**Note: It is better to check the incoming operand is a number or not. The repetition codes of popping operands can be saves which reduces memory usage significantly without slowering the program too much.**

Additional Note: Some programming languages like Python use floor division not truncate division. That takes an additional step to covert the result.

### Code

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> operands;
        for (auto token : tokens) {
            if (token == "+") {
                auto op1 = operands.top();
                operands.pop();
                auto op2 = operands.top();
                operands.pop();
                operands.push(op2 + op1);
            } else if (token == "-") {
                auto op1 = operands.top();
                operands.pop();
                auto op2 = operands.top();
                operands.pop();
                operands.push(op2 - op1);
            } else if (token == "*") {
                auto op1 = operands.top();
                operands.pop();
                auto op2 = operands.top();
                operands.pop();
                operands.push(op2 * op1);
            } else if (token == "/") {
                auto op1 = operands.top();
                operands.pop();
                auto op2 = operands.top();
                operands.pop();
                operands.push(op2 / op1);
            } else {
                operands.push(stoi(token));
            }
        }
        return operands.top();
    }
};

## 739. Daily Temperatures (2024/01/31)
*What? Leetcode starts selling ads.*

### Topic
Array

### Solution
Iterate the temperatures reversely:
1. If the next temperature is higher than today, then the output value of today is 1.
2. If not, and the output value of the next day is 0, the output of today is 0 too.
3. If the next value is not 0, then jump to the next _n_ output value which is the result of the previous element to find the temperature warmer than today repeatedly.

### Code

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        auto seq_length = temperatures.size();
        vector<int> result(seq_length, 0);
        result[seq_length-1] = 0;
        for (int i = seq_length - 2; i >= 0; i--) {
            int j = i + 1;
            while (j < seq_length) {
                if (temperatures[j] > temperatures[i]) {
                    result[i] = j - i;
                    break;
                } else {
                    if (result[j] == 0) {
                        break;
                    }
                    j += result[j];
                }
            }
        }
        return result;
    }
};