目录
189. 轮转数组 Rotate Array 🌟🌟
190. 颠倒二进制位 Reverse Bits 🌟
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
189. 轮转数组 Rotate Array
kk示例 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 - 10 <= 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 位无符号整数的二进制位。
提示：
-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
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
 | |
 | |
 | |
 |