本週題目

1. Middle of the Linked List
2. Backspace String Compare
3. Min Stack
4. Diameter of Binary Tree
5. Last Stone Weight
6. Contiguous Array
7. Perform String Shifts

Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3. (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:
Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:
The number of nodes in the given list will be between 1 and 100.

Solution

1. 先遍歷一次數列，找出 linked list 的長度。
2. 因為是 linked list，在遍歷之前，我們必須先創一個 ListNode 指向原本 linked list 的頭。
3. 從頭遍歷到一半長度的位置回傳。

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
   public:
    ListNode* middleNode(ListNode* head) {
        ListNode* tmp = head;

        int count = 0;
        while (head) {
            count++;
            head = head->next;
        }
        // printf(" with count = %d", count);

        for (int i = 0; i < count / 2; i++) {
            tmp = tmp->next;
        }

        return tmp;
    }
};

Function to print a linked list

void printList(ListNode* node) {
    std::cout << "[";

    while (node) {
        std::cout << node->val;
        if (node->next != NULL)
            std::cout << ", ";
        node = node->next;
    }

    std::cout << "]";
}

</br>

Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:
Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:
Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:
1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.

Follow up:
Can you solve it in O(N) time and O(1) space?

Solution 1

1. 創兩組新的字串分別存放處理過後的 S 和 T。
2. 對兩組字串分別遍歷一次，若遇到 # 則刪去新字串最後一個字母，若無則將目前字母加入新字串。
3. 需特別處理新字串為空又遇到 # 沒有字母可以刪除的情形。
4. 最後判斷兩組新字串是否相同。

class Solution {
   public:
    bool backspaceCompare(string S, string T) {
        string s = "";
        for (char c : S) {
            if (c == '#') {
                if (s.size())
                    s.pop_back();
            } else
                s.push_back(c);
        }

        string t = "";
        for (char c : T) {
            if (c == '#') {
                if (t.size())
                    t.pop_back();
            } else
                t.push_back(c);
        }

        return (s == t);
    }
};

Solution 2

• Solution 1 簡潔一點的寫法。

class Solution {
   public:
    bool backspaceCompare(string S, string T) {
        string s = "", t = "";
        for (char c : S) {
            (c == '#') ? (s.size() > 0) ? s.pop_back() : void() : s.push_back(c);
        }
        for (char c : T) {
            (c == '#') ? (t.size() > 0) ? t.pop_back() : void() : t.push_back(c);
        }

        return (s == t);
    }
};

Solution 3

• Follow up: O(N) time and O(1) space => 不另外存新的字串。

1. 因為 # 是往前刪去前一個字母，我們用兩個 index 分別從後往前遍歷字串。
2. 因為 # 有可能重複出現，我們需要紀錄目前在兩數列分別出現以及使用了幾個 #，以處理需要連續刪除的情形。
3. 兩組字串分別從後往前遍歷，當遇到 #，累加，不是 #，累減，直到出現的 # 都使用掉（這麼做是為了當有 # 還沒使用的情形下，表示該字母會被刪除，跳過該字母不進行比較），或是已遍歷到字首。
4. 兩組字串會停在刪去的字母數等於 # 出現的字數，比較兩字串最後一個字母，不同則表示兩字串不同。
5. 若兩字串最後一個字母相同，兩字串繼續往前遍歷，直到兩字串都遍歷完。
6. 當其中一個字串遍歷完，另一個字串還沒，表示兩字串不同。
7. 兩字串同時被刪光則兩字串相同。

class Solution {
   public:
    bool backspaceCompare(string S, string T) {
        int sIdx = S.size() - 1, tIdx = T.size() - 1;
        int sCnt = 0, tCnt = 0;
        while (sIdx >= 0 || tIdx >= 0) {
            while (sIdx >= 0 && (S[sIdx] == '#' || sCnt > 0)) {
                if (S[sIdx] == '#')
                    sCnt++;
                else
                    sCnt--;

                sIdx--;
            }

            while (tIdx >= 0 && (T[tIdx] == '#' || tCnt > 0)) {
                if (T[tIdx] == '#')
                    tCnt++;
                else
                    tCnt--;

                tIdx--;
            }

            if (sIdx < 0 || tIdx < 0)
                return (sIdx == tIdx);

            if (S[sIdx] == T[tIdx]) {
                sIdx--;
                tIdx--;
            } else
                return false;
        }

        return (sIdx == tIdx);
    }
};

