?
?
lc73矩陣置零
queue隊列標記
? // 整行置零
?for(int y=0; y<n; y++)?
? ? ? ? ? ? ? ? matrix[i][y] = 0;?
?// 整列置零
? ? ? ? ? ? for(int x=0; x<m; x++)?
? ? ? ? ? ? ? ? matrix[x][j] = 0;?
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix)?
{
int m = matrix.size(), n = matrix[0].size();
// 新增標記隊列
queue<pair<int, int>> q;?
? ? ? ? // 第一次遍歷：記錄原始0的位置
for(int i=0; i<m; i++)?
{
for(int j=0; j<n; j++)?
{
if(matrix[i][j] == 0)?
{
q.push({i, j});?
// 僅記錄原始0坐標
}
}
}
? ? ? ? // 處理所有標記點
while(!q.empty())?
{
auto [i,j] = q.front();
q.pop();
// 整行置零
for(int y=0; y<n; y++)?
matrix[i][y] = 0;?
// 整列置零
for(int x=0; x<m; x++)?
matrix[x][j] = 0;?
}
}
};
?
lc48 從外到內，旋轉矩陣
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
int l = 0, r = n - 1;
int t = 0, b = n - 1;
//從外到內，處理每圈
while (l <= r && t <= b)?
{
// 上層轉到右層
for (int i = l; i < r; i++) swap(matrix[t][i],matrix[i][r]);
// 下層轉到左層
for (int i = r; i > l; i--) swap(matrix[b][i],matrix[i][l]);
// 上下層交換
for (int i = l; i < r; i++) swap(matrix[t][i],matrix[b][n - 1 - i]);
l++;r--;t++;b--;
}
}
};
?
?
概率dp 矩陣dp 的思想
逆想記憶化搜索，從下往上推
lc1277.全一正方形個數
dp[I][j]: 枚舉右下角,min(三方位）+1
eg. ?
dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
?class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int total = 0;
// 初始化第一行和第一列
for (int i = 0; i < m; ++i) {
dp[i][0] = matrix[i][0];
total += dp[i][0];
}
for (int j = 1; j < n; ++j) {
dp[0][j] = matrix[0][j];
total += dp[0][j];
}
// 填充dp數組
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][j] == 1) {
dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
total += dp[i][j];
}
}
}
return total;
}
};
?
lc961.?在長度 2N 的數組中找出重復 N 次的元素
間隔最小為2
?class Solution {
public:
int repeatedNTimes(vector<int>& nums)?
{
int n = nums.size();
for(int i = 0; i < n - 2; i++)?
{
if(nums[i] == nums[i + 1] || nums[i] == nums[i + 2])?
return nums[i];
}
return nums[n - 1]; // 避免長度為4, 間隔為2的情況
}
};
?
