本週題目

1. Product of Array Except Self
2. Valid Parenthesis String
3. Number of Islands
4. Minimum Path Sum
5. Search in Rotated Sorted Array
6. Construct Binary Search Tree from Preorder Traversal
7. Leftmost Column with at Least a One

Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:
Input: [1,2,3,4]
Output: [24,12,8,6]

Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Solution 1

• 第一個想法是遍歷數列得到所有數字之積，再去除以相對應位置上的數。不過題目排除了使用除法的做法...

1. 只能用乘法，那就把數列以現在的位置，分為前半段數字的乘積和後半段數字的乘積（都不包含目前的數字），所求即為前半段乘積乘上後半段乘積。
2. 做法是使用兩組新的數列，初始為 1，分別累乘以及存下數列在每個位置的前半段乘積和後半段乘積，再將每個位置上兩數列相乘即為所求。

class Solution {
   public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();

        vector<int> productPrefix(n, 1);
        for (int i = 0; i < n - 1; i++)
            productPrefix[i + 1] = productPrefix[i] * nums[i];

        vector<int> productSuffix(n, 1);
        for (int i = n - 1; i > 0; i--)
            productSuffix[i - 1] = productSuffix[i] * nums[i];

        vector<int> ans(n);
        for (int i = 0; i < n; i++)
            ans[i] = productPrefix[i] * productSuffix[i];

        return ans;
    }
};

Solution 2

• Follow up: space complexity = O(1)。

1. 其實我們並不需要兩組新的數列，我們可以使用來回遍歷數列的方式，直接更新 output array。
2. 初始 output array 為 1，先從頭往後遍歷，累乘前面出現過的數，得到的 output array 為 Solution 1 中前半段數字的乘積。
3. 再從倒數第二個數遍歷回來，累乘 Solution 1 中後半段數字的乘積即為所求。

class Solution {
   public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 1);

        for (int i = 0; i < n - 1; i++)
            ans[i + 1] = ans[i] * nums[i];

        int suffix = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }

        return ans;
    }
};

</br>

Valid Parenthesis String

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
An empty string is also valid.

Example 1:
Input: "()"
Output: True

Example 2:
Input: "(*)"
Output: True

Example 3:
Input: "(*))"
Output: True

Note:
The string size will be in the range [1, 100].

Solution 1

