文章目录
- 旋转数组(无重复)的最小值，T153
- 旋转数组的最大值
- 旋转降序数组的最小值
- 旋转数组(重复)的最小值，剑指offer11，T154
- 最大值索引先升序再降序，T852
- 搜索旋转数组(无重复)(返回索引)，T33
- 搜索旋转数组(重复)(返回)True/False），T81
- 搜索旋转数组(重复)(返回最小索引)，面试问题10.03
- 旋转数组，T189
- 颠倒字符串中的单词，T151
旋转数组(无重复)的最小值，T153
题目要点：
nums请返回旋转数组中的最小元素。
class Solution: def findMin(self, nums: List[int]) -> int: n = len(nums) if n == 1: return nums[0] left = 0 right = n - 1 #这是为了获得最小值，而不是和谐target比较只需要保证最后两个比较，两者不需要重叠 while left < right: mid = left (right - left) // 2 #如果包含mid右半边是升序，可以排除在外mid右边的值 #不存在等于的情况 if nums[mid] < nums[right]: right = mid #包含mid左半部分是升序 else: left = mid 1 return nums[left] 旋转数组的最大值
题目：
nums元素值不同，请返回旋转数组中最大元素
def findMax(nums): n = len(nums) if n == 1: return nums[0] left = 0 right = n - 1 while left < right: mid = left + (right - left) // 2 #注意：上一题将nums[mid]和nums[right]比较，mid和right是不可能重合的，所以没有nums[mid]==nums[right]的情况发生，但如果求最大值，mid和left是有可能重合的，为了保证不陷入死循环，必须单独提出该情况。 if mid == left: return max(nums[left],nums[right]) elif nums[mid] > nums[left]: left = mid else: right = mid - 1 return nums[left] nums = [4,5,1,2,3] print(findMax(nums)) 旋转降序数组的最小值
题目要点：
旋转降序排序的数组，求最小值
def findMin(nums):
n = len(nums)
if n == 1:
return nums[0]
left = 0
right = n - 1
while left < right:
mid = left + (right - left) // 2
if mid == left:
return min(nums[left],nums[right])
if nums[mid] < nums[left]:
left = mid
else:
right = mid - 1
return nums[left]
旋转数组（有重复）的最小值，剑指offer11，T154
题目要点：
nums可能存在重复元素，请返回旋转数组的最小元素。
def findMin(nums):
n = len(nums)
if n == 1:
return nums[0]
left = 0
right = n - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[right]:
right = mid
elif nums[mid] > nums[right]:
left = mid + 1
else:
right -= 1
return nums[left]
先升序再降序的最大值索引，T852
题目：先严格升序再严格降序的数组arr【len(arr) >= 3】，找到最大值所在下标。
（可能有重复值）
def findMax(arr):
n = len(arr)
left = 0
right = n - 2
while left < right:
mid = left + (right - left) // 2
if arr[mid] < arr[mid + 1]:
left = mid + 1
else:
right = mid
return left
搜索旋转数组（无重复）（返回索引），T33
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left = 0
right = n - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
搜索旋转数组（有重复）（返回True/False），T81
class Solution:
def search(self, nums: List[int], target: int) -> bool:
n = len(nums)
left = 0
right = n - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return True
if nums[left] == nums[right] == nums[mid]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return False
搜索旋转数组（有重复）（返回最小索引），面试题10.03
def searchTarget(arr, target):
n = len(arr)
left = 0
right = n - 1
while left <= right:
#重点判断
if arr[left] == target:
return left
mid = left + (right - left) // 2
if arr[mid] == target:
right = mid
elif arr[left] == arr[mid] == arr[right]:
left += 1
right -= 1
elif arr[left] <= arr[mid]:
if arr[left] < target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
旋转数组，T189
题目：
给你一个数组，将数组中的元素向右轮转k个位置，其中k是非负数
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
""" Do not return anything, modify nums in-place instead. """
def reverse(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
n = len(nums)
if n == 0:
return
k = k % n
if k == 0 or n == 1:
return
reverse(nums, 0, n - 1)
reverse(nums, 0, k - 1)
reverse(nums, k, n - 1)
颠倒字符串中的单词，T151
（与旋转数组思想相同）
题目：
“the sky is blue"→"blue is the sky”
class Solution:
def reverseWords(self, s: str) -> str:
#去除两端空格
left = 0
right = len(s) - 1
while left <= right and s[left] == ' ':
left += 1
while left <= right and s[right] == ' ':
right -= 1
#去除单词间多个空格
words = []
for i in range(left, right+1):
c = s[i]
if c != ' ':
words.append(c)
elif words[-1] != ' ':
words.append(c)
#翻转整个字符串
def reverse(start, end):
while start < end:
words[start], words[end] = words[end], words[start]
start += 1
end -= 1
start = 0
end = len(words) - 1
reverse(start, end)
#逐个翻转单词
start = 0
end = 0
while end < len(words):
while end < len(words) and words[end] != ' ':
end += 1
reverse(start, end-1)
start = end + 1
end = start
return "".join(words)