Leetcode 第137场周赛解题报告

Leetcode 第137场周赛解题报告

今天的比赛的题目相对来说比较「直白」,不像前几周都是一些特定的算法,如果你没学过不可能想出来。

做了这些周,对leetcode比赛的题目也发现了一些「规律」。 一般前两道题都很「简单」,只要有想法,直接敲代码就能解出来。更多考察的是结果是否正确,速度其次。

后两道题有些难度 ,不同场次难度不一样,也可能和不同人的水平感受不同。但是肯定比前两道要难。

一般在做后两道题的时候,只要复杂度是对的,一些细节也不用考虑太多。例如数组开的空间大小,一些线性的提前剪枝判断,写不写都可以过。最主要的是复杂度是同一个量级的。

相信leetcode这么设计是为了「人性化」,让选手更关注比赛题目核心,能够在一个半小时内完成比赛题目。

总之leetcode的比赛还是很人性化,很注重主要考点,不纠结于细节。利用这些特性,可以在比赛中排除一些错误想法。

下面是详细的题解和思考。


比赛的地址 Weekly Contest 137

https://leetcode-cn.com/contest/weekly-contest-137

1. 最后一块石头的重量

题目:

最后一块石头的重量(Last Stone Weight)

地址:

https://leetcode-cn.com/contest/weekly-contest-137/problems/last-stone-weight/

题意:

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出两块最重的石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0。

思路:

一个数组,每次把最大的两个数拿出来相减,然后把绝对值放回原数组。一直重复到最后只剩下一个元素,输出即可。

典型的模拟题,按照题目的意思写即可。可以用堆来实现,每次拿堆顶的两个最大元素。

由于是第一题,每次都排序一遍,也能通过。不过在日常工程中,还是老老实实用堆来实现吧。

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue< int > q;
        for(auto &stone : stones)
        {
            q.push(stone);
        }
        while(q.size()>1)
        {
            int x = q.top();
            q.pop();
            int y = q.top();
            q.pop();
            int z = abs(x-y);
            q.push(z);
        }
        return q.top();
    }
};

2. 删除字符串中的所有相邻重复项

题目:

删除字符串中的所有相邻重复项(Remove All Adjacent Duplicates In String)

地址:

https://leetcode-cn.com/contest/weekly-contest-137/problems/remove-all-adjacent-duplicates-in-string/

题意:

给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

思路:

类似于游戏「爱消除」,相同的两个字母抵消掉,形成的新字符串再接着抵消,直到稳定为止。

用栈来实现,遍历字符串的每个字符。如果栈为空,则插入字符,否则比较字符和栈顶元素,相同则弹出栈顶元素,不同则压栈。

最后输出栈内的字符串即可。

代码:

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for(auto ch : S)
        {
            if(st.empty())
            {
                st.push(ch);
            }
            else
            {
                if(st.top()==ch)
                {
                    st.pop();
                }
                else
                {
                    st.push(ch);
                }
            }
        }
        string res;
        while(!st.empty())
        {
            res.push_back(st.top());
            st.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

3. 最长字符串链

题目:

最长字符串链(Longest String Chain)

地址:

https://leetcode-cn.com/contest/weekly-contest-137/problems/longest-string-chain/

题意:

给出一个单词列表,其中每个单词都由小写英文字母组成。

如果我们可以在 word1 的任何地方添加一个字母使其变成 word2,那么我们认为 word1 是 word2 的前身。例如,”abc” 是 “abac” 的前身。

词链是单词 [word_1, word_2, …, word_k] 组成的序列,k >= 1,其中 word_1 是 word_2 的前身,word_2 是 word_3 的前身,依此类推。

从给定单词列表 words 中选择单词组成词链,返回词链的最长可能长度。

思路:

这道题本质是图算法。

分两步解:

第一步先构造出每个单词之间的关系,判断任意两个单词是为前身后继关系。构造完关系就能画出了图。

第二步就是求解这个图中最长路径。由于是单向有向图,而且没有环。

构造一个集合,每次给集合放入新的点A,都判断集合中其他的点到该点的距离,取最大值为集合内部到新点A的最大距离L。下次再加入新的点A1,如果A和A1连通,则集合到A1的距离为L+1。

由于终点有多个,最后要遍历所有点的最长距离。

其实这道题的思想和Dijkstra算法是一样的。

代码:

class Solution {
public:
    bool canChange(string& s1, string& s2)
    {
        int len1 = s1.length();
        int len2 = s2.length();
        if(len1+1!=len2)
            return false;
        int i=0;
        int j=0;
        while(j<len2)
        {
            if(s1[i]==s2[j])
            {
                ++i;
                ++j;
            }
            else
            {
                ++j;
                if(j-i>1)
                {
                    return false;
                }        
            }
        }
        return true;
    }
    int longestStrChain(vector<string>& words) {
        int n = words.size();
        vector<vector<int>> g(n, vector<int>(n, 0));
        sort(words.begin(), words.end(), [](string& w1, string& w2)
             {
                 return w1.length()<w2.length();
             }
            );
        for(int i = 0; i < n; ++i)
        {
            for(int j = i+1; j < n; ++j)
            {
                if(canChange(words[i], words[j]))
                {
                    g[i][j] = 1;
                }
            }
        }
        vector<int> lcnt(n, 1);
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<i;++j)
            {
                if(g[j][i])
                {
                    int tmp = lcnt[j]+1;
                    lcnt[i] = max(tmp, lcnt[i]);
                }
            }
        }
        return *max_element(lcnt.begin(), lcnt.end());
    }
};

4. 最后一块石头的重量 II

题目:

最后一块石头的重量 II(Last Stone Weight II)

地址:

https://leetcode-cn.com/contest/weekly-contest-137/problems/last-stone-weight-ii/

题意:

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。

思路:

和第一题的题意只有一句差别,就是每次拿石头是「任意」的。问最后能消掉剩余的最小值是多少。

一般最开始可能想到用贪心,但实际上没有这种算法的。

由于石头碎掉之后还能放回去,类似于把石头分成两堆来看。只要依次拿两堆的石头互相粉碎,最后剩下的就是最小整数。

最多有100个石头,每个石头最多300的重量。所以两个集合最大的差值不会超过30000。

用数组构造结果。

在加入第n个石头重量为m时,查找n-1个石头能够组成的两堆石头的差值的绝对值为diff。

该石头两个选择,放入多的堆,则差值更大,为diff+m;
放入小的堆,则差值为|diff-m|。这时更新n个石头能组成的所有重量。

最后输出最后一个石头能组成的最小重量即可。

代码:

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int diff[101][30001]={0};
        int sum = 0;
        int n = stones.size();
        for(int i=0;i<n;++i)
        {
            sum+=stones[i];
        }
        diff[0][stones[0]] = 1;
        for(int i=1;i<n;++i)
        {
            for(int j=0;j<=sum;++j)
            { 
                if(diff[i-1][j])
                {
                    diff[i][j+stones[i]] = 1;
                    diff[i][abs(j-stones[i])] = 1;
                }
            }
        }
        for(int i = 0; i <= sum; ++i)
        {
            if(diff[n-1][i])
            {
                return i;
            }
        }
        return 0;
    }
};

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

发表评论

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