力扣刷题笔记:动态规划与链表操作

需积分: 0 1 下载量 194 浏览量 更新于2024-06-30 收藏 966KB PDF 举报
"力扣500题刷题笔记2,包含C++代码实现,涉及动态规划、链表操作和双指针技术" 本资源主要涵盖了LeetCode中的三道经典问题,分别是力扣500题中的某一部分,包括杨辉三角II、移除链表元素和反转字符串中的单词III。每个问题都有相应的C++解决方案,并且运用了不同的算法思想。 首先,力扣500题中的“杨辉三角II”是一个典型的动态规划问题。动态规划是一种通过构建子问题来解决复杂问题的方法。在这个问题中,目标是生成杨辉三角的某一行。代码中定义了一个二维数组`f`,用于存储每一行的元素。状态转移方程`f[i][j]=f[i-1][j]+f[i-1][j-1]`表示当前行的第`j`个元素等于上一行的第`j`个元素与上一行的第`j-1`个元素之和。初始化`f[i][0]`和`f[i][i]`为1,因为这两边的元素始终为1。最后返回第`n`行的结果。 接下来是“移除链表元素”问题,这是一个链表操作的模拟题目。问题要求移除链表中所有值等于`val`的节点。代码中创建了一个虚拟头节点`dummy`,方便处理边界情况。然后使用双指针`p`和`dummy`遍历链表,当遇到值为`val`的节点时,将其跳过,否则移动指针。最后返回`dummy->next`作为新链表的头节点。 最后,"反转字符串中的单词III"问题使用了双指针技术。双指针法是一种在数组或字符串中同时从两端向中间处理元素的有效方法。在这个问题中,遍历整个字符串`s`,当遇到空格时,跳过并更新单词的起始位置`j`;如果`j`不指向空格,就让`j`向后移动。然后对`s[i, j-1]`这个单词进行翻转。遍历结束后返回字符串`s`。 这些题目展示了C++在解决算法问题上的灵活性和效率,同时也体现了动态规划、链表操作和双指针等基础算法在实际问题中的应用。通过深入理解和实践这些代码,可以提升在数据结构和算法方面的能力,对于准备LeetCode或其他编程竞赛非常有帮助。