题目：

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

Exercise 1

Problem Description:

You are given two integers, m and n, where:

• m represents the number of repeated units (patterns).
• n represents the number of elements (underscores) within each unit.

The goal is to generate a string where:

• Each unit contains n underscores (_), separated by |.
• These units are then concatenated together, separated by *.

My Solution:

1
2
3
4
5

def generate_struct(n):
    return '|'.join(n * ['_'])

def f1(m, n):
    return ' * '.join(m * [generate_struct(n)])

My Thought Process:

I think of each unit as a separate structure. So, I decompose the problem by breaking down the smallest unit, which is the structure made of underscores joined by |.
After constructing each unit, I use join() to combine them together using *.

Helper Function generate_struct(n):

This function generates the basic structure.
It creates a list of underscores (_) of length n and joins them with |.
Example: If n = 2, the result will be “_|_“.

Standard Solution:

1
2

def f1(m, n):
    return ' * '.join('|'.join('_' for _ in range(n)) for _ in range(m))

Concise Expression:

The inner join creates a string of n underscores joined by | using a generator expression ('_' for _ in range(n)).
The outer join repeats this process m times and concatenates the units using *.

In summary, my solution focuses on modularity by breaking down the problem into smaller parts (like creating a structural unit), whereas the standard solution compresses everything into one line using list comprehensions.

Exercise 2

Problem Description:

The goal is to generate a pattern based on the digits of a given number n. Specifically:

If a digit is odd, it should be represented by a black square (⬛).
If a digit is even, it should be represented by a white square (⬜).
The program takes a number n as input and prints a string of squares corresponding to the digits of n.

My Solution:

1
2
3
4
5
6
7
8

def f2(n):
    ans = ''
    for i in str(n):
        if int(i) % 2 == 0:
            ans += '⬜'
        else:
            ans += '⬛'
    print(ans)

My Thought Process:

1. Loop through each digit:
   Convert the number n to a string to iterate over each digit individually.

2. Check if the digit is even or odd:
   Convert each digit back to an integer and use the modulus operator (% 2) to check if the digit is even or odd.

3. Append the corresponding square:

   • If the digit is even, append a white square (⬜) to the result string.
   • If the digit is odd, append a black square (⬛).

4. Print the final string:
   After processing all the digits, print the final string containing black and white squares.

Standard Solution:

1
2

def f2(n):
    print(''.join({0: '\u2b1c', 1: '\u2b1b'}[int(d) % 2] for d in str(n)))

Dr.Martin’s solution is:

1. More compact and Pythonic.
2. Uses a dictionary and list comprehension for brevity and efficiency.
3. The Unicode characters for the squares are referenced directly using their escape sequences (\u2b1c for white, \u2b1b for black).

Exercise 3

Problem Description:

In this task, the number n is treated as a number expressed in different bases (ranging from 2 to 10), and we aim to convert it into its corresponding base 10 value for each of these bases, where the conversion is valid.

For n = 2143:

• 2143 in base 5 is equivalent to 298 in base 10.
• 2143 in base 6 is equivalent to 495 in base 10.
• And so on.

The goal is to iterate over different base systems from 2 to 10, treat the input number n as if it is expressed in each base, and then convert it to base 10.

My Solution:

1
2
3
4
5
6
7
8

def f3(n: int):
    for i in range(2, 11):
        try:
            # Treat n as a number in base i and convert it to base 10
            value = int(str(n), i)
            print(f'{n} is {value} in base {i}')
        except ValueError:
            pass

My Thought Process:

1. Iterating over Bases (2 to 10):

   • We loop through the base values i ranging from 2 to 10.

2. Conversion Using int():

   • For each base i, we treat the number n as a number in that base. To do this, we first convert n to a string (str(n)) and then use int() to interpret it as a base i number.
   • If the digits of n are valid for base i, this conversion succeeds, and the result is the base 10 equivalent of n.
   • If the digits of n are not valid for base i (for example, if base 2 is used and n contains digits greater than 1), a ValueError is raised, and we skip the invalid base.

