企业官网建设流程全解析

许昌 网站开发,中国互联网协会,wordpress the7教程,网站开发介绍双指针 思路分析 使用双指针 sIndex 和 tIndex 分别指向字符串 s 和 t。遍历 t#xff0c;如果 s 当前字符和 t 当前字符相同#xff0c;sIndex 右移#xff0c;tIndex 始终右移。最后判断 sIndex 是否等于 s 的长度#xff0c;如果是则 s 是 t 的子序列。 代码实现 public…双指针思路分析使用双指针 sIndex 和 tIndex 分别指向字符串 s 和 t。遍历 t如果 s 当前字符和 t 当前字符相同sIndex 右移tIndex 始终右移。最后判断 sIndex 是否等于 s 的长度如果是则 s 是 t 的子序列。代码实现publicbooleanisSubsequence(Strings,Stringt){// 1. 定义指针i,j分别指向s,t的第一个元素inti0;intj0;// 2. 遍历字符串t校验字符串s的每个字符是否都在t中while(is.length()jt.length()){if(s.charAt(i)t.charAt(j)){i;}j;}// 3. 如果i指针遍历完了s字符串说明s是t的子序列returnis.length();}复杂度分析时间复杂度为 O(n)这里 n 是字符串 t 的长度。空间复杂度为O(1)动态规划思路分析定义一个二维数组 dp[i][j]其中 i 表示字符串 s 的前 i 个字符j 表示字符串 t 的前 j 个字符。dp[i][j] 的值为 true 表示 s 的前 i 个字符是 t 的前 j 个字符的子序列否则为 false。初始化 dp[0][j] 为 true因为空字符串是任何字符串的子序列。状态转移方程为如果 s[i - 1] t[j - 1]那么 dp[i][j] dp[i - 1][j - 1]表示如果当前字符相等s 的前 i 个字符是 t 的前 j 个字符的子序列当且仅当 s 的前 i - 1 个字符是 t 的前 j - 1 个字符的子序列。如果 s[i - 1] ! t[j - 1]那么 dp[i][j] dp[i][j - 1]表示如果当前字符不相等s 的前 i 个字符是 t 的前 j 个字符的子序列当且仅当 s 的前 i 个字符是 t 的前 j - 1 个字符的子序列。最终 dp[s.length()][t.length()] 的值即为所求。代码实现publicbooleanisSubsequence2(Strings,Stringt){intms.length();intnt.length();boolean[][]dpnewboolean[m1][n1];for(intj0;jn;j){dp[0][j]true;}for(inti1;im;i){for(intj1;jn;j){if(s.charAt(i-1)t.charAt(j-1)){dp[i][j]dp[i-1][j-1];}else{dp[i][j]dp[i][j-1];}}}returndp[m][n];}复杂度分析时间复杂度为O(m∗n)其中 m 是字符串 s 的长度n 是字符串 t 的长度因为需要填充一个 m * n 的二维数组。空间复杂度为 O(m∗n)即二维数组的大小。