代码随想录算法训练营第二十二天 | leetcode：组合总和,组合总和II,分割回文串
0 / 0 / 创建于 1年前
_zzh 的个人博客
39. 组合总和#
注意的地方#
本题和 77. 组合，216. 组合总和 III 的区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。
解题方法#
- 与 77. 组合，216. 组合总和 III 不同，本题元素可以无限重复使用。所以递归时 startIndex 不需要 + 1
- 剪枝操作，在给 candidates 排序后，需要判断当前 path 下元素相加与当前循环元素 $candidates [$i] 相加小于等于 target 再进行下一次循环。即：array_sum ($this->path) + $candidates [$i] <= $target
复杂度#
时间复杂度
O(n * 2^n)
空间复杂度
O(target)
code#
class Solution {
private $res = [];//结果数组
private $path = [];//组合数组
/**
* @param Integer[] $candidates
* @param Integer $target
* @return Integer[][]
*/
function combinationSum($candidates, $target) {
//排序为后面剪枝操作做准备
sort($candidates);
$this->backtracking($candidates, $target, 0);
return $this->res;
}
function backtracking($candidates, $target, $startIndex){
//当组合之和大于target的情况
if(array_sum($this->path) > $target) return;
//当组合之和等于target的情况
if(array_sum($this->path) == $target){
$this->res[] = $this->path;
}
//遍历数值，下标从0开始，所以startindex要从0开始 排序后如果array_sum($this->path) + $candidates[$i] >target 就没必要再循环了
for($i = $startIndex; $i < count($candidates) && array_sum($this->path) + $candidates[$i] <= $target; $i++){
//压入组合数组
$this->path[] = $candidates[$i];
//因为数字可以重复选取，所以startindex不需要+1
$this->backtracking($candidates,$target,$i);
//回溯操作
array_pop($this->path);
}
}
}40. 组合总和 II#
注意的地方#
- candidates 中的每个数字在每个组合中只能使用一次。
- 解集不能包含重复的组合。
- 本题数组 candidates 的元素是有重复的。
解题方法#
- 树枝（纵向）去重逻辑：使用 used 数组存储当前纵向递归已使用元素。保证每次纵向递归的元素不重复。并且对已使用元素数组也采用回溯操作，使每次纵向递归后，进入下一次横向循环时，used 数组因回溯操作，会置空前一次的数据，加入当前横向循环的元素。
- 树层（横向）去重逻辑：对 candidates 排序，使重复的元素相邻。结合树枝去重逻辑，每次纵向递归后，used 因回溯会会置空前一次的数据，加入当前横向循环的元素。，即 used [i - 1] == empty，used [i] != empty。如果此时 candidates [i] == candidates [i - 1]，就代表当前要进行的纵向递归与前一次重复，所以需要 continue 跳过。
- used [i - 1] == true，说明同一树枝 candidates [i - 1] 使用过
- used [i - 1] == false，说明同一树层 candidates [i - 1] 使用过
复杂度#
时间复杂度
O(n * 2^n)
空间复杂度
O(n)
code#
class Solution {
private $res = [];//结果数组
private $path = [];//组合数组
private $used = [];//已使用数组
/**
* @param Integer[] $candidates
* @param Integer $target
* @return Integer[][]
*/
function combinationSum2($candidates, $target) {
//return [[array_sum($candidates)]];
if(array_sum($candidates) < $target) return $this->res;
if(array_sum($candidates) == $target) return [$candidates];
sort($candidates);
$this->backtracking($candidates, $target, 0);
return $this->res;
}
function backtracking($candidates, $target, $startIndex){
print_r($this->used);
//当组合之和等于target的情况
if(array_sum($this->path) == $target){
$this->res[] = $this->path;
return;
}
//遍历数值，下标从0开始，所以startindex要从0开始
for($i = $startIndex; $i < count($candidates) && array_sum($this->path) + $candidates[$i] <= $target; $i++){
/*
此处去重逻辑：
used在回溯的作用下，在每次纵向递归完进行下一次外层for循环时，会被回溯清空前一次used数据，
此时如果$candidates[$i] == $candidates[$i - 1]，证明当前要进行的纵向递归与前一次重复，所以需要continue跳过。
*/
if($i > 0 && empty($this->used[$i-1]) && $candidates[$i] == $candidates[$i - 1] ){
continue;
}
//压入组合数组
$this->used[$i] = $candidates[$i];
$this->path[] = $candidates[$i];
$this->backtracking($candidates,$target,$i+1);
//回溯操作
array_pop($this->used);
array_pop($this->path);
}
}
}131. 分割回文串#
注意的地方#
- 遍历过程中如何切割目标字符串。
- 如何判断是否回文串。
解题方法#
- 分析一下切割，其实切割问题类似组合问题。
例如对于字符串 abcdef：
组合问题：选取一个 a 之后，在 bcdef 中再去选取第二个，选取 b 之后在 cdef 中再选取第三个…..。
切割问题：切割一个 a 之后，在 bcdef 中再去切割第二段，切割 b 之后在 cdef 中再切割第三段…..。
切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
切割的起点为 startIndex,> 切割的起点为 startIndex, 切割的终点为循环中的 i。- 判断是否回文串，可以使用双指针，一头一尾分别判断是否相等，如果不相等 return false。最后 return true 即可。
复杂度#
时间复杂度
O(n * 2^n)
空间复杂度
O(n^2)
code#
class Solution {
private $res = [];
private $path = [];
/**
* @param String $s
* @return String[][]
*/
function partition($s) {
$this->backtracking($s,0);
return $this->res;
}
function backtracking($s, $startIndex){
if($startIndex >= strlen($s)){
$this->res[] = $this->path;
return;
}
for($i = $startIndex; $i < strlen($s); $i++){
//判断切割的字符是否是回文串
if(!$this->isPalindrome($s, $startIndex, $i)) {
continue;
}else{
//获得切割的字符串
$str = substr($s, $startIndex, $i - $startIndex + 1);
//print_r("start:".$startIndex." end:".$i. " str:".$str."\n");
$this->path[] = $str;
}
$this->backtracking($s, $i+1);
array_pop($this->path);
}
}
function isPalindrome($str, $start, $end){
for($s = $start, $e = $end; $s < $e; $s++,$e--){
if($str[$s] != $str[$e]){
return false;
}
}
return true;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：