描述

在给定的 2D 平面 board 中搜索单词 word，可以在垂直相邻和水平相邻方向进行深度搜索，如果找到返回 True，否则返回 False。

1
2
3
4
5
6
7
8
9
10

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

题目描述

https://leetcode.com/problems/subarrays-with-k-different-integers/

给定一个数组 A，求有 k 个不同元素组成的子数组个数。

例如：

1
2
3

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

题目要求

类型 1： 给定两个字符串 s 和 t，找满足某种变化规律的字串/最大字串/最大字串长度等。

类型 2：给定字符串 s，查找满足某种条件的最大/最小窗口。

二分法

今天重新审视了二分法，结合同事的思考认为，

二分的本质是，在一段或多段单调序列里找分界点

使用左开右闭 [l, r) 的模板如下：

1
2
3
4
5
6
7
8
9

def binary_search(l, r):
    while l < r:
        m = l + (r - l) // 2
        if f(m): return m # optional
        if g(m):
            r = m  # new range [l, m)
        else:
            l = m + 1 # new range [m+1, r)
    return l # or not found

m 如果满足查找条件，即 f(m) 返回 true，则查找结束。如果 f(m) 返回 false， 则根据 g(m) 的结果构造新的查找区间。如果新区间在左边，则新的左闭右开区间是 [l, m) 等价于 [l, m-1]；如果新区间在右边，则新的左闭右开是 [m+1, r)。

题目描述

剪切板中初始状态下只有一个字母 ‘A’，只允许复制全部和粘贴全部操作，使用最小的操作步骤得到 n 个字符 ‘A’。

一个健全的、可互操作的 JavaScript Promise 标准 —— 由开发者而定，为开发者而生。

promise代表异步操作的最终结果。Promise 开放的最原始接口是 then 方法，由该方法注册的回调函数来接受 Promise 成功状态（fulfilled）下返回的值或失败状态（rejected）下返回的错误信息。

本规范详细定义了 then 方法的行为，提供了 Promise 可互操作的基础，所有 Promises/A+ 兼容的 Promise 实现都可以参考该规范。因此，该规范是非常稳定的。 尽管 Promises/A+ 组织有时会为了向后兼容而对此规范做小的改动，但只有经过深思熟虑，充分讨论和测试之后，我们才会集成有较大改动的或向后兼容的版本更改。

异步概述

我们知道 JavaScirpt 有单线程和异步的特点，为什么 JavaScript 不使用多线程？为什么 JavaScript 要使用异步？

零、背景

前段时间博主曾经写过一篇文章《Windows 10 配合 Ubuntu 搭建舒适开发环境不完全指北》，文章介绍了如何使用 Windows 配合 Ubuntu 搭建舒适的开发环境，此后博主由于一些个人因素离开了上家公司，加入了目前的公司。不巧的是，新公司默认情况下配置的电脑也是 Windows（后来听说入职之前可以向 HR 申请 MBP，但我没有申请），而且电脑一旦配发，如无损坏需用满三年才能更换，而我特别不喜欢使用 Windows 的 Terminal 工具。一方面是开发环境部署困难，比如安装 Python 你可能需要自行下载 Python 安装镜像然后手动安装，安装完成后可能还需要配置环境变量，几乎所有的开发工具在 Windows 下的安装都是类似的；另一方面是 Terminal 界面丑陋，用户体验较差。即使有 Git Bash，Cmder，PowerShell，choco 等一系列辅助工具，还是无法赢得很多喜欢命令行工具的程序员的青睐， 我也一样。

Description

题目描述

https://leetcode.com/problems/range-sum-of-bst/

给定一颗二叉搜索树，返回节点的值在 L 和 R 之间的所有节点（包括 L 和 R）的和，其中二叉搜索树的所有节点的值唯一。r如下案例：

Example 1:

1
2

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example 2:

1
2

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

描述

https://leetcode.com/problems/word-ladder/

给定两个单词 beginWord ，endWord 和一组单词列表，求从 beginWord 到 endWord 的最短转换序列的长度，其中转换规则如下：

1. 每次只能转换一个字母
2. 每次转换后的单词都必须在给定的单词列表中

分析

如下案例,

1
2
3
4
5
6
7
8
9

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

首先使用（给定的单词和单词列表中的）每个单词作为一个顶点，构建连通图，如果两个顶点之间只相差一个字母，则两点之间可达。作图如下，

显然，问题的本质在于图的搜索，即从 beginWord 起始搜索 endWord，如果找到，返回最小路径，否则返回 0。那么问题分两部：

1. 构建无向图
2. 搜索

求解

1. 列表构建无向图，使用二维 map。其中两个顶点的连通性有他们之间的字母差异数决定，当且仅当两顶点的单词相差 1 个字母时连通。

   1 2 3 4 5 6 7

   grahp = [] wordList.append(beginWord) for x in wordList: if x not in graph: grahp[x] = {} for y in wordList: grahp[x][y] = acessiable(x, y)

   其中 accessiable 函数如下定义：

   1 2 3 4 5 6 7 8 9 10

   def acessiable(a, b): if len(a) != len(b): return False i, diff = 0, 0 while i < len(a): if a[i] != b[i]: diff += 1 i += 1 return diff == 1