Month: 一月 2020

面试刷题总结(三) – 深度优先搜索与回溯

回溯(backtrack)是一种系统性地搜索问题解答的方法。为了实现回溯,首先需要为问题定义一个解空间(solution space),这个空间必须至少包含问题的一个解(可能是最优的)。深度优先搜索方法本质上是对解空间的深度优先遍历,也就是说要做到「心中有树」。

回溯问题往往使用同一套代码可以解决一个问题的好几个变种。所以我们解决问题的时候应该首先尝试解决最基础的形式:判定是否有解或者有几个解,然后再去具体求解路径。

本质上来说,回溯就是一种暴力解法。

解题模板

核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」。下面的 if 不可行 其实就是剪枝的过程。给定的函数往往不一定满足回溯的函数签名,添加一个 helper 函数就好了。track 就是路径的意思,所以回溯(backtrack)本身就是路径退回的意思。

需要注意的是,剪枝虽然能够提高程序运行速度,但是对于时间复杂度往往没有改善。回溯算法的时间复杂度往往是 O(2^n)

选择列表  # 题目给定
ans = []
def backtrack( track , pos ):
    """
    track: 当前路径
    pos: 当前位置,或者是剩下的未访问元素
    """
    if 满足结束条件 :  # base case
        ans.add( track )
        return

    # 通过考虑 pos,可以让选择列表小一点
    for 选择 in 选择列表 [pos] :
        if 不可行 :
            continue
        做选择  # track -> new_track
        backtrack( new_track , 选择 )
        撤销选择  # new_track -> track

我们可以看到回溯的空间复杂度实际上就是路径的最大长度。ans 参数完全可以写到 backtrack 函数中一直传递,但是本来 backtrack 函数的参数就够多了,我还是建议把他作为一个全局变量或者闭包外的变量,这样清晰一些。

另外值得注意的一点是,我们传递了 pos 这个变量,实际上从这里很容易转变成动态规划了。实际上这里的 pos 就是动态规划中遍历数组的索引。

改变函数签名与参数传递

正如上面所说的,回溯算法往往是需要定义一个 helper 函数的。

回溯最好把结果变量作为一个全局变量和输入变量都定义在外边,这样方便一些,不然就得一路传递下去,容易出问题。backtrack 函数接收两个参数:

  1. 当前路径
  2. 当前遍历位置

这里其实是更广义的 result in parameter 还是 result in return value 的问题。最好给用户用的函数是 result in return value 的,自己的内部实现可以是 result in parameter 的。另外也可以用闭包实现 result in parameter 的效果,也就是说不传递参数,直接从 closure 中读取。其实也可以用一个全局变量来做,都是类似的效果。

—存疑—
固定传递的参数也包括了向下传递还是向上返回。具体来说有以下几种:

  1. 向下传递额外参数,如边界等,这个参数可能是随着调用在变的。
  2. 向上返回额外参数,也就是后续遍历才能够使用到返回的值。
    —存疑结束—

例题

对于 Python 来说,一般没必要使用全局变量,可以使用内部函数访问闭包内的变量。

LeetCode 17

这道题可以说是最最简单的一道 dfs 题目了。

参考

  1. https://www.dailycodingproblem.com/blog/an-introduction-to-backtracking/
  2. https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/hui-su-suan-fa-xiang-jie-xiu-ding-ban
  3. https://www.cnblogs.com/hustcat/archive/2008/04/09/1144645.html
  4. https://www.1point3acres.com/bbs/thread-583166-1-1.html
  5. https://zhuanlan.zhihu.com/p/92782083

面试刷题总结(二) – 分治

分解 -> 解决子问题 -> 合并

分治的时间复杂度

正如上一节所说的,分治问题在递归过程中实际上是遍历了状态空间树,所以时间复杂度的计算也需要根据树的高度和每一层的时间复杂度来计算。

recursion-tree

