旺崽的博客

要么天赋异禀，要么天道酬勤

0%

发表于 分类于 Valine：

题目链接

现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。

在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

示例 1：

在这里插入图片描述

1
2
3
4
5
6
7
8
输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。

示例 2：

在这里插入图片描述

1
2
3
4
5
6
输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。 
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。 
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。

根据最短路径构造一颗新树，然后用树上 DP 求非相邻节点的最大路径和，将这条路径和减半即可得到最终答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append((b, price[b]))
            g[b].append((a, price[a]))

        def dijkstra_path(start, end):  # 存储最短路径
            dist = [float('inf')] * n
            dist[start] = 0
            heap = [(0, start, [])]
            while heap:
                d, u, path = heapq.heappop(heap)
                if u == end:
                    return path + [u]
                if d > dist[u]:
                    continue
                for v, w in g[u]:
                    if dist[u] + w < dist[v]:
                        dist[v] = dist[u] + w
                        heapq.heappush(heap, (dist[v], v, path + [u]))
            return []

        price_n = [0] * n
        for s, e in trips:
            path = dijkstra_path(s, e)
            for node in path:
                price_n[node] += price[node]
        dp = [[0] * 2 for _ in range(51)]
        for i in range(n):
            dp[i][1] = price_n[i]

        def dfs(x, f):
            for y, _ in g[x]:
                if y != f:
                    dfs(y, x)
                    dp[x][1] += dp[y][0]
                    dp[x][0] += max(dp[y][1], dp[y][0])

        dfs(0, -1)
        return sum(price_n) - max(dp[0][0], dp[0][1]) // 2

发表于 分类于 Valine：

题目链接

给你一个有 n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中
edges[i] = [fromi, toi, edgeCosti] 表示从 fromi 到 toi 有一条代价为 edgeCosti 的边。

请你实现一个 Graph 类：

  • Graph(int n, int[][] edges) 初始化图有 n 个节点，并输入初始边。
  • addEdge(int[] edge) 向边集中添加一条边，其中 edge = [from, to, edgeCost]
    。数据保证添加这条边之前对应的两个节点之间没有有向边。
  • int shortestPath(int node1, int node2) 返回从节点 node1 到 node2 的路径 最小 代价。如果路径不存在，返回
    -1 。一条路径的代价是路径中所有边代价之和。
    示例 1：
    在这里插入图片描述
1
2
3
4
5
6
7
8
9
10
11
12
输入：
["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]
输出：
[null, 6, -1, null, 6]

解释：
Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);
g.shortestPath(3, 2); // 返回 6 。从 3 到 2 的最短路径如第一幅图所示：3 -> 0 -> 1 -> 2 ，总代价为 3 + 2 + 1 = 6 。
g.shortestPath(0, 3); // 返回 -1 。没有从 0 到 3 的路径。
g.addEdge([1, 3, 4]); // 添加一条节点 1 到节点 3 的边，得到第二幅图。
g.shortestPath(0, 3); // 返回 6 。从 0 到 3 的最短路径为 0 -> 1 -> 3 ，总代价为 2 + 4 = 6 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Graph:
    def __init__(self, n: int, edges: List[List[int]]):
        self.n = n
        self.graph = [[] for _ in range(n)]  # 邻接表
        for u, v, c in edges:
            self.graph[u].append((v, c))

    def addEdge(self, edge: List[int]) -> None:
        u, v, c = edge
        self.graph[u].append((v, c))

    def shortestPath(self, node1: int, node2: int) -> int:
        dist = [-1] * self.n  # 最短距离数组，初始为-1
        dist[node1] = 0
        visited = [False] * self.n  # 记录节点是否被访问过
        pq = [(0, node1)]  # 小根堆，记录最短距离和节点编号
        while pq:
            cur_dist, cur_node = heapq.heappop(pq)
            if visited[cur_node]:  # 跳过已经访问过的节点
                continue
            visited[cur_node] = True
            if cur_node == node2:  # 找到终点，直接返回
                return dist[node2]
            for next_node, next_dist in self.graph[cur_node]:
                if visited[next_node]:  # 跳过已经访问过的节点
                    continue
                if dist[next_node] == -1 or cur_dist + next_dist < dist[next_node]:
                    dist[next_node] = cur_dist + next_dist
                    heapq.heappush(pq, (dist[next_node], next_node))
        return -1  # 没有找到路径

