今日學(xué)習(xí)的視頻和文章
- 代碼隨想錄 有序數(shù)組的平方
- 代碼隨想錄 長(zhǎng)度最小的子數(shù)組
- 代碼隨想錄 螺旋矩陣
- @YouLookDeliciousC 的題解：54. 螺旋矩陣 - 力扣（Leetcode）
LeetCode977 有序數(shù)組的平方
-
初見題目的想法
一開始我想的是設(shè)置一個(gè)
left指針和一個(gè)right指針脊串，從數(shù)組“中間”開始向兩邊比較辫呻。這個(gè)邏輯是錯(cuò)誤的，應(yīng)該是找到平方值最小的那個(gè)元素的位置作為雙指針的起始位置琼锋，而不是取數(shù)組的“中間”印屁。那么，應(yīng)該遍歷一遍數(shù)組斩例，找到合適的起始位置雄人。變量尋找合適的起始位置的代碼如下
int n = nums.size(); vector<int> res; int start = 0; int curPowMin = pow(nums[start], 2); for (int i = 1; i < n; i++) { if (pow(nums[i], 2) < curPowMin) { curPowMin = pow(nums[i], 2); start = i; } } int left = start; int right = start + 1;找到合適的起始位置后，用
left和right分別向左和向右取數(shù)組元素念赶，比較平方值础钠，將平方值較小的元素放入答案數(shù)組中。while (0 <= left || right < n) { int powLeft = 0 <= left ? pow(nums[left], 2) : INT_MAX; int powRight = right < n ? pow(nums[right], 2) : INT_MAX; if (powLeft < powRight) { res.push_back(powLeft); left--; } else { res.push_back(powRight); right++; } }
完整題解代碼如下：
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> res;
int start = 0;
int curPowMin = pow(nums[start], 2);
for (int i = 1; i < n; i++) {
if (pow(nums[i], 2) < curPowMin) {
curPowMin = pow(nums[i], 2);
start = i;
}
}
int left = start;
int right = start + 1;
while (0 <= left || right < n) {
int powLeft = 0 <= left ? pow(nums[left], 2) : INT_MAX;//三目表達(dá)式防止下標(biāo)越界
int powRight = right < n ? pow(nums[right], 2) : INT_MAX;
if (powLeft < powRight) {
res.push_back(powLeft);
left--;
}
else {
res.push_back(powRight);
right++;
}
}
return res;
}
分別遍歷了兩次數(shù)組叉谜，時(shí)間復(fù)雜度應(yīng)為O(n)旗吁。
- 看了代碼隨想錄講解后自己的一些體會(huì)
以前寫題的時(shí)候也看過代碼隨想錄的講解，感覺比大學(xué)課堂里的講解清楚很多停局。最近考研復(fù)習(xí)也在復(fù)習(xí)高數(shù)很钓，所以聯(lián)想到了二次函數(shù)的圖像，最小的平方值相對(duì)來說在數(shù)組的“中間”董栽，最大的平方值相對(duì)來說在數(shù)組的“兩邊”码倦。既然要比較“兩邊”誰大誰小，自然就想到了雙指針來向兩邊取元素锭碳。
不過我自己寫的方法和代碼隨想錄里的比起來還是不夠簡(jiǎn)潔袁稽，我的方法里“找起始位置“這一步，其實(shí)是沒有必要的擒抛。只需要讓left從最左邊開始推汽，right從最右邊開始，將平方值較大的數(shù)歧沪，從答案數(shù)組的最大下標(biāo)向最小下標(biāo)開始填充就可以了歹撒。
改良后的題解代碼如下，甚至可以用三目表達(dá)式一條語句搞定诊胞。
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
for (int l = 0, r = n - 1, k = r; l <= r; ) {
res[k--] = pow(nums[l], 2) > pow(nums[r], 2) ?
pow(nums[l++], 2) : pow(nums[r--], 2);
}
return res;
}
LeetCode209 長(zhǎng)度最小的子數(shù)組
- 初見題目時(shí)的想法
- 用
left保存子數(shù)組在原數(shù)組中的起始下標(biāo)暖夭，用right保存子數(shù)組在原數(shù)組中的結(jié)束下標(biāo)。 - 讓
right先向右移動(dòng)厢钧，如果出現(xiàn)了[left, right]的子數(shù)組的元素之和大于等于target鳞尔，就讓left向右移動(dòng)，然后讓right繼續(xù)向右移動(dòng)早直，繼續(xù)尋找元素之和大于等于target的連續(xù)子數(shù)組寥假。 - 然后我就在邊界條件的調(diào)試上卡了很久，最后還是直接看講解了霞扬。
- 用
- 看了講解之后的體會(huì)：
- 外層循環(huán)的邊界條件一定是
right移動(dòng)到右邊界糕韧，如果是left移動(dòng)到右邊界的話就和暴力解法沒有區(qū)別了枫振。我自己做題的時(shí)候一直沒有明確這一點(diǎn)，還在考慮left == right且right移動(dòng)到右邊界的情況萤彩，實(shí)際上這和滑動(dòng)窗口的思想就矛盾了粪滤。
- 外層循環(huán)的邊界條件一定是
完整題解代碼如下
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int res = INT_MAX;
int l = 0;
int r = 0;
int sum = 0;
while (r < n) {
sum += nums[r];
while (sum >= target) {
res = min(res, r - l + 1);
sum -= nums[l++];
}
r++;
}
return res == INT_MAX ? 0 : res;
}
- 這題卡了比較久，還是要橙阜觯回頭看杖小，并且多練類似思想的題目。
- 另外還鬧了個(gè)烏龍愚墓，這題是在外面聽講座的時(shí)候做的予权，讀題目時(shí)，電腦開了節(jié)電模式浪册，沒看清要求是”大于等于 target“而不是”等于 target“扫腺。這種細(xì)節(jié)問題也是要注意的，如果代碼邏輯對(duì)了村象，但是還是不能AC笆环，那可能就要看看自己是不是看錯(cuò)題目了……
LeetCode59 螺旋矩陣II
-
初見題目時(shí)的想法
- 這道題目以前寫過類似的，而且看到了一個(gè)思路非常簡(jiǎn)潔清晰的題解厚者，其中“移動(dòng)邊界”來操作螺旋的思想令我印象深刻躁劣。
- 54. 螺旋矩陣 - 力扣（Leetcode）
- @YouLookDeliciousC 的題解：54. 螺旋矩陣 - 力扣（Leetcode）
-
按照循環(huán)不變量原則，我在這里記錄一下自己的體會(huì)：
-
首先是如何定義螺旋籍救，代碼隨想錄里是這樣定義的（如圖）：
- image.png
每條邊都是一個(gè)左閉右開區(qū)間习绢，對(duì)于方陣而言，這是非常清晰蝙昙、明確的“螺旋”的定義。但是我在寫 LeetCode54 題時(shí)梧却，繼續(xù)按照這個(gè)定義去處理“螺旋”奇颠，就碰到了很多邊界條件的問題。
因?yàn)?LeetCode54 并沒有限制矩陣是方陣放航，按照左閉右開區(qū)間的定義烈拒，在處理只有一行或者一列的矩陣的時(shí)候，就會(huì)出現(xiàn)一些奇怪的情況广鳍，因?yàn)樽箝]右開區(qū)間荆几，在矩陣只剩一行或一列的還沒被訪問的時(shí)候，就有可能出現(xiàn)因?yàn)閰^(qū)間右邊不能取等號(hào)而遺漏元素的情況赊时。
以下是我磕磕絆絆修修補(bǔ)補(bǔ)才通過的 LeetCode54 的代碼
class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> result; int rowNum = matrix.size(); int colNum = matrix[0].size(); int sumNum = rowNum * colNum; int x = 0; int y = 0; int loop = rowNum / 2; int count = 1; while(count <= loop) { for (; x < colNum - count; x++) { result.push_back(matrix[y][x]); if(result.size() == sumNum) return result; } for (; y < rowNum - count; y++) { result.push_back(matrix[y][x]); if(result.size() == sumNum) return result; } if(result.size() == sumNum) return result; for (; x >= count; x--) { result.push_back(matrix[y][x]); if(result.size() == sumNum) return result; } for (; y >= count; y--) { result.push_back(matrix[y][x]); if(result.size() == sumNum) return result; } if(result.size() == sumNum) return result; count++; x++; y++; } if (rowNum <= colNum) { for (; x <= colNum - count; x++) { result.push_back(matrix[y][x]); if(result.size() == sumNum) return result; } } if (rowNum > colNum) { for (; y <= rowNum - count; y++) { result.push_back(matrix[y][x]); if(result.size() == sumNum) return result; } } return result; } };
-
-
所以吨铸，在堅(jiān)持循環(huán)不變量原則的同時(shí)，如何找或者說如何去定義循環(huán)不變量也影響我們?nèi)绾稳懘a祖秒。如果我們這樣去定義“螺旋”诞吱，所有區(qū)間都取閉區(qū)間舟奠，就可以避免一些由于開區(qū)間而導(dǎo)致的邊界條件判斷。
- 從左到右訪問完矩陣的第一行房维，然后重新定義上邊界沼瘫，體現(xiàn)在代碼上就是矩陣的“上邊界”+1。
- 判斷上下邊界是否交錯(cuò)即（上邊界 > 下邊界）咙俩。
- 從上到下訪問完矩陣的最后一列耿戚，然后重新定義右邊界，體現(xiàn)在代碼上就是矩陣的“右邊界”-1阿趁。
- 判斷左右邊界是否交錯(cuò)即（左邊界 > 右邊界）溅话。
- 從右到左訪問完矩陣的最后一行，然后重新定義下邊界歌焦，體現(xiàn)在代碼上就是矩陣的“下邊界”-1飞几。
- 判斷左右邊界是否交錯(cuò)即（左邊界 > 右邊界）。
- 從下到上訪問完矩陣的第一列独撇，然后重新定義左邊界屑墨，體現(xiàn)在代碼上就是矩陣的“左邊界”+1。
- 判斷上下邊界是否交錯(cuò)即（上邊界 > 下邊界）纷铣。
- 不斷重復(fù)以上步驟卵史，直到左右邊界交錯(cuò)或者上下邊界交錯(cuò)。
為什么這樣做可以所有的區(qū)間都只用閉區(qū)間來定義“螺旋”呢搜立？按照之前提到左閉右開的定義以躯，我們對(duì)于“螺旋”的定義是靜態(tài)的，沒有考慮每訪問一條邊之后矩陣的變化啄踊。而按照 @YouLookDeliciousC 的方法忧设，對(duì)于“螺旋”的定義是動(dòng)態(tài)的，考慮了每訪問一條邊之后矩陣的變化颠通，從而能只用閉區(qū)間來定義“螺旋”址晕。
LeetCode59 完整的題解代碼如下：
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n));
int top = 0;
int bottom = n - 1;
int left = 0;
int right = n - 1;
int count = 1;
while (count <= n * n) {
for (int x = left, y = top; x <= right; x++) {
res[y][x] = count++;
}
if (++top > bottom) break;
for (int x = right, y = top; y <= bottom; y++) {
res[y][x] = count++;
}
if (--right < left) break;
for (int x = right, y = bottom; x >= left; x--) {
res[y][x] = count++;
}
if (--bottom < top) break;
for (int x = left, y = bottom; y >= top; y--) {
res[y][x] = count++;
}
if (++left > right) break;
}
return res;
}
