QUESTION：

MyCalendar.md

My Think：

Today we are talking about MyCalendar I II III. The daily questions for these three days are the same, so we will do them together.

今天我们讲MyCalendar I II III, 这三天的每日一题都是一样的,所以一起做了.

I:

We use binary search to find where startTime can be inserted, and return False if it is found in advance. After finding the insertion point, we can check whether there is overlap.

我们用二分查找, 查找 startTime 在哪里可以插入, 如果提前找到了直接返回 False. 找到了插入点后, 再检查是否有重叠即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class MyCalendar:

    def __init__(self):
         self.date = []

    def book(self, startTime: int, endTime: int) -> bool:
        # Binary Search 二分查找 
        n = len(self.date)
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if self.date[mid][0] < startTime:
                left = mid + 1  # Move the left pointer 移动左指针
            elif self.date[mid][0] > startTime:
                right = mid - 1  # Move the right pointer 移动右指针
            else:
                return False  # Find the overlap 发现重叠
        # Check for overlap with previous and next intervals 检查与前后区间的重叠
        if left > 0 and self.date[left - 1][1] > startTime:
            return False
        if left < len(self.date) and self.date[left][0] < endTime:
            return False

        # Insert it 插入区间
        self.date.insert(left, (startTime, endTime))
        return True

II:

This question requires us to check whether there will be three reservations under the conditions of the previous question. Although binary search can also be done, it will be much more complicated. We introduce the idea of ​​differential (Line Sweep) in this question.

1. Record the changes at each time point (start and end)
   When a new interval [startTime, endTime) is to be inserted:

   1. At the position corresponding to startTime +1
   2. At the position corresponding to endTime -1
      In this way, we only record “how much the overlap number should be added/subtracted at these two boundary time points”.

2. Count the current maximum overlap when necessary
   Sort all-time points (keys) from small to large, and accumulate their +1/-1 values in turn.
   The result of the accumulation is the number of activities carried out simultaneously at the corresponding time (that is, the “overlap number”).
   If you want to find out whether there is a triple reservation, see whether the maximum of this accumulation process reaches 3 (or higher)

这道题要求我们在上一道题的条件下, 检查是否会出现三次预定. 二分查找虽然也可以做, 但是会复杂很多. 我们在这一题引入差分(Line Sweep)的思想.

1. 记录每个时间点（开始与结束）的变化
   当有新的区间 [startTime, endTime) 要插入时：

   1. 在 startTime 对应的位置 +1
   2. 在 endTime 对应的位置 -1
      这样我们只记录“在这两个边界时间点，重叠数量要加/减多少”。

2. 在需要时统计当前的最大重叠
   把所有的时间点（key）从小到大排序，依次累加其 +1/-1 值。
   累加的结果就是对应时刻同时进行的活动数量（也就是“重叠数量”）。
   如果要查找是否出现三重预定，就看这个累加过程最大是否到达 3（或更高）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

from sortedcontainers import SortedDict
class MyCalendarTwo:
    def __init__(self):
        self.sd = SortedDict()
    def book(self, startTime: int, endTime: int) -> bool:
        self.sd[startTime] = self.sd.get(startTime, 0) + 1
        self.sd[endTime] = self.sd.get(endTime, 0) - 1
        s = 0
        for v in self.sd.values():
            s += v
            if s > 2:
                self.sd[startTime] -= 1
                self.sd[endTime] += 1
                return False
        return True

III:

This question is even more difficult. It requires us to find the maximum number of multiple reservations. We can just record it based on the previous question.

1. Difference record

   Same as before: +1 at the position corresponding to startTime, -1 at the position corresponding to endTime.

   Store in self.sd: key = time point, value = increase or decrease at that time point.

2. Find the maximum number of overlaps

   Use a rolling variable ongoing to indicate “how many overlaps there are at the current moment”.
   Each time a time point is traversed, the corresponding difference is accumulated to ongoing, and then max_overlap = max(max_overlap, ongoing) is updated.

这道题更加过分, 要求我们找到多重预定中最多有多少重, 我们就在上一道题的基础上记录即可.

1. 差分记录

   与之前一致：在 startTime 对应的位置 +1，在 endTime 对应的位置 -1。
   self.sd 中存储：key=时间点, value=该时间点的增减量。

2. 求最大重叠数

   用一个滚动变量 ongoing 表示“当前时刻有多少重叠”。
   每遍历一个时间点，把对应的差分累加到 ongoing，然后更新 max_overlap = max(max_overlap, ongoing)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

