1046. 最后一块石头的重量

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。
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000

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

数据量很小，每次都重新排序也能通过。不过也可以用堆来实现，每次拿堆顶的两个最大元素。

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) 
    {
        while(stones.size()>1)
        {
            sort(stones.begin(),stones.end());
            if(stones[stones.size()-1]==stones[stones.size()-2]) 
            {
                stones.pop_back();
                stones.pop_back();
            }
            else
            {
                stones[stones.size()-2]=stones[stones.size()-1]-stones[stones.size()-2];
                stones.pop_back();
            }
        }
        if(stones.size()) return stones[0];
        else return 0;
    }
};

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

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","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 "a","ba","bda","bdca"。

对字符串遍历，相邻的两个相同字母抵消掉，i前移一位再接着抵消，直到遍历结束。

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

class Solution {
public:
    string removeDuplicates(string S) 
    {
        string str="";
        for(int i=0;i<S.length()-1;)
        {
            if(S[i]==S[i+1])
            {
                if(S.length()==2) return str;
                S.erase(i,2);
                if(i>0) i--;
            }
            else i++;
        }
        return S;
    }
};

1048. 最长字符串链

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","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 "a","ba","bda","bdca"。

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

由题可得出，若word1 是 word2 的前身，则word1长度 = word2长度-1，所以从长度为n的单词向长度为n+1的单词递推就行，

为了简单，我将所有单词按长度排序，按最长递增子序列的方法来做
结果由于时间复杂度O(n²)，一开始时间超限，
我又设了个数组num，在num的对应引索位储存对应长度单词的开始引索，对两个双重循环的条件加以限制，就ac了

class Solution {
public:
    bool ispredecessor(string s1,string s2)
    {
        int n=s1.length();
        if (s2.length() != n + 1) return false;
        int i=0;
        for(;i<n;i++) if(s1[i]!=s2[i]) break;
        for(i;i<n;i++) if(s1[i]!=s2[i+1]) return false;
        return true;
    }

    static bool cmp(string s1,string s2) 
    {
        return s1.length() < s2.length();
    }
    bool vis[1005][1005];
    int dp[1005];
    int num[20];
    int longestStrChain(vector<string>& words) 
    {
        int n=words.size(),ans=1;
        sort(words.begin(),words.end(),cmp);
        // for(int i=0;i<n;i++) cout<<words[i]<<endl;
        memset(num,-1,sizeof(num));
        int l=words[0].length(),r=words[n-1].length();
        num[l]=num[0]=0;
        num[r+1]=n;
        for(int i=1;i<n;i++)  
        {
            if(words[i].length()!=words[i-1].length())
            {
                for(int j=words[i-1].length()+1;j<=words[i].length();j++) num[j]=i;
            }
        }
        for(int i=0;i<num[r];i++)  
        {
            
            for(int j=num[words[i].length()+1];j<num[words[i].length()+2];j++)
            {
                if(ispredecessor(words[i],words[j])) vis[i][j]=true;
            }
        }
        int k=0;
        for(int i=0;i<n;i++)
        {
            dp[i]=1;
            for(int j=0;j<num[words[i].length()];j++) 
                if(vis[j][i]) dp[i]=max(dp[i],dp[j]+1);
            // if(dp[i]==11) cout<<words[i]<<" ";
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};

1049. 最后一块石头的重量 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。

示例：
输入：[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

和第一题的区别在于每次任意取两块石头，求最后一块石头最小的可能值

没想到怎么做，网上看到的解法是将原题等价为：将石头分为两组（不一定等大小），求该两组石头权值之差最小值
https://www.zhihu.com/question/325104725
可以用动态规划做，对这堆石头遍历，第n个石头只有两种结果，放入多的那堆，差值为ans+stones[n]；放入少的那堆，差值为|ans-stones[n]|

class Solution {
public:
    int dp[30][15005];
    
    int lastStoneWeightII(vector<int>& stones) 
    {
        int n=stones.size();
        dp[0][stones[0]]=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<=15000;j++)
            {
                if(dp[i-1][j])
                {
                    // cout<<i<<" "<<j<<" "<<endl;
                    dp[i][abs(j-stones[i])]=1;
                    dp[i][stones[i]+j]=1;
                }
            }
        }
        for(int i=0;i<=15000;i++) if(dp[n-1][i]) return i;
        return 0;
            
        
    }
};