Jacky's blog
wangjiasheng
2021-01-03
目录

双指针

# 5.最长回文子串 (opens new window)

题解：

  • 知识点：双指针

  • 需要考虑两种情况：

    1. c[aba]d（中心点b）
    2. c[abba]d（中心点bb）

  • 指针问题：

    • 考虑越界情况：while(left<right)
    • 考虑指针的移动情况：当左==右时，left--| right++

伪代码：

// 定义两个游标变量【全局变量】，定义function目标就是改变改两个值
// start、maxlength <==> 这个回文子符串
let start = ..;
let maxlength = ..;
// 定义检测回文字符串函数：
function expandCenterAround(left,right){
    while(1.考虑越界问题 && 2.指针移动条件){
        if(检测是否需要更新全局变量){
            更新全局变量
        }
        否则，则移动指针【left--、right++】
    }
}

for(遍历字符串){
	调用两次，两种情况：aba,abba
}
// 根据 start 和 maxlength 去截取该字符串
return s.substring(start, start + maxlength);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
点击查看

参考代码：

var longestPalindrome = function(s) {
    // 极端值考虑，空值和单值a
    if(s.length <=1){
        return s
    }
    // 定义两个游标变量
    let start = 0;
    let maxlength = 1;

    // 定义一个funciton函数，输入left，right，去操控全局变量
    function expandAround(left, right){
        while(left>=0 && right<s.length && s[left] == s[right] ){
            if( right - left + 1 > maxlength){
                maxlength = right - left + 1;
                start = left;
            }
            left-- ;
            right++;
        }
    }
    for(let i = 0;i<s.length;i++){
        // [aba]
        expandAround(i-1,i+1);
        // [abba]
        expandAround(i-1,i);
    }
    console.log(start);
    console.log(maxlength);
    return s.substring(start, start + maxlength);
};
1
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

# 680.验证回文字符串 Ⅱ (opens new window)

题解：

  • 基本结构：同第5题最长回文子串
  • 注意比较与第5题，这里使用的while循环，从外侧往内收，而最长回文子串是从中心往外寻，故需要考虑越界的问题。

伪代码：

// 1. 将[第125的验证回文串]编写成一个函数isPalindrome
// 2. 两次调用函数 isPalindrome(left+1,right) || isPalindrome(left,right-1)
1
2
点击查看

参考代码：

var validPalindrome = function(s) {
// 参考：最长回文字符串

// 第1步：将验证回文子符串编写为一个函数
function isPalindrome(left, right){
    while(left < right){
        if(s[left] !== s[right]){
            return false;
        }else{
            left++;
            right--;
        }
    }
    return true;
}

// 第2步同上：只不过这次步如果 左 != 右不直接返回false，而是进一步进行判断
let left = 0;
let right = s.length - 1;
while(left < right){
    if(s[left] !== s[right]){
        // 不直接返回false
        return isPalindrome(left+1, right) || isPalindrome(left, right-1);
    }else{
            left++;
            right--;       
    }
}
return true;
};
1
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

# 15.三数之和 (opens new window)

知识点：双指针

题解分析

  1. 数组排序：作用当三指针上的数(>/=/<)0时，移动指针即可。

    • 指针移动原则：小于0，则 →start，大于0则←end

  2. 本题核心是三指针，其中第1个指针可以是顺序遍历【for循环 | i=0至倒数第2个索引】原数组。第2和3指针只可能落在区间[i+1, length-2]中，故使用条件循环【while循环| 条件：start < end】

  3. 难点： 指针移动的时候存在的问题，跳过重复值怎么写？

    a. i的指针是由for循环确定的因，for循环的场景：遍历顺序固定，有规律

    ​ 跳过时：只需要做次判断：nums[i] == nums[i-1]即可

    b. 三个指针中只能固定一个指针，其余两个指针是从处i以外的任意指针，范围是[i+1, length-1]内选择两个指针。

    ​ 故：令 start = i +1 , end = length - 1

伪代码

1. 排序
2. for(第1个指针循环遍历，思考遍历范围？)
       定义 start、 end指针
       while(start<end){
    		- if(条件判断：num[i]+num[start]+num[end] 与 0 的关系)
            - >0 ---> 右移start
    		- <0 ---> 左移end
    		- =0 ---> 右移start，左移end,result.push()
		}
	return result
3. 单独考虑重复数组的情况
1
2
3
4
5
6
7
8
9
10
11

参考答案

