###### tags: `grind75`, `week1`

# Grind 75 Week2

# 1. [Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/solutions/)
:::success
# Recursive

- Time: $O(N)$：若都是 valid，每個節點都要走過
- Space: $O(logN)$：同一時間 stack 最多就是一條 path 從 root 到 leaf。

| Runtime | 11 ms Beats 81.53% |
| --- | --- |
| Memory | 21.6 MB Beats 13.31% |

/**
 * 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:
   // abs(heightLeft - heightRight) <= 1
    bool isBalanced(TreeNode* root) {
      if(!root) return true;
      return heightOfInvalid(root) != -1;
    }

    int heightOfInvalid(TreeNode * root) {
      if(!root->left && !root->right) return 1;

      int leftHeight = heightOfInvalid(root->left);
      int rightHeight = heightOfInvalid(root->right);
      
      if (leftHeight < 0) return -1;
      if (rightHeight < 0) return -1;
      if (abs(leftHeight - rightHeight) > 1) return -1;
      return 1 + max({leftHeight, rightHeight});
    }
};

:::

:::info
# DFS
- TC: O(n)
- SC: O(n)

var isBalanced = function(root) {
	if (!root) return true;
	// -1 is the unbalanced situation
    return getHeight(root) !== -1;
}

function getHeight(root) {
    if (!root) return 0;

    let leftHeight = getHeight(root.left);

    let rightHeight = getHeight(root.right);

    // if already unbalanced, return
    if (leftHeight == -1 || rightHeight == -1) return -1;
    
    // if unbalanced, return
    if (Math.abs(leftHeight - rightHeight) > 1) return -1;

    // reutrn the height of this subtree
    return Math.max(leftHeight, rightHeight) + 1;
}

:::

# 2. Linked List Cycle
:::success
## Loop
- Time: $O(n)$
- Space: $O(1)$

| Runtime | 7 ms Beats 95.27% |
| --- | --- |
| Memory | 8.2 MB Beats 49.43% |

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
      if(!head || !head->next) return false;

        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next) {
          slow = slow->next;
          fast = fast->next->next;
          if(slow == fast) return true;
        }
        return false;
    }
};

:::

:::info
# Hash Table
- TC: O(n)
- SC: O(n)

const hasCycle = function(head) {
    const seen = new Set();

    while (head) {
        if (seen.has(head)) return true;

        seen.add(head);
        head = head.next;
    }

    return false;
};

:::

# 3. Implement Queue using Stacks
:::success
# 解法

放東西進去 stack 前先倒出來到 stack2，放新的到 stack 最下面，再把 stack2 倒回去

- Time: $O(n)$
- Space: $O(n)$

class MyQueue {
public:
    stack<int> s;
    MyQueue() {
        
    }
    
    void push(int x) {
      stack<int> tmp;
      while(!s.empty()) {
        int top = s.top();
        tmp.push(top);
        s.pop();
      }
      s.push(x);
      while(!tmp.empty()) {
        int top = tmp.top();
        s.push(top);
        tmp.pop();
      }
    }
    
    int pop() {
      int top = s.top();
      s.pop();  
      return top;
    }
    
    int peek() {
        return s.top();
    }
    
    bool empty() {
        return s.empty();
    }
};

/**
 * 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();
 */

:::

:::info
- TC: O(1) for push(), O(n) for pop(), peek(), empty()
- SC: O(n)

var MyQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
};


MyQueue.prototype.push = function(x) {
    this.stack1.push(x);
};


