分享236个单周活动,力扣,单周赛,题目

发表时间:2021-05-11

5727.找出游戏的获胜者

https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/

难度:中等

题目:

共有 n 名小伙伴一起做游戏。小伙伴们围成一圈,按 顺时针顺序 从 1 到 n 编号。确切地说,从第 i 名小伙伴顺时针移动一位会到达第 (i+1. 名小伙伴的位置,其中 1 <= i < n ,从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。

游戏遵循如下规则:

从第 1 名小伙伴所在位置 开始 。
沿着顺时针方向数 k 名小伙伴,计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数,一些小伙伴可能会被数过不止一次。
你数到的最后一名小伙伴需要离开圈子,并视作输掉游戏。
如果圈子中仍然有不止一名小伙伴,从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始,回到步骤 2 继续执行。
否则,圈子中最后一名小伙伴赢得游戏。
给你参与游戏的小伙伴总数 n ,和一个整数 k ,返回游戏的获胜者。

示例:

示例 1:

输入:n = 5, k = 2

输出:3

解释:
游戏运行步骤如下:

  1. 从小伙伴 1 开始。
  2. 顺时针数 2 名小伙伴,也就是小伙伴 1 和 2 。
  3. 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。
  4. 顺时针数 2 名小伙伴,也就是小伙伴 3 和 4 。
  5. 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。
  6. 顺时针数 2 名小伙伴,也就是小伙伴 5 和 1 。
  7. 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。
  8. 顺时针数 2 名小伙伴,也就是小伙伴 3 和 5 。
  9. 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。

示例 2:

输入:n = 6, k = 5

输出:1

解释:
小伙伴离开圈子的顺序:5、4、6、2、3 。小伙伴 1 是游戏的获胜者。

分析

这是一道标准的约瑟夫环问题,类似的题目很多,比如剑指offer中有一道小朋友们的游戏与此题就如出一辙。大家找个链表画下题目就迎刃而解了,类似斐波那契数列一样,了解公式直接解题。

解题:

class Solution:
    def findTheWinner(self, n, k):
        if n == 1:
            return 1
        val = 0
        for i in range(2, n + 1):
            cur = (val + k) % i
            val = cur
        return val + 1

5728.最少侧跳次数

https://leetcode-cn.com/problems/minimum-sideway-jumps/

难度:中等

题目:

给你一个长度为. n. 的. 3 跑道道路. ,它总共包含. n + 1. 个. 点. ,编号为. 0. 到. n. 。一只青蛙从. 0. 号点第二条跑道. 出发. ,它想要跳到点. n. 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1. 的数组. obstacles. ,其中. obstacles[i]. (取值范围从 0 到 3)表示在点 i. 处的. obstacles[i]. 跑道上有一个障碍。如果. obstacles[i] == 0. ,那么点. i. 处没有障碍。任何一个点的三条跑道中. 最多有一个. 障碍。

比方说,如果. obstacles[2] == 1. ,那么说明在点 2 处跑道 1 有障碍。
这只青蛙从点 i. 跳到点 i + 1. 且跑道不变的前提是点 i + 1. 的同一跑道上没有障碍。为了躲避障碍,这只青蛙也可以在. 同一个. 点处. 侧跳. 到 另外一条. 跑道(这两条跑道可以不相邻),但前提是跳过去的跑道该点处没有障碍。

比方说,这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
这只青蛙从点 0 处跑道 2. 出发,并想到达点 n. 处的 任一跑道 ,请你返回 最少侧跳次数. 。

注意:点 0. 处和点 n. 处的任一跑道都不会有障碍。

示例:

示例 1:

输入:obstacles = [0,1,2,3,0]

输出:2

解释:最优方案如上图箭头所示。总共有 2 次侧跳(红色箭头)。

注意,这只青蛙只有当侧跳时才可以跳过障碍(如上图点 2 处所示)。

示例 2:

输入:obstacles = [0,1,1,3,3,0]

输出:0

解释:跑道 2 没有任何障碍,所以不需要任何侧跳。

示例 3:

输入:obstacles = [0,2,1,0,3,0]

输出:2

解释:最优方案如上图所示。总共有 2 次侧跳。

分析

  1. 青蛙初始入赛道数记为num,然后for循环一直前行
  2. 当判断i + 1 等于num时,我们需要考虑两点
  3. 如果位置是否有障碍(因为走到了当前所有障碍肯定不是num),然后只有三条赛道,所以此时求差集后直接次数加一继续即可
  4. 如果当前位置无障碍,这需要贪心思维,获取除num以外的两个赛道,谁能下一次走的更远,选择最远的跳过去
  5. 重复2,3,4,完成解题...

解题:

class Solution:
    def minSideJumps(self, obstacles):
        length = len(obstacles)
        ret = 0
        num = 2
        choices = {1, 2, 3}
        for i in range(length - 1):
            if obstacles[i + 1] == num:
                _choice = choices - {num, obstacles[i]}
                if len(_choice) == 1:
                    num = _choice.pop()
                    ret += 1
                else:
                    tmp = {}
                    for j in _choice:
                        n = i
                        while n < length and obstacles[n] != j:
                            n += 1
                        tmp[n] = j
                    num = tmp[max(tmp)]
                    ret += 1
        return ret

欢迎关注我的公众号: 清风Python ,带你每日学习Python算法刷题的同时,了解更多python小知识。

有喜欢力扣刷题的小伙伴可以加我微信(King_Uranus)互相鼓励,共同进步,一起玩转超级码力!

我的个人博客: https://qingfengpython.cn

力扣解题合集: https://github.com/BreezePython/AlgorithmMarkdown

文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free