CodingTour
ARTS #168

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,才值得被大家追随。