力扣-2029-石子游戏-‘屎山’代码

简介: 力扣-2029-石子游戏-‘屎山’代码

题目:

Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ,其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合,Alice 先手。每一回合,玩家需要从 stones 中移除任一石子。

  • 如果玩家移除石子后,导致 所有已移除石子 的价值 总和 可以被 3 整除,那么该玩家就 输掉游戏 。
  • 如果不满足上一条,且移除后没有任何剩余的石子,那么 Bob 将会直接获胜(即便是在 Alice 的回合)。

假设两位玩家均采用 最佳 决策。如果 Alice 获胜,返回 true ;如果 Bob 获胜,返回 false 。

示例 1:

输入:stones = [2,1]

输出:true

解释:游戏进行如下:

- 回合 1:Alice 可以移除任意一个石子。

- 回合 2:Bob 移除剩下的石子。

已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此,Bob 输,Alice 获胜。


示例 2:

输入:stones = [2]

输出:false

解释:Alice 会移除唯一一个石子,已移除石子的值总和为 2 。

由于所有石子都已移除,且值总和无法被 3 整除,Bob 获胜。


示例 3:

输入:stones = [5,1,2,4,3]

输出:false

解释:Bob 总会获胜。其中一种可能的游戏进行方式如下:

- 回合 1:Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。

- 回合 2:Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。

- 回合 3:Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。

- 回合 4:Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.

- 回合 5:Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.

Alice 输掉游戏,因为已移除石子值总和(15)可以被 3 整除,Bob 获胜。提示:

  • 1 <= stones.length <= 105
  • 1 <= stones[i] <= 104

记录第一次写出来屎山代码,前后长达一个小时,中间不断的调试,改bug,碰壁就更改条件。

终于,功夫不负有心人,也是被我拿下了。下面请欣赏我的‘屎山’代码。

代码:

class Solution:
    def stoneGameIX(self,stones: List[int]) -> bool:
        n=len(stones)
        if n==1: return False
        ls1,ls2,ls3=[],[],[]
        for i in stones:
            if i%3==1: ls1.append(i)
            elif i%3==2: ls2.append(i)
            else: ls3.append(i)
        # print(ls1,ls2,ls3)
        flag=True
        a,b,c=len(ls1),len(ls2),len(ls3)
        # print(a,b,c)
        if a>=1:
            res=c+1  # 1 6 6 7  16 6 7 
            a-=1
            while a and b:
                a-=1
                b-=1
                c=0
                res+=2
            if a and not b :
                a-=1
                res+=1
            if c!=0 and c%2==1:
                c=0
            if res%2==0: flag=False # 1 1 1 
            # if res%2==0 and a: 
            #     # print(555)
            #     flag=True  # 30 26 26 52  82 
            elif res%2==1 and a==0 and b==0: 
                # print(77)
                flag=False
            if b==0 and c and (a+c)%2==0: 
                print(55)  # 1 7 6 6 1 2 0   1 1 1 1 
                flag=False
        else: flag=False
        if flag==True: return flag
        a,b,c=len(ls1),len(ls2),len(ls3)
        if b>=1:
            # print(666)
            res=c+1    
            b-=1
            while a and b:
                b-=1
                a-=1
                res+=2 # 6  2   2  1 --6--  2    1 2 1 2
            if b and not a :
                b-=1
                res+=1
            # if res%2==0 : 
            #     # print(b)
            #     # print(555)
            #     flag=False
            if res%2==1 and (a or b):  # 30 25 25 80  1  25 25 50 80 1   2  
                #print('keyi')     #1 1 2  1 2  26  26 1  
                flag=True
        else: flag=False
        return flag
a=Solution()
b=a.stoneGameIX(stones=[3,1,1,1])
print(b) 

代码长达60行,但是优秀的题解仅需短短几行,哈哈哈。也算是不撞南墙不回头,能解出来就硬着头皮往下写了。好在写出来了,感觉挺有意义的~

相关文章
|
1月前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
22天前
|
算法
力扣经典150题第三十八题:生命游戏
力扣经典150题第三十八题:生命游戏
10 0
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
1月前
|
算法 机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
【经典LeetCode算法题目专栏分类】【第5期】贪心算法:分发饼干、跳跃游戏、模拟行走机器人
|
1月前
|
存储 算法 数据挖掘
力扣174题动态规划:地下城游戏(含模拟面试)
力扣174题动态规划:地下城游戏(含模拟面试)
|
1月前
|
SQL 算法 数据可视化
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】
|
2月前
|
算法
leetcode代码记录(全排列 II
leetcode代码记录(全排列 II
27 4
|
2月前
leetcode代码记录(最长回文子串
leetcode代码记录(最长回文子串
24 2
|
2月前
|
算法
leetcode代码记录(全排列
leetcode代码记录(全排列
23 1
|
2月前
|
索引
leetcode代码记录(Z 字形变换
leetcode代码记录(Z 字形变换
24 1