代码如下
func reverseWords(s string) string {
b := []byte(s)
slowindex,fastindex := 0,0 //设置两个指着,快慢指针
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] //如果慢指针的前一个元素不是空格,则直接取到慢指针之前一个元素即可
}
reverse(&b,0,len(b)-1) //先反转一次字符串
i := 0 //i表示的是单词的起始位置
for i < len(b) { //遍历字符串
j := i //j表示的是单词的终止位置
for ; j < len(b)&& b[j] != ' ' ; j++ { //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--
}
}
242 有效的字母异位词
代码如下
func isAnagram(s string, t string) bool {
record := [26]int{} //思路如下 每个字母与'a'进行相减,得到ASCII码的差值,而 record[s[i]-'a']代表每个不同的字母,并记录每个字母的个数
for i := 0 ; i < len(s) ; i++ {
record[s[i]-'a']++
}
for i := 0 ; i <len(t) ; i++ { //遍历另一个字符串,如果字母个数相同则返回TRUE
record[t[i]-'a']--
}
if record == [26]int{}{
return true
}else {
return false
}
}
0-1 背包问题
代码如下
package main
import "fmt"
func main() {
weight := []int{1, 3, 4} //设置每个物品的重量,物品的数量等于weight数组的长度
value := []int{15, 20, 30}
bagweight := 4
dp := make([][]int, len(weight)) //数组大小为物品数量
for i := 0; i < len(dp); i++ { //建立一个物品与背包重量的二维数组
dp[i] = make([]int, bagweight+1)
}
for j := weight[0]; j <= bagweight; j++ { //初始化,从背包等于物品0的重量,到总的背包重量
dp[0][j] = value[0]
}
for i := 1; i < len(weight); i++ {
for j := 0; j <= bagweight; j++ {
if j < weight[i] { //如果背包重量小于当前物品重量,则不放入该物品
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]) //否则,则是在不放与放之间取一个最大值,且如果要放这个物品,那么之前背包的最大值应该是当前背包容量减去该物品的容量,在这个容量之下,i-1个物品的最大价值
}
}
}
fmt.Println(dp[len(weight)-1][bagweight])
}
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}