目录

1. 最大公约数和最小公倍数  ★

2. 最小路径和  ★★

3. 二叉树的锯齿形层序遍历  ★★★

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

1. 最大公约数和最小公倍数

本题要求两个给定正整数的最大公约数和最小公倍数。

输入格式：
输入在两行中分别输入正整数x和y。
输出格式：
在一行中输出最大公约数和最小公倍数的值。

输入样例：
100
1520
输出样例：
20 7600

代码：

def hcf(x, y):if x > y:smaller = yelse:smaller = x for i in range(1,smaller + 1):if((x % i == 0) and (y % i == 0)):hcf = i return hcfdef lcm(x, y): if x > y:greater = xelse:greater = ywhile(True):if((greater % x == 0) and (greater % y == 0)):lcm = greaterbreakgreater += 1return lcmnum1 = int(input("输入第一个数字: "))
num2 = int(input("输入第二个数字: "))
print("最大公约数为",hcf(num1, num2),"最小公倍数为",lcm(num1,num2))

以上是原题中给出的循环暴力求解的代码，其实求最大公约数最好应该用辗转相除法。以下是我以前写过的多种方法的总结：

方法一：for循环

def GCD(m, n):gcd = 1 # 此行可以省略for i in range(1,min(m, n)+1):if m%i==0 and n%i==0:gcd = ireturn gcdprint(GCD(81,3))
print(GCD(81,15))
print(GCD(81,54))

方法二：while循环

def GCD(m, n):while m!=n:if m>n: m -= nelse: n -= mreturn mprint(GCD(81,3))
print(GCD(81,15))
print(GCD(81,54))

方法三：递归法

def GCD(m, n):if n==0: return mreturn GCD(n, m%n)print(GCD(81,3))
print(GCD(81,15))
print(GCD(81,54))

方法四：辗转相除法

def GCD(m, n):while n!=0:m, n = n, m%nreturn mprint(GCD(81,3))
print(GCD(81,15))
print(GCD(81,54))

方法五：递减法

def GCD(m, n):gcd = min(m, n)while m%gcd or n%gcd:gcd -= 1return gcdprint(GCD(81,3))
print(GCD(81,15))
print(GCD(81,54))

方法六：库函数math.gcd

from math import gcdprint(gcd(81,3))
print(gcd(81,15))
print(gcd(81,54))

或者：直接用 import('math').gcd

__import__('math').gcd(81,3)
__import__('math').gcd(81,15)
__import__('math').gcd(81,54)

方法七：约分法，库函数fractions.Fraction()

def GCD(m, n):from fractions import Fractionreturn m//Fraction(m, n).numerator #取分子#return n//Fraction(m, n).denominator #或取分母print(GCD(81,3))
print(GCD(81,15))
print(GCD(81,54))

 辗转相除法：

用来求两个正整数最大公约数的算法，计算公式gcd(a,b) = gcd(b,a mod b)。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法，所以也被命名为欧几里得算法。

最小公倍数则可以用公式 lcm(a,b) * gcd(a,b) = a*b 来求得。

2. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

代码：

class Solution(object):def minPathSum(self, grid):""":type grid: List[List[int]]:rtype: int"""height = len(grid)if height == 0:return 0width = len(grid[0])pathmap = []for i in range(height):pathmap.append([100000000000] * width)pathmap[0][0] = grid[0][0]for i in range(height):for j in range(width):compare = [pathmap[i][j]]if i - 1 >= 0:compare.append(pathmap[i - 1][j] + grid[i][j])if j - 1 >= 0:compare.append(pathmap[i][j - 1] + grid[i][j])pathmap[i][j] = min(compare)return pathmap[-1][-1]# %%
s = Solution()
print(s.minPathSum(grid = [[1,3,1],[1,5,1],[4,2,1]]))
print(s.minPathSum(grid = [[1,2,3],[4,5,6]]))

输出：

7
12

递归法：

def minPathSum(grid, i=0, j=0):sum1, sum2 = 0, 0m, n = len(grid), len(grid[0])if i < m-1:sum1 += minPathSum(grid, i + 1, j) + grid[i][j]if j < n-1:sum2 += minPathSum(grid, i, j + 1) + grid[i][j]if i == m-1 and j == n-1:return grid[m-1][n-1]if sum1 == 0:return sum2elif sum2 == 0:return sum1else:return min(sum1, sum2)print(minPathSum(grid = [[1,3,1],[1,5,1],[4,2,1]]))
print(minPathSum(grid = [[1,2,3],[4,5,6]]))

3. 二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：给定二叉树 [3,9,20,null,null,15,7],

     3/ \9  20/  \
15   7

返回锯齿形层序遍历如下：

[
[3],
[20,9],
[15,7]
]

代码：

class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def zigzagLevelOrder(self, root: TreeNode) -> list:import collectionsif not root:return []res, q = [], collections.deque()flag = Falseq.append(root)while q:temp = []flag = not flagfor _ in range(len(q)):node = q.popleft()if flag:temp.append(node.val)else:temp.insert(0, node.val)if node.left:q.append(node.left)if node.right:q.append(node.right)res.append(temp)return resdef listToTree(lst: list) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
root = listToTree([3,9,20,null,null,15,7])
print(s.zigzagLevelOrder(root))

输出：

[[3], [20, 9], [15, 7]]

说明：

zigzagLevelOrder()方法中flag标识初始值设置为False是关键，如果初始值设为True，就是反向的Z字形遍历。去掉flag标记，就是正常的层序遍历：

class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def LevelOrder(self, root: TreeNode) -> list:import collectionsif not root:return []res, q = [], collections.deque()q.append(root)while q:temp = []for _ in range(len(q)):node = q.popleft()temp.append(node.val)if node.left:q.append(node.left)if node.right:q.append(node.right)res.append(temp)return resdef listToTree(lst: list) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return root# %%
s = Solution()
null = None
root = listToTree([1,2,3,4,5,6,7,8,9])
print(s.LevelOrder(root))

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