current position:Home>leetcode 1560. Most Visited Sector in a Circular Track(python)

leetcode 1560. Most Visited Sector in a Circular Track(python)

2022-01-31 13:33:25 Wang Daya

「 This is my participation 11 The fourth of the yuegengwen challenge 13 God , Check out the activity details :2021 One last more challenge

describe

Given an integer n and an integer array rounds. We have a circular track which consists of n sectors labeled from 1 to n. A marathon will be held on this track, the marathon consists of m rounds. The ith round starts at sector rounds[i - 1] and ends at sector rounds[i]. For example, round 1 starts at sector rounds[0] and ends at sector rounds[1]

Return an array of the most visited sectors sorted in ascending order.

Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction (See the first example).

Example 1:

Input: n = 4, rounds = [1,3,1,2]
Output: [1,2]
Explanation: The marathon starts at sector 1. The order of the visited sectors is as follows:
1 --> 2 --> 3 (end of round 1) --> 4 --> 1 (end of round 2) --> 2 (end of round 3 and the marathon)
We can see that both sectors 1 and 2 are visited twice and they are the most visited sectors. Sectors 3 and 4 are visited only once.
 Copy code 

Example 2:

Input: n = 2, rounds = [2,1,2,1,2,1,2,1,2]
Output: [2]
 Copy code 

Example 3:

Input: n = 7, rounds = [1,3,5,7]
Output: [1,2,3,4,5,6,7]
 Copy code 

Note:

2 <= n <= 100
1 <= m <= 100
rounds.length == m + 1
1 <= rounds[i] <= n
rounds[i] != rounds[i + 1] for 0 <= i < m
 Copy code 

analysis

According to the meaning , Given an integer n And an array of integers rounds . We have a circular track , It consists of n The marks are 1 To n Sector composition of . The marathon will be held on this track , Marathon runs counter clockwise m round . The first i Wheel slave sector rounds[i - 1] Start , To sector rounds[i] end . for example , The first 1 Wheel slave sector rounds[0] Start and in sector rounds[1] end , The title requires us to return the most visited sector array sorted in ascending order .

The idea is simple , It's running around the track counterclockwise , Find the sector that has passed the most times , We can think of this circular track as a straight track , The maximum number of rounds you can run is len(rounds) , If we n=4 , rounds = [2,3,1,2] , We can turn the track into the following form :

[1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]
 Copy code 

So let's find the starting position first 2, And will 2 Remove all the preceding numbers , At this point, the track becomes :

[2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]
 Copy code 

At this point, we just need to find out what happened 2 、3 、1 、2 The number of times of four numbers is enough , This is the case :

1  After  1  Time 
2  After  2  Time 
3  After  1  Time 
4  After  1  Time 
 Copy code 

Finally, find the number that has passed the most times to form a list , Return in ascending order .

answer

class Solution(object):
    def mostVisited(self, n, rounds):
        """
        :type n: int
        :type rounds: List[int]
        :rtype: List[int]
        """
        L = [i for i in range(1, n + 1)] * (len(rounds))
        d = {i: 0 for i in range(1, n + 1)}
        for i in range(L.index(rounds[0])):
            L.pop(0)
        for pos in rounds[1:]:
            i = L.index(pos)
            for j in range(i + 1):
                d[L.pop(0)] += 1
        result = [k for k, v in d.items() if v == max(d.values())]
        result.sort()
        return result
        	      
		
 Copy code 

Running results

Runtime: 168 ms, faster than 8.82% of Python online submissions for Most Visited Sector in a Circular Track.
Memory Usage: 13.6 MB, less than 8.82% of Python online submissions for Most Visited Sector in a Circular Track.
 Copy code 

analysis

In fact, the above simulation method is clumsy , I saw the master's solution , You just need to find the rules and find that the sector with the most frequent access is only related to / The end position is related to , The answer can be found through simple calculation .

answer

class Solution(object):
    def mostVisited(self, n, rounds):
        """
        :type n: int
        :type rounds: List[int]
        :rtype: List[int]
        """
        start=rounds[0]
        end=rounds[-1]
        result=[]
        if(start>end):
            for i in range(end):
                result.append(i+1)
            for i in range(start,n+1):
                result.append(i)
        else:
            for i in range(start,end+1):
                result.append(i)
        return result
 Copy code 

Running results

Runtime: 32 ms, faster than 67.65% of Python online submissions for Most Visited Sector in a Circular Track.
Memory Usage: 13.3 MB, less than 94.12% of Python online submissions for Most Visited Sector in a Circular Track.
 Copy code 

Original link :leetcode.com/problems/mo…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201311333237274.html

Random recommended