Leetcode 第133场周赛解题报告
比赛时先看的第二题，一看题就有了思路，直接用的广度优先搜索，写完提交正确。再一看有人都做了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>& costs) {
vector va;
vector 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; jbcost)
{
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> allCellsDistOrder(int R, int C, int r0, int c0) {
vector<vector> res;
vector<vector> visited(R, vector(C, 0));
queue<pair> q;
q.push({r0,c0});
while(!q.empty())
{
pair 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=0&&x=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& A, int len, vector&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& A, int L, int M) {
int n = A.size();
vector B = A;
reverse(B.begin(),B.end());
vector L1(n,0);
vector L2(n,0);
vector M1(n,0);
vector 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 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 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& 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);
*/
About The Author
maynard
懒散，不想无聊