算法题-字符串 leetcode

替换空格——字符串的修改 1.
遍历字符串，用新的字符串返回结果
时间，空间复杂化均为O（n）
代码如下

func replaceSpace(s string) string { var res string for _,v:=range s{ if v==' '{ res=res+"%20" }else{ res=res+string(v) } } return res }

效果如下

文章图片

2.
占用内存空间较小的方法
golang中字符串是无法修改的，要对字符串进行操作应将其转化为字符数组
【算法题-字符串】例如

var str string = "hello" strBytes := []byte(str) strBytes[0] = 'H' str = string(strBytes) fmt.Println(str)

题解

func replaceSpace(s string) string { b := []byte(s) length := len(b) spaceCount := 0 // 计算空格数量 for _, v := range b { if v == ' ' { spaceCount++ } } // 扩展原有切片 resizeCount := spaceCount * 2 tmp := make([]byte, resizeCount) b = append(b, tmp...) i := length - 1 j := len(b) - 1 for i >= 0 { if b[i] != ' ' { b[j] = b[i] i-- j-- } else { b[j] = '0' b[j-1] = '2' b[j-2] = '%' i-- j = j - 3 } } return string(b) }作者：carlsun-2 链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/solution/jian-zhi-offer-05-ti-huan-kong-ge-shuang-cgk3/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

效果

文章图片

可见内存得到了一定的优化
3.
库函数

Replace返回字符串s的前n的副本非重叠实例旧替换为新。如果old为空，则匹配字符串的开头在每个UTF-8序列之后，产生多达k+1个替换对于k-rune字符串。如果n < 0，则不限制替换次数。

源码如下

文章图片

func replaceSpace(s string) string{ return strings.Replace(s," ","%20",-1) }

字符串的排列——字符、字符串及其切片，字符串的遍历 ————回溯/剪枝/动态规划
1.
回溯

func permutation(str string) []string { if len(str) == 0 { return nil } newStr := []string{} // 将字符串转换成字符串切片，方便排序 for _, value := range str { newStr = append(newStr, string(value)) } result := []string{} sort.Strings(newStr) dfsPermutation(newStr, 0, &result) return result }// 回溯函数实现 // i表示本次函数需要放置的元素位置 func dfsPermutation(str []string, i int, result *[]string) { n := len(str) if i == n-1 { var tmp string //tmp := make([]string, n) //copy(tmp, str) //tmp = append(tmp, value) for _, value := range str { tmp += value } *result = append(*result, tmp) return } // nums[0:i]是已经决定的部分，nums[i:]是待决定部分，同时待选元素也都在nums[i:] for k := i; k < n; k++ { // 跳过重复数字 if k != i && str[k] == str[i] { continue } str[k], str[i] = str[i], str[k] dfsPermutation(str, i+1, result) } // 还原状态 for k := n - 1; k > i; k-- { str[i], str[k] = str[k], str[i] } }

2.
动态规划
每次添加一个新的字符

文章图片

代码

func permutation(s string) []string { length := len(s) mp, pre, result := make(map[string]int), make([]string, 0), []string{string(s[0])} for i := 1; i < length; i++ { for _, str := range result { ll := len(str) for j := 0; j <= ll; j++ { temp := str[:j] + string(s[i]) + str[j:] if _, OK := mp[temp]; !OK { mp[temp]++ pre = append(pre, temp) } } } result, pre = pre, make([]string, 0) } return result }