刷题记录合辑

一篇记录多题：思路 → 代码 → 优化 → 总结 → 相关题目
标题不含题号，题号写在正文与 description 中。

122. 买卖股票的最佳时机

思路
代码

思路
贪心算法
如果天与天之间的收益查，两个坐标之间的值之和表示在左坐标买右坐标买所得到的收益

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0 
        size = len(prices)
        if size == 0:
            return 0 
        for i in range(1,size):
            if prices[i]-prices[i-1] > 0:
                res = res + prices[i] - prices[i-1]
        return res

总结

376. 摆动序列

思路
代码
不同解法
题解

思路

尝试1 找波峰: 错误
找到摆动数列其实就是找波峰，也就是找到满足一下条件的元素nums[i]:
nums[i] > nums[i-1] && nums[i] < nums[i+1]
或者
nums[i] < nums[i-1] && nums[i] > nums[i+1]

尝试2 动态规划:
使用动态规划，维护两个dp状态，dp[i][j][]

这个方法是错误的,因为我只统计了作为波峰或者波谷的数量，但是事实上两边都应该纳入参考同时要避免重合

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        size = len(nums)
        res1 = 0
        res2 = 0
        for i in range(1,size-1):
            if nums[i] > nums[i-1] and nums[i] < nums[i+1]:
                res1 = res1 + 1
            if nums[i] < nums[i-1] and nums[i] > nums[i+1]:
                res2 = res2 + 1
        return max(res1,res2)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for part in path.split('/'):
            if part in ('', '.'):
                continue
            if part == '..':
                if stack:
                    stack.pop()
            else:
                stack.append(part)
        return '/' if not stack else '/' + '/'.join(stack)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for part in path.split('/'):
            if part in ('', '.'):
                continue
            if part == '..':
                if stack:
                    stack.pop()
            else:
                stack.append(part)
        return '/' if not stack else '/' + '/'.join(stack)

总结
关注三类特殊片段：''、'.'、'..'；用栈实现路径归约。

相关题目

    1. 矩阵置零（原地矩阵操作）
    1. 移动零（数组重排模板）
    1. 旋转图像（矩阵原地旋转）
    1. 二叉树的右视图（层序/DFS）

知识点小结

  • 栈：路径归约、括号匹配、表达式求值等
  • 模拟：生命游戏、棋盘/网格类，边界与状态编码是关键
  • 原地更新：位或标记减少额外空间
  • 位运算技巧：状态压缩、掩码读取
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。