头像

tea321000

SZU




在线 



tea321000
8小时前

题目描述

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数,随后玩家 2 继续从剩余数组任意一端拿取分数,然后玩家 1 拿,…… 。每次一个玩家只能拿取一个分数,分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组,预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

样例

输入:[1, 5, 2]
输出:False
解释:一开始,玩家1可以从1和2中进行选择。
如果他选择 2(或者 1 ),那么玩家 2 可以从 1(或者 2 )和 5 中进行选择。如果玩家 2 选择了 5 ,那么玩家 1 则只剩下 1(或者 2 )可选。
所以,玩家 1 的最终分数为 1 + 2 = 3,而玩家 2 为 5 。
因此,玩家 1 永远不会成为赢家,返回 False 。

算法1

(递归) $O(n^2)$

输入:数组
输出:先手玩家是否必胜

状态表示:
$f(i,j)$:集合,表示从i下标到j下标长度的数组中,先手玩家所能够获得的最大分数 - 右手玩家最大分数, 当大于0时,先手玩家胜
$i$: 下界,从$0$到$\lceil len/2 \rceil$
$j$: 上界,从$\lceil len/2 + 1 \rceil$到$\lceil len \rceil$
属性:分数

状态计算:
由于只能选择取最前或者最后的数,即两种选择,而且在对手取时,首先对手取的分会使我们的分数下降,因此是负的,另外取负号时可以把对我方最不利的选择,即max改成min(min-max游戏),因此在状态转移时可以加上负号,使得$max()$变成$min()$:
$$f(i, j) = max(-f(i+1, j)+f[i], -f(i, j-1)+f[j])$$

C++ 代码

class Solution {
public:
    int f(int i, int j, vector<int>& nums)
    {
        if(i==j)
            return nums[i];
        return max(-f(i+1, j, nums)+nums[i], -f(i, j-1, nums)+nums[j]);
    }
    bool PredictTheWinner(vector<int>& nums) {
        #ifdef _commet


        int i = 0, j = nums.size() - 1;
        return f(i, j, nums) >=0? true :false;


    }

};

算法2

(动态规划) $O(n^2)$

从递归解法可以看出,我们的$f[i][j]$从$f[i+1][j]$和$f[i][j-1]$进行转移,即矩阵下边和左边相邻的元素。因此,我们只要先将矩阵对角线上的元素(即$f[0][0]$到$f[n-1][n-1]$)先进行初始化,然后再递推计算上三角矩阵元素即可(当$j$小于$i$时不存在数组,下三角部分不需要进行计算)。

C++ 代码

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> f(n,vector<int>(n));
        for(int l = 1;l <= n;l++)
            for(int i = 0; i + l -1 < n; i++)
            {
                int j = i + l - 1;
                if (l == 1)
                    f[i][j] = nums[i];
                else
                {
                    f[i][j] = max(-f[i + 1][j] + nums[i], -f[i][j - 1] + nums[j]);
                }
            }
        return f[0][n - 1] >=0 ? true: false;

    }
};


活动打卡代码 LeetCode 486. 预测赢家

tea321000
8小时前
class Solution {
public:
    int f(int i, int j, vector<int>& nums)
    {
        if(i==j)
            return nums[i];
        return max(-f(i+1, j, nums)+nums[i], -f(i, j-1, nums)+nums[j]);
    }
    bool PredictTheWinner(vector<int>& nums) {
        #ifdef _commet
        输入:数组
        输出:先手玩家是否必胜

        状态表示:
        $f(i,j)$:集合,表示从i下标到j下标长度的数组中,先手玩家所能够获得的最大分数 - 右手玩家最大分数, 当大于0时,先手玩家胜
        $i$: 下界,从$0$到$\lceil len/2 \rceil$
        $j$: 上界,从$\lceil len/2 + 1 \rceil$到$\lceil len \rceil$
        属性:分数

        状态计算:
        由于只能选择取最前或者最后的数,即两种选择,而且在对手取时,首先对手取的分会使我们的分数下降,因此是负的,另外取负号时可以把对我方最不利的选择,即max改成min(min-max游戏),因此在状态转移时可以加上负号,使得max()变成min():
        $$f(i, j) = max(-f(i+1, j)+f[i], -f(i, j-1)+f[j])$$
        #endif

        int i = 0, j = nums.size() - 1;
        return f(i, j, nums) >=0? true :false;


    }

};



tea321000
10小时前

题目描述

你和你的朋友,两个人一起玩 Nim 游戏:

