一、反转字符串
2020.09.01
No.344 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=344 lang=javascript
*
* [344] 反转字符串
*/
// @lc code=start
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
return s.reverse()
};
方案二：
/*
* @lc app=leetcode.cn id=344 lang=javascript
*
* [344] 反转字符串
*/
// @lc code=start
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
let i = 0,
x = s.length -1;
while (i < x) {
[s[i], s[x]] = [ s[x], s[i] ]
I++
x--
}
};
有三种解法：1、利用本身的reverse()的api；2、利用双指针进行输入输出交换；3、利用递归进行输入输出交换
2020.09.02
No.345 反转字符串中的元音字母
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1：
输入："hello"
输出："holle"
示例 2：
输入："leetcode"
输出："leotcede"
提示：
元音字母不包含字母 "y" 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：
/*
* @lc app=leetcode.cn id=345 lang=javascript
*
* [345] 反转字符串中的元音字母
*/
// @lc code=start
/**
* @param {string} s
* @return {string}
*/
var reverseVowels = function(s) {
let p1 = 0,
p2 = s.length -1,
strArr = s.split('');
const reg = /[aeiou]/I;
while(p1 < p2) {
if(reg.test(strArr[p1]) && reg.test(strArr[p2])) {
[strArr[p1],strArr[p2]] = [strArr[p2],strArr[p1]]
p1++;
p2--;
} else if(!reg.test(strArr[p1])) {
p1++;
} else if(!reg.test(strArr[p2])) {
p2--;
}
}
return strArr.join('');
};
思路比较清晰，就是首尾双指针进行遍历替换
2020.09.03
No.541 反转字符串-ii
给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
提示：
该字符串只包含小写英文字母。
给定字符串的长度和 k 在 [1, 10000] 范围内。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=541 lang=javascript
*
* [541] 反转字符串 II
*/
// @lc code=start
/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var reverseStr = function(s, k) {
let sArr = s.split(''),
arrs = [];
if(sArr.length < k){
arrs.push(sArr.reverse().join(''));
} else {
while(sArr.length >= k) {
let arr = sArr.splice(0, 2*k);
arrs.push(arr);
}
sArr.length > 0 && (arrs = [...arrs,sArr]);
for(let i =0; i< arrs.length; i++) {
// 在这里对arrs[i]的每项进行前k项调换
arrs[i] = arrs[i].splice(0, k).reverse().concat(arrs[i]).join('');
}
}
sArr=[...arrs];
return sArr.join('');
};
方案二：
/*
* @lc app=leetcode.cn id=541 lang=javascript
*
* [541] 反转字符串 II
*/
// @lc code=start
/**
* @param {string} s
* @param {number} k
* @return {string}
*/
var reverseStr = function(s, k) {
let strArr = s.split('');
let reverse = (start, end) => {
let temp = null;
while (start < end) {
temp = strArr[start];
strArr[start] = strArr[end];
strArr[end] = temp;
start++;
end--;
}
};
for (let i = 0; i < s.length; i += 2 * k) {
reverse(i, i + k - 1);
}
return strArr.join('');
};
主要是两种思路：一种是先2k分片再对k进行操作；另一种是找寻数学规律，进行异步操作分片
2020.09.04
No.557 反转字符串
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
提示：
在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-words-in-a-string-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=557 lang=javascript
*
* [557] 反转字符串中的单词 III
*/
// @lc code=start
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function(s) {
return s.split(' ').map(item => item.split('').reverse().join('')).join(' ');
};
方案二：
/*
* @lc app=leetcode.cn id=557 lang=javascript
*
* [557] 反转字符串中的单词 III
*/
// @lc code=start
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function(s) {
const ret = [];
const length = s.length;
let i = 0;
while (i < length) {
let start = I;
while (i < length && s.charAt(i) != ' ') {
I++;
}
for (let p = start; p < i; p++) {
ret.push(s.charAt(start + i - 1 - p));
}
while (i < length && s.charAt(i) == ' ') {
I++;
ret.push(' ');
}
}
return ret.join('');
};
有两种解法：1、利用本身的reverse和split的api；2、利用双指针或循环遍历进行分割要求匹配后反转；
2020.09.07
No.926 将字符串翻转到单调递增
如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是单调递增的。
我们给出一个由字符 '0' 和 '1' 组成的字符串 S，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。
返回使 S 单调递增的最小翻转次数。
示例 1：
输入："00110"
输出：1
解释：我们翻转最后一位得到 00111.
示例 2：
输入："010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。
示例 3：
输入："00011000"
输出：2
解释：我们翻转得到 00000000。
提示：
1 <= S.length <= 20000
S 中只包含字符 '0' 和 '1'
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flip-string-to-monotone-increasing
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=926 lang=javascript
*
* [926] 将字符串翻转到单调递增
*/
// @lc code=start
/**
* @param {string} S
* @return {number}
*/
var minFlipsMonoIncr = function(S) {
let left = [],
right = [],
n = 0;
// 从左向右遍历，记录到字符串这个位置含有1的个数，全1数为left[S.length-1]的值
for( let i = 0; i < S.length; i++) {
if(S[i] == '1') n++;
left[i] = n;
}
// 从右向左遍历，记录到字符串这个位置含有0的个数，全0数为right[0]的值
n = 0; // 重置
for(let i = S.length -1; i >= 0;i--) {
if(S[i] == '0') n++;
right[i] = n;
}
// 移动窗口，选出到i位置包含0和1个数的和的最小值，即左边0右边1的最小值
n = Infinity;
for(let i = 0;i< S.length-1; i++) {
n = Math.min(left[i]+right[i+1],n);
}
// 返回 左边0右边1 全0 全1 三者的最小值
return Math.min(n, left[S.length-1], right[0])
};
方案二：
/*
* @lc app=leetcode.cn id=926 lang=javascript
*
* [926] 将字符串翻转到单调递增
*/
// @lc code=start
/**
* @param {string} S
* @return {number}
*/
const { min } = Math;
var minFlipsMonoIncr = function(S) {
let dp = Array.from({ length: S.length + 1 }).map(item => [0, 0]);
dp[0][0] = dp[0][1] = 0;
for (let i = 1; i <= S.length; i++) {
if (S[i - 1] === '0') {
dp[i][0] = dp[i - 1][0];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
} else {
dp[i][0] = dp[i - 1][0] + 1;
dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]);
}
}
return min(dp[S.length][0], dp[S.length][1]);
};
有两种解法：1、利用左右指针向中间遍历的思路，维护一个数据结构数组，这个数据结构数组存储 arr=[位置(存放到该位置为0或为1的个数)]，利用这个数据结构获取 全0 全1 左0右1的最小值；2、动态规划，维护一个二维数组，进行状态转移；
总结：
- 翻转字符串类型的常见思路还是利用左右指针的向中间靠拢来进行对应的反转，这个中间可能是中点，也可能是其他位置；
- 可以利用已有的相关api进行操作，常见的有reverse和split、slice等进行字符串的操作
二、回文串
2020.09.08
No.336 回文对
给定一组 互不相同 的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例 1：
输入：["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2：
输入：["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为 ["battab","tabbat"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=336 lang=javascript
*
* [336] 回文对
*/
// @lc code=start
/**
* @param {string[]} words
* @return {number[][]}
*/
var palindromePairs = function(words) {
let r=[];
// 优化这里存储的数据结构，这里的存储是O(words.length^2*拼接后单词的长度)
for(let i = 0;i < words.length; i++) {
for(let j = i+1; j < words.length; j++) {
isReverse(words[i] + words[j]) && r.push([i,j]);
isReverse(words[j] + words[i]) && r.push([j,i]);
}
}
function isReverse(s) {
let p1 = 0,
p2 = s.length - 1;
while(p1 < p2) {
if( s[p1] != s[p2] ) return false;
p1++;
p2--;
}
return true;
}
return r;
};
方案二：
/*
* @lc app=leetcode.cn id=336 lang=javascript
*
* [336] 回文对
*/
// @lc code=start
/**
* @param {string[]} words
* @return {number[][]}
*/
var palindromePairs = function(words) {
//创建字典树中的节点对象
function createNode() {
var obj = {};
obj.chi = new Array(26).fill(0);
obj.flag = -1;
return obj;
};
var tree = new Array();
tree.push(createNode());
var n = words.length;
for(let i = 0; i < n; i++) {
insert(words[i], i); //将字符串数组中的所有字符串先加入字典树
};
var ret = new Array();
for(let i = 0; i < n; i++) {
var m = words[i].length;
for(let j = 0; j <= m; j++) {
if(isPalindrome(words[i], j, m - 1)) { //如果字符串i的j至m-1位为回文串
var leftId = findWord(words[i], 0, j - 1); //需要在字典树中寻找是否存在字符串i倒序的字符串
if (leftId != -1 && leftId != i) {
ret.push([i, leftId]);
}
}
if(j !=0 && isPalindrome(words[i], 0, j - 1)) {
var rightId = findWord(words[i], j, m - 1);
if(rightId != -1 && rightId != i) {
ret.push([rightId, i]);
}
}
}
};
return ret;
//将每一个字符串插入到字典树当中
function insert(s, id) {
var len = s.length, add = 0;
for(let i = 0; i < len; i++) {
var x = s[i].charCodeAt() - 'a'.charCodeAt();
if(tree[add].chi[x] == 0) {
tree.push(createNode());
tree[add].chi[x] = tree.length - 1;
}
//tree[add].ch[x]保存着子节点在tree中的位置；同时，不等于0说明当前字母与节点所代表的字母相等
add = tree[add].chi[x];
}
tree[add].flag = id; //标记下标为add的节点保存了第id个字符串
}
//判断字符串是否为回文
function isPalindrome(s, left, right) {
var len = right - left + 1;
for(let i = 0; i < len / 2; i++) {
if(s[left + i] != s[right - i]) {
return false;
}
}
return true;
}
//在字典树中寻找判断是否存在某字符串的倒序
function findWord(s, left, right) {
var add = 0;
for(let i = right; i >= left; i--) {
var x = s[i].charCodeAt() - 'a'.charCodeAt();
if(tree[add].chi[x] == 0) {
return -1;
}
add = tree[add].chi[x];
}
return tree[add].flag; //节点的flag在insert函数中保存了字符串在字符串数组中的下标
}
};
方案三：
/*
* @lc app=leetcode.cn id=336 lang=javascript
*
* [336] 回文对
*/
// @lc code=start
/**
* @param {string[]} words
* @return {number[][]}
*/
var palindromePairs = function (words) {
let n = words.length,
_result = [],
map = new Map()
for (let i = 0; i < n; ++i) {
// 生成倒序字符字符map
const str = words[i].split('').reverse().join('')
map.set(str, i)
}
for (let i = 0; i < n; i++) {
let word = words[I],
m = words[i].length
if (m == 0) continue
for (let j = 0; j <= m; j++) {
// 前缀片段为回文，则验证后缀片段是否存在与之匹配的回文
if (check(word, j, m - 1)) {
let leftId = findWord(word, 0, j - 1)
if (leftId !== -1 && leftId !== i) {
_result.push([i, leftId])
}
}
// 同理，后缀片段为回文，则验证前缀片段是否可以匹配到回文
if (j !== 0 && check(word, 0, j - 1)) {
let rightId = findWord(word, j, m - 1)
if (rightId !== -1 && rightId !== i) {
_result.push([rightId, I])
}
}
}
}
function check(s, left, right) {
let len = right - left + 1
for (let i = 0; i < len / 2; i++) {
if (s.charAt(left + i) !== s.charAt(right - i)) {
return false
}
}
return true
}
function findWord(s, left, right) {
return map.has(s.substring(left, right + 1))
? map.get(s.substring(left, right + 1))
: -1
}
return _result
}
有三种解法：1、暴力解法：循环遍历字符串数组的匹配判断是否回文对，然后输出，容易想到，但是时空复杂度太差；2、字典树，对于存储结构那里进行了数据结构的优化；3、前缀+后缀或者叫以中心截取判断，利用回文字符的特点对回文中心进行分拆，然后判断输出
2020.09.09
No.564 寻找最近的回文数
给定一个整数 n ，你需要找到与它最近的回文数（不包括自身）。
“最近的”定义为两个整数差的绝对值最小。
示例 1:
输入: "123"
输出: "121"
注意:
n 是由字符串表示的正整数，其长度不超过18。
如果有多个结果，返回最小的那个。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-closest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=564 lang=javascript
*
* [564] 寻找最近的回文数
*/
// @lc code=start
/**
* @param {string} n
* @return {string}
*/
var nearestPalindromic = function(n) {
let r = [],
len = n.length,
min = '',
c = 13; // 截取中间的位数
if(len < c) {
let [r1, r2] = getR(n);
getMin(r1,r2,n)
return min;
} else {
let m = reverse(n,len-c).slice(len-c,c),
l = reverse(n,len-c).slice(0,len-c),
r = reverse(n,len-c).slice(c,len);
let [r1, r2] = getR(m);
getMin(r1,r2,m);
return l+min+r;
}
// 获取最小值，也是最终返回的结果
function getMin(r1,r2,n) {
if(Math.abs(r1-n) < Math.abs(r2-n)) {
min= r1;
} else if(Math.abs(r1-n) == Math.abs(r2-n)) {
min= Math.min(r1,r2)+''
} else {
min= r2;
}
}
// 获取距离n最近的两个回文数的数组r
function getR(n) {
// 寻找第一个不是0的数
let str = ( n[0] == '0' ? n.slice(1,n.length-1) : n );
str = Number(str);
for(let i=1;; i++) {
if(isReverse(str+i)){
r.push(`${str+i}`);
}
if(isReverse(str-i)) {
r.push(`${str-i}`);
};
if(r.length >= 2) break;
}
r = r.map(i=>n[0] == '0' ? i = '0' + i + '0' : i)
return r;
}
// 判断是否是回文数
function isReverse(s) {
s += '';
let l = 0,
r = s.length - 1;
while(l<r) {
if(s[l] != s[r]) return false;
l++;
r--;
}
return true;
}
// 反转回文数
function reverse(s,l) {
s += '';
let p1 = 0,
p2 = len -1,
arr=s.split('');
for(let i=0;i<l;i++) {
if(arr[p1+i] != arr[p2-i]) arr[p2-i] = arr[p1+i];
}
return arr.join('');
}
};
方案二：
/*
* @lc app=leetcode.cn id=564 lang=javascript
*
* [564] 寻找最近的回文数
*/
// @lc code=start
/**
* @param {string} n
* @return {string}
*/
var nearestPalindromic = function (n) {
let palindromicList = ["",""] //初始化数组，用于存放 小于n的最近回文数 和 大于n的最近回文数
let nearest = "" //最近回文数
let lenN = n.length
let halfN = ""
let typeN = false //不是回文数
if (Number(n) < 11) { //个位数需要单独处理
nearest = String(Number(n) - 1)
return nearest
} else if (Number(n) == 11) {
nearest = "9"
return nearest
}
if (n.split("").reverse().join("") == n) {
typeN = true //n本身就是回文数
}
let isEvenNum = lenN % 2 == 0 //n是否为偶数
if (isEvenNum) { //长度为偶数位，则截取 [0,lenN/2) 的元素
halfN = n.slice(0, lenN / 2)
} else { //长度为奇数位，则截取 [0,Math.ceil(lenN/2))的元素
halfN = n.slice(0, Math.ceil(lenN / 2))
}
let lenHalfN = halfN.length
for (let L = Number(halfN) - 1, R = Number(halfN); L >= -1; L--, R++) { //halfN作为起始点 ，左右两边同时查找
let revsL = ""
let strL = Math.abs(L).toString()
let lenStrL = strL.length
if (isEvenNum) {
revsL = strL.split("").reverse().join("")
} else {
revsL = strL.substring(0, lenStrL - 1).split("").reverse().join("")
}
let palindromicL = strL + revsL.toString()
if (palindromicL.length < lenN) { //处理1000 ---> 999 等 字符串长度减少的情况，需要补1位
palindromicL += strL[0] //999 --> 9999
}
if (palindromicL != n) {
if ((Math.abs(palindromicL - n)) < (Math.abs(palindromicList[0] - n))) {
palindromicList[0] = palindromicL
}
}
let revsR = ""
let strR = R.toString()
let lenStrR = strR.length
if (isEvenNum) {
revsR = strR.split("").reverse().join("")
if (lenStrR > lenHalfN) {
revsR = revsR.substr(1)
}
} else {
revsR = strR.substring(0, lenStrR - 1).split("").reverse().join("")
if (revsR.length == 0) { //处理 个位数情况
revsR = strR
} else if (lenStrR > lenHalfN) { //处理 999 + 1 = 1000 等 字符串长度增加的情况，需要去掉1位
revsR = revsR.substr(1) // 0001 --> 001
}
}
let palindromicR = strR + String(revsR)
if ((Math.abs(palindromicR - n) < Math.abs(n - palindromicList[0]) && (palindromicR < n))) {
palindromicList[0] = palindromicR
continue
}
if (palindromicR != n) {
palindromicList[1] = palindromicR
break
}
}
if (palindromicList[1] - n < n - palindromicList[0]) {
nearest = palindromicList[1]
} else {
nearest = palindromicList[0]
}
return nearest
};
有两种解法：1、暴力解法：直接以该字符串为中心进行左右范围的查询，获取最近的两个回文数，js存在最大数值，因而在处理的时候需要对数值进行一定的操作，这种方法比较好想，但是时间复杂度较大；2、分析数学表达式，对个别边界进行细节处理，获取最终的结果
2020.09.10
No.647 回文子串
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
输入的字符串长度不会超过 1000 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindromic-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=647 lang=javascript
*
* [647] 回文子串
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
let r = [],
len = s.length;
for(let i=1;i<=len;i++) {
getTemp(i).forEach(a => isReverse(a) && r.push(a))
}
return r.length;
// 移动窗口获取所有子串
function getTemp(n) {
let start = 0,
end = start + n,
temp = []; // 用于存放截取的子串
for(let i=0;i< len + 1 - n;i++,start++,end++) {
temp.push(s.slice(start,end))
}
return temp;
}
function isReverse(s) {
let p1=0,p2=s.length-1;
while(p1<p2) {
if(s[p1] != s[p2]) return false;
p1++;
p2--;
}
return true;
}
};
方案二：
/*
* @lc app=leetcode.cn id=647 lang=javascript
*
* [647] 回文子串
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
const n = s.length;
let ans = 0;
for (let i = 0; i < 2 * n - 1; ++i) {
let l = i / 2, r = i / 2 + i % 2;
while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
--l;
++r;
++ans;
}
}
return ans;
};
方案三：
/*
* @lc app=leetcode.cn id=647 lang=javascript
*
* [647] 回文子串
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
const countSubstrings = (s) => {
const len = s.length;
let count = 0;
const dp = new Array(len);
for (let j = 0; j < len; j++) {
for (let i = 0; i <= j; i++) {
if (s[i] == s[j] && (j - i <= 1 || dp[i + 1])) {
dp[i] = true;
count++;
} else {
dp[i] = false;
}
}
}
return count;
};
方案四：
/*
* @lc app=leetcode.cn id=647 lang=javascript
*
* [647] 回文子串
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
let n = s.length;
let t = ['$', '#'];
for (let i = 0; i < n; ++i) {
t.push(s.charAt(i));
t.push('#');
}
n = t.length;
t.push('!');
t = t.join('');
const f = new Array(n);
let iMax = 0, rMax = 0, ans = 0;
for (let i = 1; i < n; ++i) {
// 初始化 f[i]
f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
// 中心拓展
while (t.charAt(i + f[i]) == t.charAt(i - f[i])) {
++f[I];
}
// 动态维护 iMax 和 rMax
if (i + f[i] - 1 > rMax) {
iMax = I;
rMax = i + f[i] - 1;
}
// 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
ans += Math.floor(f[i] / 2);
}
return ans;
};
有四种解法：1、暴力解法：将子串截取，获取所有子串后进行判断是否回文子串，然后获取总数量，此时时间复杂度为O(n3)；2、中心拓展：基于暴力解法的优化，这里获取子串可以通过遍历可能的查找中心，然后中心向两边扩展，进行获取总数量，此时时间复杂度为O(n2)；3、动态规划：将字符串打撒，对每个字符进行组合匹配，将每个dp[i]和dp[i-1]进行转化，区分1个字符和2个字符以及大于2个字符的组合匹配，时间复杂度为O(n^2)，空间复杂度可以优化为O(n)；4、Manacher：利用填空，将奇字符串和偶字符串都转化为奇字符串，这样就只有一个中心，然后以不同半径进行中心扩展，利用最大子串覆盖半径进行拓展，这样可以将查询中心的时间进行优化而不用盲目遍历，时间复杂度为O(n)
2020.09.11
No.680 验证回文字符串-ii
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba"
输出: True
示例 2:
输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=680 lang=javascript
*
* [680] 验证回文字符串 Ⅱ
*/
// @lc code=start
/**
* @param {string} s
* @return {boolean}
*/
var validPalindrome = function(s) {
let n = 0; // 闭包应用，记录一个位置
if(!isReverse(s)) {
let arr1 = s.split(''),
arr2 = s.split('');
arr1.splice(n,1);
arr2.splice(s.length - 1 - n,1);
return (isReverse(arr1.join('')) || isReverse(arr2.join('')));
}
return true;
function isReverse(s) {
let p1 = 0,
p2 = s.length - 1;
while(p1 < p2) {
if(s[p1] != s[p2]) return false;
n++;
p1++;
p2--;
};
return true;
}
};
主要是利用首尾指针进行中间靠拢查找，本题目是验证回文串的变种
总结：
- 回文串方案主要还是利用的双指针查找的方案，这里的查找方案可以进行优化，如前缀后缀法、中心扩展法、Manacher等；
- 对于自己构造的字符串生成回文串的方案可以采用动态规划以及数学表达式通项公式d
三、最长问题
2020.09.14
No.3 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=3 lang=javascript
*
* [3] 无重复字符的最长子串
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let max = 0, index = 0;
for(let i=0,j=0;j<s.length;j++) {
index = s.slice(i,j).indexOf(s[j]);
if(isRepeat(s.slice(i,j))) {
i += index + 1;
}
max = Math.max(max, j - i + 1)
}
return max;
function isRepeat(s) {
return s.length == Array.from(new Set(s.split(''))).length;
}
};
方案二：
/*
* @lc app=leetcode.cn id=3 lang=javascript
*
* [3] 无重复字符的最长子串
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let arr = [], max = 0
for(let i = 0; i < s.length; i++) {
let index = arr.indexOf(s[i])
if(index !== -1) {
arr.splice(0, index+1);
}
arr.push(s.charAt(i))
max = Math.max(arr.length, max)
}
return max
};
方案三：
/*
* @lc app=leetcode.cn id=3 lang=javascript
*
* [3] 无重复字符的最长子串
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let map = new Map(), max = 0
for(let i = 0, j = 0; j < s.length; j++) {
if(map.has(s[j])) {
i = Math.max(map.get(s[j]) + 1, i)
}
max = Math.max(max, j - i + 1)
map.set(s[j], j)
}
return max
};
主要是利用滑动窗口进行字符串选择匹配，这里可以使用字符串、数组以及map去做数据结构查找
2020.09.15
No.14 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=14 lang=javascript
*
* [14] 最长公共前缀
*/
// @lc code=start
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if(strs.length == 0) return '';
let r = strs[0];
strs.forEach(str => {
r = commonStr(r,str)
});
return r;
function commonStr(str1, str2) {
let len = Math.min(str1.length, str2.length),
str = '';
for(let i=0; i<len; i++) {
if(str1[i] == str2[I]){
str += str1[I];
} else {
return str; // 有不同的不再往后比较
}
}
return str;
}
};
方案二：
/*
* @lc app=leetcode.cn id=14 lang=javascript
*
* [14] 最长公共前缀
*/
// @lc code=start
/**
* @param {string[]} strs
* @return {string}
*/
const longestCommonPrefix = (strs) => {
if (!strs || strs.length === 0) return ''
let lcp = '' // 共同的前缀字符串
let index = 0 // 指针
for (const c of strs[0]) { // 遍历第一个字符串的每个字符
for (let i = 1; i < strs.length; i++) { // 遍历剩余的字符串们
if (index >= strs[i].length || strs[i][index] !== c) {
return lcp
}
}
lcp += c
index++
}
return lcp
}
方案三：
/*
* @lc app=leetcode.cn id=14 lang=javascript
*
* [14] 最长公共前缀
*/
// @lc code=start
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if(!strs || strs.length == 0){
return '';
}
strs.sort();
let first = strs[0];
let end = strs[strs.length-1];
// 此处 end.match(eval('/^'+first+'/')) 可以换成
// end.indexOf(first) == 0，是一样的
if(first == end || end.match(eval('/^'+first+'/'))){
return first;
}
for(let i = 0;i < first.length;i++){
if(first[i] != end[I]){
return first.substring(0,i);
}
}
};
方案四：
/*
* @lc app=leetcode.cn id=14 lang=javascript
*
* [14] 最长公共前缀
*/
// @lc code=start
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
return lCPrefixRec(strs)
};
// 若分裂后的两个数组长度不为 1，则继续分裂
// 直到分裂后的数组长度都为 1，
// 然后比较获取最长公共前缀
function lCPrefixRec(arr) {
let length = arr.length
if(length === 1) {
return arr[0]
}
let mid = Math.floor(length / 2),
left = arr.slice(0, mid),
right = arr.slice(mid, length)
return lCPrefixTwo(lCPrefixRec(left), lCPrefixRec(right))
}
// 求 str1 与 str2 的最长公共前缀
function lCPrefixTwo(str1, str2) {
let j = 0
for(; j < str1.length && j < str2.length; j++) {
if(str1.charAt(j) !== str2.charAt(j)) {
break
}
}
return str1.substring(0, j)
}
方案五：
/*
* @lc app=leetcode.cn id=14 lang=javascript
*
* [14] 最长公共前缀
*/
// @lc code=start
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
// 初始化 Trie 树
let trie = new Trie()
// 构建 Trie 树
for(let i = 0; i < strs.length; i++) {
if(!trie.insert(strs[i])) return ""
}
// 返回最长公共前缀
return trie.searchLongestPrefix()
};
// Trie 树
var Trie = function() {
this.root = new TrieNode()
};
var TrieNode = function() {
// next 放入当前节点的子节点
this.next = {};
// 当前是否是结束节点
this.isEnd = false;
};
Trie.prototype.insert = function(word) {
if (!word) return false
let node = this.root
for (let i = 0; i < word.length; i++) {
if (!node.next[word[i]]) {
node.next[word[i]] = new TrieNode()
}
node = node.next[word[I]]
}
node.isEnd = true
return true
};
Trie.prototype.searchLongestPrefix = function() {
let node = this.root
let prevs = ''
while(node.next) {
let keys = Object.keys(node.next)
if(keys.length !== 1) break
if(node.next[keys[0]].isEnd) {
prevs += keys[0]
break
}
prevs += keys[0]
node = node.next[keys[0]]
}
return prevs
}
本题解法较多，常见的主要有五种：1、横向比较，获取字符串，相邻两个互相比较，得到最小子串；2、纵向比较，维护一个指针，对所有字符串的同一位置进行纵向比较；3、先按字符排序，每个字符的位置只需比较首尾是否相同，最后收到一个字符串中，算是纵向比较的一种优化；4、分治算法，利用分治，对两两比较进行分组，优化比较时长；5、Trie树，维护一个Trie树，对最长公共前缀进行输出
2020.09.16
No.32 最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=32 lang=javascript
*
* [32] 最长有效括号
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let left = [],
right = [],
r = []; // 将可以匹配的位置收到一个数组中
// 遍历，将'('和')'的位置分别记录在left数组和right数组中
for(let i = 0; i < s.length; i++) {
if(s[i] == '(') {
left.push(i);
} else if(s[i] == ')') {
right.push(i)
}
}
// 对left数组中的位置和right数组中的位置进行临近的配对，配对要求右边数组的值要比左边数组的值大
for(let i=left.length-1; i>=0; i--) {
for(let j=0; j<right.length; j++) {
if(left[i] < right[j]) {
r.push(left[i],right[j]);
left.splice(i,1);
right.splice(j,1);
continue;
}
}
};
r.sort((a,b)=>a-b);
// 获取r中最长连续数字
let pos = [],
max = 0;
for(let i=0;i<=r.length-1;i++) {
if(r[i+1] - r[i] != 1) {
pos.push(I+1)
}
}
pos.unshift(0);
// 分割位置数组的gap进行最大值获取，取得的最大值就是最长有效括号
for(let i=0;i<pos.length-1;i++) {
if(max < pos[i+1] - pos[i]) max = pos[i+1] - pos[I];
}
return max;
};
方案二：
/*
* @lc app=leetcode.cn id=32 lang=javascript
*
* [32] 最长有效括号
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function (s) {
const stack = [-1]
let ans = 0
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
stack.push(i)
} else {
stack.pop()
if (stack.length === 0) {
// 加入新边界
stack.push(i)
} else {
ans = Math.max(ans, i - stack[stack.length - 1])
}
}
}
return ans
}
方案三：
/*
* @lc app=leetcode.cn id=32 lang=javascript
*
* [32] 最长有效括号
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let len = s.length,
_result = 0;
if (len === 0) return _result
let dp = Array(len).fill(0);
for (let i = 1; i < s.length; i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
}
else if (
i - dp[i - 1] > 0 &&
s.charAt(i - dp[i - 1] - 1) == '('
) {
dp[i] = dp[i - 1] +
((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0)
+ 2;
}
_result = Math.max(_result, dp[I]);
}
}
return _result
};
方案四：
/*
* @lc app=leetcode.cn id=32 lang=javascript
*
* [32] 最长有效括号
*/
// @lc code=start
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let temp = s,
reg = new RegExp(/(\((1*)\))/ig);
while(reg.test(temp)){
temp = temp.replace(reg,1+'$2');
}
let arr = temp.split(/[\(\)]/ig);
return arr.reduce((total,item,index)=>{
let len = item.length*2;
total = total > len ? total : len;
return total;
},0)
};
本题解法较多，主要有4种方法：1、利用左右括号的位置进行配对输出最大值；2、对1中的匹配过程利用栈的出入进行数值的计算；3、动态规划，找到通项公式进行匹配；4、正则替换，将符合的进行替换，获取对应的个数
2020.09.17
No.521 最长特殊序列I
给你两个字符串，请你从这两个字符串中找出最长的特殊序列。
「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。
输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。
示例 1：
输入: "aba", "cdc"
输出: 3
解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。
示例 2：
输入：a = "aaa", b = "bbb"
输出：3
示例 3：
输入：a = "aaa", b = "aaa"
输出：-1
提示：
两个字符串长度均处于区间 [1 - 100] 。
字符串中的字符仅含有 'a'~'z' 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-uncommon-subsequence-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：
/*
* @lc app=leetcode.cn id=521 lang=javascript
*
* [521] 最长特殊序列 Ⅰ
*/
// @lc code=start
/**
* @param {string} a
* @param {string} b
* @return {number}
*/
var findLUSlength = function(a, b) {
if(a == b) {
return -1;
} else {
return Math.max(a.length, b.length);
}
};
文字游戏，其实在考两个字符串是否相同
2020.09.18
No.521 最长特殊序列II
给定字符串列表，你需要从它们中找出最长的特殊序列。最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
子序列可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。
输入将是一个字符串列表，输出是最长特殊序列的长度。如果最长特殊序列不存在，返回 -1 。
示例：
输入: "aba", "cdc", "eae"
输出: 3
提示：
所有给定的字符串长度不会超过 10 。
给定字符串列表的长度将在 [2, 50 ] 之间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-uncommon-subsequence-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：
/*
* @lc app=leetcode.cn id=522 lang=javascript
*
* [522] 最长特殊序列 II
*/
// @lc code=start
/**
* @param {string[]} strs
* @return {number}
*/
var findLUSlength = function(strs) {
// 对数组进行排序，将字符串长度较大的排在前面
strs.sort((a,b) => b.length - a.length);
let maxStr = '', flag = true;
for(let i=0;i<strs.length;i++) {
maxStr = strs[I];
for(let j=0;j<strs.length;j++){
if(j!=i) {
if(strs[j].includes(maxStr)) {
flag = false;
break;
} else {
// 求子序列
if(isSubseq(strs[j],maxStr)) {
flag = false;
break;
} else {
flag = true;
}
}
}
}
if(flag) break;
}
if(flag) {
return maxStr.length;
} else {
return -1;
}
// 判断str2是否是str1的子序列
function isSubseq(str1,str2) {
let i = 0,
j = 0;
while ( i < str1.length && j < str2.length ) {
if (str2.charAt(j) == str1.charAt(i)) {
j++;
}
I++;
}
return j == str2.length;
}
};
对最长字符串获取，然后判断是否是子序列，注意这里是是否是子序列，做一个函数进行判断
总结：
- 最长方案主要会设计到递归和循环，这里可以利用栈、树等数据结构进行构造优化，减少时长；
- 对于需要进行不断寻找最长的问题可以考虑动态规划等通项公式解法、分治算法等
