# 中等
# 无重复字符的最长字串
# 题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
2
3
示例：
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
2
3
题目链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
# 解法
var lengthOfLongestSubstring = function(s) {
let arr=[],result=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[i]);
result=Math.max(arr.length,result);
}
return result;
};
2
3
4
5
6
7
8
9
10
11
12
# 三数之和
# 题目
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
2
示例：
输入：nums = [0]
输出：[]
2
题目链接：https://leetcode-cn.com/problems/3sum/
# 解法
var threeSum = function(nums) {
if(nums.length<3){
return []
}
if(nums.length>=3 && nums.every(num=>num==0)){
return [[0,0,0]]
}
nums.sort((a,b)=>a-b)//先排序
let i=0,j=1,k=nums.length-1;
let arr=[]
while(j<k){
const sum=nums[i]+nums[j]+nums[k]
if(sum==0){
arr.push([nums[i],nums[j],nums[k]])
j++;
}
if(sum>0){
k--;//大于0 负数过小，右值左移
}
if(sum<0){
j++;//小于0 正数过大，左值右移
}
if(j>=k){
i++;
j=i+1;
k=nums.length-1;
}
}
//去重：对象key方式去重
const obj={};
for(const count of arr){
const sortNum=JSON.stringify(count.sort());
if(!obj[sortNum]){
obj[sortNum]=true;
}
}
const result=Object.keys(obj).map(JSON.parse);
return result;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 盛水最多的容器
# 题目
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
2
3
示例：
输入：height = [1,2,1]
输出：2
2
题目链接：https://leetcode-cn.com/problems/container-with-most-water/
# 解法
var maxArea = function(height) {
let res=0,i=0,j=height.length-1;
while(i<j){
res=Math.max(res,Math.min(height[j],height[i])*(j-i));
if(height[i]<height[j]){
i++;
}else{
j--;
}
}
return res;
};
2
3
4
5
6
7
8
9
10
11
12
# 字符串转整数
# 题目
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。 假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
注意：
本题中的空白字符只包括空格字符 ' ' 。 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 231 − 1 或 −231 。
示例：
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字
2
3
题目链接：https://leetcode-cn.com/problems/string-to-integer-atoi/
# 解法
var myAtoi = function(s) {
s=parseInt(s,10)
if(isNaN(s)){
return 0;
}else{
return s>=0?Math.min(s,Math.pow(2,31)-1):Math.max(s,Math.pow(-2,31))
}
};
2
3
4
5
6
7
8
# 电话号码的字母组合
# 题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例：
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
2
题目链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
# 解法
var letterCombinations = function(digits) {
if(digits.length==0) return [];
const map={
'2':'abc',
'3':'def',
'4':'ghi',
'5':'jkl',
'6':'mno',
'7':'pqrs',
'8':'tuv',
'9':'wxyz'
}
let arr=[];
arr.push('');
for(let i=0;i<digits.length;i++){
const levelSize = arr.length;
for(let j=0;j<levelSize;j++){
const curStr=arr.shift()
const letter=map[digits[i]]
for(let l of letter){
arr.push(curStr+l)
}
}
}
return arr;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 丑数 II
# 题目
编写一个程序，找出第 n 个丑数。丑数就是质因数只包含 2, 3, 5 的正整数。
示例：
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
2
3
题目链接：https://leetcode-cn.com/problems/ugly-number-ii/
# 解法
var nthUglyNumber = function(n) {
let i1=0,i2=0,i3=0;
let dp=[1]
for(let i=1;i<n;i++){
let min=Math.min(dp[i1]*2,dp[i2]*3,dp[i3]*5)
if(min==dp[i1]*2) i1++;
if(min==dp[i2]*3) i2++;
if(min==dp[i3]*5) i3++;
dp.push(min)
}
return dp[n-1]
};
2
3
4
5
6
7
8
9
10
11
12
13
# 只出现一次的次数 III
# 题目
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例：
输入: [1,2,1,3,2,5]
输出: [3,5]
2
题目链接：https://leetcode-cn.com/problems/single-number-iii/
# 解法一
var singleNumber = function(nums) {
nums=nums.sort((a,b)=>a-b)
let set=new Set()
for(let item of nums){
if(set.has(item)){
set.delete(item)
}else{
set.add(item)
}
}
return [...set];
};
2
3
4
5
6
7
8
9
10
11
12
# 解法二
var singleNumber = function(nums) {
nums=nums.sort((a,b)=>a-b)
let set=new Set()
for(let item of nums){
if(nums.indexOf(item)==nums.lastIndexOf(item)){
set.add(item)
}
}
return [...set];
};
2
3
4
5
6
7
8
9
10
# 最长回文子串
# 题目
给你一个字符串 s，找到 s 中最长的回文子串。
示例：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
2
3
示例：
输入：s = "ac"
输出："a"
2
题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
# 解法一
var longestPalindrome = function(s) {
if(!s || s.length<2) return s
let start=0,end=0,n=s.length;
let centerExpand=(left,right)=>{
while(left>=0 && right<n && s[left]==s[right]){
left--;
right++;
}
return right-left-1;
}
for(let i=0;i<n;i++){
let len1=centerExpand(i,i)
let len2=centerExpand(i,i+1)
let maxLen=Math.max(len1,len2)
if(maxLen>end-start){
start = i - ((maxLen - 1) >> 1);
end = i + (maxLen >> 1);
}
}
return s.substring(start,end+1);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 解法二（暴力解法，但是超时了）
var longestPalindrome = function(s) {
s=s.split('');
let arr=[];
let result=''
for(let i=0;i<s.length;i++){
for(let j=i+1;j<=s.length;j++){
let res=s.slice(i,j);
if(res.join('')==res.reverse().join('')){
if(result.length<res.length){
result=res
}
}
}
}
return result.join('');
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 最长回文子串
# 题目
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
2
题目链接：https://leetcode-cn.com/problems/generate-parentheses/
# 解法
const generateParenthesis = function (n) {
const res = [];
function dfs(l, r, str) {
if (l == n && r == n) {
return res.push(str);
}
// l 小于 r 时不满足条件 剪枝
if (l < r) {
return;
}
// l 小于 n 时可以插入左括号，最多可以插入 n 个
if (l < n) {
dfs(l + 1, r, str + "(");
}
// r < l 时 可以插入右括号
if (r < l) {
dfs(l, r + 1, str + ")");
}
}
dfs(0, 0, "");
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 旋转数组
# 题目
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例：
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
2
3
4
5
6
题目链接：https://leetcode-cn.com/problems/rotate-array/
# 解法一
var rotate = function(nums, k) {
let length=nums.length
nums.unshift(...nums.splice(length-k,k))
return nums;
};
2
3
4
5
# 解法一
var rotate = function(nums, k) {
let length=nums.length
nums.unshift(...nums.splice(length-k,k))
return nums;
};
2
3
4
5
# 有效的数独
# 题目
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
示例：
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true
2
3
4
5
6
7
8
9
10
11
12
13
题目链接：https://leetcode-cn.com/problems/valid-sudoku/
# 解法
var isValidSudoku = function(board) {
const rows=[],colums=[],boxes=[]
for(let i=0;i<9;i++){
rows[i]=[]
colums[i]=[]
boxes[i]=[]
}
console.log(rows);
for(let i=0;i<9;i++){
for(let j=0;j<9;j++){
let number=board[i][j]
if(number!='.'){
//对于横排
if(!rows[i].includes(number)){
rows[i].push(number)
}else{
return false;
}
//对于竖排
if(!colums[j].includes(number)){
colums[j].push(number)
}else{
return false;
}
//对于格子
const boxIndex=Math.floor(i / 3) * 3 + Math.floor(j / 3);
if(!boxes[boxIndex].includes(number)){
boxes[boxIndex].push(number)
}else{
return false
}
}
}
}
return true;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 旋转图像
# 题目
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
2
题目链接：https://leetcode-cn.com/problems/rotate-image/
# 解法一
var rotate = function(matrix) {
let n=matrix.length;
const matrix_new = new Array(n).fill(0).map(() => new Array(n).fill(0));
// matrix=matrix.toString().split(",").map(item=>+item)
for(let i=0;i<n;i++){
for(let j=0;j<n;j++){
matrix_new[j][n - i - 1] = matrix[i][j];
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
matrix[i][j] = matrix_new[i][j];
}
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 打家劫舍
# 题目
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
示例：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
2
3
4
题目链接：https://leetcode-cn.com/problems/house-robber/
# 解法一
var rob = function(nums) {
let len=nums.length;
let dp=new Array(len+1);
dp[0]=0
dp[1]=nums[0]
for(let i=2;i<=len;i++){
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1])
}
return dp[len]
};
2
3
4
5
6
7
8
9
10
# 字符串的排列
# 题目
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例：
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
2
3
题目链接：https://leetcode-cn.com/problems/permutation-in-string/
# 解法
var checkInclusion = function(s1, s2) {
let n=s1.length,m=s2.length;
if(n>m) return false;
let arr1=new Array(26).fill(0)
let arr2=new Array(26).fill(0)
for(let i=0;i<n;i++){
arr1[s1[i].charCodeAt()-97]++
arr2[s2[i].charCodeAt()-97]++;
}
if(arr1.join('')==arr2.join('')){
return true;
}
for(let i=n;i<m;i++){
arr2[s2[i].charCodeAt()-97]++;
arr2[s2[i-n].charCodeAt()-97]--;
if(arr1.join('')==arr2.join('')){
return true;
}
}
return false;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 最长不含重复字符的子字符串
# 题目
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例：
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
2
3
题目链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
# 解法一
var lengthOfLongestSubstring = function(s) {
let str='',max=0;
for(let i=0;i<s.length;i++){
if(str.indexOf(s[i])==-1){
str+=s[i]
}else{
max=Math.max(max,str.length)
str+=s[i]
str=str.slice(str.indexOf(s[i])+1)
}
}
max=Math.max(max,str.length)
return max||str.length;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
# 解法二
var lengthOfLongestSubstring = function(s) {
let max=0;
for(let i=0;i<s.length;i++){
for(let j=i+1;j<=s.length;j++){
let str=s.slice(i,j)
max=Math.max(max,str.length)
if(str.includes(s[j])){
break;
}
}
}
return max
};
2
3
4
5
6
7
8
9
10
11
12
13
# 整数拆分
# 题目
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例：
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
2
3
题目链接：https://leetcode-cn.com/problems/integer-break/
# 解法一
var cuttingRope = function(n) {
const dp=new Array(n+1).fill(1);
console.log(dp);
for(let i=3;i<=n;i++){
for(let j=1;j<i;j++){
dp[i]=Math.max(dp[i],j*(i-j),j*dp[i-j])
}
}
return dp[n]
};
2
3
4
5
6
7
8
9
10
# 解法二（数学解法）
var cuttingRope = function(n) {
if(n==2 ) return 1
if(n==3 ) return 2
let a=Math.floor(n/3)
let b=n%3;
if(b==0) return Math.pow(3,a)
if(b==1) return Math.pow(3,a-1)*4
return Math.pow(3,a)*2
};
2
3
4
5
6
7
8
9
# 最大连续1的个数 III
# 题目
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。返回仅包含 1 的最长（连续）子数组的长度。
示例：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
2
3
4
5
题目链接：https://leetcode-cn.com/problems/max-consecutive-ones-iii
# 解法一
var longestOnes = function(A, K) {
let left=0,right=0,max=0,zeroCount=0;
let len=A.length;
for(;right<len;right++){
if(A[right]==0) zeroCount++;
if(zeroCount>K && A[left++]==0)zeroCount--;
}
return right-left;
};
2
3
4
5
6
7
8
9
# 解法二
var longestOnes = function(A, K) {
let left=0,right=0,max=0,zeroCount=0;
let len=A.length;
while(right<len){
if(A[right]==0) zeroCount++;
while(zeroCount>K){
if(A[left++]==0) zeroCount--;
}
max=Math.max(max,right-left+1)
right++;
}
return max;
};
2
3
4
5
6
7
8
9
10
11
12
13
# 四数相加 II
# 题目
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
示例：
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
2
3
4
5
6
7
8
9
10
11
12
13
题目链接：https://leetcode-cn.com/problems/4sum-ii/
# 解法
var fourSumCount = function(A, B, C, D) {
const map=new Map();
let index=0;
A.forEach(a => {
B.forEach(b => {
if(map.has(a+b)){
map.set(a+b,map.get(a+b)+1)
}else{
map.set(a+b,1)
}
});
});
C.forEach(c=>{
D.forEach(d=>{
if(map.has(-c-d)){
index+=map.get(-c-d)
}
})
})
return index;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 可获得的最大点数
# 题目
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例：
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
2
3
4
题目链接：https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/
# 解法
var maxScore = function(cardPoints, k) {
let len=cardPoints.length;
const size=len-k;
let totalSum=cardPoints.reduce((p,v)=>p+v);
let sum=0;
for(let i=0;i<size;i++){
sum+=cardPoints[i]
}
let minSum=sum;
for(let i=size;i<len;i++){
sum+=cardPoints[i]-cardPoints[i-size];
minSum=Math.min(minSum,sum)
}
return totalSum-minSum;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 最长重复子数组
# 题目
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
2
3
4
5
6
题目链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
# 解法
var findLength = function(A, B) {
let aLen=A.length,bLen=B.length;
let max=0;
for(let i=0;i<aLen;i++){
for(j=0;j<bLen;j++){
if(A[i]==B[j]){
let len=1;
while(i+len<aLen && j+len<bLen && A[i+len]==B[j+len]){
len++;
}
max=Math.max(max,len)
}
}
}
return max;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 组合
# 题目
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例：
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
2
3
4
5
6
7
8
9
10
题目链接：https://leetcode-cn.com/problems/combinations/
# 解法（回溯法）
var combine = function(n, k) {
let res=[]
const dfs=(start,temp)=>{
if(temp.length==k){
res.push(temp.slice())
return;
}
for(let i=start;i<=n;i++){
temp.push(i)
dfs(i+1,temp)
temp.pop()
}
}
dfs(1,[])
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 组合总和
# 题目
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
示例：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
2
3
4
5
6
题目链接：https://leetcode-cn.com/problems/combination-sum/
# 解法
var combinationSum = function(candidates, target) {
let res=[]
const dfs=(arr,sum)=>{
if(sum==target){
let str=arr.slice().sort((a,b)=>a-b)
for(let i=0;i<res.length;i++){
if(str.join('')==res[i].join('')) return;
}
res.push(str)
}else if(sum>target){
return;
}
for(let i=0;i<candidates.length;i++){
arr.push(candidates[i])
dfs(arr,sum+candidates[i])
arr.pop();
}
}
dfs([],0)
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 组合总和 II
# 题目
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
示例：
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
2
3
4
5
6
7
8
题目链接：https://leetcode-cn.com/problems/combination-sum-ii/
# 解法
var combinationSum2 = function(candidates, target) {
let res=[]
const dfs=(start,arr,sum)=>{
if(sum==target){
let str=arr.slice().sort((a,b)=>a-b)
for(let i=0;i<res.length;i++){
if(str.join('')==res[i].join('')) return;
}
res.push(str)
}else if(sum>target){
return;
}
for(let i=start;i<candidates.length;i++){
arr.push(candidates[i])
dfs(i+1,arr,sum+candidates[i])
arr.pop()
}
}
dfs(0,[],0)
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 组合总和 III
# 题目
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
示例：
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
2
题目链接：https://leetcode-cn.com/problems/combination-sum-iii/
# 解法
var combinationSum3 = function(k, n) {
let res=[]
const dfs=(start,arr,sum)=>{
if(arr.length==k){
if(sum==n){
res.push(arr.slice())
}
return ;
}
for(let i=start;i<=9;i++){
arr.push(i);
dfs(i+1,arr,sum+i)
arr.pop();
}
}
dfs(1,[],0)
return res
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 字符串的好分割数目
# 题目
给你一个字符串 s ，一个分割被称为 「好分割」 当它满足：将 s 分割成 2 个字符串 p 和 q ，它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。
示例：
输入：s = "aacaba"
输出：2
解释：总共有 5 种分割字符串 "aacaba" 的方法，其中 2 种是好分割。
("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。
2
3
4
5
6
7
8
题目链接：https://leetcode-cn.com/problems/number-of-good-ways-to-split-a-string/
# 解法
var numSplits = function(s) {
let map=new Map(),set=new Set(),res=0
for(let item of s){
map.set(item,(map.get(item)||0)+1)
}
for(let key of s){
set.add(key)
let value=map.get(key)-1
value?map.set(key,value):map.delete(key)
if(map.size<set.size) return res
map.size==set.size && res++;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
# 爱生气的书店老板
# 题目
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
示例：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
2
3
4
5
题目链接：https://leetcode-cn.com/problems/grumpy-bookstore-owner/
# 解法
var maxSatisfied = function(customers, grumpy, X) {
let len=grumpy.length;
let total=0;
let max=0;
for(let i=0;i<len;i++){
if(grumpy[i]==0){
total+=customers[i]
}
}
for(let i=0;i<=len-X;i++){
let sum=0;
for(let j=i;j<i+X;j++){
if(grumpy[j]==1){
sum+=customers[j]
}
}
max=Math.max(max,total+sum)
}
return max;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 分割回文串
# 题目
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
示例：
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
2
3
4
5
6
题目链接：https://leetcode-cn.com/problems/palindrome-partitioning/
# 解法
var partition = function(s) {
let len=s.length;
let res=[]
const isPaliddrome=(l,r)=>{
while(l<r){
if(s[l]!=s[r]) return false;
l++;
r--;
}
return true;
}
const dfs=(start,temp)=>{
if(start==len){
res.push([...temp])
}
for(let i=start;i<len;i++){
if(isPaliddrome(start,i)){
temp.push(s.substring(start,i+1));
dfs(i+1,temp)
temp.pop()
}
}
}
dfs(0,[])
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 字母大小全排写序列
# 题目
给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。
示例：
示例：
输入：S = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]
输入：S = "3z4"
输出：["3z4", "3Z4"]
输入：S = "12345"
输出：["12345"]
2
3
4
5
6
7
8
9
题目链接：https://leetcode-cn.com/problems/letter-case-permutation/
# 解法
var letterCasePermutation = function(S) {
S=S.toLowerCase()
let res=[]
const dfs=(num,s)=>{
res.push(s)
for(let i=num;i<s.length;i++){
let str=s.slice(0,i)+s[i].toUpperCase()+s.slice(i+1)
dfs(i+1,str)
}
}
dfs(0,S)
return [...new Set(res)]
};
2
3
4
5
6
7
8
9
10
11
12
13
# 划分字母区间
# 题目
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
2
3
4
5
6
题目链接：https://leetcode-cn.com/problems/partition-labels/
# 解法
var partitionLabels = function(S) {
let map=new Map()
let arr=[]
let start=0,end=0
for(let index in S){
map.set(S[index],index)
}
for(let i=0;i<S.length;i++){
end=Math.max(end,map.get(S[i]))
if(i==end){
arr.push(end-start+1)
start=i+1;
}
}
return arr;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 去除重复字母
# 题目
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例：
输入：s = "cbacdcbc"
输出："acdb"
2
题目链接：https://leetcode-cn.com/problems/remove-duplicate-letters/
# 解法
var removeDuplicateLetters = function(s) {
let arr=[]
for(let i=0;i<s.length;i++){
if(arr.indexOf(s[i])!=-1) continue;
while(arr[arr.length-1]>s[i] && s.indexOf(arr[arr.length-1],i)>i){
arr.pop()
}
arr.push(s[i])
}
return arr.join('')
};
2
3
4
5
6
7
8
9
10
11
# 重复的DNA序列
# 题目
所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
示例：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
2
题目链接：https://leetcode-cn.com/problems/repeated-dna-sequences
# 解法
var findRepeatedDnaSequences = function(s) {
const L=10;
let map=new Map();
let arr=[]
for(let i=0;i<=s.length-L;i++){
let str=s.slice(i,i+L)
if(map.has(str)){
arr.push(str)
}else{
map.set(str,1)
}
}
return [...new Set(arr)];
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 替换后的最长重复子串
# 题目
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
示例：
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。
2
3
题目链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement/
# 解法
var characterReplacement = function(s, k) {
const arr=new Array(26).fill(0)
let max=0,left=0,right=0;
let len=s.length;
while(right<len){
arr[s[right].charCodeAt()-'A'.charCodeAt()]++;
max=Math.max(max,arr[s[right].charCodeAt()-'A'.charCodeAt()])
if(right-left>max+k-1){
arr[s[left].charCodeAt()-'A'.charCodeAt()]--
left++
}
right++
}
return right-left;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 统计字典序元音字符串的数目
# 题目
给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
示例：
输入：n = 1
输出：5
解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]
2
3
题目链接：https://leetcode-cn.com/problems/count-sorted-vowel-strings/
# 解法一
var countVowelStrings = function(n) {
let arr = Array(5).fill(1)
for(let i=0;i<n-1;i++){
for(let j=1;j<arr.length;j++){
arr[j]=arr[j]+arr[j-1]
}
}
return arr.reduce((p,v)=>p+v)
};
2
3
4
5
6
7
8
9
10
# 解法二
var countVowelStrings = function(n) {
let cnt = 0
const dfs = (l, valid) => {
if (l === 0) {
cnt += 1
return
}
for (let i = 0; i < valid; i++) dfs(l - 1, valid - i)
}
dfs(n,5)
return cnt
};
2
3
4
5
6
7
8
9
10
11
12
13
# 全排列
# 题目
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例：
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
2
3
4
5
6
7
8
9
10
题目链接：https://leetcode-cn.com/problems/permutations/
# 解法
var permute = function(nums) {
let res=[]
let used={}
const dfs=(use)=>{
if(use.length==nums.length){
res.push(use.slice())
return;
}
for(let item of nums){
if(used[item]) continue;
use.push(item)
used[item]=true
dfs(use)
use.pop() // 上一句的递归结束，回溯，将最后选的数pop出来
used[item]=false
}
}
dfs([])
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 全排列II
# 题目
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
2
3
4
5
题目链接：https://leetcode-cn.com/problems/permutations-ii/
# 解法
var permuteUnique = function(nums) {
let res=[]
let used={}
nums.sort((x, y) => x - y);
const dfs=(temp)=>{
if(temp.length==nums.length){
res.push(temp.slice())
return;
}
for(let i=0;i<nums.length;i++){
if(used[i]||(i>0 && nums[i]==nums[i-1] && !used[i-1])) continue;
temp.push(nums[i]);
used[i]=true;
dfs(temp);
temp.pop();
used[i]=false;
}
}
dfs([])
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 比特位计数
# 题目
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例：
输入: 2
输出: [0,1,1]
2
题目链接：https://leetcode-cn.com/problems/counting-bits/
# 解法
var countBits = function(num) {
let arr=[]
for(let i=0;i<=num;i++){
arr.push(i.toString(2).replace(/[0]/g,'').length)
}
return arr;
};
2
3
4
5
6
7
# 最长公共子序列
# 题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列，则返回 0。
示例：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
2
3
题目链接：https://leetcode-cn.com/problems/longest-common-subsequence/
图解：
# 解法
var longestCommonSubsequence = function(text1, text2) {
// 初始化二维 dp 数组
let m=text1.length,n=text2.length;
const dp = new Array(m)
for (let i = 0; i < m+1; i++) {
dp[i] = new Array(n+1).fill(0)
}
let max=0;
for(let i=1;i<=text1.length;i++){
for(let j=1;j<=text2.length;j++){
if(text1[i-1]==text2[j-1]){
dp[i][j]=dp[i-1][j-1]+1
}else{
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n]
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 两个字符串的删除操作
# 题目
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例：
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
2
3
题目链接：https://leetcode-cn.com/problems/delete-operation-for-two-strings/
# 解法
var minDistance = function(word1, word2) {
const m=word1.length,n=word2.length;
if(!word2 || !word1) return m+n;
let record=[]
for(let i=0;i<=m;i++){
record[i]=[]
for(let j=0;j<=n;j++){
if (!i || !j) record[i][j] = 0;
else if (word1[i - 1] === word2[j - 1]) record[i][j] = record[i - 1][j - 1] + 1;
else record[i][j] = Math.max(record[i - 1][j], record[i][j - 1]);
}
}
console.log(record);
return m+n-2*record[m][n]
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 子集
# 题目
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
2
题目链接：https://leetcode-cn.com/problems/subsets/
# 解法
var subsets = function(nums) {
let res=[]
const dfs=(start,temp)=>{
res.push(temp.slice())
if(start>nums.length){
return;
}
for(let i=start;i<nums.length;i++){
temp.push(nums[i])
dfs(i+1,temp)
temp.pop()
}
}
dfs(0,[])
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 子集II
# 题目
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
示例：
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
2
3
4
5
6
7
8
9
10
题目链接：https://leetcode-cn.com/problems/subsets-ii/
# 解法
var subsetsWithDup = function(nums) {
let res=[]
let used={}
nums=nums.sort((a,b)=>a-b)
const dfs=(start,temp)=>{
res.push(temp.slice())
if(start>nums.length){
return;
}
for(let i=start;i<nums.length;i++){
if(i>0 && !used[nums[i-1]] && nums[i]==nums[i-1]) continue;
temp.push(nums[i]);
used[nums[i]]=true;
dfs(i+1,temp);
temp.pop();
used[nums[i]]=false;
}
}
dfs(0,[])
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 递增子序列
# 题目
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例：
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
2
题目链接：https://leetcode-cn.com/problems/increasing-subsequences/
# 解法
var findSubsequences = function(nums) {
let res=[]
let set=new Set()
const dfs=(start,temp)=>{
if(temp.length>=2){
let str=temp.toString()
if(!set.has(str)){
set.add(str)
res.push(temp.slice())
}
}
for(let i=start;i<nums.length;i++){
if(temp.length==0 || temp[temp.length-1]<=nums[i]){
temp.push(nums[i])
dfs(i+1,temp)
temp.pop()
};
}
}
dfs(0,[])
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 回文子串
# 题目
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
2
3
题目链接：https://leetcode-cn.com/problems/palindromic-substrings/
# 解法
var countSubstrings = function(s) {
let index=0;
const len=s.length;
function isPalid(str){
let i=0;
let j=str.length-1;
while(i<=j){
if(str[i]!=str[j]) return false;
i++;
j--;
}
return true
}
for(let i=0;i<len;i++){
for(let j=i+1;j<len+1;j++){
let str=s.slice(i,j)
if(isPalid(str)){
index++;
}
}
}
return index;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 活字印刷
# 题目
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。注意：本题中，每个活字字模只能使用一次。
示例：
输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
2
3
题目链接：https://leetcode-cn.com/problems/letter-tile-possibilities/
# 解法
var numTilePossibilities = function (tiles) {
let set=new Set()
let used={}
const dfs=(path)=>{
if(path.length){
set.add(path)
}
for(let i=0;i<tiles.length;i++){
if(used[i]) continue;
used[i]=true;
path+=tiles[i];
dfs(path);
path=path.slice(0,path.length-1);
used[i]=false;
}
}
dfs('')
return set.size;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 螺旋矩阵
# 题目
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
2
题目链接：https://leetcode-cn.com/problems/spiral-matrix/
# 解法
var spiralOrder = function(matrix) {
const row=matrix.length,col=matrix[0].length,size=row*col,res=[];
let t = 0, r = col - 1, b = row - 1, l = 0//上右下左四个方向
while(res.length!=size){
// 从左到右
for (let i = l; i <= r; i++) res.push(matrix[t][i])
t++
// 从上到下
for (let i = t; i <= b; i++) res.push(matrix[i][r])
r--
// 检查下是否越觉
if (res.length === size) break
// 从右到左
for (let i = r; i >= l; i--) res.push(matrix[b][i])
b--
// 从下到上
for (let i = b; i >= t; i--) res.push(matrix[i][l])
l++
}
return res;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 下一个更大元素 II
# 题目
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例：
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
2
3
4
5
题目链接：https://leetcode-cn.com/problems/next-greater-element-ii/
# 解法
var nextGreaterElements = function(nums) {
var res = [];
var _nums = nums.concat(nums);
for(let i=0;i<nums.length;i++){
let flag=true;
for(let j=i+1;j<_nums.length;j++){
if(nums[i]<_nums[j]){
res.push(_nums[j])
flag=false;
break;
}
}
if(flag) res.push(-1)
}
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 所有排列中的最大和
# 题目
有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [starti, endi] 。第 i 个查询求 nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi] 的结果 ，starti 和 endi 数组索引都是 从 0 开始 的。你可以任意排列 nums 中的数字，请你返回所有查询结果之和的最大值。由于答案可能会很大，请你将它对 109 + 7 取余 后返回。
示例：
输入：nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
输出：19
解释：一个可行的 nums 排列为 [2,1,3,4,5]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
总和为：8 + 3 = 11。
一个总和更大的排列为 [3,5,4,2,1]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5 = 8
总和为： 11 + 8 = 19，这个方案是所有排列中查询之和最大的结果。
2
3
4
5
6
7
8
9
10
题目链接：https://leetcode-cn.com/problems/maximum-sum-obtained-of-any-permutation/
# 解法
var maxSumRangeQuery = function(nums, requests) {
const len = nums.length
const hash = new Array(len).fill(0)
let res = 0
requests.forEach((item) => {
const [start, end] = item
for (let i = start; i <= end; i++) {
hash[i]++
}
})
hash.sort((a,b) => b - a)
nums.sort((a,b) => b - a)
for (let i = 0; i < len; i++) {
res += nums[i] * hash[i]
}
return res % (Math.pow(10, 9) + 7)
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 保持城市天际线
# 题目
在二维数组grid中，grid[i][j]代表位于某处的建筑物的高度。 我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度。 高度 0 也被认为是建筑物。最后，从新数组的所有四个方向（即顶部，底部，左侧和右侧）观看的“天际线”必须与原始数组的天际线相同。 城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。 请看下面的例子。建筑物高度可以增加的最大总和是多少？
示例：
例子：
输入： grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出： 35
解释：
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]
从数组竖直方向（即顶部，底部）看“天际线”是：[9, 4, 8, 7]
从水平水平方向（即左侧，右侧）看“天际线”是：[8, 7, 9, 3]
在不影响天际线的情况下对建筑物进行增高后，新数组如下：
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
题目链接：https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/
# 解法
var maxIncreaseKeepingSkyline = function(grid) {
let arr=[]
for(let i=0;i<grid.length;i++){
let max=-Infinity;
for(let j=0;j<grid[0].length;j++){
max=Math.max(max,grid[j][i]) //求纵向最大值
}
arr.push(max)
}
let value=0;
for(let i=0;i<grid.length;i++){
let max=Math.max(...grid[i]) //求横向最大值
for(let j=0;j<grid[0].length;j++){
if(max<=arr[j]){
value+=max-grid[i][j]
}else{
value+=arr[j]-grid[i][j]
}
}
}
return value;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 除自身以外数组的乘积
# 题目
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例：
输入: [1,2,3,4]
输出: [24,12,8,6]
2
题目链接：https://leetcode-cn.com/problems/product-of-array-except-self/
# 解法（正反遍历）
var productExceptSelf = function(nums) {
let res=[]
for(let i=0,temp=1;i<nums.length;i++){
res[i]=temp;
temp*=nums[i]
}
for(let i=nums.length-1,temp=1;i>=0;i--){
res[i]*=temp;
temp*=nums[i]
}
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
# 自定义字符串排序
# 题目
符串S和 T 只包含小写字符。在S中，所有字符只会出现一次。S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说，如果S中x在y之前出现，那么返回的字符串中x也应出现在y之前。
示例：
示例:
输入:
S = "cba"
T = "abcd"
输出: "cbad"
解释:
S中出现了字符 "a", "b", "c", 所以 "a", "b", "c" 的顺序应该是 "c", "b", "a".
由于 "d" 没有在S中出现, 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的输出。
2
3
4
5
6
7
8
题目链接：https://leetcode-cn.com/problems/custom-sort-string/
# 解法
var customSortString = function(S, T) {
T = T.split("")
T.sort((a,b)=>{
return S.indexOf(a) - S.indexOf(b)
})
return T.join("")
};
2
3
4
5
6
7
# 删掉一个元素以后全为 1 的最长子数组
# 题目
给你一个二进制数组 nums ，你需要从中删掉一个元素。请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组，请返回 0 。
示例：
输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。
2
3
题目链接：https://leetcode-cn.com/problems/longest-subarray-of-1s-after-deleting-one-element/
# 解法
var longestSubarray = function(nums) {
let left=0,right=0,max=0,zeroCount=0;
let len=nums.length;
while(right<len){
if(nums[right]==0) zeroCount++;
while(zeroCount>1){
if(nums[left++]==0) zeroCount--;
}
max=Math.max(max,right-left)
right++;
}
return max;
};
2
3
4
5
6
7
8
9
10
11
12
13
# 132模式
给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
示例：
输入: [3, 1, 4, 2]
输出: True
解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
2
3
题目链接：https://leetcode-cn.com/problems/132-pattern/
# 解法
var find132pattern = function(nums) {
let len=nums.length,mid=0,stack=[]
while(mid<len){
stack=[]
for(let i=mid;i<len;i++){
if(!stack.length) stack[0]=nums[i]
if(nums[i]>stack[0] && stack.length==1)stack[1]=nums[i]
if(nums[i]>stack[1] && stack.length==2 && i!=len-1) stack[1]=nums[i]
if(nums[i]>stack[0] && nums[i]<stack[1]) return true;
if(mid==len-2) return false;
}
mid++;
}
return false;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
示例：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
2
3
4
5
6
7
8
9
10
题目链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height
# 解法
var reconstructQueue = function(people) {
let res=[]
people.sort((a,b)=>{
if(a[0]==b[0]){
return a[1]-b[1]
}
return b[0]-a[0]
})
for(let item of people){
if(res.length<=item[1]){
res.push(item)
}else{
res.splice(item[1],0,item)
}
}
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
2
3
4
5
6
7
8
题目链接：https://leetcode-cn.com/problems/triangle/
# 解法
var minimumTotal = function(triangle) {
let n=triangle.length;
let dp=new Array(n)
for(let i=0;i<n;i++){
dp[i]=new Array(triangle[i].length)
}
for(let i=n-1;i>=0;i--){
for(let j=0;j<triangle[i].length;j++){
if(i==n-1){
dp[i][j]=triangle[i][j]
}else{
dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
}
}
}
return dp[0][0];
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 和为 K 的最少斐波那契数字数目
给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
斐波那契数字定义为：
F1 = 1 F2 = 1 Fn = Fn-1 + Fn-2 ， 其中 n > 2 。 数据保证对于给定的 k ，一定能找到可行解。
示例：
输入：k = 7
输出：2
解释：斐波那契数字为：1，1，2，3，5，8，13，……
对于 k = 7 ，我们可以得到 2 + 5 = 7 。
2
3
4
题目链接：https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/
# 解法
var findMinFibonacciNumbers = function(k) {
let n=0;
let res=[1,1]
while(n<k){
n=res[res.length-1]+res[res.length-2]
res.push(n)
}
let count=0;
for(let i=res.length-1;i>=0;i--){
if(res[i]>k) continue;
k-=res[i]
count++;
if(k==0) return count
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 避免重复字母的最小删除成本
给你一个字符串 s 和一个整数数组 cost ，其中 cost[i] 是从 s 中删除字符 i 的代价。返回使字符串任意相邻两个字母不相同的最小删除成本。请注意，删除一个字符后，删除其他字符的成本不会改变。
示例：
输入：s = "abaac", cost = [1,2,3,4,5]
输出：3
解释：删除字母 "a" 的成本为 3，然后得到 "abac"（字符串中相邻两个字母不相同）。
2
3
4
题目链接：https://leetcode-cn.com/problems/minimum-deletion-cost-to-avoid-repeating-letters
# 解法
var minCost = function(s, cost) {
let sum=0;
s=s.split('')
for(let i=0;i<s.length-1;i++){
if(s[i]==s[i+1]){
if(cost[i]<cost[i+1]){
sum+=cost[i]
}else{
sum+=cost[i+1]
cost[i+1]=cost[i] //重点在这一句
}
}
}
return sum;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 至少有 K 个重复字符的最长子串
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
示例：
输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
2
3
题目链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/
# 解法
var longestSubstring = function(s, k) {
let map=new Map()
let max=0;
for(let item of s){
map.set(item,(map.get(item)||0)+1)
}
let res=[]
for(let [value,key] of map){
if(key<k){
res.push(value)
}
}
if(res.length==0) return s.length;
let j=0;
for(let i=0;i<s.length;i++){
if(res.includes(s[i])){
console.log(s.slice(j,i));
max=Math.max(max,longestSubstring(s.slice(j,i),k))
j=i+1;
}
}
max=Math.max(max,longestSubstring(s.slice(j),k))
return max;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 定长子串中元音的最大数目
给你字符串 s 和整数 k 。请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。英文中的 元音字母 为（a, e, i, o, u）。
示例：
输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。
2
3
题目链接：https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/
# 解法
var maxVowels = function(s, k) {
let set=['a','e','i','o','u'];
let max=0;
let left=0,right=0,count=0
while(right<s.length){
if(set.indexOf(s[right])!=-1){
count++;
}
right++;
if(right-left==k){
max=Math.max(max,count)
if(set.indexOf(s[left])!=-1){
count--
}
left++
}
}
return max;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。请返回这个数组中「优美子数组」的数目。
示例：
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
2
3
题目链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays/
# 解法
var numberOfSubarrays = function(nums, k) {
let pos=[]
let total=0
nums.forEach((item,index )=> {
if(item%2==1) pos.push(index) //奇数数组
});
let oddNum=pos.length; //奇数的个数
pos.push(nums.length)
pos.unshift(-1)
for(let i=1;i<=oddNum+1-k;i++){
total+=(pos[i]-pos[i-1])*(pos[i+k]-pos[i+k-1])
}
return total
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 删除字符串中的所有相邻重复项 II
给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。在执行完所有删除操作后，返回最终得到的字符串。本题答案保证唯一。
示例：
输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。
2
3
题目链接：https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string-ii/submissions/
# 解法
var removeDuplicates = function(s, k) {
let stack=[]
for(let c of s){
let prev=stack.pop()
if(!prev || prev[0]!=c){
stack.push(prev)
stack.push(c)
}else if(prev.length<k-1){
stack.push(prev+c)
}
}
return stack.join('')
};
2
3
4
5
6
7
8
9
10
11
12
13
14
# 解法二
var removeDuplicates = function(s, k) {
const reg = new RegExp("([a-z])\\1{" + String(k - 1) + "}");
while (reg.exec(s)) {
s = s.replace(reg, "");
}
return s;
};
2
3
4
5
6
7
# 复原 IP 地址
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
示例：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
2
题目链接：https://leetcode-cn.com/problems/restore-ip-addresses/
# 解法
const restoreIpAddresses = (s) => {
let res=[]
const dfs=(temp,start)=>{
if(temp.length==4 && start==s.length){
res.push(temp.join('.'))
return;
}
if(temp.length==4 && start<=s.length){
return;
}
for(let i=1;i<4;i++){
if(start+i-1>=s.length) return;
if(i!=1 && s[start]=='0') return;
let str=s.substring(start,start+i)
if(i==3 && +str>255) return
temp.push(str)
dfs(temp,start+i)
temp.pop();
}
}
dfs([],0)
return res
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例：
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
2
3
4
5
6
7
题目链接：https://leetcode-cn.com/problems/group-anagrams/
# 解法
var groupAnagrams = function(strs) {
let map=new Map()
for(let item of strs){
let str=item.split('').sort().join('')
let set=map.get(str)?map.get(str):new Array()
set.push(item)
map.set(str,set)
}
return [...map.values()]
};
2
3
4
5
6
7
8
9
10
# 检查一个字符串是否可以打破另一个字符串
给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。
示例：
输入：s1 = "abc", s2 = "xya"
输出：true
解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。
2
3
题目链接：https://leetcode-cn.com/problems/check-if-a-string-can-break-another-string/
# 解法
var checkIfCanBreak = function(s1, s2) {
let len=s1.length
s1=s1.split('').sort()
s2=s2.split('').sort()
let compare=(s1,s2)=>{
for(let i=0;i<len;i++){
if(s2[i].charCodeAt()<s1[i].charCodeAt()){
return false;
}
}
return true
}
return compare(s1,s2)||compare(s2,s1)
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17