Algorithm

本周选择的算法题是：Jump Game II

规则如下：

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

Solution

dp 的思想，加上一些优化策略：

备注录
倒序遍历
result 为 1 时提前结束循环，因为不会有比 1 更少的次数了

class Solution:
    def jump(self, nums: List[int]) -> int:
        end = len(nums) - 1
        if end < 0: return 0

        note = dict()
        def min_jumps_number(start: int) -> int:
            if start == end: return 0
            if nums[start] >= end - start: return 1

            if start in note: return note[start]
            result = float("inf")
            for i in range(nums[start] -1, -1, -1):
                result = min(result, min_jumps_number(start + i + 1))
                if result == 1: break
            result += 1
            note[start] = result
            return result
        return min_jumps_number(0)

上面的解法之所以用 dp 是因为每一步有很多选择，在不确定哪个解是最优解的情况下是比较适用的。

但实际上这题可以用贪心，从局部最优解得出最终解的，只要从每一跳中总是选择能到达的最右边界，忽略区间中的其他值即可：

class Solution:
    def jump(self, nums: List[int]) -> int:
        current, max_right, jumps = 0, 0, 0
        for i in range(len(nums) - 1):
            max_right = max(max_right, i + nums[i])
            if i == current:
                jumps += 1
                current = max_right
        return jumps

Review

How “defer” operator in Swift actually works

从汇编层面分析 Swift defer 的实现方式。

简而言之，return 和 defer 都不是原子操作，return 操作会被拆解成多条指令，并在真正 return 前执行 defer，执行时还处于当前的作用域，函数栈也还没有被弹出。

defer 在很多不同的语言中都有延迟的语义，有时是为了加快速度而延迟执行（比如在 HTML 中），有时是为了方便开发者做一些资源清理工作，提高代码的可读性。

Tip

OSX ld: why does pagezero_size default to 4GB on 64b OSX?

一篇关于 pagezero 段的讨论：

64位系统上不能使用32位指针
如果使用32位指针会触发 trap

一个好玩的手电筒灯光效果，点击下方的按钮进行体验：

关闭暗黑模式效果更好

很简洁的实现:

<style>
  body.dark {
    background-color: black;
    background-image: url(/assets/img/67-flashlight.png);
    background-repeat: no-repeat;
    background-size: 500px 500px;
  }
</style>

<script>
  function updateFlashlight(e) {
    var style = document.body.style;
    style.backgroundPositionX = e.pageX - 250 + "px";
    style.backgroundPositionY = e.pageY - 250 + "px";
  }

  $("#switch_button").click((e) => {
    var body = document.body;
    body.classList.toggle("dark");
    if (body.classList.contains("dark")) {
      updateFlashlight(e);
      ["mousemove", "touchstart", "touchmove", "touchend"].forEach(function(s) {
        document.documentElement.addEventListener(s, updateFlashlight, false);
      });
    } else {
      ["mousemove", "touchstart", "touchmove", "touchend"].forEach(function(s) {
        document.documentElement.removeEventListener(s, updateFlashlight, false);
      });
    }
  });
</script>

Algorithm

Solution

Review

Tip

Share