代码编织梦想

1143.最长公共子序列

  • 这道题与#718区别在于这里不要求是连续的了,但要有相对顺序,即:"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。
  • 与#718类似,在定义dp数组的时候依然可以按照题解的定义方式,即dp[i][j]:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]。但是也像在#718有的疑问一样,定义并不直观,那么就按照长度为[0, i]的字符串text1和长度为[0, j]的字符串text2来定义,这样就需要初始化dp数组的第一行和第一列。
  • 具体代码参考#718第三种解法来写。。。

1035.不相交的线

  • 仔细阅读题目发现:直线不能相交,这就是说明在字符串nums1中找到一个与字符串nums2相同的子序列,且这个子序列不能改变相对顺序。只要相对顺序不改变,链接相同数字的直线就不会相交。
  • 本题说是求绘制的最大连线数,其实就是求两个字符串的最长公共子序列的长度!
  • 这就与#1143一模一样了
  • #718,#1143和#1035一起整理复习!!!

53. 最大子序和

五部曲:

  1. 确定dp数组以及下标的含义:dp[i]:包括下标i之前的最大连续子序列和为dp[i]
  2. 确定递推公式:dp[i] = max(dp[i - 1] + nums[i], nums[i]); 

    因为dp[i]只有两个方向可以推出来:

    1. dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和
    2. nums[i],即:从头开始计算当前连续子序列和
  3. dp数组如何初始化:从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态,dp[0]就是递推公式的基础。dp[0] = nums[0]
  4. 确定遍历顺序:递推公式中dp[i]依赖于dp[i - 1]的状态,需要从前向后遍历。
  5. 打印检查

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/jzh013/article/details/128013488

代码随想录算法训练营day4 | 24.两两交换链表中的节点, 19.删除链表的倒数第n个节点, 160.链表相交, 142.环形链表ii_cccccilu的博客-爱代码爱编程

Leetcode 24. Swap Nodes in Pairs 首先遇到链表的题目,我们一般会使用一个虚拟头来更好的处理第一个 node,然后将 cur pointer 初始设在 dummy node。 解决这道题目需要三个步骤: 操作之后,链表如下: 这三个步骤之后 node 2 和 node 1 就换好了,之后需要将 cur po

代码随想录算法训练营day4|leetdcode24/19/160/142_jerrrrrrry99的博客-爱代码爱编程

Leetcode24 两两交换链表中的节点 思路 首先这道题是要知道如果有偶数个节点,那我们可以刚好完成交换。 如果是奇数个节点,那么当我们发现next的next节点为空的时候说明我们已经完成了交换,那么最后一个节点就不用再交换了 这里我们每次对于节点做一个保存操作 例如:     cur = res.next 这里我们把节点1 进行保存

【leetcode】-代码随想录算法训练营day4 | 24. 两两交换链表中的节点,19.删除链表的倒数第n个节点,面试题 02.07. 链表相交,142.环形链表ii_大兔砸的博客-爱代码爱编程

Leetcode题目-24. Swap Nodes in Pairs 链接: 24. Swap Nodes in Pairs 思路 此题主要还是对虚拟头节点的运用。经过简单的画图可以了解,两两交换过程中,对头两个节点的

代码随想录算法训练营第四天|24. 两两交换链表中的节点,19.删除链表的倒数第n个节点,面试题02.07. 链表相交,142.环形链表ii,总结_扭一扭.的博客-爱代码爱编程

24. 两两交换链表中的节点 看完文章后的想法: 1. 操作指针:指向需要反转的两个节点中的前一个。 2. 链表结点个数为奇数时,cur.next.next == null 时遍历结束;链表结点个数为偶数时,cur.next == null 时遍历结束。即,循环条件:cur.next != null && cur.next.next

代码随想录算法训练营-day04-24. 两两交换链表中的节点、19.删除链表的倒数第n个节点、面试题 02.07. 链表相交、142.环形链表ii_依旧1919的博客-爱代码爱编程

