Golang每日一练(leetDay0051) 颠倒字符串里的单词I\II、乘积最大子数组

package main
import (
  "fmt"
  "strings"
)
func reverseWords(s string) string {
  var res []string
  words := strings.Split(s, " ")
  for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
    words[i], words[j] = words[j], words[i]
  }
  for _, str := range words {
    str = strings.TrimSpace(str)
    if str != "" {
      res = append(res, str)
    }
  }
  return strings.Join(res, " ")
}
func main() {
  fmt.Println(reverseWords("the sky is blue"))
  fmt.Println(reverseWords("  hello world  "))
  fmt.Println(reverseWords("a good   example"))
}

package main
import (
  "bytes"
  "fmt"
)
func reverseWords(s string) string {
  n := len(s)
  i := 0
  words := make([]string, 0, n/3)
  for i < n {
    for i < n && s[i] == ' ' {
      i++
    }
    if i == n {
      break
    }
    j := i + 1
    for j < n && s[j] != ' ' {
      j++
    }
    words = append(words, s[i:j])
    i = j
  }
  for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
    words[i], words[j] = words[j], words[i]
  }
  var buf bytes.Buffer
  for i, s := range words {
    if i > 0 {
      buf.WriteByte(' ')
    }
    buf.WriteString(s)
  }
  return buf.String()
}
func main() {
  fmt.Println(reverseWords("the sky is blue"))
  fmt.Println(reverseWords("  hello world  "))
  fmt.Println(reverseWords("a good   example"))
}

package main
import (
  "fmt"
  "sort"
  "strconv"
  "strings"
)
func largestNumber(nums []int) string {
  var numsStr []string
  for _, num := range nums {
    numsStr = append(numsStr, strconv.Itoa(num))
  }
  sort.Slice(numsStr, func(i, j int) bool {
    return numsStr[i]+numsStr[j] > numsStr[j]+numsStr[i]
  })
  if numsStr[0] == "0" {
    return "0"
  }
  return strings.Join(numsStr, "")
}
func main() {
  nums := []int{10, 2}
  fmt.Println(largestNumber(nums))
  nums = []int{3, 30, 34, 5, 9}
  fmt.Println(largestNumber(nums))
}

package main
import (
  "fmt"
  "math/rand"
  "strconv"
  "strings"
)
func largestNumber(nums []int) string {
  numsStr := make([]string, len(nums))
  for i, num := range nums {
    numsStr[i] = strconv.Itoa(num)
  }
  quickSort(numsStr, 0, len(nums)-1)
  if numsStr[0] == "0" {
    return "0"
  }
  return strings.Join(numsStr, "")
}
func quickSort(nums []string, l, r int) {
  if l >= r {
    return
  }
  pivot := rand.Int()%(r-l+1) + l
  nums[pivot], nums[r] = nums[r], nums[pivot]
  i, j := l-1, l
  for ; j < r; j++ {
    if nums[j]+nums[r] > nums[r]+nums[j] {
      i++
      nums[i], nums[j] = nums[j], nums[i]
    }
  }
  i++
  nums[i], nums[r] = nums[r], nums[i]
  quickSort(nums, l, i-1)
  quickSort(nums, i+1, r)
}
func main() {
  nums := []int{10, 2}
  fmt.Println(largestNumber(nums))
  nums = []int{3, 30, 34, 5, 9}
  fmt.Println(largestNumber(nums))
}

package main
import "fmt"
func maxProduct(nums []int) int {
  n := len(nums)
  if n == 0 {
    return 0
  }
  dpMax := make([]int, n) // 以 i 位置结尾的子数组的最大乘积
  dpMin := make([]int, n) // 以 i 位置结尾的子数组的最小乘积
  dpMax[0], dpMin[0] = nums[0], nums[0]
  for i := 1; i < n; i++ {
    if nums[i] >= 0 {
      dpMax[i] = max(dpMax[i-1]*nums[i], nums[i])
      dpMin[i] = -max(-dpMin[i-1]*nums[i], -nums[i])
    } else {
      dpMax[i] = max(dpMin[i-1]*nums[i], nums[i])
      dpMin[i] = -max(-dpMax[i-1]*nums[i], -nums[i])
    }
  }
  // 返回 dpMax 数组中的最大值
  res := dpMax[0]
  for i := 1; i < n; i++ {
    if dpMax[i] > res {
      res = dpMax[i]
    }
  }
  return res
}
func max(x, y int) int {
  if x > y {
    return x
  }
  return y
}
func main() {
  nums := []int{2, 3, -2, 4}
  fmt.Println(maxProduct(nums))
  nums = []int{-2, 0, -1}
  fmt.Println(maxProduct(nums))
}