from sortedcontainers import SortedDict


class MyCalendarThree:
    def __init__(self):
        self.sd = SortedDict()

        self.max_overlap = 0

    def book(self, startTime: int, endTime: int) -> int:
        # First, record the "plus 1" and "minus 1" of this reservation.先把这次预定的“加1”和“减1”记录下来
        self.sd[startTime] = self.sd.get(startTime, 0) + 1
        self.sd[endTime] = self.sd.get(endTime, 0) - 1

        # Temporary variable, record the number of overlaps 临时变量, 记录几折叠
        ongoing = 0 # Current overlap number
        tmp_max = 0
        for v in self.sd.values():
            ongoing += v
            tmp_max = max(ongoing, tmp_max)
        self.max_overlap = max(self.max_overlap, tmp_max)
        return self.max_overlap

Introduction How Labs work

We can see the structure of the lab is like this:

1
2
3

%%run_and_test python3 -c "from exercise_1_1 import f1; print(f1(0, 0))"

'\n'

Which means run_and_test ? It is a Magic Command, run python file which is exercise_1_1.py and test the output of f1(0, 0).

And at the top of this Jupyter notebook, we can see the following code:

1

load_ext run_and_test

This is a magic command that loads the run_and_test extension, which allows us to run and test Python code in the notebook.

And if you run %pycat exercise_1_1_template.py, you will get a new file exercise_1_1.py which is the template of the exercise.

You can write your code inside the exercise_1_1.py file and run the test code in the notebook to check if your code is correct. Or directly write your code after %%writefile exercise_1_1.py command block.

Exercise 1

Finding the pattern, we can see that the first parameter m means how many structures there are, and the second parameter n means how many underscores there are.

So we can assume the structure is like:

1

|____|

And if we have m = 3 and n = 4, the output would be:

1

|____||____||____|

My solution

In Python, we can use multiplication to repeat a string. So we can use the following code to solve this problem:

1
2

def f1(m, n):
    return ('|' + '_' * n + '|') * m

Exercise 2

Same way to find the pattern, n rows and n columns, and each row contains the digit n repeated n times.

And you can find, the input n is a digit, which means it is an integer. While we use “*” with the integer, it is the mathematical multiplication.

So we need to convert the integer to a string, and then multiply it with the integer, and add a newline at the end of each row.

My solution

1
2

def f2(n):
    return (str(n)*n + "\n")*n

And… in case you want to use a for loop:

1
2
3
4
5

def f2(n):
    result = ""
    for i in range(n):
        result += str(n) * n + "\n"
    return result

Exercise 3

This problem is a bit complex to understand, so let’s break it down step by step. Based on Eric’s reply in Ed, we can see that the problem requires us to traverse from the rightmost side, removing all elements that are ≤ the last element (x) until we encounter a number that is ≥ the last element (y). It is important to note that if there are any elements to the left of y that were previously removed, they should also be removed.

This Exercise needs us use only 1 loop.

My solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def f3(L):
    # You can use [] list here, but set is more effective
    num_remove = set()
    # Check ED of Eric's reply
    i = len(L)-2
    flag = 0
    while i >= 0:
        if L[i] < L[-1] and flag == 0:
            num_remove.add(L[i])
            L.pop(i)
            # reset the length in case it have nothing
            i = len(L) - 2
        elif L[i] >= L[-1]:
            i -= 1
            flag = 1
        elif L[i] in num_remove:
            L.pop(i)
        else:
            i -= 1
    print(L)

You can full screen, change speed, and change quality of the video.

Standard Solution

I have to say Eric is a genius:

1
2
3
4

def f3(L):
    while len(L) > 1 and L[-2] < L[-1]:
        L.remove(L[-2])
    print(L)

You can full screen, change speed, and change quality of the video.

Exercise 4

The fourth function, f4, works with dictionaries:

1
2
3
4
5
6
7
8

def f4(D, n):
    if n not in D:
        return []
    ans = [n]
    while n in D and D[n] > n:
        ans.append(D[n])
        n = D[n]
    return ans

1. This function takes a dictionary D and an integer n. It generates a strictly increasing sequence of integers based on the relationships defined in the dictionary.
2. Starting from n, it appends D[n], D[D[n]], and so on to the list, as long as each subsequent value is greater than the previous one.
3. For example, if D = {1: 2, 2: 3, 3: 5} and n = 1, the function will return [1, 2, 3, 5].

Standard Solution

1
2
3
4
5
6

