“This is the 13th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

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] 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 the code

Example 2:

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

Example 3:

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

Note:

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

parsing

We are given an integer N and an integer array rounds. We have a circular track that consists of n sectors labeled 1 through N. The marathon will be held on this track and the marathon will run m rounds counterclockwise. Rounds I begins with sector [i-1] and ends with sector rounds[I]. For example, rounds[0] starts and ends on sector [1], and we are asked to return an array of the most visited sectors sorted in ascending order.

The idea is to run counterclockwise around the track and find the sector that has traveled the most times. We can straighten out the round track as a straight track, and the maximum number of rounds we can run is len(rounds). If n=4, rounds = [2,3,1,2], We can turn the track into something like this:

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

So we find the starting position 2 and remove all the digits in front of 2, so the track becomes:

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

In this case, we just need to find The Times of passing 2, 3, 1, and 2.

1 has gone through once 2 has gone through twice 3 has gone through once 4 has gone through onceCopy the code

Finally, find out the list of numbers that have passed the most times, and 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 the code

The results

Runtime: 168 ms, faster than 8.82% of Python online submissions for Most Visited sectors in a Circular Track. Memory Usage: Submissions for Most Visited sectors in a Circular Track.Copy the code

parsing

As a matter of fact, the method of simulation like the one above is quite clumsy. I have seen the solution of the expert. I only need to find the rule and find that the sector with the most frequent visits is only related to the starting/ending position, and 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 the code

The results

Runtime: 10 ms, faster than 67.65% of Python online submissions for Most Visited sectors in a Circular Track. Memory Usage: Submissions in Python online submissions for Most Visited sectors in a Circular Track.Copy the code

Original link: leetcode.com/problems/mo…

Your support is my biggest motivation