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
