扭转

题目套路

对指定的类型（数组，单链表，字符串）以指定规则进行扭转。

题目列表和思路：

189. Rotate Array

https://leetcode.com/problems/rotate-array

数组n，扭转次数k,现根据k和n取真实的扭转轴pivot。

然后将整个数组逆转，然后在轴的两边分别扭转。

举例：

nums=[1,2,3,4,5,6,7],k=2,n=7,move=k%n=2

[1,2,3,4,5,6,7]->[7,6,5,4,3,2,1]->[6,7,1,2,3,4,5]

61. Rotate List

https://leetcode.com/problems/rotate-list

思路与上题类似，先使用一个指针fast，计算出链表的长度。

151. Reverse Words in a String

https://leetcode.com/problems/reverse-words-in-a-string

186. Reverse Words in a String II

https://leetcode.com/problems/reverse-words-in-a-string-ii

思路为将整个字符串逆转，然后按照每个单词再逆转

"the sky is blue"->"eulb si yks eht"->"blue is sky the"

要注意，去除多余的空格

153. Find Minimum in Rotated Sorted Array

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array

154. Find Minimum in Rotated Sorted Array II

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii

33. Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array

81. Search in Rotated Sorted Array II

https://leetcode.com/problems/search-in-rotated-sorted-array-ii

在已经被扭转的数组中进行搜索。

思路：先用二分查找找到扭转周pivot，然后再根据pivot的位置计算真实的mid，继续通过二分查找查找需要的元素。

CheckPoint1:怎么找扭转轴

CheckPoint2:找到扭转轴后如何利用真实的mid二分查找