双指针学习

移除元素

//快慢指针法
//重点：什么时候进行交换
//当fast位置的值等于val的时候，把fast的值赋值给后面的指针slow
//因为continue的存在，fast和slow正好会差出值恰好为val的偏差
func removeElement(nums []int, val int) int {
    slow:=0
    for fast:=0;fast<len(nums);fast++{
        if nums[fast]==val{
            continue
        }
        nums[slow]=nums[fast]
        slow++
    }
    return slow
}

//如果题目不强求保证元素顺序不变
//可以使用首尾双指针法
//右指针相当于用来换数的
//左指针向右走的过程中一边检查一边交换
func removeElement(nums []int, val int) int {
    left,right:=0,len(nums)-1
    for left<right{
        if nums[left]==val{
            nums[left]=nums[right]
            right--
        }else{
            left++
        }
    }
    return left
}

力扣 LeetCode844. 比较含退格的字符串 - 力扣（LeetCode）

//1.匹配元素可以用栈
//2.可以使用从后往前的双指针，因为是退格，所以需要先看后面是不是#再移动
//3.记录#的个数，然后往前减去
//4.判断条件是，一直到一个字符串的最后留下的一个互相比较，如果不同，
///说明字符串结尾或者中间相同位置的值不一样
///5.如果一个先到达了-1，说明最后字符串长度不一样
func backspaceCompare(s, t string) bool {
    skipS, skipT := 0, 0
    i, j := len(s)-1, len(t)-1
    for i >= 0 || j >= 0 {
        for i >= 0 {
            if s[i] == '#' {
                skipS++
                i--
            } else if skipS > 0 {
                skipS--
                i--
            } else {
                break
            }
        }
        for j >= 0 {
            if t[j] == '#' {
                skipT++
                j--
            } else if skipT > 0 {
                skipT--
                j--
            } else {
                break
            }
        }
        if i >= 0 && j >= 0 {
            if s[i] != t[j] {
                return false
            }
        } else if i >= 0 || j >= 0 {
            return false
        }
        i--
        j--
    }
    return true
}

有序数组的平方

//暴力排序
//时间复杂度n+nlogn
//第一步n，第二步快排nlog n

func sortedSquares(nums []int) []int {
    for i,v:=range nums{
        nums[i]*=v
    }
    sort.Ints(nums)
    return nums
}

//双指针，时间复杂度log n
//根据题目，两边的平方一定比中间的平方大，所以从两头往中间
func sortedSquares(nums []int) []int {
    left,right,n:=0,len(nums)-1,len(nums)-1;
    ans:=make([]int,5,5)
    for left<=right{
        if nums[left]*nums[left]<nums[right]*nums[right]{
            ans[n]=nums[right]*nums[right]
            right--
        }else{
            ans[n]=nums[left]*nums[left]
            left++
        }
        n--
    }
    return ans
}