- 博客(56)
- 收藏
- 关注
RSS订阅原创 3.8 动态规划 背包问题
时间限制：5.000S 空间限制：128MB题目描述:小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。
2024-03-08 23:00:00
1840
原创 3.5 力扣 交错字符串
给定三个字符串s1s2s3，请你帮忙验证s3是否是由s1和s2组成的。两个字符串s和t的定义与过程如下，其中每个字符串都会被分割成若干a + b意味着字符串a和b连接。truefalse。
2024-03-07 01:00:00
830
原创 3.3动态规划 中等题
常用于求解值问题、后面的“值”与前面的“值”有关系（递推公式）例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。
2024-03-04 01:00:00
951
原创 1.23 力扣图论
当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。用bfs方法，从第一个房间开始，拿钥匙、进入另一个房间、拿钥匙。号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。由于我们能够进入每个房间，我们返回 true。号房间可以获得的钥匙集合。我们从 0 号房间开始，拿到钥匙 1。之后我们去 1 号房间，拿到钥匙 2。然后我们去 2 号房间，拿到钥匙 3。我们不能进入 2 号房间。
2024-01-23 22:17:50
585
原创 1.19 力扣中等图论
给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
2024-01-19 19:37:20
686
原创 1.12 力扣中等图论
给你一个有n个节点的，请你找出所有从节点0到节点n-1的路径并输出（graph[i]是一个从节点i可以访问的所有节点的列表（即从节点i到节点存在一条有向边）。有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3。
2024-01-12 23:00:00
667
原创 1.10 力扣回溯中等题
正好由四个整数（每个整数位于0到255之间组成，且不能含有前导0），整数之间用'.'分隔。给定一个只包含数字的字符串s，用以表示一个 IP 地址，返回所有可能的，这些地址可以通过在s中插入'.'来形成。你重新排序或删除s中的任何数字。你可以按顺序返回答案。s = "0000"
2024-01-10 23:00:00
566
原创 1.6 力扣回溯中等
思路：题中是要求分割s，即按顺序切割任意次，那一定会有一个情况是 单字符被切割为一个子串。考虑for循环切割。对切割后的当前子串进行判断是否为回文串，是则在次基础上继续切割，不是则此处index不进行切割，跳到下一个index+1继续做判断，如此循环即可。是正着读和反着读都一样的字符串。分割成一些子串，使每个子串都是。所有可能的分割方案。
2024-01-06 20:15:00
467
原创 1.3 力扣二叉树中等题
给你二叉搜索树的根节点root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在中。修剪树改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。[1,null,2]过了这么久再做，需要思考时间更短了，代码也更精简了许多（也可能是做过的原因）。hhhh。
2024-01-03 23:45:00
1559
原创 1.2 二叉搜索树中等题
给定二叉搜索树（BST）的根节点root和要插入树中的值value，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据，新值和原始二叉搜索树中的任意节点值都不同。，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回。
2024-01-02 19:45:00
951
原创 12.30 二叉树中等题
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（3节点5和节点1的最近公共祖先是节点3。5节点5和节点4的最近公共祖先是节点5。因为根据定义最近公共祖先节点可以为节点本身。
2023-12-30 17:31:21
1008
原创 12.06 二叉树中等题2
后序遍历数组中左子树和右子树的个数都要等于inorder数组的子树，即可分出左子树和右子树的后序遍历数组。即中序遍历数组中根节点左边的属于左子树，右边的属于右子树，即可分出左子树和右子树的中序遍历数组。时间复杂度：O(n)，其中 n为二叉树的节点个数。思路：中序遍历二叉搜索树后的结果会是单调递增且无重复的。有了根节点，可以在中序遍历数组中分出根节点的左子树和右子树，时间复杂度：O(n)，其中 n是树中的节点个数。思路：后序遍历的数组中最后一个元素会是根节点，是二叉树的中序遍历，给你一个二叉树的根节点。
2023-12-06 21:32:06
450
原创 12.04 二叉树中等题
在最坏的情况下，数组严格递增或递减，需要递归 n 层，第 i (0≤i<n)层需要遍历 n−i个元素以找出最大值，总时间复杂度为 O(n2)- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5]。- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1]。- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1]。- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 []。
2023-12-04 21:03:36
1671
原创 12.03 二叉树简单题2
思路2：满二叉树有个特点是，只有最后一层可能不是满的且从左到右不会有“间断”。对于完全满二叉树可以按2**h-1得到节点数，对于不是完全满二叉树的可以一直递归左右子树直到出现空节点或叶子节点。的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。思路：可以采用深度优先遍历，将每个节点的val放进当前path，然后判断当前节点是否为叶子节点，叶子节点则保存当前路径，非叶子节点则继续遍历。，返回所有从根节点到叶子节点的路径。
2023-12-03 22:23:21
469
原创 12.1 二叉树简单题
思路：对称二叉树 有一个特点是以 中左右顺序遍历左子树的结果会等于 中右左顺序遍历右子树的结果。思路：题目中是要求找 到叶子节点（左 右子节点为nullptr）的最小深度，并不是空节点的最小深度。可以用深度优先遍历该树，每次到叶子节点则进行最小值的迭代判断。时间复杂度：O(N)，其中 N是树的节点数。对每个节点访问一次。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。细节：引入记录当前深度和最小值的记录。给定一个二叉树，找出其最小深度。叶子节点是指没有子节点的节点。给你一个二叉树的根节点。
2023-12-02 11:47:56
455
原创 11.27 二叉树基础题
相似，不同之处在于，第 102 题要求从上到下输出每一层的节点值，而这道题要求从下到上输出每一层的节点值。除了输出顺序不同以外，这两道题的思路是相同的，都可以使用广度优先搜索进行层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）思路：经典的队列实现方法，再反转一下返回的数组。
2023-11-27 10:21:06
400
原创 11.24 力扣优先队列
c++优先队列priority_queue（自定义比较函数）_c++ priority_queue自定义比较函数_菊头蝙蝠的博客-CSDN博客//小顶堆//小顶堆以后还是直接用struct重载函数吧。
2023-11-24 18:40:35
452
原创 11.23 队列使用
思路二：维护一个单调队列保存数组下标index，队列从大到小且元素顺序和数组中的顺序一样。遍历数组时，每遍历一个nums[i]，都将插入队列deque中，将队尾小于nums[i]的数依次pop_back，直到队列为空。代码时间复杂度为O（nlogn），在最坏情况下所有元素都一样大，大根堆将保存所有元素，将元素插入大根堆的时间复杂度O（nlogn）思路一：维护一个大根堆，堆中保存的元素为数组的下标index，排序方式是nums[i]从大到小。的滑动窗口从数组的最左侧移动到数组的最右侧。时间复杂度为O（n）
2023-11-23 14:54:05
61
原创 11.20 栈简单题
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。思路：维护一个没有连续重复字符的栈，只要遍历字符串时判断栈顶元素和当前字符是否相等，相等则进行去除，不相等就push。思路：创建一个栈，维护该栈中只包含‘左括号’（ [ {，这三种，碰见右括号则判断栈顶元素是否与该右括号匹配。在 S 上反复执行重复项删除操作，直到无法继续删除。
2023-11-22 14:37:08
51
原创 11.20 栈与队列
思路：创建两个栈，一个用于接收输入st1，一个用于输出st2，在pop和peek时，将st1的元素都放入st2中。维护que1为 先入后出的“栈”，que2为辅助que1维护，que2一直保持为empty,请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（2.再把que1所有元素放到que2。3.que1和que2互换。1.先放入到que2。
2023-11-20 14:56:40
52
原创 11.19 四数之和
思路：两层for循环，加一个left right 双指针（减少复杂度，不然要用四层for循环），用set<vector<int>>进行去重。set传入的第二个比较函数一定要用 const 引用、const this指针。请你找出并返回满足下述全部条件且。
2023-11-19 13:32:28
42
原创 9.20 计算中缀表达式
本文参考了但计算中缀表达式没有在力扣和牛客网找到完整的题目。计算中缀表达式主要分为了两步骤：1）中缀转为后缀2） 计算后缀表达式的值该例题没有考虑括号，也没有用数字（而是用非符号的字符代替，如a，b，c）
2023-09-19 17:24:37
297
原创 9.19 力扣LCR 036. 逆波兰表达式求值
思路：计算后缀表达式的结果，从左到右开始，元素为数字则保留，运算符则需要找到前两个元素进行运算再将结果保留。该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6。字符串和整数的互相转换，可参考to_string（）和atoi()函数。该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9。每个运算对象可以是整数，也可以是另一个逆波兰表达式。数字可能是负数如-11等需要特殊判断。代码实现：典型需要用栈的列题。，求该后缀表达式的计算结果。
2023-09-19 16:16:54
141
原创 9.13 美团2024届秋招笔试第一场编程真题
代码实现：求每个组合的“权值”时可用DFS方法，创建v_temp、v_flag分别记录当前组合的矩阵、当前是否可入（还不是连通块）。小美拿到了一个长度为n的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有x行y列，必须保证x∗y=n，即每y个字符换行，共x行）。思路：矩阵能有多种组合，求所有组合中让“权值”最小的值。“权值”=“连通块”，即整体字符中相同的字符要尽量“相邻”。或者用暴力遍历所有组合，并求每个组合的“权值”该矩阵的权值定义为这个矩阵的连通块数量。
2023-09-13 13:58:53
547
原创 9.5 美团2024届秋招笔试第一场编程真题
有一个环形的公路，上面共有n站，现在给定了顺时针第i站到第i＋1站之间的距离（特殊的，也给出了第n站到第1站的距离）。小美想沿着公路第x站走到第y站，她想知道最短的距离是多少?第二行输入n个正整数ai，前n―1个数代表顺时针沿着公路走，i站到第i＋1站之间的距离;最后一个正整数代表顺时针沿着公路走，第n站到第1站的距离。最后只需要比较(v[y-1]-v[x-1], v[n]-(v[y-1]-v[x-1]))代码实现：利用一个数组V来保存顺时针从第一个位置走到第i个位置的公里数——V【i】。
2023-09-05 22:26:20
690
原创 9.4 美团2024届秋招笔试第一场
思路：利用每个元素只出现一次，每个元素能“记住”自己“附近”的元素则很简单能完成。思路：b数组元素=a数组元素相邻数的和，要让b数组的最大值-最小值最小，则只要让a数组中小大小大。那么b数组的最大值减最小值即为a数组的权值。例如，若a=[2,1,3]，那么b=[3,4]，b数组的极差是1。因此a数组的权值为1。现在小美希望你能构造一个长度为n的排列，满足权值尽可能小。排列是指一个长度为n的数组，其中 1 到n每个元素恰好出现一次。排列是指一个长度为n的数组，其中 1 到n每个元素恰好出现一次。
2023-09-04 20:44:20
1170
1
原创 8.22 字节跳动春招研发 毕业旅行问题 找零
例子说明：共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。状态： dp[经过城市的结合，为二进制压缩状态][当前进过的城市id]，d(V,i)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。思路：假设从顶点s出发，令d(V,i)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。
2023-08-28 21:09:08
209
原创 3.23 84. 柱状图中最大的矩形
1.找到元素value左边第一个小于value和右边第一个小于value的下标LeftMin和RightMin则矩形面积=(RightMin-LeftMin-1）*value（如果左右没有更小的值则下标设置为-1或height.size()）思路：形成矩形的角度：都会有以某一个元素的值为高度，然后向外扩展形成矩形。可以先找到以每个元素可形成的最大矩形再判断出最大值。个非负整数，用来表示柱状图中各个柱子的高度。求在该柱状图中，能够勾勒出来的矩形的最大面积。最大的矩形为图中红色区域，面积为 10。
2023-03-23 21:58:03
80
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人