15 篇博文 含有标签「双指针」

1、题干​

字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例 1:

输入: 
first = "pale"
second = "ple"
输出: True

示例 2:

输入: 
first = "pales"
second = "pal"
输出: False

2、解题思路​

顺序遍历统计左半边相同字符总数 sl，倒序遍历统计右半边相同字符总数 sr，两字符串最大长度与 sl + sr 之差不大于 $1$ 则返回 true，否则返回 false。

两个字符串长度差值大于 $1$ 则直接返回 false，这一前置判断可有可无

3、代码​

var oneEditAway = function (first, second) {
    if (Math.abs(first.length - second.length) > 1) return false;

    let sl = 0, sr = 0, m = first.length, n = second.length;
    for (let i = 0; i < Math.min(m, n) && first[i] === second[i]; i++) sl++;
    for (let i = m - 1, j = n - 1; sl - 1 < Math.min(i, j) && first[i] === second[j]; i--, j--) sr++;

    return Math.max(m, n) - sl - sr <= 1;
};

4、执行结果​

• 执行用时: 64 ms
• 内存消耗: 42.7 MB

1、题干​

给你一个字符串 s ，根据下述规则反转字符串：

• 所有非英文字母保留在原有位置。
• 所有英文字母（小写或大写）位置反转。

返回反转后的 s 。

示例 1：

输入：s = "ab-cd"
输出："dc-ba"

示例 2：

输入：s = "a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"

示例 3：

输入：s = "Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"

提示

• 1 <= s.length <= 100
• s 仅由 ASCII 值在范围 [33, 122] 的字符组成
• s 不含 '\"' 或 '\\'

2、解题思路​

双指针遍历字符串，左右都是字母时交换位置

3、代码​

var reverseOnlyLetters = function (s) {
    s = [...s];
    for (let l = 0, r = s.length - 1; l < r; l++, r--) {
        while (l < r && !(/[a-z]/i.test(s[l]))) l++;
        while (l < r && !(/[a-z]/i.test(s[r]))) r--;
        [s[l], s[r]] = [s[r], s[l]];
    }
    return s.join('');
};

4、执行结果​

1、题干​

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

示例 1：

输入：s = "loveleetcode", c = "e"
输出：[3,2,1,0,1,0,0,1,2,2,1,0]
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。

示例 2：

输入：s = "aaab", c = "b"
输出：[3,2,1,0]

• 1 <= s.length <= 104
• s[i] 和 c 均为小写英文字母
• 题目数据保证 c 在 s 中至少出现一次

题目简单，但是处理各种边界情况还是有点繁琐，代码量很难压缩，

2、解题思路​

l 和 r 分别表示左边和右边最近出现字符 c 的下标，遍历区间范围 $[l,r)$ 内的字符，记录字符离边界最近的距离即可

注意处理好边界情况

• 左边没有字符 c 时，l 取值为 -Infinity
• 右边没有字符 c 时，r 取值为 Infinity
• 内层循环要控制好 i 的范围，不能越出 $[0,s.length)$ 这个范围

3、代码​

