此文章中的题目都是Leetcode上 子序列/子串 问题相关的汇总, 点击相应标题可以跳转到该问题。
持续更新中 ...
Leetcode 53. 最大子序和
简单题 动态规划
此题存在明显的递推关系，因此可以用通用的动态规划法来做。
时间复杂度: O(n) 【具体来说是2n，dp过程是n，求数组的max也是n】
空间复杂度: O(n) 【dp辅助数组是n】
var maxSubArray = function(nums) {
/**
* dp[i]代表第i个数结尾的子数组的最大和
* 因此当dp[i-1] < 0时，dp[i]最大值是nums[i]
* dp[i-1] > 0时，dp[i]最大值是nums[i]+dp[i-1]
* 返回的总最大值是max(dp)
*/
const len = nums.length
if(len === 0) {
return
}
if(len === 1) {
return nums[0]
}
const dp = new Array(len)
dp[0] = nums[0]
for(let i=1;i<len;i++) {
dp[i] = dp[i-1]<0 ? nums[i] : nums[i] + dp[i-1]
}
return Math.max.apply(null, dp)
};
进一步发现辅助数组dp可以去除，因为dp[i]只依赖dp[i-1]的结果，我们只需要缓存上一个结果就行了，求max也可以在迭代过程中求。
时间复杂度: O(n)
空间复杂度: O(1)
var maxSubArray = function(nums) {
const len = nums.length
if(len === 0) {
return
}
if(len === 1) {
return nums[0]
}
let num = 0, max = -Infinity
for(let i=0;i<len;i++) {
num = num < 0 ? nums[i] : nums[i] + num
max = num > max ? num : max
}
return max
};
Leetcode 647. 回文子串
中等题 动态规划
主要点在回文的状态转移方程：dp[i][j] = (s[i] === s[j]) && (j-i<=1 || dp[i+1][j-1])
迭代时候需要注意，dp的某一项依赖它左下角的值(i+1,j-1)，并且dp是一个上三角形，对角线的值可以独立求出，因此遍历应该从对角线出发，从下到上，由左及右。
var countSubstrings = function(s) {
/**
* dp[i][j] 代表i到j是否为回文子串
* dp[i][j] 是回文子串 -> 一个字母时成立，两个字母时两个字母相同成立，三个以上字母时首尾字母相同，并且中间也是回文串<->dp[i+1][j-1]=true
* dp[i][j] = (s[i] === s[j]) && (j-i<=1 || dp[i+1][j-1])
*/
const len = s.length
let res = 0
const dp = Array(len).fill(0).map(item => Array(len))
for(let j=0;j<len;j++) {
for(let i=j;i>=0;i--) {
if((s[i] === s[j]) && (j-i<=1 || dp[i+1][j-1])) {
dp[i][j] = true
res++
}
}
}
return res
};
Leetcode 3. 无重复字符最长子串
中等题 动态规划 滑动窗口
假设使用暴力法：n长度的数组，子数组数量为n(n-1)/2，判断一个子数组是否有重复字符则需要O(n)的时间复杂度，因此总体复杂度为O(n^3)。
用动态规划来优化的话，设dp[i]为以i为结尾的无重复最长字符子串的长度。
则如果str[i]没有出现过的话，dp[i] = dp[i-1] + 1;
str[i]出现过，设与str[i]最近的同一个字符为str[j]，
i - j <= dp[i-1]，则j出现在i-1的无重复最长字符子串中，且(j,i]中没有重复字符，所以以i为结尾的无重复字符子串的长度是 i - j，dp[i] = i - j。
i - j > dp[i-1]，那么显而易见dp[i] = dp[i-1] + 1;
const lengthOfLongestSubstring = function(s) {
const len = s.length
if (!len) {
return 0
}
const dist = {}
const dp = new Array(len)
dp[0] = 1
dist[s[0]] = 0
for(let i=1;i<len;i++) {
if(!(s[i] in dist)) {
dp[i] = dp[i-1]+1
dist[s[i]] = i
} else {
distance = i - dist[s[i]]
dist[s[i]] = i
if (distance <= dp[i-1]) {
dp[i] = distance
} else {
dp[i] = dp[i-1]+1
}
}
}
return Math.max.apply(null, dp)
};
题解还提及到滑动窗口的解法，明天再看看。
Leetcode 128. 最长连续序列
困难题 哈希表
这道题其实用js来实现并不算难，题目要求复杂度O(n)，其实只要借助自带的Set就能方便的实现这一点。
var longestConsecutive = function(nums) {
let longgest = 0
let tmp = 0
const hashSet = new Set(nums)
for(let num of nums) {
if(!hashSet.has(num-1)) {
tmp = 0
for(let i = num; hashSet.has(i); i++) {
tmp++
}
longgest = Math.max(longgest, tmp)
}
}
return longgest
};
Leetcode 76. 最小覆盖子串
困难题 滑动窗口法
滑动窗口法在子串问题中有很多采用此方法。
var minWindow = function(s, t) {
/**
* 滑动窗口法
*/
let start, minLen = Infinity // 最小串的起始和长度
const needs = {} // t字符串的哈希表
const win = {} // 目前窗口的哈希表
for(let c of t) {
needs[c] = needs[c]?needs[c]+1:1
}
let match = 0
let right = 0, left = 0
// 执行right膨胀计划
while(right < s.length) {
// 如果right字符在need哈希表中存在的话，win哈希表计数加一，如果win哈希表值和need哈希表值相等(不能是大于等于,注意)，则匹配值match加一
if(s[right] in needs) {
win[s[right]] = win[s[right]] ? win[s[right]]+1 : 1
if(win[s[right]] === needs[s[right]]) {
match++
}
}
// 如果匹配率match和need长度一致，窗口中包含了s所有字母。
// 执行left收缩计划
while(match === Object.keys(needs).length) {
// 先检查是否可以更新最小串
if(right - left + 1 < minLen) {
minLen = right - left + 1
start = left
}
if(s[left] in needs) {
win[s[left]] = win[s[left]] ? win[s[left]]-1 : 0
if(win[s[left]] < needs[s[left]]) {
match--
}
}
left++
}
right++
}
return minLen===Infinity?'':s.substr(start,minLen)
};
