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的情况
}
};