哈尔滨seo网站管理,最好的免费信息发布平台,宜黄住房和城乡建设部网站,成都设计网站的公司java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 广度优先双分裂蛇 广度优先双分裂蛇
解题思路#xff1a;时间复…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 广度优先双分裂蛇 广度优先双分裂蛇
解题思路时间复杂度O( n ∗ c ∗ 26 n*c*26 n∗c∗26),n是字典中单词个数c是单词的长度26是26个字母空间复杂度O( n ∗ c ∗ 26 n*c*26 n∗c∗26) 此题就是求二维图起点到终点的最短路径问题。而这个问题本身只是中等难度。但是为什么这道题是困难难度呢因为这道题太抽象了虽然是考查图的最短路径但是题目描述很难让人联想到图所以以后只要遇到求最短路径的题看看能不能抽象成二维图能就说明考察的分裂蛇知识点。这道题只要抽象成图的数据结构就退化为1091题了,只要1091题掌握了这道题就只需要你将图的逻辑抽象出来就可以了。不过这道题的处理稍微有些不同. LeetCode1091. 二进制矩阵中的最短路径https://blog.csdn.net/grd_java/article/details/137090602 将题目给的字典中每个单词都抽象成一个顶点而两个单词如果只有一个字母不一样就抽象成这两个单词之间有一条边。这样就有了图数据结构了。然后创建两个Set集合一般是用队列但是这道题用队列反而不太好做因为我们需要确定当前A队列遇到的新单词是否在另一个队列中。一个从头开始走一个从终点开始走。 因为我们是抽象的图数据结构不知道顶点和边的关系所以我们需要每遇到一个单词就替换它里面每个字母生成一个新单词只要这个新单词是题目所给字典中的单词就说明当前这个单词和这个新单词都是存在于字典中的且两者之间有一条边。因此这些新单词就是当前结点的下一个广度优先遍历对象 因为两个单词如果只有一个字母不一样就抽象成这两个单词之间有一条边,但是题目本身没给这个关系我们只能一个个枚举修改这个单词中单个字母时间复杂度是O( c ∗ 26 c*26 c∗26),c是这个单词由几个字母组成 当首尾两个集合相遇的一瞬间其代表的路径就是最短路径双分裂蛇的特点。 代码官方增加了测试用例相同的算法原来是21ms超越100%现在只能到达22ms已经无法超越100%了 class Solution {//将单词抽象成图结构然后通过双向广度优先算法求最短路径//每个单词都是一个顶点如果两个单词只有一个字母不同则他俩直接有一条边public int ladderLength(String beginWord, String endWord, ListString wordList) {// 将单词列表转换为集合便于快速检查单词是否存在于列表中SetString wordSet new HashSet(wordList);if (!wordSet.contains(endWord)) return 0; // 如果结束单词不在列表中无法完成转换直接返回0// 使用两个集合代替队列分别存储从开始和结束单词出发的广度优先搜索的边界。双向广度优先一个从起点一个从终点找SetString beginSet new HashSet(), endSet new HashSet();int len 1; // 初始化路径长度为1因为开始单词也计入路径int strLen beginWord.length(); // 单词的长度假设所有单词长度相同HashSetString visited new HashSet(); // 记录已访问的单词避免重复处理我们不更改原表使用新的表来标志某个单词是否已经访问// 将开始和结束单词加入对应的集合beginSet.add(beginWord);endSet.add(endWord);// 只要两个集合都非空就继续执行双向搜索while (!beginSet.isEmpty() !endSet.isEmpty()) {// 总是选择较小的集合进行扩展以减少下一轮处理的单词数量if (beginSet.size() endSet.size()) {SetString temp beginSet;beginSet endSet;endSet temp;}SetString temp new HashSet(); // 用于存储下一轮扩展的结果如果是队列就不需要这步for (String word : beginSet) {//遍历当前队列集合中结点让他们走一步每次只走一步char[] chs word.toCharArray();// 尝试更改当前单词的每一个字符看看是否可以接龙for (int i 0; i chs.length; i) {for (char c a; c z; c) {//用a到z依次替换char old chs[i]; // 保存原始字符chs[i] c;//用a-z依次替换i位置字符String target String.valueOf(chs); // 生成新单词// 如果新单词在另一端集合中说明找到了最短路径if (endSet.contains(target)) return len 1;// 如果新单词未访问且存在于单词列表中则加入下一轮搜索if (!visited.contains(target) wordSet.contains(target)) {temp.add(target);visited.add(target); // 标记为已访问}chs[i] old; // 恢复原始字符以便下一次修改}}}beginSet temp; // 更新beginSet为下一轮搜索的边界len; // 每完成一轮双向搜索路径长度加1因为我们规定每次只走一步}return 0; // 如果无法连接开始和结束单词返回0}
}