发表于 更新于 分类于 Valine：

题目链接

给你一棵二叉树的根 root ，请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 。

如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 堂兄弟 。
请你返回修改值之后，树的根 root 。
注意，一个节点的深度指的是从树根节点到这个节点经过的边数。

示例 1：

在这里插入图片描述

1
2
3
4
5
6
7
8
9
输入：root = [5,4,9,1,10,null,7]
输出：[0,0,0,7,7,null,11]
解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 5 的节点没有堂兄弟，所以值修改为 0 。
- 值为 4 的节点没有堂兄弟，所以值修改为 0 。
- 值为 9 的节点没有堂兄弟，所以值修改为 0 。
- 值为 1 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。
- 值为 10 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。
- 值为 7 的节点有两个堂兄弟，值分别为 1 和 10 ，所以值修改为 11 。

示例 2：

在这里插入图片描述

1
2
3
4
5
6
输入：root = [3,1,2]
输出：[0,0,0]
解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 3 的节点没有堂兄弟，所以值修改为 0 。
- 值为 1 的节点没有堂兄弟，所以值修改为 0 。
- 值为 2 的节点没有堂兄弟，所以值修改为 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        q = deque([root])
        cnt = Counter()  # 存当前节点所有儿子节点的值的和
        father = dict()  # 存每个节点的父亲节点
        father[root] = 0  # 根节点的父亲节点
        cnt[0] = root.val
        while q:
            tmp = q
            q = []
            s = sum(node.val for node in tmp)  # 求当前层所有节点的值的和
            for node in tmp:
                if node.left:
                    cnt[node] += node.left.val
                    father[node.left] = node
                    q.append(node.left)
                if node.right:
                    cnt[node] += node.right.val
                    father[node.right] = node
                    q.append(node.right)
                node.val = s - cnt[father[node]]
        return root

发表于 分类于 Valine：

毕设用 Flask 框架开发了一个 Web 网站 ，在开发过程中遇到了很多问题，今天这里做一个总结，避免以后遇到同样的问题。

问题 1

1
2
# 问题代码
Error: While importing 'xxx', an ImportError was raised.

import 语句有误，检查所有 py 文件里的 import 语句，可能的错误一种是包名有误，另一种是引用其他 py 文件里的函数时需要给出完整路径 “项目名.文件夹名.文件名.函数名” 的形式
注意直接使用 flask run 指令运行项目时报错很模糊，可以直接在编译器上运行 app.py 文件，这样可以获得比较清晰的错误提示

问题 2

1
云服务器上用 flask run 命令运行项目后，本地输入云服务器 ip 无法访问

在运行指令后加上主机地址以监听所有外部请求，如下所示：

1
flask run --host=0.0.0.0

问题 3

1
2
# 问题代码
TypeError: Rule.__init__() got an unexpected keyword argument 'method'

视图函数的装饰器里的 method 漏了 s，如下所示：

1
2
# 错误代码
user_bp.route('/settings/data', method=['GET', 'POST'])

问题 4

1
2
# 问题代码
AssertionError: View function mapping is overwriting an existing endpoint function: blog.change_theme

函数名重复，文件中有两个 change_theme 函数

问题 5

1
TypeError: The view function for 'xxx' did not return a valid response. The function either returned None or ended without a return statement.

视图函数中的 return 位置有误，通常是多余的 tab 键导致函数缺少返回语句

问题 6

1
2
3
4
# 错误代码
TypeError: 'bool' object is not callable
# 错误处
if current_user.is_admin()

