Pylon PENG

Posted on Edited on In ,

二分法

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

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

使用左开右闭 [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)。

Read more »

Posted on Edited on In ,

题目要求

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

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

Read more »

Posted on Edited on In , ,

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

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

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

Read more »

Posted on Edited on In ,

零、背景

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

Read more »

Posted on Edited on In ,

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
Read more »

Posted on Edited on In ,

描述

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

Posted on Edited on In ,

Description

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

分析

给定一个数组代表每天的气温，查找多少天之后天气比今天更暖和。首先，想到了暴力算法，如下，

  1. 遍历 T
  2. 对于第 i 个元素，另 j = i，从 i 开始往后寻找比 T[i] 大的元素，如果找到则 j - i 为第 i 号元素的目标值
  3. 重复步骤 2 直到最后一位

给定数组为降序排列时，暴力算法复杂度为 O(n^2)，数组的长度在 [1, 30000]，暴力算法可能会超时。迫于没有想到更好的解题思路，只能对暴力算法先做优化，如果数组是升序的，算法复杂都是 O(n)，所以很乐观，主要考虑优化降序的部分。

考虑如下情况，数组先增后降，

下降转折点到末尾数组元素单调递减，因此每个元素后面都不会有大于他们的元素

如果单调递减后有转折点，那么单调递减的部分元素可能会存在

0%