Exercise 1:

This exercise focuses on input validation and formatting floating-point numbers. The goal is to prompt the user to enter a floating-point number between -1 and 1 (exclusive). If the input is valid, the program rounds the number to two decimal places and prints it. Otherwise, it keeps prompting the user until a valid input is provided.
Key Points:

• The program uses a try-except block to catch invalid inputs (e.g., strings that cannot be converted to floats).
• The input() function is wrapped in an infinite while loop to continuously ask for input until the correct condition is met.

In the updated version of Exercise 1, we use the formatting :.2f instead of round(). Here’s the key difference between the two:

• round(): This is a Python built-in function that rounds a number to a specified number of decimal places. For example, round(1.236, 2) will return 1.24. However, the output of round() is still a float, but it does not guarantee a fixed number of decimal places when printed. For instance, round(1.0001, 2) would return 1.0 and only display one decimal place, not two.
• :.2f: This is part of Python’s string formatting and ensures the number is displayed with exactly two decimal places, no matter what the number is. It also rounds the number appropriately. For instance, number = 1.0 formatted as f”{number:.2f}” will print 1.00. This makes :.2f particularly useful for consistent display of decimal places, which is important for formatting output for users.

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

while True:
    try:
        i = input('Enter a floating point number between -1 and 1 excluded: ')
        number = float(i)
        if '.' not in i:
            raise ValueError
        if -1 < number < 1:
            # not using round() here because it rounds to the nearest even number
            print(f'\nUp to +/-0.005, you input {number:.2f}')
        else:
            raise ValueError
        break
    except ValueError:
        print("You got that wrong, try again!\n")

Exercise 2:

This exercise involves processing a block of text and formatting it into sentences. Each sentence should have its first word capitalized, and the remaining words should be in lowercase. The task is to handle spaces and punctuation properly.

Key Points:

• A regular expression (re.sub) is used to replace multiple spaces with a single space.
• Another regular expression (re.split) is used to split the text into sentences while preserving punctuation marks.
• After splitting, the sentences are processed: the first word is capitalized, and all other words are made lowercase.
• Finally, the processed sentences are recombined into a single formatted text.

Why use re in Exercise 2, and what is re?

In Exercise 2, we use re (Python’s regular expression module) to process and format the text input. Let’s break down why re is used and what it is:

What is re?

re stands for regular expressions, which are powerful tools for matching patterns in strings. The re module in Python allows you to work with regular expressions to search, split, and manipulate text based on specific patterns. Regular expressions are highly flexible and efficient for handling complex string operations.

Why use re in Exercise 2?

In this exercise, we need to handle several complex text manipulations:

1. Replace multiple spaces with a single space: Sentences in the text may have irregular spaces between words, so we need to normalize these spaces. Instead of writing loops or conditions to handle each case, we use re.sub() with a pattern r’\s+’ to easily match all occurrences of one or more spaces and replace them with a single space.
2. Split sentences while preserving punctuation: We need to split the text into individual sentences, where each sentence is followed by punctuation (e.g., ‘.’, ‘!’, or ‘?’). The function re.split(r’([.!?])’, text) allows us to split the text based on punctuation while keeping the punctuation marks, which is crucial for proper sentence reconstruction.

Regular expressions allow us to:

• Efficiently match patterns like spaces or punctuation.
• Perform complex text transformations with minimal code.
• Handle edge cases that would otherwise require more manual handling.

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

# Assume that the argument text is a string that denotes a text,
# defined as one or more sentences, two successive
# sentences being separated by at least one space,
# the first sentence being possibly preceded with spaces,
# the last sentence being possibly followed by spaces,
# a sentence being defined as at least two words,
# two successive words in a sentence being separated by
# at least one space, a word being defined as a sequence
# of (uppercase or lowercase) letters,
# - possibly followed by a comma for a word that is
#   not the last one in its sentence,
# - definitely followed by a full stop, an exclamation mark
#   or a question mark for a word that is the last one
#   in its sentence.
import re


def f2(text):
    # Use regular expression to replace multiple spaces with a single space
    text = re.sub(r'\s+', ' ', text.strip())

    # Correct way to split sentences while preserving delimiters
    sentences = re.split(r'([.!?])', text)

    # Process sentences and punctuation separately
    new_text = []
    i = 0
    while i < len(sentences)-1:
        sentence = sentences[i].strip()
        if sentence:
            sentence =' '.join(sentence.capitalize().split())
            # Rebuild the sentence and add back the punctuation
            new_text.append(sentence +sentences[i +1])
        i += 2
    return ' '.join(new_text)

Exercise 3:

This exercise works with lists of integers and aims to repeatedly remove the first and last elements of the list as long as they are equal. The list is treated as a double-ended queue (deque) for efficient removal of elements from both ends.

Key Points:

• The deque data structure is used because it provides O(1) operations for popping elements from both ends, which is more efficient than using lists.
• The program checks if the first and last elements of the deque are equal and removes them until this condition is no longer met.
• The deque is converted back to a list before being returned.

Why is deque more efficient than list in Exercise 3?

In Exercise 3, we are frequently removing elements from both the front (left) and the back (right) of the list. This is where using a deque (double-ended queue) from Python’s collections module becomes more efficient compared to using a standard list.

Here’s why:

