JS今日份练习题3

今日份练习题

image-20250308010244500

1、无重复字符的最长子串

1
2
3
4
5
6
编写一个函数 lengthOfLongestSubstring(s)，该函数接受一个字符串 s，返回其中不包含重复字符的最长子串的长度。lengthOfLongestSubstring("abcabcbb"); // 返回 3，因为最长的无重复子串是 "abc"
lengthOfLongestSubstring("bbbbb");    // 返回 1，因为最长的无重复子串是 "b"
lengthOfLongestSubstring("pwwkew");   // 返回 3，因为最长的无重复子串是 "wke"
lengthOfLongestSubstring("abcabcbb"); // 返回 3，因为最长的无重复子串是 "abc"
lengthOfLongestSubstring("bbbbb");    // 返回 1，因为最长的无重复子串是 "b"
lengthOfLongestSubstring("pwwkew");   // 返回 3，因为最长的无重复子串是 "wke"

？ 实现思路

1、使用滑动窗口的思路。

2、定义两个指针left和right表示当前窗口的左右边界，同时初始化为索引0,。

3、使用哈希表map记录每个字符上次出现的索引。

4、开始移动右指针，如果元素已经存在于map并且!!!!!!!!上一次出现的位置是在窗口内的（重复元素的索引位置>=left)，就更新左边界left到重复元素的索引位置加一。

5、更新最长窗口距离

？ 关键

最关键的是理解右边界在延长的过程中，如果发现出现了重复元素，要判断该元素的位置是不是在左边界的右边，也就是判断是否在滑动窗口内。满足条件再移动左边界，更新map中记录的元素最新索引。并且比较最长距离。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function lengthOfLongestSubstring(s){
    let left = 0
    let map = {}
    let max_length = 0
    for (let right = 0; right < s.length; right++){
        let char = s[right]
        if (char in map && map[char] >= left){
            left = map[char] + 1
        }
        map[char] = right
        max_length = Math.max(max_length,right-left+1)
    }
    return max_length
}

2、最长回文子串

1
2
3
实现一个函数 longestPalindrome(s)，该函数接收一个字符串 s，返回 s 中最长的回文子串。如果存在多个答案，可以返回其中任意一个。
longestPalindrome("babad"); // 输出 "bab" 或 "aba"
longestPalindrome("cbbd");  // 输出 "bb"

？ 实现思路

1、考虑最简单的情况：每个字符都是回文

2、再进一步，如果子串长度为2，只需要判断首尾字符是否相同

3、再复杂一些，子串长度增加到3、4、5等等。去掉首尾后，再判断首尾，再去掉首尾…

4、可以知道，中间子串的回文判断实际上在之前就已经判断过了

5、因此将中间结果进行存储，在判断的时候进行查询

6、使用动态规划，把大问题分解为小问题，存储小问题结果。

7、每次标记新的回文后，记得更新最长子串的信息（起始位置、子串长度）！！

二维数组

dp[i][j]表示子串起始位置索引为 i ，结束位置索引为 j ，该子串的回文判断。

const dp = Array.from({length:n},()=>Array(n).fill(false))

使用类数组对象创建新的数组实例，映射函数对于生成的数组中每个元素进行处理，每个元素通过Array(n)生成，并且被填充为false。

解答

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
35
36
37
38
39
40
41
42
43
44
45
function longestPalindrome(s){
    const n = s.length // 字符串长度
    // 最长回文子串的起始位置
    let start = 0
    // 最长回文子串的长度
    let maxLength = 1
    // 如果输入是空字符串，返回""
    if (n < 1){
        return ""
    }
    // 初始化动态规划表
    const dp = Array.from({length:n},()=>Array(n).fill(false))
    // 单个字符情况
    for (let i = 0; i < n; i++){
        dp[i][i] = true
    }
    // 两个字符情况
    for (let i = 0; i < n - 1; i++){
        // 判断是否是回文
        if(s[i] === s[i+1]){
            // 如果是回文就标记
            dp[i][i+1] = true
            // 更新最长回文子串的信息
            start = i
            maxLength = 2
        }
    }
    // 多个长度的情况
    for (let length = 3; length <= n; length++){
        for (let i = 0; i <= n-length; i++){
            // 子串的结束位置
            let j = i + length - 1
            // 首尾是回文，去掉首尾也是回文！
            if (s[i] === s[j] && dp[i+1][j-1]){
                // 标记
                dp[i][j] = true
                // 更新最长回文子串信息
                start = i
                maxLength = length
            }
        }
    }

    return s.slice(start,start+maxLength)
}

3、三数之和

1
2
3
4
5
6
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a, b, c，使得 a + b + c = 0。请你找出所有满足条件且不重复的三元组，并返回这些三元组组成的数组集合。
注意： 答案中不允许包含重复的三元组。
// 示例输入:
const nums = [-1, 0, 1, 2, -1, -4];
// 可能的输出:
[[-1, -1, 2], [-1, 0, 1]]

？ 解题思路

1、排序数组。保证数组的元素是从小到大，使用sort((a,b)=>a-b)，数组元素有顺序后，方便使用双指针

2、固定一个数，在剩余的部分的首尾作为左指针、右指针。需要找到两个指针对应位置的元素之和为固定数的相反数（目标数）。

3、计算当前左右指针和，判断与目标的关系。

4、如果等于目标。左右指针往内移动；如果大于目标，右指针往内移。如果小于目标，左指针往左移。

5、特别注意！！！！！需要考虑重复元素！！！在选择固定数前，先看固定数是不是和前一个固定数重复了，重复就进入下一轮。另外如果找到了目标，在把左右指针往内移动的时候，如果元素依然和上一次相同，继续移动。

解答

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
function threeNumsTotalZero(nums) {
    nums.sort((a,b)=>a-b)
    const n = nums.length;
    const res = []
    for (let i = 0; i <= n -3; i++){
        if (i > 0 && nums[i] === nums[i-1]) continue
        const pinNum = nums[i]
        const target = 0 - pinNum
        let left = i+1
        let right = n-1
        while (left < right){
            if(nums[left] + nums[right] === target){
                res.push([pinNum, nums[left], nums[right]])
                left ++
                right --
                while(left < right && nums[left]===nums[left - 1]){
                    left++
                } 
                while(left < right && nums[right]===nums[right + 1]){
                    right--
                } 
            }
            else if(nums[left] + nums[right] < target){
                left++
            }
            else if(nums[left] + nums[right] > target){
                right--
            }
        }
    }
    return res
}