分类 网站模板,私人定制哪个网站做的比较好,php搭建网站软件下载,定制企业网站建设哪家好KMP|DFS回溯剪枝 #1、NC149kmp 初步思路#xff1a; 两层for循环#xff0c;一个T的字符开始与 S的字符比较#xff0c;挨个比较#xff0c;遇到不同就continue当前T的字符#xff0c;重复步骤》效率太低#xff0c;超时 eg: TABSABABABD SABABD
S#xff01;A时#… KMP|DFS回溯剪枝 #1、NC149kmp 初步思路 两层for循环一个T的字符开始与 S的字符比较挨个比较遇到不同就continue当前T的字符重复步骤》效率太低超时 eg: TABSABABABD SABABD
SA时退回到A与S比较发现不同 继续比较A与AB与B…A与D不相等了了。 此时D前面有两个AB所以指向S的字符索引只往前移动两个字符退回到AB|这里ABD即第一个AB公共前缀后面的A这里。 继续A与A比较…
KMP的核心思想是不必退回到开始的地方比较过的地方就不用重复比较了 用一个数组去记录应该退回到哪里合适
next[j - 1] 表示在 S[0…j-1] 这个子字符串中最长的相同前缀和后缀的长度。如果 S[j] 和当前要比较的字符不匹配这意味着 S[j] 不能作为前缀的一部分因此需要找到一个更短的前缀使得 S[0…next[j-1]] 和 S[i…] 能够匹配。 while 循环用于在 next 数组构建过程中当当前字符 S.charAt(i) 与 S.charAt(j) 不匹配时回溯找到 j 的下一个有效值。这个值是 S[0…j-1] 的最长相同前缀和后缀的长度。 为什么 while 在 if 前面
当 S.charAt(j) ! S.charAt(i) 时说明当前 j 所对应的前缀无法与 i 位置的字符匹配。此时需要减小 j 的值直到找到一个匹配的前缀或者 j 减到 0。
while 循环确保即使在多次不匹配的情况下j 也能正确地回溯到一个有效的值。如果使用 if 语句那么在 j 0 且 S.charAt(j) ! S.charAt(i) 时j 只会减少 1这可能不会找到正确的前缀匹配。
if 条件的作用当 S.charAt(j) S.charAt(i) 时说明当前字符匹配j 可以安全地向前移动一位因为 S[0…j] 和 S[i…]从 i 开始的剩余字符串有一个共同的字符可以匹配。
next[i] j; 的意义 无论 S.charAt(j) 和 S.charAt(i) 是否匹配next[i] 都被设置为 j 的当前值。 如果字符匹配j 已经增加了 1next[i] 反映了这个增加 如果字符不匹配j 通过 while 循环回溯到了正确的值next[i] 反映了这个回溯。 public int[] getNext(String S) {int l S.length();// 获得next数组int[] next new int[l];next[0] 0; //没有公共前缀int j 0;// AABAS// 01for (int i 1; i l; i) {while (j 0 S.charAt(j) ! S.charAt(i)) {j next[j - 1]; //会退一步判断// next[j - 1] 表示在 S[0...j-1] 这个子字符串中最长的相同前缀和后缀的长度。如果 S[j] 和当前要比较的字符不匹配这意味着 S[j] 不能作为前缀的一部分因此需要找到一个更短的前缀使得 S[0...next[j-1]] 和 S[i...] 能够匹配。}if (S.charAt(j) S.charAt(i)) {j;}next[i] j; //验证到了这一步了。}return next;}通过相同的思路使用next[]数组 先while退回到合适的索引位置针对S而言 然后是if判断S的索引; 如果S的索引走到了S的末尾那么说明已在T中找到等于S 的字串。 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** 计算模板串S在文本串T中出现了多少次* param S string字符串 模板串* param T string字符串 文本串* return int整型*/public int kmp (String S, String T) {// write code hereint slS.length();int tlT.length();int count0;int[] nextgetNext(S);int j0;for(int i0;itl;i){while(j0S.charAt(j)!T.charAt(i)){jnext[j-1];}if(S.charAt(j)T.charAt(i)){j;}if(jsl){count;jnext[j-1];//会退回去继续判断}}return count;}public int[] getNext(String S) {int l S.length();// 获得next数组int[] next new int[l];next[0] 0; //没有公共前缀int j 0;// AABAS// 01for (int i 1; i l; i) {while (j 0 S.charAt(j) ! S.charAt(i)) {j next[j - 1]; //会退一步判断// next[j - 1] 表示在 S[0...j-1] 这个子字符串中最长的相同前缀和后缀的长度。如果 S[j] 和当前要比较的字符不匹配这意味着 S[j] 不能作为前缀的一部分因此需要找到一个更短的前缀使得 S[0...next[j-1]] 和 S[i...] 能够匹配。}if (S.charAt(j) S.charAt(i)) {j;}next[i] j; //验证到了这一步了。}return next;}
}第二次出现的jnext[j-1]; 不是在 “j 往前走的时候已经经历过了” 的位置停止而是在每次找到匹配或确定不匹配后为下一次可能的匹配做准备。将 j 设置为 next[j-1] 允许我们在 T 的下一个字符处继续搜索。这是因为 S[0…next[j-1]] 已经是一个匹配的前缀我们可以从这个前缀的末尾开始尝试与 T 中的下一个字符匹配。
避免重复匹配如果我们将 j 重置为 0那么我们会在 T 中重复计算已经匹配的 S 的部分。使用 next[j-1] 确保我们不会重复计算并且可以继续从 T 的下一个字符开始搜索。
优化搜索过程通过这种方式KMP 算法可以在找到一次匹配后快速跳到可能的下一个匹配位置而不必从头开始搜索从而提高搜索效率。
#2、DFS回溯剪枝法 想到了树不同的子节点深度遍历下去有不同的路径结果。 分析题意 X.X.X.X 每个X∈[0,255], 要求不同出现0MM∈[0,9] 剩余X的个数1字符串的长度剩余X的个数3因为X是1到3位数组成 树有不同的子节点子节点的子节点… 即树的不同层代表着字符串s的剩余长度即当前走到了s的哪一位了索引位置cur。 public void dfs(String s,int cur){if(tmp.size()4 curs.length()){res.add(tmp.get(0).tmp.get(1).tmp.get(2).tmp.get(3));}//jianzhi if(s.length()-cur3*(4-tmp.size()))//每段大于3{return;}if(s.length()-cur4-tmp.size())//小于1{return;}int num0;//当前节点的操作即X.X.X.X中的一个X //X:从s的某个位置索引cur开始i∈[cur,cur2],且is.length()for(int icur;icur3is.length();i)//一个一个数字的判断{//0,1,2numnum*10(s.charAt(i)-0);//数字//百十个位if(num0||num255)//数字越界了就不要了{break;}//tmp.add(s.substring(cur,i1));//截取【0255】之间的数字//判断写一个位置上可能的Xdfs(s,i1);//继续判断tmp.remove(tmp.size()-1);//为啥// 回溯允许算法“回到”上一个状态重新考虑不同的数字组合。if(num0){break;//只能0.不能02|09这些}}}import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param s string字符串 * return string字符串ArrayList*/ArrayListString resnew ArrayList();ArrayListString tmpnew ArrayList();public ArrayListString restoreIpAddresses (String s) {// write code here// 限制每一个[1,3]位置以及如果是3那么数字小于255否则挪给别的// 1则不能以0开头// 根据位数判断dfs(s,0);return res;}public void dfs(String s,int cur){if(tmp.size()4 curs.length()){res.add(tmp.get(0).tmp.get(1).tmp.get(2).tmp.get(3));}//jianzhi if(s.length()-cur3*(4-tmp.size()))//每段大于3{return;}if(s.length()-cur4-tmp.size())//小于1{return;}int num0;for(int icur;icur3is.length();i)//一个一个数字的判断{//0,1,2numnum*10(s.charAt(i)-0);//数字if(num0||num255)//数字越界了就不要了{break;}tmp.add(s.substring(cur,i1));//截取【0255】之间的数字dfs(s,i1);//继续判断tmp.remove(tmp.size()-1);//为啥// 回溯允许算法“回到”上一个状态重新考虑不同的数字组合。if(num0){break;//只能0.不能02|09这些}}}
}
