Leetcode 第133场周赛解题报告

今天参加了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);
 */