Python 入门小编程

几个python入门小编程题目

1）

# Missing Number
# Given n and a list nums of all numbers 1, 2, ..., n omitting one number, find the missing number.
# https://cses.fi/problemset/task/1083


def find_missing_number(n, nums):
    pass

find_missing_number(5, [2, 3, 1, 5]) # Correct answer: 4

解决这个问题，最自然想到的办法是用循环一个一个找出。但时间复杂度是O(n^2)：

def find_missing_number(n, nums):
    for i in range(1,n+1):
        if i not in nums:
            return i


find_missing_number(5, [2, 3, 1, 5]) # Correct answer: 4

优化版本：时间复杂度O(n)

def find_missing_number(n, nums):
    return (1+n)*n/2 - sum(nums)


find_missing_number(5, [2, 3, 1, 5]) # Correct answer: 4

2）

# Trailing Zeros
# Given n, find the number of trailing zeros in the factorial n!
# https://cses.fi/problemset/task/1618

def find_trailing_zeros(n):
    pass

find_trailing_zeros(10) # Correct answer: 2

解决方法：一个数的阶乘（例如 n!）末尾零的数量是由该数分解中包含的 2 和 5 的对数决定的。由于因子 2 比因子 5 更常见，所以末尾零的数量实际上是由因子 5 的数量决定的。为了找到一个数的阶乘中因子 5 的数量，我们可以不断地将该数除以 5，并将这些商相加，直到商为零。

def find_trailing_zeros(n):
    count = 0
    while n >= 5:
        n //= 5
        count += n
    return count

find_trailing_zeros(10) # Correct answer: 2

3）

# Maximum Subarray Sum
# Given an array, find the maximum sum of values in a contiguous, nonempty subarray
# https://cses.fi/problemset/task/1643

def max_subarray_sum(array):
    pass

max_subarray_sum([-1, 3, -2, 5, 3, -5, 2, 2]) # Correct answer: 9

最自然的解决方法是循环：但时间复杂度为O(n^2)

def max_subarray_sum(array):
    max = array[0]
    for i in range(len(array)):
        for j in range(i, len(array)):
            temp = sum(array[i:j+1])
            if temp > max:
                max = temp
    return max

max_subarray_sum([-1, 3, -2, 5, 3, -5, 2, 2]) # Correct answer: 9

优化：用动态规划，时间复杂度O(n)

def max_subarray_sum(array):
    max_so_far = array[0]
    max_ending_here = 0
    max_element = array[0]

    for i in range(len(array)):
        max_ending_here = max(array[i], max_ending_here+array[i])
        max_so_far = max(max_so_far, max_ending_here)
        if max_ending_here < 0:
            max_ending_here = 0
        if array[i] > max_element:
            max_element = array[i]

    return max_so_far if max_so_far > 0 else max_element

max_subarray_sum([-1, 3, -2, 5, 3, -5, 2, 2]) # Correct answer: 9

4）

# Sum of Two Values
# Given an array of integers, return positions of two values (at distinct positions) summing to x. 
# If there are no solutions, print IMPOSSIBLE.
# https://cses.fi/problemset/task/1640. Also known as "Two Sum" in LeetCode.

def sum_of_two_values(x, array):
    pass

sum_of_two_values(8, [2, 7, 5, 1]) # Correct answer: [1, 3]

自然的想法是两层循环，但时间复杂度为O(n^2)

def sum_of_two_values(x, array):
    for i in range(len(array)):
        for j in range(i+1, len(array)):
            if x == array[i] + array[j]:
                return[i, j]
    print('IMPOSSIBLE')

sum_of_two_values(8, [2, 7, 5, 1]) # Correct answer: [1, 3]

优化：用哈希表，时间复杂度为O(n)， 但空间复杂度从O(1)变成O(n)

def sum_of_two_values(x, array):
    seen = {}
    for i, number in enumerate(array):
        complement = x - number
        if complement in seen:
            return [seen[complement], i]
        seen[number] = i
    print('IMPOSSIBLE')

sum_of_two_values(8, [2, 7, 5, 1]) # Correct answer: [1, 3]

python官方的网址，可供查找：The Python Tutorial — Python 3.12.1 documentation?????

?