- 博客(176)
- 收藏
- 关注
RSS订阅原创 动态规划_数组切分
如果j ~ i 是符合条件的 那么就把他们当作一个整体 然后在此位置进行一次切分 然后加上dp[j - 1 ] 也就是加上前面的方案数 整合到一起 然后 还在继续往前遍历j 然后又找到了一个新的符合条件的j 又要执行一次累加 这次的累加 还是加上 dp[j - 1 ]的切分情况 然后在j ~ i进行一次切分 这次 的切分 也多了几个数 ( 因为是j ~ i 这次的 j 变得更加小了 ) 所以不存在重复累加。因为出现了一个新的nums[i] 那么就阻止了重复累加的出现。
2025-02-27 10:25:25
241
原创 线性dp_接龙数列
对于23这个数的话 使用 dp[r] = dp[left] + 1 那么就是添乱 因为dp[3]本来就很大了 那么如果再dp[3] = dp[2] + 1 那么就会变得很小 那么我们就可以舍弃这个数。那么可以得到状态转移方程 dp[r] = dp[left] + 1 那么这样子还是不可以的。新的状态转移方程dp[r] = max(dp[left] + 1, dp[r])他们的关系是 ： 如果该数第一位存在 那么该数就可以接龙 状态数接在该数的尾数。改善一下 有点dp的样子。
2025-02-25 10:26:03
209
原创 704. 二分查找
定义左右边界为 -1 n 结束条件 left + 1 == right注意的是 n == 1 会照成越界 需要分类讨论还要注意 有些空数组 还有很多数组越界的问题。
2025-02-10 20:01:36
224
原创 哈希表_优质数对
但是 在最坏的情况下 还是退化成了O(n^2) 还是没能通过所有案例。开始并没有什么思路 直接暴力算法 但是超时了 并不能通过全部案例。后面使用hash表 查找是否在A中出现B B中出现A。那相同元素的不同位置 我们可以存储在一个vector当中。O(n*n)的时间复杂度在10^5还是略显没什么优势。但是这个方法还是存在缺陷 就是输入相同元素时 会覆盖。确保TMP 足够大 映射唯一值。那么这样子就要用到映射函数了。通常定义为10^9 + 7;
2025-02-09 11:10:32
316
原创 leetcode_264. 丑数 II
居然已经给出了丑数的因子 那么我们可直接用最小的丑数 * 因子 就可以得到另一个丑数。本来是想像求素数那样子求出丑数 但是发现这个数据量好像有点大 但是 On²。的时间复杂度在10000的数据量还是可以接受的。但是用逆向思维 可以很轻松得到结果。
2025-02-02 14:07:55
232
原创 priority_queue
1. pop操作是先将栈顶元素和栈底元素互换 然后再将栈顶元素下沉 然后删除栈顶。priority_queue也可以比抽象类 只要<重载 指定比较对象就可以。一些与别的stl不同的地方。
2025-02-02 11:02:20
269
原创 c++ map
在当前key已经存在value时 insert不会改变当前key的value 但是m[ ]会。其实和前面的没什么区别 就是有一点点的区别 他的insert比较复杂 和可以比较简单。// m[] 和 insert 的区别。
2025-02-02 10:17:25
179
原创 leetcode_1678. 设计 Goal 解析器
其中 find是从第一个字符开始查找 如果找到最后 没有找到与其匹配的 就会返回string::npos。看起来简单的暴力操作就可以完成 但是代码看着有点长。那么我们可以用find和replace配合实现。找到指定的字符串后 将其替换掉。
2025-01-13 20:22:05
314
原创 leetcode_2816. 翻倍以链表形式表示的数字
我们可以想到 乘法运算中 就是从低位到高位进行计算 刚开始 我想先反转链表 然后在计算 然后在进行反转 得到一个新的结果 但是这样子耗费时间太多了。搜先看到这个题目 链表的节点那么多 已经远超longlong能够表示的范围 那么暴力解题 肯定是不可以的了。然后我还想到可以先把链表中的数先组成一个数 然后在进行计算 但是这个数远超longlong能表示的范围。此时 我们想到 链表的前一个节点的数与后一个节点的数有关 那么我们可以利用递归回溯来解决这一个问题。
2025-01-11 20:42:38
439
原创 leetcode_LCR 024. 反转链表
我知道我的错误了 因为当链表为空 stk不存在元素 然后我的curr指向了stk.top() 上面都没有 会导致指针错误 对吧。，你应该在尝试访问栈的元素之前检查栈是否为空。如果栈为空，就没有节点可以反转，应该直接返回。之前检查栈是否为空，避免出现指针错误。我们写的时候很可能顺其自然就写下去了 但是忽略了原来链表是空的情况 导致错误。，就会导致未定义的行为，因为栈是空的，无法获取其顶部元素。是的，正如你所说，问题在于链表为空时，栈 () 里没有任何元素，如果你试图访问。k神解法 空间复杂度大大减少。
2024-12-17 12:59:46
536
原创 leetcode_203. 移除链表元素
这时 使用一个虚拟头节点newhead->next = head就很好的解决了这个问题 curr = newhead 若curr->next符合条件 直接将 curr->next = curr->next->next 直接把要删除的节点给移除了链表 如果不符合条件 curr = curr->next 这样子的话 也没有让指针越界 也可以很好的处理了头节点的情况。当while(head->next)的时候 尾节点的情况我就要在循环外面处理了 但是尾节点的next已经没有大小 指向它 会直接报错。
2024-12-16 09:07:51
372
原创 leetcode_面试题 02.02. 返回倒数第 k 个节点
我们可以利用双指针 定义两个指针先指向头节点 然后让一个指针先往前走k次 那么两个指针相差的位置就是k 当前面的指针走出链表 也就是指向了NULL 那么后面的指针就是指向。开始的思路 ：先白遍历整个链表 然后把链表元素入栈 接着出栈k - 1 次 栈顶元素就是所求。这样子 时间复杂度和空间复杂度都是O(N)的 空间消耗看着有点大。这样子只需消耗两个指针的空间。那我们就没办法了吗 有。
2024-12-15 13:16:49
285
原创 list_
那样直接通过索引快速访问某个位置的元素。要访问链表中的某个元素，必须从头节点开始遍历，直到找到目标元素，因此。：它是由一系列节点组成的，每个节点包含数据和指向下一个节点的指针。由于内存不一定是连续的，所以不能像。我的疑问 ： 是不是顺序表存储元素时分配的内存是连续的 而链表是分开的 所以链表不支持随机访问。：它存储元素的内存是连续的，这意味着每个元素都紧接着前一个元素。可以通过索引直接访问任意位置的元素，因此支持。，访问时间是常数时间 O(1)，访问时间是线性的 O(n)
2024-12-15 07:54:48
617
原创 leetcode_785. 判断二分图
具体实现：我们可以使用染色法 先将所有节点看作白色 表示未被访问 访问该节点是 将其染色 访问该节点的下一节点之后 将其下一节点也进行染色 但是 为了表示染色的颜色只有两个 我们可以先将第一个节点染色为颜色 0 那么他的下一节点 将会是这样子染色 color[v] = 1 - color[u];实现思路：观察题目发现 给个节点只能与另外两个节点相连 才能叫作二分图 那么我们只需要找到一个节点与其他节点相连的节点数量大于两个 那么这个图将不是二分图。
2024-12-11 14:06:56
405
原创 leetcode_547 省份数量
我想的是这个节点既然是连通的 那么必将是先访问数字小的节点 在访问数字大的节点 我这么写之后 错了 我以为是 数组越界的问题 但是这个i如果超出了数组的边界不会进去for循环内部 我又把 这一句改为 i = u 我觉得就是没有必要去继续访问比自己小的节点了 但是忽略了一个问题 就是小的节点可能直接和一个更大的节点相连 并没有和另一个小的相连 这样子的话 传入的起始节点就会很大 但是大的节点和另一个小的相连了 但是访问不到 导致得到结果偏大的问题。如果按照错误的执行 将是这样子的 执行顺序。
2024-12-10 16:02:31
256
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人