Go Snail

Posted on | In

常用的分解子问题的方式

(n-1) + 1

先得到前n-1个元素的问题的解，再构造新加一个元素后的解。使用这种办法的典型算法为insert sort 。
针对二叉树，就是先分别求在两棵子树上的解，然后再构造原树的解。

这是一种从后向前，缩减问题规模的方式。

leetcode题库中，能使用该方法解决的题有:

  • 344. Reverse String
    先翻转前n-1字符,结果记为res，然后把第n个字符插在res的前面
  • 338. Counting Bits
    分别求每个数m的二进制表示中1的个数。
    这里把输入m看作是n个bit的list。先计算前n-1个bit中1的个数(不妨设为cnt)，如果第n个bit是1，则原问题的解为cnt+1，否则为cnt
  • 104. Maximum Depth of Binary Tree
    先分别计算左子树和右子树的深度，原树深度为其两棵子树的深度的最大值加1。
  • 226. Invert Binary Tree
    先分别翻转左子树和右子树，然后把翻转后的右子树作为其左子树，把翻转后的左子树作为其右子树。
  • 283. Move Zeroes
    先将前n-1个元素中的数字移动到正确的位置。用i记录前n-1个元素中第一个0的index。如果第n个元素为0, 则结束。否则，将第n个元素拷贝到第i个位置。
  • 100. Same Tree
    先看两棵子树的左子树和右子树是否分别相等，是的话，再看两棵树的根的值是否相等，是的话，两棵树相等。否则，不相等。
  • 238. Product of Array Except Self
    先求出前n-1个元素的结果,不妨记为res，然后将结果中的每个元素乘以第n个元素。得到了前n-1个元素的最终结果。第n个元素的结果为res[n-1]乘以第n-1个数。
  • 206. Reverse Linked List
    先将前后n-1个元素的list逆序,得到的结果记为resList，然后把第1个元素连接到resList的末尾。注意要记录逆序后的list的表头和表尾。
  • 328. Odd Even Linked List
    先将后n-2个元素的list按照要求重新排列，再将前两个元素插入到该list中
  • 337. House Robber III
    先求两课子树分别在抢根结点和不抢根结点情况下的最大获益。原树的最大获益分为两种情况：1) 抢劫根结点，获益为两棵子树在不抢根结点情况下的最大获益。2) 不抢劫根结点，获益为两棵子树获益的最大和。取两种情况下的最大值。
  • 70. Climbing Stairs
    走n步到达终点的方法数为，走1步然后再走n-1步的方法数，加上走2步然后再走n-2步的方法数.
  • 89. Gray Code
    n位的格雷码按照以下方法由n-1位的格雷码构造：
    • 前一半的格雷码为n-1位的格雷码最高位添加0
    • 后一半的格雷码为n-1位的格雷码逆序后，最高位添加1
  • 53. Maximum Subarray
    先把原问题加强，求以第i个元素结尾的子序列的最大和。假设以第i-1个元素结尾的子序列的最大和为s(i-1), 那么以第i个元素结尾的子序列的最大和分两种情况:1) 如果s(i-1) < 0, 则为第i个元素 2) 否则，为s(i-1)加上第i个元素的值。
  • 62. Unique Paths
    从坐标(i,j)到达(m,n)的方法数为从(i+1,j)到(m,n)的方法数加上从(i,j+1)到(m,n)的方法数。这里问题的规模为表格的大小。
  • 216. Combination Sum III
    这里问题的规模可以认为是可选数值的个数。求和为n的k个数，有两种方案 1) 取可选数值的第1个数(不妨设为s)，然后从剩下的数中选取k-1数使其和n-s； 2) 不选可选数值的第1个数，然后从剩下的数中选取k个数使其和为n。
  • 46. Permutations
    先确定排列中第一位的数值，然后再拼接上剩下元素的排列即可。
  • 145. Binary Tree Postorder Traversal
    先遍历左右子树，再遍历根结点。
  • 24. Swap Nodes in Pairs
    先将后n-2个结点完成交换，再把前两个结点交换后，插入到链头
  • 64. Minimum Path Sum
    从坐标(i,j)到达(m,n)的最短路径为从(i+1,j)到(m,n)的最短路径与从(i,j+1)到(m,n)的最短路径中的最小值，再加上自己的权值。这里问题的规模为表格的大小。
  • 313. Super Ugly Number
    先得到前n-1个ugly number, 第n个ugly number是前n-1个ugly number分别乘以各个素数值中的最小值。
  • 75. Sort Colors
    先将前n-1个元素调整好顺序，同时记录调整后的序列中第一个不是0的位置i和第一个不是2的位置j:
    • 假如第n个数是0，则按照如下方法调整序列， 将位置i的值放到位置j，将位置j的元素放到位置n, 最后将位置n的值放到位置i. i和j都加1
    • 假如第n个数是1，则按照如下方法调整序列， 将位置j的元素放到位置n, 最后将位置n的值放到位置j. j加1
    • 假如第n个数是2，不调整
  • 107. Binary Tree Level Order Traversal II
    先计算出左子树和右子树的层序遍历结果。然后将之合并。然后将根结点加入。注意，左子树和右子树返回的结果中，第一个元素为最后一层，最后一个元素为其根。
  • 110. Balanced Binary Tree
    当前树为平衡树，要满足以下几点：1) 左右子树均为平衡树 2) 左右子树的高度差至多为1. 所以， 要计算每棵子树的高度。
  • 101. Symmetric Tree
    将原问题加强为判断两棵树是否对称。两棵树t1和t2要对称需要满足：1) t1和t2的根结点的值相等，2) t1的左子树和t2的右子树对称，t1的右子树和t2的左子树对称
  • 118. Pascal’s Triangle
    第n行的Pascal三角由第n-1行构造。构造方式如下：P[n][i]=P[n-1][i-1]+P[n-1][i], 其中，0<i<n
  • 102. Binary Tree Level Order Traversal
    先计算出左子树和右子树的层序遍历结果。然后将之合并。然后将根结点加入。注意，左子树和右子树返回的结果中，第一个元素为根，最后一个元素为最后一层。
  • 129. Sum Root to Leaf Numbers
    将问题转化为求树中所有root到leaf的路径
  • 119. Pascal’s Triangle II
    与118. Pascal’s Triangle 类似，可以从第k行的值得到第k+1行的值。