24. 两两交换链表中的节点 学习文章链接:代码分析: 代码的主体结构基于翻转链表的代码。设计虚拟头节点,方便翻转严格按照三步走逻辑,cur为虚拟头节点。 代码 class Solution { p

代码随想录算法训练营第三期day04-链表02_weixin_57614037的博客-爱代码爱编程

目录 1.T24:两两交换链表中的节点 代码实现: C++: Java: 2.T19:删除链表的倒数第N个节点 代码实现: C++: Java: 3.T160:链表相交(面试题 02.07. 链表相交) 代码实现: C++: Java: 4.T142:环形链表 II 4.1.判断链表是否有环 4.2.如果有环,如何找到这个环的

代码随想录算法训练营第四天 | 24. 两两交换链表中的节点 、 19.删除链表的倒数第n个节点 、面试题 02.07. 链表相交 、142.环形链表ii_小刘很ok的博客-爱代码爱编程

24. 两两交换链表中的节点 题目链接:24. 两两交换链表中的节点 【思路】 画图后就容易理解了,别忘了定义临时变量保存要被丢掉的节点。借用卡哥的图来看一下: 注意: 设置虚拟头结点可以方便的操作头结点注意设置临

代码随想录训练营第9天|leetcode :28. 实现 strstr()、459.重复的子字符串、双指针回顾__忆昔的博客-爱代码爱编程

参考 代码随想录 题目一:Leetode 28. 实现 strStr() class Solution { public: int strStr(string haystack, string needle)

代码随想录算法训练营第53天 | 1143.最长公共子序列 1035.不相交的线 53. 最大子序和_lebowskii的博客-爱代码爱编程

代码随想录系列文章目录 动态规划篇 —— 线性dp 文章目录 代码随想录系列文章目录1143.最长公共子序列1035.不相交的线53.最大子序和 1143.最长公共子序列 题目链接 昨天做了一个最

代码随想录算法训练营day53||1035.不相交的线||53. 最大子序和_非常的的博客-爱代码爱编程

1035.不相交的线 思路: 直线不能相交,就说明在字符串A中找到一个与字符串B相同的子序列,而且这个子序列不能改变相对顺序,只要相对顺序不改变,链接相同数字的直线就不会相交。 class Solution { public: int maxUncrossedLines(vector<int>& A, vector<

代码随想录训练营day53_jiuyu_m的博客-爱代码爱编程

题目一:最长公共子序列 力扣题目链接 题目描述: 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任

代码随想录算法训练营第四天| javascript| 24. 两两交换链表中的节点 19.删除链表的倒数第n个节点 面试题 02.07. 链表相交 142.环形链表ii_阿悦今天学习了嘛的博客-爱代码爱编程

主要是链表的训练 24. 两两交换链表中的节点 leetcode-24 题目描述 && 测试案例 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成

[代码随想录算法训练营]刷题笔记 day 4_f44011097的博客-爱代码爱编程

24. 两两交换链表中的节点 class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* dummy = new ListNode(); dummy->next = head; ListNode* c

代码随想录算法训练营 day4 | 链表 | lc24. 两两交换链表中的节点、lc19. 删除链表的倒数第 n 个结点、lc面试题 02.07. 链表相交、lc142. 环形链表 ii-爱代码爱编程

代码随想录算法训练营 Day4 | 链表 | LC24. 两两交换链表中的节点、LC19. 删除链表的倒数第 N 个结点、LC面试题 02.07. 链表相交、LC142. 环形链表 II 因为tw面试后有点摆烂,然后

(二刷)代码随想录算法训练营day4 | 24. 两两交换链表中的节点, 19.删除链表的倒数第n个节点, 160. 链表相交 , 142.环形链表ii-爱代码爱编程

题目:链表 24. 两两交换链表中的节点 (medium) 终止条件的判断 由于是两两交换,那么就自然需要考虑偶数和奇数个节点的情况:偶数时curr.next = None终止;奇数时curr.next.next = None终止。以上讨论同样适用于空链表的情况,因为链表节点数量是0,就符合偶数的情况。 那么为什么不可以先写curr

代码随想录算法训练营day4 | | 24. 两两交换链表中的节点 ,19.删除链表的倒数第n个节点 , 面试题 02.07. 链表相交-爱代码爱编程

第一题  19.Remove Nth Node From End of List  第一次根据题意自己写代码: //这个编码是错误的!!! class Solution{ public ListNode removeNthFromEnd(ListNode head, int n){ ListNode dummy = n

代码随想录算法训练营第四天 | leetcode24. 两两交换链表中的节点,19.删除链表的倒数第n个节点,面试题 02.07. 链表相交 ,142.环形链表ii-爱代码爱编程

代码随想录算法训练营第四天 | LeetCode24. 两两交换链表中的节点,19.删除链表的倒数第N个节点,面试题 02.07. 链表相交 ,142.环形链表II 一、 LeetCode24. 两两交换链表中

代码随想录算法训练营day4-爱代码爱编程

代码随想录算法训练营day4 接着链表。 24.两两交换链表中的节点leetcode24 Swap Nodes in Pairs class Solution { public: ListNode* s