| ~ |

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 »

| ~ |

第二篇杂录 侧重最佳实践.

最近 (2021/10/28) 发现官方文档有 Programming FAQ — Python 3.10.0 documentation, 很有用.

Misc

一些语法糖

2023/1/10

(1,) + (2, 3)
# (1, 2, 3)

a = {1: 1}
b = {2: 2}
{**a, **b}
# {1: 1, 2: 2}

nonlocal

2022/7/5

忘了看哪个源码的时候读到的

Python の nonlocal と global の違い - Qiita

functools

lru_cache 以及 singledispatch

Read more »

| ~ |

算法分析的那个定理.

Master Theorem

\[T(n) = \begin{cases} \Theta(1), & \text{if } n = 1,\\ aT(n/b) + f(n), & \text{if } n>1. \end{cases}\]

where $a\ge1$, $b>1$ are constants and $f$ is nonnegative. Then

  1. If $f(n) = O(n^{\log_b a-\varepsilon})$ for some constant $\varepsilon >0$, then $T(n) = \Theta(n^{\log_b a})$.
  2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a}\log n)$.
  3. If $f(n) = \Omega(n^{\log_b a+\varepsilon})$ for some constant $\varepsilon >0$, and if $af(n/b)\le cf(n)$ for some constant $c<1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.
Read more »

| ~ |

因为 TeXworks 用了太多年, 不太想换 IDE, 还是继续用了.

参考 官方文档.

文件地址: TeXworks 菜单栏的 “帮助” -> “TeXworks 配置与资源” -> “资源” -> “completion” 文件夹 -> “tw-latex.txt” 文件.

语法

<alias>:=<text>

The <alias>:= part can be omitted to turn the code text into its own alias. <text> must fit in a single line. Empty lines and lines starting with a % are ignored.

第一句话的意思是, 单纯写 blahblah 相当于 blahblah:=blahblah.

<text> 中连续的空格是有效的.

  • #RET# 表示 return, 换行.
  • #INS# 表示 insert, 光标会被放置在此处.
  • • bullet 是 placeholder, 使用 <Ctrl>+<Tab> 让光标移动到下一个占位符处.
Read more »

| ~ |

While this point may seem obvious to the reader, we have seen this blunder committed many times in published papers in top rank journals.

Consider a classification problem with a large number of predictors, as may arise, for example, in genomic or proteomic applications. A typical strategy for analysis might be as follows:

  1. Screen the predictors: find a subset of “good” predictors that show fairly strong (univariate) correlation with the class labels.
  2. Using just this subset of predictors, build a multivariate classifier.
  3. Use cross-validation to estimate the unknown tuning parameters and to estimate the prediction error of the final model.
Read more »

| ~ |

我们考虑一个事件 $A$, 它发生的概率是 $p$. 假设我们观测到事件 $A$ 发生, 我们希望定义一个信息量 $I(p)$ 来衡量 “$A$ 发生了” 这件事给了我们多少信息.

  1. $I(p)$ 是关于 $p$ 的递减函数. 如果事件发生概率高, 而且它发生了, 我们得到的信息应该比较少, 因为我们认为它确实容易发生, 这不稀奇.
  2. 考虑另一个独立的事件 $B$, 它发生的概率是 $q$, 则 $I(pq) = I(p) + I(q)$. 也就是说我们希望独立事件同时发生时提供的信息量应该是他们分别提供的信息量之和.
Read more »