点击查看 
var threeSum = function(nums) {
    nums.sort(function(a, b) {
        return a - b
    })
    const result = [];
    for (let i = 0; i < nums.length - 2; i++) {
        // 重复问题样例： -1,-1,0,1 跳过第2个-1
        if (i === 0 || nums[i] !== nums[i - 1]) {
            let start = i + 1,
                end = nums.length - 1;
            while (start < end) {
                if (nums[i] + nums[start] + nums[end] === 0) {
                    result.push([nums[i], nums[start], nums[end]]);
                    start++;
                    end--;
                    // -1,0,0,1, 跳过第2个0
                    while (start < end && nums[start] == nums[start - 1]) {
                        start++;
                    };
                    //  -1,0,1,1 跳过第1个1
                    while (start < end && nums[end] == nums[end + 1]) {
                        end--;
                    }
                } else if (nums[i] + nums[start] + nums[end] < 0) {
                    start++;
                } else if (nums[i] + nums[start] + nums[end] > 0) {
                    end--;
                }
            }
        }
    }
    return result
}
1
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

# 153.寻找旋转排序数组中的最小值 (opens new window)

题解：

  • 二分搜索思想

  • 截至条件，即直接找到：mid<mid -1 || mid-1<mid

  • 两个额外情况的考虑

伪代码：