注意属性和方法的区别，属性不需要加括号，方法需要加括号

问题 7

1
2
# 错误代码
Method Not Allowed.The method is not allowed for the requested URL.

视图函数里只有 post 方法而没有 request 方法，所以直接访问会报错

问题 8

1
2
3
4
5
6
7
# 错误代码
RuntimeError
RuntimeError: Working outside of request context.

This typically means that you attempted to use functionality that needed
an active HTTP request. Consult the documentation on testing for
information about how to avoid this problem.

flask 中的 request 对象只能在视图函数下使用，在其他地方使用会报错

问题 9

1
2
# 错误代码
sqlalchemy.exc.OperationalError: (pymysql.err.OperationalError) (2003, "Can't connect to MySQL server on '@rm-bp1o019zha4dfz18h2o.mysql.rds.aliyuncs.com' ([Errno 11003] getaddrinfo failed)")

因为 password 中有特殊字符导致无法正常连接数据库，一般是密码中含有 @ 字符，修改密码即可解决

问题 10

1
2
# 错误代码
sqlalchemy.exc.InvalidRequestError: Mapper 'mapped class User->user' has no property 'role'

User 模型中未添加 role 属性

问题 11

1
sqlalchemy.exc.InvalidRequestError: Could not locate a property which relates instances of class 'Collect' to instances of class 'User'

Collect 模型和 User 模型之间未建立联系

问题 12

1
2
3
4
5
# 错误代码
SAWarning: Attribute 'BSCV
A' on class <class 'mw.models.Cornea'> appears to be a non-schema 'sqlalchemy.sql.column()' object; this won't be part of the declarative mapping
# 错误处
BSCVA = db.column(db.DECIMAL(2, 1))

column 首字母未大写，导致数据库表声明错误

问题 13

1
2
# 错误代码
AttributeError: 'User' object has no attribute 'translate'

数据提交到数据库时类型有误，如代码所示，此时需要检查提交到 User 表中的所有数据类型是否和声明一致

问题 14

1
2
3
sqlalchemy.exc.NoForeignKeysError: Could not determine join condition between parent/child tables on relationship User.comments - there
 are no foreign keys linking these tables.  Ensure that referencing columns are associated with a ForeignKey or ForeignKeyConstraint, o
r specify a 'primaryjoin' expression.

关系建立有误，可以将目标表的关系逐一对照查错

问题 15

1
smtplib.SMTPServerDisconnected: please run connect() first

使用 smtp 服务发送邮件时报错，服务涉及的账号密码等都存在 .env 文件中，Flask 会自动读取 .env 文件里的参数，但是该文件必须放在项目根目录下，否则会因无法读取报错

问题 16

1
2
self.port = int(port)
ValueError: invalid literal for int() with base 10: 'None'

SQLAlchemy 把一个引擎的源表示为一个连同设定引擎选项的可选字符串参数的 URI，URI 的形式是:

1
2
3
return self.registry[key]
KeyError: 140581010807680
dialect+driver://username:password@host:port/database

出现上述错误的原因是程序未读出 URI 中的 port，此时要检查环境变量配置文件，如果配置准确无误但还是无法读出配置文件中的 port 值注意以下问题：

在开发时，因为安装了 python-dotenv，使用 flask run 命令启动开发服务器时 Flask 会自动导入存储在 .flaskenv 或 .env 文件中的环境变量。在生产环境下，我们需要使用性能更高的生产服务器，所以不能再使用这个命令启动程序，这时我们需要手动导入环境变量。

我们应该尽可能地提前导入环境变量操作，这样才能确保程序中获取环境变量的代码正常工作，因此最佳的导入位置就是在 wsgi.py 脚本中，其次是程序包构造文件的顶部。在wsgi.py脚本中，我们使用 python-dotenv 提供的 load_dotenv() 函数手动导入 .env 文件中设置的环境变量，如下所示：

