草庐IT

[Leetcode464]我能赢吗？——状态压缩+dfs

echoqiqi 2023-03-28 原文

1.题目

在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过  100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。

示例 1：

输入：maxChoosableInteger = 10, desiredTotal = 11
输出：false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

示例 2:

输入：maxChoosableInteger = 10, desiredTotal = 0
输出：true

示例 3:

输入：maxChoosableInteger = 10, desiredTotal = 1
输出：true

 

提示:

  • 1 <= maxChoosableInteger <= 20
  • 0 <= desiredTotal <= 300

2.思路

这道题数据范围比较小，可以想到是状态压缩的情况，但是状态十分复杂，我是参考题解想的。一个数拿回不能放回，即只能使用一次，因此需要使用一个数据结构记录状态，C++和Java都可以使用Map作为记录。状态就是当前这个数有没有使用，使用的话这一位就为1；如100是3。第i位为1表示i被使用。

如果是先手必输的话 应该是 所有情况都是后手必胜；如果是先手必胜的话 是存在一种情况是后手必输

3.代码

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
       if(((1+maxChoosableInteger)*maxChoosableInteger*0.5)<desiredTotal)
            return false;
        return dfs(maxChoosableInteger,0,desiredTotal,0);
    }
    bool dfs(int maxChoosableInteger, int userNumbers, int desiredTotal, int currentTotals)
    {
        if(memory.count(userNumbers)==0)
        {
            bool res=false;
            for(int i=0;i<maxChoosableInteger;i++)
            {
                int temp=((userNumbers>>i)&1);
                if( temp==0)
                {
                    int sum=i+1+currentTotals;
                    if(sum>=desiredTotal)
                    {
                        res=true;
                        break;
                    }
                    //判断对方是否输
                    int x=userNumbers |(1<<i);
                    int total=currentTotals+i+1;
                    if(!dfs(maxChoosableInteger,x,desiredTotal,total))
                    {
                        res=true;
                        break;
                    }
                }
            }
            memory.insert({userNumbers,res});
        }
        return memory.find(userNumbers)->second;
    }
     map<int,bool> memory;
};

 

mdashLeetcodemaxChoosableIntegercodedesiredTotal算法与数据结构

有关[Leetcode464]我能赢吗？——状态压缩+dfs的更多相关文章

  1. ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2

    我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看ruby​​zip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d

  2. ruby - 在 Ruby 程序执行时阻止 Windows 7 PC 进入休眠状态 - 2

    我需要在客户计算机上运行Ruby应用程序。通常需要几天才能完成(复制大备份文件)。问题是如果启用sleep，它会中断应用程序。否则，计算机将持续运行数周，直到我下次访问为止。有什么方法可以防止执行期间休眠并让Windows在执行后休眠吗？欢迎任何疯狂的想法;-) 最佳答案 Here建议使用SetThreadExecutionStateWinAPI函数，使应用程序能够通知系统它正在使用中，从而防止系统在应用程序运行时进入休眠状态或关闭显示。像这样的东西:require'Win32API'ES_AWAYMODE_REQUIRED=0x0

  3. ruby-on-rails - 跳过状态机方法的所有验证 - 2

    当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested

  4. ruby - 字符串文字中的转义状态作为 `String#tr` 的参数 - 2

    对于作为String#tr参数的单引号字符串文字中反斜杠的转义状态，我觉得有些神秘。你能解释一下下面三个例子之间的对比吗？我特别不明白第二个。为了避免复杂化，我在这里使用了'd'，在双引号中转义时不会改变含义("\d"="d")。'\\'.tr('\\','x')#=>"x"'\\'.tr('\\d','x')#=>"\\"'\\'.tr('\\\d','x')#=>"x" 最佳答案 在tr中转义tr的第一个参数非常类似于正则表达式中的括号字符分组。您可以在表达式的开头使用^来否定匹配(替换任何不匹配的内容)并使用例如a-f来匹配一

  5. ruby - Net::HTTP 获取源代码和状态 - 2

    我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur

  6. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  7. ruby-on-rails - 为模型创建状态属性 - 2

    我想为我的Task模型创建一个status属性，该属性将按以下顺序指示它在三部分进度中的位置:打开=>进行中=>完成。它的工作方式类似于亚马逊包裹的交付方式:已订购=>已发货=>已交付。我想知道设置此属性的最佳方法是什么。我可能是错的，但创建三个独立的bool属性似乎有点多余。实现此目标的最佳方法是什么？ 最佳答案 Rails4有一个内置的enummacro.它使用单个整数列并映射到键列表。classOrderenumstatus:[:ordered,:shipped,:delivered]end状态映射如下:{ordered:0,

  8. ruby - Ruby 的压缩库？ - 2

    是否有任何可用于Ruby的开源压缩/解压库？有没有人实现过LZW？或者，是否有任何使用压缩组件的开源库可以提取出来独立使用？编辑——感谢您的回答!我应该提到我必须压缩的是只驻留在数据库中的长字符串(我不会压缩文件)。此外，如果可以执行此操作的任何库都具有用于客户端压缩/分解的等效JavaScript实现，那将是理想的，因为这将用于Web应用程序。 最佳答案 您会在rubystdlib下找到所有已交付的ruby​​库的一个很好的列表.我会使用zlib库，它是开放的，无处不在，您会发现几乎所有语言的库!

  9. ruby - 是否可以在不实际发送或读取数据的情况下查明 ruby​​ 套接字是否处于 ESTABLISHED 或 CLOSE_WAIT 状态？ - 2

    s=Socket.new(Socket::AF_INET,Socket::SOCK_STREAM,0)s.connect(Socket.pack_sockaddr_in('port','hostname'))ssl=OpenSSL::SSL::SSLSocket.new(s,sslcert)ssl.connect从这里开始，如果ssl连接和底层套接字仍然是ESTABLISHED，或者它是否在默认值7200之后进入CLOSE_WAIT，我想检查一个线程几秒钟甚至更糟的是在实际上不需要.write()或.read()的情况下关闭。是用select()、IO.select()还是其他方法完成

  10. ruby - 在 ruby​​ 中生成一个进程，捕获 stdout，stderr，获取退出状态 - 2

    我想从ruby​​rake脚本运行一个可执行文件，比如foo.exe我希望将foo.exe的STDOUT和STDERR输出直接写入我正在运行rake任务的控制台.当进程完成时，我想将退出代码捕获到一个变量中。我如何实现这一目标？我一直在玩backticks、process.spawn、system但我无法获得我想要的所有行为，只有部分更新:我在Windows上，在标准命令提示符下，而不是cygwin 最佳答案 system获取您想要的STDOUT行为。它还返回true作为零退出代码，这可能很有用。$?填充了有关最后一次system调

随机推荐