- 博客(362)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 leetcode-HOT目录
66. 在排序数组中查找元素的第一个和最后一个位置。68. 寻找旋转排序数组中的最小值。29. 删除链表的倒数第N个节点。44. 二叉搜索树中第K小的元素。69. 寻找两个正序数组的中位数。75. 数组中的第K个最大元素。8. 无重复字符串的最长子串。16. 除自身以外数组的乘积。30. 两两交换链表中的节点。32. 复制带随机指针的链表。49. 二叉树的最近公共祖先。50. 二叉树中的最大路径和。57. 电话号码的字母组合。78. 买卖股票的最佳时机。17. 缺失的第一个正数。21. 搜索二维矩阵II。
2023-06-17 11:51:28
429
原创 HOT100-寻找重复数
遍历数组中的每一位数，将该数组num[i]对应的位置num[i]-1乘以-1，如果遍历的当前数字小于0，则返回对应的值。），可知至少存在一个重复的整数。你设计的解决方案必须。
2023-08-16 07:53:21
148
原创 HOT99-下一个排列
2. 再从右向左，找到第一个比j大的元素位置k(这个k必然存在,因为nums[j]>nums[i])。4. 对[j+1, n-1]区间的元素从小到大排序，此时只需要反转下数字即可reverse。1. 从右边向左，寻找第一个降序的数字j，对应的波峰为i （j=i-1)。3. 交换nums[j]和nums[k]。就是将其所有成员以序列或线性顺序排列。修改，只允许使用额外常数空间。
2023-08-16 07:47:56
431
原创 HOT98-颜色分类
2. 若num为2，(p2, n)必然都为2,但是(i, p2)之间的数字是不确定的,所以这里不能更新i，即原来p2指向的数字可能为2，如果更新i则会直接跳过这个数字。p0：从左向右，指向第一个非0的位置（p0左边必然都是0）；p2：从右向左,指向第一个非2的位置(p2右边必然是2)。1.若num为0， [p0, num)必然都为1，则同时更新p0和i，p0++, i++。对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。3. 若num为1，则只更新i，i++。
2023-08-15 08:05:45
126
原创 HOT97-多数元素
1. 遍历数组，当遇到跟结果变量result相同的数字时加一，遇到跟result不同的数字时减一。：用两个变量分别保存结果result和当前正在扫描的某一个数字的总数count。尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。你可以假设数组是非空的，并且给定的数组总是存在多数元素。2. 当count为0的时候，重新更新result的值。，返回其中的多数元素。多数元素是指在数组中出现次数。
2023-08-15 07:55:11
214
原创 HOT96-只出现一次的数字
除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。：位运算，按位异或。
2023-08-15 07:42:23
116
原创 HOT95-编辑距离
1. 问题定义: dp[i][j]表示以word1第i个数结尾和word2第j个数结尾的字符串的编辑距离。（1）dp[i][j] = dp[i - 1][j - 1]，当 dp[i]=dp[j]时；inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')2. 初始化： dp[i][0] = i，dp[0][j] = j。
2023-08-14 08:04:26
83
原创 HOT94-最长公共子序列
3.状态转移方程: dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1)。是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。1.问题定义: dp[i][j]表示text1[0,1,...,i]和text2[0,1,...,j]最长公共子序列的长度。2.初始化：dp[i][0] = 0， dp[0][j] = 0。是这两个字符串所共同拥有的子序列。，返回这两个字符串的最长。
2023-08-14 07:57:42
91
原创 HOT93-最长回文子串
3. 状态转移方程: dp[i][j]=dp[i+1][j-1] (s[i]!=s[j])，同时保存start和max_len。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。1. 问题定义：dp[i][j]表示s[i...j]是否为回文子串。4. 返回结果：根据s的start和max_len返回对应的子串。2. 初始化len=1对应的值，dp[i][i] = true。"aba" 同样是符合题意的答案。【方法1: 动态规划】。【方法2: 中心扩展法】
2023-08-14 07:52:31
91
原创 HOT92-最小路径和
3. 状态转移方程：dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]。1. 问题定义: dp[i][j]表示达到grid[i][j]的最小路径和。，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。4. 输出解：dp[rnum - 1][cnum - 1]。因为路径 1→3→1→1→1 的总和最小。给定一个包含非负整数的。2. 初始化：初始化第一行，第一列。每次只能向下或者向右移动一步。
2023-08-14 07:40:53
83
原创 HOT91-不同路径
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。3. 状态转移： dp[i][j] = dp[i - 1][j] + dp[i][j-1];2. 初始化：初始化第1列dp[i][0] = 1 和第一行dp[0][j] = 1。1. 问题定义: dp[i][j]表示走到nums[i][j]的路径数。4. 结果返回： dp[m - 1][n - 1]1. 向右 -> 向下 -> 向下。2. 向下 -> 向下 -> 向右。3. 向下 -> 向右 -> 向下。
2023-08-14 07:34:29
75
原创 HOT90-最长有效括号
2. 遇到右括号，先判断栈是否为空，如果栈为空，则直接将右括号和对应的下标压入栈；如果栈非空，且栈顶元素为左括号对应的pair，则先弹出匹配的左括号，并利用对应的下标更新当前的匹配最大长度。采用栈保存字符和对应的下标。的字符串，找出最长有效（格式正确且连续）括号子串的长度。1. 遇到左括号(，直接将字符入栈。最长有效括号子串是 "()()"最长有效括号子串是 "()"
2023-08-13 23:18:11
105
原创 HOT89-分割等和子集
3. 状态转移方程: dp[i][j] = dp[i-1][j-nums[i]] || dp[i][j]。1. 问题定义: dp[i][j]表示nums[0...i]中是否存在子数组,使得和为j。2. 初始化： dp[i][0] = true，一个数都不选的时候，和为0。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。题目转换为：是否存在子集，使得该子集的和为整个数组和的一半。数组可以分割成 [1, 5, 5] 和 [11]。4. 结果返回：dp[n - 1][sum]。
2023-08-13 23:10:40
97
原创 HOT88-乘积最大子数组
1. 问题定义: dp_max[k]表示以nums[k]结尾的连续子数组成绩最大值；dp_min[k]表示以nums[k]结尾的连续子数组成绩最小值，0
2023-08-13 23:04:26
135
原创 HOT87-最长递增子序列
1.问题定义：dp[k]表示以nums[k]结尾的最长严格递增子序列对应的长度(nums[k]必须被选取)3. 状态转移方程：dp[i] = std::max(max_len, dp[j] + 1)是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。最长递增子序列是 [2,3,7,101]，因此长度为 4。4. 结果返回：遍历各个元素结尾的长度，取最大值作为返回值。，找到其中最长严格递增子序列的长度。2.初始化：dp[0] = 1;
2023-08-13 22:54:49
125
原创 HOT86-单词拆分
返回 true 因为"applepenapple"可以由"apple" "pen" "apple" 拼接成。返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。1. 问题定义：dp[k]表示s[0,1,...,k-1],即以第k个字符结尾是否满足要求。3.状态转移方程: dp[i] = dp[j] && str[j, i-n]==true。不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。注意，你可以重复使用字典中的单词。4. 结果返回: dp[n]
2023-08-13 22:47:51
137
原创 HOT85-零钱兑换
3. 状态转移方程: min_count = std::min(min_count, dp[i - coin]);1. 问题定义: dp[n]表示总金额为n 对应的最少硬币。如果没有任何一种硬币组合能组成总金额，返回。，表示不同面额的硬币；你可以认为每种硬币的数量是无限的。2. 初始化： dp[0] = 0;计算并返回可以凑成总金额所需的。4. 结果返回：dp[n]
2023-08-13 22:33:49
94
原创 HOT84-完全平方数
状态转移方程： min_num = std::min(min_num, dp[i - j * j])；3. 确认遍历方式：从小到大遍历。检查下数字i: 从1到j的各个完全平方数，获取最小数量。dp[0] = 0;//由于9=9+0和 9=9是一个结果，所以dp[0]=0。是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。1. 问题定义: dp[n]表示和为n的完全平方数的最少数量。4. 返回结果：dp[n]的完全平方数的最少数量。
2023-08-13 22:25:38
134
原创 HOT83-打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。1. 问题定义：dp[k]表示nums[0...k]的最高偷窃金额；偷窃到的最高金额 = 2 + 9 + 1 = 12。偷窃到的最高金额 = 1 + 3 = 4。
2023-08-13 22:15:59
140
原创 HOT82-杨辉三角
初始化: 第1列f[i][0]和第i行第i列f[i][i]为1。在「杨辉三角」中，每个数是它左上方和右上方的数的和。给定一个非负整数 numRows。生成「杨辉三角」的前 numRows。
2023-08-13 22:10:18
91
原创 HOT81-爬楼梯
f[n]=f[n-1] + f[n-2]，然后用一个循环从小到求解即可。你有多少种不同的方法可以爬到楼顶呢？1. 1 阶 + 1 阶 + 1 阶。有两种方法可以爬到楼顶。1. 1 阶 + 1 阶。有三种方法可以爬到楼顶。2. 1 阶 + 2 阶。3. 2 阶 + 1 阶。
2023-08-13 22:03:17
101
原创 HOT80-划分字母区间
先遍历每一个字符，用一个map记录每一个字符最后出现的位置。然后再次遍历数组，为最近遍历的一堆字符寻找其出现的最后一个位置，并将最大位置设置为这一堆字符的“共同位置"，当经过这个共同位置时，则将这一堆字符放入同一块字母空间。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。划分结果为 "ababcbaca"、"defegde"、"hijhklij"。
2023-08-07 07:58:06
99
原创 HOT79-跳跃游戏 II
遍历数组中的每一个数，一边遍历，一边更新当前可跳转的最大距离记为max_pos，然后把每一个max_pos比做一面墙，每跨过一面墙，则需要跳一步。跨过这面墙后，需要寻找新的墙（即寻找新的max_pos)，再寻找墙的过程中，如果超越了终点位置，则结束寻找。跳到最后一个位置的最小跳跃数是2。从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。向前跳转的最大长度。生成的测试用例可以到达。处，你可以跳转到任意。
2023-08-07 07:43:01
330
原创 HOT78-跳跃游戏
遍历数组，保存当前能遍历到的最大跳跃位置（从0开始), max_pos=max(max_pos, i + nums[i]），如果遍历过程中存在max_pos 大于等于n-1的情况，则说明可以到达最后一个位置。无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。给定一个非负整数数组。
2023-08-05 23:24:51
431
原创 HOT77-买卖股票的最佳时机
一次遍历数组，保存从数组开始到当前元素num[i]的最小值min_value，并计算max(num[i]-min_value)，遍历完数组后，所求解到的最大值即为最大利润。在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回。设计一个算法来计算你所能获取的最大利润。
2023-08-05 22:58:28
192
原创 HOT76-数据流的中位数
大顶堆用于保存一半较小的数字，小顶堆用于保存一半较大的数字，且满足大顶堆中的所有数字均小于小顶堆中的所有数字。如果两个堆元素个数相同，则最终向小顶堆push（借助大顶堆过渡），若两个堆元素个数不同，则说明当前小顶堆的个数比大顶堆的个数多1，我们需要最终向大顶堆中push。为了求解中位数，我们可以始终维持小顶堆的元素个数大于或等于大顶堆的元素个数，且最多只能多一个（这里也可以始终维持大顶堆的元素个数小于或等于小顶堆的元素个数）。即先将num压入小顶堆中，然后将小顶堆中的top元素弹出到大顶堆中。
2023-08-05 21:56:42
198
原创 HOT75-前K个高频元素
先用map统计出各个数字出现的次数，然后根据出现次数的优先级将压入小顶堆中。之后遍历map中的对，先压入k个元素到堆顶中，之后将各个元素跟堆顶大小比较。如果当前元素比堆顶元素小，则直接忽略；如果当前元素比堆顶元素大，则弹出堆顶元素，压入当前元素，并调整堆。一直维持堆的大小为k，最后遍历完map中的所有元素后，剩下的堆中的元素即为结果集。，请你返回其中出现频率前。你所设计算法的时间复杂度。
2023-08-05 08:11:21
342
原创 HOT74-数组中的第K个最大元素
求最大的k个元素用小顶堆，求最小的k个元素用大顶堆。同时注意下c++的语法糖。std::less用于定义大顶堆, std::greater用于定义小顶堆。请注意，你需要找的是数组排序后的第。你必须设计并实现时间复杂度为。个最大的元素，而不是第。
2023-08-05 08:01:19
246
原创 HOT73-柱状图中最大的矩形
遍历每一个高度，取当前高度下的最大宽度，最大宽度的求法可以采用单调栈。用left[k]表示height[k]向左方向的下一个更小的元素，right[k]表示height[k]向右方向的下一个更小的元素，则此时最大宽度为right[k]-left[k]-1，注意初始化时，left数组各个初值都为-1，right数组各个初值都为n（n表示数组的大小）。每个柱子彼此相邻，且宽度为 1。1. 求下一个更大的元素，用单调递减栈。2. 求下一个更小的元素，用单调递增栈。求在该柱状图中，能够勾勒出来的矩形的最大面积。
2023-08-04 23:56:20
141
原创 HOT72-每日温度
本题核心解法：遍历数组元素的时候，不应该只是想着为该元素寻找下一个更大的元素，需要换一种视角，先判断下当前元素能否作为栈中已有元素的下一个元素，这样就很快可以求解了。遍历数组，将每个温度的下标入栈，入栈前先将栈中小于当前温度的下一个更高的温度设置为当前温度，将满足条件的栈中元素求解和弹出后，再将当前元素入栈。天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用。，表示每天的温度，返回一个数组。
2023-08-04 08:02:12
103
原创 HOT71-字符串解码
输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数。遍历字符串，用字符串变量result保存最终的结果，遍历过程中用栈保存当前需要扩展的次数和待扩展字符串的首字母在result中的位置。4）遇到], 则开始扩展字符, 扩展的次数和扩展的字符都可以通过栈中的信息拿到。3）遇到[, 则将 保存在栈中,同时重置count的值为0；1）遇到数字，计算下需要扩展的次数；
2023-08-04 00:50:33
202
原创 HOT69-有效的括号
将字符串中的每个字符压入栈，遇到右括号的时候，如果此时栈为空或者栈顶元素不匹配，则字符串无效。最后遍历完所有元素，判断栈是否为空即可。，判断字符串是否有效。
2023-08-01 07:42:23
157
原创 HOT68-寻找两个正序数组的中位数
这两个数组中，小于等于min(nums1[i+k/2-1], nums2[j+k/2-1])的元素最少元素个数为i+k/2-1, 或者j+k/2-1，最多元素个数为(k/2-1+k/2-1)=k-2个，加上min(nums1[i+k/2-1], nums2[j+k/2-1]),最多k-1个，所以取k/2-1作为比较值是合理的。nums1： [i, i+1, i+2,... i+k/2-1] 共 k/2-1个元素。nums2：[j, j+1, j+2, ... j+k/2-1]共 k/2-1个元素。
2023-08-01 07:21:45
194
原创 HOT67-寻找旋转排序数组中的最小值
1. 数组未发生旋转，整体升序，即nums[left] nums[right，则最小值位于右半段的第一个元素。，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。的数组，预先按照升序排列，经由。
2023-07-15 23:51:11
375
原创 HOT66-搜索旋转排序数组
判断[left, mid], [mid, right]两个区间，到底哪个是有序的空间，如果target在有序空间里，则对该区间采用二分查找。所以本题的关键在于，需要判断有序区间在哪里。你必须设计一个时间复杂度为。，则返回它的下标，否则返回。按升序排列，数组中的值。在预先未知的某个下标。
2023-07-15 23:15:48
368
原创 HOT65-在排序数组中查找元素的第一个和最后一个位置
左边界: target = num[mid]，则扩大查找范围, right=mid+1，循环结束的时候, left=right+1，left指向第一个大于target或最右侧target的位置。请你找出给定目标值在数组中的开始位置和结束位置。给你一个按照非递减顺序排列的整数数组。
2023-07-15 00:53:37
359
原创 HOT64-搜索二维矩阵
从右上角(x,y)开始查找，如果nums(x,y)等于target直接返回；若target < nums(x,y)，y--，即向左边查找；若target>nums(x,y)，则x++，则向下查找。给你一个满足下述两条属性的。
2023-07-15 00:41:44
1106
原创 HOT63-搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为。：二分查找，细节决定成败。二分查找主要考察的是细节，包括搜索区间、循环结束条件、最终循环结束后left指针和right指针分别指向什么位置。1. 循环执行的条件: 搜索区间 [left, right]。2.循环结束后，right指针在left指针的左边。
2023-07-15 00:35:38
382
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人