Algorithm
本周选择的算法题是：Rotate List
规则
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Constraints:
- The number of nodes in the list is in the range
[0, 500]. -100 <= Node.val <= 1000 <= k <= 2 * 109
Solution
原始解法：
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
length, temp = 0, head
while temp:
length += 1
temp = temp.next
if not length: return None
k = k % length
fast, slow = head, head
for _ in range(k):
fast = fast.next
while fast.next:
fast, slow = fast.next, slow.next
fast.next = head
root = slow.next
slow.next = None
return root
循环次数可以进一步优化：
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head: return None
length, fast = 1, head
while fast.next:
length += 1
fast = fast.next
fast.next = head
k = k % length
if k:
for _ in range(length - k):
fast = fast.next
root = fast.next
fast.next = None
return root
- 减少了一个指针
- 将
fast.next = head形成一个环，之后只需要在一个合适的地方打破环即可
Review
How much I made as a really good Engineer at Facebook
一位 Facebook E8 级别的工程师关于自身职业经历的分享，从中可以看出每个阶段要学习的技能是什么，如何找到自己的价值。
作者的成长路径为：
- 成为一名好的工程师
- 成为一名好的 Tech Lead
- 找机会推进产品、产出影响力
Tip
本周工作日少一天，而我又请了一天假，尝试的事物不多，但也有一些成长：
- 内部制品分发平台增加了对安卓高 DPI Icon 的支持
- 尝试做 CocoaPods 多用户缓存共享，但由于内部的 git 操作没有加锁以及对错误的处理，得基于源码做较大的改动，暂时搁置