?浮躁,是互联网时代的特点 ?
大家好,我是「柒八九」。
今天,我们继续「前端面试」的知识点。我们来谈谈关于「JS算法」的相关知识点。
该系列的文章,大部分都是前面文章的知识点汇总,如果想具体了解相关内容,请移步相关系列,进行探讨。
如果,想了解该系列的文章,可以参考我们已经发布的文章。如下是往期文章。
好了,天不早了,干点正事哇。
题目描述:
?给定两个「整数」 a 和 b ,求它们的除法的商 a/b ,要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' > 提示:
[?231, 231?1]
示例:输入: -15和2 输出: -7?
[?231, 231?1]
,所以,我们可以定义边界值 MIN = -Math.pow(2, 31)
/ MAX = Math.pow(2, 31) - 1
sign =(a>0)^(b>0)
位运算的异或运算(^):在两个二进制位不同时返回1,相同时返回0 ,这样有一个好处,就是其实我们不关心,到底是哪个为正哪个为负。Math.abs(x)将x变更成正整数
count
) ==> 而最后的次数,就是所求的商function divide(a, b) {
const MAX = Math.pow(2, 31) - 1, //最大值
MIN = -Math.pow(2, 31) //最小值
if (a == MIN && b == -1) return MAX; // 处理边界情况
const sign = (a > 0) ^ (b > 0); // 处理商的正负问题
a = Math.abs(a), b = Math.abs(b) // 变成正整数之间的相减
let count = 0
while(a >= b) {
a -= b
count++
}
// sign为正,说明,除数和被除数之间 有一个为负数
return sign ? -count : count;
};
题目描述:
?给定两个 01 字符串 a 和 b ,请计算它们的和,并以二进制字符串的形式输出。 输入为 非空 字符串且只包含数字 1 和 0 示例:输入 a = "11", b = "10" 输出: "101" ?
参考十进制加法来完成二进制加法。在进行十进制加法操作时候,总是将两个数的「右端对齐」,然后从它们的个位开始「从右向左相加同一位置的两个数」。如果前一位置有进位,还要加上进位。
从上面分析可知,有几个关键点
i
/j
)carry
)index
处字符的ASCII
码 str.charAt(index)
(digitA + digitB + carry)>=2
carry是上一位的残留产物 function addBinary(a, b) {
let result = ''; // 用于存储结果
let i = a.length - 1; // 指针i
let j = b.length -1; // 指针j
let carry = 0; // 用于存储进位
while(i>=0 || j>=0){ //只有有数据,就进行数据操作
// 指定位置的数字(二进制0/1)
// 判断位置,以免位置出错 i >=0
let digitA = i >=0 ? a.charAt(i--) -'0':0;
// 指定位置的数字(二进制0/1)
// 判断位置,以免位置出错 j >=0
let digitB = j >=0 ? b.charAt(j--) -'0':0;
// 求和处理
let sum = digitA + digitB + carry;
// 处理进位
carry = sum >=2 ? 1 :0;
// sum可能超过最大当前进度的最大值,
//例如: 十进制的 7+8 = 15 ==> 指定的个位存 5 (15-10)
sum = sum >=2 ? sum - 2:sum;
result = sum + result;
}
// 最高位可能会产生进位
if(carry ==1){
result = '1' + result;
}
return result
};
function Nsum(a,b,n){
let result = '';
let i = a.length - 1;
let j = b.length -1;
let carry = 0;
while(i>=0 || j>=0){
let digitA = i >=0 ? a.charAt(i--) -'0':0;
let digitB = j >=0 ? b.charAt(j--) -'0':0;
let sum = digitA + digitB + carry;
carry = sum >=n ? 1 :0;
sum = sum >=n ? sum - n:sum;
result = sum + result;
}
if(carry ==1){
result = '1' + result;
}
return result;
}
题目描述:
?给定一个「非负整数 n」 ,请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数,并输出一个数组。 输入: n = 2 输出: [0,1,1] 解释: 0 --> 0 1 --> 1 2 --> 10 ?
我们可以为题目做一个「转化」,只要我们能求出一个「整数」i
的二进制形式中1的个数,这个问题就迎刃而解。 因为,最后的要的数组,无非就是将某一范围内数据的二进制中1的个数做一个统计。
我们能从题目中挖掘的主要信息有:
?利用
i&(i-1)
将整数i的「最右边」的1变成0 ?
整数i
减去1,那么它最右边的1变成了0。例如:二进制1100
,它减少1的结果是1011
。而1100 & 1011 = 1000
。
所以我们可以利用这个特性,对0~n
所有的数进行i&(i-1)
处理。也就是需要两层循环,第一层循环是遍历「整体数据」,第二层循环是针对特定数据i
。
function countBits(n){
// 构建一个长度为n+1 (0~n),每项都是0的数组
let result = new Array(n+1).fill(0);
// 外层循环:处理整体数据
for(let i=0;i<=n;i++){
let j =i;
// 内层循环:对特定数据进行j&(j-1)处理,直到 j里面不含有1,也就是为0
while(j!=0){
result[i]++;
j = j & (j-1)
}
}
return result;
}
整数i的二进制形式中1的个数比i&(i-1)
的二进制形式中1的个数多1。并且,原来的代码中我们是从i=0
开始整体遍历的,然后,根据常识可知,i=0
中1的个数为0。根据这些条件,我们可以对上述代码,做一个优化处理,也就是合理利用已经计算出的结果。
function countBits(n){
// 构建一个长度为n+1 (0~n),每项都是0的数组
let result = new Array(n+1).fill(0);
// 从i=1开始遍历
for(let i=1;i<=n;i++){
result[i] = result[i&(i-1)]+1
}
return result;
}
这样,少了一层遍历,然后对应的时间复杂度也减少了。
题目描述:
?一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 「三次」 。找出并返回那个只出现了一次的元素。 提示:
-231 <= nums[i] <= 231 - 1
输入:nums = [2,2,3,2] 输出:3 ?
从提示,我们可以得知,「整数是由32个0和1组成的」。我们可以将数组中的所有数字的「同一位置相加」。
i>>1
通过右移动一位的方式,来快速获取 i/2,其实在位运算中,还可以i>>n
。 也就是将当前位的数右移N位。
因为,我们要求数组中所有数字「指定位置」(i
)的二进制位。所以,(num>>(31-i))&1
就是某个数字在i
的位数。num<<1
将当前num向右扩大一倍,从二进制角度看,就是将最右边位置补0
例子: 2的二进制位10
2<<1 == 4
(二进制位100) 可以通过(4).toSting(2)
进行验证function singleNumber(nums) {
// 构建一个用于存储数组所有数字位数之和的数组
let bitSums = new Array(32).fill(0);
for(let num of nums){
for(let i=0;i<32;i++){
// 求num在i位置的位数,并将其与指定位置的位数相加
bitSums[i] +=(num>>(31-i)) &1;
}
}
let result =0;
for(let i=0;i<32;i++){
//从最地位(0)位开始遍历
result = (result<<1) + bitSums[i]%3;
}
return result;
};
代码中(result<<1) + bitSums[i]%3
其实也承载了两种含义
bitSums[i]%3 ==0
,也就是能「被3整除」,只出现一次的数字在该位置(i
)没出现过bitSums[i]%3 ==1
,也就是能「被3除余1」,只出现一次的数字在该位置(i
)出现过题目描述:
?一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 输入: [2,2,1]输出: 1 ?
我们将上面的代码,做一个简单的修改。
function singleNumber(nums) {
// 构建一个用于存储数组所有数字位数之和的数组
let bitSums = new Array(32).fill(0);
for(let num of nums){
for(let i=0;i<32;i++){
// 求num在i位置的位数,并将其与指定位置的位数相加
bitSums[i] +=(num>>(31-i)) &1;
}
}
let result =0;
for(let i=0;i<32;i++){
//从最地位(0)位开始遍历
result = (result<<1) + bitSums[i]%2;
}
return result;
};
通过对比发现,其实我们就更改了一处地方将(result<<1) + bitSums[i]%3
更换为了(result<<1) + bitSums[i]%2
仅此而已。
其实,针对该题还有一个更简单的处理方式。是利用了位运算中异或运算(^):两个二进制位不同时返回1,相同时返回0
function singleNumber(nums) {
let result = 0;
for(let i of nums){
result ^= i;
}
return result
};
result^=i
如果在位置i上存在两个相同的数字,通过异或处理,「直接清零」。类似于消消乐,他们两个互相抵消了。那么剩下的就是那个只出现一次的数字的位数了。
?由于文章篇幅有限,如果想了解相关内容,请移步到指定文章中。 ?
JS 只支持一维数组,并不支持矩阵(多维数组) 在JS中,我们可以通过很多方式来构建一维数组。
let array = Array('柒','八','九'); // new Array / []等
而构建多维数组,就需要借助函数来构建。
const matrix= (x,y) =>
new Array(x).fill(0)
.map(
()=>new Array(y).fill(0)
)
通过matrix
我们构建了一个,x
行,y
列 且数组中值都为0
的二维数组(矩阵)。
「双指针」是一种常见的解题思路,使用两个「相反」方向或者「相同」方向的指针扫描数组从而达到解题目的。
有两种解题思路: 「反向双指针」/「同向双指针」
sum
)或者「乘积」(mult
)。题目描述:
?输入一个「递增排序」的数组和一个值
target
,在数组中找出两个和为target
的数字并返回它们的下标 提示: 数组中有且只有一对符合要求 同时一个数字不能使用两次 示例:输入数组: [1,2,4,6,10],k的值为8 输出[1,3] ?
left
指向首元素,right
指向尾元素sum
VS target
移动对应的指针function twoSum4SortedArray(nums,target){
let left=0,right= nums.length-1; // 初始化指针left,right
while(left<right && nums[left] + nums[right] != target){
if(nums[left] + nums[right]<target){
left++;
}else{
right--;
}
}
return [left,right]
}
注意:如果大家在刷leetcode
等算法网站中,肯定会见过关于数组的两数之和的题。但是,这里的题干和常规的两数之和还有点区别。首先,该题干中,天生有序,所以,可以「套用」反向双指针的套路。
为了做区分,我们将twoSum
的解题代码也直接写出来。它的解题思路是,利用了Map
对数据和下标做了转换。
function twoSum(nums,target){
let valueToIndex = new Map(); // 用于,存储[nums[i],i]之间的关系
for(let i = 0;i<nums.length;i++){
let expectValue = target - nums[i];
// 先从map中找,是否存在指定值
if(valueToIndex.has(expectValue)){
// 如果有,直接返回与值相对于的下标
return [valueToIndex.get(expectValue),i]
}
// 存储[nums[i],i]之间的关系
valueToIndex.set(nums[i],i);
}
return null;
}
题目描述:
?输入一个数组,找出数组中所有和为
target
的3个数字的三元组 提示: 返回值不得包含「重复」的三元组 示例:输入数组:[-1,0,1,2,-1,-4]
,target的值为0 输出[[-1,0,1],[-1,-1,2]]
?
left
指向固定元素的「后一个元素」,right
指向「尾元素」sum
VS target
移动对应的指针sort
但是需要指定排序函数nums.sort((a,b)=>a-b)
function threeSum(nums,target){
let result = [];
if(nums.length<3) return [];
// 人工对数据进行排序处理
nums.sort((a,b)=>a-b);
let i =0;
while(i<nums.length-2){
twoSum(nums,i,target,result);
let temp = nums[i];
// 剔除,重复元祖中第一个数值
while(i<nums.length && nums[i]==temp) i++;
}
return result;
}
我们把「排序数组中的两个数字之和」的算法,做了一个改造,因为left
不在从0
开始,所有需要将left
的前一个位置i
传入,right
的逻辑不变,还是「数组尾部」
left = i + 1
right = nums.length - 1
function twoSum(nums,i,target,result){
// 初始化指针left,right
let left = i + 1, right = nums.length -1;
while(left<right){
// 求和
let sum = nums[i] + nums[left] + nums[right];
// 指针移动过程 (if/else)
if(sum === target){
result.push([nums[i],num[left],nums[right]]);
let temp = nums[left];
// 剔除,重复元祖第二个数值
while(nums[left] === temp && left < right) left++;
}else if(sum < 0) {
left++;
}else{
right--;
}
}
}
我们来对比下,两个twoSum
的共同和不同点。
它们的核心框架是相似的。都是利用「方向双指针」进行sum
与target
之间的数据对比。
题目描述:
?输入一个「正整数」组成的数组和一个正整数
target
,找出数组中「和」大于或等于target
的「连续子数组」的「最短」长度 提示: 如果不存在满足条件的子数组,返回0 示例:输入数组:[5,1,4,3]
,target
的值为7 输出2
(和大于或等于7的最短连续子数组是[4,3]
) ?
left
指向子数组的第一个数字right
指向子数组的最后一个数字left
/right
两指针之间的所有数字的组成left
永远不会走到指针right
的右边」left
/right
「初始化」的时候都指向数组的第一个元素,套用上面的公式sum
>= target
: 右移left
(left++
),删除「子数组最左边」的数字,子数组长度-1sum
< target
: 右移 right
(right++
),在「子数组右边」增加新的数字,子数组长度+1sum
>=target
时,为了求最短子数组,我们需要移动left
进行子数组的「瘦身」处理 (left++
)function minSubArrayLen(nums,target){
let left=0,right=0; // 同向双指针,默认值
let sum=0;
// 最小的长度
let minLength = Number.MAX_SAFE_INTEGER;
for(right=0;right<nums.length;right++){
sum+=nums[right];
while(left<=right && sum>=target){
// 更新最小长度
minLength = Math.min(minLength,right - left + 1);
// 子数组**瘦身**处理
sum-= nums[left++]
}
}
return minLength == Number.MAX_SAFE_INTEGER?0:minLength;
}
有几点需要唠叨一下:
Number.MAX_SAFE_INTEGER
) 如果已知最大范围,我们也可以给一个定值。例如,100/1000
等;那最大值,就是用0
等替换right
先动,left
视情况而动题目描述:
?输入一个「正整数」组成的数组和一个正整数
target
,找出数组中「乘积」小于target
的「连续子数组」的所有组合的个数 示例:输入数组:[10,5,2,6]
,target
的值为100
输出8
([10],[5],[2],[6],[10,5],[5,2],[2,6],[5,2,6]) ?
left
永远不会走到指针right
的右边」 (left<=right
)mult
>= target
: 右移left
(left++
),删除「子数组最左边」的数字,子数组长度-1(mult变小)mult
< target
: 右移 right
(right++
),在「子数组右边」增加新的数字,子数组长度+1 (mult变大)left
到某个位置时子数组的「乘积」小于target
,就不需要移动left
。只要right
「保持不动」,[left
,right
]区间的「所有」的子数组的乘积都一定小于target
。 也就说说,两个指针之间有多少个数字,就有多少个满足条件的子数组function numSubarrayMultLessThanTarget(nums,target){
let mult = 1;
let left =0,right=0; // 初始化指针
let count = 0;
for(right=0;right<nums.length;right++){
mult *=nums[right];
// 指针left永远不会走到指针right的右边
while(left<=right && mult >= target){
mult /=nums[left++];
}
count += right>=left?right - left +1 :0;
}
return count;
}
虽然,在求正整数数组「和」或者「乘积」之间,有些具体逻辑不大相同,但是总体的思路都是利用「同向双指针」对数据进行处理。
使用「双指针解决子数组之和」有一个前提条件:数组中的「所有」数字都是「正数」。所有,双指针的在解决非正数的数组时,是不满足条件的。
针对非正数的数组,我们换一个思路来求子数组之和。
假设整个数组的长度为n
,它的某个「子数组」的第一个数字的下标是i
;最后一个数字的下标是j
。我们做一个「预处理」,计算从数组下标为0的数字开始到以「每个数字」为结尾的「子数组之和」。预处理只需要从头到尾扫描一次,就能求出从下标0开始到下标0结束的子数组之和 「S0」 ,以此类推,S1,S2,Sn-1因此,从下标为i
开始到下标为j
结束的子数组的和就是 「Sj-Si-1」
例如:在数组[1,2,3,4,5]
中,从S2的子数组[1,2,3]
之和是6,S4的子数组[1,2,3,4,5]
之和是15,那么从下标3开始到下标4结束的子数组之和[4,5]
之和是9,也就是 S4 - S2 即: 15 - 9 = 6
题目描述:
?输入一个「整数」组成的数组和一个整数
target
,找出数组中数字之和等于target
的「连续子数组」的个数 示例:输入数组:[1,1,1]
,target
的值为2
输出2
?
i
个数字之和」,并将和「保存」下来i
个数字之和记为x
j
(j<i
) 即,j
在x
前面,且数组的前j
个数字之和为x-target
(「很重要」)j+1
个数字开始到第i
个数字结束的子数组之和为target
target
的子数组的个数。当扫描到数组第i
个数字并求得前i
个数字之和是x
时,需要知道在i
之前存在「多少」个j
并且前j
个数字之和等于x-target
i
,不但要保存前i
个数字之和,还要保存每个和出现的次数Map
(哈希表)的「键」(key)保存前i
个数字之和,「值」(value)保存每个和出现的次数function subarraySum(nums,target){
// 构建哈希表,并初始化[0,1]
let sumToCount = new Map();
sumToCount.set(0,1);
let sum = 0;
let count =0;
for(let num of nums){
sum += num;
// 统计 在当前数值下的 x-target的值
count += sumToCount.get(sum - target) // 前面已经存在
|| 0; // 首次出现
sumToCount.set(
sum,
(sumToCount.get(sum)||0)+1
)
}
return count;
}
题目描述:
?输入一个只包含0和1的数组,求0和1的个数相同的「最长连续子数组」的长度 示例:输入数组:
[0,1,0]
输出2
(两个子数组分别是[0,1]和[1,0]) ?
i
个数字之和」i
个数字之和为m,前j
个数字(j<i
)之和也为m,那么从j+1
到第i个数字的子数组之和为0,长度为i - j
function findMaxLength(nums){
let sumToIndex = new Map();
sumtoIndex.set(0,-1);
let sum = 0;
let maxLength =0;
for(let i=0;i<nums.length;i++){
// 数据转化
sum+=nums[i]==0?-1:1;
if(sumToIndex.has(sum)){
maxLength = Math.max(maxLength,i-sumToIndex.get(sum));
}else{
// 存储关系
sumToIndex.set(sum,i)
}
}
return maxLength;
}
我们可以看到,在「和为target的子数组」和「0和1个数相同的子数组」中,虽然有些细节是不一样的,但是总体框架还是一致的。
i
个数字之和 求出sum
Map
来存储sum
与对应所求的(count/index
)直接的关系题目描述:
?输入一个整数数组,如果一个数字左边的子数组的数字之和等于右边子数组的数字之和,返回该数字的下标 示例:输入数组:
[1,7,3,6,2,9]
输出3
(对应的值为6) ,下标为3的数字(值为6)的左边3个数1,7,3的和与右边两个数字2,9的和相等 ?
i
个数字时i-1
个数字的和i+1
个数字开始累加到最后一个数字的和,这个和等于数组中「所有数字」之和减去从第一个数字累加到第i
个数字的和function pivotIndex(nums){
let total =0;
total =nums.reduce((pre,cur)=>pre+cur);
let sum = 0;
for(let i=0;i<nums.length;i++){
sum+=nums[i];
if(sum - nums[i] == total - sum){
return i
}
}
return -1;
}
sum
套路就那般left
为首right
为尾(求两数之和)i
个数据和)Map(sum,count/index)
来辅助?在JS中,「字符串可以被视为字符数组」 ?
str.charAt(i)
用于获取str
在i
位置的字符在JS中,字符之间是无法之间「相减」
'b' - 'a' // NAN
其实,这里面的深层次的原因是,JS中针对 '-'操作符,没兼容字符。而-
操作符要的预期就是返回数值,因为,字符没被兼容,所以结果返回了一个NAN
。
作为替换方案,str.charAt(i).charCodeAt()
(获取str
在i
位置的字符ASCLL
码值 )就肩负起,字符之间相减的操作
str = 'ba';
str.charAt(1).charCodeAt() - str.charAt(0).charCodeAt()
// 结果为1 b的ascll 为98,a的ascll为97 即:98 -97
「字符串可以被视为字符数组」,那么也可以用「双指针」的技巧来处理字符串的一些问题。
由于在处理字符串时,很多都与「统计字母出现的次数有关」,所以我们可以借用「哈希表」(map)来存储每个元素出现的次数。
?Map 在信息存储方面还是很有用的。在讲「数组」算法中,在非正整数用Si时,就用 Map进行key 和value的信息存储 ?
题目描述:
?输入字符串s1和s2,判断s2中是否包含s1的某个变位词 提示: 如果s2中包含s1的某个变位词,则s1至少有一个变位词是s2的「子字符串」 假设两个字符串中只包含英文小写字母 示例:s1 为“ac”, s2为“dgcaf” ,由于s2包含s1的变位词"ca", 结果为「true」 ?
a
, 下标为1对应字母b
s1
,每扫描到一个字符,就找到它在哈希表中的位置,并把它对应+1
s2
的「子字符串」是否包含s1
的变位词s1
长度为n
s2
中「长度为n
的子字符串」是不是s1
的变位词-1
s1
的变位词function checkInclusion(s1,s2){
let s1l = s1.length,s2l = s2.length;
if(s2l<s1l) return false;
// 构建 字符 => 个数 数组
let counts = new Array(26).fill(0);
// 遍历s1,并对s1中字符进行数据收集 (++)
// 针对已收集的s1数据信息,与s2进行匹配(--)
for(let i =0;i<s1l;i++){
counts[s1.charAt(i).charCodeAt() - 97]++;
counts[s2.charAt(i).charCodeAt() - 97]--;
}
//判断,是否全为0,如果是,刚才已经满足情况了,直接返回true
if(areaAllZero(counts)) return true;
//从s1l的位置出发,先匹配,后收集(类似同向双指针)
for(let i = s1l;i<s2l;i++){
counts[s2.charAt(i).charCodeAt() - 97]--;
counts[s2.charAt(i - s1l).charCodeAt() -97]++;
if(areaAllZero(counts)) return true;
}
return false
}
辅助函数,用于判断,数值中值是否都为0
function areaAllZero(counts){
for(let count of counts) {
if(count >0) return false
}
return true;
}
在上面的函数中,
i-s1l
的位置i
相当于「第二个指针」,指向「子字符串」的最后一个字符s1
的长度题目描述:
?输入字符串s1和s2,找出s1的「所有」变位词在s2中的「起始」下标 提示: 假设两个字符串中只包含英文小写字母 示例:s1 为“abc”, s2为“cbadabacg” ,s1的两个变位词"cba"/"bac"是
s2
中的子字符串,输出在s2
中的起始下标为0和5 ?
和找「字符串中的变位词」的思路是一样的
a
, 下标为1对应字母b
s1
,每扫描到一个字符,就找到它在哈希表中的位置,并把它对应+1
s2
的「子字符串」是否包含s1
的变位词s1
长度为n
s2
中「长度为n
的子字符串」是不是s1
的变位词-1
s1
的变位词(进行下标的记录处理)function findAnagrams(s1,s2){
let result = [];
let s1l = s1.length,s2l = s2.length;
if(s2l<s1l) return result;
let counts = new Array(26).fill(0);
for(let i= 0;i<s1l;i++){
counts[s1.charAt(i).charCodeAt() - 97]++;
counts[s2.charAt(i).charCodeAt() - 97]--;
}
if(areaAllZero(counts)) result.push(0);
for(let i= s1l;i<s2l;i++){
counts[s2.charAt(i).charCodeAt()-97]--;
counts[s2.charAt(i-s1l).charCodeAt()-97]++;
// 在满足情况下,对应的开始下标为`i-s1l+1`
if(areaAllZero(counts)) result.push(i - s1l+1);
}
return result
}
辅助函数,用于判断,数值中值是否都为0
function areaAllZero(counts){
for(let count of counts) {
if(count >0) return false
}
return true;
}
针对「字符串中的变位词」还是「字符串中所有变位词」中用到的思路,都是「利用数组来模拟哈希表」(map)然后,针对特定的场景进行数据的处理。然后,针对双指针的定义,在第二个for
循环中,第一个指针为i-s1l
对应的位置,第二个指针,为i
对应的位置,而两者恰好相差(s1l)的长度。
题目描述:
?输入一个字符串,求该字符串中不含重复字符的「最长子字符串」 示例: 输入"babcca",其最长的不含重复字符的子字符串为“abc”,长度为3 ?
new Array(256).fill(0)
function lengthOfLongestSubstring(s){
let sl = s.length;
if(sl==0) return 0;
let counts = new Array(256).fill(0);
let longest = 0;
let j= -1; // 左指针
// i 为右指针
for(let i=0;i<sl;i++){
counts[s.charAt(i).charCodeAt()]++;
while(hasGreaterThan1(counts)){
j++
counts[s.charAt(j).charCodeAt()]--;
}
// 更新最长子串的长度
longest = Math.max(i-j,longest);
}
return longest;
}
辅助函数,用于判断数组中是否有含有大于1的数
function hasGreaterThan1(counts){
for(let count of counts){
if(count>1) return true
}
return false;
}
在上面代码中,其实难点就是双指针的定义和赋值
hasGreaterThan1
为true时,j++
,且counts
指定位置counts[s.charAt(j).charCodeAt()]--
回文是一类特殊的字符串。不管「从前往后」,还是「从后往前」,得到的字符信息都是一样的。
题目描述:
?输入一个字符串,判断它是不是回文 提示: 只考虑字母和数字字符,忽略大小写 示例: 输入字符串“abba”返回true, 输入“abc”返回false ?
function isPalindrome(s){
let left =0,right = s.length -1;
while(left<right){
// 获取指定位置的字符
let cl = s.charAt(left);
let cr = s.charAt(right);
// 跳过非数字和字母的字符 (!isLetterOrDigit(x))
if(!isLetterOrDigit(cl)){
left++;
}else if(!isLetterOrDigit(cr)){
right--;
}else {
// 大小写不敏感
cl = cl.toLocaleLowerCase();
cr = cr.toLocaleLowerCase();
// 不一样,跳出循环
if(cl!=cr) return false
// 指针移动
left++;
right--;
}
}
return true;
}
辅助函数
const isLetterOrDigit = str => /^[A-Za-z0-9]+$/.test(str)
题目描述:
?输入一个字符串,判断「最多」从字符串中删除一个字符能不能得到一个回文字符串 示例: 输入字符串“abca”, 删除字符
b
或者c
能得到一个回文字符串,因此输出true ?
function validPalindrome(s){
let left =0,right = s.length -1;
let middlePosition = s.length>>1;
// 移动指针,并比较字符是否相等
for(;left<middlePosition;left++,right--){
if(s.charAt(left)!=s.charAt(right)) break;
}
// 这里有两类情况
// 1: 字符串本身是回文 (left == middlePosition)
// 2. 需要对字符串进行字符剔除 (isPalindrome)
return left == middlePosition
|| isPalindrome(s,left,right-1)
|| isPalindrome(s,left+1,right)
}
辅助函数,用于判断字符串是否是回文
function isPalindrome(s,left,right){
while(left<right){
if(s.charAt(left)!= s.charAt(right)) break;
left++;
right--;
}
return left>=right;
}
这里有一个比较重要的点,就是「最多」可以删除一个字符。放到代码中其实就是在validPalindrome
中return
那里体现
validPalindrome
中for
循环没阻断,即:left == middlePositon
validPalindrome
中的for
发生了「阻断」(break)isPalindrome(s,left,right-1)
isPalindrome(s,left+1,right)
题目描述:
?输入一个字符串,求字符串中有多少个「回文连续子字符串」? 示例: 输入字符串“abc”有3个回文子字符串,分别是"a"/"b"/"c" ?
function countSubstrings(s){
if(s==null || s.length==0) return 0; //处理边界
let count = 0;
for(let i=0;i<s.length;i++){
// 字符串下标为i。
// 既作为奇数回文的中心
// 又可以和i+1一同作为偶数回文的中心
count+=countPalindrome(s,i,i);
count+=countPalindrome(s,i,i+1);
}
return count;
}
辅助函数,
function countPalindrome(s,left,right){
let count = 0;
while(left>=0&&right<s.length
&& s.charAt(left)==s.charAt(right)){
count++;
left--;
right++;
}
return count;
}
这个题,最主要的就是需要明白:
i
个字符本身可以成为「长度为奇数」的回文字符串的对称中心i
的位置 countPalindrome(s,i,i);
i
个字符和第i+1
个字符可以成为「长度为偶数」的回文字符串的对称中心i
的位置 countPalindrome(s,i,i+1);
counts = new Array(x).fill(0)
s.charAt(i).charCodeAt()
++
或--
i-s1l
,第二指针i
left=0
/right= s.length-1
i
可为奇数中心,i
与i+1
可为偶数中心构造链表节点 单向链表的节点代码
class ListNode {
val: number
next: ListNode | null
constructor(val?: number, next?: ListNode | null) {
this.val = (val===?developer/article/2195744/undefined ? 0 : val)
this.next = (next===?developer/article/2195744/undefined ? null : next)
}
}
其实,针对链表存在一些常规的「工具方法」。一些比较复杂的算法,都是各种工具方法的组合。
而下面的这些方法,是需要「熟记」的。
关键点解释:
perv = null
cur = head
next = cur.next
next= cur.next
)cur.next = prev
)prev= cur
)cur=next
)function reverseList(head){
// 初始化prev/cur指针
let prev = null;
let cur = head;
// 开始遍历链表
while(cur!=null){
// 暂存后继节点
let next = cur.next;
// 修改引用指向
cur.next = prev;
// 暂存当前节点
prev = cur;
// 移动指针
cur = next;
}
return prev;
};
关键点解释:
while(fast && fast.next)
function hasCycle(head){
let fast = head;
let slow = head;
while(fast && fast.next){
fast = fast.next.next;
slow = slow.next;
if(fast == slow) return true;
}
return false;
}
关键点解释:
l1/l2
可能初始为空),采用dumy
节点dumy = new ListNode(0)
node = dumy
l1/l2
相同位置的节点信息while(l1 && l2)
node.next = lx
(x=1/2)lx = lx.next
l1/l2
「溢出」部分的节点信息if(lx) node.next = lx
;dumy.next
function mergeList(l1,l2){
let dumy = new ListNode(0);
let node = dumy;
while(l1 && l2){
node.next = l1;
l1 = l1.next;
node.next = l2;
l2 = l2.next;
}
// 由于l1/l2长度一致
if(l1) node.next = l1;
if(l2) node.next = l2;
return dumy.next;
}
关键点解释:
slow = head
fast = head
fast && fast.next
非空fast
每次移动两步 fast = fast.next.next
slow
每次移动一步 slow = slow.next
fast.next ==null
,但是,fast
可能不为空fast
不为空,slow
还需要移动一步 slow = slow.next
(奇数情况)slow
所在的节点就是链表的中间节点function middleNode(head){
let slow = head;
let fast = head;
// 遍历链表节点
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// 处理链表节点为偶数的情况
if(fast){
slow = slow.next;
}
return slow;
}
?「哨兵节点」是为了简化处理链表「边界条件」而引入的「附加链表节点」 ?
哨兵节点通常位于「链表的头部」,它的值没有任何意义。在一个有哨兵节点的链表中,「从第二个节点开始才真正的保存有意义的信息」。
「哨兵节点」,在链表尾部添加元素
function append(head,value) {
// 哨兵节点
let dumy = new ListNode(0);
dumy.next = head;
// 遍历链表,直到链表尾部
let node = dumy;
while(node.next!=null){
node = node.next;
}
node.next = new ListNode(value);
return dumy.next;
}
在「遍历」链表的时候,并不是直接对dumy
进行处理,而是用了一个「临时游标节点」(node
)。这样做的好处就是,在append
操作完成以后,还可以通过dumy
节点来,直接返回链表的头节点dumy.next
。 因为,dumy
一直没参与遍历过程。
?为了删除一个节点,需要找到被删除节点的「前一个节点」,然后把该节点的
next
指针指向它「下一个节点的下一个节点」。 ?
「哨兵节点」,在删除指定节点
function delete(head ,value){
let dumy = new ListNode(0);
dumy.next = head;
let node = dumy;
while(node.next!=null){
if(node.next.value==value){
node.next = node.next.next;
barek;
}
node = node.next;
}
return dumy.next;
}
通过哨兵节点(dumy
)直接将「链表为空」和「被删除节点是头节点」的两种特殊情况,直接囊括了。用最少的代码,处理最多的情况。
?使用哨兵节点可以简化「创建」或「删除」链表头节点的操作代码 ?
在链表中,双指针思路又可以根据两个指针的不同「移动方式」分为两种不同的方法。
?
k
个节点?
k
个节点题目描述:
?给定一个链表,删除链表中「倒数」第
k
个节点 提示: 假设链表中节点的总数为n
且1≤ k ≤ n
「只能遍历一次链表」 示例:链表为1->2->3->4->5
,删除倒数第2个节点后链表为1->2->3->5
,删除了4
所在的节点 ?
front
从链表的头节点开始「向前走k
步」的过程中,第2个指针back
保持不动k+1
步开始,back
也从链表的头节点开始和front
以相同的速度遍历k
」,当指针front
指向链表的尾节点时(如果存在dumy
节点的话,就是front
指向尾节点的下一个节点),「指针back
正好指向倒数第k+1
个节点」k
个节点,而利用快慢双指针,我们可以找到倒数第k+1
个节点,即「倒数k
节点的前一个节点」, 那更新倒数k+1
节点的next
指针,就可以将倒数k
个节点删除k
等于链表的节点总数时,被删除的节点为原始链表的头节点,我们可以通过dumy
节点来简化对此处的处理dumy
节点的出现,由于存在front
/back
两个指针,就需要对其进行初始化处理。back
:由于存在③的情况(删除原始链表头节点),所以back
初始化「必须」是back=dumy
(back指向dumy
)front
:初始指向原始链表的头节点(front=head
)function removeNthFromEnd(head,k){
let dumy = new ListNode(0);
dumy.next = head;
let front = head; //指向原始链表头节点
let back = dumy; // 指向dumy节点
// front 向前移动了k个节点
for(let i =0; i<k; i++){
front = front.next;
}
// 同步移动
while(front!=null){
front = front.next;
back = back.next;
}
// 删除第k个节点
back.next = back.next.next;
return dumy.next;
}
在同步移动的过程中,「只有」front
移动到尾节点的下一个节点,即:null
时,此时back
节点才到了倒数k+1
的位置
题目描述:
?如果一个链表包含「环」,找出环的入口节点! 示例:输入:head = [3,2,0,-4], 输出: pos = 1 返回索引为 1 的链表节点 ?
append/delete
,可以不用dumy
节点)n
圈」之后将会「追上」走的慢的指针fast
指针指向链表头部」,slow
指针保持不变。 并且,slow/fast
以「相同的速度」(每次移动一个节点),在slow/fast
「再次」相遇时,就是环的入口节点快慢指针相遇点
根据快慢指针移动速度之间的关系,并且假设在快指针移动n
后相遇,我们可以有
1. a + n(b+c) + b
= a+(n+1)b+nc
(「快指针移动的距离」)
2. (a+b)
(「慢指针移动的距离」)
3. a+(n+1)b+nc=2(a+b)
(「快指针比慢指针多移动一倍的距离」)
4. a=c+(n?1)(b+c)
可以得出,如果有两个指针分别从「头节点」和「相遇节点」以「相同的速度」进行移动。在经过n-1
圈后,他们会在「环的入口处相遇」
「判断一个链表是否有环」
function hasCycle(head){
let fast = head;
let slow = head;
while(fast && fast.next){
fast = fast.next.next;
slow = slow.next;
if(fast == slow) return true;
}
return false;
}
「找到环的入口节点」
function detectCycle(head){
let fast = head;
let slow = head;
while(fast && fast.next){
fast = fast.next.next;
slow = slow.next;
if(fast ==slow){
fast = head;
while(fast!=slow){
fast = fast.next;
slow = slow.next;
}
return slow
}
}
return null;
}
通过对比我们发现,利用双指针查找链表中环的入口节点,其实就是在「判断链表是否有环」的基础上进行额外的处理。
题目描述:
?输入两个「单向」链表,找出它们的「第一个」重合节点 示例:链表A:1->2->3->4->5->6 链表B: 7->8->4->5->6 输出 两个链表的第1个重合节点的值是4 ?
next
指针都「指向同一个节点」。count1/count2
)distance = Math.abs(count1-count2)
个节点distance
个节点后,此时两个链表中「所剩节点数」相同,也就是说,从接下来,可以认为在「两个相同长度的单向链表」中寻找第一个重合节点「计算链表中有多少个节点」
function countList(head){
let count = 0;
while(head!=null){
count++;
head = head.next;
}
return count;
}
「查找第一个重合节点」
function getIntersectionNode(headA, headB) {
// 计算各自节点数量
let count1 = countList(headA);
let count2 = countList(headB);
// 相差节点数
let distance = Math.abs(count1-count2);
// 找出最长/最短 链表
let longer = count1 > count2 ? headA : headB;
let shorter = count1 > count2 ? headB : headA;
// 定义指向 longer链表的指针
let node1 = longer;
// 优先移动distance个节点
for(let i =0 ;i<distance;i++){
node1 = node1.next;
}
// 定义指向 shorter 链表的指针
let node2 = shorter;
// 判断处理
while(node1!=node2){
node2 = node2.next;
node1 = node1.next;
}
return node1;
};
?单向链表最大的特点就是其「单向性」--即只能顺着指向下一个节点的指针方向从头到尾遍历。 ?
而有些情况,从链表尾部开始遍历到头节点更容易理解。所以,就需要对链表进行反转处理。
题目描述:
?将指定的链表反转,并输出反转后链表的头节点 示例:链表:
1->2->3->4->5
反转后的链表为5->4->3->2->1
, 头节点为5所在的节点 ?
function reverseList(head){
// 初始化prev/cur指针
let prev = null;
let cur = head;
// 开始遍历链表
while(cur!=null){
// 暂存后继节点
let next = cur.next;
// 修改引用指向
cur.next = prev;
// 暂存当前节点
prev = cur;
// 移动指针
cur = next;
}
return prev;
};
题目描述:
?给一个链表,链表中节点的顺序是
l0->l1->l2->(...)->l(n-1)->ln
。对链表进行重排处理,使节点顺序变成l0->ln->l1->l(n-1)->l2->l(n-2)->(...)
示例:链表:1->2->3->4->5->6
重排后的链表为1->6->2->5->3->4
?
1->2->3
第二部分:4->5->6
4->5->6
-->6->5->4
1->6->2->5->3->4
next
指针方向向前走「两步」「找到链表的中间节点」(使用快慢指针)
function middleNode(head){
let slow = head;
let fast = head;
// 遍历链表节点
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// 处理链表节点为偶数的情况
if(fast){
slow = slow.next;
}
return slow;
}
「合并两个链表」
function mergeList(l1,l2){
let dumy = new ListNode(0);
let node = dumy;
while(l1 && l2){
node.next = l1;
l1 = l1.next;
node.next = l2;
l2 = l2.next;
}
// 由于l1/l2长度一致
if(l1) node.next = l1;
if(l2) node.next = l2;
return dumy.next;
}
「重排链表」
function reorderList(head){
if(head==null) return head;
//找到链表的中间节点
let mid = middleNode(head);
// 前半部分链表
let l1 = head;
// 后半部分链表
let l2 = mid.next;
// 将原链表一分为二
mid.next = null;
// 后半部分链表反转
l2 = reverseList(l2);
// 合并处理
mergeList(l1, l2);
}
题目描述:
?判断一个链表是回文链表 要求:时间复杂度为
O(n)
,空间复杂度为O(1)
示例:链表:1->2->3->3->2->1
该链表为回文链表 ?
还是熟悉的味道
「找到链表的中间节点」 (前文有介绍,这里不再赘述)
「反转某部分链表」 (前文有介绍,这里不再赘述)
那么,现在就剩下对两个链表进行对比判断了
function equails(head1,head2){
while(head1 && head2){
//相应位置的val不同,两个链表不同
if(head1.val!=head2.val){
return faslse;
}
head1 = head1.next;
head2 = head2.next;
}
// 如果head1/head2长度不同,也返回false
return head1 ==null && head2==null;
}
「判断是否为回文」
function isPalindrome(head) {
let left = head;
// 找到链表的中间节点
let slow = middleNode(head)
// 反转链表
let right = reverse(slow);
// 比较链表
return equals(left,right)
};
dumy
节点来相助k
个节点prev/cur/next
next= cur.next
)cur.next = prev
)prev= cur
)cur=next
)我们就自己实现一个比较功能完备的stack
。它有如下的功能点
push(element(s))
:添加一个(或几个)新元素到栈顶pop()
:移除栈顶的元素,同时返回被移除的元素peek()
: 返回栈顶的元素,不对栈做任何修改isEmpty()
:如果栈里没有任何元素就返回true
,否则返回false
size()
: 返回栈里的元素个数clear()
: 移除栈里所有的元素class Stack {
constructor() {
this.items = [];
}
// 添加element到栈顶
push(element) {
this.items.push(element);
}
// 移除栈顶的元素,同时返回被移除的元素
pop() {
return this.items.pop();
}
// 返回栈顶的元素,不对栈做任何修改
peek() {
return this.items[this.items.length - 1];
}
// 如果栈里没有任何元素就返回`true`,否则返回`false`
isEmpty() {
return this.items.length === 0;
}
// 返回栈里的元素个数
size() {
return this.items.length;
}
// 移除栈里所有的元素
clear() {
this.items = [];
}
}
虽然,我们实现了一个功能完备的stack
结构,但是仔细一看,其实就是对array
中push/pop
等api
进行了一次包装。但是,经过包装后,使得针对stack
结构的各种操作,变得更具有封装性,而不会产生很多样板代码。
题目描述:
?后缀表达式是一种算术表达式,也叫「逆波兰式」(
RPN
),它的操作符在操作数的后面。 要求输入一个用字符串数组表示的后缀表达式,请输出该后缀表达式的计算结果。 示例:后缀表达式["2","1","3","*","+"]
对应的表达式是2 + 1 * 3
,因此输出的计算结果为5
?
["2","1","3","*","+"]
为例子分析。2
,由于后缀表达式的特点,「操作符」还在后面,在操作符未知的情况下,是无法进行计算处理。所以,需要将当前的操作数进行「暂存处理」。1/3
)还是「没有操作符的出现」,继续将对应的操作数进行「暂存处理」*
)。按照后缀表达式的规则,此操作符对应的操作数是「刚刚」被暂存的「一对」操作数1/3
1/3
明显位于容器的尾部。也就是说,需要从容器的尾部将「一对」数据取出,并做运算处理。stack
来作为存储操作数的容器function evalRPN(tokens){
let stack = new Stack();
for(let token of tokens){
switch(token){
// 处理操作符
case "+":
case "-":
case "*":
case "/":
// 在源数据中,靠后的操作数
let back = stack.pop();
// 在源数据中,靠前的操作数
let prev = stack.pop();
// 计算操作数,并将其入栈处理
stack.push(
calculate(prev,back,token)
);
break;
default:
// 处理操作数,直接入栈
stack.push(parseInt(token));
}
}
// 操作符都处理完,且栈中只有一个数据
return stack.pop();
}
「辅助函数」,用于处理两个操作数之间的算术问题。(有一点需要注意,就是操作数之间的顺序问题)
fucntion calculate(prev,back,operator){
switch(operator){
case "+":
return prev + back;
case "-":
return prev - back;
case "*":
return prev * back;
case "/":
return (prev/back)>>0; // 数据取整
default:
return 0;
}
}
?输入一个表示小行星的数组
[4,5,-6,4,8,-5]
,它们相撞之后最终剩下3颗小行星[-6,4,8]
?
[4,5,-6,4,8,-5]
4/5
,而在遇到「方向不同」的行星时,是率先取「最近一次」加入到数据容器的数据。也就是说,针对数据容器中的数据的存取,满足「后进先出」的规则。我们可以考虑用栈来具象化该数据结构。stack
)battle
一下,哪怕身败名裂function asteroidCollision(asteroids){
let stack = new Stack();
for(let as of asteroids){
// 当前元素向左飞行,并且该元素的绝对值比栈顶元素大
while(!stack.empty()
&& stack.peek()>0
&& stack.peek()<-as
){
stack.pop();
}
// 当前元素向左飞行,当前元素和栈顶元素体积一样 (需要互相抵消)
if(stack.length
&& as<0
&& stack.peek()==-as
){
stack.pop();
}else if(
as >0 //当前元素向右飞行
|| stack.isEmpty() // 栈为空 (初始化)
// 当前元素向左飞行(在经过对比后,还是无法消除)
|| stack.peek()<0
){
stack.push(as)
}
}
return stack;
}
?给定一个只包括
'(',')'
,'{','}'
,'[',']'
的字符串 s ,判断字符串是否有效。 有效字符串需满足:
?
function isValid (s) {
let stack = new Stack();
// 遍历 字符串
for(let c of s){
// 遇到左括号,将与其匹配的右括号入栈处理
if(c==='('){
stack.push(')')
}else if(c==='['){
stack.push(']')
}else if(c==='{'){
stack.push('}')
// 遇到右括号
// 1. 判断栈内是否有括号,如果没有,那说明此时匹配不了
// 2. 满足①的情况下,判断此时字符是否和栈顶元素匹配
}else if(stack.isEmpty() || stack.pop()!==c){
return false;
}
}
// 最后再验证一下,栈是否为空,如果不为空,说明还有未匹配的括号
return stack.isEmpty();
};
?输入一个数组,每个数字都是某天的温度。 计算每天需要等几天才会出现更高的温度 示例:输入数组
[35,31,33,36,34]
,输出结果为[3,1,1,0,0]
?
function dailyTemperatures(temperatures){
// 定义一个与源数组相同的数组,用于存储最后结果
let result = new Array(temperatures.length);
let stack = new Stack();
for(let i = 0;i<temperatures.length;i++){
// stack 非空,且当前的温度大于栈顶温度
while(!stack.empty()
&& temperatures[i]>temperatures[stack.peek()]){
// 取出,存于stack中的满足条件的温度的下标
let prev = stack.pop();
// 计算等待天数 并将其存入result[prev]中
result[prev] = i - prev;
}
// 将当前下标存入stack中
stack.push(i)
}
return result;
}
「额外提醒」
stack
中取出栈顶元素stack
中的数据,找到了它对应的「需要等待的天数」i - prev
?输入一个由非负数组成的数组,数组中的数字是直方图中柱子的高,求直方图中最大矩形的面积 假设直方图中柱子的宽度为1 示例:输入数组
[2,1,5,6,2,3]
,直方图中最大矩形的面积为10(2*5)
?
i
的柱子开始,到下标为j
的柱子结束,那么两根柱子之间的矩形(含两端的柱子)的宽度是j-i+1
,矩形的高度就是两根柱子之间的「所有」柱子最矮的高度i/j
:i
表示靠前的柱子下标,j
表示靠后的柱子下标function largestRectangleArea(heights){
let maxArae = 0;
for(let i=0;i<heights.length;i++){
let min = heights[i];
for(let j=i;j<heights.length;j++){
min = Math.min(min,heights[j]);
let area = min * (j -i +1);
maxArea = Math.max(maxArea,area)
}
}
return maxArea;
}
想到maxX
是不是联想到「选择排序」 (最主要的特点就是「找极值」的序号(minIndex/largestIndex
))
我们来简单的再重温一下,选择排序的大体思路。
function selectionSort(arr){
let len = arr.length;
if(len<2) return arr; // 处理边界值
let i,j,minIndex;
// 外层循环: 控制迭代轮次
for(i=0;i<len-1;i++){
minIndex = i;
// 内层循环:从内层循环中找到最小值的位置
for(j=i+1;j<len;j++){
// 在未排区域寻找最小的数,并记录其位置j
if(arr[j]<arr[minIndex]) minIndex = j;
}
// 内层循环完毕,最小值确定,和已排区间最后一位交互位置
swap(arr,i,minIndex);
}
return arr;
}
这两个算法之间有很多相似的地方
由于采用了双层循环,所以该方法的时间复杂度为O(n?)
,不够优雅。我们可以采用更加优雅的处理方式。
自己实现一个比较功能完备的queue
。它有如下的功能点
enqueue(element(s))
:向队列「尾部」添加一个(或多个)新的项。dequeue()
:移除队列的第一项(即排在队列最前面的项)并返回被移除的元素。peek()
:返回队列中第一个元素——最先被添加,也将是最先被移除的元素。队列不做任何变动(不移除元素,只返回元素信息——与 Stack
类的 peek
方法非常类似)。isEmpty()
:如果队列中不包含任何元素,返回 true
,否则返回 false
。size()
:返回队列包含的元素个数,与数组的 length
属性类似。class Queue {
constructor() {
this.items = [];
}
// 入队
enqueue(element) {
this.items.push(element);
}
// 出队,并返回队首元素
dequeue() {
return this.items.shift();
}
// 查看,队首元素
peek() {
return this.items[0]
}
// 如果队列里没有任何元素就返回`true`,否则返回`false`
isEmpty() {
return this.items.length === 0;
}
// 返回队列的元素个数
size() {
return this.items.length;
}
// 移除队列里所有的元素
clear() {
this.items = [];
}
}
在数组中某一个长度的「子数组」可以看成数组的一个「窗口」。若给定数组[1,2,3,4,5,6]
,那么子数组[2,3,4]
就是其中一个大小为3的窗口。窗口向右滑动一个数字,那么窗口就包含数字[3,4,5]
。
也就是向右滑动窗口,每向右滑动一个数字,都在窗口的「最右边」插入一个数字,同时把「最左边」的数字删除。即满足队列 「先进先出」的特性。
题目描述:
?给定一个「整数数据流」和一个「窗口大小」,根据该滑动窗口的大小,计算滑动窗口里所有数字的平均值。
next
函数,会在滑动窗口中添加一个整数,并返回滑动窗口的所有数字的平均值?
sum
实时记录,窗口中「现存数据」的和class MovingAverage {
constructor(size) {
this.nums = new Queue();
this.capacity = size;
this.sum = 0;
}
next(val) {
this.nums.enqueue(val);
this.sum+=val;
if(this.nums.size()>this.capacity){
this.sum -=this.nums.dequeue();
}
return this.sum / this.nums.size()
}
}
二叉树的广度优先搜索是从上到下「按层」遍历二叉树,从二叉树的根节点开始,先遍历二叉树的第一层,再遍历第二层,以此类推。
通常「基于队列来实现二叉树的广度优先搜索」。
「二叉树节点」
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = (val===?developer/article/2195744/undefined ? 0 : val)
this.left = (left===?developer/article/2195744/undefined ? null : left)
this.right = (right===?developer/article/2195744/undefined ? null : right)
}
}
利用queue
实现「二叉树广度优先遍历」
function bfs(root){
let queue = new Queue();
if(root!=null) {
queue.enqueue(root);
}
let result = [];
while(!queue.isEmpty()){
let node = queue.dequeue();
result.push(node.val)
if(node.left!=null){
queue.enqueue(node.left);
}
if(node.right!=null){
queue.enqueue(node.right);
}
}
return result;
}
由于queue
的「先进先出」特性,二叉树的「某一层节点按照从左到右的顺序」插入队列中。因此,这些节点一定会按照从左到右的顺序遍历到。用广度优先(BFS)的顺序遍历二叉树,很容易知道
也就是说,关于二叉树的题目如果出现「层」的概念,尝试用广度优先来解决问题。
题目描述:
?输入一课二叉树,请找出二叉树中「每层」的最大值。 示例:输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
?
queue1
只放当前遍历层的节点queue2
只放下一层的节点queue1
中。queue1
用来存放当前遍历层的节点,「总是从队列queue1
中取出节点来遍历」queue2
queue1
被清空时,此时能够获取到当前层的最大值queue1
指向queue2
queue2
重新初始化为空队列function largestValues(root) {
let q1 = new Queue();
let q2 = new Queue();
let result = [];
if(root!=null){
q1.enqueue(root);
}
let max = Number.MIN_SAFE_INTEGER;
while(!q1.isEmpty()){
let node = q1.dequeue();
max = Math.max(max,node.val);
if(node.left!=null){
q2.enqueue(node.left);
}
if(node.right !=null){
q2.enqueue(node.right);
}
if(q1.isEmpty()){
result.push(max);
max = Number.MIN_SAFE_INTEGER;
q1 = q2;
q2 = new Queue();
}
}
return result;
}
题目描述:
?输入一课二叉树,找出它「最底层最左边」节点的值。 示例:输入: root = [1,2,3,4,null,5,6,null,null,7] 输出: 7
?
bottomLeft
来保存每层最左边的节点的值。每当新的层级出现时候,将bottomLeft
的值变更为第一个节点的值。function findBottomLeftValue(root){
let q1 = new Queue();
let q2 = new Queue();
q1.enqueue(root);
let bottomLeft = root.val;
while(!q1.isEmpty()){
let node = q1.dequeue();
if(node.left !=null){
q2.enqueue(node.left)
}
if(node.right !=null){
q2.enqueue(node.right)
}
if(q1.isEmpty()){
q1 = q2;
q2 = new Queue();
// 当q1为空时,开始遍历下一层,如果下一层还有节点,则更新bottomLeft
if(!q1.isEmpty()){
bottomLeft = q1.peek().val;
}
}
}
return bottomLeft
}
题目描述:
?输入一课二叉树,站在该二叉树的右侧,从上到下看到的节点构成二叉树的右侧视图。 示例:输入: root = [1,2,3,null,5,null,4] 输出: [1,3,4]
?
function rightSideView(root){
let result = [];
if(root==null) return result;
let q1 = new Queue();
let q2 = new Queue();
q1.enqueue(root);
while(!q1.isEmpty()){
let node = q1.dequeue();
if(node.left!=null){
q2.enqueue(node.left)
}
if(node.right !=null){
q2.enqueue(node.right)
}
if(q1.isEmpty()){
result.push(node.val); //此时node是当前层的最后一个节点
q1= q2;
q2 = new Queue();
}
}
return result;
}
?回溯法可以看做「暴力法的升级版」,它在解决问题时的每一步都「尝试所有可能的选项」,最终「找出所有可行的解决方案」。 ?
回溯法非常适合解决「由多个步骤组成的问题,并且每个步骤都有多个选项」。
?用回溯法解决问题的过程可以形象的「用一个树形结构表示,求解问题的每个步骤可以看作树中的一个节点」。如果在某一步有
n
个可能的「选项」,那「每个选项是树中的一条边」,经过这些边就可以到达该节点的n
个子节点。 ?
在采用回溯法解决问题时,
?因此,采用回溯法解决问题的过程实质上是在树形结构中从根节点开始进行「深度优先遍历」 ?
通常,回溯法的深度优先遍历用「递归」代码实现。
如果在前往某个节点时对问题的解的「状态进行了修改」,那么在回溯到它的父节点时,要「清除相应的修改」。
从一个包含m
个元素的集合中挑选出n
个元素(0≤n≤m
)形成一个子集Subset。一个子集又称为一个组合。如果两个子集(组合)的元素完全相同只是顺序不同,那么它们可以看作同一个子集(组合)。
从一个包含m
个元素的集合中挑选出n
个元素(0≤n≤m
)并按照某种顺序形成一个「排列」。 m
等于n
的排列有称为「全排列」。如果两个排列的元素完全相同只是顺序不同,那么它们就是两个不同的排列。 「排列与元素的顺序相关」。
题目描述:
?输入一个「不含重复数字」的数据集合,请找出它的「所有」子集 输入:
nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
?
n
个元素,那么生成子集可以分为n
步」function subsets(nums){
let result = [];
if(nums.length == 0) return result;
(function helper(nums,index,subset,result){
if(index === nums.length){ // 基线条件
result.push([...subset])
}else if(index < nums.length){
helper(nums,index + 1, subset,result); // 不将数字添加到子集
subset.push(nums[index]); // 将数字添加到子集中
helper(nums,index + 1,subset,result);
subset.pop();
}
})(nums,0,[],result)
return result;
}
代码解释
helper
有四个参数nums
是数组nums
,包含输入集合的所有数字。可以逐一从集合中「取出一个数字并选择是否将数字添加到子集中」。index
是当前取出的数字在数组nums
中下标subset
是「当前子集」result
是「所有已经生成」的子集nums
中取出一个下标为index
的数字时,都要考虑是否将该数字添加到子集subset
中。subset.push(nums[index])
nums
下一个数字(下标增加1
)helper(nums,index + 1, subset, result)
helper
也执行完成,接下来将回溯到前一个数字的函数调用处继续执行。」subset.pop()
helper(nums,index + 1,subset,result)
index
的数字添加到子集subset
中」。helper
处理数组nums
中的下一个数字(下标增加1)」index
等于数组nums
的长度时候」,表示数组中的所有数字都已经处理过,因此可以生成一个子集。将子集subset
添加到result
中subset
的副本,因为接下来还需要修改subset
用以获得其他的子集result.push([...subset])
题目描述:
?输入
n
和k
,请输入从1
到n
中选取k
个数字组成的所有「组合」。 输入:n = 3, k = 2 输出:[[1,2],[1,3],[2,3]]
?
k
个数字的组合function combine(n,k){
let result = [];
(function helper(n,k,index,subset,result){
if(subset.length === k){ // 基线条件
result.push([...subset])
}else if(index <= n){
helper(n,k, index + 1, subset,result); // 不将数字添加到子集
subset.push(index); // 将数字添加到子集中
helper(n,k,index + 1,subset,result);
subset.pop();
}
})(n,k,1,[],result)
return result;
}
代码解释
helper
有五个参数n
是数组范围1~n
k
是组合的长度index
是当前取出的数字subset
是当前子集result
是所有「已经生成」的子集subset.length
等于k
时,进行子集的收集处理result.push([...subset])
index
是从1
开始的。题目描述:
?给定一个「没有重复数字」的正整数集合,请找出所有元素之和等于某个给定值(
target
)的所有组合。 同一个数字可以在组合中「重复任意次」。 输入:candidates = [2,3,6,7], target = 7
输出:[[7],[2,2,3]]
?
i
的数字,此时,「面临两个选择」。i + 1
的数字。i
的数字。function combinationSum(nums,target){
let result = [];
(function helper(nums,target,index,subset,result){
if(target ==0){ //基线条件
result.push([...subset])
}else if(target > 0 && index < nums.length){
helper(nums,target,index + 1,subset,result); // 不将数字添加到子集
subset.push(nums[index]); // 将数字添加到子集中
helper(nums,target - nums[index],index,subset,result);
subset.pop();
}
})(nums,target,0,[],result)
return result;
}
代码解释
nums[index]
可能在组合中「重复出现」,因此在index
处,「选择了将数字添加到组合」的选择,「递归调用helper
时,index
是不需要+1的」。target
target - nums[index]
target
为0
时,说明现在「子集」已经满足情况。result.push([...subset])
target
只能少,不能多,所以可以判断target
与0
的关系,来进行「剪枝」处理。if(target>0 && index < nums.length)
上面的几个题目都是关于数学上的组合、集合,其实这些「模型」可以应用到很多其他问题中。
例如,当客人走近餐厅准备吃饭,一种点菜的方法就是生成一个符合条件的组合。
k
道菜」,那么就是找出「包含k
个元素」的所有符合条件的组合题目描述:
?给定一个可能「包含重复数字」的整数集合,请找出所有元素之和等于某个给定值(
target
)的所有组合。 输出中不得包含重复的组合。 输入:candidates = [2,5,2,1,2], target = 5
输出:[[1,2,2],[5]]
?
m
的数字时,跳过所有值为m
的数字。」function combinationSum(nums,target){
nums.sort((a,b) => a -b);
let result = [];
(function helper(nums,target,index,subset,result){
if(target == 0){ // 基线条件
result.push([...subset]);
}else if(target > 0 && index < nums.length){
// 选择跳过某批值相同的数字
helper(nums,target,getNext(nums,index),subset,result);
subset.push(nums[index]);
helper(nums,target - nums[index], index + 1,subset,result);
subset.pop();
}
})(nums,target,0,[],result)
return result;
}
辅助函数
function getNext(nums,index){
let next = index;
while(next < nums.length && nums[next] == nums[index]){
next++;
}
return next;
}
代码解释
getNext
找到与当前index
值不同的下标题目描述:
?给定一个「没有重复数字」的集合,请找出它的所有全排列。 输入:
nums = [0,1]
输出:[[0,1],[1,0]]
?
n
个元素,n
步n
个选项n-1
个选项n
步,每一步面临着若干选项」 -- 「回溯法」function permute(nums){
let result = [];
(function helper(nums,index,result){
if(index == nums.length){
result.push([...nums]) // 基线条件
}else {
for(let j = index;j<nums.length;j++){
swap(nums,index,j); // 数字替换位置
helper(nums,index + 1,result);
swap(nums,index,j); // 清除对排列状态的修改
}
}
})(nums,0,result)
return result;
}
辅助函数
const swap = (nums,i,j) => [nums[i],nums[j]] = [nums[j],nums[i]];
代码解释
nums
保存着当前排列的状态」helper
生成排列的下标为index
的数字时,0
到index-1
的数字都「已经选定」,nums
中下标从index
到n-1
的数字(假设数组的长度为n
)都有可能放到排列的下标为index
的位置helper
中「有一个for
循环逐一用下标为index
的数字交互它后面的数字」。for
循环包含下标为index
的数字本身,因为它自己也能放在排列下标为index
的位置swap(nums,index,j)
index + 1
的数字helper(nums,index + 1, result)
swap(nums,index,j)
题目描述:
?给定一个包含「重复数据」的集合,请找出它的所有全排列 输入:
nums = [1,1,2]
输出:[[1,1,2],[1,2,1],[2,1,1]]
?
i
个数字时,如果已经将某个值为m
的数字交换为排列的第i
个数字,那么再遇到其他值为m
的数字就「跳过」function permuteUnique(nums){
let result = [];
(function helper(nums,index,result){
if(index === nums.length){
result.push([...nums]); // 基线条件
}else {
let map = {};
for(let j = index;j<nums.length;j++){
if(!map[nums[j]]){
map[nums[j]] = true;
swap(nums,index,j);
helper(nums,index + 1,result);
swap(nums,index,j);
}
}
}
})(nums,0,result)
return result;
}
辅助函数
const swap = (nums,i,j) => [nums[i],nums[j]] = [nums[j],nums[i]];
代码解释
map
,来保存已经交换到排列下标为index
的位置的所有值」。index
位时才做交换,否则直接跳过for
循环中多一层判断if(!map[nums[j]])
除了可以解决与集合排列、组合相关的问题,回溯法还能解决很多问题。
如果解决一个问题需要「若干步骤」,并且每一步都面临「若干选择」,当在「某一步」做了某个选择之后,前往下一步仍然面临若干选项。那么可以考虑用「回溯法」
?通常,回溯法可以用「递归代码」实现。 ?
题目描述:
?输入一个正整数
n
,请输出「所有」包含n
个左括号和n
个右括号的组合,要求每个组合的左括号和右括号匹配。 输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
?
n
,生成的括号组合包含n
个左括号和n
个右括号。2n
步,每一步生成一个括号n
个function generateParenthesis(n){
let result = [];
(function helper(left,right,subset,result){
if(left == 0 && right ==0){
result.push(subset); //基线条件
return ;
}
// 已经生成的左括号的数目少于`n`个
if(left > 0){
helper(left -1,right,subset + "(",result)
}
// 已经生成的右括号的数目少于已经生成的左括号的数目
if(left < right){
helper(left,right -1,subset + ")",restule)
}
})(n,n,"",result)
return result;
}
代码解释
left
:表示「还需要生成」的左括号的数目right
:表示「还需要生成」右括号的数目。left-1
;每生成一个右括号,参数right -1
;当left/right
都等于0
,一个完整的括号组合生成result.push(subset);
n
个」(left>0
)就能生成一个左括号left < right
)就能生成一个右括号题目描述:
?输入一个字符串,要求将它「分割成若干子字符串,使每个字符串都是回文」。 输入:
s = "aab"
输出:[["a","a","b"],["aa","b"]]
?
n
个字符,那么面临n
个选项1
的字符串(只包含该字符)2
的字符串(包含该字符及它后面的一个字符)x
的字符串 (x<n
)n
的字符串function partition(str){
let result = [];
(function heler(str,start,subset,result){
if(start == str.length){
result.push([...subset]); // 基线条件
}else {
for(let i = start;i<str.length;i++){
if(isPalinadrome(str,start,i)){
subset.push(str.substring(start,i+1));
helper(str,i + 1,subset,result);
subset.pop();
}
}
}
})(str,0,[],result)
return result;
}
辅助函数
function isPalinadrome(str,start,end){
while(start < end){
if(str[start++]!=str[end--]) return false;
}
return true
}
代码解释
start
的字符串时,用一个for
循环逐一判断从下标start
开始到i
结束的每个子字符串是否会回文i
从下标start
开始,到字符串s
的最后一个字符结束subset
中subset.push(str.substring(start,i+1))
(substring
它的第一个参数表示子字符串的开始位置,第二个位置表示结束位置--返回结果不含该位置)i+1
开始的剩余字符串。?如果解决一个问题需要若干步骤,并且在每一步都面临着若干选项,那么可以尝试用「回溯法」解决问题。 ?
应用回溯法能够解决「集合的排列、组合」的很多问题。
?回溯法都可以使用「递归」的代码实现。递归代码需要先确定「递归退出」的边界条件(基线条件),然后逐个处理集合中的元素。 ?
对于「组合类」问题,每个数字都面临两个选项
对于「排列类」问题,一个数字如果后面有n
个数字,那么面临n+1
个选择,即可以将数字和后面的数字(包括它自身)交换。
运用动态规划解决问题的第一步是识别哪些问题适合运用动态规划。和运用回溯法的问题类似,「使用动态规划的问题都存在若干步骤,并且每个步骤都面临若干选择」。
最大值或者最小值
),或者求问题的「数目」,那选择「动态规划」在采用动态规划时,总是用「递归」的思路分析问题,即「把大问题分成小问题,再把小问题的解合起来形成大问题的解」。
?找出描述大问题的解和小问题的解之间「递归关系的状态转移方程」是采用动态规划解决问题的关键所在。 ?
如果将大问题分解成若干小问题之后,小问题「相互重叠」,那么「直接用递归的代码」实现就会存在「大量重复计算」。小问题之间存在重叠的部分,这是可以运用动态规划求解问题的另一个显著特点。
在用代码实现动态规划时,有两种方式
?
?
题目描述:
?一个数组
cost
的所有数字都是正数,它的第i
个数字表示在一个楼梯的第i
级台阶往上爬的成本,在支付了成本cost[i]
之后可以从i
级台阶往上爬1级或2级。 假设台阶至少有2级,既可以从第0级台阶出发,也可以从第1级台阶出发。请计算爬上该楼梯的「最少」成本。 输入:cost = [10, 15, 20]
输出:15
--> 最低花费是从cost[1]
开始,然后走两步即可到阶梯顶,一共花费 15 。 ?
用f(i)
表示从楼梯的第i
级台阶「再往上」爬的「最少」成本。如果一个楼梯有n
级台阶(台阶从0
开始计数,从第0
级一直到第n-1
级),由于一次可以爬1级或2级台阶,因此可以从第n-2
级台阶或第n-1
级台阶爬到楼梯的顶部,「即f(n-1)
和f(n-2)
的最小值就是这个问题的最优解」。
?应用动态规划的「第1步」是找出「动态转移方程」,即用一个等式表示其中「某一步」的「最优解」和「前面若干步的最优解」的关系。(反向推理) ?
根据题目要求,可以一次爬1级或2级台阶,
i-1
级台阶爬上第i
级台阶,i-2
级台阶爬上第i
级台阶。因此,从第i
级台阶往上爬的最少成本应该是从第i-1
级台阶往上爬的最少成本和从第i-2
级台阶往上爬的最少成本的较小值再加上爬第i
级台阶的成本。
用状态转移方程表示为f(i) = Math.min(f(i-1),f(i-2)) + cost[i]
上面的状态转移方程有一个「隐含」条件,即i
大于或等于2
。
i
等于0,可以直接从第0
级台阶往上爬 -> f(0) = cost[0]
i
等于1,可以直接从第1
级台阶往上爬 -> f(1) = cost[1]
「状态转移方程其实是一个递归的表达式」,可以很方便的将它转换成递归代码。
function minCost(cost){
let len = cost.length;
return Math.min(helper(cost,len -2),helper(cost,len -1));
}
辅助函数
function helper(cost,i){
if(i<2){ // 基线条件
return cost[i]
}
return Math.min(helper(cost,i-2),helper(cost,i-1)) + cost[i];
}
代码解释
helper
和状态转移方程相对应f(i)
这个问题的解,依赖于求解f(i-1)
和f(i-2)
这两个子问题的解,由于求解f(i-1)
和f(i-2)
这两个子问题有重叠的部分。如果「只是简单的将状态转移方程转换成递归的代码就会带来严重的效率问题」。为了避免重复计算,一个常用的解决办法就是将「已经求解过的问题的结果保存下来」。
在每次求解一个问题之前,应「先检查」该问题的求解结果是否已经存在。如果问题的求解过程已经存在,则不需要重复计算,只需要「从缓存中读取」之前的求解结果即可。
function minCost(cost){
let len = cost.length;
if(len<=2){
return Math.min(cost[0],cost[1])
}
//初始化都为 0 计算之后应该是大于 0 的结果
let dp = new Array(len).fill(0);
//从最上层的台阶往下走 从上到下进入递归
helper(cost,len -1,dp);
return Math.min(dp[len-2],dp[len-1]);
}
辅助函数
function helper(cost,i,dp){
if(i<2){ //基线条件
dp[i] = cost[i]
}else if(dp[i]==0){
helper(cost,i-2,dp);
helper(cost,i-1,dp);
dp[i] = Math.min(dp[i-2],dp[i-1]) + cost[i]
}
}
代码解释
dp
用来保存求解每个问题结果的缓存dp[i]
用来保存f(i)
的计算结果0
-> new Array(len).fill(0)
f(i)
之前已经求解过,那么dp[i]
的缓存的结果将是一个大于0的数值。dp[i]
等于0时,它对应的f(i)
「之前还没有被求解过」dp
,就能确保每个问题f(i)
只需要求解一次。i<2
的情况,是直接返回dp[i] = cost[i]
,但是,没有处理比较特殊的情况cost.length ≤2
时,需要做一次特殊处理。 Maht.min(cost[0],cost[1])
也可以「自下而上」的解决这个过程,也就是「从子问题入手,根据两个子问题f(i-1)
和f(i-2)
的解求出f(i)
的结果」。
通常用「迭代」的代码实现自下而上的求解过程。
function minCost(cost){
let len = cost.length;
let dp = new Array(len).fill(0);
dp[0] = cost[0];
dp[1] = cost[1];
for(let i =2;i<len;i++){
dp[i] = Math.min(dp[i-2],dp[i-1]) + cost[i]
}
return Math.min(dp[len-2],dp[len-1])
}
代码解释
f(0)
和f(1)
的结果并保存到数组dp
的「前两个位置」dp[0] = cost[0];
dp[1] = cost[1];
for
循环根据状态转移方程逐一求解f(2)
到f(n-1)
O(n)
用一个长度为n
的数组将所有f(i)
的结果都保存下来。但是,在求解f(i)
时只需要f(i-1)
和f(i-2)
的结果。 从f(0)
到f(i-3)
的结果其实在求解f(i)
并没有任何作用。
也就是说,在求每个f(i)
的时候,需要保存之前的f(i-1)
和f(i-2)
的结果,因此「只需要一个长度为2的数组即可」
function minCost(cost){
let len = cost.length;
let dp = [cost[0],cost[1]];
fort(let i =2;i<len;i++){
dp[i&1] = Math.min(dp[0],dp[1])+cost[i]
}
return Math.min(dp[0],dp[1]);
}
代码解释
dp
的长度是2,求解的f(i)
的结果保存在数组下标为i&1
的位置。f(i-1)
和f(i-2)
的结果计算出f(i)
的结果,并「将f(i)
的结果写入之前保存f(i-2)
的位置」。f(i)
的结果覆盖f(i-2)
的结果并不会带来任何问题f(i+1)
只需要f(i)
的结果和f(i-1)
的结果f(i-2)
的结果O(n)
的数据,缓存之后就能够「确保每个子问题值需要计算一次」O(n)
O(n)
。和第二种解法有两方面的不同O(1)
。解决单序列问题,需要「若干步骤,并且每个步骤都面临若干选择,需要计算解的数目或最优解」。
这类题目的输入通常是「一个序列」,如一个一维数组或字符串。
?应用动态规划解决单序列问题的关键是「每一步在序列中{增加}一个元素,根据题目的特点找出该元素对应的最优解(或解的数目)和前面若干元素(通常是一个或两个)的最优解(或解的数目)的关系,并以此找出相应的状态转移方程」。 ?
一旦找出了状态转移方程,只要注意避免不必要的重复计算,就能解决问题。
题目描述:
?输入一个数组表示某条街道上的一排房屋内的财产的数量。如果这条街道上「相邻」的两栋房屋被盗就会自动触发报警系统。请计算小偷在这条街道上「最多」能偷取到多少财产 输入:
nums = [1,2,3,1]
输出:4
偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 =1 + 3 = 4
。 ?
n
幢房屋(分别用0~n-1
标号),小偷从标号为0
的房屋开始偷东西。f(i)
表示小偷从标号为0
的房屋开始标号为i
的房屋为止最多能偷取到的财物最大值f(n-1)
的值是小偷从n
幢房屋中能偷取的最多财物的数量。i
的房屋前有「两个选择」i-1
的房屋内,之前他「最多能偷取的财物的最大值是f(i-2)
」,因此,如果进入标号为i
的房屋并进行偷盗,他最多能偷的f(i-2)+nums[i]
i
的房屋」 - 那么他可以进入标号为i-1
的房屋,因为此时他「最多能偷取的财物数量为f(i-1)
」i
的房屋时,他能偷取的财物的最大值就是「两个选项的最大值」f(i) = max(f(i-2)+nums[i],f(i-1))
i
大于或等于2i
等于0时,f(0) = nums[0]
i
等于1时,f(1)= max(nums[0],nums[1])
「状态转移方程是一个递归的表达式」。可以创建一个数组dp
,它的第i
个元素dp[i]
用来保存f(i)
的结果。
如果f(i)
之前已经计算出结果,那么只需要从数组dp
中读取dp[i]
的值,不用在重复计算。
function rot(nums){
if(nums.length==0) return 0;
let dp = new Array(nums.length).fill(-1);
(function helper(nums,i,dp){
if(i ==0){
dp[i] = nums[0]
}else if(i ==1){
dp[i] = Math.max(nums[0],nums[1])
}else if(dp[i]<0){
helper(nums,i -2,dp);
helper(nums,i -1,dp);
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])
}
})(nums,nums.length-1,dp);
return dp[nums.length-1]
}
代码解释
helper
就是将状态转移方程f(i)= max(f(i-2)+nums[i],f(i-1))
翻译成js的代码。i
大于或等于2
,因此函数helper
单独处理了i
分别等于0
和1
的特殊情况「递归代码」是采用「自上而下」的处理方式,我们也可以选择使用「自下而上」的「迭代代码」。
先求出f(0)
和f(1)
的值,
f(0)
和f(1)
的值求出f(2)
f(1)
和f(2)
的值求出f(3)
f(n-1)
function rob(nums){
if(nums.length==0) return 0;
let dp = new Array(nums.length).fill(0);
dp[0] = nums[0];
if(nums.length>1){
dp[1] = Math.max(nums[0],nums[1])
}
for(let i=2;i<nums.length;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])
}
return dp[nums.length-1]
}
在空间复杂度为O(n)
的迭代代码中发现,计算dp[i]
时,只需要用到dp[i-1]
和dp[i-2]
两个值,也就是说,「只需要缓存两个值就足够了」,并不需要一个长度为n
的数组。
function rob(nums){
if(nums.length==0) return 0;
let dp = new Array(2).fill(0);
dp[0] = nums[0];
if(nums.length>1){
dp[1] = Math.max(nums[0],nums[1])
}
for(let i=2;i<nums.length;i++){
dp[i&1] = Math.max(dp[(i-1)&1],dp[(i-2)&1]+nums[i])
}
return dp[(nums.length-1)&1]
}
代码解释
dp
的长度为2
,将f(i)
的计算结果保存在数组下标为dp[i&1]
的位置f(i)
和f(i-2)
将保存到数组的同一个位置」f(i-1)
和f(i-2)
的结果计算出f(i)
,然后用f(i)
的结果写入数组原来保存f(i-2)
的位置。f(-1)
和f(i)
的结果计算出f(i+1)
题目描述:
?一条「环形街道」上有若干房屋。输入一个数组表示该条街道上的房屋内财产的数量。如果这条街道上相邻的两幢房屋被盗就会自动触发报警系统。计算小偷在这条街道上「最多」能偷取的财产的数量 输入:
nums = [1,2,3,1]
输出:4
先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。 偷窃到的最高金额 =1 + 3 = 4
。 ?
n
幢房屋围成一个「首尾相接」的环形,那么标号为0
的房屋和标号为n-1
的房屋相邻。如果小偷进入这两幢房屋内偷东西就会触发报警系统。0
和n-1
的两幢房屋内偷东西」0
开始到标号为n-2
结束的房屋内偷得的最多财物的数量1
开始到标号为n-1
结束的房屋内偷得的最多财物的数量在线性街道的代码基础上做一点修改
function rob(nums){
if(nums.length ==0) return 0;
if(nums.length ==1) return nums[0];
let result1 = helper(nums,0,nums.length -2);
let result2 = helper(nums,1,nums.length -1);
return Math.max(result1,result2)
}
辅助函数helper
function helper(nums,start,end){
let dp = new Array(2).fill(0);
dp[0] = nums[start];
if(start<end){
dp[1] = Math.max(nums[start],nums[start+1])
}
// 注意i的取值
for(let i= start+2;i<=end;i++){
let j = i - start; //这里是关键
dp[j&1] = Math.max(dp[(j-1)&1],dp[(j-2)&1]+nums[i])
}
// 最后取值
return dp[(end- start)&1]
}
双序列问题的输入「有两个或更多的序列,通常是两个字符串或数组」。
?由于输入的是两个序列,因此「状态转移方程通常有两个参数」,
f(i,j)
0
到i
的子序列0
到j
的子序列的「最优解或解的个数」 ?
一旦找到了f(i,j)
与
f(i-1,j-1)
f(i-1,j)
f(i,j-1)
的关系,问题就会迎刃而解。
双序列的状态转移方程有两个参数,因此通常需要使用一个「二维数组来保存状态转移方程的计算结果」。
题目描述:
?输入两个字符串,请求出它们的「最长」公共子序列的长度。 如果从字符串
s1
中「删除若干字符」之后能得到字符串s2
,那么字符串s2
就是字符串s1
的一个子序列 输入:s1 = "abcde"
,s2 = "ace"
输出:3
最长公共子序列是 "ace" ,它的长度为 3。 ?
f(i,j)
表示0
到i
的字符串(记为s1[0..i]
)0
到j
的字符串(记为s2[0..j]
)m
,第2个字符串的长度是n
,那么f(m-1,n-1)
就是问题的解i
的字符(记为s1[i]
)与第2个字符串中下标为j
(记为s2[j]
)的「字符相同」,f(i,j)
相当于在s1[0..i-1]
和s2[0..j-1]
的最长公共子序列的后面添加一个「公共字符」。f(i,j) = f(i-1,j-1)+1
s1[i]
与字符s2[j]
不相同,则这两个字符不可能「同时出现在」s1[0..i]
和s2[0..j]
的公共子序列中。此时s1[0..i]
和s2[0..j]
的最长公共子序列,s1[0..i-1]
和s2[0..j]
的最长公共子序列s1[0..i]
和s2[0..j-1]
的最长公共子序列f(i,j)
是f(i-1,j)
和f(i,j-1)
的「最大值」s1[i]==s2[j]
, f(i,j) = f(i-1,j-1)+1
s1[i]!=s2[j]
, f(i,j) = max(f(i-1,j),f(i,j-1))
i
或者j
等于0
时,即求f(0,j)
或f(i,0)
时可能需要的f(-1,j)
或f(i,-1)
的值。f(0,j)
的含义是s1[0..0]
和s2[0..j]
这两个字符串的最长公共子序列的长度0
的字符,那么f(-1,j)
对应的第1个子字符串再减少一个字符0
,所以f(-1,j)
的值等于0状态转移方程可以用递归的代码实现,但由于存在「重叠的子问题」,因此需要用一个「二维数组缓存计算结果」,以确保不必要的重复计算。
?也可以用「自下而上」的方法来计算状态转移方程,这个方程可以「看成一个表格的填充过程」,可以用一个表格来保存
f(i,j)
的计算结果。 ?
i
等于-1
对应的行和j
等于-1
对应的列都初始化为0
「先用一个二维数组实现这个表格,然后用一个二重循环实现从上到下、从左到右的填充顺序」。
function longestCommonSubsequence(s1,s2){
let l1 = s1.length;
let l2 = s2.length;
// 注意行、列的长度 (l1+1/l2+1)
let dp = new Array(l1+1).fill(0)
.map(()=>
new Array(l2+1).fill(0)
)
for(let i=0;i<l1;i++){
for(let j=0;j<l2;j++){
if(s1[i]==s2[j]){
dp[i+1][j+1]= dp[i][j]+1
}else {
dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j])
}
}
}
return dp[l1][l2];
}
代码解释
i
等于-1
对应的行和j
等于-1
对应的列,因此如果输入字符串的长度分别为m
、n
,那么代码中的二维数组dp
的行数和列数分别是m+1
和n+1
f(i,j)
的值保存在dp[i+1][j+1]
中」f(i,j)
的值依赖于表格中
f(i-1,j-1)
的值、f(i-1,j)
的值f(i,j-1)
的值由于计算f(i,j)
的值只需要使用「上方一行」的值和「同一行左边」的值,因此实际上只需要保存表格中两行就可以。
function longestCommonSubsequence(s1,s2){
let l1 = s1.length;
let l2 = s2.length;
if(l1<l2){
return longestCommonSubsequence(s2,s1)
}
//行数为2
let dp = new Array(2).fill(0)
.map(()=>
new Array(l2+1).fill(0)
)
for(let i=0;i<l1;i++){
for(let j=0;j<l2;j++){
if(s1[i]==s2[j]){
// 处理行数
dp[(i+1)&1][j+1]= dp[i&1][j]+1;
}else {
// 处理行数
dp[(i+1)&1][j+1] = Math.max(
dp[i&1][j+1],
dp[(i+1)&1][j]
)
}
}
}
return dp[l1&1][l2]
}
代码解释
dp
只有两行,f(i,j)
的值保存在dp[(i+1)&1][j+1]
中。dp
的行数是一个常数,因此此时的空间复杂度是O(min(m,n))
?只需要用一个一维数组就能保存所有计算所需要的信息。这个「一维数组的长度是表格的列数」。(即输入字符串
s2
的长度+1)。 ?
为了让一个一维数组保存表格的两行信息。
f(i,j)
和f(i-1,j)
都保存在数组dp
下标j+1
的位置。在计算f(i,j)
之前,dp[j+1]
中保存的是f(i-1,j)
的值;在完成f(i,j)
的计算之后,dp[j+1]
被f(i,j)
的值替换。
在计算f(i,j+1)
时,可能还需要f(i-1,j)
的值,因此在计算f(i,j)
之后,「不能」直接用f(i,j)
的值替换dp[j+1]
中的f(i-1,j)
的值。
可以在用f(i,j)
的值替换dp[j+1]
中f(i-1,j)
的值「之前」先将f(i-1,j)
的值「临时保存起来」。这样在下一步在计算f(i,j+1)
时还能得到f(i-1,j)
的值。
function longestCommonSubsequence(s1,s2){
let l1 = s1.length;
let l2 = s2.length;
if(l1<l2){
return longestCommonSubsequence(s2,s1)
}
let dp = new Array(l2+1).fill(0);
for(let i=0;i<l1;i++){
let prev = dp[0];
for(let j = 0;j<l2;j++){
let cur ;
if(s1[i]==s2[j]){
cur = prev +1;
}else {
cur = Math.max(dp[j],dp[j+1])
}
prev = dp[j+1];
dp[j+1]= cur;
}
}
return dp[l2]
}
代码解释
prev
用来保存数组中被替换的值。f(i,j)
之前,变量prev
保存的是f(i-1,j-1)
的值。f(i,j)
(代码中变量cur
)之后,将它保存到dp[j+1]
中。f(i,j)
之前,将保存在dp[j+1]
中的值(即f(i-1,j)
)临时保存到变量prev
中f(i,j+1)
时可以从变量prev
中得到f(i-1,j)
cur = Math.max(dp[j],dp[j+1])
中dp[j]
对应的是f(i,j-1)
dp[j+1]
对应的是f(i-1,j)
f(i,j)
之前,f(i,j-1)
的值已经计算出来并保存到dp[j]
的位置f(i,j)
的值还没有计算出来,因此保存在dp[j+1]
中的还是f(i-1,j)
的值这类问题通常输入是一个「二维的格子」,一个机器人按照一定的规则从格子的某个位置走到另一个位置,要求计算「路径的条数或找出最优路径」。
?矩阵路径相关问题的状态转移方程通常有「两个参数」,即
f(i,j)
的两个参数i
、j
通常是机器人「当前到达的坐标」。 ?
需要根据路径的特点找出到达坐标(i,j)
之前的位置,通常是
f(i-1,j-1)
的值、f(i-1,j)
的值f(i,j-1)
的值中的一个或多个。相应地,状态转移方程就是找出f(i,j)
与f(i-1,j-1)
、f(i-1,j)
、f(i,j-1)
的关系。
可以根据状态转移方程写出「递归代码」,但是一定要将f(i,j)
的计算结果用一个二维数组缓存,以避免不必要的重复计算。也可以将计算所有f(i,j)
「看成填充二维表格的过程」
题目描述:
?一个机器人从
m×n
的格子的「左上角」出发,它每步要么向下要么向右,直到抵达格子的「右下角」。请计算机器人从左上角到达右下角的路径的数目 输入:m = 3, n = 2
输出:3
从左上角开始,总共有 3 条路径可以到达右下角。
?
机器人每走一步都有「两个选择」,
「一个任务需要多个步骤才能完成,每步面临若干选择」。题目要求计算路径的数目,而不是具体路径,选择「动态规划」解决该问题。
f(i,j)
表示从格子的左上角坐标为(0,0)
的位置出发到达坐标为(i,j)
的位置的「路径数目」。m×n
,那么f(m-1,n-1)
就是问题的解i
等于0时,机器人位于格子「最上面的一行」,机器人不可能从某个位置「向下走一步」到达一个「行号」i
等于0的位置。f(0,j)
等于1f(0,j)
的位置f(0,j-1)
的位置向右走一步」j
等于0时,机器人位于格子「最左边的一列」,机器人不可能从某个位置「向右走一步」到达一个「列号」j
为0的位置。f(i,0)
等于1(i,0)
的位置(i-1,0)
的位置向下走一步」i
、列号j
都大于0时,机器人有「两种方法」可以到达坐标为(i,j)
的位置。(i-1,j)
的位置「向下走一步」(i,j-1)
的位置「向右走一步」f(i,j)= f(i-1,j)+f(i,j-1)
function uniquePaths(m,n){
let dp = new Array(m).fill(0)
.map(()=>
new Array(n).fill(0)
)
return (function helper(i,j,dp){
if(dp[i][j]==0){
if(i==0||j==0){
dp[i][j] =1;
}else {
dp[i][j] = helper(i-1,j,dp) + helper(i,j-1,dp)
}
}
return dp[i][j]
})(m-1,n-1,dp)
}
代码解释
f(i,j)
的结果」。f(i,j)
保存在dp[i][j]
中如果将二维数组dp
看成一个表格,在初始化表格的「第1行(行号为0)和第1列(列号0)之后」,可以按照「从左到右、从上到下」的顺序填充表格的其他位置。
f(0,j)
和f(i,0)
的值都等于1,将表格的第1行和第1列的值都设为1f(1,1)
等于f(0,1)
与f(1,0)
之和f(1,2)
等于f(1,1)
和f(0,2)
之和function uniquePaths(m,n){
let dp = new Array(m).fill(0).map((item,index)=>{
if(index == 0){
// 初始化f(0,j)
return new Array(n).fill(1)
}else {
return new Array(n).fill(0)
}
});
for(let i=1;i<m;i++){
dp[i][0] =1
}
for(let i=1;i<m;i++){
for(let j=1;j<n;j++){
dp[i][j] = dp[i][j-1]+dp[i-1][j]
}
}
return dp[m-1][n-1]
}
在计算f(i,j)
时,只需要计算用到f(i-1,j)
和f(i,j-1)
的值,因此只需要保存标号分别为i-1
和i
的两行就可以。
创建一个只有两行的二维数组dp
,将f(i,j)
保存在dp[i&1][j]
中,那么将空间复杂度到O(n)
。
还可以进一步优化空间效率,只需要创建一个一维数组dp
就可以,在计算f(i,j)
时需要用到f(i-1,j)
和f(i,j-1)
的值。接下来在计算f(i,j+1)
时需要用到f(i-1,j+1)
和f(i,j)
的值。「在计算完f(i,j)
之后,就不再需要f(i-1,j)
的值」。(「正上方」的值)
在二维表格中,f(i,j)
和f(i-1,j)
是「上下相邻」的位置。由于f(i-1,j)
计算出f(i,j)
就不再需要,因此可以「只用一个位置来保存f(i-1,j)
和f(i,j)
的值」。
f(i,j)
之前」保存的是f(i-1,j)
的值f(i,j)
之后」,保存的是f(i,j)
的值?「由于每个位置能够用来保存两个值,因此只需要一个一维数组就能保存表格中的两行」。 ?
function uniquePaths(m,n){
// 数组长度为列数
let dp = new Array(n).fill(1);
for(let i=1;i<m;i++){
for(let j=1;j<n;j++){
dp[j] += dp[j-1]
}
}
return dp[n-1]
}
代码解释:
dp
是一个一维数组,f(i-1,j)
和f(i,j)
都保存在dp[j]
中。dp[j]+=dp[j-1]
可以看成dp[j]= dp[j]+dp[j-1]
dp[j]
保存的是f(i-1,j)
,dp[j-1]
中保存的是f(i,j-1)
f(i,j)
之前」,按照「从左到右」的顺序f(i,j-1)
的值已经计算出来并保存在dp[j-1]
中f(i-1,j)
和f(i,j-1)
的值计算出f(i,j)
之后将结果保存到dp[j]
中dp[j]
中的f(i-1,j)
的值被覆盖,但这个值不在需要,因此覆盖这个值并不会出现任何问题题目描述:
?给定一个包含非负整数的
m x n
网格grid
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为「最小」。
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
因为路径 1→3→1→1→1
的总和最小。
?
机器人每走一步都有「两个选择」,
「一个任务需要多个步骤才能完成,每步面临若干选择」。题目要求计算路径的数目,而不是具体路径,选择「动态规划」解决该问题。
f(i,j)
表示从格子的左上角坐标为(0,0)
的位置(用grid[0][0]
表示)出发到达坐标为(i,j)
的位置(用grid[i][j]
表示)的「路径的数字之和的最小值」。m x n
,那么f(m-1,n-1)
就是问题的解i
等于0时,机器人位于格子的「最上面的一行」,机器人不可能从某个位置「向下走一步」到达一个行号i
等于0的位置。f(0,j)
为「最上面一行从grid[0][0]
开始到grid[0][j]
为止所有格子的值之和」j
等于0时,机器人位于格子的「最左边的一列」,机器人不可能从某个位置「向右走一步」到达一个列号j
等于0的位置。f(i,0)
为「最左边一列从grid[0][0]
开始到grid[i][0]
为止所有格子的值之和」i
、列号j
都大于0时,机器人有两种方法可以到达坐标为(i,j)
的位置(i-1,j)
的位置「向下走一步」(i,j-1)
的位置「向右走一步」f(i,j)= min(f(i-1,j)+f(i,j-1))+grid[i][j]
function minPathSum(grid){
const m = grid.length, n = grid[0].length
// 状态定义:dp[i][j] 表示从 [0,0] 到 [i,j] 的最小路径和
const dp = new Array(m).fill(0)
.map(() =>
new Array(n).fill(0)
)
// 状态初始化
dp[0][0] = grid[0][0]
// 状态转移
for (let i = 0; i < m ; i++) {
for (let j = 0; j < n ; j++) {
if (i == 0 && j != 0) {
dp[i][j] = grid[i][j] + dp[i][j - 1]
} else if (i != 0 && j == 0) {
dp[i][j] = grid[i][j] + dp[i - 1][j]
} else if (i != 0 && j != 0) {
dp[i][j] = grid[i][j] +
Math.min(
dp[i - 1][j],
dp[i][j - 1]
)
}
}
}
return dp[m-1][n-1]
}
在计算f(i,j)
时只需要用到它「上面一行的」f(i-1,j)
,因此实际上只需要保留两行就可以。也就是说,「创建一个只有两行的数组」dp
,将f(i,j)
保存到dp[i&1][j]
中即可。
还可以进一步优化空间,即只需要一个「一维数组」dp
。在计算f(i,j)
时,需要f(i-1,j)
的值。
f(i-1,j)
和f(i,j)
保存到同一个数组dp
的同一个位置dp[j]
中f(i,j)
之前」,dp[j]
保存的是f(i-1,j)
的值f(i-1,j)
的值,「计算f(i,j)
之后」,将f(i,j)
的值保存到dp[j]
中function minPathSum(grid){
let dp = new Array(grid[0].length).fill(0);
dp[0] = grid[0][0];
for(let j=1;j<grid[0].length;j++){
dp[j] = grid[0][j] + dp[j-1]
}
for(let i=1;i<grid.length;i++){
dp[0] +=grid[i][0];
for(let j=1;j<grid[0].length;j++){
dp[j] = grid[i][j] + Math.min(dp[j],dp[j-1])
}
}
return dp[grid[0].length-1]
}
背包问题基本描述如下:给定一组物品,每组物品都有「重量」和「价格」,在「限定的总重量」内如何选择才能使物品的「总价格最高」。
根据物品的特点,背包问题还可以进一步细分。如果「每种物品只有一个」,可以选择将之放入或不放入背包,那么可以将这类问题成为「0-1背包问题」。「0-1背包问题是最基本的背包问题」,其他背包问题通常可以转化为0-1背包问题
i
种物品「最多」有Mi个,也就是「每种物品的数量都是有限」的,那么这类背包问题称为「有界背包问题」(也可以称为「多重背包问题」)。题目描述:
?给定一个非空的正整数数组
nums
,请判断能否将这些数字分成元素和相等的两部分 输入:nums = [1,5,11,5]
输出:true
nums
可以分割成[1, 5, 5]
和[11]
。 ?
如果能够将数组中的数字分成和相等的两部分,那么数组中所有数字的和(记sum
)应该是一个「偶数」。
如果将数组中的每个数字看成物品的重量,也可以这样描述这个问题:能否选择若干物品,使它们刚好放满一个容量为t
的背包?由于每个物品(数字)「最多只能选择一次」,因此这是一个0-1背包问题
。
如果有n
个物品,每步判断一个物品是否要放入背包,也就是说解决这个问题「需要n
步」,并且每步都面临着放入或者不放入「两个选择」,看起来是一个能用「回溯法」解决的问题,但是题目中没有要求列出所有可能的方法。只要求判断是否存在放满背包的方法,所以选择用「动态规划解决」该问题。
f(i,j)
表示能否从前i
个物品(物品标号分别为0,1...i-1)中选择若干物品放满容量为j
的背包」。n
个物品,背包的容量为t
,那么f(n,t)
就是问题的解i
个物品」中选择若干物品放满容量为j
的背包时,对标号为i-1
的物品有「两个选择」i-1
的物品放入背包中」,如果能从前i-1
个物品(物品标号分别为0,1,...i-2
)中选择若干物品放满容量为j-nums[i-1]
的背包(即f(i-1,j-nums[i-1])
为true
),那么f(i,j)
就为true
i-1
的物品放入背包」,如果从前i-1
个物品中选择若干物品放满容量为j
的背包(即f(i-1,j)
为true
),那么f(i,j)
也为true
j
等于0时,即背包的容量为0
」,不论有多少物品,「只要什么物品都不选择,就能使选中的物品总重量为0」,f(i,0)
都为true
i
等于0时,即物品的数量为0
」,肯定无法用0个物品来放满容量大于0的背包,j
大于0时,f(0,j)
都为false
function canPartition(nums){
let sum =nums.reduce((acc,cur)=>acc+cur,0);
if(sum&1==1) return false;
return subsetSum(nums,sum/2)
}
辅助函数
function subsetSum(nums,target){
// 初始化为null
let dp = new Array(nums.length+1).fill(0)
.map(()=>new Array(target+1).fill(null));
return (function helper(nums,dp,i,j){
if(dp[i][j]===null){
if(j==0){
dp[i][j]= true;
}else if(i==0){
dp[i][j] = false
}else {
// 不选择放入
dp[i][j]= helper(nums,dp,i-1,j);
// 选择放入
if(!dp[i][j]&&j>=nums[i-1]){
dp[i][j] = helper(nums,dp,i-1,j-nums[i-1])
}
}
}
return dp[i][j]
})(nums,dp,nums.length,target)
}
代码解释
nums
中所有数字之和sum
,然后调用函数subsetSum
判断能否从数组中选出若干数字使它们的和等于target
(target为sum
的一半)dp
保存f(i,j)
的计算结果。dp[i][j]
等于null
,则表示该位置对应的f(i,j)
还没有计算过如果将二维数组dp
看成一个表格,就可以用「迭代」的代码进行填充。根据状态转移方程,表格的
j
等于0)的所有格子都标为true
i
等于0并且j
大于0)都标为false
i
等于1)开始「从上到下、从左到右」填充表格中每个格子。按nums = [1,5,11,5]
进行数据分析:
第2行的第2个格子对应f(1,1)
,它表示能否从数组的前一个数字(即1)中选出若干数字使和等于1.
f(1,1)
的值等于f(0,1)
的值,而f(0,1)
的为false
f(1,1)
等于f(0,0)
,而f(0,0)
为true
,因此f(1,1)
为true
第2行的第3个格子对应f(1,2)
,它表示能否从数组的前一个数字(即1)中选出若干数字使和等于2.
f(1,2)
的值等于f(0,2)
的值,而f(0,2)
的为false
f(1,1)
等于f(0,1)
,而f(0,0)
为false
,因此f(1,2)
为false
function subsetSum(nums,target){
let m = nums.length;
let n = target;
let dp = new Array(m+1).fill(0)
.map(()=>
new Array(n+1).fill(false)
);
for(let i=0;i<=m;i++){
dp[i][0] = true;
}
for(let i=1;i<=m;i++){
for(let j=1;j<=n;j++){
dp[i][j] = dp[i-1][j];
if(!dp[i][j]&& j>=nums[i-1]){
dp[i][j] = dp[i-1][j-nums[i-1]]
}
}
}
return dp[m][n]
}
题目描述:
?给定正整数数组
conis
表示硬币的面额和一个目标总额t
,请计算凑出总额t
至少需要的硬币数目。「每种硬币可以使用任意多枚」 输入:coins = [1, 2, 5], t = 11
输出:3
11 = 5 + 5 + 1
。 ?
将每种面额的硬币看成一种物品,而将目标总额看成背包的容量,那么这个问题可以等价于求将背包放满时物品的「最少件数」。 这里每种面额的硬币可以使用「任意多次」,因此这个问题不是0-1背包问题
,而是一个「无界背包问题」(也叫完全背包问题)
0-1背包问题
的思路类似f(i,j)
表示用前i
种硬币(coins[0...i-1]
)凑出总额为j
需要的硬币的最少数目」。i-1
的硬币时,f(i,j)
等于f(i-1,j)
(用前i-1
种硬币凑出总额j
需要的最少硬币数目,再加上0枚标号为i-1
的硬币)i-1
的硬币时,f(i,j)=f(i-1,j-coins[i-1])+1
(用前i-1
种硬币凑出总额j-coins[i-1]
需要的最少硬币数目,再加上1枚标号为i-1
的硬币)k
枚标号为i-1
的硬币时,f(i,j) = f(i-1,j-k × coins[i-1]) + k
(用前i-1
种硬币凑出总额j - k × coins[i-1]
需要的最少硬币数目,再加上k
枚标号为i-1
的硬币)f(i,j)=min(f(i-1,j - k × conis[i-1])+k)
k × conis[i-1]≤j
)n
种,目标总额为t
,那么f(n,t)
就是问题的解j
等于0(即总额等于0)时,f(i,0)
等于0,即从前i
种硬币中选出0个硬币,使总额等于0i
等于0且j
大于0
时,即用0种硬币凑出大于0的总额,这是不可能的可以用不同的方法实现状态转移方程
f(i,j)
看成填充一个表格并用二重循环实现function coinChane(conis,target){
let dp = new Array(target+1).fill(target+1);
dp[0]= 0;
for(let coin of coins){
for(let j = target;j>=-1;j--){
for(let k=1;k*coin <= j;k++){
dp[j] = Math.min(dp[j],dp[j-k*coin]+k)
}
}
}
return dp[tareget] > target
?-1
:dp[target]
}
代码解释:
target
,那么硬币的数目一定小于或等于target
target+1
表示某个面额不能用输入的硬币凑出用函数f(i)
表示凑出总额为i
的硬币需要的最少数目。这个函数只有一个参数,表示硬币的总额。如果目标总额为t
,那么f(t)
就是整个问题的解。
为了凑出总额为i
的解,有如下选择
i-conis[0]
的硬币中添加1枚标号为0的硬币,此时f(i)=f(i-coins[0])+1
(在凑出总额为i-coins[0]
的最少硬币数的基础上加1枚标号为0的硬币)i-coins[1]
的硬币中添加1枚标号为1的硬币,此时f(i)=f(i-coins[1])+1
i-coins[n-1]
的硬币中添加1枚标号为n-1
的硬币,此时f(i)
等于f(i-coins[n-1])+1
状态转移方程表示为
f(i) = min(f(i-coins[j])+1)
coins[j]≤i
)由于状态转移方程只有1个参数,因此只需要一个一维数组就可以保存所有f(i)
的计算结果
function coinChange(coins,target){
let dp = new Array(target+1).fill(0)
for(let i=1;i<=target;i++){
dp[i]= target+1;
for(let coin of coins){
if(i>=coin){
dp[i] = Math.min(dp[i],dp[i-coin]+1)
}
}
}
return dp[target]>target?-1:dp[target]
}
?通过记住一些事情来节省时间,这就是动态规划的精髓。 具体来说,如果一个问题的子问题会被我们重复利用,我们则可以考虑使用动态规划 ?
一般来说,动态规划使用一个一维数组或者二维数组来保存状态
动态规划做题步骤
dp(i)
应该表示什么(二维情况:dp(i)(j));dp(i)
和 dp(i-1)
的关系得出状态转移方程;dp(0)
?分为几步
?
运用「数学归纳思想」解决问题
「分享是一种态度」。
参考资料:剑指offer/leetcode官网/学习JavaScript数据结构与算法第3版
「全文完,既然看到这里了,如果觉得不错,随手点个赞和“在看”吧。」