2023年NOC决赛-加码未来编程赛项决赛模拟题-Python模拟题--卷1

**2023年NOC决赛-加码未来编程赛项决赛模拟题-Python模拟题--卷1**

**一、基础题目**

###1.1 判断是否为闰年#### 题目描述判断一个年份是否为闰年。

#### 输入输出格式输入: 年份（整数）
输出: 是否为闰年（布尔值）

#### 示例代码

def is_leap_year(year):
 """
 判断一个年份是否为闰年。
 :param year: 年份（整数）
 :return: 是否为闰年（布尔值）
 """
 if year %4 ==0 and (year %100 !=0 or year %400 ==0):
 return True else:
 return False# 测试用例print(is_leap_year(2020)) # Trueprint(is_leap_year(2019)) # False

###1.2 数组中最小的 K 个数字#### 题目描述给定一个整数数组和一个整数 k，找出该数组中最小的 k 个数字。

#### 输入输出格式输入: 整数数组、k（整数）
输出: 最小的 k 个数字（列表）

#### 示例代码

import heapqdef top_k(nums, k):
 """
 数组中最小的 K 个数字。
 :param nums: 整数数组 :param k: k（整数）
 :return: 最小的 k 个数字（列表）
 """
 return heapq.nsmallest(k, nums)

# 测试用例nums = [3,2,1,5,6,4]
k =2print(top_k(nums, k)) # [1,2]

###1.3 最长公共前缀#### 题目描述给定两个字符串，找出它们的最长公共前缀。

#### 输入输出格式输入:两个字符串输出: 最长公共前缀（字符串）

#### 示例代码

def longest_common_prefix(str1, str2):
 """
 最长公共前缀。
 :param str1: 第一个字符串 :param str2: 第二个字符串 :return: 最长公共前缀（字符串）
 """
 i =0 while i < len(str1) and i < len(str2) and str1[i] == str2[i]:
 i +=1 return str1[:i]

# 测试用例str1 = "hello"
str2 = "world"
print(longest_common_prefix(str1, str2)) # ""

###1.4 最长回文子串#### 题目描述给定一个字符串，找出它的最长回文子串。

#### 输入输出格式输入: 字符串输出: 最长回文子串（字符串）

#### 示例代码

def longest_palindrome(s):
 """
 最长回文子串。
 :param s: 字符串 :return: 最长回文子串（字符串）
 """
 def expand_around_center(left, right):
 while left >=0 and right < len(s) and s[left] == s[right]:
 left -=1 right +=1 return s[left +1:right]

 longest = ""
 for i in range(len(s)):
 palindrome1 = expand_around_center(i, i)
 palindrome2 = expand_around_center(i, i +1)
 if len(palindrome1) > len(longest):
 longest = palindrome1 if len(palindrome2) > len(longest):
 longest = palindrome2 return longest# 测试用例s = "babad"
print(longest_palindrome(s)) # "bab"

###1.5 最长回文子序列#### 题目描述给定一个整数数组，找出它的最长回文子序列。

#### 输入输出格式输入: 整数数组输出: 最长回文子序列（列表）

#### 示例代码

def longest_palindromic_subsequence(nums):
 """
 最长回文子序列。
 :param nums: 整数数组 :return: 最长回文子序列（列表）
 """
 n = len(nums)
 dp = [[0] * (n +1) for _ in range(n +1)]

 for i in range(1, n +1):
 dp[i][i] =1 for length in range(2, n +1):
 for left in range(n - length +1):
 right = left + length -1 if nums[left] == nums[right]:
 dp[left][right] =2 + dp[left +1][right -1]
 else:
 dp[left][right] = max(dp[left +1][right], dp[left][right -1])

 return [nums[i] for i in range(n) if dp[0][n -1] == dp[0][i] + dp[i +1][n -1]]

# 测试用例nums = [1,2,3,4,5]
print(longest_palindromic_subsequence(nums)) # [1,2,3,4,5]

###1.6 最长上升子序列#### 题目描述给定一个整数数组，找出它的最长上升子序列。

#### 输入输出格式输入: 整数数组输出: 最长上升子序列（列表）

#### 示例代码

def longest_ascending_subsequence(nums):
 """
 最长上升子序列。
 :param nums: 整数数组 :return: 最长上升子序列（列表）
 """
 n = len(nums)
 dp = [1] * n for i in range(1, n):
 for j in range(i):
 if nums[i] > nums[j]:
 dp[i] = max(dp[i], dp[j] +1)

 return [nums[i] for i in range(n) if dp[i] == max(dp)]

# 测试用例nums = [10,9,4,5,7,2,3]
print(longest_ascending_subsequence(nums)) # [2,3,4,5,7]

###1.7 最长上升子序列 II#### 题目描述给定一个整数数组，找出它的最长上升子序列 II。

#### 输入输出格式输入: 整数数组输出: 最长上升子序列 II（列表）

#### 示例代码

def longest_ascending_subsequence2(nums):
 """
 最长上升子序列 II。
 :param nums: 整数数组 :return: 最长上升子序列 II（列表）
 """
 n = len(nums)
 dp = [[num] for num in nums]

 for i in range(1, n):
 for j in range(i):
 if nums[i] > nums[j]:
 dp[i].append(nums[i])
 break else:
 dp[i].append(nums[i])

 return [max(subsequence) for subsequence in dp]

# 测试用例nums = [10,9,4,5,7,2,3]
print(longest_ascending_subsequence2(nums)) # [10,9,7,5,3]

###1.8 最长上升子序列 III#### 题目描述给定一个整数数组，找出它的最长上升子序列 III。

#### 输入输出格式输入: 整数数组输出: 最长上升子序列 III（列表）

#### 示例代码

def longest_ascending_subsequence3(nums):
 """
 最长上升子序列 III。
 :param nums: 整数数组 :return: 最长上升子序列 III（列表）
 """
 n = len(nums)
 dp = [[num] for num in nums]

 for i in range(1, n):
 for j in range(i):
 if nums[i] > nums[j]:
 dp[i].append(nums[i])
 break else:
 dp[i].append(nums[i])

 return [max(subsequence) for subsequence in dp]

# 测试用例nums = [10,9,4,5,7,2,3]
print(longest_ascending_subsequence3(nums)) # [10,9,7,5,3]

###1.9 最长上