三个月算法进阶--day51
目录
比O(n)更快的就是O(log n)
当O(n)是显而易见的答案时，就要思考二分查找来更快。
pivot中心点
第一次计算可放在循环中
二分防溢出
low + (high - low) // 2
二分防无限循环
至少一个边界在移动的时候不能到pivot，而是需+-1
二分查找防遗漏
如果可以和两个边界比较，那么可只考虑一个来划分全部情况
记录
leetcode剑指offer第11题旋转数组的最小数字
class Solution:
def minArray(self, numbers: List[int]) -> int:
left, right = 0, len(numbers) - 1
while left < right:
pivot = left + (right - left) // 2
if numbers[pivot] < numbers[right]:
right = pivot
elif numbers[pivot] > numbers[right]:
left = pivot + 1
else:
right -= 1
return numbers[left]
找局部匹配即搜索
深搜(回溯、暴力搜索)+剪枝
leetcode剑指offer第12题矩阵中的路径
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(m, n, k):
if m >= len(board) or m < 0 or n < 0 or n >= len(board[0]) or board[m][n] != word[k]:
return False
if k == len(word) -1:
return True
tmp, board[m][n] = board[m][n], "#"
res = dfs(m+1, n, k+1) or dfs(m, n+1, k+1) or dfs(m-1, n, k+1) or dfs(m, n-1, k+1)
board[m][n] = tmp
return res
for i in range(len(board)):
for t in range(len(board[0])):
if dfs(i, t, 0):
return True
return False