AcWing语法基础课【Python3】版题解-函数/类和对象/常用库
【AcWing 0x00. 语法基础课【Python3】版题解-顺序/判断/循环语句】
【AcWing 0x01. 语法基础课【Python3】版题解-内置数据结构/字符串】
【AcWing 0x02. 语法基础课【Python3】版题解-函数/类和对象/常用库】
函数
例题
def factorial(n):
res = 1
for i in range(1, n+1):
res *= i
return res
n = int(input())
print(factorial(n))
解析：用循环求阶乘。
def myMax(x, y):
return x if x > y else y
x, y = map(int, input().split())
print(myMax(x, y))
解析：用三目运算符实现求最大值。
def myGCD(a, b):
divisor = 1
ran = min(a, b)
for i in range(1, ran+1):
if a % i == 0 and b % i == 0:
divisor = i
return divisor
a, b = map(int, input().split())
print(myGCD(a, b))
解析：用循环求最大公约数。
def mySwap(x, y):
x, y = y, x
return x, y
x, y = map(int, input().split())
s = mySwap(x, y)
print(s[0], s[1])
解析：Python3函数可以以元组的形式返回多个值。
def printSize(a, size):
return a[:size]
n, size = map(int, input().split())
a = list(map(int, input().split()))
for i in printSize(a, size):
print(i, end=' ')
解析：使用列表切片返回前size个数。
def print2D(matrix, row, col):
for i in range(row):
for j in range(col):
print(matrix[i][j], end=" ")
print()
row, col = map(int, input().split())
matrix = [list(map(int, input().split())) for i in range(row)]
print2D(matrix, row, col)
解析：用双重循环遍历并打印矩阵。
def factorial(n):
if n == 1:
return 1
return n * factorial(n-1)
n = int(input())
print(factorial(n))
解析：阶乘数列通项公式为Fn=n×Fn−1,F1=1。
def fibonacci(n):
if n == 1 or n == 2:
return 1
return fibonacci(n-1) + fibonacci(n-2)
n = int(input())
print(fibonacci(n))
解析：斐波那契数列通项公式为Fn=Fn−1+Fn−2,F1=F2=1，此为递归求解。
习题
def myAbs(x):
return x if x >= 0 else -x
x = int(input())
print(myAbs(x))
解析：直接模拟。
def myAdd(x, y):
return x + y
x, y = map(float, input().split())
print(f"{myAdd(x, y):.2f}")
解析：直接模拟。
def mySum(l, r):
return sum(range(l, r+1))
l, r = map(int, input().split())
print(mySum(l, r))
解析：直接模拟。
def lcm(a, b):
gcd = lambda a, b: a if b == 0 else gcd(b, a % b)
return a * b // gcd(a, b)
a, b = map(int, input().split())
print(lcm(a, b))
解析：先求出最大公因数gcd（用lambda表达式），然后再求最小公倍数lcm。
def copy(a, b):
b[:size] = a[:size]
n, m, size = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
copy(a, b)
for num in b:
print(num, end=" ")
解析：Python的列表是引用，可以直接用列表切片对其修改。
import sys
def myPrint(str):
sys.stdout.write(str)
str = input()
myPrint(str)
解析：在Python中调用print时，事实上调用了sys.stdout.write(obj+'\n')。
def reverse(a, size):
a[:size] = a[:size][::-1]
n, size = map(int, input().split())
a = list(map(int, input().split()))
reverse(a, size)
for num in a:
print(num, end=" ")
解析：列表使用切片法翻转创建了一个副本，故反转后还需赋值一次。
def get_unique_count(a):
return len(set(a))
n = int(input())
a = list(map(int, input().split()))
print(get_unique_count(a))
解析：集合（set）是一个无序的不重复元素序列，set(iterable) 创建一个集合，len(set) 计算集合元素的个数。
def sort(a, l, r):
b = a[l: r + 1]
b.sort();
a[l: r + 1] = b
n, l, r = map(int, input().split())
a = list(map(int, input().split()))
sort(a, l, r)
for num in a:
print(num, end=" ")
解析：直接对切片调用sort() 方法会生成一个副本，故先把切片赋值给新列表，对其排序后再赋值回原列表。
def plan(n, m):
if m == n:
return 1
elif m > n:
return 0
else:
return plan(n, m + 1) + plan(n, m + 2)
n = int(input())
print(plan(n, 0))
解析：记总台阶数为n，当前所在台阶数为m，则m < n 时没走到头，继续往上走；m == n 时恰好走完，记为一种方案；m > n 时，该走法错误，方案不成立。
def plan(n, m, i, j):
if i == n and j == m:
return 1
elif i > n or j > m:
return 0
else:
return plan(n, m, i + 1, j) + plan(n, m, i, j + 1)
n, m = map(int, input().split())
print(plan(n, m, 0, 0))
解析：记终点坐标为(n, m)，当前所在台阶为(i, j)，则i <= n, j <= m （i，j不同时取等）时没走到终点，继续走；i == n, j == m 时走到终点，记为一种方案；i > n 或j > m 时，已经走出范围，方案不成立。
def enumerate(n, index, permutation, hashtable):
if index == n:
for num in permutation:
print(num + 1, end=" ")
print()
return
for i in range(n):
if hashtable[i] == False:
permutation[index] = i
hashtable[i] = True
enumerate(n, index + 1, permutation, hashtable)
hashtable[i] = False
n = int(input())
permutation = [0 for i in range(n)]
hashtable = [False for i in range(n)]
enumerate(n, 0, permutation, hashtable)
解析：列表permutation存放当前已经排好的数字，hashtable标示下标的数字是否已经被选择，在枚举到第index位时，首先枚举1~n，如果当前枚举的数字还没被选择，则选择它加入到数字排列中，并将其标示为已被选择，然后递归枚举第index+1位。
import itertools
n = int(input())
nums = list(range(1, n + 1))
for it in itertools.permutations(nums, n):
for i in range(n):
print(it[i], end=" ")
print()
解析：调用标准库 itertools 里的 permutations() 函数生成全排列。
类和对象
例题
class Solution(object):
def Fibonacci(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
elif n == 1 or n == 2:
return 1
else:
f = f0 = 1
for i in range(2, n):
f, f0 = f + f0, f
return f
解析：斐波那契数列通项公式为Fn=Fn−1+Fn−2,F1=F2=1，此为递推求解。
AcWing用户【Worzeny_Mud 】给出的解答非常优美，值得学习【AcWing 21. 斐波那契数列（python全服最短）】
class Solution(object):
def replaceSpaces(self, s):
"""
:type s: str
:rtype: str
"""
str = ""
for character in s:
if character == " ":
str = str + "%20"
else:
str = str + character
return str
解析：遍历原字符串中的所有字符，如果遇到空格就换成”%20”并归入新字符串。
class Solution(object):
def getSum(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
return n + self.getSum(n - 1)
解析：简单递归。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void
"""
if node.next != None:
node.val = node.next.val
node.next = node.next.next
解析：单链表不能在O(1)时间内找到当前结点的前驱结点，可将下一个结点的值复制到当前结点，然后将下一个节点删除。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def merge(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
p = head = ListNode(None)
while l1 != None and l2 != None:
if l1.val <= l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
p.next = l2 if l1 == None else l1
return head.next
解析：双指针合并两个有序链表，比较两个指针当前所指结点的值，并把值比较小的结点归入新链表，且指针后移一位。有一个链表移动到末尾时，直接把另一个链表剩下的结点归入新链表。
习题
class Solution(object):
def leftRotateString(self, s, n):
"""
:type s: str
:type n: int
:rtype: str
"""
return s[n:] + s[:n]
解析：Python内置的字符串切片可以直接实现。
class Solution(object):
def strToInt(self, str):
"""
:type str: str
:rtype: int
"""
if len(str) == 0 or type(str) != type(""):
return 0
symbol, numstr = "", ""
weight, num = 1, 0
INT_MIN = - 2 ** 31
INT_MAX = 2 ** 31 - 1
for i in range(len(str)):
if ord("0") <= ord(str[i]) <= ord("9"):
if i == 0:
pass
else:
if ord(str[i-1]) < ord("0") or ord(str[i-1]) > ord("9"):
if str[i-1] != " " and str[i-1] != "+" and str[i-1] != "-":
return 0
numstr = str[i] + numstr
if str[i] == "+" or str[i] == "-":
symbol = str[i]
for n in numstr:
num += weight * (ord(n) - ord("0"))
weight *= 10
if symbol == "-":
num = -1 * num
if num < INT_MIN:
return INT_MIN
elif num > INT_MAX:
return INT_MAX
else:
return num
解析：首先判断参数是否为字符串或字符串长度是否为0，如果是则直接返回0；其次判断字符串中的数字是否符合题意，如果字符串中第一个数字前的字符是”+”、”-“或” “，或者字符串中第一个数字前没有字符，则字符串中的数字符合题意，否则直接返回0。然后取出原字符串中的数字字符串并把每一个数位转变成对应的整数，得到所求整数。
迭代版：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 迭代版
if head == None or head.next == None:
return head
virtual = ListNode(None)
virtual.next, p, head.next = head, head.next, None
while p != None:
q = p.next
p.next = virtual.next
virtual.next = p
p = q
return virtual.next
解析：迭代法，首先设置一个虚拟头结点指向原本头结点，指针p指向原本头结点的下一个结点，令原本头结点指向None；从p开始遍历链表，把当前结点用头插法插入到虚拟头结点后面；最后返回虚拟头结点的下一个结点，即链表反转后的第一个结点。
递归版：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 递归版
if head == None or head.next == None:
return head
tail = self.reverseList(head.next)
head.next.next = head
head.next = None
return tail
解析：递归版，递归边界为head为None或head为单结点；如果未到递归边界，则递归翻转以head.next为头结点的链表，并把现头结点head归入到反转后链表的尾结点之后，而以head.next为头结点的链表反转后尾结点正是head.next，再把head结点的下一个结点设置为None，返回原链表的尾结点即可。
错误解法：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def findFirstCommonNode(self, headA, headB):
"""
:type headA, headB: ListNode
:rtype: ListNode
"""
p1 = headA
while p1 != None:
p2 = headB
while p2 != None:
if p1 == p2:
return p1
p2 = p2.next
p1 = p1.next
return None
这道题不能二重循环来枚举判断是否存在公共结点，会 Time Limit Exceeded ，需要优化。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def findFirstCommonNode(self, headA, headB):
"""
:type headA, headB: ListNode
:rtype: ListNode
"""
p1 = headA
p2 = headB
while p1 != p2:
if p1 != None:
p1 = p1.next
else:
p1 = headB
if p2 != None:
p2 = p2.next
else:
p2 = headA
return p1
解析：双指针法，令p1，p2分别指向headA和headB，同时开始遍历。p1从headA开始遍历，遍历完headA再遍历headB，p2从headB开始遍历，遍历完headB再遍历headA，如果有交点，两个指针会同时遍历到交点处，如果没有交点，两个指针会同时遍历到None。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplication(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
virtual = ListNode(None)
virtual.next = head
pre = virtual
p = head
while p != None:
while p.next != None and p.val == p.next.val:
p = p.next
if pre.next != p:
pre.next = p.next
else:
pre = pre.next
p = p.next
return virtual.next
解析：双指针法，设置一个虚拟头结点，指针pre指向虚拟头结点，指针p指向head结点。遍历链表，首先让p移动到重复区间的最后一位（无重复元素即当前位），具体步骤是判断p的下一个结点的值是否与p的值相等，如果相等，则p后移到下一个结点；其次判断pre的下一个结点是否是p所指结点，如果不是，则把pre的下一个结点指向p的下一个结点（去除重复区间），如果不是，让pre后移一位；让p指针后移一位，遍历完成后返回虚拟头结点的下一个结点，即链表去重后的第一个结点。
常用库
例题
class Solution(object):
def getNumberOfK(self, nums, k):
"""
:type nums: list[int]
:type k: int
:rtype: int
"""
# return nums.count(k)
count = 0
for num in nums:
if num == k:
count += 1
return count
解析：实现一个计数器即可。
class Solution(object):
def getMissingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0 or nums[0] != 0:
return 0
elif nums[-1] != len(nums):
return nums[-1] + 1
for i in range(len(nums) - 1):
if nums[i] + 1 != nums[i + 1]:
return nums[i] + 1
解析：简单模拟，注意边界的处理。
class Solution(object):
def reOrderArray(self, array):
"""
:type array: List[int]
:rtype: void
"""
i, j = 0, len(array) - 1
while i < j:
while array[i] % 2 == 1:
i += 1
while array[j] % 2 == 0:
j -= 1
if i < j:
array[i], array[j] = array[j], array[i]
解析：双指针法，左右指针分别从数组首尾向中间扫描直到相遇，左指针遇到奇数就递增，直到遇到偶数为止，右指针遇到偶数就递减，直到遇到奇数为止，然后判断两个指针位置是否合理，合理就交换数组元素。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def printListReversingly(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
nums= []
while head != None:
nums.append(head.val)
head = head.next
nums.reverse()
return nums
解析：遍历链表并用列表存储链表结点的值，返回反转后的列表。
class MyQueue(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.stk = []
self.cache = []
def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: void
"""
self.stk.append(x)
def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
while self.stk:
self.cache.append(self.stk.pop())
ans = self.cache.pop()
while self.cache:
self.stk.append(self.cache.pop())
return ans
def peek(self):
"""
Get the front element.
:rtype: int
"""
while self.stk:
self.cache.append(self.stk.pop())
ans = self.cache.pop()
self.stk.append(ans)
while self.cache:
self.stk.append(self.cache.pop())
return ans
def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return not self.stk
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
解析：用两个栈stk和cache来模拟队列，stk是主栈，cache是辅助栈，插入（push(x)）的时候直接插入到主栈里面；弹出（pop()）的时候先把主栈的元素全部压入辅助栈，然后弹出并记录辅助栈的栈顶元素，再把辅助栈的元素压入主栈，并返回记录；返回队首元素（peek()）的过程和pop()一致，但是记录完辅助栈的栈顶元素，要将其再压入主栈；判空（empty()）只需返回主栈是否非空即可。
习题
class Solution(object):
def getLeastNumbers_Solution(self, input, k):
"""
:type input: list[int]
:type k: int
:rtype: list[int]
"""
input.sort()
return input[:k]
解析：先排序后切片。
class Solution(object):
def maxInWindows(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
maxs = []
for i in range(len(nums) - k + 1):
maxi = float("-inf")
for j in range(i, i + k):
if nums[j] > maxi:
maxi = nums[j]
maxs.append(maxi)
return maxs
解析：遍历滑动窗口，取最大值填入列表中。
import itertools
class Solution:
def permutation(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
per_0 = list(itertools.permutations(nums))
per = set([p for p in per_0])
# 这里取了个巧，没把数字序列转换成list，直接用tuple了
ans = list(per)
return ans
解析：先用itertools库的permutations函数生成输入数字的全排列（包含重复项），再用set去重，最后把set转换为list即可
class Solution(object):
def NumberOf1(self,n):
"""
:type n: int
:rtype: int
"""
count = 0
lowbit = lambda x: x & - x
if n < 0:
n = n & 0xffffffff
while n > 0:
n -= lowbit(n)
count += 1
return count
解析：首先考虑n是非负数的情况，负数在计算机中用其绝对值的补码来表示，相当于把其绝对值的每一位都取反，然后末位加1，这等价于直接把其绝对值最右边的1左边的每一位都取反，因此 lowbit(x)=x & −x 就是取x的二进制最右边的1和它右边的所有0，因此，n能够减去lowbit(n)而大于0的次数，就是正数n的二进制形式中1的个数。
然后考虑n是负数的情况，因为为Python3没有位数的概念，所以就会把lowbit函数求得的负数视为了正数，直接使用lowbit函数+循环来统计1的个数会陷入死循环（只有Python3有这个问题，C++没有）。对于负数，我们要想使用lowbit函数，就需要得到与负数的绝对值的补码这一字符串相同的正数，然后求这个正数的二进制中1的个数，就间接得到了原负数的二进制表示中1的个数。由于Python3没有32位或者64位整数的说法，只有可无限扩展的长整数，考虑数据范围，我们把该数据视为一个32位整数，将其与0xffffffff这个32位的全1数字按位与，就得到了与原负数的绝对值的补码这一字符串相同的正数，然后再对这个正数求二进制形式中1的个数即可。
N = int(input())
tuples = [tuple(input().split()) for i in range(N)]
for tup in sorted(tuples, key=lambda tup: int(tup[0])): print(tup[0], tup[1], tup[2])
解析：key 形参用来指定在进行比较前要在每个列表元素上调用的函数（或其他可调用对象），可参考【官方文档示例：sorted()对tuples排序】。
