第一题 P3353 在你窗外闪耀的星星
题目描述
解题报告
看到求区间和，我就想拿出我熟悉的前缀和了。看到有佬佬们用线段树，但是暂时不退，RBQ 。
前缀和的使用主要是
① 前缀和数组sum的预处理
② sum[区间右端点] - sum[区间左端点 - 1]来实现O(1)的区间和查询。
这个题了，因为题目说的是每颗星星都有自己的位置，并没有说每个位置只能有一颗星星，一个位置是可以允许有多枚星星的，倘若是按照每个位置只有一颗星星的想法处理了，只有10分~
统计窗口能够看到的最亮的星星的亮度了，小类似滑动窗口。窗口的长度是w。为了把窗口滑动的过程+前缀和区间求和的公式结合在一起，枚举的时候，可以将窗口长度作为初始值，这种既可以统计窗口长度内的区间和，也不会出现数组角标越界。
参考代码(C++版本)
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100000+10; int sum[N],cnt[N]; int main() { //前缀和 //输入星星的数量和窗户的宽度 int n , w,pos = 0; cin >> n >>w; for(int i = 1; i <= n;i++) { int a,b; //输入坐标和亮度 cin >> a >> b; cnt[a] += b;//可能说，同一个坐标，是有多个不同亮度的星星，因此比平常的前缀和多一步预处理 //统计星星的坐标，找到最远的坐标 pos = max(pos,a); } //预处理前缀和 for(int i = 1; i <= pos;i++) sum[i] = sum[i-1] + cnt[i]; int ans = -1; //按照窗户宽度扫一遍，找最大值 for(int i = w; i <= pos;i++) ans = max(sum[i]-sum[i-w],ans); cout << ans; return 0; }
搜索的知识铺垫
搜索的原理
深度优先搜索
常规玩法：
① 递归统计结果，比如求阶乘
② 递归求指数型枚举，比如求斐波那契数列的第n项
③ 递归求排列型枚举，比如求n个数字的全排列
进阶应用领域： 枚举、容斥原理、基于状态压缩的动态规划、记忆化搜索、有向图强连通分量、无向图割边割点和双连通分量、LCA最近公共祖先、博弈、二分图、欧拉回路、K短路、线段树、最大团、最大流、树形DP。
上面的内容有个印象就好，具体想掌握，还得落实到题目上，感觉英雄哥写的记忆化搜和剪枝的内容让我受益匪浅，着重记录一下。以及捋清楚了回溯是怎么回溯的，浅偷下一了
基于DFS的记忆化搜索
基于DFS的剪枝
广度优先搜索
第二题 565. 数组嵌套
模拟+扫描
题目描述
解题报告
其实是求当前给的数组中，最多能组成多少个题目给出的嵌套模式。
那么就可以直接扫描每个数能够形成的最长的序列长度是多少，最后返回最长的就好了。
参考代码(C++版本)
class Solution { public: int arrayNesting(vector<int>& nums) { int n = nums.size(); //开个记录每个点状态的数组，默认都是没有用过吧 int st[n]; memset(st,0,sizeof(st)); int ans = -1; //从索引为0的位置开始扫描吧 for(int i = 0; i < n;i++) { int cnt = 0;//统计当前这种扫描模式能够嵌套的数量 while(!st[i])//倘若当前这个点没有用过，进去搜索 { //标记用过了 st[i] = 1; cnt ++; //按照题目背景更新索引 i = nums[i]; } //统计每个点扫描处理的结果，要找到最大值 ans = max(ans,cnt); } return ans; } };
第三题 401. 二进制手表
记录sprintf + 字符数组通过强制转换转成字符串 + 使用标记区分不同的搜索状态
题目描述
解题报告
这个图也太草率了吧~
我自己不太这道题目的搜索+回溯的玩法，参考了大佬的题解:
位运算暴力？回溯？我全都要！就不信还讲不明白了！😤。需要的小伙伴自行阅读嗷~
假如使用递归去搜索了，要拿捏核心的两个点：
基线条件：递归什么时候结束，并统计当前搜索出来的时间
递归条件：递归函数需要计算什么，需要实现什么，递归进入下一层的逻辑是什么呢
基线条件
题目给我们的是LED的数量，LED灯只有亮和不亮两种状态，那么，倘若我们把所有亮着的LED灯都处理完了，也就到达了递归的边界了。
到达递归的边界之后，通过我们设定的flag标记来分别处理分钟和时钟。
倘若是分钟，就加入到统计分钟的数组，等最后统计结果的时候取出来用。
倘若是时钟，就可以着手记录当前搜索的结果。
递归条件
常规的将二进制转换为对应的十进制的逻辑，已经递归进入下一层dfs(step + 1)
参考代码(C++版本)
class Solution { private: vector<string> ans; vector<int> mins; void dfs(int pos, int sum, int cnt, bool flag) { //设置递归结束条件，也就是所有亮的灯都处理完了 if(cnt == 0) { //根据当前的标记flag,来判断是处理分钟还是时钟 //如果是分钟，将当前的分钟数放到用于统计分钟的集合中 if(flag) mins.push_back(sum); //否则当前是处理时钟，那么就需要将存储的分钟拿出来，结合时钟表示当前搜索的结果了 else { if(!mins.empty()) { for(auto it : mins) { char tmp[10]; //将小时和分钟转换成字符串数组 sprintf(tmp,"%d:%02d",sum,it); //将字符串数组转换为字符串 string str_ans = (string)tmp; //将结果统计起来 ans.push_back(str_ans); } } } return ; } //根据flag的标签，决定怎么再进一步搜索 for(int i = pos; i < (flag?6:4);i++) { //当前亮的点表示二进制，根据权值转换为十进制 int ten_n = pow(2,i); //判断算出来的结果，是否符合表盘要求: // 小时（0-11）， 分钟（0-59） if(flag && sum + ten_n >= 60 || !flag && sum + ten_n >= 12) break; //这儿只能写i + 1 和 cnt -1 else dfs(i+1,sum + ten_n,cnt-1,flag); //递归进入下一层 } } public: vector<string> readBinaryWatch(int turnedOn) { //设「亮灯数」为 turnedOn ，枚举分钟，分钟的显示使用了 i 个灯，可得时钟显示剩余的可用灯数为 turnedOn - i for(int i = 0; i < 6 && turnedOn >= i ;i++) { //搜分钟和搜时钟的逻辑差不多，为了实现区分，使用标记来区分 //分别代表当前枚举的LED的位置，现在算出来的二进制总和，当前亮的LED灯，标记 dfs(0,0,i,true); dfs(0,0,turnedOn - i,false); mins.clear(); } return ans; } };
枚举 + lowbit。这里将前导0的判断可以积累一下。感觉深搜真的是增加了题目难度了
class Solution { public: vector<string> readBinaryWatch(int turnedOn) { vector<string> res; //直接从 0:00 枚举到 11:59 每个时间有多少1 for (int i = 0; i < 12; i++) { for (int j = 0; j < 60; j++) //找到满足要求的了 if (lowbit(i) + lowbit(j) == turnedOn) res.push_back(to_string(i)+":"+ (j < 10 ? "0"+to_string(j) : to_string(j))); } return res; } //计算二进制中1的个数 int lowbit(int n) { int res = 0; while (n) { n -= (n & -n); //或者写成也可以 n = n & (n - 1); res++; } return res; } };
第四题 1079. 活字印刷
题目描述
解题报告
原本以为是一个简答的递归实现指数型枚举，但是认真看了样例之后，发现已经出现过的字符，是不能再出现相同的了，那么回溯+剪枝就成为了这个题的重点。
关于去重，可以使用STL中的set容器来实现去重，也可以使用哈希表，也可以自行编写去重条件。
倘若想要自行编写去重的条件：
① 判断当前这个点是否已经探索/使用过了，倘若是，就跳过。
② 判断当前探索的点i是否和其前一个字符相等tiles[i] == tiles[i-1]，倘若是相等，就是重复的字母，我们只取第一个未访问的，即，当i-1个点也是是未被访问过的，visited[i-1]==false
至于这个visited数组是一个用于记录当前的位置是否被探索过了。
可以使用vector库函数来开一个bool数组，使用visited.assign(n,false);来初始化。
也可以就使用熟悉的普通数组，开int类型或者bool类型都可以，使用memset(visited,0,sizeof(visited));来初始化。
参考代码(C++版本)
class Solution { public: int vis[10]; int ans = 0; int numTilePossibilities(string tiles) { //因为连续的相同字符只能使用第一个，这个题就是回溯的基础上加剪枝 int n = tiles.size(); memset(vis,0,n); //排序是为了找到联系重复的字符 sort(tiles.begin(),tiles.end()); dfs(tiles,0); return ans; } void dfs(const string &tiles,int step) { //设置递归的基线条件 if(step == tiles.size()) return; //递归实际的探索逻辑 for(int i = 0;i < tiles.size();i++) { //剪枝——这里是跳过这种使用过的，或者是重复的方案 if(vis[i] || i > 0 && tiles[i] == tiles[i-1] && vis[i-1] == 0) continue; //标记当前的方案可行，能够探索一个点 vis[i] = 1; ans ++; dfs(tiles,step + 1);//递归进入下一层 //回溯——还原现场 vis[i] = 0; } } };
这个题也可以使用哈希表来实现，可以使用STL中的map或者哈希表的思想都行。注意使用迭代器的时候。
下面涉及一些引用传参的知识点，详情参考这篇文章
C++ 值传递、指针传递、引用传递详解
C++中const关键字修饰
class Solution { public: int ans = 0; void dfs(unordered_map<char,int> &hash) { //使用范围for取出哈希表中的数据 //这个取地址符不要忘记，不然终止不了递归 for(auto &it: hash) { //只要当前的数字还存在，就可以使用它形成新的序列 if(it.second) { it.second --; ans ++; //递归进去 dfs(hash); //还原现场 it.second ++; } } } int numTilePossibilities(string tiles) { unordered_map<char,int> hash; int n = tiles.size(); for(int i = 0; i <n;i++) hash[tiles[i]] ++; //直接把哈希表传进去dfs dfs(hash); return ans; } };
第五题 1219. 黄金矿工
题目描述
解题报告
暂时不知道多源DFS怎么结束递归，浅放一下吧，磕了好几个小时了，心塞。后面点了我来补充。
