- 博客(122)
- 收藏
- 关注
RSS订阅原创 洛谷P3865 【模板】ST 表
洛谷P3865 【模板】ST 表题目描述给定一个长度为 NNN 的数列，和 MMM 次询问，求出每一次询问的区间内数字的最大值。输入格式第一行包含两个整数 N,MN,MN,M，分别表示数列的长度和询问的个数。第二行包含 NNN 个整数（记为 aia_iai），依次表示数列的第 iii 项。接下来 MMM 行，每行包含两个整数 li,ril_i,r_ili,ri，表示查询的区间为 [li,ri][l_i,r_i][li,ri]。输出格式输出包含 MMM 行，每行一个整数，依
2021-10-21 16:05:57
542
原创 剑指 Offer 34. 二叉树中和为某一值的路径
剑指 Offer 34. 二叉树中和为某一值的路径输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。参考以下这颗二叉搜索树：示例:给定如下二叉树，以及目标和 target = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \
2021-06-08 12:34:08
244
原创 剑指 Offer 33. 二叉搜索树的后序遍历序列
剑指 Offer 33. 二叉搜索树的后序遍历序列输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。参考以下这颗二叉搜索树： 5 / \ 2 6 / \ 1 3示例 1：输入: [1,6,3,2,5]输出: false示例 2：输入: [1,3,2,6,5]输出: true限制：数组长度 <= 1000思路：递归 根据后序遍历
2021-06-07 22:29:26
233
原创 剑指 Offer 32 - III. 从上到下打印二叉树 III
剑指 Offer 32 - I. 从上到下打印二叉树请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回：[ [3], [20,9], [15,7]]限制：节点总数 <= 1000思路：BFS + 标记 clas
2021-06-07 22:10:43
162
原创 剑指 Offer 32 - II. 从上到下打印二叉树 II
剑指 Offer 32 - I. 从上到下打印二叉树从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回：[ [3], [9,20], [15,7]]限制：节点总数 <= 1000思路：BFS class Solution {public: vector<vector&
2021-06-07 22:10:09
105
原创 剑指 Offer 32 - I. 从上到下打印二叉树
剑指 Offer 32 - I. 从上到下打印二叉树从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回：[3,9,20,15,7]限制：节点总数 <= 1000思路：BFS class Solution {public: vector<int> levelOrder(TreeNode
2021-06-07 22:07:26
103
原创 剑指 Offer 31. 栈的压入、弹出序列
剑指 Offer 31. 栈的压入、弹出序列输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。示例 1：输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出：true解释：我们可以按以下顺序执行：push(1),
2021-06-07 10:58:10
99
原创 剑指 Offer 30. 包含min函数的栈
剑指 Offer 30. 包含min函数的栈定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。示例 1：MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.min(); --> 返回 -3.minStack.pop();minStack.t
2021-06-07 10:51:47
113
原创 剑指 Offer 29. 顺时针打印矩阵
剑指 Offer 29. 顺时针打印矩阵输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。示例 1：输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5]示例 2：输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7]限制：0 <= matrix.length <= 1000 <= mat
2021-06-07 10:37:11
105
原创 剑指 Offer 28. 对称的二叉树
剑指 Offer 28. 对称的二叉树请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2/ \ / \3 4 4 3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \3 3示例 1：输入：root = [1,2,2,3,4,4,3]输出：true示例 2
2021-06-02 10:21:43
122
原创 剑指 Offer 27. 二叉树的镜像
剑指 Offer 27. 二叉树的镜像请完成一个函数，输入一个二叉树，该函数输出它的镜像。例如输入：4/ \2 7/ \ / \1 3 6 9镜像输出： 4/ \7 2/ \ / \9 6 3 1示例 1：输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]限制：0 <= 节点个数 <= 1000思路一：BFS class Solution {public:
2021-06-02 10:21:10
116
原创 剑指 Offer 26. 树的子结构
剑指 Offer 26. 树的子结构输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)B是A的子结构， 即 A中有出现和B相同的结构和节点值。例如:给定的树 A:3/ \4 5/ \1 2给定的树 B：4 /1示例 1：输入：A = [1,2,3], B = [3,1]输出：false示例 2：输入：A = [3,4,5,1,2], B = [4,1]输出：true限制：0 <= 节点个数 <= 10000
2021-06-02 10:20:33
94
原创 剑指 Offer 25. 合并两个排序的链表
剑指 Offer 25. 合并两个排序的链表输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。示例 1：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4限制：0 <= 链表长度 <= 1000思路：模拟 class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
2021-06-01 16:14:44
106
原创 剑指 Offer 24. 反转链表
剑指 Offer 24. 反转链表定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。示例 1：输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL限制：0 <= 节点个数 <= 5000思路：模拟 class Solution {public: ListNode* reverseList(ListNode* head) {
2021-06-01 16:14:13
108
原创 剑指 Offer 22. 链表中倒数第k个节点
剑指 Offer 22. 链表中倒数第k个节点输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。示例 1：给定一个链表: 1->2->3->4->5, 和 k = 2.返回链表 4->5.思路：双指针 class Solution {public:
2021-06-01 16:13:12
93
原创 剑指 Offer 20. 表示数值的字符串
剑指 Offer 20. 表示数值的字符串请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。数值（按顺序）可以分成以下几个部分：若干空格一个 小数 或者 整数（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数\若干空格小数（按顺序）可以分成以下几个部分：（可选）一个符号字符（’+’ 或 ‘-’）下述格式之一：至少一位数字，后面跟着一个点 ‘.’至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字一个点 ‘.’ ，后面跟
2021-06-01 16:11:52
130
原创 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。示例 1：输入：nums = [1,2,3,4]输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。说明：0 <= nums.length <= 500001 <= nums[i] <= 10000思路：双指针 class Solution {public:
2021-06-01 10:58:20
122
原创 剑指 Offer 19. 正则表达式匹配
剑指 Offer 19. 正则表达式匹配请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。示例 1：输入:s = "aa"p = "a"输出: false解释: "a" 无法匹配 "aa" 整个字符串。示例 2：输入:s = "aa"p = "a*
2021-06-01 10:44:39
108
原创 [数组 - 哈希表] LeetCode 1. 两数之和
1. 两数之和给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例 1：输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：输入：nums = [3,2,4],
2021-06-01 01:06:35
243
原创 剑指 Offer 18. 删除链表的节点
剑指 Offer 18. 删除链表的节点给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。**注意：**此题对比原题有改动示例 1：输入: head = [4,5,1,9], val = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.示例 2：输入: head = [4,5,1,9], val = 1输出: [4,5,9]
2021-05-31 11:37:58
142
原创 剑指 Offer 17. 打印从1到最大的n位数
剑指 Offer 17. 打印从1到最大的n位数输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。示例 1：输入: n = 1输出: [1,2,3,4,5,6,7,8,9]注意：用返回一个整数列表来代替打印n 为正整数思路：模拟 class Solution {public: vector<int> printNumbers(int n) { int mx = 0
2021-05-31 11:09:16
81
原创 hduoj 2544 最短路（SPFA）
hduoj 2544 最短路Problem Description在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？Input输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=
2021-05-18 22:03:23
150
原创 [洛谷 P4779] 单源最短路径（Dijkstra堆优化模板）
P4779 【模板】单源最短路径（标准版）题目描述给定一个 nnn 个点，mmm 条有向边的带非负权图，请你计算从 sss 出发，到每个点的距离。数据保证你能从 sss 出发到任意点。输入格式第一行为三个正整数 n,m,sn, m, sn,m,s。 第二行起 m 行，每行三个非负整数 ui,vi,wiu_i, v_i, w_iui,vi,wi ，表示从uiu_iui到viv_ivi有一条权值为wiw_iwi的有向边。输出格式输出一行 nnn 个空格分隔的非负整数，表示 s
2021-05-18 21:17:36
188
原创 [动态规划] LeetCode 188. 买卖股票的最佳时机 IV
188. 买卖股票的最佳时机 IV给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1：输入：k = 2, prices = [2,4,1]输出：2解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2
2021-03-30 21:38:05
129
原创 [动态规划] LeetCode 123. 买卖股票的最佳时机 III
123. 买卖股票的最佳时机 III给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1：输入：prices = [3,3,5,0,0,3,1,4]输出：6解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格
2021-03-30 21:12:10
194
原创 [动态规划 | 贪心] LeetCode 122. 买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1：输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格
2021-03-30 16:19:10
160
原创 [动态规划 | 贪心] LeetCode 121. 买卖股票的最佳时机
121. 买卖股票的最佳时机给定一个数组 prices，它的第i个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。示例 1：输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5
2021-03-30 15:30:42
178
原创 nowcoder 桃花 (两次DFS求直径)
桃花题目描述桃花一簇开无主，可爱深红映浅红。——《题百叶桃花》桃花长在桃树上，树的每个节点有一个桃花，调皮的HtBest想摘尽可能多的桃花。HtBest有一个魔法棒，摘到树上任意一条链上的所有桃花，由于HtBest法力有限，只能使用一次魔法棒，请求出Htbest最多可以摘到多少个桃花。输入描述:第一行有一个正整数n，表示桃树的节点个数。接下来n-1行，第i行两个正整数ai,bi ，表示桃树上的节点ai,bi之间有一条边。输出描述:第一行一个整数，表示HtBest使用一次魔法棒最多
2021-03-15 16:43:59
125
原创 nowcoder 水图 (DFS)
水图题目描述小w不会离散数学，所以她van的图论游戏是送分的小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度小w现在在点x上她想知道从点x出发经过每个点至少一次，最少需要走多少路输入描述:第一行两个整数 n,x,代表点数,和小w所处的位置第二到第n行,每行三个整数 u,v,w,表示u和v之间有一条长为w的道路输出描述:一个数表示答案示例1输入3 11 2 12 3 1输出2备注1 ≤ n ≤ 50000 , 1 ≤ w
2021-03-15 16:35:32
122
原创 [动态规划 | LIS | 二分] LeetCode 354. 俄罗斯套娃信封问题
300. 最长递增子序列给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。注意：不允许旋转信封。示例 1：输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]输出：3解释：最多信封的个数为
2021-03-08 11:27:31
291
1
原创 [单调栈] LeetCode 739. 每日温度
739. 每日温度请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提示：气温 列表长度的范围是[1, 30000]。每个气温的值的均为华氏度，都是在[30, 100] 范围内的整数。解题思路（单调栈）维护
2021-03-08 10:25:47
176
原创 [0-1背包] LeetCode 416. 分割等和子集
416. 分割等和子集给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例 1：输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].示例 2：输入: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的子集.提示：每个数组中的元素不会超过 100数组的大小不会超过 200解题思路（动态规划 0-1背包）题目要求分割两个子集的元素和相等
2021-03-03 22:50:15
242
2
原创 [0-1背包] LeetCode 494. 目标和
494. 目标和给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和-。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。示例 1：输入：nums: [1, 1, 1, 1, 1], S: 3输出：5解释：-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3一共有5种
2021-03-03 22:30:40
257
1
原创 [动态规划 | 二分 + 贪心] LeetCode 300. 最长递增子序列
300. 最长递增子序列给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。示例 1：输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：输入：nums = [0,1,0,3,2,3]输出：4示例 3：输入：nums
2021-03-03 16:58:32
238
1
原创 [完全背包] LeetCode 518. 零钱兑换 II
518. 零钱兑换 II给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。示例 1：输入: amount = 5, coins = [1, 2, 5]输出: 4解释: 有四种方式可以凑成总金额:5=55=2+2+15=2+1+1+15=1+1+1+1+1示例 2：输入: amount = 3, coins = [2]输出: 0解释: 只用面额2的硬币不能凑成总金额3。示例 3：输入: amount = 10, coi
2021-03-03 16:04:59
226
1
原创 [完全背包] LeetCode 322. 零钱兑换
322. 零钱兑换给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。示例 1：输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1示例 2：输入：coins = [2], amount = 3输出：-1示例 3：输入：coins = [1], amount = 0输出：0
2021-03-03 15:38:37
182
1
原创 hduoj5248 序列变换 (二分答案 | 贪心)
序列变换Problem Description给定序列A=A1,A2,...,AnA={A1,A2,...,An}A=A1,A2,...,An, 要求改变序列A中的某些元素，形成一个严格单调的序列B（严格单调的定义为：Bi<Bi+1,1≤i<N）Bi<B_{i+1},1≤i<N）Bi<Bi+1,1≤i<N）。我们定义从序列A到序列B变换的代价为cost(A,B)=max(∣Ai−Bi∣)(1≤i≤N)。cost(A,B)=max(|Ai−Bi|)(1≤i≤N)。c
2021-02-27 19:58:03
350
原创 [暴力 | 双指针 | 单调栈] LeetCode 42. 接雨水
42. 接雨水给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例 1：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例 2：输入：height = [4,2,0,3,2,5]输出：9提示：n == height.length0 <= n
2021-02-19 20:20:50
139
原创 [栈与队列] LeetCode 225. 用队列实现栈
225. 用队列实现栈请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop 和 empty）。实现 MyStack 类：void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。注意：你只能使用队列的基本操作 —— 也就是 push to back、peek/pop
2021-02-18 19:50:59
214
原创 [栈与队列] LeetCode 232. 用栈实现队列
232. 用栈实现队列请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类：void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空，返回 true ；否则，返回 false说明：你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop
2021-02-18 14:07:54
209
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人