Algorithm

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

规则如下：

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.

Determine if you are able to reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 3 * 10^4
0 <= nums[i][j] <= 10^5

Solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        current, max_right, length = 0, 0, len(nums)-1

        for i in range(length):
            if i > max_right: return False
            max_right = max(nums[i] + i, max_right)
            if i == current: current = max_right
        return max_right >= length

Review

Python 3.9

Python官方的 PEP 596 – Python 3.9 Release Schedule 过于零碎，找了一篇脱水性质的文章，摘要如下：

发布周期调整为12个月（每年10月份）
更强大的类型检查支持
字符串类型增加了一些实用方法
字典类型支持 union 操作
…

观察 Python 这门语言未来的走向，比如类型检查从 3.0 一直到 3.9 都在持续增强，可以看出社区对此越来越重视。

Tip

在尝试 macOS 的虚拟化方案中，发现 macOS 的系统设置很难完全禁用睡眠，经过一番寻找后，发现 KeepingYouAwake 这个免费应用可以很完全的解决这个问题。

而它是基于苹果的 caffeinate 来实现的：文档。

这周小小更新了下 CodingTour，改善了 TOC 锚点的跳转位置：在之前的版本中，由于有固定头部的存在，会产生锚点关联的元素被遮挡的现象。本次较为完美的解决了这个问题。

解决方式为：

解析地址栏中的 hash，找出需要跳转到的元素
屏蔽默认行为，以手动跳转代替自动跳转，并在这个过程中加上自定义的偏移值

主要逻辑为：

// 锚点的点击事件
onClick: function(e) {
  e.preventDefault();
  e.stopPropagation();
  
  // 添加一个新的 hash
  history.pushState(null, document.title, location.pathname + e.target.hash);
  jumpToHash();
  return false;
}

// 跳转到指定的 hash 位置
function jumpToHash() {
  if (location.hash.length !== 0) {
    let targetTop = document.getElementById(decodeURI(location.hash).substring(1)).offsetTop - 45;
    window.scrollBy({
      top: targetTop - window.pageYOffset,
      left: 0,
      behavior: 'smooth'
    });
  }
}

// 在页面内手动修改 hash 后更新 offset
$(window).on('hashchange', function(e) {
  e.preventDefault();
  e.stopPropagation();
  jumpToHash();
  return false;
});

// 进入页面时也根据 hash 设置 offset
window.setTimeout(jumpToHash, 0);

这样可以在不修改布局和 CSS 的情况下解决该问题。

顺便附上一段简单的 JavaScript TOC 实现：

(function() {
    window.tocbot = {
        init: function (config) {
            let list = document.createElement("ul");
            list.setAttribute("class", "toc-list");
            
            let headings = document.body.querySelectorAll("h1, h2")
            headings.forEach(heading => {
                let link = document.createElement("a");
                link.setAttribute("href", "#" + heading.id);
                link.setAttribute("class", config.linkClass + " " + "node-name--" + heading.nodeName);
                link.textContent = heading.textContent;

                let item = document.createElement("li");
                item.setAttribute("class", "toc-list-item");
                item.appendChild(link);

                list.appendChild(item);
            });
            document.body.appendChild(list);
        },
    };
})();

Algorithm

Solution

Review

Tip

Share