Python算法-模拟过程实现算法

6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P A H N
A P L S I I G
Y I R

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2: 
            return s
        res = ["" for _ in range(numRows)]
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1: 
                flag = -flag
            i += flag
        return "".join(res)

思路参考：https://leetcode-cn.com/problems/zigzag-conversion/solution/zzi-xing-bian-huan-by-jyd/

661. 图片平滑器

图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。

每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。

如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。

class Solution:
    def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
        row = len(img)
        col = len(img[0])
        # 形成一个row*col的零矩阵
        ans = [[0]*col for _ in range(row)]
        for i in range(row):
            for j in range(col):
                # 池化总和与数量
                total, num = 0, 0
                # 需要判断是否有缺失
                for x in range(max(i-1, 0), min(i+2, row)):
                    for y in range(max(j-1, 0), min(j+2, col)):
                        total += img[x][y]
                        num += 1
                # 更新矩阵(取整数计算)
                ans[i][j] = total//num
        return ans

946. 验证栈序列

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        index = 0
        for num in pushed:
            stack.append(num)
            # 当栈不为空且栈顶元素与出栈元素对应，则说明发生了出栈操作
            while stack and stack[-1] == popped[index]:
                stack.pop()
                index += 1
        # 判断栈是否为空
        return not stack