1 + (n-1)

先从原问题中排除掉一个元素，然后求解剩下n-1个元素问题的解。最后，再构造原问题的解。使用这种方法的典型算法为bubble sort 。

这里缩减问题规模的方式，很特殊，是找到一个特殊的元素，将其减去。

使用这种方法的典型算法为贪心算法。通常，尾递归算法可以归为这一类。

还有一种情况，可以归为这一类。就是，根据第一个元素，分情况讨论。

贪心算法

贪心算法通常选择最值为要去除的那个元素。

leetcode题库中，能使用该方法解决的题有:

根据第一个元素，分情况讨论：

leetcode题库中，能使用该方法解决的题有:

  • 198. House Robber
    如果抢第一家，则只能抢第二家之后的n-2家。如果，不抢第一家，则可以抢第一家之后的n-1家，选择这两种情况的最大值即可。
  • 77. Combinations
    如果选取第一个元素，则从剩下的n-1个元素中选k-1个就可以了。如果不选取第一个元素，则从剩下的n-1个元素选择k个元素。

其它

leetcode题库中，能使用该方法解决的题有:

(n/2) + (n/2)

先分别求解前n/2个元素和后n/2个元素问题的解, 然后再构造原问题的解。使用这种方法的典型算法为 merge sort 。

leetcode题库中，能使用该方法解决的题有:

  • 338. Counting Bits
    分别求每个数m的二进制表示中1的个数。
    这里把输入m看作是n个bit的list。分别计算前n/2和后n/2个bit中1的个数，然后将两者相加即可。

1+(n-1), 2+(n-2), …, (n-1)+1

