DAY27| 39. 组合总和 ,40.组合总和II ,131.分割回文串

2024-04-15 23:36

本文主要是介绍DAY27| 39. 组合总和 ,40.组合总和II ,131.分割回文串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 39.组合总和
    • 40.组合总和II
    • 131.分割回文串

39.组合总和

文字讲解:组合总和

视频讲解:组合总和

状态: 此题ok

思路:

代码:

class Solution {int sum;public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> tempList = new LinkedList<>();backTracking(result, tempList, candidates, 0, target);return result;}public void backTracking(List<List<Integer>> result, LinkedList<Integer> tempList, int[] candidates, int startIndex, int target) {if (!tempList.isEmpty()&&sum>target) {return;}if (!tempList.isEmpty() && sum==target) { //收集List<Integer> resultParam = new ArrayList<>(tempList);result.add(resultParam);return;}for (int i = startIndex; i < candidates.length; i++) {tempList.offer(candidates[i]);sum+=candidates[i];backTracking(result, tempList, candidates, i, target);tempList.pollLast();sum-=candidates[i];}}
}

40.组合总和II

文字讲解:组合总和II

视频讲解:组合总和II

状态:这题一开始想先排序后去重,再做回溯;想岔批了,应该要保证前后处理相同元素的时候,要进行跳过来进行去重;

思路:

1、这一题,注意枝剪操作,即sum + candidates[i] <= target;不然提交leetcode会超时;

代码:

class Solution {int sum;public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> tempList = new LinkedList<>();Arrays.sort(candidates);//完成去重backTracking(result, tempList, candidates, 0, target);return result;}public void backTracking(List<List<Integer>> result, LinkedList<Integer> tempList, int[] candidates, int startIndex, int target) {if (!tempList.isEmpty()&&sum==target) {List<Integer> resultParam = new ArrayList<>(tempList);result.add(resultParam);return;}for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {if (i>startIndex && candidates[i]==candidates[i-1]) {continue;}tempList.offer(candidates[i]);sum+=candidates[i];backTracking(result, tempList, candidates, i+1, target);tempList.pollLast();sum-=candidates[i];}}
}

131.分割回文串

文字讲解:分割回文串

视频讲解:分割回文串

状态:这题细细一想,和前两题也是类似换汤不换药,看来还是对回溯-排列问题理解不够透彻;

思路:

代码:

class Solution {List<List<String>> result = new ArrayList<>();LinkedList<String> tempList = new LinkedList<>();public List<List<String>> partition(String s) {backTracking(s, 0);return result;}public void backTracking(String s, int startIndex) {if (startIndex>=s.length()) {List<String> resultParam = new ArrayList<>(tempList);result.add(resultParam);return;}for (int i = startIndex; i < s.length(); i++) {if(isPalindrome(s, startIndex, i)) {tempList.offer(s.substring(startIndex, i+1));} else {continue;}backTracking(s, i+1);tempList.pollLast();}}public boolean isPalindrome(String s, int start, int end) {while (start<=end) {if (s.charAt(start) == s.charAt(end)) {start++;end--;} else {return false;}}return true;}
}

这篇关于DAY27| 39. 组合总和 ,40.组合总和II ,131.分割回文串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907237

相关文章

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

SAM2POINT:以zero-shot且快速的方式将任何 3D 视频分割为视频

摘要 我们介绍 SAM2POINT,这是一种采用 Segment Anything Model 2 (SAM 2) 进行零样本和快速 3D 分割的初步探索。 SAM2POINT 将任何 3D 数据解释为一系列多向视频,并利用 SAM 2 进行 3D 空间分割,无需进一步训练或 2D-3D 投影。 我们的框架支持各种提示类型,包括 3D 点、框和掩模,并且可以泛化到不同的场景,例如 3D 对象、室

Go组合

摘要 golang并非完全面向对象的程序语言,为了实现面向对象的继承这一神奇的功能,golang允许struct间使用匿名引入的方式实现对象属性方法的组合 组合使用注意项 使用匿名引入的方式来组合其他struct 默认优先调用外层方法 可以指定匿名struct以调用内层方法 代码 package mainimport ("fmt")type People struct{}type Pe

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入:nums = [1,2,1,1,3],

代码训练营 Day26 | 47.排序II | 51. N-皇后 |

47.排序II 1.跟46题一样只不过加一个树层去重 class Solution(object):def backtracking(self,nums,path,result,used):# recursion stopif len(path) == len(nums):# collect our setresult.append(path[:])return for i in range(