当前位置: 首页 > >

【leetcode_week137】最后一块石头的重量_最长字符串链等

发布时间:

没啥长进,只AC了前两道签到题,还做的非常慢,中间还出错了很多次。



最后一块石头的重量删除字符串中的所有相邻重复项最长字符串链最后一块石头的重量 II

leetcode第137场周赛赛题地址: https://leetcode-cn.com/contest/weekly-contest-137



最后一块石头的重量

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


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


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


提示:


1 <= stones.length <= 30
1 <= stones[i] <= 1000



思路和参赛代码

这题没有想到什么捷径,于是就很简单地按照步骤一步步做,排序后每次取两块最重的进行操作,看最后剩下的石头重量。代码如下:


class Solution {
public:
bool cmp(const int& l, const int& r){
return l > r;
}

int lastStoneWeight(vector& stones) {
vector::iterator it1 = stones.begin();
vector::iterator it2 = stones.begin()+1;
int ans = 0;

while (!stones.empty()) {
sort(stones.begin(), stones.end(), greater());

if (stones.size() == 1) {
ans = stones[0];
break;
}
else if (stones.size() == 0) {
ans = 0;
break;
}
else {
vector::iterator it1 = stones.begin();

if (stones[0] == stones[1]) {
stones.erase(it1);
vector::iterator it2 = stones.begin();
stones.erase(it2);
}
else {
stones[0] -= stones[1];
vector::iterator it2 = ++it1;
stones.erase(it2);
}
}
}
return ans;
}
};

别人的解答

我每次参加周赛感觉都太急,代码很繁很难看。依旧还是需要向大神学*。


class Solution {
public:
priority_queue H;
int lastStoneWeight(vector& stones) {
int n=stones.size(),i,j;
for(i=0;i while(!H.empty())
{
i=H.top();
H.pop();
if(H.empty())return i;
j=H.top();
H.pop();
i-=j;
if(i)H.push(i);
}
return 0;
}
};

还有priority_queue这种方便的东西,我还傻傻地每次都排序。



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

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


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


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


示例:
输入:“abbaca”
输出:“ca”
解释: 例如,在 “abbaca” 中,我们可以删除 “bb”,由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”,其中又只有 "aa"可以执行重复项删除操作,所以最后的字符串为 “ca”。



思路和参赛代码

这题也是想的很简单,直接遍历,碰到两个一样的,就向两边扩散,把前后一样的也一并去除。


class Solution {
public:
string removeDuplicates(string S) {
for (int i = 0; !S.empty() && i < S.length()-1; ) {
if (S[i] == S[i+1]) {

int j = 1;
while (i-j >= 0 && i+1+j < S.length() && S[i-j] == S[i+j+1]) {
j++;
}
i = i-j+1;
S.erase(i, j*2);
}
else {
i++;
}
}
return S;
}
};

别人的解答

赛后也和同学讨论过这道题,说是可以直接用栈,一想确实很有道理,比我的时间复杂度还要低一些,少了一些比较次数。我看别人的解答也是这个思路,不过没用栈,直接新开了一个string


class Solution {
public:
string removeDuplicates(string S) {
string ans;
int n=S.size(),i;
for(i=0;i else ans.pop_back();
return ans;
}
};


最长字符串链


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


如果我们可以在 word1 的任何地方添加一个字母使其变成 word2,那么我们认为 word1 是 word2 的前身。例如,"abc"是 “abac” 的前身。
词链是单词 [word_1, word_2, …, word_k] 组成的序列,k >= 1,其中 word_1 是 word_2的前身,word_2 是 word_3 的前身,依此类推。




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


示例:
输入:[“a”,“b”,“ba”,“bca”,“bda”,“bdca”]
输出:4
解释:最长单词链之一为"a",“ba”,“bda”,“bdca”。


提示:
1 <= words.length <= 1000
1 <= words[i].length <= 16 words[i]
仅由小写英文字母组成。



思路

比赛的时候倒是有想过根据每个字符串的长度,一步步动态规划来慢慢找到最长字符串链,但是,没有做出来。


补一个看了同学的java代码之后写的c++:【但是,超时了,尴尬。。。下次再改改】


class Solution {
public:
static bool cmp(string &a, string &b) {
return a.length() < b.length();
}

static bool IsChild(string tail, string i) {
int lent = tail.length();
int leni = i.length();

if (lent != leni-1) {
return false;
}

int ii = 0, jj = 0;

for (; ii < leni && jj < lent; ) {
if (tail[jj] != i[ii]) {
ii++;

}
else{
ii++;
jj++;
}
}
if (jj == lent) {
return true;
}
else {
return false;
}
}

int longestStrChain(vector& words) {
sort(words.begin(), words.end(), cmp);
int len = words.size();

int dp[1000];
memset(dp, -1, sizeof(dp));

for (int i = 0; i < len; i++) {
int tail = i-1;
int max = -1;

while(tail >= 0) {
if (IsChild(words[tail], words[i])) {
if (dp[tail] > max) {
max = dp[tail];
}
}
tail--;
}
dp[i] = (max==-1)?1:max+1;
}
sort(dp, dp+len);
return dp[len-1];
}
};

别人的解答

看到有别人的解答 http://www.cnblogs.com/owenandhisfriends/p/10890627.html 是转化成图来做的,思路感觉挺不错。



最后一块石头的重量 II

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


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


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

示例:


输入:[2,7,4,1,8,1]
输出:1
解释: 组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1], 组合 7 和8,得到 1,所以数组转化为 [2,1,1,1], 组合 2 和 1,得到 1,所以数组转化为 [1,1,1], 组合 1 和 1,得到0,所以数组转化为 [1],这就是最优值。


提示:
1 <= stones.length <= 30
1 <= stones[i] <= 1000



思路
原来是想贪心,先把差值最大的给减出来,然后再找差值最大的,后来发现并不对。也曾想过把问题转换为添加“+”和“-”来求取最小值的动态规划问题,但是,最终绕晕了,感觉好像也不好做。

没有做出来。


别人的解答

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


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


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


详情可见 http://www.cnblogs.com/owenandhisfriends/p/10890627.html



友情链接: