1. 39组合总和
难点是怎么控制无限制重复选取还不和前面选过的重复的.自己写出来了.但是还是有小错误,for循环的时候把candidate[i]写成了candidate[index]
2. 40.组合总和II
本题第一次涉及到组合的去重问题.给你的集合有重复元素,但是结果不允许有.
看到这先去扩充了下js有什么自带的方法:
- 数组:
arr.include()-
arr.indexOf() !==-1
两个时间复杂度都是O(n)
2.map
has:map.has()平均时间复杂度是O(1),最坏才是O(n)
3.Set
是的,前面记错了,js里有set,let set = new Set()
也是用has时间复杂度同map
我看到题的思路是先把数组存到set里?
就算用这个思路我也出了问题,set不是基于索引的集合,而是基于值的集合.没法用索引,所以不能用Set[0]下标找到东西,只能得到undifined,要想用索引找只能先把set转回array Array.from(setname)
写完了发现不对,题目给的集合有值相同的元素,但是他们算是不同的元素,只是恰巧值相同,不能直接合并成set.
而且如果一个值出现多次,它当然可以算多个元素,但是解集不能重复.
比如[2,2,1,2]三个2是不同元素,如果target是5,应该是三个[1,2,2].但是题目说了解集不能包含重复组合,所以三个就是一个.
卡哥思路:
用[1,1,2]target3举例
放一个辅助数组,大小和candidate相同,用过的元素下标就赋成1.
这种情况下,深度方向是不需要去重的,两个1是不同的元素有相同值而已,并没有重复取元素.
但是宽度方向,假设集合排好了序,那第一个1向后取,第二个1也向后取,第一个1向后的部分必然包括了第二个1的部分,导致重复.
从这道题里也学了个js的数组排序的方法:
let sortNums = candidates.sort((a,b)=>a-b);
a如果大于b,a就会放在后面
但是该方法会修改原数组,返回修改后的数组,所以如果不想原数组,要这样:slice()是对数组的浅拷贝
let sortNums = candidates.slice().sort((a,b)=>a-b)
这里也是第一次用到continue,因为[1,1,2]如果碰到第二个1就return的话,结果是不全的,要继续for循环才对,因为后面还有2
- 本题在宽度上判断是否重复用的是
used[i-1] ===0.因为如果是宽度的情况,比如取了1,1,那used就是[1,1,0]虽然此时两个元素值相同,但是第一个1的used是1,表明它在树枝方向上在操作,而不是树层方向,前面也分析了,树枝方向也就是深度方向的时候我们不需要判断重复.等回溯到树层时,第一个used被重置成0,这时候就表明这是宽度方向,要检查重复.
3. 131.分割回文串 Palindrome Partitioning
- 什么是回文串?
正着反着读都一样的字符串 - backtracking的返回条件是到最后一位才算切完,才把结果全push进去.
当前还是搞不太懂这个path.push(s.slice(startIndex,i+1)),卡哥说的是startIndex就是切割线.
