提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

Python每日一练(20230317)

Python 每日
2023-09-14 09:01:29 时间

目录

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

2. 最小路径和  ★★

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

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

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

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

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

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

代码：

def hcf(x, y):
   if x > y:
       smaller = y
   else:
       smaller = x 
   for i in range(1,smaller + 1):
       if((x % i == 0) and (y % i == 0)):
           hcf = i 
   return hcf

def lcm(x, y): 
   if x > y:
       greater = x
   else:
       greater = y
   while(True):
      if((greater % x == 0) and (greater % y == 0)):
         lcm = greater
         break
      greater += 1
   return lcm

num1 = int(input("输入第一个数字: "))
num2 = int(input("输入第二个数字: "))
print("最大公约数为",hcf(num1, num2),"最小公倍数为",lcm(num1,num2))

以上是原题中给出的循环暴力求解的代码，其实求最大公约数最好应该用辗转相减法或者辗转相除法。

方法一：循环

def GCD(m, n):
    gcd = 1 # 此行可以省略
    for i in range(1,min(m, n)+1):
        if m%i==0 and n%i==0:
            gcd = i
    return gcd

print(GCD(81,3))
print(GCD(81,15))
print(GCD(81,54))

方法二：辗转相减法

def GCD(m, n):
    while m!=n:
        if m>n: m -= n
        else: n -= m
    return m
        
print(GCD(81,3))
print(GCD(81,15))
print(GCD(81,54))

方法三：辗转相减法 递归方式

def GCD(m,n):
	if m>n: return GCD(m-n,n)
	if m<n: return GCD(m,n-m)
	return m
        
print(GCD(81,3))
print(GCD(81,15))
print(GCD(81,54))

方法四：辗转相除法

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

 方法五：辗转相除法 递归方式

def GCD(m, n):
    if n==0: return m
    return GCD(n, m%n)
        
print(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 -= 1
    return gcd
        
print(GCD(81,3))
print(GCD(81,15))
print(GCD(81,54))

方法七：库函数math.gcd

from math import gcd

print(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 Fraction
    return 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 0
        width = 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, 0
    m, 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 sum2
    elif sum2 == 0:
        return sum1
    else:
        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 = x
        self.left = None
        self.right = None

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> list:
        import collections
        if not root:
            return []
        res, q = [], collections.deque()
        flag = False
        q.append(root)
        while q:
            temp = []
            flag = not flag
            for _ 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 res
    
def listToTree(lst: list) -> TreeNode:
    if not lst:
        return None
    root = TreeNode(lst[0])
    queue = [root]
    i = 1
    while i < len(lst):
        node = queue.pop(0)
        if lst[i] is not None:
            node.left = TreeNode(lst[i])
            queue.append(node.left)
        i += 1
        if i < len(lst) and lst[i] is not None:
            node.right = TreeNode(lst[i])
            queue.append(node.right)
        i += 1
    return 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 = x
        self.left = None
        self.right = None

class Solution:
    def LevelOrder(self, root: TreeNode) -> list:
        import collections
        if 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 res
    
def listToTree(lst: list) -> TreeNode:
    if not lst:
        return None
    root = TreeNode(lst[0])
    queue = [root]
    i = 1
    while i < len(lst):
        node = queue.pop(0)
        if lst[i] is not None:
            node.left = TreeNode(lst[i])
            queue.append(node.left)
        i += 1
        if i < len(lst) and lst[i] is not None:
            node.right = TreeNode(lst[i])
            queue.append(node.right)
        i += 1
    return 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每日一练 专栏

相关文章