MyQueue.prototype.pop = function() {
    if (this.stack2.length === 0) {
        while (this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2.pop();
};


MyQueue.prototype.peek = function() {
    if (this.stack2.length === 0) {
        while (this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2[this.stack2.length - 1];
};

MyQueue.prototype.empty = function() {
    return (this.stack1.length === 0 && this.stack2.length === 0);
};

:::

# 4. First Bad Version
:::success
## Binary Search

- Time: $O(logN)$
- Space: $O(1)$

| Runtime | 3 ms Beats 46.4% |
| --- | --- |
| Memory | 5.9 MB Beats 57.41% |

class Solution {
public:
    int firstBadVersion(int n) {
      int s = 1, e = n;
      int mid;
      bool bad;
      while(s <= e) {
        // 靠腰喔
        // mid = (s+e)/2; // signed integer overflow: 1063376696 + 2126753390 cannot be represented in type 'int' 
        mid = s + (e-s)/2;
        bad = isBadVersion(mid);
        if(bad) {
          e = mid-1;
        } else {
          s = mid+1;
        }
      }
      
      if(bad) {
        return mid;
      } else {
        return mid+1;
      }
    }
};

:::

:::info
# Binary Search
- TC: O(logn)
- SC: O(1)

var solution = function(isBadVersion) {
    return function(n) {
        let left = 1;
        let right = n;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
};

:::

# 5. Ransom Note
:::success
## Complexity

- Time: $O(\text{max}(L_r, L_m))$：loop
- Space: $O(1)$：fixed 26 array

## Code

**15 ms** Beats **68.18%**

**8.7 MB** Beats **78.75%**

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int note[26] = {0};
        int mag[26] = {0};
        for(int i = 0 ;i < ransomNote.size();i++) {
          note[ransomNote[i] - 'a']++;
        }
        for(int i = 0 ;i < magazine.size();i++) {
          mag[magazine[i] - 'a']++;
        }
        for(int i = 0 ;i < 26;i++) {
          if(mag[i] < note[i]) return false;
        }

        return true;
    }
};

:::

:::info
# Hash Table
- TC: O(n)
- SC: O(n)

var canConstruct = function(ransomNote, magazine) {
    const map = new Map();

    for (const char of magazine) {
        map.has(char)
        ? map.set(char, map.get(char) + 1)
        : map.set(char, 1);
    }

    for (const char of ransomNote) {
        if (
            !map.get(char) // 判斷字母是否存在
            || map.get(char) === 0 // 判斷字母數量是否一致（ ransomNote 的要少於等於 magazine ）
        ) return false;

        map.set(char, map.get(char) - 1); // 每次進來都扣除原本字母的次數
    }

    return true;
};

:::

# 6. Climbing Stairs
:::success
## Complexity

- Time: $O(n)$
- Space: $O(1)$

## Code

**0 ms** Beats **100%**

**6 MB** Beats **49.59%**

class Solution {
public:
    int climbStairs(int n) {
      int a[46] = { 0 };
      a[1] = 1;
      a[2] = 2;
      for(int i = 3 ; i <=n ;i++) {
        a[i] = a[i-1] + a[i-2];
      }
      return a[n];
    }
};

:::

:::info
# DP
- TC: O(n)
- SC: O(n)

var climbStairs = function(n) {
    if (n === 1) return 1;

    let dp = new Array(n + 1);

    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
};

:::

# 7. Longest Palindrome

:::success
## Loop

- Time: $O(n)$：看過整個 s 一次就結束了
- Space: $O(1)$：fixed-length 52 array

**0 ms** Beats **100%**
**6.6 MB** Beats **56.78%**

class Solution {
public:
    int longestPalindrome(string s) {
        int a[52] = {0};
        int left = s.size();
        int sum = 0;
        
        for(int i = 0;i< s.size();i++) {
          int index;
          if(s[i] >= 'a') {
            index = s[i] - 'a'+26; // 0~26 for A-Z, 27~51 for a-z
          } else {
            index = s[i] - 'A';
          }
          
          a[index]++;
          
          if(a[index]==2) {
            a[index]-=2;
            sum+=2;
            left-=2;
          }
        }

        return sum + (left > 0 ? 1 : 0);
    }
};

:::

:::info
# Hash Map
- TC: O(n)
- SC: O(n)

var longestPalindrome = function(s) {
    let freq = new Map();
    for (let i = 0; i < s.length; i++) {
        let c = s.charAt(i);
        freq.set(c, (freq.get(c) || 0) + 1);
    }
    let length = 0;
    let hasOddFreq = false;
    for (let [c, f] of freq) {
        if (f % 2 === 0) {
            length += f;
        } else {
            length += f - 1;
            hasOddFreq = true;
        }
    }
    return hasOddFreq ? length + 1 : length;
};

:::

# 8. Reverse Linked List
:::success
## Loop

- Time: $O(n)$
- Space: $O(1)$

**3 ms** Beats **95.52%**
**8.3 MB** Beats **86.13%**

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
      if(!head) return head;

      ListNode * temp = nullptr;
      ListNode * prev = nullptr;
      while(head) {
        temp = head->next;
        head->next= prev;
        prev = head;
        head = temp;
      }
      return prev;
    }
};

## Recursive

- Time: $O(n)$
- Space: $O(n)$

**3 ms** Beats **95.52%**
**8.6 MB** Beats **11.14%**

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
      if(!head) return head;

     ListNode* newHead = getNewHead(nullptr, head);
     return newHead;
    }
    ListNode* getNewHead(ListNode* prev, ListNode* head) {
      if(!head->next) {
        head->next = prev;
        return head;
      }
      ListNode * newHead = getNewHead(head, head->next);
      head->next = prev;
      return newHead;
    }
};

:::

:::info
# Brute Force
- TC: O(n)
- SC: O(1)

const reverseList = function(head) {
    if (!head) return null;

    let previous = null;
    let current = head;

    while (current) {
        let temp = current.next;
        current.next = previous; 
        previous = current;
        current = temp;
    }

    return previous;
}

# List Destructing Assignment

const reverseList = function(head) {
    if (!head) return null;

    let [prev, curr] = [null, head];

    while (curr) {
        [curr.next, prev, curr] = [prev, curr, curr.next]
    }

    return prev;
}

:::

# 9. Majority Element
:::success
# Boyer-Moore
T:O(n)
S:O(1)

24 ms Beats 39.58%
19.6 MB Beats 37.79%

class Solution {
public:
    int majorityElement(vector<int>& nums) {
      if(nums.size() == 1) return nums[0];
      
      int cand = nums[0];
      int count = 0;

      for(int i = 0;i<nums.size();i++) {
        if(nums[i] == cand) count++;
        else {
          count--;
          if(count == 0) {
            cand = nums[i];
            count = 1;
          }
        }
      }
      return cand;
    }
};

:::

:::info
# Boyer-Moore Majority Vote Algorithm
- TC: O(n)
- SC: O(1)

var majorityElement = function(nums) {
	let major = null, count = 0;

    for (let i = 0; i < nums.length; i++) {
        if (count === 0) major = nums[i];
        count += nums[i] === major ? 1 : -1;
    }

    return major;
}

:::