T(n) = a T(n/b) + f(n), if f(n) ∈ O(n^d), d >=0
T(n)∈ { 
    O(n^d), a < b^d;
    O(n^d logn), a = b^d;
    O(n^(logba), a > b^d;
}

通过 O(n) 的时间,把 n 的问题,变为了两个 n/2 的问题,复杂度是多少?

T(n) = 2T(n/2) + O(n)
    = 2 * 2T(n/4) + O(n) + O(n)
    = n + nlogn
    ≈ O(NlogN)

通过 O(1) 的时间,把 n 的问题,变成了两个 n/2 的问题,复杂度是多少?

T(n) = 2T(n/2) + O(1)
    = 2 * 2T(n/4) + O(1) + O(1)
    = n + (1 + 2 + 4 +…+ n)
    ≈ n + 2n
    ≈ O(n)

对于 O(nlogn) 的算法 T(n) = 2T(n/2) + O(n)

证明一般采用数学归纳法,反证法

改变函数签名与参数传递

参见递归中的说明

例题

LeetCode 241

class Solution:
    def diffWaysToCompute(self, s: str) -> List[int]:
        if s.isdigit():
            return [int(s)]
        ans = []
        for i in range(len(s)):
            if s[i] in ("+", "-", "*"):
                left = self.diffWaysToCompute(s[:i])
                right = self.diffWaysToCompute(s[i+1:])
                for l in left:
                    for r in right:
                        if s[i] == "+":
                            ans.append(l+r)
                        elif s[i] == "-":
                            ans.append(l-r)
                        else:
                            ans.append(l*r)
        return ans

参考资料

  1. https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247487045&idx=3&sn=e9f67f1fd33649c60478638c1d6cc2d9
  2. https://oi-wiki.org/basic/divide-and-conquer/

使用 partition by 查找并删除 MySQL 数据库中重复的行

在创建 MySQL 数据表的时候,经常会忘记给某个字段添加 unique 索引,但是等到想添加的时候又已经有了重复数据,这时候就需要删除重复数据。

准备数据

本文使用如下的数据作为演示:

CREATE TABLE contacts (
    id INT PRIMARY KEY AUTO_INCREMENT,
    first_name VARCHAR(50) NOT NULL,
    last_name VARCHAR(50) NOT NULL,
    email VARCHAR(255) NOT NULL
);

INSERT INTO contacts (first_name,last_name,email) 
VALUES ("Carine ","Schmitt","carine.schmitt@verizon.net"),
       ("Jean","King","jean.king@me.com"),
       ("Peter","Ferguson","peter.ferguson@google.com"),
       ("Janine ","Labrune","janine.labrune@aol.com"),
       ("Jonas ","Bergulfsen","jonas.bergulfsen@mac.com"),
       ("Janine ","Labrune","janine.labrune@aol.com"),
       ("Susan","Nelson","susan.nelson@comcast.net"),
       ("Zbyszek ","Piestrzeniewicz","zbyszek.piestrzeniewicz@att.net"),
       ("Roland","Keitel","roland.keitel@yahoo.com"),
       ("Julie","Murphy","julie.murphy@yahoo.com"),
       ("Kwai","Lee","kwai.lee@google.com"),
       ("Jean","King","jean.king@me.com"),
       ("Susan","Nelson","susan.nelson@comcast.net"),
       ("Roland","Keitel","roland.keitel@yahoo.com"),
       ("Roland","Keitel","roland.keitel@yahoo.com");

注意其中有一行重复了三次。输入完成后,数据如图所示:

file

查找重复的行

使用 group by 和 having

假设我们要通过 email 字段来查找重复值。通过使用 group by 和 having 子句可以查找到哪些行是重复的。

SELECT
    email,
    COUNT(email)
FROM
    contacts
GROUP BY email
HAVING COUNT(email) > 1;

file

Having 就类似于 Group by 之后的 where 子句。但是这个语句还是很难解决我们的问题,我们只知道发生重复的第一行了,而不知道哪些行是重复的。这时候可以使用 partition by 语句。

使用 partition by 找出所有的重复行

需要注意的是,partition by 只有在 MySQL 8.0 之后才支持,而现在常用的是 5.6 和 5.7 版本。

Partition 语句又叫做窗口聚合语句,也就是说他会把同一个值的行聚合成一个窗口,但是和 Group by 语句不同的是,窗口内的每一个行并没有被压缩成一行,具体说Partition by 的语法是:

window_function_name(expression) 
    OVER (
        [partition_defintion]
        [order_definition]
        [frame_definition]
    )

删除重复的行

删除的方法有很多种,这里介绍两种。

References

  1. https://www.mysqltutorial.org/mysql-window-functions/
  2. 2.

Buy the rumor, sell the fact.

buy the rumor, sell the fact 说的是市场往往具有领先性,在事情还没有落地之前,已经开始抢跑了。等到协议真正签署的时候,也就是利好兑现的时候,当前的市值早已经蕴含了对这个利好成功兑现的预期。所以在真正达成协议的时候,先期在低价买入的一方便会决定卖出以兑现自己的收益。由于这时候卖方变多,如果没有后续利好的情况下,利好兑现反而会导致股价会出现一定的回调。反过来说,有时候利空出尽甚至会带来股价的上扬,当然也是在基本面看好的前提下。举几个例子就很明白啦~

  1. 超出市场预期的例子。中美谈判对峙时期,美国态度强硬。Xi 突然去江西视察了一家稀土企业——金力永磁,并支持稀土是中国的战略资产,必要时候可以限制出口。很明显这是针对美国的嘛,因为这个事情之前市场都没有想到过,原来稀土还能有这么大的价值,所以这就是一件超出市场预期的事情,那么包括金力永磁、宁波韵升之类的一大批稀土企业的股票就都暴涨了。http://finance.sina.com.cn/stock … vhiqay3582814.shtml

  2. 不及市场预期的例子。拼多多三季报营收大增 122%,亏损也扩大了 112.6%,总的来说这份财报有喜有忧,但是股票直接从 $40 掉到了 $30。主要原因是不及预期,也就是说市场之前没想着亏损竟然能这么大,当时的市值已经高估了拼多多的盈利能力。https://xueqiu.com/7700511931/136081485

  3. 超出市场预期的例子。格力的股权交易。由于格力的管理层董明珠和大股东珠海国资委的关系一向不是很好,所以格力的控股权交易让市场充满了担忧。按照 buy the rumor 的说法,在格力被收购的传闻阶段股价就会被抬起来了,但是因为刚刚说的原因,股价反而一直维持在低位。直到靴子落地,高瓴资本正式和管理层签订了协议,没有发生撕逼的事情,格力才开始从 50 多块一路涨到了现在的接近 70。

  4. 利好兑现的例子。这个就太多了,刚开始炒股的时候一看这个年报也不错,那个季报也挺牛逼,觉得买买买就好了,往往就容易入套了。因为一个公司的经营状况不可能是完全保密的,比如说线上的销售数据啊、苹果的出货量啊、原材料的价格啊这些数据只要用心或者花钱都是可以收集到的,那么其实机构们早在报表发布之前已经算准了你盈利到底增加多少。如果存在低估现象的话,早就提前入场了,如果报表符合预期(大概率),那么可能就会确定收益。最近我持仓的一个例子:国联股份,1 月 9 号公布了业绩预增 61%-70%,但是随后两天却从最高点还是阴跌了,这就是利好兑现的一个典型。http://stock.jrj.com.cn/2020/01/09192728651513.shtml

回到中美协议这个事情,一方面谈了这么久,早就确定要签了,协议的内容其实两边也都基本 ok,这也就是大家都知道的事情。另一方面,Trump 面临 2020 的大选,是在是不太可能有精力在大选前在折腾了。所以这件事情虽然是个很大的利好,但是不管 A 股还是美股,早就先涨为敬了。协议的落地长远来看肯定是很大的利好,对短期来说,说不定是利空呢。

所以最重要的有时候不是利好还是利空,重要的是有没有超出或者不及市场(分析师)的预期。市场的预期在哪里找呢?可以先看看券商的研报,一般都有某个股票的目标价位。