var shortestToChar = function (s, c) {
    const res = [];
    for (let l = -Infinity, r = s.indexOf(c); l < s.length;) {
        for (let i = Math.max(0, l); i < Math.min(s.length, r); i++) {
            res.push(Math.min(r - i, i - l));
        }
        l = r, r = s.indexOf(c, r + 1), r = r < 0 ? Infinity : r;
    }
    return res;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

示例 1：

输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12

示例 2：

输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点

提示：

• 二叉树的节点个数的范围是  [1, 104].
• -104 <= Node.val <= 104
• root 为二叉搜索树
• -105 <= k <= 105

注意：本题与主站 653 题相同： https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

2、解法1​

DFS遍历+哈希查找：DFS遍历所有节点node，在哈希表set中查找是否存在k - node.val，若存在则返回true否则继续遍历直至结束则返回false。

3、代码​

var findTarget = function (root, k) {
    const set = new Set();
    function dfs(node) {
        if (!node) return false;
        if (set.has(k - node.val)) return true;
        set.add(node.val);
        return dfs(node.left) || dfs(node.right);
    }
    return dfs(root);
};

4、复杂度​

时间复杂度：$O(n)$

空间复杂度：$O(n)$

5、执行结果​

6、解法2​

DFS遍历+DFS二分查找：DFS遍历所有节点node，利用BST特性进行DFS二分查找是否存在k - node.val，若存在则返回true否则继续遍历直至结束则返回false。

这里二分搜索的时间复杂度受到二叉树平衡性的影响，最坏情况下二叉树可能退化成链表，导致搜索时间复杂度为$O(n)$，总体时间复杂度为$O(n^2)$

7、代码​

var findTarget = function (root, k) {
    function find(node, num) {
        if (!node) return false;
        if (num === node.val) return true;
        return num > node.val ? find(node.right, num) : find(node.left, num);
    }

    function findSum(node, num) {
        if (!node) return false;
        return (num !== 2 * node.val && find(root, num - node.val)) || findSum(node.right, num) || findSum(node.left, num);
    }

    return findSum(root, k);
};

8、复杂度​

时间复杂度：平衡二叉搜索树的情况下为$O(nlogn)$ ，非平衡二叉搜索树的情况下超过$O(nlogn)$，最差为$O(n^2)$

空间复杂度：$O(1)$

9、执行结果​

1、题干​

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

• ages[y] <= 0.5 * ages[x] + 7
• ages[y] > ages[x]
• ages[y] > 100 && ages[x] < 100

否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

示例 1：

输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。

示例 2：

输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。

示例 3：

输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

提示：

• n == ages.length
• 1 <= n <= 2 * 104
• 1 <= ages[i] <= 120

2、题目分析​

• 交友年龄限制的限制条件转换后，可以理解为：对于任意年龄ages[x]，交友范围的区间是(0.5 * ages[x] + 7,ages[x]]；
• 由交友范围还可推断出，年龄15岁以下的用户交友范围区间是空集，因此后续编码时可以直接排除15岁以下的数据。

3、解法1-计数排序​

对年龄使用计数排序，遍历所有年龄age，累计并更新交友范围区间(0.5 * age + 7,age]内的人数preCount，然后对最终结果res累加当前年龄的交友请求数(preCount - 1) * counts[age]

4、代码​

var numFriendRequests = function (ages) {
    const counts = new Array(121).fill(0);
    for (const age of ages) if (age > 14) counts[age]++;
    let preCount = 0, res = 0;
    for (let age = 15; age < counts.length; age++) {
        if (age % 2 === 0) preCount -= counts[((age - 1) / 2 + 8) >> 0];
        preCount += counts[age];
        res += (preCount - 1) * counts[age];
    }
    return res;
};

代码简要说明

• if (age % 2 === 0) preCount -= counts[((age - 1) / 2 + 8) >> 0]
  • 对于任意年龄age与age-1而言，交友年龄下限分别为counts[(age / 2 + 8) >> 0]、counts[((age - 1) / 2 + 8) >> 0]
  • age为奇数时这两个交友年龄下限相同，age为偶数时交友年龄下限比age-1大1
  • 因此age为偶数时，需要减去age-1的交友下限人数counts[((age - 1) / 2 + 8) >> 0]
• preCount += counts[age]
  • 加上当前年龄用户的数量
• res += (preCount - 1) * counts[age]
  • 当前年龄人数为counts[age]，他们会给交友范围内除自己外的所有人preCount - 1发请求
  • 因此有res += (preCount - 1) * counts[age]

5、执行结果​

6、解法2-二分查找​

先对所有年龄ages进行降序排序，然后遍历所有年龄，对当前年龄的交友年龄下限进行二分查找，累计所有交友请求数。其中，遇到相同年龄时直接跳过并累计其数量same，当年龄不再相同时对最终结果累加same * (same - 1)

该方法存在较多边界条件，处理不当很容易报错，不建议使用该方法实现

7、代码​

var numFriendRequests = function (ages) {
    ages.sort((a, b) => b - a);
    let same = 1;
    return ages.reduce((acc, cur, i) => {
        if (cur === ages[i + 1]) same++;
        if (cur <= 14 || (cur === ages[i + 1] && i !== ages.length - 1)) return acc;

        let l = i + 1, r = ages.length - 1;
        while (l < r) {
            const m = Math.floor((l + r) / 2);
            ages[m] <= cur / 2 + 7 ? (r = m - 1) : (l = m + 1);
        }

        acc += same * (same - 1 + Math.max(0, r - i - (ages[r] > cur / 2 + 7 ? 0 : 1)));
        return (same = 1), acc;
    }, 0);
};

8、执行结果​

执行用时：124 ms 内存消耗：47.3 MB