先将原问题分别分为1+(n-1),…,(n-1)+1这几种情况，然后根据问题描述综合得到原问题的解。其实，这里的基本想法还是分治

leetcode题库中，能使用该方法解决的题有:

  • 96. Unique Binary Search Trees
    规模为n的树的形态数，为其左右子树结点数分别为(0,n-1),…,(n-1,0)时树的形态数的和。
  • 22. Generate Parentheses
    n对括号，可以由以下方式构成：
    • i对括号连接n-i对括号，其中 1<=i<=n
    • n-1对括号的外层加一对括号
  • 312. Burst Balloons
    把这道题归在这里，其实不是很合适。因为，想到分割原问题的方式是很难的。
  • 241. Different Ways to Add Parentheses
    这里的规模n为字符串中含的符号数。然后，分别从每个符号的位置将原字符串一分为二，递归求解即可。

forall k < n –> n

leetcode题库中，能使用该方法解决的题有:

  • 300. Longest Increasing Subsequence
    可以先将问题加强为，求以第n个元素结尾的最长上升子序列。它是前n-1个元素中比第n个元素小的元素，其最长上升子序列，中的最大值加1.

二分查找

二分查找其实是(n/2)+(n/2)问题的一种特例。因为数据的有序性质，而使得原问题的解直接归结为前一半问题或后一半问题的解。从而消除了回溯。

leetcode题库中，能使用该方法解决的题有:

遍历

遍历是把问题的求解过程变成了判断过程。当解空间有限时，我们可以枚举解空间的任意一个值，再判断该值是否为原问题的解。常见的遍历(枚举)方法为 深度优先 和 广度优先 ,以避免枚举过程中的重复问题。针对线性的数据结构， 线性遍历遍历 就可以了。

线性遍历

leetcode题库中，能使用该方法解决的题有:

深度优先

先序遍历

leetcode题库中，能使用该方法解决的题有:

广度优先

树的层序遍历，图中寻找最短路径多使用广度优先。

树的层序遍历要注意如何判断一层的元素已经全被遍历完了。有两种方法：

  • 记录一层的元素个数，该数值为上一层元素的孩子数。 在开始遍历一层的时候，已经遍历了几个元素。当遍历的个数达到该层的元素个数时，该层遍历结束。
  • 设置一个queue，只保存当前正在遍历的层的所有元素。当该queue中所有元素被遍历完时，该层就被遍历完了。

当所有问题为求最短路径时，可以试着使用广度优先。

leetcode题库中，能使用该方法解决的题有:

回溯(backtrace)

有时，我们无需将解空间全部遍历一遍。当我们知道解空间中的一个值不是原问题的解时，我们可以知道其它的一些值也一定不是解。这时候，就用到了回溯。比方说，解空间的值为 *(a1,…,an) , 当 ai 等于某值(不妨设为 v )时, 对于任意的 a(i+1) … an , (v1, …,v(i-1), v, a(i+1), … ,an) 都不是原问题的解，则无需再遍历这些解。回溯的策略是，依次遍历 ai 的值。 将遍历解空间的值变为了遍历解空间中各个维度的值。一个典型算法为 八皇后问题 。 回溯可以看作是带剪枝的遍历。

leetcode题库中，能使用该方法解决的题有:

  • 52. N-Queens II
    依次确定第i行的皇后的位置。当第i的某个位置不能放皇后时，第i行后的其它行也不必遍历了。

动态规划(dynamic programming)

不太明白动态规划原本的含义是什么。我只把它看作是一种优化手段，当发现重复计算时，便将计算结果存下来。

leetcode题库中，能使用该方法解决的题有:

一些特殊方法

使用上述的方法，通常能找到一个多项式时间的算法。但是，如果希望得到更低时间复杂度的算法，就需要进行一些细致的观察了。利用原有数据中的一些特殊性质。在这里列出的方法一般没法直接拿来用。就直接当作题库吧。遇到过就会，没有遇到过，还是算了吧。

Two Pointers

