关于leetcode:算法题字符串317

翻转单词程序

重点
1. 删除字符串中冗余的空格

2. 字符串翻转函数

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++
    }
    // 删除尾部冗余空格
    if slowIndex-1 > 0 && b[slowIndex-1] == ' ' {b = b[:slowIndex-1]
    } else {b = b[:slowIndex]
    }
    //2. 反转整个字符串
    reverse(&b, 0, len(b)-1)
    //3. 反转单个单词  i 单词开始地位，j 单词完结地位
    i := 0
    for i < len(b) {
        j := i
        for ; j < len(b) && b[j] != ' '; j++ { }
        reverse(&b, i, j-1)
        i = j
        i++
    }
    return string(b)
}



func reverse(b *[]byte, left, right int) {
    for left < right {(*b)[left], (*b)[right] = (*b)[right], (*b)[left]
        left++
        right--
    }
}

把字符串转换为整数

——自动机 / 正则表达式 / 字符串
——披着字符串皮的其余标签题

func strToInt(str string) int {if len(str)==0{return 0}
    var int32_max=2147483647
    var int32_min=-2147483648
    var sign=1
    var i int
    // 跳过字符头部数值
    for i<len(str)&&str[i]==' '{i++}
    // 如果都是空格，则返回 0
    if i==len(str){return 0}
    // 如果是符号位则 i ++
    if str[i]=='-'||str[i]=='+'{if str[i]=='-'{sign=-1}
        i++
    }
    var res int
    // 开始解决数值
    for i<len(str){
        // 不合乎规定则跳过
        if str[i]<'0'||str[i]>'9'{break}
        // 解决越界的状况
        res=res*10+int(str[i]-'0')
        if res>int32_max{
            if sign==1{return int32_max}else{return int32_min}
        }
        i++
    }
    return sign*res
}

自动机

func strToInt(str string) int {
    var ans int
    var ok bool
    am := &autoMaton{preState: START, flag: 1, ans: 0}
    for i := 0; i < len(str); i++ {if ans, ok = am.calculate(str[i]); !ok {return ans}
    }
    return ans
}



const (
    START int = iota
    SIGN
    NUMBER
    END
)

var m = map[int]map[int]int{START: map[int]int{
        START: START,
        SIGN: SIGN,
        NUMBER: NUMBER,
        END: END,
    },
    SIGN: map[int]int{
        START: END,
        SIGN: END,
        NUMBER: NUMBER,
        END: END,
    },
    NUMBER: map[int]int{
        START: END,
        SIGN: END,
        NUMBER: NUMBER,
        END: END,
    },
    END: map[int]int{
        START: END,
        SIGN: END,
        NUMBER: END,
        END: END,
    },
}

type autoMaton struct {
    preState int
    flag int
    ans int
}

func (am *autoMaton) calculate(c byte) (int, bool) {curState := m[am.preState][am.getCol(c)]
    am.preState = curState
    if curState == END {return am.ans * am.flag, false}
    if curState == NUMBER {k := int(c-'0')
        if am.ans > math.MaxInt32/10 ||
            (am.ans == math.MaxInt32/10 && k > 7) {
            if am.flag < 0 {return math.MinInt32, false} else {return math.MaxInt32, false}
        } else {am.ans = am.ans*10 + k}
    } else if curState == SIGN {
        if c == '-' {am.flag = -1} else {am.flag = 1}
    }
    return am.ans * am.flag, true
}

func (am *autoMaton) getCol(c byte) int {
    if c == ' ' {return START} else if c >= '0' && c <= '9' {return NUMBER} else if c == '+' || c == '-' {return SIGN}
    return END
}

正则 o.o

暂未学会