热度网络网站建设,上海快速建站平台,沈阳做网站哪个好,品牌建设实施方案1.分割回文串题目链接思路#xff1a;回溯算法的组合方法#xff08;分割问题类似组合问题#xff09;。流程图#xff1a;红色竖杠就是startIndex。 for循环是横向走#xff0c;递归是纵向走。回溯三部曲#xff1a;递归函数参数#xff1a;字符串s和startIndex#…1.分割回文串题目链接思路回溯算法的组合方法分割问题类似组合问题。流程图红色竖杠就是startIndex。 for循环是横向走递归是纵向走。回溯三部曲递归函数参数字符串s和startIndex因为是在同一个集合中进行分割或组合就需要startIndex递归函数终止条件只要切割线切到了字符串最后面就终止然后add到result数组中这里默认已经判断回文了单层搜索的逻辑在for (int i startIndex; i s.size(); i)循环中我们定义了起始位置startIndex那么 [startIndex, i] 就是要截取的子串。解法class Solution {ListListString res new ArrayList();LinkedListString path new LinkedList();public ListListString partition(String s) {back(s, 0);return res;}// 递归函数参数private void back(String s, int startIndex) {// 终止条件if (startIndex s.length()){res.add(new ArrayList(path));return;}for (int i startIndex; i s.length(); i){// 如果是回文子串就path.addif (isPalindrome(s, startIndex, i)){path.add(s.substring(startIndex, i 1));}elsecontinue;back(s, i 1);path.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;}
}2.子集题目链接思路这个题是典型的组合问题。子集是收集树形结构中树的所有节点的结果。而组合问题、分割问题是收集树形结构中叶子节点的结果注意for循环里每次都要inums.length。class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger subsets(int[] nums) {back(nums, 0);return res;}private void back(int[] nums, int startIndex) {res.add(new ArrayList(path));for (int i startIndex; i nums.length; i){path.add(nums[i]);back(nums, i 1);path.removeLast();}}
}
