算法题-字符串3.17 leetcode

翻转单词顺序重点
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'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
【算法题-字符串3.17】暂未学会