• List Behavior: When you use a standard list and call list.pop(0) to remove the first (leftmost) element, it requires shifting all the remaining elements one position to the left. This shift operation takes linear time—O(n), where n is the number of elements in the list. This means that for every removal from the front, the larger the list, the slower the operation becomes.

  • Removing from the right side of a list using list.pop() is an O(1) operation (constant time) because no elements need to be shifted, making it efficient only when working from the end of the list.

• Deque Behavior: A deque (double-ended queue) is specifically designed to support efficient append and pop operations from both ends. In a deque, both popleft() and pop() operations take constant time—O(1)—because the deque is implemented as a doubly linked list. This means no elements need to be shifted when popping from the left or right.

  • In Exercise 3, where we need to frequently remove elements from both ends of the list, using a deque ensures that both the removal from the left (popleft()) and the right (pop()) are performed in constant time. This makes the entire process much more efficient, especially for large lists where repeated operations would slow down if we used a standard list.

What is a deque?

A deque (short for “double-ended queue”) is a data structure that allows for fast appending and popping of elements from both ends. It is part of the collections module in Python and is optimized for scenarios where you need to efficiently add or remove elements from both ends of the sequence.

Key Features of deque:

• O(1) time complexity for operations on both ends (append, pop, appendleft, popleft).
• It is implemented as a doubly linked list, meaning each element contains a reference to both the previous and next elements, allowing efficient traversal in both directions.
• deque is ideal for scenarios where you need frequent and efficient insertions and removals from both the front and back of a sequence, unlike a standard list where such operations are costly at the front.

Standard Solution:

1
2
3
4
5
6
7

def f3(L):
# Remove the list as long as it has at least two elements and the first and last elements are equal
    while len(L) > 1 and L[0] == L[-1]:
        L.pop(0) # Remove the first element
        L.pop(-1) # Remove the last element
    return L

My Solution:

1
2
3
4
5
6
7
8
9

from collections import deque

def f3(L):
    L = deque(L)  # Convert the list to a deque for efficient popping from both ends
    # Continue removing elements while there are at least two elements and the first and last are equal
    while len(L) > 1 and L[0] == L[-1]:
        L.popleft()  # Efficiently remove the first element (O(1) operation)
        L.pop()      # Efficiently remove the last element (O(1) operation)
    return list(L)   # Convert the deque back to a list and return it

Exercise 4:

This exercise deals with lists of integers that are in increasing order. The goal is to remove any element whose value is equal to its index in the list. The program iterates over the list and removes such elements, ensuring the index is correctly adjusted after each removal.

Key Points:

• The program uses a while loop and checks if the element at index i is equal to i. If true, it removes the element and does not increment i, so that the next element at the same position is checked.
• The remove() function is used to delete the element, which is appropriate for this task.
• Care is taken to ensure that index adjustments are handled correctly.

The reason we use remove() instead of pop(0) or popleft() in a deque is that we need to specifically remove the value that matches the number we reached. pop() and popleft() remove elements by position, without considering the value, which isn’t suitable for our case.

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

# Assume that the argument L is a list of integers
# that forms an increasing sequence.
#
# For as long as some member of the list is equal to its index
# in the list, pop out the leftmost such member of the list.

def f4(L):
    i = 0
    while i < len(L):
        if L[i] == i:
            L.remove(L[i])  # Using remove() here since popleft() removes from the left only
        else:
            i += 1  # Only increment i if no element was removed
    return L

Exercise 5:

This exercise works with a circular list of integers. The task is to identify elements that are both larger than one of their adjacent elements and smaller than the other. The result is returned as a dictionary where each key is such an element, and its value is a pair of the adjacent elements (one smaller and one larger).

Key Points:

• The list is treated as circular, meaning the first element is considered adjacent to the last element.
• The program iterates through the list, compares each element with its neighbors, and stores those that meet the criteria.
• For each valid element, the adjacent smaller and larger elements are stored in a dictionary.

To solve this problem, we need to create a dictionary D where each key is an element in the list L that satisfies a certain condition, and the value is a tuple of two elements. The first element of this tuple is the adjacent element that is smaller than the current key, and the second element is the adjacent element that is larger than the current key.

Steps:

1. Loop structure: Check each element.
2. Processing of adjacent elements: Since the list is cyclic, the previous element of the first element is the last element, and the next element of the last element is the first element.
3. Condition check: Find the adjacent elements that are smaller and larger than the current element, and add them to the result dictionary.

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

# Assume that the argument L is a list of at least 3 distinct integers.
#
# Returns a dictionary D whose keys are those of the members e of L,
# if any, that are
# - smaller than the element right before or right after, and
# - larger than the element right before or right after.
# It is considered that
# - the first member of L is right after the last member of L, and
# - the last member of L is right before the first member of L
# (as if making a ring out of the list).
# For a key e in D, the associated value is the pair whose
# first element is the member of L that is right before or right after
# e and smaller than e, and whose second element is the member of L
# that is right before or right after e and greater than e.

def f5(L):
    D = {}
    for i in range(len(L)):
        m = L[i - 1]
        n = L[(i + 1) % len(L)]
        if n < m:
            m, n = n, m
        if m < L[i] < n:
            D[L[i]] = m, n
    return D

Exercise 6:

This exercise deals with factorizing an integer n into the form 2^k * m, where m is an odd number. If n is negative, the program adds a negative sign to the output. If n is zero, it prints a special message.

Key Points:

