Golang每日一练(leetDay0064) 轮转数组、颠倒二进制位

简介: Golang每日一练(leetDay0064) 轮转数组、颠倒二进制位

189. 轮转数组 Rotate Array


给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。


示例 1:


输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]


解释:

向右轮转 1 步: [7,1,2,3,4,5,6]

向右轮转 2 步: [6,7,1,2,3,4,5]

向右轮转 3 步: [5,6,7,1,2,3,4]


示例 2:

输入:nums = [-1,-100,3,99], k = 2

输出:[3,99,-1,-100]


解释:  

向右轮转 1 步: [99,-1,-100,3]

向右轮转 2 步: [3,99,-1,-100]


提示:

   1 <= nums.length <= 10^5

   -2^31 <= nums[i] <= 2^31 - 1

   0 <= k <= 10^5


进阶:

   尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。

   你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

代码1: 循环暴力

package main
import "fmt"
func rotate(nums []int, k int) {
  n := len(nums)
  k %= n
  for i := 0; i < k; i++ {
    last := nums[n-1]
    for j := n - 1; j > 0; j-- {
      nums[j] = nums[j-1]
    }
    nums[0] = last
  }
}
func main() {
  nums := []int{1, 2, 3, 4, 5, 6, 7}
  rotate(nums, 3)
  fmt.Println(nums)
  nums = []int{-1, -100, 3, 99}
  rotate(nums, 2)
  fmt.Println(nums)
}


代码2: 反转数组

package main
import "fmt"
func rotate(nums []int, k int) {
  n := len(nums)
  k %= n
  // 整个数组反转
  reverse(nums, 0, n-1)
  // 前k个元素反转
  reverse(nums, 0, k-1)
  // 后n-k个元素反转
  reverse(nums, k, n-1)
}
func reverse(nums []int, left, right int) {
  for left < right {
    nums[left], nums[right] = nums[right], nums[left]
    left++
    right--
  }
}
func main() {
  nums := []int{1, 2, 3, 4, 5, 6, 7}
  rotate(nums, 3)
  fmt.Println(nums)
  nums = []int{-1, -100, 3, 99}
  rotate(nums, 2)
  fmt.Println(nums)
}


代码3: 环状替代

package main
import "fmt"
func rotate(nums []int, k int) {
  n := len(nums)
  k %= n
  count := gcd(k, n)
  for i := 0; i < count; i++ {
    curr := i
    prev := nums[curr]
    for j := 0; j < n/count-1; j++ {
      next := (curr + k) % n
      nums[next], prev = prev, nums[next]
      curr = next
    }
    nums[i] = prev
  }
}
func gcd(a, b int) int {
  if b == 0 {
    return a
  }
  return gcd(b, a%b)
}
func main() {
  nums := []int{1, 2, 3, 4, 5, 6, 7}
  rotate(nums, 3)
  fmt.Println(nums)
  nums = []int{-1, -100, 3, 99}
  rotate(nums, 2)
  fmt.Println(nums)
}


输出:

[5 6 7 1 2 3 4]

[3 99 -1 -100]


190. 颠倒二进制位 Reverse Bits


颠倒给定的 32 位无符号整数的二进制位。


提示:


   请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。


   在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在 示例 2 中,输入表示有符号整数 -3,输出表示有符号整数 -1073741825。


示例 1:

输入:n = 00000010100101000001111010011100

输出:964176192 (00111001011110000010100101000000)

解释:输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,

    因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。


示例 2:

输入:n = 11111111111111111111111111111101

输出:3221225471 (10111111111111111111111111111111)

解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,

    因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。


提示:

   输入是一个长度为 32 的二进制字符串

进阶: 如果多次调用这个函数,你将如何优化你的算法?


代码1: 位运算

package main
import "fmt"
func reverseBits(num int) int {
  var result int
  for i := 0; i < 32; i++ {
    result <<= 1
    result |= num & 1
    num >>= 1
  }
  return result
}
func main() {
  n := 0b00000010100101000001111010011100
  n = reverseBits(n)
  fmt.Println(n)
  n = 0b11111111111111111111111111111101
  n = reverseBits(n)
  fmt.Println(n)
}



代码2: 转字符串后反转

package main
import (
  "fmt"
  "strconv"
)
func reverseBits(num int) int {
  s := strconv.FormatInt(int64(num), 2)
  for len(s) < 32 {
    s = "0" + s
  }
  rs := reverseString(s)
  n, _ := strconv.ParseUint(rs, 2, 32)
  return int(n)
}
func reverseString(s string) string {
  runes := []rune(s)
  for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
    runes[i], runes[j] = runes[j], runes[i]
  }
  return string(runes)
}
func main() {
  n := 0b00000010100101000001111010011100
  n = reverseBits(n)
  fmt.Println(n)
  n = 0b11111111111111111111111111111101
  n = reverseBits(n)
  fmt.Println(n)
}


输出:

964176192

3221225471

目录
相关文章
|
3月前
|
Go
Golang语言之数组(array)快速入门篇
这篇文章是关于Go语言中数组的详细教程,包括数组的定义、遍历、注意事项、多维数组的使用以及相关练习题。
38 5
|
4月前
|
监控 Serverless Go
Golang 开发函数计算问题之Go 语言中切片扩容时需要拷贝原数组中的数据如何解决
Golang 开发函数计算问题之Go 语言中切片扩容时需要拷贝原数组中的数据如何解决
|
6月前
|
算法 Java Go
【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)
75 2
|
7月前
|
程序员 Go
第七章 Golang数组和切片
第七章 Golang数组和切片
51 2
|
7月前
|
Shell Linux 算法
Shell编程——弱数据类型的脚本语言快速入门指南
Shell编程——弱数据类型的脚本语言快速入门指南
95 0
Shell编程——弱数据类型的脚本语言快速入门指南
|
7月前
|
Go Linux Shell
Linux 终端命令之文件浏览(2) more
Linux 终端命令之文件浏览(2) more
65 0
Linux 终端命令之文件浏览(2) more
|
7月前
|
Shell 机器学习/深度学习 Linux
Linux 终端操作命令(2)内部命令
Linux 终端操作命令(2)内部命令
68 0
Linux 终端操作命令(2)内部命令
|
7月前
|
C++ 算法 存储
力扣 C++|一题多解之动态规划专题(2)
力扣 C++|一题多解之动态规划专题(2)
64 0
力扣 C++|一题多解之动态规划专题(2)
|
7月前
|
Go
【Golang】使用泛型对数组进行去重
【2月更文挑战第11天】使用泛型对数组进行去重
74 0
|
3月前
|
Go
Golang语言之管道channel快速入门篇
这篇文章是关于Go语言中管道(channel)的快速入门教程,涵盖了管道的基本使用、有缓冲和无缓冲管道的区别、管道的关闭、遍历、协程和管道的协同工作、单向通道的使用以及select多路复用的详细案例和解释。
126 4
Golang语言之管道channel快速入门篇