内容简介:今天参加了leetcode的周赛,算法比赛,要求速度比较快。有思路就立马启动,不会纠结是否有更好的方法或代码可读性。只要在算法复杂度数量级内,基本上是怎么实现快速就怎么来了。比赛时先看的第二题,一看题就有了思路,直接用的广度优先搜索,写完提交正确。再一看有人都做了3道题了,应该是职业选手了,要多像他们看齐。之后看第一题,发现直接用贪心就能做,写了个双重循环,一次过掉。
今天参加了leetcode的周赛,算法比赛,要求速度比较快。有思路就立马启动,不会纠结是否有更好的方法或代码可读性。只要在算法复杂度数量级内,基本上是怎么实现快速就怎么来了。
比赛时先看的第二题,一看题就有了思路,直接用的广度优先搜索,写完提交正确。再一看有人都做了3道题了,应该是职业选手了,要多像他们看齐。
之后看第一题,发现直接用贪心就能做,写了个双重循环,一次过掉。
第三题求最优连续子数组和,想到是动态规划。然后在处理代码细节上花了很长时间,中间提交还错了一次,在十一点半左右提交通过。
再看第四题,能想到是trie树和ac自动机,但是我手上没有现成代码,到比赛完也没有完成。
本次比赛题目偏简单,及时第四题如果经常做竞赛也很容易写。以后要多做些训练,把常用的代码整理下,否则比赛会比较耗时间。另外要多训练算法思维,一是在比赛时能够思路快。二是算法在工作中也比较重要,虽然很多时候都有封装好的现成函数,但是知道其中的原理,能够更高效地解决问题,对于新问题的思考也更全面更准确。
下面是今天比赛的详细解题。
今天比赛的地址 Weekly Contest 133 https://leetcode-cn.com/contest/weekly-contest-133
1. 两地调度(Two City Scheduling)
题号:1029
题目:两地调度(Two City Scheduling)
题意:2*N个人去A、B两地,每个地方都只有N个人去,每个人去A、B两地的费用分别给出,求总计最小费用。
思路:
方法一:
有最优策略,先把2N个人随意分成A、B两个集合,每个集合N个人。A集合去A地,B集合去B地。然后对于A集合中每个人ai,到B集合中遍历每个人bj,看是否能互换位置,让整体费用更低。如果有则换位置,没有检查下一个。全部换完则是最优解。
换的条件是ai去A的费用+bj去B的费用,要大于ai去B的费用+bj去A的费用。这样bj与ai互换整体费用会最低。
时间复杂度O(n^2)
class Solution { public: int twoCitySchedCost(vector<vector<int>>& costs) { vector<int> va; vector<int> vb; for(int i=0;i<costs.size();++i) { if(i%2==0) va.push_back(i); else vb.push_back(i); } for(int i=0;i<va.size();++i) { for(int j=0; j<vb.size();++j) { int aindex=va[i]; int bindex=vb[j]; int acost = costs[aindex][0]+costs[bindex][1]; int bcost = costs[aindex][1]+costs[bindex][0]; if(acost>bcost) { swap(va[i],vb[j]); } } } int sum = 0; for(auto i : va) { sum+=costs[i][0]; } for(auto i : vb) { sum+=costs[i][1]; } return sum; } };
方法二
把2N个人的费用排序,到B地比到A地超出差价大的人排在前面,最后让前N个人去,排在前面的人去A地更划算。整体费用最低。
时间复杂度O(nlogn)
方法三
动态规划,此题有最优子结构。用f[n][m]表示n个人,派m个人去A地,所花费的最小钱数。这时再来一个人,这个人有两种选择,一种是去A地,一种是去B地。
则更新
1. 如果去A地:f[n+1][m+1] = min(f[n+1][m+1], f[n][m]+costA);
2. 如果去B地:f[n+1][m] = min(f[n+1][m], f[n][m]+costB);
costA、costB表示这个人去A、B的花费。
2. 距离顺序排列矩阵单元格
题号:1030
题目:距离顺序排列矩阵单元格(Matrix Cells in Distance Order)
题意:给出矩阵的行列值,和一个坐标点r,输出所有矩阵坐标,按照每个点到r曼哈顿距离 排序 输出。
两个坐标点(r1,c1)(r2,c2)的曼哈顿距离是|r1 – r2| + |c1 – c2|。
思路:
方法一:直接求出每个点到给出坐标的距离,再排序,然后输出即可。
方法二:用广度优先搜索,每次搜索到的点依次输出即可。比方法一代码麻烦。
class Solution { public: vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) { vector<vector<int>> res; vector<vector<int>> visited(R, vector<int>(C, 0)); queue<pair<int, int>> q; q.push({r0,c0}); while(!q.empty()) { pair<int,int> p = q.front(); q.pop(); int i = p.first; int j = p.second; if(visited[i][j]==1) continue; visited[i][j] = 1; res.push_back({i,j}); int dx[]={-1,1,0,0}; int dy[]={0,0,-1,1}; for(int k=0;k<4;++k) { int x = dx[k]+i; int y = dy[k]+j; if(x>=0&&x<R&&y>=0&&y<C) { if(visited[x][y]==0) { q.push({x,y}); } } } } return res; } };
3. 两个非重叠子数组的最大和
题号:1031
题目:两个非重叠子数组的最大和(Maximum Sum of Two Non-Overlapping Subarrays)
题意:
给出非负整数数组 A ,返回两个非重叠(连续)子数组中元素的最大和,子数组的长度分别为 L 和 M。(这里需要澄清的是,长为 L 的子数组可以出现在长为 M 的子数组之前或之后。)
从形式上看,返回最大的 V,而 V = (A[i] + A[i+1] + … + A[i+L-1]) + (A[j] + A[j+1] + … + A[j+M-1]) 并满足下列条件之一:
0 <= i < i + L – 1 < j < j + M – 1 < A.length, 或 0 <= j < j + M – 1 < i < i + L – 1 < A.length.
思路:
按照题目的思路,把A数组从元素i开始,分割成两部分,A[0…i],A[i+1…n]。求出A[0…i]中连续子数组中长度为L、M的和的最大值maxl1,maxm1,再求出A[i+1…n]中连续子数组中长度为L和M的和最大值maxl2,maxm2,在第i个元素分割时找到的最大值是maxi=max((maxl1+maxm2),(maxm1+maxl2))。
那如何计算长度为L或M的连续子数组的和呢?假设要求的sum区间是L[k+1,k+2,…,k+L],则这个区间的值,可以用L[0,…k+L]的和减去L[0,…,k+1]的区间和。
class Solution { public: int getMaxSum(vector<int>& A, int len, vector<int>&v) { int i=0; int sum=0; int maxsum=0; for(i=0;i<len;++i) sum+=A[i]; v[len-1]=sum; maxsum = sum; for(i=len;i<A.size();++i) { sum=sum-A[i-len]+A[i]; maxsum=max(sum,maxsum); v[i]=maxsum; } return 0; } int maxSumTwoNoOverlap(vector<int>& A, int L, int M) { int n = A.size(); vector<int> B = A; reverse(B.begin(),B.end()); vector<int> L1(n,0); vector<int> L2(n,0); vector<int> M1(n,0); vector<int> M2(n,0); getMaxSum(A, L, L1); getMaxSum(B, M, M1); int sum1=0; for(int i = L-1;i<n-M;++i) { int x = i; int y = n-1-(i+1); sum1=max(sum1,L1[i]+M1[n-1-(i+1)]); } int sum2=0; int res = 0; getMaxSum(A, M, L2); getMaxSum(B, L, M2); for(int i = M-1;i<n-L;++i) { sum1=max(sum1,L2[i]+M2[n-1-(i+1)]); } res = max(sum1,sum2); return res; } };
4. 字符流
题号:1032
题目:字符流(Stream of Characters)
题意:给定一个单词表words,然后每次输入一个字母,假设地k次输入字母为a[k]。则a[i],a[i+1]…a[k]组成的单词(i>=1且i<=k),在单词表words中出现,输出true,否则输出false。
思路:
题目比较好理解,主要是根据words建立字典,由于都是小写字母,而且涉及到前缀的查询,用trie树是最好的数据结构。
对于每次输入字母a[k],首先查询a[k]是否匹配某个单词。然后把之前输入的前缀能查到的单词,和a[k]结合,再查询是否能匹配某个单词。如果完全匹配,则返回结果为true。在返回前,要把所有能匹配单词表中单词,或词表前缀的单词留下来,留着下一轮输入字母时匹配备用。
但是这里是有方法优化的,如果每次都重头匹配单词,会超时。优化的方法有三种,
一、把上次匹配到前缀的trie树节点指针存储起来,下次只匹配一次字母即可。
二、使用ac自动机进行多模式匹配。
三、trie树中存储倒序的字符串,然后把每次输入的字母都按顺序保存起来。按照倒序匹配,如果匹配到一个完整的单词,返回true;如果匹配到不存在的单词,则返回false;如果匹配的是某个前缀,继续往下匹配。
class TrieNode{ public: bool hasVal=false; vector<TrieNode*> children; TrieNode() : children(26,NULL){} }; class TrieTree{ public: TrieNode* root; TrieTree() { root = new TrieNode(); } int insert(string& word) { TrieNode* p = root; for(int i = 0; i < word.length(); ++i) { int n=word[i]-'a'; if(p->children[n]==NULL){ p->children[n]=new TrieNode(); } p=p->children[n]; } p->hasVal=true; return 0; } bool query_has_r_suffix(string& word) { TrieNode* p = root; for(int i=word.length()-1;i>=0;--i){ char ch = word[i]; int n=ch-'a'; if(p->children[n]==NULL){ return false; } p=p->children[n]; if(p->hasVal) return true; } return false; } }; class StreamChecker { TrieTree * tree =new TrieTree(); string suf_str; public: StreamChecker(vector<string>& words) { for(string w:words){ reverse(w.begin(),w.end()); tree->insert(w); } } bool query(char letter) { suf_str.push_back(letter); return tree->query_has_r_suffix(suf_str); } }; /** * Your StreamChecker object will be instantiated and called as such: * StreamChecker* obj = new StreamChecker(words); * bool param_1 = obj->query(letter); */
以上所述就是小编给大家介绍的《Leetcode 第133场周赛解题报告》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- Leetcode 第135场周赛解题报告
- Leetcode 第136场周赛解题报告
- Codeforces Round #530 (Div. 2) 解题报告
- Codeforces Round #538 (Div. 2) 解题报告
- The Cryptopals Crypto Challenges 解题报告(1)
- The Cryptopals Crypto Challenges 解题报告(2)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。