和百练机试格式一样，百练上的中文题已经刷得差不多了，剩下的英文题不好定义难度，过于简单和过于难的机试都不会考，反而LeetCode标了难度为medium的都在机试范围内，虽然机试不建议刷LeetCode，因为有很多机试题重点在于数据处理，而LeetCode正好帮助新手避免了这个问题，但是因为我是老司机了（bushi，所以还是刷LeetCode了，以medium为主
目录：日期+题号+题目大意+题解+总结
2021.3.31
3：无重复字符的最长子串
题目大意：如题
一开始以为只有小写字母，直接二分答案+
判断，结果还有数字字符乱七八糟的，我直接开256布尔数组，老暴力了，时间复杂度
.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { public: bool check(int x,string s) { int flag[256]={0}; bool mark=true; for (int i=0;i<x;++i) if (!flag[(int)s[i]]) ++flag[(int)s[i]]; else mark=false,++flag[(int)s[i]]; if (mark) return true; for (int i=1;i<=s.length()-x;++i) { --flag[(int)s[i-1]],++flag[(int)s[i+x-1]],mark=true; for (int j=0;j<256;++j) if (flag[j] && flag[j]!=1) { mark=false; break; } if (mark) return true; } return false; } int lengthOfLongestSubstring(string s) { int l=1,r=s.length(),ans=0; while (l<=r) { int mid=(l+r)>>1; if (check(mid,s)) ans=mid,l=mid+1; else r=mid-1; } return ans; } }; |
总结：①其实没啥好总结的，但是前段时间在忙论文得有一个月没做算法题，然后晚上脑子直接瓦特了，反正调了好久
5：最长回文子串
题目大意：如题
md一开始以为又是一个二分，刷刷一通写，后来发现并不满足二分的性质，盲猜dp一看题解果然是，直接dp判断i~j的子串是不是回文串就好了，转移方程还是很好想的，但是我一开始想错方向了，高级做法是manacher，有时间再更新学习笔记吧
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { private: bool dp[1010][1010]; public: string longestPalindrome(string s) { string ans; int maxlen=0; for (int i=0;i<s.length();++i) dp[i][i]=true; for (int i=0;i<s.length()-1;++i) dp[i][i+1]=(s[i]==s[i+1]); for (int i=2;i<=s.length();++i) for (int j=0;j<s.length()-i;++j) dp[j][j+i]=dp[j+1][j+i-1] && (s[j]==s[j+i]); for (int i=0;i<s.length();++i) for (int j=i;j<s.length();++j) if (dp[i][j] && maxlen<j-i+1) maxlen=j-i+1,ans=s.substr(i,j-i+1); return ans; } }; |
2021.4.1
6：Z字形变换
题目大意：给出一个字符串，以倒立Z字形排列，然后按行按列从左到右输出排列后的字符串
直接模拟，根据一个Z字形判断需要多少个字符，然后根据行数进行赋值即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { private: char T[1010][5020]; public: string convert(string s, int numRows) { int n=numRows+numRows-2,posx=1,posy=1,m; if (n) m=(int)ceil(s.length()*1.0/n)*(numRows-1); else return s; string ans; for (int i=1;i<=numRows;++i) for (int j=1;j<=m;++j) T[i][j]=' '; T[posx][posy]=s[0]; for (int i=1;i<s.length();++i) { if (i%n<numRows && i%n) ++posx; if (i%n>=numRows || i%n==0) --posx,++posy; T[posx][posy]=s[i]; } for (int i=1;i<=numRows;++i) for (int j=1;j<=m;++j) if (T[i][j]!=' ') ans+=T[i][j]; return ans; } }; |
总结：①忘了考虑n可能为0的情况，导致除0RE
1006：笨阶乘
题目大意：把原先阶乘计算的乘号全部换成乘除加减，然后计算改变后的阶乘
可以发现乘除挨在一块永远是一块计算的，然后算完的数剩下的只剩加减法了，无论是用栈还是队列都可以直接加减加减循环计算，我这里用的是队列
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { public: int clumsy(int N) { int ans=N; queue<int>S; for (int i=0;i<N-1;++i) { if (i%4==0) ans*=(N-i-1); if (i%4==1) ans/=(N-i-1); if (i%4==2) S.push(ans),S.push(N-i-1),ans=0; if (i%4==3) ans=N-i-1; } if (ans) S.push(ans); if (S.size()<2) return ans; else { int count=0; ans=S.front(),S.pop(); while (!S.empty()) { ++count; if (count&1) ans+=S.front(),S.pop(); else ans-=S.front(),S.pop(); } } return ans; } }; |
2021.4.2
8：字符串转换整数
题目大意：如题
实际上就是让你手动实现C++atoi，按照题目上的步骤一步步来就行，几个样例覆盖比较全面，边界用long long处理的，唯一sb的地方是计算字符串的时候不知道为什么nt地设置Pow数组来记录
，明明ans反复*10就能解决的问题，果然年纪大了QAQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { private: const int inf=0x7fffffff; public: int myAtoi(string s) { int pos; for (pos=0;pos<s.length() && s[pos]==' ';++pos); bool flag=true; if (s[pos]=='-') flag=false; if (s[pos]=='+' || s[pos]=='-') ++pos; int st=pos,ed; for (;s[pos]>='0' && s[pos]<='9' && pos<s.length();++pos); ed=pos; long long ans=0; string tmp=s.substr(st,ed-st); for (int i=0;i<tmp.length();++i) { ans=ans*10+(tmp[i]-'0'); if (flag && ans>(long long)inf) { ans=(long long)inf; break; } if (!flag && ans>-(long long)(1<<31)) { ans=-(long long)(1<<31); break; } } if (flag) return (int)ans; else return (int)-ans; } }; |
2021.4.3
1143：最长公共子序列
题目大意：子序列的定义改为不改变排列顺序删除任意个字符得到的字符串都为子序列，求最长公共子序列
果然dp一生之敌，一开始没往dp上面想，因为子序列的定义改了，感觉dp并不能表示所有状态（事实证明我错了），所以就把所有可能的序列都列举出来跑一个一维的最长上升子序列，结果被无数个a重复的数据卡TLE了，不过只要不是这种极限数据，一维最长上升子序列的复杂度应该能完爆普通数据，就是极限的情况就不行了，所以还是二维dp吧，状态转移方程就不说了，稍微想想就有了
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { private: int dp[1010][1010]; public: int longestCommonSubsequence(string text1, string text2) { for (int i=1;i<=text1.length();++i) for (int j=1;j<=text2.length();++j) if (text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); return dp[text1.length()][text2.length()]; } }; |
总结：①尝试所有可能的解决方案，对dp不熟所以没有一下子想到dp，还需要多练
2021.4.4
781：森林中的兔子
题目大意：每个兔子有一个颜色，给出一个序列，序列中的每个值是与当前兔子颜色相同的兔子数，求最少的兔子数
其实是一个思维题，我一开始还以为套个并查集然后一查大小就完事了，后来发现这样做的问题是相同数的兔子可能并不是同一种颜色，比如说3个1肯定就至少是两个颜色，于是直接想到n个n-1肯定是同一种颜色，把所有颜色的数目统计一下直接累加就可以了
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { private: int num[1010]; public: int numRabbits(vector<int>& answers) { int ans=0; for (int i=0;i<answers.size();++i) ++num[answers[i]]; for (int i=0;i<1000;++i) if (num[i]) ans+=(int)ceil(num[i]*1.0/(i+1))*(i+1); return ans; } }; |
12：整数转罗马数字
题目大意：如题
把题目中列的罗马数字，加上特殊的4、9、40、90什么的全都放进map里转成罗马字符串，然后从大到小循环找比当前数小的最大数去减，减一个输出一个对应的罗马数字即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { private: map<int,string>G; public: string intToRoman(int num) { string ans; G[1]="I",G[5]="V",G[10]="X",G[50]="L",G[100]="C",G[500]="D",G[1000]="M"; G[4]="IV",G[9]="IX",G[40]="XL",G[90]="XC",G[400]="CD",G[900]="CM"; int nums[13]={1,4,5,9,10,40,50,90,100,400,500,900,1000}; while (num) { for (int i=12;i>=0;--i) if (nums[i]<=num) { while (num>=nums[i]) ans+=G[nums[i]],num-=nums[i]; break; } } return ans; } }; |
2021.4.5
15：三数之和
题目大意：求序列中的三元组使得三元组之和为0，三元组不能重复
其实
很好想，我想的是枚举两个数
和
，然后判断
是否也出现在序列中，然而这样做很大问题出现在判断重复上，T了无数次终于发现自己脑子瓦特了，一开始我的做法是疯狂上STL，用map映射、二分查找、set去重，然后push进vector的时候按顺序push，还写了个三个数从小到大排序，然而对于大量的0这个数据T了，然后我又离散化手动map，这样查找时间复杂度
了，但是还是T，可能3k的数据量对于常数太大的程序在lc上容易T，后来想明白了，既然记录了每个数出现的次数又何必再遍历原数组呢，直接遍历去重后的数组不就可以了么，然后就A了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#pragma GCC optimize(3) class Solution { private: int uni_nums[3010],tot,count[3010],id[500010]={-1}; public: vector<int> get(int x,int y,int z) { vector<int>tmp; if (x<=y && x<=z) tmp.push_back(x),tmp.push_back(min(y,z)),tmp.push_back(max(y,z)); else if (y<=x && y<=z) tmp.push_back(y),tmp.push_back(min(x,z)),tmp.push_back(max(x,z)); else tmp.push_back(z),tmp.push_back(min(x,y)),tmp.push_back(max(x,y)); return tmp; } vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int> >ans; set<vector<int>>Q; if (nums.size()<3) return ans; sort(nums.begin(),nums.end()),uni_nums[++tot]=nums[0],id[nums[0]+200000]=tot; int last=nums[0]; for (int i=1;i<nums.size();++i) if (nums[i]!=last) uni_nums[++tot]=nums[i],last=nums[i],id[nums[i]+200000]=tot; for (int i=0;i<nums.size();++i) ++count[id[nums[i]+200000]]; for (int i=1;i<=tot;++i) for (int j=i;j<=tot;++j) { int pi=id[uni_nums[i]+200000],pj=id[uni_nums[j]+200000],t=id[-uni_nums[i]-uni_nums[j]+200000]; --count[pi],--count[pj]; if (t>0 && t<=tot && count[t] && count[pi]>=0 && count[pj]>=0) Q.insert(get(uni_nums[i],uni_nums[j],-uni_nums[i]-uni_nums[j])); ++count[pi],++count[pj]; } for (set<vector<int> >::iterator i=Q.begin();i!=Q.end();++i) ans.push_back(*i); return ans; } }; |
总结：①STL常数太大，能尽量不用就不用②吐槽lc数据范围标的
，结果加上还有负数
2021.4.6
16：最接近的三数之和
题目大意：找出三个数使得三数之和接近target，求这三个数的和
二分答案，二分与target的差x，然后查找target-x和target+x之间是否有数存在，这个可以用前缀和实现，时间复杂度
.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
class Solution { private: int ans,num[20010],diff; const int sum=1e4; map<int,int>G; public: bool check(int x,vector<int>& nums,int target) { for (int i=0;i<nums.size()-1;++i) for (int j=i+1;j<nums.size();++j) { int count=0; if (nums[i]>=target-x-nums[i]-nums[j] && nums[i]<=target+x-nums[i]-nums[j]) ++count; if (nums[j]>=target-x-nums[i]-nums[j] && nums[j]<=target+x-nums[i]-nums[j]) ++count; if (num[target+x-nums[i]-nums[j]+sum]-num[target-x-nums[i]-nums[j]+sum-1]-count) return true; } return false; } int threeSumClosest(vector<int>& nums, int target) { for (int i=0;i<nums.size();++i) ++num[nums[i]+sum],++G[nums[i]]; for (int i=1;i<=2*sum;++i) num[i]+=num[i-1]; int l=0,r=1e4; while (l<=r) { int mid=(l+r)>>1; if (check(mid,nums,target)) diff=mid,r=mid-1; else l=mid+1; } for (int i=0;i<nums.size()-1;++i) for (int j=i+1;j<nums.size();++j) { --G[nums[i]],--G[nums[j]]; if (G[target+diff-nums[i]-nums[j]]) ans=target+diff; else if (G[target-diff-nums[i]-nums[j]]) ans=target-diff; ++G[nums[i]],++G[nums[j]]; } return ans; } }; |
80：删除有序数组中的重复项 II
题目大意：在空间复杂度下原地删除出现超过2次的数
超过2次的数标记为inf，然后用vector.erase删除这个数，删除的过程中vector.size()会有变化，所以用while循环来进行删除
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { private: const int inf=1e5; public: int removeDuplicates(vector<int>& nums) { int count=0,last; last=nums[0],++count; for (int i=1;i<nums.size();++i) if (nums[i]==last) { ++count; if (count>2) nums[i]=inf; } else last=nums[i],count=1; int pos=0; while (pos<nums.size()) { while (pos<nums.size() && nums[pos]==inf) nums.erase(nums.begin()+pos); ++pos; } return nums.size(); } }; |
2021.4.7
81：搜索旋转排序数组 II
题目大意：将一个数组按某个位置旋转求值为target的数是否在数组中
应该是让练习二分查找的，但是我一看复杂度能过我就直接遍历了。。
|
1 2 3 4 5 6 7 8 |
class Solution { public: bool search(vector<int>& nums, int target) { for (int i=0;i<nums.size();++i) if (nums[i]==target) return true; return false; } }; |
17：电话号码的字母组合
题目大意：如题
字符串最大长度为4，也就是最多四重循环，直接上循环
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Solution { private: map<int,string>G; public: vector<string> letterCombinations(string digits) { vector<string>ans; G[2]="abc",G[3]="def",G[4]="ghi",G[5]="jkl",G[6]="mno",G[7]="pqrs",G[8]="tuv",G[9]="wxyz"; if (digits.size()==1) for (int i=0;i<G[digits[0]-'0'].length();++i) { string tmp=""; tmp+=G[digits[0]-'0'][i]; ans.push_back(tmp); } if (digits.size()==2) for (int i=0;i<G[digits[0]-'0'].length();++i) for (int j=0;j<G[digits[1]-'0'].length();++j) { string tmp=""; tmp+=G[digits[0]-'0'][i]; tmp+=G[digits[1]-'0'][j]; ans.push_back(tmp); } if (digits.size()==3) for (int i=0;i<G[digits[0]-'0'].length();++i) for (int j=0;j<G[digits[1]-'0'].length();++j) for (int k=0;k<G[digits[2]-'0'].length();++k) { string tmp=""; tmp+=G[digits[0]-'0'][i]; tmp+=G[digits[1]-'0'][j]; tmp+=G[digits[2]-'0'][k]; ans.push_back(tmp); } if (digits.size()==4) for (int i=0;i<G[digits[0]-'0'].length();++i) for (int j=0;j<G[digits[1]-'0'].length();++j) for (int k=0;k<G[digits[2]-'0'].length();++k) for (int l=0;l<G[digits[3]-'0'].length();++l) { string tmp=""; tmp+=G[digits[0]-'0'][i]; tmp+=G[digits[1]-'0'][j]; tmp+=G[digits[2]-'0'][k]; tmp+=G[digits[3]-'0'][l]; ans.push_back(tmp); } return ans; } }; |
2021.4.8
153：寻找旋转排序数组中的最小值
题目大意：如题
又是一道二分查找的题，我又直接遍历了。。
|
1 2 3 4 5 6 7 8 |
class Solution { public: int findMin(vector<int>& nums) { int ans=5001; for (int i=0;i<nums.size();++i) ans=min(ans,nums[i]); return ans; } }; |
19：删除链表的倒数第N个结点
题目大意：如题
其实进阶做法就是快慢指针，但是由于链表的题实在不知道该怎么写，只会纸上谈兵，不得已参考了一下std，发现标算都是先设一个头指针指向链表首结点，然后ans赋值为头指针，然后delete头指针返回ans
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *dummy=new ListNode(0,head); ListNode *fast=head,*slow=dummy; for (int i=0;i<n;++i) fast=fast->next; while (fast) fast=fast->next,slow=slow->next; slow->next=slow->next->next; ListNode *ans=dummy->next; delete dummy; return ans; } }; |
2021.4.10
102：二叉树的层序遍历
题目大意：如题
实际上层序遍历就是每一层从左到右遍历，本质上还是bfs，所以用队列记录一下每个结点所在的深度，然后相同深度的push_back即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<pair<int,int>>q; vector<vector<int>>ans; queue<TreeNode*>Q; vector<int>tmp; int last=0; if (root) Q.push(root),q.push(make_pair(root->val,0)); while (!Q.empty()) { TreeNode *x=Q.front(); Q.pop(); if (q.front().second==last) tmp.push_back(q.front().first); else ans.push_back(tmp),last=q.front().second,tmp.clear(),tmp.push_back(q.front().first); if (x->left) Q.push(x->left),q.push(make_pair(x->left->val,q.front().second+1)); if (x->right) Q.push(x->right),q.push(make_pair(x->right->val,q.front().second+1)); q.pop(); } if (tmp.size()) ans.push_back(tmp); return ans; } }; |
103：二叉树的锯齿形层序遍历
题目大意：如题
实际上就是102奇数层正着扫偶数层反着扫，我们已知每个层的大小之后直接在索引把结点值赋上即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>>ans; queue<TreeNode*>q; if (root) q.push(root); bool flag=true; while (!q.empty()) { int size=q.size(); vector<int>level(size, 0); while (size--) { root=q.front(); q.pop(); level[flag?level.size()-size-1:size]=root->val; if (root->left) q.push(root->left); if (root->right) q.push(root->right); } ans.push_back(move(level)); flag=!flag; } return ans; } }; |
2021.4.11
78：子集
题目大意：给出一个集合求所有子集
dfs，用flag记录当前元素选了或没选，当前元素个数>n时输出方案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { private: vector<vector<int>>ans; vector<int>tmp; bool flag[11]; public: void dfs(int x,vector<int>&nums) { if (x>=nums.size()) { tmp.clear(); for (int i=0;i<nums.size();++i) if (flag[i]) tmp.push_back(nums[i]); ans.push_back(tmp); } else { flag[x]=true,dfs(x+1,nums); flag[x]=false,dfs(x+1,nums); } } vector<vector<int>> subsets(vector<int>& nums) { dfs(0,nums); return ans; } }; |
90：子集 II
题目大意：与上题不同的是集合中可能有重复元素，输出的子集要去重
在上题的基础上对集合sort一下然后放入set去重
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { private: bool flag[11]; vector<vector<int>>ans; vector<int>tmp; set<vector<int>>Q; public: void dfs(int x,vector<int>&nums) { if (x>=nums.size()) { tmp.clear(); for (int i=0;i<nums.size();++i) if (flag[i]) tmp.push_back(nums[i]); sort(tmp.begin(),tmp.end()); Q.insert(tmp); } else { flag[x]=true,dfs(x+1,nums); flag[x]=false,dfs(x+1,nums); } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { dfs(0,nums); for (set<vector<int>>::iterator i=Q.begin();i!=Q.end();++i) ans.push_back(*i); return ans; } }; |
2021.4.12
179：最大数
题目大意：给出一些整数，求这些整数连接在一起产生的最大值
其实挺简单的一道题，但是中间有个细节想错了，比如3和34连接，应该是343而不是334，其实比较的就是两个字符串连接之后哪个比较大，排序即可，而不是讨论34和3的最后一个字符的大小，直接根据字符串连接来排序即可，排的序是带有传递性的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Solution { private: string s[110]; public: static bool cmp(string x,string y) { if (x[0]<y[0]) return false; else if (x[0]==y[0]) { string tmp1=x+y,tmp2=y+x; if (tmp1>tmp2) return true; else return false; } else return true; return false; } string largestNumber(vector<int>& nums) { string tmp,ans; for (int i=0;i<nums.size();++i) { tmp=""; if (nums[i]==0) { s[i]="0"; continue; } while (nums[i]) tmp+=nums[i]%10+'0',nums[i]/=10; reverse(tmp.begin(),tmp.end()),s[i]=tmp; } sort(s,s+nums.size(),cmp); for (int i=0;i<nums.size();++i) ans.append(s[i]); int pos=0; while (ans[pos]=='0' && pos<ans.length()-1) ++pos; ans=ans.substr(pos,ans.length()-pos); return ans; } }; |
264：丑数 II
题目大意：只能被2、3、5整除的数为丑数，求第n个丑数是哪个数
调一下测试用例就能知道第1690个数大约接近int的最大值，所以直接打表即可（雾
其实是我并不会正解，看了一下正解用的最小堆
和dp 的，没太看懂，但是打表是真的快，30s就打出来了
打表程序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<bits/stdc++.h> using namespace std; int n=1690; int main() { string ans; int i=1,count=0; while (count!=1690) { int x=i; while (x!=1) { if (x%2==0) x/=2; else if (x%3==0) x/=3; else if (x%5==0) x/=5; else break; } if (x==1) { ++count; string tmp=""; int y=i; while (y) tmp+=y%10+'0',y/=10; reverse(tmp.begin(),tmp.end()); ans.append(tmp),ans+=','; } ++i; } freopen("biao.txt","w",stdout); cout<<ans<<endl; return 0; } |
（这难道不是正解？）
|
1 2 3 4 5 6 7 |
int ans[]={1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100,108,120,125,128,135,144,150,160,162,180,192,200,216,225,240,243,250,256,270,288,300,320,324,360,375,384,400,405,432,450,480,486,500,512,540,576,600,625,640,648,675,720,729,750,768,800,810,864,900,960,972,1000,1024,1080,1125,1152,1200,1215,1250,1280,1296,1350,1440,1458,1500,1536,1600,1620,1728,1800,1875,1920,1944,2000,2025,2048,2160,2187,2250,2304,2400,2430,2500,2560,2592,2700,2880,2916,3000,3072,3125,3200,3240,3375,3456,3600,3645,3750,3840,3888,4000,4050,4096,4320,4374,4500,4608,4800,4860,5000,5120,5184,5400,5625,5760,5832,6000,6075,6144,6250,6400,6480,6561,6750,6912,7200,7290,7500,7680,7776,8000,8100,8192,8640,8748,9000,9216,9375,9600,9720,10000,10125,10240,10368,10800,10935,11250,11520,11664,12000,12150,12288,12500,12800,12960,13122,13500,13824,14400,14580,15000,15360,15552,15625,16000,16200,16384,16875,17280,17496,18000,18225,18432,18750,19200,19440,19683,20000,20250,20480,20736,21600,21870,22500,23040,23328,24000,24300,24576,25000,25600,25920,26244,27000,27648,28125,28800,29160,30000,30375,30720,31104,31250,32000,32400,32768,32805,33750,34560,34992,36000,36450,36864,37500,38400,38880,39366,40000,40500,40960,41472,43200,43740,45000,46080,46656,46875,48000,48600,49152,50000,50625,51200,51840,52488,54000,54675,55296,56250,57600,58320,59049,60000,60750,61440,62208,62500,64000,64800,65536,65610,67500,69120,69984,72000,72900,73728,75000,76800,77760,78125,78732,80000,81000,81920,82944,84375,86400,87480,90000,91125,92160,93312,93750,96000,97200,98304,98415,100000,101250,102400,103680,104976,108000,109350,110592,112500,115200,116640,118098,120000,121500,122880,124416,125000,128000,129600,131072,131220,135000,138240,139968,140625,144000,145800,147456,150000,151875,153600,155520,156250,157464,160000,162000,163840,164025,165888,168750,172800,174960,177147,180000,182250,184320,186624,187500,192000,194400,196608,196830,200000,202500,204800,207360,209952,216000,218700,221184,225000,230400,233280,234375,236196,240000,243000,245760,248832,250000,253125,256000,259200,262144,262440,270000,273375,276480,279936,281250,288000,291600,294912,295245,300000,303750,307200,311040,312500,314928,320000,324000,327680,328050,331776,337500,345600,349920,354294,360000,364500,368640,373248,375000,384000,388800,390625,393216,393660,400000,405000,409600,414720,419904,421875,432000,437400,442368,450000,455625,460800,466560,468750,472392,480000,486000,491520,492075,497664,500000,506250,512000,518400,524288,524880,531441,540000,546750,552960,559872,562500,576000,583200,589824,590490,600000,607500,614400,622080,625000,629856,640000,648000,655360,656100,663552,675000,691200,699840,703125,708588,720000,729000,737280,746496,750000,759375,768000,777600,781250,786432,787320,800000,810000,819200,820125,829440,839808,843750,864000,874800,884736,885735,900000,911250,921600,933120,937500,944784,960000,972000,983040,984150,995328,1000000,1012500,1024000,1036800,1048576,1049760,1062882,1080000,1093500,1105920,1119744,1125000,1152000,1166400,1171875,1179648,1180980,1200000,1215000,1228800,1244160,1250000,1259712,1265625,1280000,1296000,1310720,1312200,1327104,1350000,1366875,1382400,1399680,1406250,1417176,1440000,1458000,1474560,1476225,1492992,1500000,1518750,1536000,1555200,1562500,1572864,1574640,1594323,1600000,1620000,1638400,1640250,1658880,1679616,1687500,1728000,1749600,1769472,1771470,1800000,1822500,1843200,1866240,1875000,1889568,1920000,1944000,1953125,1966080,1968300,1990656,2000000,2025000,2048000,2073600,2097152,2099520,2109375,2125764,2160000,2187000,2211840,2239488,2250000,2278125,2304000,2332800,2343750,2359296,2361960,2400000,2430000,2457600,2460375,2488320,2500000,2519424,2531250,2560000,2592000,2621440,2624400,2654208,2657205,2700000,2733750,2764800,2799360,2812500,2834352,2880000,2916000,2949120,2952450,2985984,3000000,3037500,3072000,3110400,3125000,3145728,3149280,3188646,3200000,3240000,3276800,3280500,3317760,3359232,3375000,3456000,3499200,3515625,3538944,3542940,3600000,3645000,3686400,3732480,3750000,3779136,3796875,3840000,3888000,3906250,3932160,3936600,3981312,4000000,4050000,4096000,4100625,4147200,4194304,4199040,4218750,4251528,4320000,4374000,4423680,4428675,4478976,4500000,4556250,4608000,4665600,4687500,4718592,4723920,4782969,4800000,4860000,4915200,4920750,4976640,5000000,5038848,5062500,5120000,5184000,5242880,5248800,5308416,5314410,5400000,5467500,5529600,5598720,5625000,5668704,5760000,5832000,5859375,5898240,5904900,5971968,6000000,6075000,6144000,6220800,6250000,6291456,6298560,6328125,6377292,6400000,6480000,6553600,6561000,6635520,6718464,6750000,6834375,6912000,6998400,7031250,7077888,7085880,7200000,7290000,7372800,7381125,7464960,7500000,7558272,7593750,7680000,7776000,7812500,7864320,7873200,7962624,7971615,8000000,8100000,8192000,8201250,8294400,8388608,8398080,8437500,8503056,8640000,8748000,8847360,8857350,8957952,9000000,9112500,9216000,9331200,9375000,9437184,9447840,9565938,9600000,9720000,9765625,9830400,9841500,9953280,10000000,10077696,10125000,10240000,10368000,10485760,10497600,10546875,10616832,10628820,10800000,10935000,11059200,11197440,11250000,11337408,11390625,11520000,11664000,11718750,11796480,11809800,11943936,12000000,12150000,12288000,12301875,12441600,12500000,12582912,12597120,12656250,12754584,12800000,12960000,13107200,13122000,13271040,13286025,13436928,13500000,13668750,13824000,13996800,14062500,14155776,14171760,14348907,14400000,14580000,14745600,14762250,14929920,15000000,15116544,15187500,15360000,15552000,15625000,15728640,15746400,15925248,15943230,16000000,16200000,16384000,16402500,16588800,16777216,16796160,16875000,17006112,17280000,17496000,17578125,17694720,17714700,17915904,18000000,18225000,18432000,18662400,18750000,18874368,18895680,18984375,19131876,19200000,19440000,19531250,19660800,19683000,19906560,20000000,20155392,20250000,20480000,20503125,20736000,20971520,20995200,21093750,21233664,21257640,21600000,21870000,22118400,22143375,22394880,22500000,22674816,22781250,23040000,23328000,23437500,23592960,23619600,23887872,23914845,24000000,24300000,24576000,24603750,24883200,25000000,25165824,25194240,25312500,25509168,25600000,25920000,26214400,26244000,26542080,26572050,26873856,27000000,27337500,27648000,27993600,28125000,28311552,28343520,28697814,28800000,29160000,29296875,29491200,29524500,29859840,30000000,30233088,30375000,30720000,31104000,31250000,31457280,31492800,31640625,31850496,31886460,32000000,32400000,32768000,32805000,33177600,33554432,33592320,33750000,34012224,34171875,34560000,34992000,35156250,35389440,35429400,35831808,36000000,36450000,36864000,36905625,37324800,37500000,37748736,37791360,37968750,38263752,38400000,38880000,39062500,39321600,39366000,39813120,39858075,40000000,40310784,40500000,40960000,41006250,41472000,41943040,41990400,42187500,42467328,42515280,43046721,43200000,43740000,44236800,44286750,44789760,45000000,45349632,45562500,46080000,46656000,46875000,47185920,47239200,47775744,47829690,48000000,48600000,48828125,49152000,49207500,49766400,50000000,50331648,50388480,50625000,51018336,51200000,51840000,52428800,52488000,52734375,53084160,53144100,53747712,54000000,54675000,55296000,55987200,56250000,56623104,56687040,56953125,57395628,57600000,58320000,58593750,58982400,59049000,59719680,60000000,60466176,60750000,61440000,61509375,62208000,62500000,62914560,62985600,63281250,63700992,63772920,64000000,64800000,65536000,65610000,66355200,66430125,67108864,67184640,67500000,68024448,68343750,69120000,69984000,70312500,70778880,70858800,71663616,71744535,72000000,72900000,73728000,73811250,74649600,75000000,75497472,75582720,75937500,76527504,76800000,77760000,78125000,78643200,78732000,79626240,79716150,80000000,80621568,81000000,81920000,82012500,82944000,83886080,83980800,84375000,84934656,85030560,86093442,86400000,87480000,87890625,88473600,88573500,89579520,90000000,90699264,91125000,92160000,93312000,93750000,94371840,94478400,94921875,95551488,95659380,96000000,97200000,97656250,98304000,98415000,99532800,100000000,100663296,100776960,101250000,102036672,102400000,102515625,103680000,104857600,104976000,105468750,106168320,106288200,107495424,108000000,109350000,110592000,110716875,111974400,112500000,113246208,113374080,113906250,114791256,115200000,116640000,117187500,117964800,118098000,119439360,119574225,120000000,120932352,121500000,122880000,123018750,124416000,125000000,125829120,125971200,126562500,127401984,127545840,128000000,129140163,129600000,131072000,131220000,132710400,132860250,134217728,134369280,135000000,136048896,136687500,138240000,139968000,140625000,141557760,141717600,143327232,143489070,144000000,145800000,146484375,147456000,147622500,149299200,150000000,150994944,151165440,151875000,153055008,153600000,155520000,156250000,157286400,157464000,158203125,159252480,159432300,160000000,161243136,162000000,163840000,164025000,165888000,167772160,167961600,168750000,169869312,170061120,170859375,172186884,172800000,174960000,175781250,176947200,177147000,179159040,180000000,181398528,182250000,184320000,184528125,186624000,187500000,188743680,188956800,189843750,191102976,191318760,192000000,194400000,195312500,196608000,196830000,199065600,199290375,200000000,201326592,201553920,202500000,204073344,204800000,205031250,207360000,209715200,209952000,210937500,212336640,212576400,214990848,215233605,216000000,218700000,221184000,221433750,223948800,225000000,226492416,226748160,227812500,229582512,230400000,233280000,234375000,235929600,236196000,238878720,239148450,240000000,241864704,243000000,244140625,245760000,246037500,248832000,250000000,251658240,251942400,253125000,254803968,255091680,256000000,258280326,259200000,262144000,262440000,263671875,265420800,265720500,268435456,268738560,270000000,272097792,273375000,276480000,279936000,281250000,283115520,283435200,284765625,286654464,286978140,288000000,291600000,292968750,294912000,295245000,298598400,300000000,301989888,302330880,303750000,306110016,307200000,307546875,311040000,312500000,314572800,314928000,316406250,318504960,318864600,320000000,322486272,324000000,327680000,328050000,331776000,332150625,335544320,335923200,337500000,339738624,340122240,341718750,344373768,345600000,349920000,351562500,353894400,354294000,358318080,358722675,360000000,362797056,364500000,368640000,369056250,373248000,375000000,377487360,377913600,379687500,382205952,382637520,384000000,387420489,388800000,390625000,393216000,393660000,398131200,398580750,400000000,402653184,403107840,405000000,408146688,409600000,410062500,414720000,419430400,419904000,421875000,424673280,425152800,429981696,430467210,432000000,437400000,439453125,442368000,442867500,447897600,450000000,452984832,453496320,455625000,459165024,460800000,466560000,468750000,471859200,472392000,474609375,477757440,478296900,480000000,483729408,486000000,488281250,491520000,492075000,497664000,500000000,503316480,503884800,506250000,509607936,510183360,512000000,512578125,516560652,518400000,524288000,524880000,527343750,530841600,531441000,536870912,537477120,540000000,544195584,546750000,552960000,553584375,559872000,562500000,566231040,566870400,569531250,573308928,573956280,576000000,583200000,585937500,589824000,590490000,597196800,597871125,600000000,603979776,604661760,607500000,612220032,614400000,615093750,622080000,625000000,629145600,629856000,632812500,637009920,637729200,640000000,644972544,645700815,648000000,655360000,656100000,663552000,664301250,671088640,671846400,675000000,679477248,680244480,683437500,688747536,691200000,699840000,703125000,707788800,708588000,716636160,717445350,720000000,725594112,729000000,732421875,737280000,738112500,746496000,750000000,754974720,755827200,759375000,764411904,765275040,768000000,774840978,777600000,781250000,786432000,787320000,791015625,796262400,797161500,800000000,805306368,806215680,810000000,816293376,819200000,820125000,829440000,838860800,839808000,843750000,849346560,850305600,854296875,859963392,860934420,864000000,874800000,878906250,884736000,885735000,895795200,900000000,905969664,906992640,911250000,918330048,921600000,922640625,933120000,937500000,943718400,944784000,949218750,955514880,956593800,960000000,967458816,972000000,976562500,983040000,984150000,995328000,996451875,1000000000,1006632960,1007769600,1012500000,1019215872,1020366720,1024000000,1025156250,1033121304,1036800000,1048576000,1049760000,1054687500,1061683200,1062882000,1073741824,1074954240,1076168025,1080000000,1088391168,1093500000,1105920000,1107168750,1119744000,1125000000,1132462080,1133740800,1139062500,1146617856,1147912560,1152000000,1162261467,1166400000,1171875000,1179648000,1180980000,1194393600,1195742250,1200000000,1207959552,1209323520,1215000000,1220703125,1224440064,1228800000,1230187500,1244160000,1250000000,1258291200,1259712000,1265625000,1274019840,1275458400,1280000000,1289945088,1291401630,1296000000,1310720000,1312200000,1318359375,1327104000,1328602500,1342177280,1343692800,1350000000,1358954496,1360488960,1366875000,1377495072,1382400000,1399680000,1406250000,1415577600,1417176000,1423828125,1433272320,1434890700,1440000000,1451188224,1458000000,1464843750,1474560000,1476225000,1492992000,1500000000,1509949440,1511654400,1518750000,1528823808,1530550080,1536000000,1537734375,1549681956,1555200000,1562500000,1572864000,1574640000,1582031250,1592524800,1594323000,1600000000,1610612736,1612431360,1620000000,1632586752,1638400000,1640250000,1658880000,1660753125,1677721600,1679616000,1687500000,1698693120,1700611200,1708593750,1719926784,1721868840,1728000000,1749600000,1757812500,1769472000,1771470000,1791590400,1793613375,1800000000,1811939328,1813985280,1822500000,1836660096,1843200000,1845281250,1866240000,1875000000,1887436800,1889568000,1898437500,1911029760,1913187600,1920000000,1934917632,1937102445,1944000000,1953125000,1966080000,1968300000,1990656000,1992903750,2000000000,2013265920,2015539200,2025000000,2038431744,2040733440,2048000000,2050312500,2066242608,2073600000,2097152000,2099520000,2109375000,2123366400}; class Solution { public: int nthUglyNumber(int n) { return ans[n-1]; } }; |
2021.4.13
113：路径总和 II
题目大意：找出从树根到叶子结点的路径之和等于target的所有路径
dfs，找到叶子结点时判断路径之和是否等于target，不行就回溯找下一个
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { private: vector<vector<int>>ans; vector<int>tmp; public: void dfs(TreeNode *x,int targetSum) { if (x) { tmp.push_back(x->val); if (x->left==NULL && x->right==NULL) { int sum=0; for (int i=0;i<tmp.size();++i) sum+=tmp[i]; if (sum==targetSum) ans.push_back(tmp); return; } if (x->left) { dfs(x->left,targetSum); tmp.pop_back(); } if (x->right) { dfs(x->right,targetSum); tmp.pop_back(); } } } vector<vector<int>> pathSum(TreeNode* root, int targetSum) { dfs(root,targetSum); return ans; } }; |
131：分割回文串
题目大意：在字符串中切割任意刀，使得每个子串都是回文串，输出所有方案
dfs枚举出所有刀切的位置，就能得到所有切割方案，然后根据回文串的dp预处理可以判断是否是回文串
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution { private: vector<vector<string>>ans; vector<string>tmp; int n,dp[17][17]; public: void dfs(const string &s,int i) { if (i==n) { ans.push_back(tmp); return; } for (int j=i;j<n;++j) if (dp[i][j]) { tmp.push_back(s.substr(i,j-i+1)); dfs(s,j+1); tmp.pop_back(); } } vector<vector<string>> partition(string s) { n = s.size(); for (int i=0;i<n;++i) dp[i][i]=1; for (int i=0;i<n-1;++i) dp[i][i+1]=(s[i]==s[i+1]); for (int i=2;i<=n;++i) for (int j=0;j<n-i;++j) dp[j][j+i]=dp[j+1][j+i-1] && (s[j]==s[j+i]); dfs(s,0); return ans; } }; |
2021.4.14
200：岛屿数量
题目大意：给出01矩阵，求相连的1的块数
直接bfs然后设标记数组即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { private: int a[310][310],n,m,ans; bool flag[310][310]; queue<int>q; public: int get(int x,int y) { return (x-1)*m+y; } int numIslands(vector<vector<char>>& grid) { n=grid.size(),m=grid[0].size(); for (int i=0;i<n;++i) for (int j=0;j<m;++j) a[i+1][j+1]=grid[i][j]-'0'; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (!flag[i][j] && a[i][j]) { q.push(get(i,j)); while (!q.empty()) { int x=(int)ceil(q.front()*1.0/m),y=q.front()-(x-1)*m; q.pop(); if (x>1 && a[x-1][y] && !flag[x-1][y]) flag[x-1][y]=true,q.push(get(x-1,y)); if (y>1 && a[x][y-1] && !flag[x][y-1]) flag[x][y-1]=true,q.push(get(x,y-1)); if (x<n && a[x+1][y] && !flag[x+1][y]) flag[x+1][y]=true,q.push(get(x+1,y)); if (y<m && a[x][y+1] && !flag[x][y+1]) flag[x][y+1]=true,q.push(get(x,y+1)); } ++ans; } return ans; } }; |
207：课程表
题目大意：修某一门课需要把所有先修课程修完才能修，给出n个课程和若干个依赖关系，问能否全部修完
拓扑排序，之前一直没弄懂用邻接表怎么写，看到blog里说每次把入度为0的点放到队列里，每次dfs减去相邻点入度-1，用标记数组判断是否搜索过，如果搜索过表示有环存在返回false，否则为true
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#define N 100010 class Solution { private: int cnt,h[N],degree[N],tot; struct data { int to,next; }edge[5010]; bool flag[N],ans,mark[N]; queue<int>q; public: void add(int u,int v) { edge[++cnt]=(data){v,h[u]},h[u]=cnt; } void dfs(int x) { if (flag[x]) ans=false; flag[x]=true,mark[x]=true; for (int i=h[x];i;i=edge[i].next) { --degree[edge[i].to]; if (!degree[edge[i].to]) q.push(edge[i].to); } } bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { ans=true; for (int i=0;i<prerequisites.size();++i) ++degree[prerequisites[i][0]],add(prerequisites[i][1],prerequisites[i][0]); for (int i=0;i<numCourses;++i) if (!degree[i]) q.push(i); while (!q.empty()) { int x=q.front(); q.pop(),dfs(x); if (!ans) break; } for (int i=0;i<numCourses;++i) if (!mark[i]) { ans=false; break; } return ans; } }; |
2021.4.15
213：打家劫舍 II
题目大意：一个环形序列，每个序列上有权值，只能取不相邻的权值求能取到的最大值
环形dp，可以把序列拆成n个链状序列来跑dp，![dp[i][0/1]](http://www.newjourney520.cn/wp-content/plugins/latex/cache/tex_d29aa9c8a8b751cceee32116ae9924e3.gif)
表示当前第i个0表示不取，1表示取的最大值，转移方程![dp[i][0]=max(dp[i-1][1],dp[i-1][0]),dp[i][1]=dp[i-1][0]+a[i]](http://www.newjourney520.cn/wp-content/plugins/latex/cache/tex_b75f9fdb9a75f3a8856d52a1cd614ac9.gif)
.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { private: int dp[210][2],a[210]; public: int rob(vector<int>& nums) { int ans=0; if (nums.size()==1) return nums[0]; if (nums.size()==2) return max(nums[0],nums[1]); for (int i=0;i<2*nums.size();++i) a[i]=nums[i%nums.size()]; for (int i=0;i<nums.size()+2;++i) { memset(dp,0,sizeof(dp)),dp[i][0]=0,dp[i][1]=a[i]; for (int j=i+1;j<i+nums.size()-1;++j) dp[j][0]=max(dp[j-1][0],dp[j-1][1]),dp[j][1]=dp[j-1][0]+a[j]; ans=max(ans,max(dp[i+nums.size()-2][0],dp[i+nums.size()-2][1])); } return ans; } }; |
总结：①i+nums.size()-2可能小于0，这时数组越界应该加条件判断
210：课程表 II
题目大意：课程表那个题原题，现在需要输出修课的序列
课程表那个题拓扑排序稍微改改
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#define N 100010 class Solution { private: int cnt,h[N],degree[N],tot; struct data { int to,next; }edge[5010]; bool flag[N],mark; queue<int>q; vector<int>ans; public: void add(int u,int v) { edge[++cnt]=(data){v,h[u]},h[u]=cnt; } void dfs(int x) { if (flag[x]) mark=false; flag[x]=true; for (int i=h[x];i;i=edge[i].next) { --degree[edge[i].to]; if (!degree[edge[i].to]) q.push(edge[i].to); } } vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { mark=true; for (int i=0;i<prerequisites.size();++i) ++degree[prerequisites[i][0]],add(prerequisites[i][1],prerequisites[i][0]); for (int i=0;i<numCourses;++i) if (!degree[i]) q.push(i); while (!q.empty()) { int x=q.front(); ans.push_back(x),q.pop(),dfs(x); if (!mark) break; } if (!mark || ans.size()!=numCourses) ans.clear(); return ans; } }; |
2021.4.16
63：不同路径 II
题目大意：n*m矩阵中间有一些障碍物，求(1,1)走到(n,m)的方案数
直接dp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { private: int a[110][110],n,m,dp[110][110]; public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { n=obstacleGrid.size(),m=obstacleGrid[0].size(); for (int i=0;i<n;++i) for (int j=0;j<m;++j) a[i+1][j+1]=obstacleGrid[i][j]; if (a[n][m]) return 0; dp[1][1]=1; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (!a[i][j]) { if (!a[i-1][j]) dp[i][j]+=dp[i-1][j]; if (!a[i][j-1]) dp[i][j]+=dp[i][j-1]; } return dp[n][m]; } }; |
64：最小路径和
题目大意：(1,1)走到(n,m)的最小路径和
直接dp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { private: int dp[210][210],n,m,a[210][210]; public: int minPathSum(vector<vector<int>>& grid) { n=grid.size(),m=grid[0].size(); for (int i=0;i<n;++i) for (int j=0;j<m;++j) a[i+1][j+1]=grid[i][j]; for (int i=0;i<=n;++i) for (int j=0;j<=m;++j) dp[i][j]=200; dp[1][1]=a[1][1]; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (!(i==1 && j==1)) dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j]; return dp[n][m]; } }; |
2021.4.17
220：存在重复元素 III
题目大意：给出k和t，求是否存在两个不同下标i和j，使得abs(num[i]-num[j])<=t并且abs(i-j)<=k
先给序列排序，带id的cmp排序，然后对于每个a[i]就可以找到差的绝对值<=t的区间，然后在这个区间内找是否存在id差值在k以内的，直接用双指针指就可以了，一开始还以为是线段树，来求最大值最小值的思路是错误的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#define inf 0x7fffffff typedef long long LL; class Solution { private: int n; struct data { int id,val; }a[20010]; public: static bool cmp(data x,data y) { return x.val==y.val?x.id<y.id:x.val<y.val; } bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { if (nums.size()<=1) return false; for (int i=0;i<nums.size();++i) a[++n]=(data){i+1,nums[i]}; sort(a+1,a+n+1,cmp); for (int i=1;i<=n;++i) { int L=i,R=i; while (L>1 && abs((LL)a[i].val-(LL)a[L-1].val)<=t) { --L; if (abs(a[i].id-a[L].id)<=k) return true; } while (R<n && abs((LL)a[i].val-(LL)a[R+1].val)<=t) { ++R; if (abs(a[i].id-a[R].id)<=k) return true; } } return false; } }; |
2021.4.19
300：最长递增子序列
题目大意：如题
直接dp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { private: int ans,dp[2510],n; public: int lengthOfLIS(vector<int>& nums) { n=nums.size(); for (int i=0;i<n;++i) dp[i]=1; for (int i=n-1;i>=0;--i) for (int j=i+1;j<n;++j) if (nums[j]>nums[i]) dp[i]=max(dp[i],dp[j]+1); for (int i=0;i<n;++i) ans=max(ans,dp[i]); return ans; } }; |
2021.4.20
279：完全平方数
题目大意：给出一个数，求能用完全平方数相加的最小数量
n最大是1w，也就是说完全平方数最大为100，先用二分找到比n小的完全平方数是第几个，然后![dp[i]](http://www.newjourney520.cn/wp-content/plugins/latex/cache/tex_2e20c111ac36480b34873b71b5e40095.gif)
表示用完全平方数表示i所用的最小数量，实际是一个完全背包问题，![dp[j]=min(dp[j],dp[j-a[i]]+1)](http://www.newjourney520.cn/wp-content/plugins/latex/cache/tex_faa14504ecb2ba2d44651ed81f891ee1.gif)
，时间复杂度
，m表示比n小的完全平方数是第m个
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#define inf 0x3fff class Solution { private: int a[110],dp[10010]; public: int BinarySearch(int x) { int l=1,r=100; while (l<=r) { int mid=(l+r)>>1; if (a[mid]<=x) l=mid+1; else r=mid-1; } return l-1; } int numSquares(int n) { for (int i=1;i<=100;++i) a[i]=i*i; int p=BinarySearch(n); for (int i=1;i<=n;++i) dp[i]=inf; for (int i=1;i<=p;++i) dp[a[i]]=1; for (int i=1;i<=p;++i) for (int j=a[i];j<=n;++j) dp[j]=min(dp[j],dp[j-a[i]]+1); return dp[n]; } }; |
983：最低票价
题目大意：给出旅行行程，表示第几天去旅行，可以买1天、7天和30天的旅行通行证，每种通行证都有花费，求完成全部旅程的最小花费
比较显然的一维dp，表示完成前i个行程的最小花费，则转移方程为![dp[i]=min(dp[p1]+costs[0],dp[p2]+costs[1],dp[p3]+costs[2])](http://www.newjourney520.cn/wp-content/plugins/latex/cache/tex_81a9fa37e43711fe56230075d4f4b30f.gif)
，其中
分别表示第几天买的1天、7天、30天通行证，因为用了二分查找，时间复杂度
.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { private: int dp[370]; public: int BinarySearch(vector<int> &days,int x) { int l=0,r=days.size()-1; while (l<=r) { int mid=(l+r)>>1; if (days[mid]<=x) l=mid+1; else r=mid-1; } return l-1; } int mincostTickets(vector<int>& days, vector<int>& costs) { for (int i=0;i<days.size();++i) { int p1=BinarySearch(days,days[i]-1),p2=BinarySearch(days,days[i]-7),p3=BinarySearch(days,days[i]-30); if (p1>=0) dp[i]=dp[p1]+costs[0]; else dp[i]=costs[0]; if (p2>=0) dp[i]=min(dp[i],dp[p2]+costs[1]); else dp[i]=min(dp[i],costs[1]); if (p3>=0) dp[i]=min(dp[i],dp[p3]+costs[2]); else dp[i]=min(dp[i],costs[2]); } return dp[days.size()-1]; } }; |
2021.4.21
91：解码方法
题目大意：大写字母A到Z可以映射数字1到26，给出一个数字串，求有多少种由大写字母映射的数字串
可以先dfs暴搜出所有分割字符串的方法数，然后判断是否在1~26之间，保留出所有合法的方法就是答案，但是暴搜会超时，可以把暴搜改成记忆化搜索，用![dp[x]](http://www.newjourney520.cn/wp-content/plugins/latex/cache/tex_4def7508eabd292f4d6e966d5d23d885.gif)
记录当前在x位置分割的方法数，如果搜索过直接将答案返回即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution { private: vector<vector<string>>ans; vector<string>tmp; int dp[110]; bool flag[110]; public: int dfs(string s,int x) { if (flag[x]) return dp[x]; if (x==s.length()) { ans.push_back(tmp); return 1; } int res=0; for (int i=x;i<s.length();++i) { string t=s.substr(x,i-x+1); if (t.length()>2) continue; else if (t.length()==2 && (t>"26" || t<"10")) continue; else if (t.length()==1 && (t<"1" || t>"9")) continue; tmp.push_back(t); dp[i+1]=dfs(s,i+1),res+=dp[i+1],flag[i+1]=true; tmp.pop_back(); } return res; } int numDecodings(string s) { dp[0]=dfs(s,0); return dp[0]; } }; |
97：交错字符串
题目大意：给出三个字符串，求前两个字符串是否能完美交错匹配第三个字符串
自从dfs暴搜运用熟练之后，现在越来越喜欢记忆化搜索了，把暴搜打出来然后记忆化就A了，暴搜需要三个状态，当前匹配的第三个字符串位置
，匹配了第一个字符串
个字符，匹配了第二个字符串
个字符，然后边界条件是
分别等于三个字符串长度则返回true，否则返回false
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { private: bool dp[210][110][110],flag[210][110][110]; public: bool dfs(int x,int p1,int p2,string &s1,string &s2,string &s3) { if (flag[x][p1][p2]) return dp[x][p1][p2]; if (x==s3.length() && p1==s1.length() && p2==s2.length()) return true; else if (x==s3.length()) return false; if (s3[x]==s1[p1]) { dp[x+1][p1+1][p2]=dfs(x+1,p1+1,p2,s1,s2,s3); flag[x+1][p1+1][p2]=true; } if (s3[x]==s2[p2]) { dp[x+1][p1][p2+1]=dfs(x+1,p1,p2+1,s1,s2,s3); flag[x+1][p1][p2+1]=true; } return dp[x][p1][p2]=dp[x+1][p1+1][p2]||dp[x+1][p1][p2+1]; } bool isInterleave(string s1, string s2, string s3) { dp[0][0][0]=dfs(0,0,0,s1,s2,s3); return dp[0][0][0]; } }; |
总结：①标记是否搜索过的flag数组要在dfs之后设为true②边界条件要各种情况都考虑到，不能只考虑为true的情况
2021.4.22
139：单词拆分
题目大意：求是否能将一个字符串分成若干单词使得所有单词都在词表中
又是dfs+记忆化，但是这里写的时候出现了一些问题，按照之前写的分割字符串，然后最后对所有单词进行判断然后返回结果，用dp数组记录的时候没有在分割时判断是否在词表中，这个思路是错误的，原因是一开始分割的字符串极有可能是不满足条件的，然后判断为false之后赋给了dp数组，等到下次dfs到这个位置的时候就直接返回false了，并没有继续下一个尝试
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
class Solution { private: bool dp[210],pd[210]; vector<string>tmp; public: bool dfs(int x,string &s,vector<string> &wordDict) { if (pd[x]) return dp[x]; if (x==s.length()) { bool mark=true; for (int i=0;i<tmp.size();++i) { bool flag=false; for (int j=0;j<wordDict.size();++j) if (wordDict[j]==tmp[i]) { flag=true; break; } if (!flag) { mark=false; break; } } return mark; } bool ans=false; for (int i=x;i<s.length();++i) { string t=s.substr(x,i-x+1); bool flag=false; for (int j=0;j<wordDict.size();++j) if (wordDict[j]==t) { flag=true; break; } if (!flag) continue; tmp.push_back(s.substr(x,i-x+1)); dp[i+1]=dfs(i+1,s,wordDict),pd[i+1]=true,ans=ans||dp[i+1]; tmp.pop_back(); } return ans; } bool wordBreak(string s, vector<string>& wordDict) { dp[0]=dfs(0,s,wordDict); return dp[0]; } }; |
221：最大正方形
题目大意：给出n*m的01矩阵，求全为1的最大正方形的面积
最大正方形满足一个性质，最大正方形也包含次大正方形，所以在找最大正方形面积时可以一步步递增去判断是否满足条件的，进而满足二分答案的条件，所以二分正方形边长，预处理前缀和，然后判断枚举正方形的任意一个端点即可，时间复杂度
.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { private: int n,m,a[310][310],sum[310][310]; public: bool check(int x) { for (int i=x;i<=n;++i) for (int j=x;j<=m;++j) if (sum[i][j]-sum[i-x][j]-sum[i][j-x]+sum[i-x][j-x]==x*x) return true; return false; } int maximalSquare(vector<vector<char>>& matrix) { n=matrix.size(),m=matrix[0].size(); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) a[i][j]=matrix[i-1][j-1]-'0'; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; int l=0,r=min(n,m); while (l<=r) { int mid=(l+r)>>1; if (check(mid)) l=mid+1; else r=mid-1; } return (l-1)*(l-1); } }; |
2021.4.24
377：组合总和 IV
题目大意：给出互不相同的整数序列，求总和为target的组合个数
dfs暴搜还是非常好打的，然后就是dfs改记忆化，这部分也是昨天做题一直在困扰我的地方就是改成记忆化不好改，其实注意到一点是在每个dfs的过程中sum是一直在记录信息的，应该也作为状态之一，但是dp数组里没有记录sum，所以就不能完美表示所有状态
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { private: int ans,sum,dp[210][1010]; bool flag[210][1010]; public: int dfs(int x,vector<int> &nums,int target) { if (sum>target) return 0; if (flag[x][target-sum]) return dp[x][target-sum]; if (target==sum) return 1; int res=0; if (sum<target) for (int i=0;i<nums.size();++i) { sum+=nums[i]; if (sum>target) { sum-=nums[i]; continue; } dp[i][target-sum]=dfs(i,nums,target),flag[i][target-sum]=true,res+=dp[i][target-sum],sum-=nums[i]; } return res; } int combinationSum4(vector<int>& nums, int target) { return dfs(0,nums,target); } }; |
877：石子游戏
题目大意：偶数堆石子，两个人每人每次取一堆，总数为奇数，问是否有必胜策略
博弈论也是之前一直薄弱的地方，今天还专门找了篇博客学了学，大体理解了博弈论的中心思想，改天写篇博客总结一下，这个题最终结果是先手必胜的，上午的时候没有想明白原因，晚上的时候突然顿悟了，因为石子总数是奇数，而堆数是偶数，那么可以按奇数堆和偶数堆划分为两组，因为总数是奇数所以肯定有一组石子更多，无论后手怎么选，先手只要一直选那组石子更多的就可以必胜
|
1 2 3 4 5 6 |
class Solution { public: bool stoneGame(vector<int>& piles) { return true; } }; |
2021.4.25
40：组合总和 II
题目大意：求总和为target的所有组合，每个数只能选一次
求方案的只能dfs回溯，记录sum大于target剪枝即可，有更简便的方法可以dfs，但是目的是练回溯就不细究了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Solution { private: vector<int>tmp; vector<vector<int>>ans; int sum; public: void dfs(int x,vector<int> &candidates,int target) { if (sum>target) return; if (x==candidates.size()) { if (sum==target) { vector<int>Tmp=tmp; sort(Tmp.begin(),Tmp.end()); bool flag=true; for (int i=0;i<ans.size();++i) if (Tmp==ans[i]) { flag=false; break; } if (flag) ans.push_back(Tmp); } return; } tmp.push_back(candidates[x]),sum+=candidates[x]; dfs(x+1,candidates,target); tmp.pop_back(),sum-=candidates[x]; dfs(x+1,candidates,target); } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { dfs(0,candidates,target); return ans; } }; |
319：灯泡开关
题目大意：初始n个灯泡关闭，第i轮每i个灯泡切换状态，即第一轮每个灯泡切换状态，第二轮每两个灯泡切换状态，求n轮之后灯泡为开启的个数
一看到n的范围是
基本就知道是有简便方法的了，但是我一开始没看出来，非常显然的一个性质是第i个灯泡n轮之后的状态与i的因子个数有关，如果是奇数就亮偶数就暗，所以通过判断1~n的因子个数奇偶性即可，打了个暴力，发现答案正好等于
，然后直接输出就A了，但是不知道证明，看了一下题解之后发现，只有完全平方数的因子个数是奇数，非完全平方数的因子个数都是偶数，由一个数的因子个数的一半分布在
之间，所以非完全平方数的因子个数就算之间的因子个数*2，肯定是偶数，完全平方数的因子个数就是奇数
|
1 2 3 4 5 6 |
class Solution { public: int bulbSwitch(int n) { return (int)sqrt(n); } }; |
2021.4.26
372：超级次方
题目大意：求
的值，a的范围是int，b的范围是2000位整数
一看就是快速幂，然后准备用大整数取模，在网上搜了一下板子，基本上都是用秦九韶算法来取模的，但是这里应该取模的是
，这里应该再复习一下欧拉定理，好像上次得到的那个结论有点问题，所以这里
，所以对1140取模即可，然后直接快速幂就出来了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { private: const int mod=1337; public: int superMod(vector<int> &b) { int count=0; for (int i=0;i<b.size();i++) count=((count*10+b[i])%1140); return count; } int qpow(int x,int y) { if (!y) return 1; if (y==1) return x%mod; int t=qpow(x,y/2); if (y&1) return t*t%mod*x%mod; else return t*t%mod; return 0; } int superPow(int a, vector<int>& b) { int y=superMod(b)+1140; return qpow(a%mod,y); } }; |
1011：在D天内送达包裹的能力
题目大意：求在D天内按照顺序装载货物的最小装载重量
直接二分答案然后判断，时间复杂度.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public: bool check(int x,vector<int> &weights,int D) { int count=1,sum=0; for (int i=0;i<weights.size();++i) { if (x<weights[i]) return false; if (sum+weights[i]<=x) sum+=weights[i]; else { ++count,sum=weights[i]; if (sum>x) ++count,sum=0; } } return count<=D; } int shipWithinDays(vector<int>& weights, int D) { int sum=0; for (int i=0;i<weights.size();++i) sum+=weights[i]; int l=1,r=sum; while (l<=r) { int mid=(l+r)>>1; if (check(mid,weights,D)) r=mid-1; else l=mid+1; } return r+1; } }; |
2021.4.27
50：Pow(x, n)
题目大意：如题
这个是浮点数的快速幂，需要注意的是n的范围是int，很容易爆int，所以直接把int换成long long
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
typedef long long LL; class Solution { private: LL y; public: double qpow(double x,LL n) { if (n==0) return 1; if (n==1) return x; double t=qpow(x,n/2); if (n&1) return t*t*x; else return t*t; } double myPow(double x, int n) { LL y=(LL)n; return y<0?1.0/qpow(x,-y):qpow(x,y); } }; |
397：整数替换
题目大意：奇数替换为n+1或n-1，偶数替换为n/2，求n=1时的最小替换次数
因为有n/2，所以复杂度肯定是
的，奇数替换n+1或者n-1需要dfs判断一下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#define inf 0x7fffffff typedef long long LL; class Solution { private: int sum,ans; public: void dfs(LL x) { if (x==1) return ans=min(ans,sum),void(); if (x&1) { ++sum,dfs(x+1),--sum; ++sum,dfs(x-1),--sum; } else ++sum,dfs(x/2),--sum; } int integerReplacement(int n) { ans=inf,dfs((LL)n); return ans; } }; |
总结：①范围在int的变量一定要换成long long，防止爆int
2021.4.28
462：最少移动次数使数组元素相等 II
题目大意：给一个序列，每次移动可以选一个元素+1或-1，求让序列所有数相等的最少移动次数
一开始写的二分，后来发现答案不是单调函数，就网上搜了一下三分的姿势然后写了三分，因为答案是单峰函数，然后根据两个mid的值大小关系判断即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
typedef long long LL; #define inf 0x7fffffff class Solution { private: int res; public: LL check(LL x,vector<int> &nums) { LL sum=0; for (int i=0;i<nums.size();++i) sum+=abs((LL)nums[i]-x); return sum; } int minMoves2(vector<int>& nums) { LL l=inf,r=-inf; for (int i=0;i<nums.size();++i) l=min(l,(LL)nums[i]),r=max(r,(LL)nums[i]); while (l<=r) { LL mid1=l+(r-l)/3,mid2=r-(r-l)/3; if (check(mid1,nums)<check(mid2,nums)) r=mid2-1; else l=mid1+1; } for (int i=0;i<nums.size();++i) res+=abs(nums[i]-(int)r); return res; } }; |
633：平方数之和
题目大意：求一个数能否表示为两个数的平方和的形式
直接
暴力判断即可
|
1 2 3 4 5 6 7 8 9 10 |
class Solution { public: bool judgeSquareSum(int c) { for (int i=0;i<=sqrt(c);++i) { int x=c-i*i; if ((int)sqrt(x)*(int)sqrt(x)==x) return true; } return false; } }; |
2021.5.2
310：最小高度树
题目大意：给出一棵树，求以哪个结点为根时树的深度最小
正解是树的直径，一开始我在想是树的重心，启发这个思路的原因是看到样例里面有一个或者两个结点，想到树的重心的性质是至多有两个重心，但是其实里面的一个样例已经能够hack掉这个想法了，深思了一下原因，树的重心是所有结点到该结点的距离之和最小，而不是深度最小，如果让深度最小应该是直径的中心才对，求树的直径只需要两遍dfs，具体证明网上有很多，这里就不详细证了，求完直径，在dfs的过程中记录一下每个结点的father，然后从直径的两个端点暴力往上找father即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#define N 20010 class Solution { private: int cnt,h[N],deep[N],P,Q,ans,father[N]; struct data { int to,next; }edge[N<<1]; bool flag[N]; vector<int>res; public: void add(int u,int v) { edge[++cnt]=(data){v,h[u]},h[u]=cnt,edge[++cnt]=(data){u,h[v]},h[v]=cnt; } void dfs(int x) { flag[x]=true; for (int i=h[x];i;i=edge[i].next) if (!flag[edge[i].to]) deep[edge[i].to]=deep[x]+1,father[edge[i].to]=x,dfs(edge[i].to); flag[x]=false; } vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { for (int i=0;i<edges.size();++i) add(edges[i][0]+1,edges[i][1]+1); dfs(1); for (int i=1;i<=n;++i) if (deep[i]>ans) ans=deep[i],P=i; memset(deep,0,sizeof(deep)),dfs(P),ans=0; for (int i=1;i<=n;++i) if (deep[i]>ans) ans=deep[i],Q=i; int count=0; if (n==1) res.push_back(0); while (Q!=P) { if (ans/2==0) res.push_back(Q-1); ++count,Q=father[Q]; if (ans&1) if (count==ans/2+1 || count==ans/2) res.push_back(Q-1); else; else if (count==ans/2) res.push_back(Q-1); } return res; } }; |
554：砖墙
题目大意：给出一系列砖的宽度，保证这些砖组成的每一行长度都相等，求在砖墙垂直划一道线所经过的最少砖数
很明显的一个性质是划线的时候只要是划线的这个位置前面是当前行砖的宽度和这道线就不会碰到当前行的砖，所以我们预处理出每行的砖的宽度前缀和，然后排序找一下出现次数最多的数有多少个，用行数减去这个数就是答案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { private: vector<int>sum; int ans,count,last; public: int |