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;
}
};
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] 這個位置又讓陣列發生了遞減情況，所以至少要改兩個地方，這樣絕對達不到題目要求，因此我們可以提早結束判斷、回傳失敗結果。
LeetCode 隨筆 - 74. Search a 2D Matrix
題目難度：Medium
題目連結: Search a 2D Matrix
題目大綱
給你一個 m x n 的整數二維陣列和一個 value target，要你判斷 target 是否在這個陣列中。
題目保證這個二維陣列：
- 每個 row 的數字的順序已經由小到大排序過了
- 每個 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);
}
}
};