</br>

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

Hint #1
Consider each node in the stack having a minimum value. (Credits to @aakarshmadhavan)

1. 這題要幫 stack 加一個找最小值的功能。
2. push(x) 和 pop() 兩個功能要特別去判斷一下當前的值是不是最小值。

Solution 1

1. 先設一個變數 min，初始為整數最大值。
2. 這邊有個小 trick，因為我們在做 pop() 的時候，如果 pop() 到最小值，我們會不知道之前的最小值是多少。
3. 所以我們在 push(x) 的時候，如果 x 小於或等於最小值，我們把之前的最小值先推進去當作資訊 -> 先 push(min) 再 push(x)。
   ex. [0, 1, 2] 最小值 min = 0 -> push(-1) -> [0, 1, 2, 0, -1] 最小值 min = -1。
4. 這樣當我們 pop() 到最小值的時候，就可以把最小值設成之前那個，並且多做一次 pop() 把暫存的最小值資訊丟掉。
   ex. [0, 1, 2, 0, -1] 最小值 min = -1 -> pop() twice -> [0, 1, 2] 最小值 min = 0。
5. 要注意這邊如果在 push(x) 的時候，如果 x 等於最小值，也要把之前的最小值先推進去。
   ex. [0, 1, 2, 0] 最小值 min = 0 -> pop() 0 出來後會不知道之前的最小值是多少。
   所以我們在推 0 進去 [0, 1, 2] 的時候，先多送一個 0 進去 -> [0, 1, 2, 0, 0]。
   之後把 0 拿出來的時候，因為它也是最小值，所以會多 pop() 一次 -> [0, 1, 2] 而且最小值 min = 0。

class MinStack {
   private:
    stack<int> s;
    int min;

   public:
    /** initialize your data structure here. */
    MinStack() {
        min = INT32_MAX;
    }

    void push(int x) {
        if (x <= min) {
            s.push(min);
            min = x;
        }
        s.push(x);
    }

    void pop() {
        int top = s.top();
        s.pop();
        if (top == min) {
            min = s.top();
            s.pop();
        }
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return min;
    }
};

Solution 2

• 用兩個 stack，一個做普通的 push(x) 和 pop()，一個用來紀錄曾經的最小值。

class MinStack {
   private:
    stack<int> s;
    stack<int> sMin;

   public:
    /** initialize your data structure here. */
    MinStack() {
    }

    void push(int x) {
        if (sMin.empty() || x <= sMin.top()) sMin.push(x);
        s.push(x);
    }

    void pop() {
        if (s.top() == sMin.top()) sMin.pop();
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return sMin.top();
    }
};

</br>

Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

      1
     / \
    2   3
   / \     
  4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Solution 1

1. 要找出最遠兩個 node 的距離，我們考慮使用遞迴，通常 binary tree 的題型都適用遞迴法。
2. 因為最遠的距離有可能不會經過 root，我們要考慮三種情形的最大值：
   -- 有經過 node 的 diameter = 左邊的 MAX depth + 右邊的 MAX depth。
   -- 左邊 sub-tree 的 diameter -> 適用遞迴。
   -- 右邊 sub-tree 的 diameter -> 適用遞迴。
3. 從 root 開始遞迴的方式相當於從最下層一路累加找出每個 node 的 MAX depth，即 std::max(left, right) + 1。
4. 我們設一個 global 的變數 diameter，在遞迴的過程中一邊更新 diameter = std::max(diameter, left + right)。
5. 遞迴在最後抵達 root 的時候結束，diameter 即是我們要的最遠兩個 node 的距離。

class Solution {
   private:
    int diameter;

   public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return diameter;
    }

    int maxDepth(TreeNode* node) {
        if (!node) return 0;
        int left = maxDepth(node->left);
        int right = maxDepth(node->right);
        diameter = max(diameter, left + right);
        return max(left, right) + 1;
    }
};

Solution 2

