Leetcode 隨筆 - 62. Unique Paths
題目難度：Medium
題目連結: Unique Paths
題目大綱
給你一個 m x n 的矩陣地圖, 請你找出從座標 (0, 0) 走到 (m-1, n-1) 一共有多少種走法。題目有限制每一次只能往下或往右走一步。
解題思路
解法一 - DP
設計一個 2 維陣列 dp[m][n], 其中 dp[i][j] 對應到座標 (i, j)，代表了從 (0, 0) 走到 (i, j) 一共有多少種走法。
接著從題目的限制我們可以知道，要走到 (i, j) 的話一定要先走到 (i-1, j) 或是 (i, j-1)，然後再往下或往右走一步來到達 (i, j)。
也就是說，走到 (i, j) 的走法數，會等於走到 (i-1, j) 的走法數加上走到 (i, j-1) 的走法數
有了這層關係，我們就可以得出 dp 的公式如下：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
而一開始要初始化 dp[i][0] = 1 (0 <= i <= m) 以及 dp[0][j] = 1 (0 <= j <= n)，代表從起點開始，一路往右或往下都只有一種走法
Leetcode 隨筆 - 139. Word Break
題目難度：Medium
題目連結: Word Break
題目大綱
給定一個字串 s 和一個字串陣列 wordDict, 請你判斷是否有辦法
程式碼
解法一
這是我看完 NeetCode 影片的前半段的解題思路後想出來的解法
class Solution {
private:
vector<int> word_len;
int s_len;
vector<int> dp;
public:
void solve(string& s, int idx, vector<string>& wordDict)
{
if (idx >= s_len)
{
dp[s_len] = 1;
return;
}
if (dp[idx] != -1)
return;
for (int i = 0; i < wordDict.size(); i++)
{
if (s.compare(idx, word_len[i], wordDict[i]) == 0)
{
solve(s, idx + word_len[i], wordDict);
if (dp[s_len] == 1)
return;
}
}
dp[idx] = 0;
}
bool wordBreak(string s, vector<string>& wordDict) {
word_len.resize(wordDict.size(), 0);
s_len = s.length();
dp.resize(s_len + 1, -1);
dp[s_len] = 0;
for (int i = 0; i < wordDict.size(); i++)
{
word_len[i] = wordDict[i].length();
}
solve(s, 0, wordDict);
return dp[s_len];
}
};
解法二
NeetCode 提出的最佳解
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);
}
}
};