关于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
}