day24
一、判断是否是平衡二叉树
思路
这题的要求又是一个谜。空间复杂度为1，这意味着都不能递归，因为递归开栈的空间复杂度就不止O(1)了 。
值得注意的是，求树的高度时不能自顶向下，这样总的时间复杂度就是N^2.为了避免重复计算一些节点的高度，可以采用自底向上的方式。
代码：
class Solution { public: bool dfs(TreeNode* root, int* depth) { if (root == nullptr) { *depth = 0; return true; } int leftdepth = 0; if (dfs(root->left, &leftdepth) == false) return false; int rightdepth = 0; if (dfs(root->right, &rightdepth) == false) return false; if (abs(leftdepth - rightdepth) > 1)return false; *depth = max(leftdepth,rightdepth)+1; return true; } bool IsBalanced_Solution(TreeNode* pRoot) { int n=0; return dfs(pRoot,&n); } };
二、最大子矩阵
思路
先枚举子矩阵左右端点作为宽，在确定好一个宽的区间之后，将整个宽度抽象成一维。于是就剩下的就是在一个一维数组里面求一段连续的最大和。
代码：
#include <iostream> #include<cstring> using namespace std; const int N=110; int a[N][N]; int f[N]; int main() { int n; cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; a[i][j]+=a[i][j-1]; } } int ans=-1e9; for(int a1=1;a1<=n;a1++){ for(int a2=a1;a2<=n;a2++){ memset(f,0,sizeof f); for(int b1=1;b1<=n;b1++){ int s=a[b1][a2]-a[b1][a1-1]; f[b1]=max(f[b1-1]+s,s); ans=max(f[b1],ans); } } } cout<<ans<<endl; return 0; }
三、小葱的01串
思路
字符串首尾相邻，可以复制一个它自己到尾部，这样就能以线性的视角看待环形字符串。
再根据题意，染色的子串长度一定是原来字符串长度的一半。设原来字符串长度为n,所以我们只需要维护一个区间为n的子串，从中间分开，看分开的两个区间中1的数量是否相等。由于非0即1，1的数量确定，0的数量也就确定。
于是我们枚举长度为n子串的左端点，右端点也就确定了，在用前缀和O（1）的时间复杂度内求出这个区间左右两半1的数量。
代码：
#include <iostream> using namespace std; const int N = 6e5 + 100; int a[N]; int main() { int n; cin >> n; string str; cin >> str; str += str; for (int i = 1; i <= 2 * n; i++) { a[i] = a[i - 1] + (str[i - 1] == '1' ? 1 : 0); } int ans = 0; for (int l = 1; l <= n; l++) { int r = l + n - 1; int mid = l + n / 2 - 1; if (a[r] - a[mid] == a[mid] - a[l - 1]) { ans++; } } cout << ans << endl; return 0; }
day25
一、笨小猴
哈希一遍就完了。
代码：
#include <iostream> #include<string> #include<unordered_map> using namespace std; bool is_prim(int x){ if(x<2)return false; for(int i=2;i<=x/i;i++){ if(x%i==0)return false; } return true; } int main() { string str; cin>>str; int maxn=0; int minn=1e9; unordered_map<char,int> mp; for(int i=0;i<str.size();i++){ mp[str[i]]++; } for(auto& it:mp){ maxn=max(it.second,maxn); minn=min(it.second,minn); } if(is_prim(maxn-minn)){ cout<<"Lucky Word"<<endl; cout<<maxn-minn<<endl; }else{ cout<<"No Answer"<<endl; cout<<0<<endl; } return 0; }
二、主持人调度
区间排序，按左端点排序。sort默认就是按第一个元素排序。
排序完后看时候是不是有两个相邻区间冲突，即节目i开始的时间在i-1节目的结束时间前面。
代码：
class Solution { public: bool hostschedule(vector<vector<int> >& schedule) { sort(schedule.begin(),schedule.end()); int n=schedule.size(); for(int i=1;i<n;i++){ if(schedule[i][0]<schedule[i-1][1]){ return false; } } return true; } };
三、分割等和子集
01背包问题。首先是看所有元素的和s是否是一个偶数。如果不是，说明不可能平均分割出两个相等和的子集。
然后在n个元素里面选，看能不能凑成s/2。f[j]表示从n个元素选任意元素能否凑成和为j，是一个布尔值。
对于第i个元素来说，如果选了这个数，那么f[j]的值取决于f[j-a[i]]，如果f[j-a[i]]为真，说明能凑出j-a[i],也就一定能凑出j。
于是易得状态f[j] |= f[j-a[i]]
代码:
#include <iostream> #include<vector> using namespace std; const int N=5e4; bool f[N+10]; int main() { int n; cin>>n; int s=0; vector<int> a(n+1); for(int i=1;i<=n;i++){ cin>>a[i]; s+=a[i]; } if(s%2){ cout<<"false"<<endl; return 0; } f[0]=true; for(int i=1;i<=n;i++){ for(int j=a[i];j<=N;j++){ f[j]|=f[j-a[i]]; } } if(f[s/2])cout<<"true"<<endl; else cout<<"false"<<endl; }
day27
一、kotori和气球
快速幂求组合数。有m个位置，每个位置上可以放一种气球，气球有n种，要求同种气球不相邻。
简单的排列组合问题，枚举每个位置可以放的气球种数。第一个位置为n,后面都是n-1.
所以组合的方式就是n*(m-1)^(n-1)。幂数过大，用快速幂。
代码：
#include <iostream> using namespace std; typedef long long LL; const int p=109; LL kuimi(LL a,LL b){ LL res=1; while(b){ if(b&1)res=res*a%p; b>>=1; a=a*a%p; } return res; } int main() { int n,m; cin>>n>>m; cout<<kuimi(n-1,m-1)*n%p<<endl; return 0; }
二、走迷宫
bfs板子题。
代码：
#include <iostream> #include<queue> using namespace std; typedef pair<int,int> PII; const int N=1100; char g[N][N]; bool st[N][N]; int dx[]={0,0,1,-1}; int dy[]={-1,1,0,0}; int n,m; int bfs(int sx,int sy,int ex,int ey){ queue<PII> q; q.push({sx,sy}); int res=0; while(!q.empty()){ int sz=q.size(); for(int i=0;i<sz;i++){ auto it=q.front(); q.pop(); int x=it.first; int y=it.second; if(x==ex&&y==ey)return res; st[x][y]=true; for(int j=0;j<4;j++){ int a=dx[j]+x; int b=dy[j]+y; if(a>=0&&a<n&&b>=0&&b<m&&!st[a][b]&&g[a][b]=='.'){ q.push({a,b}); st[a][b]=true; } } } res++; } return -1; } int main() { cin>>n>>m; int sx,sy,ex,ey; cin>>sx>>sy>>ex>>ey; getchar(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>g[i][j]; } } cout<<bfs(sx-1,sy-1,ex-1,ey-1)<<endl; return 0; }
三、主持人调度
优先队列+排序。先按活动开始的时间从小到大排序。枚举每一个活动，基于贪心的思想，看当前活动能不能由前面已经完成任务的主持人去主持。即维护一个最小堆，堆里面放的是还在第1到i-1个活动中还在执行的任务的结束时间。
取出前面活动的最小的结束时间，如果当前活动的开始时间大于它，说明堆顶这个活动的主持人在完成它的任务之后可以再去主持当前活动，并且把这个元素弹出堆顶，当前活动的结束时间入堆。
如果取出的最小结束时间小于当前活动的开始时间，表示堆里面已经没有主持人能马上赶过来主持当前任务，于是主持人数加一，并且新活动执行，活动的结束时间入堆。
代码：
class Solution { public: int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) { priority_queue<int,vector<int>,greater<int>> q; sort(startEnd.begin(),startEnd.end()); q.push(startEnd[0][1]); int ans=1; for(int i=1;i<n;i++){ if(startEnd[i][0]>=q.top()){ q.pop(); q.push(startEnd[i][1]); }else{ q.push(startEnd[i][1]); ans++; } } return ans; } };
day28
一、游游的重组偶数
用字符串读数据。遍历字符串，找一个偶数数位，跟末尾交换。
代码：
#include <iostream> using namespace std; int main() { int q; cin>>q; while(q--){ string num; cin>>num; int n=num.size(); if(num[n-1]%2==0){ cout<<num<<endl; continue; } int pos=-1; for(int i=0;i<num.size();i++){ if(num[i]%2==0){ pos=i; break; } } if(pos==-1){ cout<<-1<<endl; } else { swap(num[pos],num[num.size()-1]); cout<<num<<endl; } } return 0; }
二、体操队形
数据很小，暴力枚举每种排列方式。遍历每一种排队序列，看是否出现与a[i]要求位置矛盾的情况。没有则答案加一。
代码：
#include <iostream> #include<vector> using namespace std; const int N=11; int a[N]; int n; bool st[N]; int pos[N]; int ans; void dfs(int u,vector<int> p){ if(u==n+1){ for(int i=0;i<n;i++){ pos[p[i]]=i+1; } int f=0; for(int i=1;i<=n;i++){ if(a[i]==i)continue; if(pos[a[i]]>=pos[i]){ f=1; break; } } if(!f)ans++; } for(int i=1;i<=n;i++){ if(!st[i]){ p.push_back(i); st[i]=true; dfs(u+1,p); st[i]=false; p.pop_back(); } } } int main() { cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } vector<int> p; dfs(1,p); cout<<ans<<endl; return 0; }
三、二叉树的最大路径和
做过这道题，力扣里的原题。
设计一个函数getmax（root）表示以当前节点为路径的起点，往下走的最大路径和是多少。这个路径可以是往左走，也可以是往右孩子走。这样一来我们能求出所有单支路径的最大和的情况。但是由于答案路径可以两个孩子路径与父节点相连。所以我们还要用一个变量ans维护答案。
具体更新策略如下：
通过getmax函数能求的以左孩子为起点的最大路径和，也能求的以右孩子为起点的最大路径和。于是我们可以将当前节点的值与左右孩子为起点的最大路径和相加。这样所有路径都不会漏下了。
此外值得注意的是，如果左右孩子为起点最大路径和是负数，我们可以选择不要。ans初始化为负数，这是因为可能树的所有节点的值都是负数。
代码：
int ans; class Solution { public: int getmax(TreeNode* root){ if(root==nullptr)return 0; int l=max(0,getmax(root->left)); int r=max(0,getmax(root->right)); ans=max(ans,root->val+l+r); return root->val+max(l,r); } int maxPathSum(TreeNode* root) { ans=-1e9; getmax(root); return ans; } };
day29
一、排序子序列
暴力枚举：遍历整个数组。先判断如果a[i]！=a[i-1],那么说明一定出现了一个非递增或者非递减序列。为了保证序列段数最少，每个递增或者递减序列越长越好。
后判断如果a[i]==a[i-1]，则不一定属于是非递增或者非递减序列的一部分，比如 2 2 1和2 2 3 。当遍历到中间这个2时，我们并不知道 2 2 属于递增序列还是递减序列的一部分，我们得看后面第一个不相等的元素。如果小于2，那么 2 2这俩元素就属于非递增子序列，比如 2 2 1这个序列。否则就是属于非递减子序列，比如 2 2 3.
特判，如果后面全是相等的，那么把这所有相等的元素看成是非递增序列或者是非递减序列都可以，答案加一。
代码：
#include <iostream> using namespace std; const int N=1e5+10; int a[N]; int main() { int n; cin>>n; for(int i=0;i<n;i++)cin>>a[i]; if(n<=2){ cout<<1<<endl; return 0; } int ans=0; for(int i=1;i<n;i++){ if(a[i]>a[i-1]){ ans++; while(i<n&&a[i]>=a[i-1]){ i++; } }else if(a[i]<a[i-1]){ ans++; while(i<n&&a[i]<=a[i-1]){ i++; } } if(i==n-1)ans++; } cout<<ans<<endl; return 0; } // 64 位输出请用 printf("%lld")
二、消减整数
贪心或者记忆化搜索。思考这样一个问题，什么时候可以减去2倍的数字？设上一次减去的数字是d。
如果这个剩下的数h能够被2*d整除.这个时候一定能减去2*d且不会出现减到后面不能减到0的情况。（实在不行后面就每次都减2*d）
那如果剩下的数h不能被2*d整除呢？我们还能不能直接减去2*d呢？设x为h除以2*d的余数。这个x一定是小于2*d的且大于0。而后面每次减去的数都会比2*d大，且是2*d的倍数，这个x到 最后一定会被剩下来。就一定会导致h不能恰好减为0.
如何计算时间复杂度。虽然H的范围到1e9，但是，对于一个偶数来说，每次都能减去一个偶数，这个偶数一定是2^n且n一定是递增的,不可能出现连续3次相同的n。比如 2 2 2 一定可以转换成2 4。这两种方案是一样的。所以时间复杂度为tlog(H)
代码：
#include <iostream> #include<queue> using namespace std; int main() { int t; cin>>t; while(t--){ int h; cin>>h; int d=1; int ans=0; while(h){ h-=d; ans++; if(h%(2*d)==0)d*=2; } cout<<ans<<endl; } return 0; }
三、最长上升子序列（二）
dp+二分。
老板子题目了。dp[i]表示最长上升子序列长度为i的最后一个元素的值。d
遍历整个数组。如果a[i]>dp.back（）。说明a[i]能直接放到当前最长的子序列的后面。否则，我们就要在[0,dp.size()-1]里面去找一个第一个大于它的元素的位置pos，然后让dp[pos]=a[i]。因为a[i]>dp[pos-1]且a[i]
最后dp的长度就是最长子序列的长度。
代码：
class Solution { public: int LIS(vector<int>& a) { int n=a.size(); if(n==0)return 0; vector<int> dp; dp.push_back(a[0]); for(int i=1;i<n;i++){ if(a[i]>dp.back()){ dp.push_back(a[i]); }else{ int l=-1; int r=dp.size(); while(l+1!=r){ int mid=(l+r)>>1; if(dp[mid]>a[i])r=mid; else l=mid; } if(r>=0&&r<dp.size()){ // cout<<"iii"<<r<<endl; dp[r]=a[i]; } } // cout<<dp.size()<<endl; } return dp.size(); } };
【笔试训练】day24-day48合集（2）：https://developer.aliyun.com/article/1515238
