Hero Image
Leetcode 隨筆 - 152. Maximum Product Subarray

題目難度:Medium

題目連結: Maximum Product Subarray

題目大綱

給你一個整數陣列, 找出擁有最大乘積的子陣列 (contiguous non-empty subarray)

程式碼

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans = nums[0];
        int max_product = 1;
        int min_product = 1;
        int t1, t2;

        for (int i = 0; i < nums.size(); i++)
        {
            t1 = max_product * nums[i];
            t2 = min_product * nums[i];
            max_product = max(t1, max(t2, nums[i]));
            min_product = min(t1, min(t2, nums[i]));
            ans = max(max_product, ans);
        }
        return ans;
    }
};

Hero Image
Leetcode 隨筆 - 199. Binary Tree Right Side View

題目難度:Medium

題目連結: Binary Tree Right Side View

題目大綱

給你一個 binary tree, 請你找出:從右邊看這棵樹,能看到的 node 有哪些。

解題思路

這題翻譯過後就是,請你找出此 binary tree 的每一層的最右邊的 node,所以我們只需要使用 level order traverse 的方式把 tree 掃過一遍抓出每層最右邊的 node 就行了!

程式碼

實作採用 C++ STL 的 queue, 遍歷時加上每個 node 的 level 資訊,當每掃到新的 level 時就會把該 node 加進 ans 裡面並更新 level 資訊;再來因為我們需要最右邊的 node, 所以 traverse 順序改成先掃右邊的 subtree 再掃左邊 subtree 的方式比較方便實作。

/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        queue<pair<TreeNode*, int>> q;
        pair<TreeNode*, int> node;
        vector<int> ans;
        int cur_level = -1;

        if (root == NULL)
            return vector<int>();

        q.push(pair<TreeNode*, int>(root, 0));

        while (!q.empty()) {
            node = q.front();
            q.pop();

            if (node.second != cur_level) {
                ans.push_back(node.first->val);
                cur_level = node.second;
            }

            if (node.first->right != NULL) {
                q.push(pair<TreeNode*, int>(node.first->right, node.second + 1));
            }
            if (node.first->left != NULL) {
                q.push(pair<TreeNode*, int>(node.first->left, node.second + 1));
            }
        }

        return ans;
    }
};

Hero Image
Leetcode 隨筆 - 665. Non-decreasing Array

題目難度:Medium

題目連結: Non-decreasing Array

題目大綱

給你一個陣列 nums,請你檢查是否可以在 “最多修改一個元素的值” 的限制下,把這個陣列變成一個非遞減陣列 (原來就已經是非遞減陣列也可以算通過檢查)

非遞減定義: nums[i] <= nums[i+1], where 0 <= i <= nums.size()-2

解題思路

首先需要把陣列從頭開始掃描一遍,遇到 nums[i+1] < nums[i] 時停下來檢查是否可以修改元素值來完成題目要求,如果可以改,那就紀錄本次修改。所以我們可以用一個 counter 來記錄修改次數,而若修改次數大於 1 次就可以提前結束不用再往後檢查了。

接下來重點就是:要怎麼確認可以修改(改成非遞減)? 這裡可以分成幾個 case 來討論:

Case 1. 陣列的開頭 or 結尾發生遞減情況

也就是 nums[0] > nums[1] or nums[nums.size()-1] > nums[nums.size()-2],這時候一定可以修改,因為只要把陣列頭的值往下修或把陣列尾的值往上調就可以了,所以直接更新 counter (counter++) 即可。

Case 2. 陣列中間發生遞減情況

這時候發生了 nums[i+1] < nums[i],為了判斷是否能夠只改一個值就能改成非遞減陣列,我們必須額外再抓出 nums[i-1] & nums[i+2] 這兩個元素來幫助我們判斷。

首先第一項檢查

nums[i+2] 是否大於等於 nums[i-1] ?

因為若這個條件不符合,代表除了 nums[i]nums[i+1] 之外,在 nums[i+2] 這個位置又讓陣列發生了遞減情況,所以至少要改兩個地方,這樣絕對達不到題目要求,因此我們可以提早結束判斷、回傳失敗結果。

Hero Image
LeetCode 隨筆 - 74. Search a 2D Matrix

題目難度:Medium

題目連結: Search a 2D Matrix

題目大綱

給你一個 m x n 的整數二維陣列和一個 value target,要你判斷 target 是否在這個陣列中。 題目保證這個二維陣列:

  1. 每個 row 的數字的順序已經由小到大排序過了
  2. 每個 row 的第一個數字一定比上一個 row 的最後一個數字還要大

解題思路

由題目可知,將這個二維陣列按照 row 展開成一維陣列後就是一個排序過的 array,所以我們就可以直接用 二分搜 (Binary Search) 來找 target。 需要注意的是傳入的是二維陣列,所以在寫 binary search 的時候需要轉換一維 & 二維之間的坐標系

一維 & 二維坐標系轉換範例: 假設我們要轉換一維陣列的 index i 到一個 m x n (m rows * n columns) 的二維陣列的 index (row, col)

row = i / n;
col = i % n;

程式碼

binary search 可以使用迴圈或遞迴的方式來實作,以下提供兩種版本供讀者參考

迴圈版

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        int left = 0, right = m*n - 1;
        int i, j, mid;

        while (left <= right) {
            mid = (left + right) / 2;
            i = mid / n;
            j = mid % n;
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
};

遞迴版

class Solution {
public:
    int m, n;
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        m = matrix.size();
        n = matrix[0].size();
        return binarySearch(matrix, target, 0, m*n - 1);
    }

    bool binarySearch(vector<vector<int>>& matrix, int target, int begin, int end) {
        int mid;
        int i, j;

        if (begin > end)
            return false;

        mid = (begin + end) / 2;
        i = mid / n;
        j = mid % n;

        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] > target) {
            return binarySearch(matrix, target, begin, mid-1);
        } else {
            return binarySearch(matrix, target, mid+1, end);
        }
    }
};