def f4(D, n):
    L = [] if n not in D else [n]
    while n in D and n < D[n]:
        L.append(D[n])
        n = D[n]
    return L

Exercise 5

The fifth function, f5, reads from a file and processes each line:

1
2
3
4
5
6

def f5(filename):
    with open(filename) as f:
        for i in f:
            name, number = i.split(',')
            number = int(number) * 1000
            print(f"{number} people named {name}")

1. This function reads a text file, where each line consists of a name and a count separated by a comma.
2. The function multiplies the count by 1000 and prints the result in the format: “X people named Y”.
3. For example, if the file contains a line “John,5”, it will print:

1

5000 people named John

Standard Solution

1
2
3
4
5

def f5(filename):
    with open(filename) as file:
        for line in file:
            name, count = line.split(',')
            print(int(count) * 1_000, 'people named', name)

Exercise 6

The final function, f6, also reads from a text file, but with a different format:

1
2
3
4
5
6
7

def f6(filename):
    with open(filename) as f:
        for i in f:
            # Check if the line is not empty
            if not i.isspace():
                number, charactor = i.split()
                print(int(number) * charactor)

1. This function reads lines that contain an integer followed by a symbol (e.g., “5 *”).
2. It multiplies the symbol by the integer and prints the result.
3. For example, if the file contains the line “3 # “, the function will print:

1

### 

Exercise 1

what is yield in python?

The yield keyword in Python is used to create generator functions. A generator function is a special kind of function that returns a generator iterator, which can be used to iterate over a sequence of values. Unlike a regular function that returns a single value using the return statement, a generator function can yield multiple values, one at a time, pausing its state between each one.

How it works?

When a generator function is called, it doesn’t execute its code immediately. Instead, it returns a generator object that can be iterated over. Each time you request the next item from the generator (using next() or a loop), the generator function resumes execution from where it last left off, runs until it hits a yield statement, and yields the value to the caller.

Problem Description

First, we need to understand the requirements of the problem:

Input: A list of integers L, such as [n1, n2, n3, …]. Output:

• Output n1 lines of rank 1 X, which means X without indentation.
• Between each pair of rank 1 X, output n2 lines of rank 2 X, which are indented with one tab (\t).
• Between each pair of rank 2 X, output n3 lines of rank 3 X, which are indented with two tabs.
• Continue this pattern until all elements in the list L have been processed.

My solution

1
2
3
4
5
6
7
8
9
10
11
12
13

def f1():
    while True:
        print(" /\\")
        print("/  \\")
        yield
        print("----")
        yield
        print("\\  /")
        print(" \\/")
        yield
        print(" ||")
        print(" ||")
        yield

Standard solution

1
2
3
4
5
6
7
8
9
10

def f1():
    while True:
        print(' /\\\n/  \\')
        yield
        print('----')
        yield
        print('\\  /\n \\/')
        yield
        print(' ||\n ||')
        yield

Exercise 2

Problem Description

1
2
3
4
5
6
7

Line:   [1,   3,   3,   1]
           |     |     |
          i=0   i=1   i=2
           ↓     ↓     ↓
Calculate:1+3   3+3   3+1
           ↓     ↓     ↓
Results:   4     6     4

My solution

1
2
3
4
5
6
7

def f2():
    # initialized
    row = [1]
    while True:
        yield row
        # row[i] + row[i + 1] is the expression in list comprehension
        row = [1] + [row[i] + row[i + 1] for i in range(len(row)-1)] + [1]

Standard solution

1
2
3
4
5
6

def f2():
    L = [1]
    yield L
    while True:
        L = [1] + [L[i] + L[i + 1] for i in range(len(L) - 1)] + [1]
        yield L

Exercise 3

Problem Description

First, we need to understand the requirements of the problem:

Input: A list of integers L, such as [n1, n2, n3, …]. Output:

• Output n1 lines of rank 1 X, which means X without indentation.
• Between each pair of rank 1 X, output n2 lines of rank 2 X, which are indented with one tab (\t).
• Between each pair of rank 2 X, output n3 lines of rank 3 X, which are indented with two tabs.
• Continue this pattern until all elements in the list L have been processed.

My solution

1
2
3
4
5
6
7
8
9
10

def f3(L):
    def helper(L, rank):
        if not L:
            return
        n = L[0]
        for i in range(n):
            print('\t' * rank + 'X')
            if i < n - 1:
                helper(L[1:], rank + 1)
    helper(L, 0)

