2020 年
作者 19级lf；修改 20-软工-高歌
def func1(s): result = 0 vowel_set = {'a', 'e', 'i', 'o', 'u'} for i in s.lower(): # 全部转成小写 if i in vowel_set: result += 1 return resultdef func1(s): return sum(i in {'a', 'e', 'i', 'o', 'u'} for i in string.lower())def func2(lst): lst.sort() result = lst[1] - lst[0] for i in range(1, len(lst) - 1): result = max(result, lst[i + 1] - lst[i]) return resultdef func2(lst): return max(j - i for i, j in zip(sorted(lst)[:-1], sorted(lst)[1:]))def func3(f): def gcd(m, n): # 辗转相除法求最大公约数 return gcd(n % m, m) if n % m != 0 else m if f == 0: return (0, 1) n = len(str(f).split('.')[1]) # 获得小数部分位数 x, y = f * 10 ** n, 10 ** n # 求最大公因数 m = gcd(x, y) return (int(x / m), int(y / m))def func4(lst): def calculate(s): n = len(s) dct = {} for c in s: # 统计字符c在单词中的出现次数 dct[c] = dct.get(c, 0) + 1 E = 0 for fi in dct.values(): # 计算熵值E pi = fi / n E += pi * math.log2(pi) return E lst.sort(key=calculate) return lstdef func4(lst): return sorted(lst, key=lambda s: sum((fi / len(s)) * math.log2(fi / len(s)) for fi in {c: s.count(c) for c in set(s)}.values()))
def func5(matrix): result = [] while matrix: result += matrix.pop(0) # 取矩阵第一行并删除 matrix = list(zip(*matrix))[::-1] # 旋转矩阵 return resultdef func5(matrix): if not matrix or not matrix[0]: return list() rows, columns = len(matrix), len(matrix[0]) visited = [[False] * columns for _ in range(rows)] total = rows * columns order = [0] * total directions = [[0, 1], [1, 0], [0, -1], [-1, 0]] row, column = 0, 0 directionIndex = 0 for i in range(total): order[i] = matrix[row][column] visited[row][column] = True nextRow, nextColumn = (row + directions[directionIndex][0], column + directions[directionIndex][1]) if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]): directionIndex = (directionIndex + 1) % 4 row += directions[directionIndex][0] column += directions[directionIndex][1] return orderdef func5(matrix): result = [] if matrix is None: return result top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1 while True: for i in range(left, right + 1): # ➡️ result.append(matrix[top][i]) top += 1 if top > bottom: break for i in range(top, bottom + 1): # ⬇️ result.append(matrix[i][right]) right -= 1 if right < left: break for i in range(right, left - 1, -1): # ⬅️ result.append(matrix[bottom][i]) bottom -= 1 if bottom < top: break for i in range(bottom, top - 1, -1): # ⬆️ result.append(matrix[i][left]) left += 1 if left > right: break return resultdef func6(DC, k): students = {} for subject in DC.values(): # 建立 {学生学号:选课数目} 的字典 for stu in subject: students[stu] = students.get(stu, 0) + 1 result = [] for stu in students.items(): # 将符合条件的学生学号加入结果 if stu[1] == k: result.append(stu[0]) result.sort(reverse=True) # 降序排列 return resultdef func7(n): # 动态规划完全背包问题 (空间优化版本) money = [1, 2, 5, 10] result = [1] + [0] * n for i in money: for j in range(i, n + 1): result[j] += result[j - i] return result[n]def func7(n): def go(n): if n < 0: return set() elif n == 0: return {(0, 0, 0, 0)} else: result = set() for t in go(n-1): result.add((t[0] + 1, t[1], t[2], t[3])) for t in go(n-2): result.add((t[0], t[1] + 1, t[2], t[3])) for t in go(n-5): result.add((t[0], t[1], t[2] + 1, t[3])) for t in go(n-10): result.add((t[0], t[1], t[2], t[3] + 1)) return result return len(go(n))def func7(n): cache = {} def go(n): if n in cache: return cache[n] else: if n < 0: result = set() elif n == 0: result = {(0, 0, 0, 0)} else: result = set() for t in go(n-1): result.add((t[0] + 1, t[1], t[2], t[3])) for t in go(n-2): result.add((t[0], t[1] + 1, t[2], t[3])) for t in go(n-5): result.add((t[0], t[1], t[2] + 1, t[3])) for t in go(n-10): result.add((t[0], t[1], t[2], t[3] + 1)) cache[n] = result return result return len(go(n))>>> from timeit import timeit # 动态规划 >>> timeit(lambda: func7(25), number=100) 9.99927520751953e-06 # 暴力（无缓存） >>> timeit(lambda: func7(25), number=100) 0.6817917537689209 # 暴力（带缓存） >>> timeit(lambda: func7(25), number=100) 0.00043999433517456055def func8(s): pattern = re.compile('(\d{1,3}(,\d\d\d)*(\.\d+)?)') wordtuple = pattern.findall(s) wordlist = [] for tuple in wordtuple: for word in tuple: wordlist.append(word) break def str2num(word): word = word.replace(',', '') return eval(word) wordlist.sort(key=str2num) return wordlist
总结
最后更新于