桌子上有一堆石头。
你们轮流进行自己的回合,你作为先手。
每一回合,轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数,来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢,返回 true;否则,返回 false 。

样例

输入:n = 4
输出:false 
解释:如果堆中有 4 块石头,那么你永远不会赢得比赛;
     因为无论你拿走 1 块、2 块 还是 3 块石头,最后一块石头总是会被你的朋友拿走。

算法1

(sg函数) $O(n)$

使用sg函数在数字较大时,容易爆栈

C++ 代码

class Solution {
public:
    unordered_map<int, int> f;
    int sg(int x)
    {
        if (f.count(x))
            return f[x];
        unordered_set<int> S;
        for(int i = 1; i <= 3; i++)
        {
            if(x >= i)
            {
                S.insert(sg(x - i));
            }
        }

        for (int i = 0; ; i++)
        {
            if (!S.count(i))
            {
                f[x] = i;
                return i;
            }
        }
    }
    bool canWinNim(int n) {
        return sg(n) == 0? false: true;
    }
};

算法2

(数学) $O(1)$

由于此题所做的操作为减1-3个石子,相当于可以取走模4后剩余的数,因此只要我方先取走模4后剩余的数则必胜,否则必败。

C++ 代码


class Solution {
public:
    bool canWinNim(int n) {
        return n%4?true:false;
    }
};


活动打卡代码 LeetCode 292. Nim 游戏

tea321000
10小时前
class Solution {
public:
    bool canWinNim(int n) {
        return n%4?true:false;
    }
};


活动打卡代码 AcWing 892. 台阶-Nim游戏

#include<iostream>
using namespace std;
int n, nim, tmp;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>tmp;
        if(i&1)  continue;
        nim^=tmp;
    }
    cout<<(nim==0?"No":"Yes")<<endl;
}


活动打卡代码 AcWing 891. Nim游戏

#include<iostream>
using namespace std;
int n;
int nim,tmp;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>tmp;
        nim^=tmp;
    }
    cout<<(nim==0?"No":"Yes")<<endl;

}



题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。

注意:如果 s 中存在这样的子串,我们保证它是唯一的答案。

样例

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"

算法1

(差值哈希) $O(n)$

此题跟LC438题如出一辙,可以使用匹配串和模式串字符种类的差值来做。但与LC438相比难度增大的一点在于,窗的长度不再是固定的,窗只要涵盖模式串的所有字符即可。但此题使用差值来做会导致条件判断等比较麻烦,调试也会比较慢。

C++ 代码

class Solution {
public:
    string minWindow(string s, string t) {
    #ifdef _commet
    输入:s匹配串 t模式串
    输出:s 中涵盖 t 所有字符的最小子串

    此题跟LC438题如出一辙,需要使用匹配串和模式串字符种类的差值来做。但与LC438相比难度增大的一点在于,窗的长度不再是固定的,窗只要涵盖模式串的所有字符即可。
    #endif
        unordered_map<char, int> diff;//键:字符种类 值:每种字符种类的出现次数的差
        string res="";
        for(auto &c : t)
            diff[c]++;
        int cnt = 0,tar = diff.size();
        for(int i = 0, j = 0; i<s.size(); i++)
        {
            //第i个元素入窗,当该元素种类在模式串里有时,该字符种类差值减1(由于涵盖关系,此处已经修改)。当入窗之后差值等于0,该种类匹配,计数+1
            if(diff.count(s[i]))//check 有没有s[i]这个key,有再操作
                if(!--diff[s[i]])
                    cnt++;
            //当j已经多余的时候(不存在key或者diff[s[j]]<0,即有多余的该字符),第j个元素可以出窗,当该元素种类在模式串里有时,才将该字符种类差值加1(由于涵盖关系,此处已经修改)。当出窗前差值为0,则出窗后种类将会不匹配,计数-1。由于窗长不再固定,因此需要使用while
            while (!diff.count(s[j]) || diff[s[j]] < 0)
            {
                if(diff.count(s[j]))//check 有没有s[j]这个key,有再操作
                    if(!diff[s[j]]++)
                        cnt--;
                if(j==s.size()-1) break;//遍历到s字符串末尾无法继续遍历 跳出循环
                j++;
            }

            if(cnt == tar)
                if (res.empty() || i - j + 1 < res.size())
                    res = s.substr(j, i - j + 1);
        }
        return res;
    }
};

算法2

(用匹配串和模式串两个哈希) $O(n)$

用匹配串和模式串两个哈希来做,虽然空间上会大一倍甚至更多(模式串长度小),但是可以有效避免hash.count()判断的问题,写起来会方便些

