CodingTour —
ARTS #155

Algorithm

本周选择的算法题是：Coin Change。

规则

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

Solution

# 递归
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def recursive(remainder, cache):
            if remainder < 0: return -1
            if remainder == 0: return 0

            if cache[remainder-1] != 0: return cache[remainder-1]

            min = float("inf")
            for coin in coins:
                res = recursive(remainder - coin, cache)
                if res >= 0 and res < min:
                    min = 1 + res
            
            cache[remainder-1] = -1 if min == float("inf") else min
            return cache[remainder-1]
        
        if amount < 1: return 0
        return recursive(amount, [0] * amount)

# dp
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0: return 0

        ans = [0] + [float('inf')] * amount
        for coin in coins:
            for i in range(coin, amount+1):
                ans[i] = min(ans[i], ans[i-coin]+1)
        
        return ans[-1] if ans[-1] != float('inf') else -1

Review

30-Day Writing Challenge: The Complete Guide on How To Make More Content

作者主要介绍了三部分内容：

  • 设置挑战的好处
  • 如何开启挑战
  • 如何高效执行

在第一部分，作者描述了自己过去一年成功完成的几次写作挑战，并总结了挑战带来的好处：

  • 写作行为本身会更具有生产力

  • 总有可发布的内容(缓冲)
  • 避免惯性忙碌，能更合理规划自己的时间

而要开启一个新的挑战，需要认真做一些准备，作者介绍了 5 条经验：

  1. 选择聚焦的方向、话题
  2. 为每天设置一个可衡量的目标
  3. 为了确保完成每个计划，需要认真评估它的完成周期，有时 30 天的计划可能最终需要 34 天
  4. 把任务分配好，规划到每一天
  5. 允许请假

这句话特别棒：如果你没有做好准备，你就是在准备失败。

在高效执行环节，作者额外介绍了几种有助于提高生产力的工具，比如 5 秒法则、12 Week Year 等，总的来说和番茄工作法类似。

我自己坚持 ARTS 快 3 年了，我认为持续写作的好处主要是 4 点：

  • 公共平台的写作能锻炼自己的沟通能力
  • 公共平台的写作能通过给自己压力，将零散的知识点形成系统性的认识
  • 知识不是死记硬背，持续获取知识的能力更重要
  • 学习需要持续，而成长却看起来不是“持续”的，它不会对学习产生即时反馈，它可能会有某个点突然出现，然后一夜长大，在它长大之前，耐心培育它吧

在职场中，沟通/写作能力其实范围涵盖非常大，且越是高阶的职位，其价值越大。

Tip

验证了在 python3 下基于绝对路径执行指定文件的想法。

Share

关于 OKR 的信心值

信心值概念来自《OKR 工作法》一书，用于衡量目标设立是否科学的工具。

在定目标的时候，OKR 中的目标不要定的太难，太难的目标会令人沮丧，望而却步；也不能够太简单，不努力就可以轻松完成，没有挑战的欲望；有一定难度的目标才是振奋人心的目标。

篮球之所以广受欢迎，和篮球架的高度设计合理有直接关系，因为人 “跳一跳，就够得着”。

信心值作为衡量目标的工具，能借助数字表达，如：5/10 的信心值，表示“ 我有50%的把握达成目标”，1/10 表示“没什么希望”，10/10 表示“这个肯定能搞定“。

在实际应用过程中，可以用不同颜色的信心值来表示目标实现的信心状态：

  • 信心值 3/10 - 低于 4 时，标记为红色
  • 信心值 4/10 - 大于等于 4 时，标记为黄色
  • 信心值 7/10 - 大于等于 7 时，标记为绿色

不同的颜色使目标状态更容易被识别，当它为红色时，我们不应该设置该目标，或许是因为条件不够充分、或者是不适合在当前阶段落地，除非信心值有所提升，否则不应视为当前目标。我们的工作经验、技术调研、业务理解等都只是提高信心值的工具，这也是为什么“调研 xxx” 不能作为 KR 的原因，因为工具是达成手段而不是目的或结果。

目标制定完后不要轻易改变，因为它是一个方向，但信心值是可以在目标达成的过程中动态调整的，此时它变成了跟进工具，当我们获取到的信息越来越多时，或者每个小阶段都顺利完成时，就像是完成了一个又一个的挑战，信心值也会不断提高，直至 10/10，最终实现了一个完整的目标。而如果如果从 8/10 降到了 2/10，你得知道是为什么，是什么发生了变化，这会有助于我们及时跟进和调整状态，保证信心值持续向好。