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

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