• The program uses a loop to divide n by 2 until n is no longer divisible by 2, counting the number of divisions (k).
• The absolute value of n is used to ensure correct handling of negative numbers, and a sign is added to the final result if the original number was negative.
• The program handles the special case where n = 0 by printing a unique message.

More Details:

1. You need to express the given integer n as n = 2^k * m.
   • k represents the number of times n can be divided by 2. In other words, it is the power of 2 in the factorization of n.
   • m is the remaining odd part after dividing out all factors of 2.
2. If n is negative, the output should include a negative sign.
3. Special case: If n = 0, a specific message should be printed.
4. The result is printed directly, not returned.

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

# Assume that the argument n is an integer.
#
# The output is printed out, not returned.
#
# You might find the abs() function useful.
def f6(n):
    if n == 0:
        print("0 = 2^k * 0 for all integers k!")
    else:
        k = 0
        ori = n
        if n < 0:
            sign = '-'
            n = -n
        else:
            sign = ''
        while n % 2 == 0:
            n //= 2
            k += 1
        print(f"{ori} = {sign}2^{k} * {n}")
    return

FOR VERY VERY VERY VERY VERY BIG NUMBER:

When dealing with very large integers, the method of continuously dividing the number by 2 to factor out powers of 2 (2^k) can become inefficient. This is because each division can be costly in terms of computational time, especially for very large numbers with millions or billions of digits. Each division involves recalculating the entire integer, which is slow for large integers.
Using Bit Manipulation:

A much more efficient approach is to use bit manipulation to determine how many times a number can be divided by 2 (i.e., how many factors of 2 it has). This method avoids division altogether and instead directly analyzes the binary representation of the number to count the number of trailing zeros, which correspond to the powers of 2 in the factorization.

Why?

1. Bitwise operations are much faster than arithmetic operations like division, especially for large integers. Counting the trailing zeros in a number’s binary representation can be done in constant time.

2. Extracting the lowest set bit of a number allows us to quickly find how many times a number can be divided by 2 without having to repeatedly divide the number. This provides the power of 2 (k) directly.

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

def f6(n):
    if n == 0:
        print("0 = 2^k * 0 for all integers k!")
        return
    
    # Handle negative sign
    sign = '-' if n < 0 else ''
    n = abs(n)
    
    # Using bit manipulation to count how many trailing zeros (powers of 2)
    k = (n & -n).bit_length() - 1  # Count trailing zeros by isolating the lowest set bit
    
    # Remove 2^k factor from n
    m = n >> k  # Equivalent to n // 2^k, shifting right by k bits
    
    # Print the result
    print(f"{sign}{n} = {sign}2^{k} * {m}")

Lattice-based Cryptography: Basic Example

Introduction to Lattice

In lattice-based cryptography, a lattice is a regularly spaced grid of points in space. It is formed by taking integer linear combinations of a set of vectors, called the “basis”. For this example, let’s use a 2-dimensional lattice, where the lattice points are integer combinations of two vectors.

Why Can Bad Basis Be Used for Encryption, and Good Basis for Decryption?

The core issue lies in lattice-based encryption, where information is mapped to a lattice, encrypted using the public key (Bad Basis), and finally decrypted using the private key (Good Basis). The key point here is the geometric properties of Good Basis and Bad Basis.

Encryption Process (Using Bad Basis as Public Key):

In the encryption process, the dense lattice structure generated by Bad Basis maps the message to a lattice point.
Suppose we want to encrypt a message. First, we choose a random error (noise) and then add some randomness to the message so that the encrypted message can be represented as a point in the lattice. Since the lattice structure of Bad Basis is very dense and hard to manipulate, attackers cannot directly recover the original message from the encrypted one.

Decryption Process (Using Good Basis as Private Key):

During decryption, the private key uses Good Basis. Since the basis vectors of Good Basis are orthogonal, the lattice structure is clearer and easier to manipulate, making it possible to recover the information using Good Basis.
Specifically, using Good Basis, we can find the closest lattice point (i.e., recover the original message using the decryption formula). Because the lattice structure generated by Good Basis is simple, decryption becomes very easy.

Why Can We Use Bad Basis for Encryption and Good Basis for Decryption?

The key lies in the relationship between Bad Basis and Good Basis:

Good Basis and Bad Basis are mathematically related, as they belong to the same lattice. Although the lattice structure generated by Bad Basis is more complex and dense, it is still a different representation of the lattice defined by Good Basis. Through mathematical operations, we can convert Bad Basis into Good Basis and recover information from it.

In fact, the relationship between Bad Basis and Good Basis can be obtained through matrix operations. Using specific algorithms, such as Babai’s rounding algorithm, we can use the information from Bad Basis to find the closest Good Basis point. Since the structure of Good Basis is clearer, it is easy to recover the original message using its basis vectors during decryption.

The security of lattice-based encryption relies on a mathematical problem: recovering the shortest vector (or the correct message) from a dense lattice (defined by Bad Basis) is a very difficult problem. This problem, known as the Shortest Vector Problem (SVP), is currently not efficiently solvable by existing quantum algorithms.

Explanation of Key Points

• Lattice Structure: The lattice is generated by linear combinations of basis vectors $( \mathbf{v_1} )$ and $( \mathbf{v_2} )$. In this example, the vectors are simple, but in real applications, the lattice structure is much more complex.

• Encryption: The message is transformed into a ciphertext through lattice operations, typically involving some noise or error terms (such as in LWE).

• Decryption: The secret key (a vector or some form of trapdoor information) is used to recover the original message by solving lattice-related problems.

