003.轮转数组

• 189.轮转数组
  • 额外数组
  • 反转
  • 环状替换

字符串反转相关题目

• 344.反转字符串
• 541.反转字符串 II
• 剑指 Offer 05.替换空格
  • LCR 122. 路径加密（不是一个题，但力扣删除了剑指 Offer 系列题目）
• 151.反转字符串中的单词
• 剑指 Offer58-II.左旋转字符串
  • LCR 182.动态口令

轮转数组 - 额外数组

func rotate(nums []int, k int)  {
	n := len(nums)
	// 0 索引要轮转到 step 索引位置
	step := k % n
	if step == 0 {
		return
	}
	helper := make([]int, n)
	copy(helper, nums)
	copy(nums[step:n], helper[:n - step])
	copy(nums[:step + 1], helper[n - step:n])
}

轮转数组 - 反转

func rotate(nums []int, k int)  {
	n := len(nums)
	// 0 索引要轮转到 step 索引位置
	step := k % n
	if step == 0 {
		return
	}
	reverse(nums, 0, n)
	reverse(nums, 0, step)
	reverse(nums, step, n)
}
 
// [left, right)
func reverse(nums []int, left, right int) {
	right--
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

轮转数组 - 环状替换

最大公约数

func rotate(nums []int, k int)  {
	n := len(nums)
	// 0 索引要轮转到 step 索引位置
	// 这里没创建新变量 step，而是复用了 k 变量
	k %= n
 
	// 几轮？
	for start, count := 0, gcd(k, n); start < count; start++ {
		cur, curNum := start, nums[start]
		// 走完一轮
		for ok := true; ok; ok = cur != start {
			next := (cur + k) % n
			nums[next], curNum, cur = curNum, nums[next], next
		}
	}
}
 
// 最大公约数
func gcd(a, b int) int {
	for a != 0 {
		a, b = b % a, a
	}
	return b
}