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

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

151. 颠倒字符串中的单词 Reverse Words In A String

给你一个字符串 s ,颠倒字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意:输入字符串s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。

示例 1:

输入:s = "the sky is blue"

输出:"blue is sky the"


示例 2:

输入:s = "  hello world  "

输出:"world hello"

解释:颠倒后的字符串中不能存在前导空格和尾随空格。


示例 3:

输入:s = "a good   example"

输出:"example good a"

解释:如果两个单词间有多余的空格,颠倒后的字符串需要将单词间的空格减少到仅有一个。


提示:

  • 1 <= s.length <= 104
  • s 包含英文大小写字母、数字和空格 ' '
  • s至少存在一个 单词

进阶:如果字符串在你使用的编程语言中是一种可变数据类型,请尝试使用 O(1) 额外空间复杂度的 原地 解法。

代码1: string库函数

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"))
}

代码2: bytes缓冲区

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"))
}

输出:

blue is sky the

world hello

example good a


186. 颠倒字符串里的单词 II Reverse Words In A String II

给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

示例 1:

输入:nums = [10,2]

输出:"210"

示例 2:

输入:nums = [3,30,34,5,9]

输出:"9534330"


提示:

  • 单词的定义是不包含空格的一系列字符
  • 输入字符串中不会包含前置或尾随的空格
  • 单词与单词之间永远是以单个空格隔开的

进阶:

使用 O(1) 额外空间复杂度的原地解法。

代码1: 排序

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))
}

代码2: 快速排序

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))
}

输出:

210

9534330


152. 乘积最大子数组 Maximum Product Sub-Array

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32位 整数。

子数组 是数组的连续子序列。

示例 1:

输入: nums = [2,3,-2,4]

输出: 6

解释: 子数组 [2,3] 有最大乘积 6。


示例 2:

输入: nums = [-2,0,-1]

输出: 0

解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。


提示:

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • nums 的任何前缀或后缀的乘积都 保证 是一个 32位 整数

代码:

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))
}

输出:

6

0


最大值、最小值函数的相互替用,如已有:

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

用max()求a,b的最小值:

Min := -max(-a, -b)

反之亦然: Max = -min(-a, -b)


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/


目录
相关文章
|
5月前
|
Shell Linux 算法
Shell编程——弱数据类型的脚本语言快速入门指南
Shell编程——弱数据类型的脚本语言快速入门指南
82 0
Shell编程——弱数据类型的脚本语言快速入门指南
|
5月前
|
Go Linux Shell
Linux 终端命令之文件浏览(2) more
Linux 终端命令之文件浏览(2) more
57 0
Linux 终端命令之文件浏览(2) more
|
5月前
|
Shell 机器学习/深度学习 Linux
Linux 终端操作命令(2)内部命令
Linux 终端操作命令(2)内部命令
50 0
Linux 终端操作命令(2)内部命令
|
1月前
|
Go
Golang语言之管道channel快速入门篇
这篇文章是关于Go语言中管道(channel)的快速入门教程,涵盖了管道的基本使用、有缓冲和无缓冲管道的区别、管道的关闭、遍历、协程和管道的协同工作、单向通道的使用以及select多路复用的详细案例和解释。
53 4
Golang语言之管道channel快速入门篇
|
1月前
|
Go
Golang语言文件操作快速入门篇
这篇文章是关于Go语言文件操作快速入门的教程,涵盖了文件的读取、写入、复制操作以及使用标准库中的ioutil、bufio、os等包进行文件操作的详细案例。
46 4
Golang语言文件操作快速入门篇
|
1月前
|
Go
Golang语言之gRPC程序设计示例
这篇文章是关于Golang语言使用gRPC进行程序设计的详细教程,涵盖了RPC协议的介绍、gRPC环境的搭建、Protocol Buffers的使用、gRPC服务的编写和通信示例。
53 3
Golang语言之gRPC程序设计示例
|
1月前
|
安全 Go
Golang语言goroutine协程并发安全及锁机制
这篇文章是关于Go语言中多协程操作同一数据问题、互斥锁Mutex和读写互斥锁RWMutex的详细介绍及使用案例,涵盖了如何使用这些同步原语来解决并发访问共享资源时的数据安全问题。
43 4
|
1月前
|
Go
Golang语言错误处理机制
这篇文章是关于Golang语言错误处理机制的教程,介绍了使用defer结合recover捕获错误、基于errors.New自定义错误以及使用panic抛出自定义错误的方法。
39 3
|
1月前
|
Go 调度
Golang语言goroutine协程篇
这篇文章是关于Go语言goroutine协程的详细教程,涵盖了并发编程的常见术语、goroutine的创建和调度、使用sync.WaitGroup控制协程退出以及如何通过GOMAXPROCS设置程序并发时占用的CPU逻辑核心数。
27 4
Golang语言goroutine协程篇
|
1月前
|
Prometheus Cloud Native Go
Golang语言之Prometheus的日志模块使用案例
这篇文章是关于如何在Golang语言项目中使用Prometheus的日志模块的案例,包括源代码编写、编译和测试步骤。
25 3
Golang语言之Prometheus的日志模块使用案例
下一篇
无影云桌面