This Markdown example is a basic introduction, and in practical lattice-based schemes, the lattice vectors, encryption, and decryption processes are far more intricate. But this should provide a simple framework for understanding the key concepts.

How to solve the problem of UNPROTECTED PRIVATE KEY FILE?

1
2
3
4
5
6
7
8
9

F:\> ssh -i "id_rsa" -p 2251 ??@??.com
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@         WARNING: UNPROTECTED PRIVATE KEY FILE!          @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Permissions for 'id_rsa' are too open.
It is required that your private key files are NOT accessible by others.
This private key will be ignored.
Load key "id_rsa": bad permissions
??@??.com: Permission denied (publickey).

So I went home and tested it with my old computer:

1. An error message appeared: ssh: The term 'ssh' is not recognized as the name of a cmdlet, function, script file, or operable program

2. Checked whether OpenSSH was installed through Get-WindowsCapability -Online | ? Name -like 'OpenSSH*', and found that Windows7 system does not natively support OpenSSH

3. Tried to solve it by installing Git Bash, but Unable to locate the program input point GetSystemTimePreciseAsFileTime on the dynamic link library KERNEL32.dll

4. Tried Release on the OpenSSH official website, and found that it could not be compiled because the api-ms-win-core-file-l1-1-0.dll file was missing in the computer

5. Cygwin official website found that it supports unsupported Windows version, https://cygwin.com/install.html

6. Win+R->cmd->setup-x86_64.exe --allow-unsupported-windows --site http://ctm.crouchingtigerhiddenfruitbat.org/pub/cygwin/circa/64bit/2024/01/30/231215 --no-verify

7. Successfully run Cygwin, set up the Tsinghua University mirror source, https://mirrors.tuna.tsinghua.edu.cn/cygwin/, select openssh, and install various C++ packages

8. It still failed, and then I found that the key file can be used after it is removed from the USB drive. . .

题目：

思想：

就排序，排完之后，两两比较后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

Exercise 1:

This exercise focuses on input validation and formatting floating-point numbers. The goal is to prompt the user to enter a floating-point number between -1 and 1 (exclusive). If the input is valid, the program rounds the number to two decimal places and prints it. Otherwise, it keeps prompting the user until a valid input is provided.
Key Points:

• The program uses a try-except block to catch invalid inputs (e.g., strings that cannot be converted to floats).
• The input() function is wrapped in an infinite while loop to continuously ask for input until the correct condition is met.

In the updated version of Exercise 1, we use the formatting :.2f instead of round(). Here’s the key difference between the two:

• round(): This is a Python built-in function that rounds a number to a specified number of decimal places. For example, round(1.236, 2) will return 1.24. However, the output of round() is still a float, but it does not guarantee a fixed number of decimal places when printed. For instance, round(1.0001, 2) would return 1.0 and only display one decimal place, not two.
• :.2f: This is part of Python’s string formatting and ensures the number is displayed with exactly two decimal places, no matter what the number is. It also rounds the number appropriately. For instance, number = 1.0 formatted as f”{number:.2f}” will print 1.00. This makes :.2f particularly useful for consistent display of decimal places, which is important for formatting output for users.

My Solution

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

while True:
    try:
        i = input('Enter a floating point number between -1 and 1 excluded: ')
        number = float(i)
        if '.' not in i:
            raise ValueError
        if -1 < number < 1:
            # not using round() here because it rounds to the nearest even number
            print(f'\nUp to +/-0.005, you input {number:.2f}')
        else:
            raise ValueError
        break
    except ValueError:
        print("You got that wrong, try again!\n")

Standard Solution

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

while True:
    try:
        x = input('Enter a floating point number between -1 and 1 excluded: ')
        if '.' not in x:
            raise ValueError
        x = float(x)
        if not (-1 < x < 1):
            raise ValueError
        break
    except ValueError:
        print('You got that wrong, try again!\n')
print(f'\nUp to +/-0.005, you input {x:.2f}')

Exercise 2:

This exercise involves processing a block of text and formatting it into sentences. Each sentence should have its first word capitalized, and the remaining words should be in lowercase. The task is to handle spaces and punctuation properly.

In other words: Modify the sentence to conform to English grammar

Standard Solution

1. Split text into a list of words.
2. Iterate through the words and apply the following rules:
   • If the word is the first word of the sentence (i.e., the first word or follows a sentence-ending punctuation mark), capitalize it.
   • If the word is not the first word of the sentence, make it lowercase.

1
2
3
4
5
6
7

def f2(text):
    words = text.split()
    for i in range(len(words)):
        # Ternary Expression
        words[i] = words[i].title() if i == 0 or words[i - 1][-1] in '.!?'\
            else words[i].lower()
    return ' '.join(words)

Key Points:

• A regular expression (re.sub) is used to replace multiple spaces with a single space.
• Another regular expression (re.split) is used to split the text into sentences while preserving punctuation marks.
• After splitting, the sentences are processed: the first word is capitalized, and all other words are made lowercase.
• Finally, the processed sentences are recombined into a single formatted text.

Why use re in Exercise 2, and what is re?

In Exercise 2, we use re (Python’s regular expression module) to process and format the text input. Let’s break down why re is used and what it is:

What is re?

re stands for regular expressions, which are powerful tools for matching patterns in strings. The re module in Python allows you to work with regular expressions to search, split, and manipulate text based on specific patterns. Regular expressions are highly flexible and efficient for handling complex string operations.

