# Leetcode 第133场周赛解题报告

## 1. 两地调度(Two City Scheduling)

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;
}
};

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. 距离顺序排列矩阵单元格

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. 两个非重叠子数组的最大和

0 <= i < i + L – 1 < j < j + M – 1 < A.length, 或 0 <= j < j + M – 1 < i < i + L – 1 < A.length.

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. 字符流

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);
*/