1. 使用兩個 stack 分別紀錄左括號 ( 和星號 * 的位置。
2. 遍歷字串，遇到左括號 ( 或星號 * 時，將其 index 存入相對應的 stack。
3. 當遇到右括號 ) 時，檢查兩個 stack，若都為空，表示沒有能夠和這個右括號 ) 配對的符號 => invalid。
4. 若左括號 ( stack 不為空，取出一個左括號 ( 與右括號 ) 配對抵銷，要是左括號 ( stack 為空，則取星號 * 來配對抵銷。
5. 遍歷字串結束，我們希望左括號 ( stack 中已經沒有多餘的左括號 (，若還有，我們嘗試使用星號 * 來抵銷。
6. 檢查左括號 ( 和星號 * 的 stack，若左括號 ( 的位置在星號 * 的右邊，則兩者無法配對 => invalid。
7. 否則我們把星號 * 作為右括號 ) 和左括號 ( 配對抵銷，分別從兩個 stack 中取出。
8. 取到其中一個 stack 為空，檢查左括號 ( 的 stack，若不為空，表示還有剩餘無法配對的左括號 ( => invalid。

class Solution {
   public:
    bool checkValidString(string s) {
        stack<int> left, star;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(')
                left.push(i);
            else if (s[i] == '*')
                star.push(i);
            else if (s[i] == ')') {
                if (left.empty() && star.empty())
                    return false;
                else if (!left.empty())
                    left.pop();
                else if (!star.empty())
                    star.pop();
            }
        }

        while (!left.empty() && !star.empty()) {
            if (left.top() > star.top())
                return false;
            else {
                left.pop();
                star.pop();
            }
        }

        return left.empty();
    }
};

Solution 2

• 這個解法滿有趣的，讓我苦惱想了很久，試著解釋看看，哪裡有誤請不吝賜教。

1. 先考慮不含星號 * 的經典題型，我們用一個變數遇到左括號 ( 加 1，右括號 ) 減 1，有兩種 invalid 的情形：
   -- 中間變數一旦為負數，表示左括號 ( 不足夠與右括號 ) 配對抵銷 => invalid。
   -- 若變數最後的值大於 0，表示有多出來的右括號 ) => invalid。
   -- 只有最後變數為 0，才是 valid。
2. 再考慮加入星號 * 的情形，因為星號 * 可以當作左括號 ( 、右括號 ) 或空字串：
   -- 先把星號 * 當作左括號 ( 遍歷一次字串，一樣用一個變數遇到星號 * 或左括號 ( 加 1，右括號 ) 減 1，得到的變數一旦小於 0，則 invalid，這樣我們便可以把左括號 ( 數量不足和右括號 ) 數量過多的狀況過濾掉。
   -- 接著一樣的概念，只是我們反向遍歷，把星號 * 當作右括號 )，用一個變數遇到星號 * 或右括號 ) 加 1，左括號 ( 減 1，得到的變數一旦小於 0，則 invalid，這樣我們便可以把右括號 ) 數量不足和左括號 ( 數量過多的狀況過濾掉。
   -- 兩個變數都沒有出現過小於 0 的情形 => valid。

class Solution {
   public:
    bool checkValidString(string s) {
        int left = 0, right = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(' || s[i] == '*')
                left++;
            else
                left--;

            int j = s.size() - 1 - i;
            if (s[j] == ')' || s[j] == '*')
                right++;
            else
                right--;

            if (left < 0 || right < 0)
                return false;
        }
        return true;
    }
};

</br>

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:
Input:
11110
11010
11000
00000
Output: 1

Example 2:
Input:
11000
11000
00100
00011
Output: 3

Solution 1

• 深度優先搜尋 DFS (Depth-First Search) 的做法：

1. 建一個和 2d grid map 一樣大的 vector 來紀錄每個島嶼是否被訪問過 -> 如果是個島嶼（grid[row][col] == 1）而且沒有被訪問過，將它標記為訪問過，並遞迴去檢查上下左右各個點，注意要排除掉超出邊界的點。
2. 這樣一輪的檢查完會將相連的島嶼標記為訪問過並將島嶼數量增加 1。
3. 繼續尋找下一個還沒訪問過的島嶼，重複這個過程直到遍歷完 2d grid map 中的每個點。

class Solution {
   private:
    int rows;
    int cols;

   public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        rows = grid.size();
        cols = grid[0].size();

        int island = 0;
        vector<vector<bool>> visited(rows, vector<bool>(cols));
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == '1' && !visited[row][col]) {
                    visitIsland(grid, visited, row, col);
                    island++;
                }
            }
        }

        return island;
    }

    void visitIsland(vector<vector<char>>& grid, vector<vector<bool>>& visited, int row, int col) {
        bool withinBound = (row >= 0) && (row < rows) && (col >= 0) && (col < cols);
        if (withinBound)
            if (grid[row][col] == '1' && !visited[row][col]) {
                visited[row][col] = true;
                visitIsland(grid, visited, row - 1, col);
                visitIsland(grid, visited, row + 1, col);
                visitIsland(grid, visited, row, col - 1);
                visitIsland(grid, visited, row, col + 1);
            }
    }
};

Solution 2

• 和 Solution 1 做法相同，但我們不另外建一個和 2d grid map 一樣大的 vector 來紀錄島嶼是否被訪問過，而直接紀錄在原本的 2d grid map -> 將訪問過的島嶼設為 0。

class Solution {
   private:
    int rows;
    int cols;

   public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        rows = grid.size();
        cols = grid[0].size();

        int island = 0;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == '1') {
                    visitIsland(grid, row, col);
                    island++;
                }
            }
        }

        return island;
    }

    void visitIsland(vector<vector<char>>& grid, int row, int col) {
        bool withinBound = (row >= 0) && (row < rows) && (col >= 0) && (col < cols);
        if (withinBound)
            if (grid[row][col] == '1') {
                grid[row][col] = '0';
                visitIsland(grid, row - 1, col);
                visitIsland(grid, row + 1, col);
                visitIsland(grid, row, col - 1);
                visitIsland(grid, row, col + 1);
            }
    }
};