Why use re in Exercise 2?

In this exercise, we need to handle several complex text manipulations:

1. Replace multiple spaces with a single space: Sentences in the text may have irregular spaces between words, so we need to normalize these spaces. Instead of writing loops or conditions to handle each case, we use re.sub() with a pattern r’\s+’ to easily match all occurrences of one or more spaces and replace them with a single space.
2. Split sentences while preserving punctuation: We need to split the text into individual sentences, where each sentence is followed by punctuation (e.g., ‘.’, ‘!’, or ‘?’). The function re.split(r’([.!?])’, text) allows us to split the text based on punctuation while keeping the punctuation marks, which is crucial for proper sentence reconstruction.

Regular expressions allow us to:

• Efficiently match patterns like spaces or punctuation.
• Perform complex text transformations with minimal code.
• Handle edge cases that would otherwise require more manual handling.

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

# Assume that the argument text is a string that denotes a text,
# defined as one or more sentences, two successive
# sentences being separated by at least one space,
# the first sentence being possibly preceded with spaces,
# the last sentence being possibly followed by spaces,
# a sentence being defined as at least two words,
# two successive words in a sentence being separated by
# at least one space, a word being defined as a sequence
# of (uppercase or lowercase) letters,
# - possibly followed by a comma for a word that is
#   not the last one in its sentence,
# - definitely followed by a full stop, an exclamation mark
#   or a question mark for a word that is the last one
#   in its sentence.
import re


def f2(text):
    # Use regular expression to replace multiple spaces with a single space
    text = re.sub(r'\s+', ' ', text.strip())

    # Correct way to split sentences while preserving delimiters
    sentences = re.split(r'([.!?])', text)

    # Process sentences and punctuation separately
    new_text = []
    i = 0
    while i < len(sentences)-1:
        sentence = sentences[i].strip()
        if sentence:
            sentence =' '.join(sentence.capitalize().split())
            # Rebuild the sentence and add back the punctuation
            new_text.append(sentence +sentences[i +1])
        i += 2
    return ' '.join(new_text)

Exercise 3:

This exercise works with lists of integers and aims to repeatedly remove the first and last elements of the list as long as they are equal. The list is treated as a double-ended queue (deque) for efficient removal of elements from both ends.

Key Points:

• The deque data structure is used because it provides O(1) operations for popping elements from both ends, which is more efficient than using lists.
• The program checks if the first and last elements of the deque are equal and removes them until this condition is no longer met.
• The deque is converted back to a list before being returned.

Why is deque more efficient than list in Exercise 3?

In Exercise 3, we are frequently removing elements from both the front (left) and the back (right) of the list. This is where using a deque (double-ended queue) from Python’s collections module becomes more efficient compared to using a standard list.

Here’s why:

• List Behavior: When you use a standard list and call list.pop(0) to remove the first (leftmost) element, it requires shifting all the remaining elements one position to the left. This shift operation takes linear time—O(n), where n is the number of elements in the list. This means that for every removal from the front, the larger the list, the slower the operation becomes.

  • Removing from the right side of a list using list.pop() is an O(1) operation (constant time) because no elements need to be shifted, making it efficient only when working from the end of the list.

• Deque Behavior: A deque (double-ended queue) is specifically designed to support efficient append and pop operations from both ends. In a deque, both popleft() and pop() operations take constant time—O(1)—because the deque is implemented as a doubly linked list. This means no elements need to be shifted when popping from the left or right.

  • In Exercise 3, where we need to frequently remove elements from both ends of the list, using a deque ensures that both the removal from the left (popleft()) and the right (pop()) are performed in constant time. This makes the entire process much more efficient, especially for large lists where repeated operations would slow down if we used a standard list.

What is a deque?

A deque (short for “double-ended queue”) is a data structure that allows for fast appending and popping of elements from both ends. It is part of the collections module in Python and is optimized for scenarios where you need to efficiently add or remove elements from both ends of the sequence.

Key Features of deque:

• O(1) time complexity for operations on both ends (append, pop, appendleft, popleft).
• It is implemented as a doubly linked list, meaning each element contains a reference to both the previous and next elements, allowing efficient traversal in both directions.
• deque is ideal for scenarios where you need frequent and efficient insertions and removals from both the front and back of a sequence, unlike a standard list where such operations are costly at the front.

Standard Solution:

1
2
3
4
5
6
7

def f3(L):
# Remove the list as long as it has at least two elements and the first and last elements are equal
    while len(L) > 1 and L[0] == L[-1]:
        L.pop(0) # Remove the first element
        L.pop(-1) # Remove the last element
    return L

My Solution:

1
2
3
4
5
6
7
8
9

from collections import deque

def f3(L):
    L = deque(L)  # Convert the list to a deque for efficient popping from both ends
    # Continue removing elements while there are at least two elements and the first and last are equal
    while len(L) > 1 and L[0] == L[-1]:
        L.popleft()  # Efficiently remove the first element (O(1) operation)
        L.pop()      # Efficiently remove the last element (O(1) operation)
    return list(L)   # Convert the deque back to a list and return it

Exercise 4:

This exercise deals with lists of integers that are in increasing order. The goal is to remove any element whose value is equal to its index in the list. The program iterates over the list and removes such elements, ensuring the index is correctly adjusted after each removal.

Key Points:

