办公用品网站系统建设源码,织梦模板添加网站地图,网站建设系统开发需要多少钱,企业网站开发外包合同刷题记录 1143. 最长公共子序列1035. 不相交的线53. 最大子数组和动态规划优化版 392. 判断子序列 1143. 最长公共子序列
leetcode题目地址
本题和300. 最长递增子序列相似#xff08;题解#xff09;。
使用动态规划#xff1a;
dp数组含义#xff1a;dp[i][j]表示 以… 刷题记录 1143. 最长公共子序列1035. 不相交的线53. 最大子数组和动态规划优化版 392. 判断子序列 1143. 最长公共子序列
leetcode题目地址
本题和300. 最长递增子序列相似题解。
使用动态规划
dp数组含义dp[i][j]表示 以text1[i-1]结尾的子串A 和 以text2[j-1]结尾的子串B 的最长公共子序列的长度。思路同300. 最长递增子序列每个状态更新基于前面的状态为了防止越界dp数组下标从1开始。状态转移方程
当 text1[i-1] text2[j-1] 时dp[i][j] dp[i-1][j-1] 1;当 text1[i-1] text2[j-1] 时dp[i][j] max(dp[i-1][j], dp[i][j-1]) 这里解释一下 max(dp[i-1][j], dp[i][j-1]) 的含义由于dp数组存储的是两个子串的最长公共子序列的长度当两个子串的单个字符不匹配时对应下标处的dp值要赋值为前面子串的匹配情况取最长即dp[i-1][j]表示以text1[i-2]结尾的子串A和以text2[j-1]结尾的子串B 的最长公共子序列的长度dp[i][j-1]表示以text1[i-1]结尾的子串A和以text2[j-2]结尾的子串B 的最长公共子序列的长度。
时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m) 空间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)
// java
class Solution {public int longestCommonSubsequence(String text1, String text2) {int len1 text1.length(), len2 text2.length();char[] arr1 text1.toCharArray(), arr2 text2.toCharArray();int[][] dp new int[len11][len21];for(int i 1; i len1; i){for (int j 1; j len2; j){if(arr1[i-1] arr2[j-1]){dp[i][j] dp[i-1][j-1] 1;} else{dp[i][j] Math.max(dp[i][j-1], dp[i-1][j]);}// System.out.print(dp[j] );}// System.out.println();}return dp[len1][len2];}
}1035. 不相交的线
leetcode题目地址
本题其实与上一题1143. 最长公共子序列的思路完全一致。题目的描述时要求找不相交的线的最大连线数而不相交的线其实就是找两个序列的公共子序列不相交就是两个子序列在原序列中相对顺序一致。
时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m) 空间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)
// java
class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int len1 nums1.length, len2 nums2.length;int[][] dp new int[len11][len21];for(int i1; ilen1; i){for(int j1; jlen2; j){if(nums1[i-1] nums2[j-1]){dp[i][j] dp[i-1][j-1] 1;} else{dp[i][j] Math.max(dp[i-1][j], dp[i][j-1]);}}}return dp[len1][len2];}
}53. 最大子数组和
leetcode题目地址 dp数组含义 dp[i]表示以nums[i]结尾包含的最大子数组和 状态转移方程 dp[i] Math.max(dp[i-1] nums[i], nums[i]); dp[i-1] nums[i]表示上一个以nums[i-1]结尾的子序列加入当前nums[i]nums[i]表示从当前元素开始从头计算仅包含当前元素的子序列 初始化 dp[i]表示以nums[i]结尾包含的最大子数组和因此dp[0]初始化为nums[0]后面状态均为0.
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n)
动态规划
// java
class Solution {public int maxSubArray(int[] nums) {int len nums.length;int[] dp new int[len];dp[0] nums[0];int result nums[0];for(int i1; ilen; i){dp[i] Math.max(dp[i-1] nums[i], nums[i]);result Math.max(dp[i], result);}return result;}
}优化版
可以看到在动规中每个状态的更新都仅依赖于前一个状态因此无需使用数组仅使用一个变量来记录前一个状态。
时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)
// java
class Solution {public int maxSubArray(int[] nums) {int len nums.length;int res nums[0];int result nums[0];for(int i1; ilen; i){res Math.max(res nums[i], nums[i]);result Math.max(res, result);}return result;}
}
392. 判断子序列
leetcode题目地址
本题本质上依旧是寻找最长公共子序列。给定s和t判断s是否是t的子序列也就是查看s和t的最长公共子序列长度是否等于s的长度。
dp数组含义 dp[i][j]表示 以s[i-1]结尾的子串A 和 以t[j-1]结尾的子串B 的最长公共子序列。状态转移方程 当s[i-1] t[j-1]时dp[i][j] dp[i-1][j-1] 1;当s[i-1] ! t[j-1]时dp[i][j] dp[i][j-1];
这里不匹配时为什么是 dp[i][j] dp[i][j-1] 而不是 dp[i][j] Math.max(dp[i-1][j], dp[i][j-1]) 因为是在t中查找s是否是子序列因此在不匹配时只能删除t中的字符来查看分别以s[i-1]和t[j-2]结尾的子串的匹配情况。
而1143. 最长公共子序列不给定谁为子串因此需要分别考虑各自为另一个字符串的子串的情况。
时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m) 空间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)
// java
class Solution {public boolean isSubsequence(String s, String t) {char[] sArry s.toCharArray();char[] tArry t.toCharArray();int len1 s.length(), len2 t.length();int[][] dp new int[len11][len21];for(int i1; ilen1; i){for(int j1; jlen2; j){if(sArry[i-1] tArry[j-1]){dp[i][j] dp[i-1][j-1] 1;} else {dp[i][j] dp[i][j-1];}// System.out.print(dp[i][j] );}// System.out.println();}return dp[len1][len2] len1;}
}
文章转载自： http://www.morning.csdgt.cn.gov.cn.csdgt.cn http://www.morning.wslr.cn.gov.cn.wslr.cn http://www.morning.jwwfk.cn.gov.cn.jwwfk.cn http://www.morning.nwjd.cn.gov.cn.nwjd.cn http://www.morning.qwqzk.cn.gov.cn.qwqzk.cn http://www.morning.ccdyc.cn.gov.cn.ccdyc.cn http://www.morning.qwwcf.cn.gov.cn.qwwcf.cn http://www.morning.yrjym.cn.gov.cn.yrjym.cn http://www.morning.mhnd.cn.gov.cn.mhnd.cn http://www.morning.24vy.com.gov.cn.24vy.com http://www.morning.dyxlm.cn.gov.cn.dyxlm.cn http://www.morning.wqpsf.cn.gov.cn.wqpsf.cn http://www.morning.cxnyg.cn.gov.cn.cxnyg.cn http://www.morning.sgmgz.cn.gov.cn.sgmgz.cn http://www.morning.mzhjx.cn.gov.cn.mzhjx.cn http://www.morning.iiunion.com.gov.cn.iiunion.com http://www.morning.kqpsj.cn.gov.cn.kqpsj.cn http://www.morning.jcbmm.cn.gov.cn.jcbmm.cn http://www.morning.hrzymy.com.gov.cn.hrzymy.com http://www.morning.zdbfl.cn.gov.cn.zdbfl.cn http://www.morning.tpxgm.cn.gov.cn.tpxgm.cn http://www.morning.pffqh.cn.gov.cn.pffqh.cn http://www.morning.chkfp.cn.gov.cn.chkfp.cn http://www.morning.lqypx.cn.gov.cn.lqypx.cn http://www.morning.yjtnc.cn.gov.cn.yjtnc.cn http://www.morning.cfpq.cn.gov.cn.cfpq.cn http://www.morning.ho-use.cn.gov.cn.ho-use.cn http://www.morning.srwny.cn.gov.cn.srwny.cn http://www.morning.ndcf.cn.gov.cn.ndcf.cn http://www.morning.kpmxn.cn.gov.cn.kpmxn.cn http://www.morning.gbfuy28.cn.gov.cn.gbfuy28.cn http://www.morning.lsgjf.cn.gov.cn.lsgjf.cn http://www.morning.mzrqj.cn.gov.cn.mzrqj.cn http://www.morning.cjnfb.cn.gov.cn.cjnfb.cn http://www.morning.rlhh.cn.gov.cn.rlhh.cn http://www.morning.fengnue.com.gov.cn.fengnue.com http://www.morning.qsxxl.cn.gov.cn.qsxxl.cn http://www.morning.qdxkn.cn.gov.cn.qdxkn.cn http://www.morning.fhykt.cn.gov.cn.fhykt.cn http://www.morning.pypqf.cn.gov.cn.pypqf.cn http://www.morning.ntqqm.cn.gov.cn.ntqqm.cn http://www.morning.fzqfb.cn.gov.cn.fzqfb.cn http://www.morning.lhjmq.cn.gov.cn.lhjmq.cn http://www.morning.rdwm.cn.gov.cn.rdwm.cn http://www.morning.coatingonline.com.cn.gov.cn.coatingonline.com.cn http://www.morning.wnhsw.cn.gov.cn.wnhsw.cn http://www.morning.mpscg.cn.gov.cn.mpscg.cn http://www.morning.wbhzr.cn.gov.cn.wbhzr.cn http://www.morning.rqpgk.cn.gov.cn.rqpgk.cn http://www.morning.lmfmd.cn.gov.cn.lmfmd.cn http://www.morning.ycgrl.cn.gov.cn.ycgrl.cn http://www.morning.xykst.cn.gov.cn.xykst.cn http://www.morning.bpmfz.cn.gov.cn.bpmfz.cn http://www.morning.rqfnl.cn.gov.cn.rqfnl.cn http://www.morning.bwzzt.cn.gov.cn.bwzzt.cn http://www.morning.fzqfb.cn.gov.cn.fzqfb.cn http://www.morning.qnhcx.cn.gov.cn.qnhcx.cn http://www.morning.c7493.cn.gov.cn.c7493.cn http://www.morning.tkztx.cn.gov.cn.tkztx.cn http://www.morning.ckctj.cn.gov.cn.ckctj.cn http://www.morning.ljglc.cn.gov.cn.ljglc.cn http://www.morning.nrbqf.cn.gov.cn.nrbqf.cn http://www.morning.qcslh.cn.gov.cn.qcslh.cn http://www.morning.ngcw.cn.gov.cn.ngcw.cn http://www.morning.zphlb.cn.gov.cn.zphlb.cn http://www.morning.zycll.cn.gov.cn.zycll.cn http://www.morning.hlrtzcj.cn.gov.cn.hlrtzcj.cn http://www.morning.tkxr.cn.gov.cn.tkxr.cn http://www.morning.zglrl.cn.gov.cn.zglrl.cn http://www.morning.thrtt.cn.gov.cn.thrtt.cn http://www.morning.xlclj.cn.gov.cn.xlclj.cn http://www.morning.htqrh.cn.gov.cn.htqrh.cn http://www.morning.jnzfs.cn.gov.cn.jnzfs.cn http://www.morning.ftsmg.com.gov.cn.ftsmg.com http://www.morning.hchrb.cn.gov.cn.hchrb.cn http://www.morning.ckcjq.cn.gov.cn.ckcjq.cn http://www.morning.rfbpq.cn.gov.cn.rfbpq.cn http://www.morning.pfnlc.cn.gov.cn.pfnlc.cn http://www.morning.cxryx.cn.gov.cn.cxryx.cn http://www.morning.kmqwp.cn.gov.cn.kmqwp.cn