该方法缩减问题规模的方式可以从前后两个方向开始缩减。到底从哪边缩减，因具体情况而定。该方法常用于有序数组上的一些问题。使用这个办法的典型算法为 quick sort 中的 partition。如果原问题本身有一种前后的对称性，也可以考虑使用该办法。

leetcode题库中，能使用该方法解决的题有:

  • 344 Reverse String
    基于这样的观察：将字符串反转，是先将首尾两个字母调换，然后剩下的字符串翻转。
  • 345. Reverse Vowels of a String
    算法和上一道题一致。
  • 75. Sort Colors
    从两头开始遍历数组，左侧保证全是0，右侧保证全是1和2，且所有的1都在2的前面。

Partition

leetcode题库中，能使用该方法解决的题有:

位运算

这种题，千变万化，目前没有找到规律。

leetcode题库中，能使用该方法解决的题有:

其它的一些技巧

记录某个字母c出现的次数，可以用数组来存储。num[ord(c)-ord(‘a’)]记录c出现的次数。如果知道要遍历的数值的范围，也可以这么做。

记录某个元素出现的次数，或记录某个元素是否出现过，可以使用HashTable，查找时间复杂度为O(1)

记录某个字母(都是小写字母或都是大写字母)是否出现过, 可以用一个int数的各个bit来记录。

将数组化身为链表

关于数组的问题，看看先排序后，是否能有更好的算法。

加入一个int类型变量的取值范围为0或者1，那么可以使用该变量除了最低位的其它位来存储别的值。

其它

有一些习题的算法无法用上面的办法想到，或者有一些习题的一些算法无法用上面的办法想到。这里列出了这些习题。

math

天才的想法

天才的想法总来自于那灵光一闪的一刻。我们很难探究这些想法的来源。只要安静地欣赏就好了。

投票

It is proposed in “A fast majority vote algorithm”[^vote].
It is proved formally in “Experiences with software specification and verification using LP, the Larch proof assistant”[^voteproof]

其它

简单题

其它

update:

2016-7-13

随着做的题越来越多，越来越发现，想找几种通用的pattern来帮助你更快地解题，变得越来越困难。比方说，我总觉得首先寻找分割子问题的方式，可能是着手解题的一个好的开始。可是，越来越多的题表明，这么做并没有什么用。在正文中其他条目中，题目的不断增加，便越来越说明了这一点。

或许，回归直觉，是一个好的办法。从一个给定输入出发，看看自己能够找到一个求解问题的办法。从中，看看能否发现一些规律，然后推广到别的输入。也就是，波利亚在《数学与猜想》中提到的，从特殊到一般。

或者，换一个思路去思考问题。不是从问题本身的结构出发，而是从描述问题所使用的数据结构出发，或许有好的思路。比如说，输入是一个有序数组，输入是两个有序数组，会让你有更好地解决办法。总结一下，描述问题所用的数据结构可以利用的一些性质，或许有帮助。一个典型的题目是Find K Pairs with Smallest Sums，由两个有序数组的元素组成的pair可以构成一棵树，树的性质为如果m是n的祖先，则它们有序。然后，便容易有了这个题目的广度优先遍历算法。

参考文献

[^vote]: Robert S. Boyer and J. Strother Moore. MJRTY: A fast majority vote algorithm. In Automated Reasoning: Essays in Honor of Woody Bledsoe, pages 105–118. Kluwer, 1991.

[^voteproof]: Manfred Broy. Experiences with software specification and verification using LP, the Larch proof assistant. Formal Methods in System Design, 8(3):221–272, 1996.

Go Snail

Posted on | In

假如你希望借助于机器 broker 来访问机器 target, 可以在~/.ssh/config文件中添加如下内容

1
2
3
4
5
6
7
Host broker             # Machine B definition (the broker)
    Hostname broker-ip  # Change this IP address to the address of the broker
    User myusername     # Change this default user accordingly 
                        # (`user@unibroker` can overwrite it)