We need to write a recursive function to handle this nested structure. Here is the implementation idea:

Define a helper function helper(L, rank), where:

• L is the list currently being processed.
• rank is the current level (indentation level).

In the helper function:

1. If the list is empty, return directly.
2. Get the number of lines to output at the current level, n = L[0].
3. Use a loop to output n lines of the current level’s X, with each line having the corresponding number of tab characters (\t) based on the rank.
4. After each output, if it is not the last element and it is not the last line, recursively call helper to handle the next level of X lines.

Standard solution

1
2
3
4
5
6
7
8
9
10
11
12

def f3(L):
    _f3(L, 0)

def _f3(L, n):
    if n == len(L):
        return
    for _ in range(L[n] - 1):
        print('\t' * n, 'X', sep='')
        _f3(L, n + 1)
    if L[n]:
        print('\t' * n, 'X', sep='')

Exercise 4

Problem Description

Objective: Given a list L of integers, we need to:

• Break it down into sublists of equal length, where the length is maximal.
• This process is recursive: each sublist is further broken down in the same manner.
• The original list should be preserved (i.e., not modified).

Key Points:

• We aim to split the list into the largest possible sublists of equal length (greater than 1) that evenly divide the length of the list.
• The recursion continues until a sublist cannot be broken down further (i.e., its length cannot be divided into equal parts greater than 1).

My solution

1
2
3
4
5
6
7
8
9
10
11

from math import sqrt

