LeetCode-算法-双指针-第18天

布衣者

发布于 2021-09-07 11:40:19

2110

发布于 2021-09-07 11:40:19

文章被收录于专栏：布衣者博客

844. 比较含退格的字符串

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。注意：如果对空文本输入退格字符，文本继续为空。

示例 1：输入：S = "ab#c", T = "ad#c" 输出：true 解释：S 和 T 都会变成 “ac”。示例 2：输入：S = "ab##", T = "c#d#" 输出：true 解释：S 和 T 都会变成 “”。示例 3：输入：S = "a##c", T = "#a#c" 输出：true 解释：S 和 T 都会变成 “c”。示例 4：输入：S = "a#c", T = "b" 输出：false 解释：S 会变成 “c”，但 T 仍然是 “b”。

具体题目链接

Python

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        len_s,len_t=len(s)-1,len(t)-1
        num_s,num_t=0,0#字符前#号的次数
        while len_s>=0 or len_t>=0:  #一次将两个字符串遍历          
            while len_s>=0:#判断s字符串
                if s[len_s]=='#':#如果时#号，则代表我将要消除前面的字符
                    num_s+=1#记录#号的次数
                elif num_s>0:#如果记录#的次数大于0，则证明需要消除一个字符。
                    num_s-=1# #号-1
                else:
                    break
                len_s-=1#进行消除一个字符
            while len_t>=0:#于上步骤同理
                if t[len_t]=='#':
                    num_t+=1
                elif num_t>0:
                    num_t-=1
                else:
                    break
                len_t-=1
            if len_s>=0 and len_t>=0:#如果未结束则需要进行比对
                if s[len_s]!=t[len_t]:#如果两个字符不同，则证明字符串不相等
                    return False
            elif len_s>=0 or len_t>=0:
                return False#如果一个字符串结束，但另一个未结束，则证明不相等。
            len_t-=1
            len_s-=1
        return True

思路：双指针，倒序遍历，因为#只会消除前面的字符，因此倒序进行，可以统计#的个数，当遇到字符时则进行跳过#的个数。最后比较两个字符串当前字符是否相等，具体思路可以看注释。

GO

func backspaceCompare(s string, t string) bool {
    return handle(s)==handle(t)
}
func handle(s string) string {
    s1 := []byte{}
    for i := range s {
        if s[i] != '#' {
            s1 = append(s1, s[i])
        } else if len(s1) > 0 {
            s1 = s1[:len(s1)-1]
        }
    }
    return string(s1)
}

思路：先处理字符串，遇到#则弹出一个字符，遇见字符则加入一个字符。

986. 区间列表的交集

给定两个由一些闭区间组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对不相交的，并且已经排序。返回这两个区间列表的交集。形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

示例 1：输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] 输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] 示例 2：输入：firstList = [[1,3],[5,9]], secondList = [] 输出：[] 示例 3：输入：firstList = [], secondList = [[4,8],[10,12]] 输出：[] 示例 4：输入：firstList = [[1,7]], secondList = [[3,10]] 输出：[[3,7]]

具体题目链接

Python

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        intersection=[]
        len_f,len_s,f,s=len(firstList),len(secondList),0,0
        while f<len_f and s<len_s:
            min_num=max(firstList[f][0],secondList[s][0])
            max_num=min(firstList[f][1],secondList[s][1])
            if max_num>=min_num:
                intersection.append([min_num,max_num])
            if firstList[f][1]>secondList[s][1]:#让区间结尾小的，先结束。
                s+=1
            else:
                f+=1
        return intersection

思路：两个区间的交集有以下几种情况。

一个区间全部在另一个区间内。例如interval1=[1,2],interval1=[1,4]=>[1,2]
两个区间只重叠部分。例如interval1=[1,3],interval1=[2,4]=>[2,3]
两个区间不重叠。例如interval1=[1,2],interval1=[3,4]=>[]

规律：交集的开始决定于两个区间开始的最大值，交集的结束决定于两个区间结束的最小值。当交集开始的值大于交集结束的值则是空集。 if firstList[f][1]>secondList[s][1]的意思是两个区间的结束值小的先推出，进行下一个判断。例如firstList = [[0,2],[5,10]],secondList = [[1,5]]，当[0,2]与[1,5]交集后，5>2,则将[0,2]推出，推入[5,10],在于[1,5]取交集。

GO

func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
    intersection:=[][]int{}
    len_f,len_s,f,s:=len(firstList),len(secondList),0,0
    for min_num,max_num:=0,0;f<len_f &&s<len_s;{
        min_num=max(firstList[f][0],secondList[s][0])
        max_num=min(firstList[f][1],secondList[s][1])
        if max_num>=min_num{
            intersection=append(intersection,[]int{min_num,max_num})
        }
        if firstList[f][1]>secondList[s][1]{
            s+=1
        }else{
            f+=1
            }
    }
    return intersection
}
func min(x,y int)int {
    if x<y{
        return x
    }
    return y

}
func max(x,y int)int{
    if x<y{
        return y
        }
    return x
}

思路：同python

11. 盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：输入：height = [1,1] 输出：1 示例 3：输入：height = [4,3,2,1,4] 输出：16 示例 4：输入：height = [1,2,1] 输出：2

具体题目链接

Python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left,right,area=0,len(height)-1,0
        while left<right:
            temp=min(height[left],height[right])*(right-left)
            area=temp if temp>area else area
            if height[left]>height[right]:
                right-=1
            else:
                left+=1
        return area

思路：我们必须知道移动指针的面积的变化情况。我们有两种选择，移动长边或短边，那么我们需要分析两种情况带来的面积变化。移动长边：距离变短，移动长边后可能面临变长或变短，但高度取决于短边，因此面积可以看出只会小于原来的面积。移动短边：距离变短，移动短边后可能面临变长或变短，高度取决于短边，因此面积可能会增加、不变、减少。因此我们只有移动短边才会遇见最大值。

GO

func maxArea(height []int) int {
    area,left,right:=0,0,len(height)-1
    for temp:=0;left<right;{
        temp=min(height[left],height[right])*(right-left)
        if temp>area{
            area=temp
        }
        if height[left]>height[right]{
            right--
        }else{
            left++
        }
    }
    return area
}
func min(x,y int)int {
    if x<y{
        return x
    }
    return y
}

思路：同python

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021年08月19日，如有侵权请联系 cloudcommunity@tencent.com 删除