双指针技巧秒杀七道数组题目 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：双指针技巧秒杀七道数组题目

评论礼仪 见这里，违者直接拉黑。

[GreenHandTo]

寻找链表的倒数第 n 个元素那个最后还要判断slow.next是不是Null

[zxs1633079383]

嗯对的. 我加了个判断, 如果下一个 是 最后一个元素. 并且 下一个元素不等于 此行元素. 则 手动 slow 添加下一个单元

[a2247960736]

在最前面判断head是不是空就好了,文中代码也有写

[GreenHandTo]

奥 前面已经返回了。。

[Feyl]

142.环形链表II https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/kuai-man-zhi-zhen-shu-xue-tui-dao-by-yuhhen/ 这个数学证明比较好。

[xiangyueerli]

反转数组c++一行代码{狗头}{狗头}

void reverseString(vector<char>& s) {
        for(int i = 0, j = s.size()-1; i <= j; ++i, --j)    swap(s[i], s[j]);
}

[PeachLuis]

167题，还能使用 二分查找+双指针，更优

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) >>> 1;
            if (numbers[i] + numbers[m] > target) {
                j = m - 1;
            } else if (numbers[m] + numbers[j] < target) {
                i = m + 1;
            } else if (numbers[i] + numbers[j] > target) {
                j--;
            } else if (numbers[i] + numbers[j] < target) {
                i++;
            } else {
                return new int[]{i + 1, j + 1};
            }
        }
        return new int[]{0, 0};
    }
}

[buptcaicai76]

第五题的代码是不是有问题啊

[qiangjin613]

是没问题的， 注意，在 palindrome 方法的 while 条件中，如果 left > 0 是会导致数据越界的；
而 labuladong 中的越界判断是 left >= 0

[billgoo]

27题，左右指针解法

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        curr, tail = 0, len(nums) - 1
        while curr <= tail:
            if nums[curr] == val:
                nums[curr], nums[tail] = nums[tail], nums[curr]
                tail -= 1
            else:
                curr += 1
        return curr

[billgoo]

2022.4.2 mark

[King-Eternal]

第五题代码 是 有问题

[labuladong]

@King-Eternal @buptcaicai76 第五题有啥问题，我把代码复制过去提交通过了啊

[qiangjin613]

是没问题的， 注意，在 palindrome 方法的 while 条件中，如果 left > 0 是会导致数据越界的；
而 labuladong 中的越界判断是 left >= 0

[huahuablog]

打卡2022.4.4

[gzz0204]

这里好像有点问题：”高效解决这道题就要用到快慢指针技巧：我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。“ 应该是先让slow前进一步，再赋值吧

[labuladong]

@gzz0204 嗯，你说的有道理，我改下表述

[Ref-Rain07]

2022.4.17 打卡

[Maxiah]

厉害呀，跟着刷完了双指针的数组题目，感觉越来越得心应手

[Loomione]

c++翻转数组一行代码实现

void reverseString(vector<char>& s) {
        for (int left = 0, right = s.size() - 1; left < right; swap(s[left++], s[right--]));
    }

[Margaretmmh]

第五题为什么是返回s[l+1,r]而不是s[l,r+1]呢？字符串索引不是从0开始的嘛？

[Margaretmmh]

懂了，因为此时的left -=1跑到左边一格，right +=1跑到右边一格去了

[wen-shuai]

牛逼，赞了

[zenyanggongmian1995]

LeetCode80,相较于给的题解 好理解一些
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n <= 2) {
return n;
}

    int slow = 2; // 慢指针从第三个元素开始
   while(fast<nums.length){
       if (nums[fast] != nums[slow - 2]) {
            // 当前元素与慢指针指向的前两个元素不同，可以保留
            nums[slow] = nums[fast];
            slow++;
        }
       fast++;
   }        
    // 数组长度为慢指针的索引 + 1
    return slow;
}

}

[DengQ]

打卡

[TeslaPeer]

删除链表重复节点那不要轻易直接delect，没有new的游离节点会自动回收的，记着new和delete配对就行

[TeslaPeer]

C++

[DreamYuki]

滴，求职卡！

[karlli1976]

关于『5.最长回文串』的优化

根据labuladong的solution（记为S2），最快只能跑到：

Runtime:19 ms, faster than 61.87% of Java online submissions.
Memory Usage:44.1 MB, less than 37.64% of Java online submissions.

但我在leetcode上发现有人用同样的思路，号称是java fastest solution（记为S3，https://leetcode.com/problems/longest-palindromic-substring/solutions/4069931/java-fastest-solution-easy-to-understand-9ms-o-n-memory-o-1/ ），但跑出来的结果是：

Runtime:9 ms, faster than 91.90% of Java online submissions.
Memory Usage:40.7 MB, less than 97.69% of Java online submissions.

为什么同样的思路，跑出来的结果居然可以相差这么远？

比较之下发现差别在于：

1. 回文函数返回值
   S2当中的判断回文函数，返回的是String；而S3的判断回文函数，不返回值，只修改类变量maxLength和start

2. 主函数比较
   由于判断回文函数的返回值不同，S2需要字符串赋值后比较:

res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;

但S3已经在判断回文函数里面进行了比较：

// Calculate length of palindrome and update start and maxLength
    int length = r - l - 1;
    if (length > maxLength) {
        maxLength = length;
        start = l + 1;
    }

3. 提前返回
   S3的主函数循环里面有这一段：

if (maxLength == s.length()) {
    return s.substring(start, start + maxLength);
}

用于判断是否提前结束，非常有用。这段code所提升的性能：

// from:
// Runtime:15 ms, faster than 84.48% of Java online submissions.
// Memory Usage:40.6 MB, less than 99.77% of Java online submissions.
// to:
//  Runtime:9 ms, faster than 91.90% of Java online submissions.
//  Memory Usage:41.4 MB, less than 67.41% of Java online submissions

[ahighmoon]

谢谢分享！

[lawyuhang]

一刷打卡

[hjianming]

为什么第五题中，可以substring(l+1,r)，当遍历到string的最后一位时，执行的是substring(string.length(),string.length())，为什么这里不会报越界错误？

[llnancy]

快慢指针相等时不用交换和其它操作

[DamonEvil]

fast 可以初始化为1，无需和slow一样初始化为0进行比较

[CZT0]

golang中没有三元表达式，用if就好，gpt直接翻译了三元表达式.....

func longestPalindrome(s string) string {
   var res=""
   for i:=0;i<len(s);i++{
     s1:=palindrome(s,i,i)
     s2:=palindrome(s,i,i+1)
     if len(res)<len(s1){
       res=s1
     }
      if len(res)<len(s2){
       res=s2
     }
   }
   return res
}


func palindrome(s string,l,r int)string{
  for l >= 0 && r < len(s) && s[l]==s[r]{
    l--
    r++
  }
  return s[l+1:r]
}

[ahighmoon]

分享一个Leetcode5 最长回文子序列的C++解法，可使用std::function
#include <string> using namespace std; class Solution { public: string longestPalindrome(string s) { if (s.size() < 2) return s; int maxLength = 0, start = 0; auto palindrome = [&](int l, int r) { while (l >= 0 && r < s.size() && s[l] == s[r]) { l--; r++; } if (r - 1 - l > maxLength) { maxLength = r - 1 - l; start = l + 1; } }; for (int i = 0; i < s.size(); ++i) { palindrome(i, i); palindrome(i, i + 1); if (maxLength == s.size()) return s.substr(start, maxLength); } return s.substr(start, maxLength); } };

[smallkaka]

专题结束🔚