3. Handling Errors with try-except:

   • The try-except block ensures that invalid bases are skipped, allowing us to handle cases where the digits in n are not valid for a particular base.

Standard Solution:

1
2
3
4
5

def f3(n):
    n_as_string = str(n)
    min_base = max(2, max({int(d) for d in n_as_string}) + 1)
    for b in range(min_base, 11):
        print(f'{n} is {int(n_as_string, b)} in base {b}')

It skips the bases where the digits in n are not valid, and it uses a set comprehension to extract the unique digits from n_as_string. The maximum digit is then used to determine the minimum base to start iterating from.

Exercise 4

Problem Description:

The task is to create a function f4(n, base) that returns a dictionary D, where:

Keys are integers from 0 to n.
Values are tuples that represent the base base representation of each key, converted from base 10.

My Solution:

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

def convert_to_base(n, base):
    if n == 0:
        return '0'
    digits = []
    while n:
        digits.append(str(n % base))
        n //= base
    return ''.join(digits[::-1])

def f4(n: int, base: int):
    D = {}
    for i in range(0, n + 1):
        D[i] = tuple(map(int, convert_to_base(i, base)))
    return D

My Thought Process:

1. Helper Function convert_to_base(n, base):

   • This function converts a number n from base 10 to the specified base.
   • We use a while loop to repeatedly take the modulus (n % base) and append the remainder to the list digits.
   • We then divide n by base (n //= base) to reduce it for the next iteration.
   • After collecting all digits, we reverse the list and return it as a string.

2. Main Function f4(n, base):
   We initialize an empty dictionary D.
   For each number i from 0 to n, we convert i to the given base using convert_to_base().
   The converted base digits are then mapped to integers and stored in a tuple as the value for each key i in the dictionary.

Explanation of Why map() is not Pythonic:

In the function f4, the use of map(int, convert_to_base(i, base)) applies the int function
to each element of the result from convert_to_base, effectively converting each character to an integer.

However, it’s worth noting that the map() function, which originates from functional programming,
has largely been superseded by more Pythonic constructs such as list comprehensions.

These comprehensions are generally considered superior for several reasons:

• They are more elegant and concise.
• They tend to be shorter in terms of syntax, making the code easier to read.
• They are easier to understand for most people, especially those who are more familiar with Python’s
  standard syntax rather than functional programming constructs.
• In many cases, they are also more efficient in terms of performance.

For example, instead of using map(int, ...), the same functionality could be achieved with a
list comprehension, like so:

D[i] = tuple([int(digit) for digit in convert_to_base(i, base)])

This list comprehension achieves the same result but follows a more modern Pythonic style.

Standard Solution:

1
2
3
4
5
6
7
8
9
10

def f4(n, base):
    D = {0: (0,)}
    for m in range(1, n + 1):
        digits = []
        p = m
        while p:
            digits.append(p % base)
            p //= base
        D[m] = tuple(reversed(digits))
    return D

Both solutions are valid and achieve the same result. My approach uses a helper function for base conversion, which adds modularity,
whereas the standard solution is more concise and directly integrates the conversion logic into the main function.

Exercise 5

At the first, try to run this:

1

print(0.1 + 0.2)

What happened? The result is not 0.3, but 0.30000000000000004. Why?

Problem Description:

The approach we are using in this exercise is designed to expose the limitations of floating-point arithmetic in computers. Let’s break down why this approach leads to precision inaccuracies and why other methods might not reveal these issues as clearly.

This problem can seem complex, and it’s designed to highlight the subtleties of floating-point arithmetic. Let’s walk through the logic using the test cases to figure out what the function does.

Key Concepts:

• Floating-point numbers: Computers store floating-point numbers using a binary format, which often introduces precision errors.
• Precision: We’re working with two types of precision in this function—simple precision (same as the length of the fractional part) and double precision (twice that length).

Solution:

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

def f5(integral_part, fractional_part):
    # Calculate the number of digits in the fractional part
    precision = len(str(fractional_part))
    
    # Concatenate the integral and fractional parts as strings, then convert to a float
    a_float = float(str(integral_part) + '.' + str(fractional_part))
    
    # Format the float with precision equal to the number of digits in the fractional part (simple precision)
    simple_precision = f'{a_float:.{precision}f}'
    
    # Append a number of zeros equal to the fractional part length to the simple precision value (extended precision)
    extended_simple_precision = simple_precision + '0' * precision
    
    # Format the float with precision equal to twice the number of fractional digits (double precision)
    double_precision = f'{a_float:.{precision * 2}f}'
    
    # Print the first part of the output
    print('With', precision * 2, 'digits after the decimal point, ', end='')
    
    # Compare if extended precision and double precision values are the same
    if extended_simple_precision == double_precision:
        # If they are the same, it means the float is precise and has trailing zeros
        print(simple_precision, 'prints out with', precision, 'trailing',
              precision == 1 and 'zero,' or 'zeroes,', 'namely, as',
              extended_simple_precision
             )
    else:
        # If not, there is a precision error, and no trailing zeros
        print(simple_precision, 'prints out as', double_precision)

Our function attempts to check and display this floating point error with simple precision (simple_precision) and double precision (double_precision). The error becomes more obvious when we represent floating point numbers with higher precision (double the number of decimal places). So in this way, we show that floating point numbers are not always actually stored as we expect them to be with more precise representation.

Exercise 6

Problem Description:

In this task, we are given:

• A list L, which contains multiple sub-lists of integers, and all sub-lists have the same length n.
• A list fields, which is a permutation of {1, ..., n}.

We are required to sort the list L by using a multi-key sorting mechanism, where:

• First, the elements in L are sorted based on the position given by the first element of fields.
• If two sub-lists are equal based on the first field, we move to the second field, and so on.
• Finally, if required, the sorting proceeds up to the last field in fields.

Example of Fields Explanation:

If fields = [2, 1], it means:

1. First, sort based on the second element of each sublist.
2. If there are ties (same values in the second position), sort based on the first element.

My Solution:

1
2

def f6(L, fields):
    return sorted(L, key=lambda x: [x[i-1] for i in fields])

1. Sorting with sorted():
   The sorted() function is used to sort the list L.
   The key parameter defines how the sorting will be performed.

2. Lambda Function:
   The lambda function defines how the sublists will be sorted. It generates a list of values for each sublist based on the positions specified in fields.
   For example, if fields = [2, 1], the lambda function will extract the second and first elements from each sublist in that order, and sorting will be done based on this new list.

3. Key Structure:
   The key is a list of elements from each sublist, indexed by the positions specified in fields. We use x[i - 1] because fields is 1-based, and list indexing in Python is 0-based.

4. What is Lambda Function?

For example:

We have:

1

f = lambda x: x * x

This is equivalent to:

1
2

def f(x):
    return x * x

And lambda function in a sorted function is used to define a custom sorting key.

1
2
3
4
5

L = [(1,2), (3,1), (5,0)]

SortedL = sorted(L, key=lambda x: x[1])

print(SortedL)

The result is: [(5, 0), (3, 1), (1, 2)], it sorts the list based on the second element of each tuple.

Standard Solution:

1
2

def f6(L, fields):
    return sorted(L, key=lambda x: tuple(x[i - 1] for i in fields))

Why Use a Tuple?:

• Tuples are often preferred for multi-key sorting because they are immutable, and Python’s built-in sorting functions can efficiently compare tuples.
• Each sublist is transformed into a tuple of its elements based on the order defined by fields. The sorted() function then uses these tuples to sort the list.

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}")

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:

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}")

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. . .

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.

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

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 ).