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

转载请注明来源:Leetcode 第133场周赛解题报告
欢迎收听公众号

发表评论

电子邮件地址不会被公开。 必填项已用*标注