leetcode周赛203

2020-08-23 阅读量

字数统计: 1.7k字 | 阅读时长: 7分

题目5495. 圆形赛道上经过次数最多的扇区

给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成，扇区编号从 1 到 n 。现将在这条赛道上举办一场马拉松比赛，该马拉松全程由 m 个阶段组成。其中，第 i 个阶段将会从扇区 rounds[i - 1] 开始，到扇区 rounds[i] 结束。举例来说，第 1 阶段从 rounds[0] 开始，到 rounds[1] 结束。

请你以数组形式返回经过次数最多的那几个扇区，按扇区编号升序排列。

注意，赛道按扇区编号升序逆时针形成一个圆（请参见第一个示例）。

用例

输入：n = 4, rounds = [1,3,1,2]
输出：[1,2]

输入：n = 2, rounds = [2,1,2,1,2,1,2,1,2]
输出：[2]

输入：n = 7, rounds = [1,3,5,7]
输出：[1,2,3,4,5,6,7]

解题思路

思路一：模拟法

思路二：题目并不在乎每一个经过了多少次，实际上最终的结果一定是[i,…j]这样的集合
所以只需要关注起点与终点就可以了

代码

from typing import List
from collections import defaultdict


class Solution:
    def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
        visited = defaultdict(int)
        for i in range(1, len(rounds)):
            start = rounds[i - 1]
            end = rounds[i]
            while start != end:
                visited[start] += 1
                start = n if (start + 1) % n == 0 else (start + 1) % n
        visited[start] += 1
        M = max(visited.values())
        ans = []
        for k,v in visited.items():
            if v == M:
                ans.append(k)
        ans.sort()
        return ans


class Solution:
    def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
        s, e = rounds[0], rounds[-1]
        if s <= e:
            # [起点, 终点]
            return list(range(s, e + 1))
        else:
            # [1, 终点]+[起点, n]
            return list(range(1, e + 1)) + list(range(s, n + 1))

题目5496. 你可以获得的最大硬币数目

有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：

每一轮中，你将会选出任意 3 堆硬币（不一定连续）。

Alice 将会取走硬币数量最多的那一堆。
你将会取走硬币数量第二多的那一堆。
Bob 将会取走最后一堆。
重复这个过程，直到没有更多硬币。
给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。

返回你可以获得的最大硬币数目。

用例

输入：piles = [2,4,1,2,7,8]
输出：9

输入：piles = [9,8,7,6,5,1,2,3,4]
输出：18

解题思路

你在每次拿取的时候只能够拿到次大的，而bob只能拿到最小的，所以最后，bob拿数组中剩下最小的，
你拿次大的，alice拿最大的

代码

class Solution:
    def maxCoins(self, piles: List[int]) -> int:
        piles.sort()
        n = len(piles)
        time = n // 3
        idx = n - 2
        summary = 0
        while time != 0:
            summary+= piles[idx]
            idx-=2
            time -= 1
        return summary

题目5497. 查找大小为 M 的最新分组

给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。

在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。

给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。

返回存在长度恰好为 m 的一组 1 的最后步骤。如果不存在这样的步骤，请返回 -1 。

用例

输入：arr = [3,5,1,2,4], m = 1
输出：4

输入：arr = [3,1,5,4,2], m = 2
输出：-1

输入：arr = [1], m = 1
输出：1

解题思路

思路一：用并查集将插入的结点连接起来，同时为了保证求取结果的快速，对连接后的长度进行保存，连接后原长度的数量减一，新增的长度数量加一

思路二：转换思维，插入1反向过来为从连续的1中切开，只要当前长度出现m，就立刻返回结果

代码

class Solution:

    def findLatestStep(self, arr: List[int], m: int) -> int:
        n = len(arr)
        self.dp = [-1] * (n + 2)
        self.count = defaultdict(int)
        self.number = defaultdict(int)
        last = -1
        for i, v in enumerate(arr):
            self.dp[v] = v
            self.count[v] = 1
            self.number[1] += 1
            if self.dp[v - 1] != -1:
                self.union(v, v - 1)
            if self.dp[v + 1] != -1:
                self.union(v + 1, v)
            # if m in set(self.count.values()):
            #     last = i + 1
            # for k in self.count.values():
            #     if k == m:
            #         last = i + 1
            #         break
            if self.number[m] != 0:
                last = i + 1
        return last

    def union(self, child, parent):
        parent = self.find(parent)
        child = self.find(child)
        self.dp[child] = parent
        self.number[self.count[parent]] -= 1
        self.count[parent] += self.count[child]
        self.number[self.count[parent]] += 1
        self.number[self.count[child]] -= 1
        del self.count[child]

    def find(self, x):
        if self.dp[x] != x:
            self.dp[x] = self.find(self.dp[x])
        return self.dp[x]

import java.util.TreeSet;

class Solution {
    public int findLatestStep(int[] arr, int m) {
        TreeSet<Integer> set=new TreeSet<>();//记录插入点
        set.add(0);
        set.add(arr.length+1);
        if(arr.length==m) return arr.length;
        int n=arr.length;
        for (int i = n-1; i >=0; i--) {
            int index=arr[i];
            int a=set.lower(index);
            int b=set.higher(index);
            if(index-a-1==m||b-index-1==m){
                return i;
            }
            set.add(index);
        }
        return -1;
    }
}

本文作者： ketsudou
发布时间： 2020-08-23
最后更新： 2020-08-23
本文标题： leetcode周赛203
本文链接： http://huangketsudou.github.io/2020/08/23/leetcode周赛203/
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处

题目5495. 圆形赛道上经过次数最多的扇区

用例

解题思路

代码

题目5496. 你可以获得的最大硬币数目

用例

解题思路

代码

题目5497. 查找大小为 M 的最新分组

用例

解题思路

代码

题目5498. 石子游戏 V

用例

解题思路

代码