九十六、双指针和滑动窗口算法模板

Python之王

共 17175字,需浏览 35分钟

 ·

2021-09-15 13:18

「@Author:Runsen」

双指针的算法原理,通过两个指针在一个for循环下完成两个for循环的工作。时间复杂度从优化到了

双指针的算法模板比较简单,突破口主要是需要找到题目中的单调性,从而加以利用。

快慢指针

快慢指针一个链表操作技巧,它还有一个有趣的名字,龟兔赛跑。

  • 移除元素:
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};
  • 环的入口位置:应用快慢指针,快指针走两步,慢指针走一步。假使有环,两指针迟早相遇;假使无环,快指针就会走到尽头,退出循环。如果有环,慢指针重新开始,此时快指针是交点,同速两指针交点必是入口。
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        
        if (fast && fast->next){
            slow = head;
            while(slow!=fast){
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
        return nullptr;
    }
};
  • 链表的中间结点:应用快慢指针,快指针走两步,慢指针走一步。快指针走到尽头时,慢指针刚好走了一半,返回即为中间结点。

  • 删除链表的倒数第 N 个结点:快指针先走 n 步,然后快慢指针同时走,快指针走到头时,慢指针就在倒数第 n 个位置。

反向指针

反向指针经典题目是N sum 系列和二分变种题目。

N sum 系列的经典题目是:三数之和

def threeSum(nums):
    nums.sort()
    # [-4, -1, -1, 0, 1, 2]
    res_list = []
    # 头部循环查找
    for i in range(len(nums)):
     #  必须判断 nums[i] > nums[i - 1]这个条件
        if i == 0 or nums[i] > nums[i - 1]:
            # 最左端
            l = i + 1
            # 最右端
            r = len(nums) - 1
            while l < r:  # 正在查找
                three_sum = nums[i] + nums[l] + nums[r]
                if three_sum == 0:
                    res_list.append([nums[i], nums[l], nums[r]])
                    l += 1  # 右移一位
                    r -= 1  # 左移一位
                    while l < r and nums[l] == nums[l - 1]:
                        # 从左往右,相同数值直接跳过
                        l += 1
                    while r > l and nums[r] == nums[r + 1]:
                        # 从右往左,相同数值直接跳过
                        r -= 1
                elif three_sum > 0:
                    # 大于零,右边数值大,左移
                    r -= 1
                else:
                    # 小于零,左边数值小,右移
                    l += 1
    return res_list

在四种二分变种中,根据王争算法专栏中,写死low = 0high = len(list) - 1。循环条件low <= high。往左移动high = mid - 1,往右移动low = mid + 1

def binary_search(nums, target):
 '''标准二分算法模板'''
    low = 0
    high = len(nums) - 1  # 注意1 low和high用于跟踪在其中查找的列表部分
    while low <= high:  # 注意2 只要还没有缩小到只有一个元素,就不停的检查
        mid = (low + high) // 2
        if list[mid] == target:
            return mid
        elif list[mid] > target:
            high = mid - 1  # 注意3 猜的数字大了
        elif list[mid] < target:
            low = mid + 1   # 注意4 猜的数字小了
    return mid


def bsearch_low(nums,target):
    '''求第一个等于定值 '''
    low = 0
    high = len(nums) - 1
    # 这里需要 <=
    while low <= high:
        # 这里需要注意: 就是使用((high - low) >> 1)需要双扩号
        mid = low + ((high - low) >> 1)
        if nums[mid] < target:
            low = mid + 1
        elif nums[mid] > target:
            high = mid - 1
        else:
            if mid == 0 or nums[mid-1] != target:
                return mid
            else:
                high = mid -1

    return -1

def bsearch_high(nums,target):
    '''求最后一个等于定值的'''
    low = 0
    higt = len(nums) -1
    while low <= higt:
        mid = low + ((higt- low) >>1 )
        if nums[mid] > target:
            higt = mid - 1
        elif nums[mid] < target:
            low = mid +1
        else:
            if mid == (len(nums) -1or nums[mid] != nums[mid+1]:
                return mid
            else:
                low = mid +1
    return  -1

'''
查找第一个大于等于给定值的元素
* 如序列:3,4,6,7,19 查找第一个大于5的元素,即为6,return 2
* 第一个大于给定值,则说明上一个小于给定值,依次判断
'''

def bsearch_low_not_less(nums,target):
    low = 0
    high = len(nums) -1
    while(low<=high):
        mid = low + ((high-low) >>1)
        if nums[mid] >= target:
            if mid == 0 or nums[mid - 1] < target:
                return mid
            else:
                # 往左移动
                high = mid - 1
        else:
            # 往右移动
            low = mid +1
    return -1

'''
查找第一个小于给定值的元素
* 如序列:3,4,6,7,19 查找第一个小于5的元素,即为4,返回1
* 第一个大于给定值,则说明上一个小于给定值,依次判断
'''

def bsearch_high_not_greater(nums,target):
    '''求最后一个小于等于值'''
    low = 0
    higt = len(nums) -1
    while low <= higt:
        mid = low + (( higt -low ) >> 1)
        if nums[mid] <= target:
            if (mid == len(nums) -1or (nums[mid + 1] > target):
                return mid
            else:
                low = mid +1
        else:
            higt = mid -1
    return  -1

滑动窗口

原文:https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA

滑动窗口算法是双指针技巧的最高境界,主要用于两个字符串匹配的问题。

掌握了滑动窗口的解题模板可以轻松解决一系列字符串匹配的问题。

下面模板代码来源labuladong,解决LeetCode 76 题,Minimum Window Substring,求最小覆盖子串。

/* 滑动窗口算法框架 */
string minWindow(string s, string t) {
     // 两个unordered_map ,一个need记录模式串的字符数量,一个window记录窗口的字符
    unordered_map<charint> need, window;
    // 初始化need
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    // 两个unordered_map的符合条件数目
    int valid = 0;
    // 记录最小覆盖子串的起始索引及长度
    int start = 0, len = INT_MAX;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (valid == need.size()) {
            // 在这里更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }                    
        }
    }
    // 返回最小覆盖子串
    return len == INT_MAX ?
        "" : s.substr(start, len);
}

在python里unodered map可以用collections.defaultdict和collections.Counter实现


浏览 45
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报