| ~ |

当前状况

在 Jekyll 版本的 NexT 主题上做了若干修改. 目前初步搬运完成, 还需要进一步 debug.

线下使用 VNote 写作, 目前发现的和线上 md 的区别:

  • 链接 [discription](url) 描述中如果有 | 的话线上会编译成 table, 需要转义.
Read more »

| ~ |

制作流程和基本知识

Read more »

| ~ |

Months ago I came across an article on the methods of shuffling cards in TCG tournaments. Given limited time in a match, the author, hyakkoTCG@hyakko_tcg sought a way to mix a deck thoroughly by shuffling three times. However, at least to me, it is obvious that the methodology proposed is fundamentally flawed. Later I found out in surprise that the article was widely disseminated: it got 2.3k retweets and 3.1k likes on twitter.

Read more »

| ~ |

本系列起始于 2019 年夏天, 目的是记录自己学习厨艺的过程, 尽量把烹饪流程拆分成原子操作, 并探究其原理. 不过因为实践的次数极少所以进展龟速, 另外原理部分我是外行, 全靠查资料, 这进一步拖慢了进度. 姑且先发出来之后慢慢填坑.

Read more »

| ~ |

LeetCode 847. Shortest Path Visiting All Nodes

2020/7/19

广度优先搜索.

一个 trick 是可以用二进制数表示访问过的节点, 1 表示访问过, 0 表示未访问过. 比如一共 5 个节点 (0-indexed), 则可以用 11001 表示访问过节点 0, 3, 4. 位运算 1<<n 比 2**n 快得多.

from collections import deque

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        '''
        binary representation
        e.g. 11001 for nodes 034 visited and 12 unvisited
        '''
        goal = (1<<len(graph)) - 1
        # (curr_node, visited_nodes, steps)
        queue = deque((node, 1<<node, 0) for node in range(len(graph)))
        seen = set()
        while queue:
            curr_node, visited_nodes, steps = queue.popleft()
            if visited_nodes == goal:
                return steps
            for adj_node in graph[curr_node]:
                state = (adj_node, visited_nodes | 1<<adj_node, steps+1)
                if state not in seen:
                    seen.add(state)
                    queue.append(state) 
        return -1
Read more »

| ~ |

要求 $a^n$, 其中 $a\in\mathbb R$, $n\in\mathbb Z$. 先不妨假设 $n\ge 0$, 基本想法是

\[a^n = \begin{cases} a^{n/2}a^{n/2}, & \text{if $n$ is even,}\\ a^{(n-1)/2}a^{(n-1)/2}a, & \text{if $n$ is odd.} \end{cases}\]

很容易写出时间复杂度 $O(\log n)$ 的递归算法, 而要写迭代算法需要再想一想.

Read more »