题目

leetcode:151翻转字符串里的单词
有一点要注意:字符数组注意传指针

题解与分析

方法一

想到的第一个方法是调api,(我是一个冷酷无情的api杀手:smiling_imp:)
先split然后入栈,再组装
然鹅:使用split库函数,分隔单词,然后定义一个新的string字符串,最后再把单词倒序相加,那么这道题题目就失去了它的意义。

class Solution:
    def reverseWords(self, s: str) -> str:
        lis = []
        tmp = s.split(" ")
        for x in tmp:
            if x!=' 'and x!="":
                lis.insert(0, x)
        print(lis)
        ret = " ".join(lis)
        return ret

方法二

这是我没有想到的

  • 先去掉首尾以及中间多余空格
  • 反转整个字符串
  • 找到单词边界,反转单词
    里面有一点要注意,反转单词的时候,最后右边的边界和之前不一样了

移除多余空格时,虽然标注的移除首空格,但那时候并没有移除,只是把fastIndex索引迁移了,在移除中间多余空格的时候才进行移除。
删除尾部空格的时候 可以用切片。

func reverseWords(s string) string {
    slowIndex, fastIndex := 0, 0
    b := []byte(s)
    //1.使用双指针删除冗余的空格
    removeRedundantString(&b, fastIndex, slowIndex)
    fmt.Println("str:'", string(b), "'")

    //2.反转整个字符串
    left, right := 0, len(b)-1
    reverse(&b, left, right)
    fmt.Println("str:'", string(b), "'")
    //3.反转单个单词  i单词开始位置,j单词结束位置
    left, right = 0, 0
    reverseWord(&b, left, right)

    fmt.Println(string(b))
    return string(b)
}
// removeRedundantString 移除多余空格
func removeRedundantString(b *[]byte, fastIndex, slowIndex int) {
    //删除头部冗余空格
    // 实际上这一步并没有删除,他只是移动了索引, 到删除单词间冗余空格才从实际上删除
    for len(*b) > 0 && fastIndex < len(*b) && (*b)[fastIndex] == ' ' {
        fastIndex++
    }
    //删除单词间冗余空格
    for ; fastIndex < len(*b); fastIndex++ {
        if fastIndex-1 > 0 && (*b)[fastIndex-1] == (*b)[fastIndex] && (*b)[fastIndex] == ' ' {
            continue
        }
        // 下面才开始双指针的骚操作,进行删除了
        (*b)[slowIndex] = (*b)[fastIndex]
        slowIndex++
    }

    //删除尾部冗余空格
    // 利用切片来删除
    if slowIndex-1 > 0 && (*b)[slowIndex-1] == ' ' {
        *b = (*b)[:slowIndex-1]
    } else {
        *b = (*b)[:slowIndex]
    }
}
// reverseWord 反转单词
func reverseWord(b *[]byte, left, right int) {
    for left <= right && right <= len(*b)-1 {
        if (*b)[right] == ' ' || right == len(*b)-1 {
            // 因为最后右边的边界和之前不一样了
            if right == len(*b)-1 {
                right += 1
            }
            reverse(&*b, left, right-1)
            left = right + 1
        }
        right++
    }
}
// reverse 是反转函数,不管局部还是整体,通杀
func reverse(b *[]byte, left int, right int) {
    for left <= right {
        //b[left], b[right] = b[right], b[left]
        (*b)[left], (*b)[right] = (*b)[right], (*b)[left]
        left++
        right--
    }
}

下面是没有进行封装的代码,方便理解

func reverseWords(s string) string {
    //1.使用双指针删除冗余的空格
    slowIndex, fastIndex := 0, 0
    b := []byte(s)
    //删除头部冗余空格
    // 实际上这一步并没有删除,他只是移动了索引, 到删除单词间冗余空格才从实际上删除
    for len(b)>0&&fastIndex<len(b)&&b[fastIndex]==' '{
        fastIndex++
    }
    //删除单词间冗余空格
    for ;fastIndex<len(b); fastIndex++{
        if fastIndex-1>0&&b[fastIndex-1]==b[fastIndex]&&b[fastIndex]==' '{
            continue
        }
        // 下面才开始双指针的骚操作,进行删除了
        b[slowIndex]=b[fastIndex]
        slowIndex++
    }
    fmt.Println("1 str:'", string(b), "'")
    //删除尾部冗余空格
    // 利用切片来删除
    if slowIndex-1>0&&b[slowIndex-1]==' '{
        b = b[:slowIndex-1]
    }else{
        b = b[:slowIndex]
    }
    fmt.Println("2 str:'", string(b), "'")
    //2.反转整个字符串
    left, right := 0, len(b)-1
    reverse(&b, left, right)
    fmt.Println("str:'", string(b), "'")
    //3.反转单个单词  i单词开始位置,j单词结束位置
    left, right = 0,0
    for left<=right&&right<=len(b)-1{
        if b[right]==' '||right==len(b)-1{
            if right==len(b)-1{
                right+=1
            }
            reverse(&b, left, right-1)
            left = right+1
        }
        right++
    }
    return string(b)
}
func reverse(b *[]byte, left int, right int){
        for left<=right{
            // b[left], b[right] = b[right], b[left]
            (*b)[left], (*b)[right] = (*b)[right], (*b)[left]
            left++
            right--
    }
}


分类: 算法

站点统计

  • 文章总数:313 篇
  • 分类总数:19 个
  • 标签总数:193 个
  • 运行天数:1080 天
  • 访问总数:238869 人次

浙公网安备33011302000604

辽ICP备20003309号