Algorithm
本周选择的算法题是:Split Array into Consecutive Subsequences。
规则
You are given an integer array nums
that is sorted in non-decreasing order.
Determine if it is possible to split nums
into one or more subsequences such that both of the following conditions are true:
- Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
- All subsequences have a length of
3
or more.
Return true
if you can split nums
according to the above conditions, or false
otherwise.
A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5]
is a subsequence of [1,2,3,4,5]
while [1,3,2]
is not).
Example 1:
Input: nums = [1,2,3,3,4,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5
Example 2:
Input: nums = [1,2,3,3,4,4,5,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5
Example 3:
Input: nums = [1,2,3,4,4,5]
Output: false
Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.
Constraints:
1 <= nums.length <= 104
-1000 <= nums[i] <= 1000
nums
is sorted in non-decreasing order.
Solution
class Solution:
def isPossible(self, nums: List[int]) -> bool:
counts = Counter(nums)
tails = Counter()
for num in nums:
if not counts[num]: continue
counts[num] -= 1
if tails[num-1]:
tails[num-1] -= 1
tails[num] += 1
elif counts[num+1] and counts[num+2]:
counts[num+1] -= 1
counts[num+2] -= 1
tails[num+2] += 1
else:
return False
return True
Review
Fear not the Rust Borrow Checker
一篇介绍 Rust 所有权、借用和生命周期标记的文章,文章虽然不长,但条理很清晰,例子也很棒。
Rust 的这三个玩意儿肯定需要花很多时间来理解,一开始上手挺困难的,但是一旦理解了它,这套系统就会成为保障应用稳定的安全网,可以防止许多其他编程语言中常见的问题,特别是相对 C 这种系统级编程语言而言。
Tip
学习数据标准建设过程。
Share
几年前读《如何成为一个大家愿意追随的 Leader?》时,简单做了点笔记:
素质 | 描述 |
---|---|
赢得他人的信任 | 别人愿意向你打开心扉,和你说他心里最柔软的东西,这才是真正的信任 |
开放的心态 + 倾向性的价值观 | 对新生事物要有开放的心态,对每个人的观点要有开放的心态,但并不是要认同所有的观点和事情 |
Lead By Example | 以身作则,展示怎么做,以及 Always Be Coding,要能非常明白一个技术方案的优缺点,实现复杂度,知道什么是最佳实践,你的方案才会更具执行力和实践性 |
保持热情和冲劲 | 正视问题,正视不足,正视错误,从中进行反思和总结得到更好的解决方案 |
能够抓住重点,看透事物的本质 | 作为一个 Leader,能够抓住主要矛盾,看清事物的本质,给出清楚的观点或方向,简化复杂的事情 |
描绘令人激动的方向,提供令人向往的环境 | 一个好的 Leander 一定会把每人人心中最真善美的东西呼唤出来,并且还能让人相信这是有机会有可能做到的 |
甘当铺路石,为他人制造机会 | Leader 不从团队收割成绩,而是给予团队成绩,成就他人其实也是在成就自己 |
这些是一个 “好” Leader 需要具备的软素质,之所以先列出这些,是因为相比技术领导力,软素质更容易被忽视 — 大多数走上 “管理者” 岗位的人,是因其技术水平高而成为 “管理者”,殊不知这样的行为容易使团队得到一名蹩脚的 “管理者” 以及失去一名优秀的工程师。
当然除了软素质外,Leader 还需具备技术领导力:
- 尊重技术,追求核心技术
- 追求高效率的自动化工具和技术,同时避免低效的组织架构和管理动作
- 解放生产力,致力于提高人效
- 能开发抽象和高质量的可重用的技术组件
- 坚持高于社会主流的技术标准和要求
软素质 + 技术领导力,才是能推着事情往前走的 Leader,有自己的 Own 作用域,并为该作用域的结果产出负责,因此既要有推动事情的意愿也要有对应的能力,不断带着大家打胜仗的 Leader,才值得被大家追随。