今日学习记录
1.统计全 1 子矩形leetcode.1504
关键词：动态规划 矩阵 数组
问题分析：
- 给你一个
m x n的二进制矩阵mat，请你返回有多少个 子矩形 的元素全部都是 1 . - 没啥好分析,就是字面意思,难在任意矩形
核心思路
- 首先先看懂 2025-08-20 的第一题,然后我就思考了一下,发现不能用动态规划,但是为什么呢,问题出现在哪里,可以先区分一下正方形与矩形,正方形固定边,长等于高,确定长就可以确定高,但是矩形不行,从动态规划的变化过程中思考,我们无法再只讨论边,要讨论长和宽,但是无法从两个过程变量中等到答案,且长和宽没有关系,那么我可以先限定长或者宽,让过程变量单一,简单来说就是枚举不同高 h 的矩形,看数组中符合 h 的子矩形有多少个,先看第一列得到一个一维数组 arr{0,1,1,0},再枚举到第二层 h=2,直接把下一层的数据加到上一层变成 arr{0,2,2,1},于是要得到的子矩型就是 arr 的等于 h 的子数组,那么问题变成
- 统计 a 的全 h 子数组的数目 2025-08-19 的第一题。
int numSubmat(vector<vector<int>>& mat) {
int r = mat.size(),c = mat[0].size();
int ans = 0;
for(int top = 0;top<r;top++){
vector<int> arr(c);
for(int bm = top;bm<r;bm++){
int h = bm - top + 1;
int n = 0;
for(int i = 0;i<c;i++){
arr[i] += mat[bm][i];
if(arr[i]!=h) n = 0;
else{
n++;
ans += n;
}
}
}
}
return ans;
}- 还有个单调栈的做法,我还不会…
**最终代码：
学到的点：
- 新技巧
2. 通过质数传送到达终点的最少跳跃次数leetcode.3629
关键词：队列 bfs 哈希表 数论
问题分析：
- 就是跳格子,如果当前是质数,就可以跳到数组中存在的该质数的倍数的位子,然后看最少要几步走完到 n-1 的地方
核心思路
- 要跳质数的倍数嘛,那就要先弄清楚数组中的质数都能跳到哪个位子,既然是质数的倍数,有很多,所以要预处理,说到处理质数和质数的倍数,就想到了埃式筛,筛完后,创建哈希表,记录数组中每个质数能移动到哪个下标
- 这种一般就是 bfs 的问题,找到最短路径嘛,先从 0 开始,找 i+1,i-1,加一个 i>0 的判断就行,先把 0 入队,找到 0 能移动到的地方,再把这些地方放入队列中,还要进行标记,避免重复操作,再继续增加操作此次数,直到有下标到达 n-1 就返回答案
- bfs 的时候一定要注意队列的长度,会随着加入的数据变大,遍历队列开始的时候固定队列长度,我因为这个搞了一个多小时,逆天啊
最终代码：
const int N = 1000001;
vector<int> arr[N];
int init = []{
for(int i = 2;i<N;i++){
if(arr[i].empty()){
for(int j = i;j<N;j+=i){
arr[j].push_back(i);
}
}
}
return 0;
}();
class Solution {
public:
int minJumps(vector<int>& nums) {
int n = nums.size();
unordered_map<int,vector<int>> mp;
for(int i = 0;i<n;i++){
for(int p:arr[nums[i]]){
mp[p].push_back(i);
}
}
queue<int> q;
q.push(0);
vector<bool> visted(n,false);
visted[0] = true;
int ans = 0;
while(true){
int len = q.size();
for(int i = 0;i<len;i++){
int m = q.front();
if(m==n-1) return ans;
q.pop();
auto &t = mp[nums[m]];//取地址,方便后续清楚避免重复计算
t.push_back(m+1);
if(m>0) t.push_back(m-1);
for(int b:t){
if(!visted[b]){
visted[b] = true;
q.push(b);
}
}
t.clear();
}
ans++;
}
}
};学到的点： 1.