• 和 Solution 1 做法相同，只是將 global 的變數 diameter 改用指標傳入 maxDepth，在遞迴時同時更新。

class Solution {
   public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        maxDepth(root, diameter);
        return diameter;
    }

    int maxDepth(TreeNode* node, int& diameter) {
        if (!node) return 0;

        int left = maxDepth(node->left, diameter);
        int right = maxDepth(node->right, diameter);
        diameter = max(diameter, left + right);

        return max(left, right) + 1;
    }
};

</br>

Last Stone Weight

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

Example 1:
Input: [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

Note:
1 <= stones.length <= 30
1 <= stones[i] <= 1000

Hint #1
Simulate the process. We can do it with a heap, or by sorting some list of stones every time we take a turn.

Solution 1

1. 排序（使用 #include <algorithm> 中的 std::sort()）找出前兩大的值，紀錄下它們的差值，並將這兩個值從原數列移出。
2. 若差值不為 0，則將差值推入原數列。
3. 重複直到數列只剩下一個值或為空。

class Solution {
   public:
    int lastStoneWeight(vector<int>& stones) {
        while (stones.size() > 1) {
            sort(stones.begin(), stones.end());
            int diff = stones[stones.size() - 1] - stones[stones.size() - 2];
            stones.erase(stones.end() - 2, stones.end());

            if (diff)
                stones.push_back(diff);
        }

        return (stones.size()) ? stones[0] : 0;
    }
};

Solution 2

• 和 Solution 1 一樣的做法，使用 pop_back() 取代 erase()。

class Solution {
   public:
    int lastStoneWeight(vector<int>& stones) {
        while (stones.size() > 1) {
            sort(stones.begin(), stones.end());
            int max = stones[stones.size() - 1];
            stones.pop_back();
            int diff = max - stones[stones.size() - 1];
            stones.pop_back();

            if (diff)
                stones.push_back(diff);
        }

        return (stones.size()) ? stones[0] : 0;
    }
};

Solution 3

1. 將原字串依序丟入 #include <queue> 的 std::priority_queue 中。
2. 利用 priority queue 的特性，不需要在 while 迴圈裡重複做 sorting，只需要將前兩大值的差值推入 priority queue 中。

class Solution {
   public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> priority_q;
        for (int stone : stones) priority_q.push(stone);

        while (priority_q.size() > 1) {
            int max1 = priority_q.top();
            priority_q.pop();
            int max2 = priority_q.top();
            priority_q.pop();
            int v = abs(max1 - max2);
            if (v) priority_q.push(v);
        }

        return (priority_q.size()) ? priority_q.top() : 0;
    }
};

Solution 4

• Solution 3 簡潔一點的寫法。

class Solution {
   public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> priority_q(begin(stones), end(stones));

        while (priority_q.size() > 1) {
            int max1 = priority_q.top();
            priority_q.pop();
            int max2 = priority_q.top();
            priority_q.pop();
            if (max1 - max2) priority_q.push(max1 - max2);
        }

        return (priority_q.size()) ? priority_q.top() : 0;
    }
};

</br>

Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

Solution 1 (Time Limit Exceeded)

• 想了一個暴力解，果然用兩個迴圈是行不通的... 還是紀錄一下解題想法。

1. 遍歷所有子數列，遇到 0 減 1，遇到 1 加 1，如果總和為 0，表示這個子數列有一樣多的 0 和 1。
2. 找出有相同數目的 0 和 1 且最長的子數列長度。
3. 如果剩下的子數列長度小於前面得到的最長子數列長度，跳出迴圈，前面得到的最長子數列長度即為解。

class Solution {  // Time Limit Exceeded
   public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (!n) return 0;

        int ans = 0;
        for (int j = 0; j < n - 1; j++) {
            if (n - j <= ans) break;

            int sum = (nums[j] * 2) - 1;
            for (int i = j + 1; i < n; i++) {
                sum += (nums[i] * 2) - 1;
                int len = i - j + 1;
                if ((sum == 0) && (len > ans))
                    ans = len;
            }
        }

        return ans;
    }
};

Solution 2

