站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:864 天
  • 访问总数:474698 人次

二分法

基本思路是利用查找中间值,将中间值和target比较,判断,target在左区间还是右区间, 如果nums[mid] > target ,则说明target在左区间

right赋值为mid – 1, 如果nums[mid] > target, 则说明target在右区间,更新left = mid + 1

func search(nums []int, target int) int {
    high := len(nums) - 1
    low := 0
    for low <= high {
        mid := low + (high-low)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] > target {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1
}

双指针法

定义两个指针,快指针可以在for循环 里,不用额外定义。慢指针要定义,两个都从0开始,如果快指针与目标值不相等则每一次慢指针递增一,如果相等,则慢指针停下,快指针在for循环递增,数组当前元素=数组当前索引对应的下一个元素。

func removeElement(nums []int, val int) int {
    l := len(nums)
    //fast := 0
    slow := 0
    for fast :=0; fast<l; fast ++{
        if val != nums[fast]{
            nums[slow] = nums[fast]
            slow ++
        }
    }
    return slow
}

leetcode 26

自己想的比较低效的一种写法
func removeDuplicates(nums []int) int {
    slow := 0
    l := len(nums)
    ln := len(nums)
    if ln == 0{
        return 0
    }
    if ln<2{
        return 1
    }
    for fast :=slow+1; fast<l; fast++{
        if nums[fast]== nums[slow]{
            for i:=slow; i<l-1;i++{
                nums[i] = nums[i+1]

            }
            fmt.Println("---")
            fmt.Println("l:", l)
            if nums[fast]==nums[slow]{
                fast--
                slow--
            }
            l --
        }
        slow ++
    }
    fmt.Println(nums)
    return l
}

借鉴了评论里一个大佬方案
func removeDuplicates(nums []int) int {

    slow := 0
    fast := 1
    l := len(nums)
    if l<2{
        return l
    }
    for fast<l{
        if nums[slow]!=nums[fast]{
            nums[slow+1]=nums[fast]
            slow ++
        }
        fast++
        //l--
    }
    return slow+1
}

对比了一下,我是对比如果相等的情况,而他的是对比不相等的情况,如果不相等那么把当前指针后一个索引的数字赋值为fast指向的数字,然后slow向后移一位,其他情况那么fast继续向后走。
leetcode844

堆栈
func backspaceCompare(s string, t string) bool {
    // 堆栈
    return build(s)==build(t)

}

func build(str string)string{
    s := []byte{}
    for i,v := range str{
        if v != 35{
            s = append(s, str[i])
        }else if len(s)>0{
            // fmt.Println("pop before:", string(s))
            s = append(s[:0], s[:len(s)-1]...)
            // fmt.Println("pop after:", string(s))
        }
    }
    return string(s)
}
双指针法
func backspaceCompare(s string, t string) bool {
    flagS, flagT := 0, 0
    i , j := len(s)-1, len(t)-1
    for i>=0||j>=0 {
        for i >= 0{
            if s[i] == 35 {
                flagS++
                i--
            } else if flagS > 0 {
                flagS--
                i--
            }else {
                // 这个时候说明遇到正常字符,不用去掉的那种,这个时候需要停下,让另一个循环执行, 如果两个字符相等那么继续,不相等直接返回false
                break
            }
        }
        for j >= 0{
            if t[j] == 35 {
                flagT++
                j--
            } else if flagT > 0 {
                flagT--
                j--
            }else{
                break
            }
        }
        if i>=0&&j>=0{
            if s[i]!= t[j]{
                return false
            }
        }else if i>=0||j>=0{
            return false
        }
        // 能坚持到这,说明都是被break了, 没有--
        i--
        j--
    }
    return true
}
分类: go算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

ICP备案号: 辽ICP备20003309号