1
2
3
4
5
6
7
8
from dotenv import load_dotenv

dotenv_path = os.path.join(os.path.dirname(__file__), '.env')
if os.path.exists(dotenv_path):
	load_dotenv(dotenv_path)

from bluelog import create_app
app = create_app('production')

上面这段代码中的顺序非常重要，手动导入环境变量的语句必须在最前面，否则会导致一些环境变量无法读出造成程序崩溃。

问题 17

1
AttributeError: 'int' object has no attribute '_sa_instance_state'

Flask 数据库外键字段在创建对象赋值时，需要赋值对象，而不是该对象的 id 或者其他单独的字段。

发表于 更新于 分类于 Valine：

我的第一篇博客文章

这是我自建博客网站的第一篇文章，从18年至今，已经写了两年多的博客了，唯一值得骄傲的是我从未放弃，一直坚持了下来，之前的博客都在CSDN，博客链接。为什么选择CSDN？因为方便+大众，现在闲下来无事就创了自己的博客网站，因为CSDN也有它无法避免的缺点，就是界面不够美观。
之前在CSDN的博客绝大部分都和ACM相关，这个博客网站就准备放一些我自己做的小项目和心得体会，谢谢大家一直以来的支持，我仍会继续努力，写出更高质量更高水平的博客！

在这里插入图片描述