1. 看來我們只能遍歷一次數列，判斷規則相同，遇到 0 減 1，遇到 1 加 1，如果總和為 0，表示這個子數列有一樣多的 0 和 1。
2. 從頭累加數列，若在兩個不同位置有相同的總和，表示兩個位置的總和差為 0 -> 這兩個位置中間的子數列有相同數目的 0 和 1。
3. 建一個 hashmap，紀錄不同總和出現的位置 -> hashmap {sum, index}，若是總和在 hashmap 中已經出現過，這個有相同數目的 0 和 1 的子數列長度即為當前的 index 減去存在 hashmap 中的 index。
4. 因為我們要找有相同數目的 0 和 1 且最長的子數列長度 -> 在 hashmap 中只紀錄不同總和出現的第一個位置。
5. 找出有相同數目的 0 和 1 且最長的子數列長度。
6. 注意初始化 hashmap 的時候，需給予 sum = 0 的時候 index = -1 的條件，這是為了總和第一次出現 0 的時候，表示這個子數列是從原數列起始位置 index = 0 開始的，這時我們需要直接去計算目前子數列的長度，而不是去建立 hashmap 的映射。

class Solution {
   public:
    int findMaxLength(vector<int>& nums) {
        int ans = 0;
        int sum = 0;

        unordered_map<int, int> hmap = {{0, -1}};
        for (int i = 0; i < nums.size(); i++) {
            sum += (nums[i] * 2) - 1;
            if (!hmap.count(sum))
                hmap[sum] = i;
            else if (i - hmap[sum] > ans)
                ans = i - hmap[sum];
        }

        return ans;
    }
};

</br>

Perform String Shifts

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]:

direction can be 0 (for left shift) or 1 (for right shift). 
amount is the amount by which string s is to be shifted.
A left shift by 1 means remove the first character of s and append it to the end.
Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.

Return the final string after all operations.

Example 1:
Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation:
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

Example 2:
Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]
Output: "efgabcd"
Explanation:
[1,1] means shift to right by 1. "abcdefg" -> "gabcdef"
[1,1] means shift to right by 1. "gabcdef" -> "fgabcde"
[0,2] means shift to left by 2. "fgabcde" -> "abcdefg"
[1,3] means shift to right by 3. "abcdefg" -> "efgabcd"

Constraints:
1 <= s.length <= 100
s only contains lower case English letters.
1 <= shift.length <= 100
shift[i].length == 2
0 <= shift[i][0] <= 1
0 <= shift[i][1] <= 100

Hint #1
Intuitively performing all shift operations is acceptable due to the constraints.

Hint #2
You may notice that left shift cancels the right shift, so count the total left shift times (may be negative if the final result is right shift), and perform it once.

Solution 1

• 這題滿直覺的，右移一格表示把字串最右邊的字母丟到字串最左邊，兩格就做兩次；左移則反之。
  • 右移一格 -> s = 字尾 + 刪掉字尾剩下的字串。
  • 左移一格 -> s = 刪掉字首剩下的字串 + 字首。

class Solution {
   public:
    string stringShift(string s, vector<vector<int>>& shift) {
        for (auto instruction : shift) {
            bool direction = instruction[0];
            int amount = instruction[1];
            for (int i = 0; i < amount; i++) {
                if (direction)
                    s = s[s.size() - 1] + s.substr(0, s.size() - 1);
                else
                    s = s.substr(1, s.size() - 1) + s[0];
            }
        }

        return s;
    }
};

Solution 2

• 根據 Hint #2，把指令中左移和右移的總和先做抵銷，再執行最後的指令。

class Solution {
   public:
    string stringShift(string s, vector<vector<int>>& shift) {
        int final = 0;
        for (auto instruction : shift) {
            bool direction = instruction[0];
            int amount = instruction[1];
            final += (direction) ? amount : -amount;
        }

        for (int i = 0; i < abs(final); i++) {
            if (final > 0)
                s = s[s.size() - 1] + s.substr(0, s.size() - 1);
            else
                s = s.substr(1, s.size() - 1) + s[0];
        }

        return s;
    }
};

</br>

• Source code: george16886@GitHub
  • [x] Programming language: C++
  • [x] Environment: ubuntu 16.04
  • [x] Tool: Visual Studio Code
• Category: 30-Day LeetCoding Challenge
• Original post @george16886's blog