• The program uses a while loop and checks if the element at index i is equal to i. If true, it removes the element and does not increment i, so that the next element at the same position is checked.
• The remove() function is used to delete the element, which is appropriate for this task.
• Care is taken to ensure that index adjustments are handled correctly.

The reason we use remove() instead of pop(0) or popleft() in a deque is that we need to specifically remove the value that matches the number we reached. pop() and popleft() remove elements by position, without considering the value, which isn’t suitable for our case.

Standard Solution:

1
2
3
4
5
6
7
8

def f4(L):
    i = 0
    while i < len(L):
        if L[i] == i:
            L.pop(i)
        else:
            i += 1
    return L

My Solution:

1
2
3
4
5
6
7
8

def f4(L):
    i = 0
    while i < len(L):
        if L[i] == i:
            L.remove(L[i])  # Using remove() here since popleft() removes from the left only
        else:
            i += 1  # Only increment i if no element was removed
    return L

Exercise 5:

This exercise works with a circular list of integers. The task is to identify elements that are both larger than one of their adjacent elements and smaller than the other. The result is returned as a dictionary where each key is such an element, and its value is a pair of the adjacent elements (one smaller and one larger).

Key Points:

• The list is treated as circular, meaning the first element is considered adjacent to the last element.
• The program iterates through the list, compares each element with its neighbors, and stores those that meet the criteria.
• For each valid element, the adjacent smaller and larger elements are stored in a dictionary.

To solve this problem, we need to create a dictionary D where each key is an element in the list L that satisfies a certain condition, and the value is a tuple of two elements. The first element of this tuple is the adjacent element that is smaller than the current key, and the second element is the adjacent element that is larger than the current key.

Steps:

1. Loop structure: Check each element.
2. Processing of adjacent elements: Since the list is cyclic, the previous element of the first element is the last element, and the next element of the last element is the first element.
3. Condition check: Find the adjacent elements that are smaller and larger than the current element, and add them to the result dictionary.

Standard Solution:

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

def f5(L):
    D = {}
    for i in range(len(L)):
        m = L[i - 1]
        L[i]
        # Treat it as a head-tail circular array
        n = L[(i + 1) % len(L)]
        # we don't care about the order of m and n [0,1,2,4] L[3%4==3]
        if n < m:
            m, n = n, m
        # If L[i] is between m and n, store it in the dictionary:
        if m < L[i] < n:
            D[L[i]] = m, n
    return D

L[i-1] help us to get the previous element of the current element, 0 - 1 is len(L) - 1.
and L[(i+1) % len(L)] help us to get the next element of the current element. The modulo operation (i+1) % len(L) ensures that the index wraps around to the beginning of the list when it reaches the end.

Exercise 6:

This exercise deals with factorizing an integer n into the form 2^k * m, where m is an odd number. If n is negative, the program adds a negative sign to the output. If n is zero, it prints a special message.

1
2
3
4
5
6
7
8
9
10
11

def f6(n):
    if not n:
        print('0 = 2^k * 0 for all integers k!')
        return
    k = 0
    m = n
    sign = '-' if n < 0 else ''
    while m % 2 == 0:
        m //= 2
        k += 1
    print(f'{n} = {sign}2^{k} * {abs(m)}')

• If n is negative, it keeps track of the sign.
• It repeatedly divides n by 2 while it remains even (n % 2 == 0), counting how many times this happens (k).
• The remaining number, m, must be odd, because we divide out all possible factors of 2.
• Finally, it prints the equation:
  "n = sign * 2^k * m"

FOR VERY VERY VERY VERY VERY BIG NUMBER:

When dealing with very large integers, the method of continuously dividing the number by 2 to factor out powers of 2 (2^k) can become inefficient. This is because each division can be costly in terms of computational time, especially for very large numbers with millions or billions of digits. Each division involves recalculating the entire integer, which is slow for large integers.
Using Bit Manipulation:

A much more efficient approach is to use bit manipulation to determine how many times a number can be divided by 2 (i.e., how many factors of 2 it has). This method avoids division altogether and instead directly analyzes the binary representation of the number to count the number of trailing zeros, which correspond to the powers of 2 in the factorization.

Why?

1. Bitwise operations are much faster than arithmetic operations like division, especially for large integers. Counting the trailing zeros in a number’s binary representation can be done in constant time.

2. Extracting the lowest set bit of a number allows us to quickly find how many times a number can be divided by 2 without having to repeatedly divide the number. This provides the power of 2 (k) directly.

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

def f6(n):
    if n == 0:
        print("0 = 2^k * 0 for all integers k!")
        return
    
    # Handle negative sign
    sign = '-' if n < 0 else ''
    n = abs(n)
    
    # Using bit manipulation to count how many trailing zeros (powers of 2)
    k = (n & -n).bit_length() - 1  # Count trailing zeros by isolating the lowest set bit
    
    # Remove 2^k factor from n
    m = n >> k  # Equivalent to n // 2^k, shifting right by k bits
    
    # Print the result
    print(f"{sign}{n} = {sign}2^{k} * {m}")

QUESTION：

2270. Number of Ways to Split Array.md

My Think：

2 <= nums.length <= 105, 因此我们可以直接获取到第一个数字, 初始状态就在指针于index0, 正要往index1走的时候.
然后只需要一次For循环就可以搞定

重点是第二个方法, 来自题解.