发表于 分类于 Valine：

    今天是 1024 程序员节，是我步入这个专业的第四个年头，同样也是我在 CSDN 坚持写博客的第三个年头。从最近的一篇博客至今，已经四个多月未写作了，所以借此机会我想聊聊自己的计算机生涯，下面所有的话都是有感而发，不喜勿喷哦😁

    第一句话我想送给所有学弟学妹或者即将步入大学生活的同学们：
     时光如白驹过隙，大一不努力，大四徒伤悲。
    当我回过神来时蓦然发现，大学四年已经走到了尾声，遥想当年刚步入大学时，我还是个未成年的孩子，一眨眼就到了奔三的年纪[此处手动添加一颗沧桑的熊猫头🙁]。自我反思时，我很庆幸自己没有荒废三年时光。半夜十二点在电脑屏幕前对着 Codeforces 的题目抓耳挠腮、打牛客暑期学校时苦思冥想几个小时终于 AC 的喜悦、早上六点多爬起来赶地铁去打蓝桥杯的辛苦、银川站打铁走在瑟瑟冷风中的宁夏理工学院的心酸、过年熬夜几天狂肝美赛论文的充实、准备一次又一次互联网+答辩的紧张，这些都历历在目。
    但是如果当初我没有做这些事呢？如果我只是整天呆在宿舍里打打游戏，混混日子，那我会有今天的成就吗？答案是否定的。我的身边不乏高中从尖子班来的同学，也不乏普通高中的前几名进来的，但是他们中有人挂科太多强制转下，有人碌碌无为只能慌忙准备考研，有人找工作频频被拒，这些人的失败有很大程度是因为虚度时光，所以我从过来人的角度告诫你们，光阴似箭，一眨眼可能就发现自己的大学时光已接近尾声，而我不希望那时的你们一事无成，所以请务必珍惜自己的大学时光，不要老大徒伤悲！

    第二句我想说的话是：
     当你决心去做一件事情的时候，全世界都会为你让路。

    这句话是我当时准备保研时一直作为 QQ 签名鼓励自己的，这里给各位讲一下自己的保研之路吧。我是大三上学期才开始准备保研的，那时候我的绩点排名是多少呢？全院 232 个人，我排 87 名，大概 37% 左右，而我们院正常的保研比例只有 14%，如果我没提保研成功的话，几乎所有人都觉得不可能吧，甚至在夏令营阶段找学院领导签字时，老师也觉得我没有希望，但我最终创造了奇迹，在所有保研人里以绩点倒数第一，综测倒数第三的成绩顺利保研。
    我想成功的秘诀就在于做这件事情的时候，我首先并不是去考虑结果，而是竭尽全力地去做，因为你做了哪怕只有一丝机会都有可能成功，但是如果你畏手畏脚不敢下手，就毫无机会了。整个大三学年里我没出去看过一次电影，几乎没有娱乐活动，考试周过了就准备竞赛、写论文、做项目，结果是这一年里，我取得了多项程序设计竞赛的国奖，申请了发明专利和软著，也发表了 EI 会议论文，把保研竞赛加分提到了满分，最终上天不负有心人，我成功拿到了保研名额。说这么多，我是想用亲身经历告诉各位，只要你想，没有什么是不可能的。正如苹果的乔布斯所言，“只有那些疯狂到自以为可以改变世界的人，最后才真的改变了世界。”

    最后一句话就是：
     人生不如意之事十之八九，与其在遗憾中沉沦，不如在厚积中薄发。
    大家在看完上面的内容时，一定觉得我很厉害，一直在装 X，其实不是的，我一路走来有太多太多的遗憾了，取少部分列举如下：

  • 我的高考目标是南京大学的天文系，但是很遗憾，因为个人的一些原因未能如愿以偿，现在只是一个 211 计算机专业的普通学生。
  • 我在校 ACM 队呆了近三年，参加了三次 ICPC 和一次 CCPC，都未能获奖
  • 我保研阶段拿到重大，北邮，川大的 offer，最终因为不敢冒险选择了本校
  • $\cdots$

    诚然，我相信每个人都有遗憾，爱而不得、劳而不获诸如此类，月尚有阴晴圆缺，作为凡人又何求十全十美呢。就拿竞赛这条路来说，当你总是在抱怨这抱怨那时，请记住，有太多太多条件比你差的同学仍无怨无悔地在这条路上默默耕耘着，我写博客时碰到很多出身普通一本甚至二三本学校还在努力打 ACM 的同学，他们学校和自身条件可能都不好，但是他们并没有怨天尤人，一直都在虚心求教，我相信他们最终都会取得满意的成绩。与其把时间浪费在自我怀疑和抱怨外部条件上，不如静下心来去刷两道题；与其抱怨这难那难，不如去请教学长老师搞懂这个难点；与其在遗憾中沉沦，不如在厚积中薄发。很多时候抱怨解决不了问题，改变自己才是破局之策。

    对程序设计竞赛的热爱让我选择了这个专业，也支撑着我的 CSDN 博客走到今天。今后有缘的话，我应该还会更新一些题解，不过博客的重心应该都会以项目为主了[毕竟要做研狗了/(ㄒoㄒ)/~~]。这里强烈建议搞竞赛的养成写博客的习惯，坚持下来你一定会看到别样的风景(๑•̀ㅂ•́)و✧

    最后的最后，在这个只属于程序员的节日里，送上我衷心的祝福：
    作为一个退役的 ACM 选手，衷心希望在这条路上努力的同学们题题 AC，场场 AK，奖牌拿到手软！
    作为一个即将读研的小白，希望所有考研人都能圆梦心仪的学校，也祝我们读研的道路上都能保住秀发，论文狂发！
    作为一个憧憬工作的憨憨，希望所有打工人都能朝九晚五，月薪过万！
    作为一个 IT 领域的人，希望这个行业发展越来越好，希望未来改变世界的，就是我们这些默默发光的程序员们！

发表于 分类于 Valine：

题目链接

题目描述

母牛哥在电脑面前坐久了，想站起来看看窗外的小山坡，于是就想出了这个问题：
给定一个大小为 n 的数组 a，序号从 1 开始，
计算:

max{ R - L | 1 <= L <= R <= n, a[L] == a[R], 对于所有i (L <= i <= R), 满足a[i] >= a[L] }.

也就是找到两个坐标,这两个坐标的值相等,并且他们之间的值都大于等于这两个坐标上的值.
这两个坐标相减最大能是多少.

输入描述

第一行一个整数 n，第二行 n 个整数

