我命由我,不由天!


  • 搜索
prometheus docker golang linux kubernetes

leetcode-双指针

发表于 2021-07-11 | 0 | 阅读次数 341

409.最长回文子串

image.png
代码:

func longestPalindrome(s string) int {
    var pair := make(map[byte]int)
    for i:=0;i<len(s);i++{
        pair[s[i]]++
    }
    var sum int
    flag := false
    for _,v := range(pair){
        if v % 2 != 0{
            flag = true
            v = v - 1
        }
        sum += v
    }
    if flag {
        sum ++ 
    }
    return sum
}

思路:

  1. 只需返回回文串长度,只要是字符出现的次数为偶数就直接相加,如果有为奇数的,则减1相加,并把标志位置true,最后总的sum加一
  2. 没用到双指针,也没看到题解用双指针,不知道双指针是怎么实现的

125.验证回文串

image.png
代码:

func isPalindrome(s string) bool {
    var a string
    for i:=0;i<len(s);i++{
        if isANum(s[i]){
            a += string(s[i])
        }
    }
    a = strings.ToUpper(a)
    for i,j:=0,len(a)-1;i<j;i++{
        if a[i] != a[j]{
            return false
        }
        j--
    }
    return true
}

func isANum(s byte)bool{
    return (s >='0' && s <= '9') || (s >= 'A' && s <= 'Z') || (s >='a' && s <='z')
}

思路:

  1. 在原字符串上一边遍历一边改变长度不是个好办法,情愿新申请一个变量
  2. 预处理字符串后,使用双指针头尾结合判断
  3. A的ASCII码为65,Z的ASCII码为90,a的ASCII码为97,z的ASCII码为122

5.最长回文子串

image.png

代码:

func longestPalindrome(s string) string {
    maxLen := ""
    for i:=0;i<len(s);i++{
        temLen := ""
        for left,right:=i,i;left >=0 && right <len(s);left--{
            if s[left] != s[right]{
                break
            }
            temLen = s[left:right+1]
            if len(temLen) > len(maxLen){
                maxLen = temLen
            } 
            right++
        }

        temLen = ""    
        for left,right:=i,i+1;left >=0 && right <len(s);left--{
            if s[left] != s[right]{
                break
            }
            temLen = s[left:right+1]
            if len(temLen) > len(maxLen){
                maxLen = temLen
            } 
            right++
        }
    }
    return maxLen
}

思路:

  1. 中心扩散法,从第一个位置开始,两个指针分别向两边扩散,判断是否相等,保存最长的字符串
  2. 有两种情况,一种为偶偶,另种为偶奇偶。扩散的方式不同,需要两种情况

1.两数之和

image.png

代码:

func twoSum(nums []int, target int) []int {
   pair := make(map[int]int)
   for k,v := range(nums){
       if ret,ok := pair[target-v];ok{
           return []int{ret,k}
       }
       pair[v] = k
   }
   return []int{}
}

思路:

  1. 使用target—v来作为查找判断,这个key是否在map里。
  2. index作为map的value,这样直接定位到在数组中的序号

15.三数之和

image.png
代码:

import "sort"

func threeSum(nums []int) [][]int {
    ret := [][]int{}
    sort.Ints(nums)
    for i:=0;i<len(nums);i++{
        if i > 0 && nums[i] == nums[i-1]{
            continue
        } 
        k := len(nums)-1
        target := -1 * nums[i]
        for j:=i+1;j<len(nums);j++{
            if j > i+1 && nums[j] == nums[j-1]{
                continue
            }
            for j < k && nums[k] + nums[j] > target{
                k--
            }

            if k == j{
                break
            }
            if nums[k] + nums[j] == target{
                ret = append(ret,[]int{nums[i],nums[j],nums[k]})
            }
        }
    }
    return ret
}

思路:

  1. 先排序,排完一切好说
  2. 如果两个数是一样的,就跳过
  3. 利用递增的特性,第三圈的时候,把指针移到小于的情况
  4. 直接判断是的话就append
  5. 当j递增的时候,k在回到第三步
  • 本文作者: Dante
  • 本文链接: https://gaodongfei.com/archives/l-e-e-t-c-o-d-e---shuang-zhi-zhen
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
三次握手与四次挥手
两阶段锁及减少行锁对性能影响
  • 文章目录
  • 站点概览
Dante

Dante

119 日志
5 分类
5 标签
RSS
Creative Commons
0%
© 2023 Dante
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
沪ICP备2020033702号