Host target             # Machine A definition (the target host)
    ProxyCommand ssh -q broker nc hostname.or.IP.address.target.machine 22

然后使用ssh username@target即可访问目标机器 target

当需要多级跳转时，在~/.ssh/config中添加如下内容即可。

1
2
3
4
5
6
7
8
Host ruapehu
  HostName ruapehu.example.com

Host aoraki
  ProxyCommand ssh ruapehu nc aoraki 22

Host tongariro
  ProxyCommand ssh aoraki nc %h 22

当使用命令ssh aoraki时，你其实是经过如下路径访问到了 tongariro: ruapehu –> aoraki –> tongariro

参考文献

Go Snail

Posted on | In

Merge Sort

Merge sort是典型的分治算法, 直接将原问题分为前一半和后一半。要使用分治算法，原问题必须能够分解为规模相当，且能够独立求解的两个子问题。Merge sort的算法框架可以套用在其它的分治算法上，只要把merge函数重写即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def merge_sort(nums):
    return merge_sort_helper(nums, 0, len(nums)-1)


def merge_sort_helper(nums, start, end):
    if start == end:
        return [nums[start]]
        
    mid = start + (end-start)/2
    res1 = merge_sort_helper(nums, start, mid)
    res2 = merge_sort_helper(nums, mid+1, end)
    
    return merge(res1, res2)
        

def merge(nums1, nums2):
    i = 0
    j = 0
    res = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            res.append(nums1[i])
            i += 1
        else:
            res.append(nums2[j])
            j += 1
    while i < len(nums1):
        res.append(nums1[i])
        i += 1

    while j < len(nums2):
        res.append(nums2[j])
        j += 1

    return res

Merge sort中的merge的办法可以应用到很多问题中。如

也是就是说，合并两个有序的线性结构，可以使用该merge算法。那如果是两个有序的二叉树呢(如 二分查找树)？可以这么来做。先通过该merge算法得到一个排好序的数组(时间复杂度为O(m+n))，然后再由该有序数组生成二分查找树(时间复杂度为O(m+n))。其中，m和n分别为两棵树的节点数。当然了，如果该二分查找树的表示方式为数组的话，那直接merge就完成了。

Quick Sort

Quick Sort也是分治算法。只是它分割子问题的方式相对巧妙一些。相比于merge sort,它不是直接将原数组分为前一半和后一半，而是随机选取一个元素，将原数组分为比这个元素大的一半和不比这个元素大的一半。它的好处是，把两个子问题的结果直接合并就是原问题的解。

我们还可以换一个角度来看这个排序的过程。当你把原数组分割好的时候，其实你也找到了那个分割元素在数组中的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def quick_sort(nums):
    quick_sort_helper(nums, 0, len(nums)-1)

def quick_sort_helper(nums, start, end):
    if start < end:
        r = partition(nums, start, end)
        quick_sort_helper(nums, start, r-1)
        quick_sort_helper(nums, r+1, end)


def partition(nums, start, end):
    pivot = nums[end]
    i = start
    j = end
    while i < j:
        while  i<j and nums[i] <= pivot:
            i += 1
        while i<j and nums[j] >= pivot:
            j -= 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    tmp = nums[i]
    nums[i] = nums[end]
    nums[end] = tmp

    return i
Go Snail

Posted on

安装hexo

安装和使用中碰到的问题

没有hexo server命令

原因是hexo-server模块作为一个独立的模块，需要单独安装

npm install hexo-server --save

详见Server section of hexo.io document

运行Hexo server命令后，访问4000端口出现cannot get?

查看public目录，发现没有index文件

ls /blog/public/

原因是hexo有些依赖的模块没有安装，从而没有正确的生成网站。完成安装即可。
在你的blog目录下运行

npm install

详见Hexo本地安装 都是默认的文件 命令运行了 访问4000端口出现cannot get?

hexo的next主题显示德语

原因不明。将blog/themes/next/languages/de.yml删除了，这样会显示默认语言，也就是英文。

hexo的主题

next

Go Snail

Posted on

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment