怎么向网站添加型号查询功能,网站建设企业排名推广,网站建设胡菘,十大高端网站设计131.分割回文串
131. 分割回文串 - 力扣#xff08;LeetCode#xff09;
代码随想录 (programmercarl.com)
带你学透回溯算法-分割回文串#xff08;对应力扣题目#xff1a;131.分割回文串#xff09;| 回溯法精讲#xff01;_哔哩哔哩_bilibili 给你一个字符串 sLeetCode
代码随想录 (programmercarl.com)
带你学透回溯算法-分割回文串对应力扣题目131.分割回文串| 回溯法精讲_哔哩哔哩_bilibili 给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1 输入s aab
输出[[a,a,b],[aa,b]]示例 2 输入s a
输出[[a]]提示 1 s.length 16s 仅由小写英文字母组成 切割问题类似于组合问题。这个题由于在回溯这个板块下面一开始还是知道应该用回溯来解也能画出图但是自己在分析的时候对于回溯三部曲没有分析出来。 回溯三部曲
1、确定递归的参数 全局变量path存放切割后回文的子串二维数组result存放结果集因为切割过的地方需要标记出来避免重复切所以还需要startIndex // 声明一个二维列表用于存储所有的分割方案ListListString lists new ArrayList();// 声明一个双端队列用于辅助回溯DequeString deque new LinkedList();2、确定终止条件自己就是分析到这里卡住了
startIndex是分割线当分割线分割到末尾时说明可以终止了
private void backTracking(String s, int startIndex) {// 如果起始位置大于等于字符串 s 的长度说明找到了一组分割方案if (startIndex s.length()) {lists.add(new ArrayList(deque)); // 将当前双端队列中的元素加入结果列表中return;
}
3、确定单层遍历的逻辑[startIndex,i]是我们要截取的子串如果这个子串是回文子串就加入到path中
for (int i startIndex; i s.length(); i) {// 如果是回文子串则记录到双端队列中if (isPalindrome(s, startIndex, i)) {String str s.substring(startIndex, i 1); // 截取回文子串deque.addLast(str); // 将回文子串加入双端队列的末尾} else {continue; // 如果不是回文子串则跳过}// 递归调用回溯函数起始位置后移继续搜索下一个回文子串backTracking(s, i 1);deque.removeLast(); // 回溯移除最后一个元素尝试其他分割方案}
确定回文子串
双指针法汗颜这个还真没想到..... // 判断字符串是否是回文串private boolean isPalindrome(String s, int startIndex, int end) {// 从两端向中间比较字符是否相等直到指针相遇for (int i startIndex, j end; i j; i, j--) {if (s.charAt(i) ! s.charAt(j)) {return false; // 如果发现字符不相等则不是回文串}}return true; // 如果全部字符相等则是回文串}
综合代码
class Solution {// 声明一个二维列表用于存储所有的分割方案ListListString lists new ArrayList();// 声明一个双端队列用于辅助回溯DequeString deque new LinkedList();// 主函数用于调用回溯函数并返回结果public ListListString partition(String s) {backTracking(s, 0); // 调用回溯函数开始搜索return lists; // 返回所有的分割方案}// 回溯函数用于搜索所有的分割方案private void backTracking(String s, int startIndex) {// 如果起始位置大于等于字符串 s 的长度说明找到了一组分割方案if (startIndex s.length()) {lists.add(new ArrayList(deque)); // 将当前双端队列中的元素加入结果列表中return;}// 遍历字符串 s从起始位置开始for (int i startIndex; i s.length(); i) {// 如果是回文子串则记录到双端队列中if (isPalindrome(s, startIndex, i)) {String str s.substring(startIndex, i 1); // 截取回文子串deque.addLast(str); // 将回文子串加入双端队列的末尾} else {continue; // 如果不是回文子串则跳过}// 递归调用回溯函数起始位置后移继续搜索下一个回文子串backTracking(s, i 1);deque.removeLast(); // 回溯移除最后一个元素尝试其他分割方案}}// 判断字符串是否是回文串private boolean isPalindrome(String s, int startIndex, int end) {// 从两端向中间比较字符是否相等直到指针相遇for (int i startIndex, j end; i j; i, j--) {if (s.charAt(i) ! s.charAt(j)) {return false; // 如果发现字符不相等则不是回文串}}return true; // 如果全部字符相等则是回文串}
}总结还是回溯模板用得不太熟练。 93.复原IP地址
93. 复原 IP 地址 - 力扣LeetCode
代码随想录 (programmercarl.com)
回溯算法如何分割字符串并判断是合法IP| LeetCode93.复原IP地址_哔哩哔哩_bilibili 有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 . 分隔。 例如0.1.2.201 和 192.168.1.1 是 有效 IP 地址但是 0.011.255.245、192.168.1.312 和 192.1681.1 是 无效 IP 地址。 给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 . 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。 示例 1 输入s 25525511135
输出[255.255.11.135,255.255.111.35]示例 2 输入s 0000
输出[0.0.0.0]示例 3 输入s 101023
输出[1.0.10.23,1.0.102.3,10.1.0.23,10.10.2.3,101.0.2.3]提示 1 s.length 20s 仅由数字组成 这个题和上一个又有了区别这题用来切割的符号一定是3个还要保证切割后每个区间的数值为小于255的数。一开始的想法是先判断整体数值的个数如果是12位呢就刚好从第3个数值开始切.....后来想到这样的话if嵌套就太多了。去看了卡哥题解卡哥还是从第一位后面开始切的。 回溯三部曲
1、确定参数 同样用startIndex记录切割的起始位置还需要一个pointNum来记录逗点的数量因为一定只能用3个逗点切割多一个少一个都不行。
private void backTrack(String s, int startIndex, int pointNum) {}
2、确定终止条件pointNum3的时候终止遍历然后查看切割后的子串是否符合要求符合则加入最终结果集 if (pointNum 3) { // 如果逗点数量为3说明分割结束if (isValid(s, startIndex, s.length() - 1)) { // 判断第四段子字符串是否合法result.add(s); // 如果合法将该字符串加入结果列表}return;
3、单层搜索的逻辑[startIndex,i]区间是切割的子串判断子串是否合法合法就在后面加上逗号表示正式切割不符合就结束本层循环。
然后就是递归和回溯的过程
递归调用时下一层递归的startIndex要从i2开始因为需要在字符串中加入了分隔符.同时记录分割符的数量pointNum 要 1。
回溯的时候就将刚刚加入的分隔符. 删掉就可以了pointNum也要-1。
代码如下 for (int i startIndex; i s.length(); i) {if (isValid(s, startIndex, i)) { // 如果当前子串合法s s.substring(0, i 1) . s.substring(i 1); // 在字符串后面插入一个逗点pointNum; // 逗点数量加1backTrack(s, i 2, pointNum); // 递归调用插入逗点之后下一个子串的起始位置为i2pointNum--; // 回溯恢复逗点数量s s.substring(0, i 1) s.substring(i 2); // 回溯删除插入的逗点} else {break;}
最后根据题意判断一下子串是否合法 // 判断子串是否是合法的IPv4地址private boolean isValid(String s, int start, int end) {if (start end) {return false;}if (s.charAt(start) 0 start ! end) { // 0开头的数字不合法return false;}int num 0;for (int i start; i end; i) {if (s.charAt(i) 9 || s.charAt(i) 0) { // 非数字字符不合法return false;}num num * 10 (s.charAt(i) - 0);if (num 255) { // 如果大于255不合法return false;}}return true;
综合代码
class Solution {ListString result new ArrayList();public ListString restoreIpAddresses(String s) {if (s.length() 12) return result; // 剪枝如果字符串长度大于12直接返回结果backTrack(s, 0, 0); // 调用回溯函数开始搜索分割方案return result;}// 回溯函数private void backTrack(String s, int startIndex, int pointNum) {if (pointNum 3) { // 如果逗点数量为3说明分割结束if (isValid(s, startIndex, s.length() - 1)) { // 判断第四段子字符串是否合法result.add(s); // 如果合法将该字符串加入结果列表}return;}for (int i startIndex; i s.length(); i) {if (isValid(s, startIndex, i)) { // 如果当前子串合法s s.substring(0, i 1) . s.substring(i 1); // 在字符串后面插入一个逗点pointNum; // 逗点数量加1backTrack(s, i 2, pointNum); // 递归调用插入逗点之后下一个子串的起始位置为i2pointNum--; // 回溯恢复逗点数量s s.substring(0, i 1) s.substring(i 2); // 回溯删除插入的逗点} else {break;}}}// 判断子串是否是合法的IPv4地址private boolean isValid(String s, int start, int end) {if (start end) {return false;}if (s.charAt(start) 0 start ! end) { // 0开头的数字不合法return false;}int num 0;for (int i start; i end; i) {if (s.charAt(i) 9 || s.charAt(i) 0) { // 非数字字符不合法return false;}num num * 10 (s.charAt(i) - 0);if (num 255) { // 如果大于255不合法return false;}}return true;}
}78.子集 90. 子集 II - 力扣LeetCode 代码随想录 (programmercarl.com) 回溯算法解决子集问题如何去重| LeetCode90.子集II_哔哩哔哩_bilibili 给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的 子集幂集。 解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列 示例 1 输入nums [1,2,2]
输出[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2 输入nums [0]
输出[[],[0]]提示 1 nums.length 10-10 nums[i] 10 这题一上来自己画树形结构不知道怎么画。看了卡哥题解其实还是一样的 回溯三部曲 1、确定参数startIndex确定开始选取子集得位置
ListListInteger result new ArrayList(); // 存放符合条件结果的集合
LinkedListInteger path new LinkedList(); // 用来存放符合条件结果
private void subsetsHelper(int[] nums, int startIndex) {} 2、确定终止条件剩余集合为空的时候就是叶子节点。什么时候剩余集合为空呢startIndex大于数组长度时就终止 if (startIndex nums.length) { // 如果起始位置超出数组范围直接返回结束递归return;}
3、确定单层搜素的逻辑 太好了这题不用剪枝把所有节点都放到结果集里 for (int i startIndex; i nums.length; i) { // 遍历数组从当前起始位置开始path.add(nums[i]); // 将当前元素加入当前路径子集中subsetsHelper(nums, i 1); // 递归调用继续生成子集起始位置移动到下一个位置path.removeLast(); // 回溯将最后加入的元素移除继续尝试其他可能的子集组合}
综合代码:
class Solution {ListListInteger result new ArrayList(); // 存放符合条件结果的集合LinkedListInteger path new LinkedList(); // 用来存放符合条件结果public ListListInteger subsets(int[] nums) {subsetsHelper(nums, 0); // 调用辅助函数开始生成子集return result; // 返回生成的所有子集}// 辅助函数用于生成所有子集private void subsetsHelper(int[] nums, int startIndex) {result.add(new ArrayList(path)); // 将当前路径上的元素列表加入结果集合相当于将当前子集记录下来if (startIndex nums.length) { // 如果起始位置超出数组范围直接返回结束递归return;}for (int i startIndex; i nums.length; i) { // 遍历数组从当前起始位置开始path.add(nums[i]); // 将当前元素加入当前路径子集中subsetsHelper(nums, i 1); // 递归调用继续生成子集起始位置移动到下一个位置path.removeLast(); // 回溯将最后加入的元素移除继续尝试其他可能的子集组合}}
}牢记回溯模板
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}总结这题单层搜索的逻辑并不是太明确需要根据代码画图再理解一下。