// 极端情况1
// 极端情况2
// 双指针 + 二分搜索
let left, right = ...;
while(left < right){
    let mid = ...;
    // 写：直接找到的条件
    if(直接找到1){return 索引值}
    if(直接找到2){return 索引值}
    
    // 若一下子无法找到，则移动left和right
    if(left和mid比较){
        移动left
    }else{移动right}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
点击查看

参考代码：

var findMin = function(nums) {
    // 例外1：
    if(nums.length === 1){
        return nums[0]
    };
    // 例外2：本身有序，返回初始值
    if(nums[nums.length - 1]>nums[0]){
        return nums[0]
    }

    // 思考的时候：默认：1、存在两个分区 2、默认单分区存在两个值及以上
    left = 0;
    right = nums.length - 1;
    while(left<right){
        // 1. 找到mid值
        let mid = Math.floor((left + right)/2);
        // 2. 找到的条件
        if(nums[mid]>nums[mid+1]){
            return nums[mid+1]
        }
        if(nums[mid]<nums[mid-1]){
            return nums[mid]
        }
        //3. 继续寻找
        if(nums[left] < nums[mid]){
            //说明此时mid在左区域，且在mid右侧
            left = mid + 1 ;
        }else{
            //说明此时mid在左区域，故放弃所有右区域
            right = mid - 1;
        }
    }

};
1
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

# 283.移动零 (opens new window)

题解：

  • 知识点：临时工作区 or 双指针
点击查看

参考代码：

var moveZeroes = function(nums) {
    // 双指针：
    // i指针移动：检测是否当前值为0，若为0不操作，若非0，则压入工作区
    // j指针移动：【临时工作区】
    let j = 0;
    for(let i =0;i<nums.length;i++){
        if(nums[i] === 0 ){
            continue;
        }else{
            // 不为0，则交给j
            nums[j] = nums[i];
            j++; // j多走了一步
        }
    }
    for(let i = j;i<nums.length;i++){
        nums[i] = 0;
    }
    return nums;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 905.按奇偶排序数组 (opens new window)

题解：

  • 知识点：类似快速排序、两头双指针

    左指针和右指针分别在两侧

    更新规则：只有当左奇右偶时，则执行交换操作。

伪代码：

let i = 0, j = 末端;
while(i<j){
    if(四种条件：左odd右even|左odd右odd|左even右even|左even右odd){
        移动索引;
    }
}
return A
1
2
3
4
5
6
7
点击查看

参考代码：

var sortArrayByParity = function(A) {
let i = 0 ; j = A.length - 1;
while(i<j){
    // 偶在前，奇在后
    if(A[i]%2 === 1 && A[j]%2 === 0){
        // 左是奇数，右使偶数，则交换
        [A[i], A[j]] = [A[j], A[i]];
        i++;
        j--;
    }else if(A[i]%2 === 0 && A[j]%2 === 0){
        // 都是偶数
        i++;
    }else if(A[i]%2 === 1 && A[j]%2 === 1){
        // 都是奇数
        j--;
    }else{
        // 左是偶数，右是奇数,正常迭代
        i++;
        j--;
    }
}
return A
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 922.按奇偶排序数组 II (opens new window)

题解：

  • 知识点：交替指针更新

伪代码：

// 注意：非两层for循环，i与j的循环不同步时怎么写?
for(i指针正常+2迭代){
    if(j指针+2迭代，但是注意j指针的终止条件){
        // 找到A[i]奇数，A[j]偶数时交换
    }
}
1
2
3
4
5
6
点击查看

参考代码：

var sortArrayByParityII = function(A) {
// 一偶一奇排序
// 核心：1. i与j都是同侧+2递进，2. i的位置上保证一定未偶数，若不满足，与A[j]位置上的偶数交换
let j = 1;
for(let i=0;i<A.length;i+=2){
    //交换时, A[i]是奇数 A[j]是偶数
	if(A[i]%2 === 1){
		// 奇数
		while(A[j]%2 === 1 && j<A.length){
            // 若A[j]是奇数，则+2寻找，退出循环时是偶数
			j+=2;
		}
		[A[i], A[j]] = [A[j], A[i]];
	}
}
return A;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 844.比较含退格的字符串 (opens new window)

题解：

  • 知识点：指针从后往前遍历
  • 两串子符串，比较S[i]与S[j]是否相等，若不相等就return false
  • 技巧：使用单独变量记录当前字符是否已删除

伪代码：

let i,j = 末端;
while(i和j从后往前迭代){
    while(i>=0){
        if(退格符=0，且当前字符不为"#"){break}
    }
    while(j>=0){
        if(退格符=0，且当前字符不为"#"){break}
    }
   	if(比较S[i]与S[j]){直接return false}；
    否则，正常迭代i与j;
}
迭代结束后，return true;
1
2
3
4
5
6
7
8
9
10
11
12
点击查看

参考代码:

var backspaceCompare = function(S, T) {
let i = S.length - 1,j = T.length - 1;
let backspaceS = 0, backspaceT = 0;
while(i>=0 || j>=0){
	while(i>=0){
		if(S[i] === "#"){
			backspaceS++;
			i--;
		}else if(backspaceS >0){
			backspaceS--;
			i--;
		}else{
			break;
		}
	}
	while(j>=0){
		if(T[j] === "#"){
			backspaceT++;
			j--;
		}else if(backspaceT >0){
			backspaceT--;
			j--;
		}else{
			break;
		}
	}
	if(S[i] !== T[j]){
		return false;
	}
	i--;
	j--;
}
return true;
};
1
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

# 滑动窗口

滑动窗口题目的特性：

  • 与双指针题目类似，滑动窗口的核心点是维护窗口条件满足题目要求
    • 连续
    • 窗口符合一定的条件

# 3.无重复字符 的最长子串 (opens new window)

题解：

  • 核心：滑动窗口

    dhjjabcaksd
---[j--i]--
    1
    2

  • 步骤：

    1. 维护一个滑动窗口，i是滑动窗口末索引,j是滑动窗口的初始索引

    2. 确定滑动窗内的数据条件：不重复连续子串

    3. 具体步骤：

      先移动i直至不满足滑动窗内的条件，再调整j直至满足滑动窗口，之后继续添加i的内容

伪代码：

//1. 设置全局i,j
let i,j = 0;
let maxlength = ...;
for(遍历字符串){
    if(s[i]是否可以加入窗口内){
        若满足条件,则将s[i]加入set中
        更新maxlength;
    }else{
        while(条件同上,s[i]是否可以加入窗口内){
            //通过调整j收缩窗口,使s[i]可以加入(即让i++继续向前移动)
            j++;
        }
        将s[i]继续加入【记忆：s[i]始终需要加入的，所以需要有这步！！】
    }
}
return maxlength;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这道题还有一个技巧：就是如何满足滑动窗口，上面使用set集合的方式。

还可以使用s.indexOf(s[i],minIndex)，巧用 indexOf 第二个参数。

如果indexOf的结果不等于i，则说明字符串有重复，假设存在字符串如:

**a**a**a**("*"为任意其余字符)
-----[j-i]--
1
2

活动窗口下标j应是第2个a下标+1，所以必须还要维护一个指针，让indexOf在这个指针之后查看重复数组，如：

**a**a**a**  ("*"为任意其余字符)
--m--[j-i]-- 
**a**a**a**a**  ("*"为任意其余字符)
-----m--[j-i]-- 
**a**a**a**a**a**  ("*"为任意其余字符)
--------m--[j-i]--
1
2
3
4
5
6

核心代码：

let minIndex = 0 
for(let i = 0; i < s.length; i++){
        if(s.indexOf(s[i], minIndex) < i){
          // 如，一旦发现有两个a，将minIndex更新为第1个a下标+1
          minIndex = s.indexOf(s[i], minIndex) + 1
        }else{
          // 否则，正常更新最大长度
          maxLength = Math.max(maxLength, i - minIndex + 1)
        }
    }
    return maxLength
};
1
2
3
4
5
6
7
8
9
10
11
12
点击查看

参考代码：

var lengthOfLongestSubstring = function(s) {
    if(s.length===0){
        return 0;
    }
    const setJs = new Set();
    let maxlength = 0,i=0,j=0;
    // 滑动窗口
    for(i;i<s.length;i++){
        if(!setJs.has(s[i])){
            // s[i]不在set集中
            setJs.add(s[i]);
            maxlength = Math.max(maxlength,setJs.size); 
        }else{
            // s[i]在数据集中，则移动j，直到当前数据集中没有s[i]
            while(setJs.has(s[i])){
                setJs.delete(s[j])
                j++;
            }
            // 移动窗口：是先移动j确保当前set中没有该值，再加上该值s[i]
            setJs.add(s[i]);
        }
    }
    return maxlength;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

注：没有通过的原因，忘记了let的简化写法

错误：let i,j,maxLength=0

正确：let i=0,j=0,maxLength=0

  • .indexOf()第二个参数的妙用
var lengthOfLongestSubstring = function(s) {
    let minIndex = 0
    let ans = 0 //"alqebriaxvoo"
    for(let i = 0; i < s.length; i++){
        if(s.indexOf(s[i], minIndex) < i){
          // 如，一旦发现有两个a，将minIndex更新为第1个a下标+1
          minIndex = s.indexOf(s[i], minIndex) + 1
        }else{
          // 否则，正常更新最大长度
          maxLength = Math.max(maxLength, i - minIndex + 1)
        }
    }
    return maxLength
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • 还可以借鉴第5题的最长回文子串的搜索方式编写
var lengthOfLongestSubstring = function(s) {
    if(s.length<2){
        return s.length;
    }
    let maxlength = 1;
    let start = s[0];
    function check(s,left,right){
        const dict = new Map;
        for(let i=left;i<=right;i++){
            if(dict.has(s[i])){
                return false;
            }else{
                dict.set(s[i],i);
            }
        }
        return true;
    }
    function maxlongest(left){
        for(let right=left+maxlength;right<s.length;right++){
           if(check(s,left,right)){
               maxlength = Math.max(maxlength,right-left+1);
           }else{
               break;
           }
        }
    }
    for(let i =0;i<s.length;i++){
        maxlongest(i)
    }
    return maxlength
};
1
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

# 187.重复的DNA序列 (opens new window)

题解:

  • 知识点： 固定滑动窗口+ 字典

Map固定写法：

const map = new Map();
if(map.get(str) === undefined or !map.has(str)){
    // 若原先没有，则写
    map.set(str,1);
}else{
    // 若原先有，则取出原先的值+1
    map.set(str,map.get(str)+1);
}
1
2
3
4
5
6
7
8

伪代码：

//初始result变量 + 字典空间
let map,result = ...;
for(循环滑动窗口){
    dna = s.substring(i,i+10);
    if(map.get(dna)的值>1){
    	直接push进result即可
	}
}
1
2
3
4
5
6
7
8
点击查看

参考代码：

var findRepeatedDnaSequences = function(s) {

let map = new Map();
let result = [];
for(let i=0;i+10<=s.length;i++){
    const dna = s.substring(i,i+10);
    // 字典中没有该值
    if(map.get(dna) === undefined){
        map.set(dna,1);
    // 字典若已经有了该值，则直接存入result
    }else if(map.get(dna) === 1){
        map.set(dna,2);
        result.push(dna);
    }else{
        continue;
    }
}
return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 904.水果成篮 (opens new window)

题解：

  • 知识点：滑动窗口

  • map中需要存放两个内容，一是果子的种类，二是当前果子种类对应的最后一个索引。

  • 区别与第3题，j指针不是+1，而是删除map中索引值最小的值。

    for(const [fruit,index] of map){
    minindex <-- Math.min(index)
}
    1
    2
    3

伪代码：

// 全局变量
let i, j = 0 ;
for(i正常更新){
    map中存放key - value
    例外情况：使用while循环，直至满足条件
    while(map.size > 2){
    	核心难点：更新 minIndex 	
        map.delete(tree[minIndex]);
    	更新j 
	}
}
// 最后的结果
return Math.max(result, i - j + 1);
1
2
3
4
5
6
7
8
9
10
11
12
13
点击查看

参考代码：

var totalFruit = function(tree) {
let i = 0,j = 0;
let result = 1;
let map = new Map();
for(i;i<tree.length;i++){
   map.set(tree[i], i);// 此时map = 3
   while(map.size>2){
       let minIndex = tree.length - 1;
       // 此时i的未知不动，更新j的位置[map中最小的索引号 + 1]
        for(const [fruit, index] of map){
            minIndex = Math.min(minIndex, index);
        }
        map.delete(tree[minIndex]); //此时map=2，符合题意要求
        j = minIndex + 1;
   }
   result = Math.max(result, i - j + 1);
}
return result;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
编辑 (opens new window)
#刷题
上次更新: 2022/04/06, 15:04:00
动态规划
递归专题

← 递归专题→

最近更新
01
如何理解浏览器的 user agent 用户代理的含义?
11-05
02
浏览器事件循环机制
10-31
03
浏览器页面渲染机制【2023】
10-15
更多文章>
Theme by Vdoing | Copyright © 2020-2023