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