</br>

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Solution 1

• 動態規劃 DP (Dynamic Programming) 的做法：

1. 我們先建一個 m x n 的 grid（ans）來紀錄每個點的 cost (到這個點最小的數字和)。藉由初始化 ans 為原 grid（ans = grid）賦予原點 cost 值（ans[0][0] = grid[0][0]）。
2. 因為只能往右或往下移動，對每個點來說，它的 cost 就是左邊的 cost 或上面的 cost 加上它自己本身的值。我們從兩者中選擇較小的 cost，一路累加從左上 propagate 到右下。
3. 第一行因為只會從左邊過來，所以它的 cost 就是從左往右一路累加；同理第一列就是一路從上到下累加。
4. 處理完邊界的條件後我們從 ans[1][1] 開始遍歷，遍歷結束 ans[rows - 1][cols - 1] 的 cost 就是我們要的答案。

class Solution {
   public:
    int minPathSum(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();

        vector<vector<int>> ans = grid;
        for (int row = 1; row < rows; row++)
            ans[row][0] = ans[row - 1][0] + grid[row][0];
        for (int col = 1; col < cols; col++)
            ans[0][col] = ans[0][col - 1] + grid[0][col];

        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                ans[row][col] = min(ans[row - 1][col], ans[row][col - 1]) + grid[row][col];
            }
        }

        return ans[rows - 1][cols - 1];
    }
};

Solution 2

• Solution 1 另一種寫法，將對第一行和第一列的處理寫入遍歷的迴圈中。
  • 從 ans[0][1] 開始遍歷，不包含 ans[0][0] -> ans[0][0] 還是必須另外賦值。

class Solution {
   public:
    int minPathSum(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();

        vector<vector<int>> ans = grid;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (row > 0 && !col)
                    ans[row][0] = ans[row - 1][0] + grid[row][0];
                else if (col > 0 && !row)
                    ans[0][col] = ans[0][col - 1] + grid[0][col];
                else if (row > 0 && col > 0)
                    ans[row][col] = min(ans[row - 1][col], ans[row][col - 1]) + grid[row][col];
            }
        }

        return ans[rows - 1][cols - 1];
    }
};

Solution 3

• 和前面做法相同，只是不另外建一個 m x n 的 grid（ans）來紀錄每個點的 cost，直接將 cost 更新在原來的 grid 上。

class Solution {
   public:
    int minPathSum(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (row > 0 && !col)
                    grid[row][0] = grid[row - 1][0] + grid[row][0];
                else if (col > 0 && !row)
                    grid[0][col] = grid[0][col - 1] + grid[0][col];
                else if (row > 0 && col > 0)
                    grid[row][col] = min(grid[row - 1][col], grid[row][col - 1]) + grid[row][col];
            }
        }

        return grid[rows - 1][cols - 1];
    }
};

</br>

Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Solution 1 (Time complexity = O(n))

• 這樣竟然也能通過OJ...

class Solution {
   public:
    int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++)
            if (nums[i] == target) return i;

        return -1;
    }
};

Solution 2

• 題目指定 Time complexity = O(log n)，很明顯必須使用二分法：