输出描述

输出题目所求的值

示例1

输入

1
2
5
1 2 3 2 1

输出

1
4

单调栈~
单调栈里元素值递增，当当前元素小于栈顶元素时，一直弹出栈顶即可，直到出现以下三种情况：

  • 栈为空，此时直接压入元素即可
  • 栈顶元素等于当前元素，将两者下标之差和答案取 max
  • 栈顶元素小于当前元素，压入元素即可

AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, ans, a[1000005];

int main() {
    cin >> n;
    stack<int> s;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        while (!s.empty() && a[i] < a[s.top()]) s.pop();
        if (s.empty()) s.push(i);
        else if (a[i] == a[s.top()]) ans = max(ans, i - s.top());
        else s.push(i);
    }
    cout << ans;
    return 0;
}

发表于 分类于 Valine：

题目链接

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

1
2
3
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

1
2
3
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

1
2
3
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

经典 DP ~

用 dp[i][j] 表示字符串1 [0,i-1] 位置和字符串2 [0,j-1] 位置的最大公共子序列的长度，那么有如下状态转移方程：

  1. 对当前位置 i，j，若有 text1[i-1]=text2[j-1]，则有 dp[i][j]=dp[i-1][j-1]+1
  2. 对当前位置 i，j，最大答案即为：dp[i][j]=max{dp[i][j],dp[i][j-1],dp[i-1][j]}

AC 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) {
            char a = text1[i - 1];
            for (int j = 1; j <= m; j++) {
                char b = text2[j - 1];
                if (a == b) dp[i][j] = dp[i - 1][j - 1] + 1;
                dp[i][j] = max({dp[i][j], dp[i][j - 1], dp[i - 1][j]});
            }
        }
        return dp[n][m];
    }
};

发表于 分类于 Valine：

题目链接

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
在这里插入图片描述

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。

示例:

1
2
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

单调栈~
首先我们不妨思考一下，什么时候能存水，肯定要出现两高夹一低才行，此时我们把存的水看作是一个矩形，假设遍历到某一高度 $i$ 时，出现了两高夹一低的情况，中间下标为 $top$，左侧为 $left$，那么这个矩形的宽就是 $i-left-1$，高就是 $min(height[i],height[left])-height[top]$。综上，只要每出现一次两高夹一低时，把矩形面积加到答案里即可~
而我们需要用一个数据结构来维护高度，显然高度是要递增的，所以很容易想到单调栈，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int trap(vector<int> &height) {
        int ans = 0;
        stack<int> s;
        int n = height.size();
        for (int i = 0; i < n; i++) {
            while (!s.empty() && height[i] > height[s.top()]) {
                int top = s.top();
                s.pop();
                if (s.empty()) break;
                int left = s.top();
                int w = i - left - 1;
                int h = min(height[left], height[i]) - height[top];
                ans += h * w;
            }
            s.push(i);
        }
        return ans;
    }
};

发表于 分类于 Valine：

题目链接

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

在这里插入图片描述

1
2
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

在这里插入图片描述

1
2
输入：head = [0,1,2], k = 4
输出：[2,0,1]

简单链表操作，我们注意到移动的次数 k 可能会大于链表长度，所以必须要取模，这样一来移动的可能性只会为 [0,len-1]，而 0 就相当于没移动，所以我们只需要只需要遍历一下列表，将左边 len-k 的部分拼接到右边的末尾即可，AC 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:  # 判空
            return head
        cnt, l = 0, 0
        p = head  # 计算链表长度
        while p:
            p = p.next
            l += 1
        p = head
        left = p  # 链表右移的部分
        k = k % l if k % l else l  # 取模
        while p:
            cnt += 1
            if cnt == l - k:
                break
            p = p.next
        if not p:  # 移到距离刚好等于链表长度的话相当于没动
            return head
        right = p.next  # 链表左移的部分
        p.next = None
        p = right
        while p.next:
            p = p.next
        p.next = left
        return right