def f4(L):
    n = len(L)
     # Try to find the maximal sublist length greater than 1
    for sublist_length in range(n // 2, 1, -1):
        if n % sublist_length == 0:
            # Split the list into sublists
            sublists = [f4(L[i:i + sublist_length]) for i in range(0, n, sublist_length)]
            return sublists
    return L.copy()

Standard solution

1
2
3
4
5
6
7

def f4(L):
    for n in range(2, round(sqrt(len(L))) + 1):
        if len(L) % n == 0:
            w = len(L) // n
            return [f4(L[i : i + w]) for i in range(0, len(L), w)]
    return list(L)

Exercise 5

Problem Description

Objective: Given a special list L (a list whose elements are integers or other special lists), we need to return a dictionary where:

Keys are tuples of indices (i_1, i_2, ..., i_n).
Values are integers e.
The keys represent the path of indices to reach an integer e within the nested list structure.

Interpretation:

• If the key is (i_1,), then L[i_1] is an integer e.
• If the key is (i_1, i_2), then L[i_1][i_2] is an integer e.
• If the key is (i_1, i_2, i_3), then L[i_1][i_2][i_3] is an integer e.
• And so on.

Constraints:

We need to handle any depth of nesting.
Use isinstance() to check if an element is an integer or a list.
The original list should not be modified.

My solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def f5(L):
    result = {}
    def helper(sublist, path):
        for index, element in enumerate(sublist):
            current_path = path + (index,)
            if isinstance(element, int):
                result[current_path] = element
            elif isinstance(element, list):
                helper(element, current_path)
            else:
                # If there are other types, you might want to handle them or raise an error
                pass
    helper(L, ())
    return result

Standard solution

1
2
3
4
5
6
7
8
9
10

def f5(L):
    D = {}
    for i in range(len(L)):
        if isinstance(L[i], int):
            D[(i,)] = L[i]
        else:
            E = f5(L[i])
            for s in E:
                D[i, *s] = E[s]
    return D

Difference between my solution and the standard solution

My Solution

• Uses a Helper Function (helper): Your solution defines an inner function helper(sublist, path) to handle the recursion.
• Explicit Path Passing: The path variable, representing the current position in the nested list, is explicitly passed and updated at each recursive call.
• State Encapsulation: By using a nested function, the state (path and result) is encapsulated within the f5 function’s scope.
  Standard Solution
• Direct Recursion: The standard solution directly calls f5(L[i]) recursively without using a helper function.
• Implicit Path Construction: It constructs the path by combining the current index i with the indices from the recursive call (s) using tuple unpacking.
• Dictionary Merging: After each recursive call, it merges the returned dictionary E into the current dictionary D.

Exercise 6

Problem Description

The given problem is not strictly about the Fibonacci sequence, but it generalizes similar principles to a broader set of recursive relationships. In the problem, you’re asked to compute the n-th term of a series, where the series is defined by some initial terms (first_terms) and a set of recurrence factors (factors). The Fibonacci sequence is a special case of such a recurrence relation, where each term is the sum of the two preceding terms.

My solution(Wrong)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def f6(first_terms, factors, n):
    k = len(first_terms) - 1
    sequence = first_terms.copy()
    
    # If n is within the initial terms, return it directly
    if n <= k:
        return sequence[n]
    
    # Compute terms iteratively up to n
    for i in range(k + 1, n + 1):
        xi = 0
        for s in range(k + 1):
            xi += factors[s] * sequence[i - k - 1 + s]
        sequence.append(xi)
    
    return sequence[n]

Standard solution

1
2
3
4
5
6
7
8
9
10
11

from collections import defaultdict

def f6(n):
    _f6(n)

def _f6(n, nb_of_tabs=0, nb_of_calls=defaultdict(int)):
    nb_of_calls[n] += 1
    print('\t' * nb_of_tabs, f'Computation nb {nb_of_calls[n]} of fibo({n})...', sep='')
    fibo_n = n if n in {0, 1} else _f6(n - 1, nb_of_tabs + 1) + _f6(n - 2, nb_of_tabs + 1)
    print('\t' * nb_of_tabs, f'... computed as {fibo_n}', sep='')
    return fibo_n

Description:

You are given an integer array nums of even length. You have to split the array into two parts nums1 and nums2 such that:

nums1.length == nums2.length == nums.length / 2.
nums1 should contain distinct elements.
nums2 should also contain distinct elements.
Return true if it is possible to split the array, and false otherwise.

Example 1:

Input: nums = [1,1,2,2,3,4]
Output: true
Explanation: One of the possible ways to split nums is nums1 = [1,2,3] and nums2 = [1,2,4].
Example 2:

Input: nums = [1,1,1,1]
Output: false
Explanation: The only possible way to split nums is nums1 = [1,1] and nums2 = [1,1]. Both nums1 and nums2 do not contain distinct elements. Therefore, we return false.

Thinking:

题目要求判断是否可以将数组分成两个部分，使得两个部分的元素都是不同的。
最开始考虑的是Counter()记录每个数字是否满足某个条件，如果不满足就返回False。后面发现不需要Counter，普通的字典记录，中途遇到某个数字大于2就返回False即可。

Code:

1
2
3
4
5
6
7
8

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        Counter_nums = Counter(nums)
        for i, j in Counter_nums.items():
            if j > 2:
                return False
        else:
            return True

1
2
3
4
5
6
7
8

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1
            if count[num] > 2:
                return False
        return True

Description:

https://leetcode.cn/problems/minimum-length-of-anagram-concatenation/description/?envType=daily-question&envId=2024-12-20
You are given a string s, which is known to be a concatenation of anagrams of some string t.

Return the minimum possible length of the string t.

An anagram is formed by rearranging the letters of a string. For example, “aab”, “aba”, and, “baa” are anagrams of “aab”.

Example 1:

Input: s = "abba"

Output: 2

Explanation:

One possible string t could be "ba".

Example 2:

Input: s = "cdef"

Output: 4

Explanation:

One possible string t could be "cdef", notice that t can be equal to s.

Thinking:

Since the problem naturally suggests using a counting method (Counter), we need to find the minimum substring for each string. For example, for abba, the result is ab; for cdef, it’s cdef.
We iterate from length 1 (a single character) onwards, slicing the string to get the current substring.

Initially, we compute the character count for the original string using Counter, which gives us a dictionary of character frequencies.
Next, we only need to check if the count of each character in the current substring multiplied by n/k equals the count in the original string (i.e., whether repeating the current substring x times equals the original string).

由于题意很容易联想到这道题要进行计数(Counter). 我们需要找到每个字符串的最小子串，abba为ab, cdef为cdef. 于是我们从长度0（即单个字符）开始遍历，期间通过切片的形式来获取当前子串。
因为最开始我们对原始字符串进行了Counter，得到了字符数量和字符对应的字典。接下来我们只需要判断当前子串的Counter到的某个字符的数值乘以n/k是否等于原始字符串的Counter的值即可（即当前子串乘以x倍是否等于源字符串）。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import collections
class Solution:
    def minAnagramLength(self, s: str) -> int:
        def check(k: int) -> bool:
            # 遍历字符串 s，每次取长度为 k 的子串
            # Iterate over the string `s`, taking substrings of length `k`
            for i in range(0, n, k):
                # 统计每个字符出现的次数
                # Count the occurrences of each character in the current substring
                cnt1 = collections.Counter(s[i: i + k])
                for c, v in cnt.items():
                    # 如果每个字符出现的次数乘以 n/k != cnt[] return False
                    # If the count of any character multiplied by (n // k) != the original count, return False
                    if cnt1[c] * (n // k) != v:
                        return False
            return True

        cnt = collections.Counter(s)
        n = len(s)
        for i in range(1, n+1):
            if n % i == 0 and check(i):
                return i

QUESTION：

3159. Find Occurrences of an Element in an Array.md
You are given an integer array nums, an integer array queries, and an integer x.

For each queries[i], you need to find the index of the queries[i]th occurrence of x in the nums array. If there are fewer than queries[i] occurrences of x, the answer should be -1 for that query.

Return an integer array answer containing the answers to all queries.

Example 1:

Input: nums = [1,3,1,7], queries = [1,3,2,4], x = 1

Output: [0,-1,2,-1]

Explanation:

For the 1st query, the first occurrence of 1 is at index 0.
For the 2nd query, there are only two occurrences of 1 in nums, so the answer is -1.
For the 3rd query, the second occurrence of 1 is at index 2.
For the 4th query, there are only two occurrences of 1 in nums, so the answer is -1.
Example 2:

Input: nums = [1,2,3], queries = [10], x = 5

Output: [-1]

Explanation:

For the 1st query, 5 doesn’t exist in nums, so the answer is -1.

Constraints:

1 <= nums.length, queries.length <= 105
1 <= queries[i] <= 105
1 <= nums[i], x <= 104

My Think：

I haven’t written a solution for a long time. Now that I’m on vacation, I’m starting over. This question requires us to find “all x’s indices” from the given nums, and then return the index address of the queries-th x.
So we can use the list generation formula indices = [i for i, value in enumerate(nums) if value == x] to return a list containing all x’s indices,
and then query them one by one.
First mistake: I didn’t consider the case where indices is empty, so indices[q-1] out of range.
Second mistake: I forgot that the for loop in Golang needs two parameters to receive the value passed by range.

很久没有写题解了,现在放假了于是重新开始了. 这一道题要求我们从给定的nums中找到”所有x的索引”, 然后返回第queries个x的索引地址即可.
于是我们可以用列表生成式indices = [i for i, value in enumerate(nums) if value == x]来返回一个包含所有x索引的列表,
然后依次在其中查询即可.
第一次错误: 没有考虑indices为空的情况, 于是indices[q-1] out of range.
第二次错误: 忘记了Golang里的for循环需要两个参数接收range传来的value.

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:
        # Find the indices of all elements equal to x
        indices = [i for i, value in enumerate(nums) if value == x]
        # print(indices)
        n = len(indices)
        ans = []
        for q in queries:
            if indices and q-1 < n:
                ans.append(indices[q-1])
            else:
                ans.append(-1)
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

func occurrencesOfElement(nums []int, queries []int, x int) []int {
    var indices []int
    for i, value := range nums {
        if value == x {
            indices = append(indices, i)
        }
    }
    var ans []int
    n := len(indices)
    for _, q := range queries { // "_, q"
        if n > 0 && q-1 < n { 
            ans = append(ans, indices[q-1])
        } else {
            ans = append(ans, -1)
        }
    }
    return ans
}

Description:

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:

Input: nums = [1]
Output: [[1]]

Thinking:

This question is more like a tree problem.
like the tree below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

dfs(0): nums = [1,2,3]
|
|-- i=0: swap(0,0) -> [1,2,3]
|   |
|   |-- dfs(1)
|       |-- i=1: swap(1,1) -> [1,2,3]
|       |   |-- dfs(2): append [1,2,3]
|       |-- i=2: swap(1,2) -> [1,3,2]
|           |-- dfs(2): append [1,3,2]
|
|-- i=1: swap(0,1) -> [2,1,3]
|   |
|   |-- dfs(1)
|       |-- i=1: swap(1,1) -> [2,1,3]
|       |   |-- dfs(2): append [2,1,3]
|       |-- i=2: swap(1,2) -> [2,3,1]
|           |-- dfs(2): append [2,3,1]
|
|-- i=2: swap(0,2) -> [3,2,1]
    |
    |-- dfs(1)
        |-- i=1: swap(1,1) -> [3,2,1]
        |   |-- dfs(2): append [3,2,1]
        |-- i=2: swap(1,2) -> [3,1,2]
            |-- dfs(2): append [3,1,2]

We swap the current position index with each possible candidate i from index to the end. They can be seen as left and right pointers: index determines which position we’re filling, and i tries different numbers to place there.

Before the recursive call, we swap nums[i] and nums[index] to try placing a new number at position index. If we reach the last position (index == len(nums) - 1), we add the current permutation to the answer list.
After recursion, we swap back to restore the original state (backtracking).

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # index
        def dfs(index):
            # Reach the last element
            if index == len(nums) - 1:
                res.append(list(nums))
                return
            for i in range(index, len(nums)):
                nums[i], nums[index] = nums[index], nums[i]
                dfs(index + 1)
                nums[i], nums[index] = nums[index], nums[i]

        res = []
        dfs(0)
        return res

题目：

思想：

就排序，排完之后，两两比较后merge.

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 先按区间的起始位置进行排序
        intervals.sort(key=lambda x: x[0])
        
        merged = []
        for interval in intervals:
            # 如果merged列表为空，或者当前区间不与merged列表中的最后一个区间重叠，直接添加到merged列表
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # 否则我们就合并当前区间和merged列表中的最后一个区间
                merged[-1][1] = max(merged[-1][1], interval[1])
        
        return merged

QUESTION：

1366. Rank Teams by Votes.md
In a special ranking system, each voter gives a rank from highest to lowest to all teams participating in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

You are given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = [“ABC”,”ACB”,”ABC”,”ACB”,”ACB”]
Output: “ACB”
Explanation:
Team A was ranked first place by 5 voters. No other team was voted as first place, so team A is the first team.
Team B was ranked second by 2 voters and ranked third by 3 voters.
Team C was ranked second by 3 voters and ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team, and team B is the third.
Example 2:

Input: votes = [“WXYZ”,”XYZW”]
Output: “XWYZ”
Explanation:
X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position.
Example 3:

Input: votes = [“ZMNAGUEDSJYLBOPHRQICWFXTVK”]
Output: “ZMNAGUEDSJYLBOPHRQICWFXTVK”
Explanation: Only one voter, so their votes are used for the ranking.

Constraints:

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length.
votes[i][j] is an English uppercase letter.
All characters of votes[i] are unique.
All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

My Think：

This question requires us to count their votes. The first thing that comes to mind is to build a double structure, similar to this:
这道题要求我们统计他们的投票情况. 首先想到的就是构建一个双重结构体, 类似于这样:

1
2
3
4
5
6
7

type struct {
    char A {
        1: 1;
        2: 1;
        3: 1;
    }
}

Then fill in the dictionary in a double loop and sort it. It’s very simple in Python, but I thought it was complicated at first and built the sorting logic manually.
Finally, we can use lambda expression sorted_teams = sorted(rank.keys(), key = lambda x: ([-rank[x][i] for i in range(len(votes[0]))], x))

What needs to be noted in Go is the usage of the standard answer. Use slices.SortedFunc to sort the teams. The sorting rules are defined according to the requirements of the question:

1. Sort in descending order by votes.
2. If the votes are the same, sort in ascending alphabetical order.
   maps.Keys(cnts) gets the keys of all teams (that is, the characters of all teams)
   slices.Compare(cnts[b], cnts[a]): compare the vote slices of two teams and sort in descending order by votes (b comes first).
   cmp.Compare(a, b): when the votes are the same, sort in ascending alphabetical order.
   cmp.Or: execute the first comparison rule. If the return value is not 0 (that is, there is a priority difference), return directly; otherwise execute the next rule.

然后在一个双重循环中填写这个字典, 最后进行排序即可. 在Python中十分简单, 但是我一开始想复杂了, 手动构建了排序逻辑.
最后用lambda表达式即可sorted_teams = sorted(rank.keys(), key = lambda x: ([-rank[x][i] for i in range(len(votes[0]))], x))

Go里需要注意的是标准答案的用法, 使用 slices.SortedFunc 对团队进行排序，排序规则按题目要求定义：

1. 按票数降序排列。
2. 如果票数相同，按字母升序排列。
   maps.Keys(cnts) 获取所有团队的键（即所有团队的字符）
   slices.Compare(cnts[b], cnts[a])：比较两个团队的票数切片，按票数降序排列（b 在前）。
   cmp.Compare(a, b)：当票数相同时，按字母升序排列。
   cmp.Or：执行第一个比较规则，如果返回值非 0（即有优先级差异），直接返回；否则执行下一个规则。

Code：

1
2
3
4
5
6
7
8

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        rank = defaultdict(lambda: defaultdict(int))
        for value in votes:
            for ind, c in enumerate(value):
                rank[c][ind] += 1
        sorted_teams = sorted(rank.keys(), key = lambda x: ([-rank[x][i] for i in range(len(votes[0]))], x))
        return ''.join(sorted_teams)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def rankTeams_Siz(self, votes: List[str]) -> str:
        rank = defaultdict(lambda: defaultdict(int))
        for value in votes:
            for ind, c in enumerate(value):
                rank[c][ind] += 1
        print(rank)
        ans = ''
        for i in range(len(votes[0])):
            temp_ans = ''
            count = 0
            for key, value in rank.items():
                if value[i] > count:
                    temp_ans = key
                    count = value[i]
                else:
                    # 如果并列, 则考虑下一位 If there is a tie, consider the next one
                    while value[i] == count:
                        i += 1 # 这个i是临时变量, 直接用 This i is a temporary variable, use it directly
                        if i > len(votes[0]): # 考虑找到最后都没找到的情况Consider the situation where you find nothing in the end.
                            # 答案值应该是字母顺序 The answer values should be in alphabetical order
                            temp_ans = key
                            break
                        if value[i] > count:
                            temp_ans = key
                            count = value[i]
            ans += temp_ans
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

func rankTeams(votes []string) string {
    cnts:=map[rune][]int{}
    for _,ch := range votes[0] {
        cnts[ch]=make([]int,len(votes[0]))
    }

    for _,vote := range votes{
        for i,ch := range vote{
            cnts[ch][i]++
        }
    }

    res := slices.SortedFunc(maps.Keys(cnts),func(a,b rune) int{
        return cmp.Or(slices.Compare(cnts[b],cnts[a]),cmp.Compare(a,b))
    })
    return string(res)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

package main

import "sort"

func rankTeams(votes []string) string {
	rank := make(map[byte]map[int]int)

	for _, vote := range votes {
		for i := 0; i < len(vote); i++ {
			team := vote[i]
			if _, ok := rank[team]; !ok {
				rank[team] = make(map[int]int)
			}
			rank[team][i]++
		}
	}

	teams := make([]byte, 0, len(rank))
	for team := range rank {
		teams = append(teams, team)
	}

	sort.Slice(teams, func(i, j int) bool {
		a, b := teams[i], teams[j]
		for k := 0; k < len(votes[0]); k++ {
			// 比较两队在 k 排位的票数 // Compare the votes of the two teams in position k
			countA, countB := rank[a][k], rank[b][k]
			if countA != countB {
				return countA > countB // 按票数降序 Sort by votes in descending order
			}
		}
		return a < b // 字母升序 Alphabetical ascending
	})
	// 拼接结果
	return string(teams)
}

2894. 分类求和并作差

Thought

题意：
在 $[1, n]$ 中，求所有不能被 $m$ 整除的数的总和与能被整除的数的总和之差。

思路推导：

1. 总和：
   $S_{\text{total}} = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

2. 能被 $m$ 整除的数为：$m, 2m, 3m, \dots, \left\lfloor \frac{n}{m} \right\rfloor m$
   $S_{\text{divisible}} = m \cdot \left(1 + 2 + \dots + k\right) = m \cdot \frac{k(k+1)}{2}$

3. 所以不能被整除的和为：
   $S_{\text{not_div}} = S_{\text{total}} - S_{\text{divisible}}$

4. 所求答案为：
   $\text{差值} = S_{\text{not_div}} - S_{\text{divisible}}$
   $= \frac{n(n+1)}{2} - m \cdot \frac{\left\lfloor \frac{n}{m} \right\rfloor(\left\lfloor \frac{n}{m} \right\rfloor+1)}{2} - m \cdot \frac{\left\lfloor \frac{n}{m} \right\rfloor(\left\lfloor \frac{n}{m} \right\rfloor+1)}{2}$
   $= \frac{n(n+1)}{2} - m \cdot \left\lfloor \frac{n}{m} \right\rfloor(\left\lfloor \frac{n}{m} \right\rfloor+1)$

Code

1
2
3
4
5

class Solution:
    def differenceOfSums(self, n: int, m: int) -> int:
        # divisible = m * (1 + n // m) * (n // m) // 2
        # undivisible = n * (n + 1) // 2 - n * ((1 + n // m) * (n // m) // 2)
        return - m * ((1 + n // m) * (n // m)) + (n * (n + 1) >> 1)

1

const differenceOfSums = (n: number, m: number): number => -m * ((1 + Math.floor(n / m)) * Math.floor(n / m)) + (n * (n + 1) >> 1);