1. 從數列中間切一刀，如果剛好切中 target，直接回傳中間的位置。
2. 因為數列被旋轉過，我們檢查左右兩邊哪邊仍維持是一個遞增數列，再檢查 target 有沒有在這個遞增數列當中：
   -- 若有，將另外半邊的數列捨去。
   -- 若沒有，將此遞增數列捨去。
3. 若最後只剩兩個數字，會出現 mid 等於 left 的情形，這時如果 nums[mid] 不是 target，target 就只可能在 right，因此我們必須丟掉左邊的數，下一步就是 mid 等於 left 等於 right，去檢查 nums[mid] 是不是 target。這邊左右判斷條件會有點不對稱:
   -- 如果是先看左半邊數列是不是為遞增要多加一個等號 nums[mid] >= nums[left] -> Solution 2。
   -- 如果先檢查右半邊數列則只需要 nums[mid] < nums[right] -> Solution 3。

class Solution {
   public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;

            if (nums[mid] >= nums[left]) {
                if (nums[mid] > target && target >= nums[left])
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return -1;
    }
};

Solution 3

• Solution 2 改為先判斷右半邊數列是不是仍維持為一個遞增數列。

class Solution {
   public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;

            if (nums[mid] < nums[left]) {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            } else {
                if (nums[mid] > target && target >= nums[left])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
        }

        return -1;
    }
};

</br>

Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note:
1 <= preorder.length <= 100
The values of preorder are distinct.

Solution 1

• 利用 BST (Binary Search Tree) 的特性，left.val < root.val < right.val，我們先遍歷數列找到下一個比 root.val 大的節點，即為當前 root 節點的右節點 right。再將左右節點 left 和 right 分別作為 root 節點，遞迴求解：
  • 左節點 left 建構出 root 節點的左子樹，範圍為 [left, right - 1]。
  • 右節點 right 建構出 root 節點的右子樹，範圍為 [right, end]。

class Solution {
   public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        return bstFromPreorder(preorder, 0, preorder.size() - 1);
    }

    TreeNode* bstFromPreorder(vector<int>& preorder, int start, int end) {
        if (start > end) return NULL;

        int left = start + 1, right = start + 1;
        while (right <= end) {
            if (preorder[right] > preorder[start])
                break;
            right++;
        }

        TreeNode* root = new TreeNode(preorder[start]);
        root->left = bstFromPreorder(preorder, left, right - 1);
        root->right = bstFromPreorder(preorder, right, end);

        return root;
    }
};

Solution 2

1. 使用兩個數列 left 和 right 來歸類屬於左子樹還是右子樹。
2. 將原數列的第一個數字作為 root，遍歷數列 -> 比 root 大放進右數列 right，比 root 小放進左數列 left。
3. 兩個子樹再分別建立左右子樹，遞迴求之。

class Solution {
   public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        int n = preorder.size();
        if (!n) return NULL;

        vector<int> left, right;
        TreeNode* root = new TreeNode(preorder[0]);

        for (int i = 1; i < n; i++) {
            if (preorder[i] > root->val)
                right.push_back(preorder[i]);
            else
                left.push_back(preorder[i]);
        }

        root->left = bstFromPreorder(left);
        root->right = bstFromPreorder(right);

        return root;
    }
};

Function to print a tree by level-order traversal

void levelOrderTraversal(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        cout << current->val << " ";

        if (current->left != NULL)
            q.push(current->left);

        if (current->right != NULL)
            q.push(current->right);
    }
}

</br>

Leftmost Column with at Least a One

(This problem is an interactive problem.)

A binary matrix means that all elements are 0 or 1. For each individual row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn't exist, return -1.

You can't access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:

BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed).
BinaryMatrix.dimensions() returns a list of 2 elements [n, m], which means the matrix is n * m.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you're given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:
Input: mat = [[0,0],[1,1]]
Output: 0

Example 2:
Input: mat = [[0,0],[0,1]]
Output: 1

