Algorithm
本周选择的算法题是：Search in Rotated Sorted Array
规则如下：
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Solution
我实现的方案：
Runtime：40 ms，快过 88.41%。
Memory：12.8 MB，低于 100%。
class Solution:
def search(self, nums: List[int], target: int) -> int:
length = len(nums)
if length == 0: return -1
low, high = 0, length - 1
while low < high:
pivot_index = (high + low) // 2
if nums[pivot_index] > nums[high]:
low = pivot_index + 1
else:
high = pivot_index
pivot_index,low, high = low, 0, length - 1
while low <= high:
mid = (low + high) // 2
adjusted_mid = (mid + pivot_index) % length
if nums[adjusted_mid] == target:
return adjusted_mid
elif nums[adjusted_mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
要求是 O(log n) 的解法，下意识就是先找到旋转点，再调整索引值或者从两边搜索。
解法二
class Solution:
def search(self, nums: List[int], target: int) -> int:
length = len(nums)
low, high = 0, length - 1
while low <= high:
pivot_index = (low + high) // 2
pivot = nums[pivot_index] \
if (target < nums[0]) == (nums[pivot_index] < nums[0]) \
else (-math.inf if target < nums[0] else math.inf)
if pivot == target:
return pivot_index
elif pivot > target:
high = pivot_index - 1
else:
low = pivot_index + 1
return -1
很巧妙的做法！
Review
10 Reasons Why Solving Code Puzzles Makes You Smarter
这是一篇关于如何学习的文章。我结合自身思考，觉得有几点很有帮助。
关键词：
- Divide and Conquer
- Embrace the Eureka Moment
- Overcome the Knowledge Gap
Divide and Conquer 在归并排序这类算法中经常出现，把大问题拆分成小问题，把小问题逐个解决。这是解决问题的思路，在解决的过程中，你解决的每一个问题都可以帮助你获得 Eureka 以及跨越 Knowledge Gap。
关键词：
- Improve From Immediate Feedback
- Measure Your Skills
有些习惯之所以难以坚持，很大程度上是因为没有有效的反馈途径，或者反馈的周期太长。好在我们所处的时代特别好，有很多工具可以帮助我们： freeCodeCamp ，The Finxter App。通过反馈，可以测量自己的技能，形成一个良性循环，所以让自己置身于一个反馈即时的学习环境很重要。
Tip
# 显示某个文件或目录的大小
du -sh /path/to/file
# 显示当前目录下所有文件的大小
du -sh ./*
Share
这一周 Django 发布了 3.0 版本，带来了对 ASGI 的支持：