Code：

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        temp_sum = nums[0]
        total_sum = sum(nums) - temp_sum
        ans = 0
        for i in range(1, len(nums)):
            if temp_sum >= total_sum:
                ans += 1
            temp_sum += nums[i]
            total_sum -= nums[i]
        return ans

1
2

t = (sum(nums) + 1) // 2
return sum(s >= t for s in accumulate(nums[:-1]))

Notes on RSA and Diffie-Hellman

1. Mathematical Background of RSA and Diffie-Hellman

RSA

• Prime Factorization: The problem of integer factorization.
• Diffie-Hellman: The discrete logarithm problem.

Let:

$$
s \in \mathbb{Z}_n^2, a_i \in \mathbb{Z}_2^n, e_i \in \mathbb{Z}^n
$$

Define:

$$
a_i \cdot s + e_i
$$

as a certain encryption form.

For example:

$$
\mathbb{Z}_n^2 = {7, 11, 13, 15, 17, 19, 23, 27, 31}
$$

2. RSA Algorithm Steps

1. Choose two prime numbers:

   $$
   p = 3, q = 11
   $$

   Then:

   $$
   n = p \cdot q = 3 \cdot 11 = 33
   $$

   $$
   \phi(n) = (p-1)(q-1) = 2 \cdot 10 = 20
   $$

   (Computing the number of integers coprime to ( n ))

   • Since ( p, q ) are primes, for all ( a \in \mathbb{Z}^+ ), if ( a < p ), then ( \gcd(a, p) = 1 ), where ( p ) is a prime.
   • There are ( (p-1) ) and ( (q-1) ) numbers coprime to ( pq ).
   • The total count of numbers up to ( n ) is ( n = p \cdot q ), and ( n ) is divisible by ( q ) and ( p ).
   • The total count of numbers not coprime to ( n ) is ( p + q - 1 ).
   • Therefore, ( \phi(n) = n - (q + p - 1) = pq - q - p + 1 = (p-1)(q-1) ).

2. Choose a public key ( e ):

   $$
   1 < e < \phi(n), , \text{and} , \gcd(e, \phi(n)) = 1
   $$

   For example:

   $$
   e = 7
   $$

3. Compute the private key ( d ):

   $$
   d \cdot e \equiv 1 , (\text{mod} , \phi(n))
   $$

   Solving:

   $$
   d = 3
   $$

4. Public-private key pair:

   • Public key: ( (e, n) = (7, 33) )
   • Private key: ( (d, n) = (3, 33) )

3. Encryption and Decryption Process

• Suppose the plaintext is ( m = 4 ), the ciphertext ( c ) is:

  $$
  c = m^e , \text{mod} , n
  $$

  Calculation:

  $$
  c = 4^7 , \text{mod} , 33 = 16
  $$

• Decrypting to retrieve ( m ):

  $$
  m = c^d , \text{mod} , n
  $$

  Calculation:

  $$
  m = 16^3 , \text{mod} , 33 = 4
  $$

4. Proof of Correctness of Decryption

The encryption and decryption rely on the following equation:

$$
e \cdot d \equiv 1 ,(\text{mod}, \phi(n))
$$

Thus, we have:

$$
e \cdot d = 1 + k \cdot \phi(n)
$$

1. From the encryption formula:

   $$
   c = m^e ,(\text{mod}, n)
   $$

2. Using the decryption formula:

   $$
   m = c^d ,(\text{mod}, n)
   $$

3. Substituting ( c ) from the encryption equation:

   $$
   m = (m^e)^d ,(\text{mod}, n)
   $$

4. Consolidating the exponent:

   $$
   m = m^{e \cdot d} ,(\text{mod}, n)
   $$

5. Since ( e \cdot d = 1 + k \cdot \phi(n) ):

   $$
   m = m^{1 + k \cdot \phi(n)} ,(\text{mod}, n)
   $$

6. Applying Euler’s theorem:

   $$
   m^{\phi(n)} \equiv 1 ,(\text{mod}, n)
   $$

7. Simplifying:

   $$
   m^{1 + k \cdot \phi(n)} \equiv m^1 \cdot (m^{\phi(n)})^k ,(\text{mod}, n)
   $$

8. Since ( m^{\phi(n)} \equiv 1 ):

   $$
   m^{1 + k \cdot \phi(n)} \equiv m ,(\text{mod}, n)
   $$

Thus, decryption is correct.

LWD:
$$
\left{ \left(a_i, \langle a_i, s \rangle + e_i \right) : s \gets \mathbb{Z}_q^n, a_i \gets \mathbb{Z}q^n, e_i \gets \chi \right}{i=1}^m
$$

1. ( \mathbb{Z} = \mathbb{Z}/q \mathbb{Z} ) represents a finite ring modulo ( q ).
2. ( \chi ) is a probability distribution over ( \mathbb{Z} ), used to generate “small numbers” (noise).

• Uniform Distribution: ( \chi ) randomly generates integer values from the range [−B, B] (e.g., [−5,5]), where ( B \ll q/2 ).
  The assumption ( B \ll q/2 ) ensures that the noise ( e_i ) does not obscure the modulated result during decryption.
• Discrete Gaussian Distribution: Another common distribution, denoted as ( D_{\mathbb{Z}, \sigma} ), with standard deviation ( \sigma ), used to generate near-zero random noise values.

( a \gets D ): a is randomly sampled (or generated) from probability distribution D.
( a \gets S ): When S is a finite set, a is randomly and uniformly selected from S.