Example 3:
Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:
Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Constraints:
1 <= mat.length, mat[i].length <= 100
mat[i][j] is either 0 or 1.
mat[i] is sorted in a non-decreasing way.

Hint #1
(Binary Search) For each row do a binary search to find the leftmost one on that row and update the answer.

Hint #2
(Optimal Approach) Imagine there is a pointer p(x, y) starting from top right corner. p can only move left or down. If the value at p is 0, move down. If the value at p is 1, move left. Try to figure out the correctness and time complexity of this algorithm.

Solution 1

1. 偷看了 Hint #2，先假設 ans 在最右邊一列（cols - 1），接著逐行遍歷，每行從 ans 開始檢查，如果是 1，就往左走走到不能走為止（左邊的數字等於 0）。也有可能直接就走到底（ans == 0），表示第一列就有 1 了。
2. 如果遍歷到了最後一行而且 ans 還是在最右邊一列（cols - 1），表示在每行的最右邊一直都沒有找到 1，為一個全 0 的矩陣 => 回傳 -1。

class Solution {
   public:
    int leftMostColumnWithOne(BinaryMatrix& binaryMatrix) {
        int rows = binaryMatrix.dimensions()[0];
        int cols = binaryMatrix.dimensions()[1];

        int ans = cols - 1;
        for (int row = 0; row < rows; row++) {
            if (binaryMatrix.get(row, ans)) {
                while (ans > 0) {
                    if (!binaryMatrix.get(row, ans - 1))
                        break;

                    ans--;
                }
            } else if ((row == rows - 1) && (ans == cols - 1))
                return -1;
        }

        return ans;
    }
};

Solution 2

• 改良 Solution 1 中往左走走到不能走為止的判斷方式。
  • Solution 1 是自己等於 1 且左邊的數字等於 0 就跳出迴圈。
  • 這邊改成自己等於 1 且左邊的數字也等於 1 就往下走，遇到 0 或走到第一列自然就跳出迴圈。

class Solution {
   public:
    int leftMostColumnWithOne(BinaryMatrix& binaryMatrix) {
        int rows = binaryMatrix.dimensions()[0];
        int cols = binaryMatrix.dimensions()[1];

        int ans = cols - 1;
        for (int row = 0; row < rows; row++) {
            if (binaryMatrix.get(row, ans))
                while (ans > 0 && binaryMatrix.get(row, ans - 1))
                    ans--;
            else if ((row == rows - 1) && (ans == cols - 1))
                return -1;
        }

        return ans;
    }
};

Solution 3

• 和 Solution 1 想法差不多，但減少一些判斷：
  • 我們在逐行遍歷的時候，每行從 ans 開始檢查，如果是 1，就往左走走到是 0 的位置，所以最後回傳的時候要再加 1 回來。
  • 如果最後 ans 還停在最右邊，表示都沒有找到 1，為一個全 0 的矩陣 => 回傳 -1。

class Solution {
   public:
    int leftMostColumnWithOne(BinaryMatrix& binaryMatrix) {
        int rows = binaryMatrix.dimensions()[0];
        int cols = binaryMatrix.dimensions()[1];

        int ans = cols - 1;
        for (int row = 0; row < rows; row++) {
            while (ans >= 0 && binaryMatrix.get(row, ans))
                ans--;
        }

        if (ans == cols - 1)
            return -1;

        return ans + 1;
    }
};

BinaryMatrix's API interface

class BinaryMatrix {
   private:
    vector<vector<int>> mat;

   public:
    BinaryMatrix(vector<vector<int>> in) {
        mat = in;
        for (auto row : mat) {
            cout << "  [ ";
            for (auto i : row)
                cout << i << " ";
            cout << "]" << endl;
        }
    };

    int get(int x, int y) {
        return mat[x][y];
    };

    vector<int> dimensions() {
        int rows = mat.size();
        int cols = mat[0].size();
        return {rows, cols};
    };
};

</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