C++ 代码

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hs, ht;
        for (auto c: t) ht[c] ++ ;

        string res;
        int cnt = 0;
        for (int i = 0, j = 0; i < s.size(); i ++ ) {
            hs[s[i]] ++ ;
            if (hs[s[i]] <= ht[s[i]]) cnt ++ ;

            while (hs[s[j]] > ht[s[j]]) hs[s[j ++ ]] -- ;
            if (cnt == t.size()) {
                if (res.empty() || i - j + 1 < res.size())
                    res = s.substr(j, i - j + 1);
            }
        }

        return res;
    }
};


活动打卡代码 LeetCode 76. 最小覆盖子串

class Solution {
public:
    string minWindow(string s, string t) {
    #ifdef _commet
    输入:s匹配串 t模式串
    输出:s 中涵盖 t 所有字符的最小子串

    此题跟LC438题如出一辙,需要使用匹配串和模式串字符种类的差值来做。但与LC438相比难度增大的一点在于,窗的长度不再是固定的,窗只要涵盖模式串的所有字符即可。
    #endif
        unordered_map<char, int> diff;//键:字符种类 值:每种字符种类的出现次数的差
        string res="";
        for(auto &c : t)
            diff[c]++;
        int cnt = 0,tar = diff.size();
        for(int i = 0, j = 0; i<s.size(); i++)
        {
            //第i个元素入窗,当该元素种类在模式串里有时,该字符种类差值减1(由于涵盖关系,此处已经修改)。当入窗之后差值等于0,该种类匹配,计数+1
            if(diff.count(s[i]))//check 有没有s[i]这个key,有再操作
                if(!--diff[s[i]])
                    cnt++;
            //当j已经多余的时候(不存在key或者diff[s[j]]<0,即有多余的该字符),第j个元素可以出窗,当该元素种类在模式串里有时,才将该字符种类差值加1(由于涵盖关系,此处已经修改)。当出窗前差值为0,则出窗后种类将会不匹配,计数-1。由于窗长不再固定,因此需要使用while
            while (!diff.count(s[j]) || diff[s[j]] < 0)
            {
                if(diff.count(s[j]))//check 有没有s[j]这个key,有再操作
                    if(!diff[s[j]]++)
                        cnt--;
                if(j==s.size()-1) break;//遍历到s字符串末尾无法继续遍历 跳出循环
                j++;
            }

            if(cnt == tar)
                if (res.empty() || i - j + 1 < res.size())
                    res = s.substr(j, i - j + 1);
        }
        return res;
    }
};



class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int sum = 0, ans = INT_MAX, sz = nums.size();
        for(int i=0, j=0; i < sz; i++)
        {
            //第i个元素入窗之后
            sum += nums[i];
            //当sum大于目标值+nums[j]时,第j个元素可以出窗
            while (sum - nums[j] >= s)
            {
                sum -= nums[j];
                j++;
            }

            //还要判断一下此时是否真的大于等于s,因为一开始i小窗宽不够时会小于s
            if(sum>=s)
                ans=min(ans, i - j + 1); 
            // cout<<j<<" "<<i<<endl;
        }
        return ans==INT_MAX ? 0 : ans;
    }
};



class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> diff;//键:不同种类的字符 值:匹配串和模式串不同种类字符计数的差
        for(auto &c : p)//先对模式串进行字符种类计数
            diff[c]++;
        int sz=p.size();
        vector<int> ans;
        int cnt = 0, tar = diff.size();//当前有效的匹配字符种数 总共需要匹配的字符种数
        //注意这里tar是diff.size()而不是p.size(),因为p的不同字符种类可能重复(如aab)
        for(int i = 0, j = 0; i < s.size(); i++)
        {
            //第i个元素入窗,该元素的差值减1,当入窗后差值为0时,该种类匹配,种类计数+1
            if(!--diff[s[i]])   cnt++;
            //第j个元素出窗,该元素的差值加1,当出窗前差值为0时,该种类会变得不匹配,种类计数-1
            //由于此题中窗口的长度是固定的,为p.size(),因此j每次只会移动一位,用if即可
            //同理,也可以将j替换成i+p.size(),但为了模板统一、直观和不容易出错不这么做(容易漏掉前面一段的初始化)
            if(i-j+1>sz)
                if(!diff[s[j++]]++)
                    cnt--;
            if(cnt == tar)
                ans.push_back(j);
            // cout<<j<<" "<<i<<"cnt:"<<cnt<<"tar:"<<tar<<endl;
        }
        return ans;
    }
};