( a_i \in \mathbb{Z}_q^n ): This denotes an ( n )-dimensional vector space modulo ( q ), where each component belongs to ( \mathbb{Z}_q ).

QUESTION：

2241. Design an ATM Machine.md
There is an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.

When withdrawing, the machine prioritizes using banknotes of larger values.

For example, if you want to withdraw $300 and there are 2 $50 banknotes, 1 $100 banknote, and 1 $200 banknote, then the machine will use the $100 and $200 banknotes.
However, if you try to withdraw $600 and there are 3 $200 banknotes and 1 $500 banknote, then the withdraw request will be rejected because the machine will first try to use the $500 banknote and then be unable to use banknotes to complete the remaining $100. Note that the machine is not allowed to use the $200 banknotes instead of the $500 banknote.
Implement the ATM class:

ATM() Initializes the ATM object.
void deposit(int[] banknotesCount) Deposits new banknotes in the order $20, $50, $100, $200, and $500.
int[] withdraw(int amount) Returns an array of length 5 of the number of banknotes that will be handed to the user in the order $20, $50, $100, $200, and $500, and update the number of banknotes in the ATM after withdrawing. Returns [-1] if it is not possible (do not withdraw any banknotes in this case).

My Think：

The purpose of this question is to simulate an ATM machine, which returns the amount of money you withdraw, no more and no less. I am greedy, because the second sentence “There are 3 $200 bills and 1 $500 bill in the machine, so the withdrawal request will be rejected”
This shows that we can skip thinking about the knapsack problem in complex dynamic programming and directly consider simple greed.

Because the denominations of the deposited money are only 20, 50, 100, 200, 500, we can store them in the list in advance and wait for traversal.

Then we create a defaultdict() to create a hash table for each denomination in the ATM machine.

deposit() creates a reverse traversal dictionary. Because we need to traverse the dictionary from large denominations to small denominations, the reverse dictionary is very convenient at this time.

Assuming the initial amount is 600, the first denomination traversed is 500, It fits the logic of the question very well

For the withdraw() function, I created a temporary dictionary deep copy storage so that the initial array will not be changed when [-1] is returned. Otherwise, it will be troublesome to backtrack.

Here, Sylvia and I used two different traversal methods. She traversed the list of denominations, while I traversed the dictionary directly (actually traversed the key directly).

1. If the current denomination (600) is greater than the current denomination (500), then try to deduct it. If the bank money is withdrawn directly, then look at the next denomination.

2. If it is not withdrawn, then amount deducts the deductible share and then continues to look at the next denomination.

3. If there is still amount left at the end, return [-1], otherwise calculate how many bills have been consumed in total, which is the answer.

这道题的目的是模拟一台ATM机器, 让你取多少钱, 就返回多少钱, 不能多也不能少. 我是贪心的思想, 因为第二句”机器里有 3 张 $200 的钞票和1 张 $500 的钞票，那么取款请求会被拒绝”
这就说明我们可以跳过思考复杂的动态规划中的背包问题, 而直接考虑简单的贪心.

因为存的钱的面额只有20, 50, 100, 200, 500 这五种面额, 于是我们提前存在列表里面等待遍历即可.
然后我们创建一个defaultdict(), 为ATM机器里面的每种面额创建哈希表.

deposit()创建了一个反向遍历的字典. 因为我们需要从大面额到小面额遍历字典, 在这个时候反向的字典就很方便.

假设初始`amount`为`600`, 遍历到的第一个面额就是`500`, 就很符合题目的逻辑

withdraw()函数, 我之所以创建了一个临时字典深拷贝储存是在返回[-1]的情况下不更改初始数组. 否则还要回溯挺麻烦的.

这里我和Sylvia用了两种不同的遍历方式, 她遍历了面额的列表, 而我是直接遍历的字典(实际上直接遍历的key).

1. 如果当前面额(600)大于了当前面额(500), 那就尝试扣除, 如果直接把银行钱取完了, 那再看下一个面值.
2. 如果没有取完, 那么amount扣除掉能扣除的份额, 再继续看下一个面额即可.
3. 到最后amount还有剩余则返回[-1], 否则计算一共消耗了多少张钞票, 即是答案了.

Code：

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
37
38
39
40
41
42

import copy
from typing import List

from collections import defaultdict


class ATM:

    def __init__(self):
        self.sd = defaultdict(int)
        self.amount = ['20', '50', '100', '200', '500']

    def deposit(self, banknotesCount: List[int]) -> None:
        for i in range(len(banknotesCount) - 1, -1, -1):
            self.sd[self.amount[i]] += banknotesCount[i]



    def withdraw(self, amount: int) -> List[int]:
        tempSd = copy.deepcopy(self.sd)
        # key = 面值, value = 张数
        for key, value in tempSd.items():
            if amount >= int(key) and value > 0:
                # 需要多少张钞票
                howManyPiece = amount // int(key)
                if howManyPiece >= value:
                    # 全部取出来
                    tempSd[key] = 0
                    amount -= value * int(key)
                else:
                    # 取出这么多钞票
                    tempSd[key] -= howManyPiece
                    amount -= int(key) * howManyPiece
        else:
            if amount > 0:
                return [-1]
            else:
                ans = []
                for i in self.sd.keys():
                    ans.append(self.sd[i] - tempSd[i])
                self.sd = copy.deepcopy(tempSd)
                return ans[::-1]

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

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