Linux迷+Python粉 - 算法

面试算法编程选记2题之二分法-寻找斜率为K的2点

2020-06-22T00:00:00+08:00

因为一直是用自学+坚持自学方法走过来的，折腾技术运用还可以，基础算法编程能力一直偏弱。

1、二分法属于思维简单，细节弄人的典型。之前陷入过二分法脑风暴中不能通透，这次趁面试遇到好好再过一次，提高深度。

2、输入数组A 例如 [(x1,y1),(x2,y2)…]，输出斜率为K的点对数目

二分查找¶

二分查找要处理好中点，缩小方法，避免死循环。重在细节实现。 Plus增强后支持最左最右查找

已过 leetcode算法题：https://www.nowcoder.com/questionTerminal/28d5a9b7fc0b4a078c9a6d59830fb9b9

class BinarySearch:
    def getPos(self, A, n, val):
        a1, a2 = 0, n-1 # a1 = 0; a2 = n-1;
        while a1 <= a2:              # a1, a2 位置未检
            mid = (a1+a2)//2        # 中间索引赋值是关键，可等左，不等右
            # print(val, A, a1, a2, mid)
            if A[mid] == val:
                return mid
            elif A[mid] < val:
                # print(A, a1, a2, mid)
                a1 = mid + 1
                # print(A, a1, a2, mid)
            else:
                a2 = mid - 1
        else:
            return -1

    def getPosPlus(self, A, n, val, searchtype=0):
        '''支持最左，最右二分查找的修改Plus版本
        'left':-1, 'fast':0, 'right':1 其中0是默认版本，找到即返回。
        '''
        a1, a2 = 0, n-1
        while a1 < a2:              # 直到重合时，单元素
            mid = (a1+a2)//2        # 中间索引赋值是关键，可等左，不等右
            # print(val, A, a1, a2, mid)
            if A[mid] == val:
                if searchtype == 0:
                    return mid
                if searchtype == -1:
                    a2 = mid
                elif searchtype == 1:
                    a1 = mid
            elif A[mid] < val:
                # print(A, a1, a2, mid)
                a1 = mid
                if a1 + 1 == a2:   #  避免剩余2个元素时， mid=左陷入死循环
                    a1 = a2
                # print(A, a1, a2, mid)
            else:
                a2 = mid
        else:
            assert a1 == a2
            return a1 if A[a1] == val else -1


if __name__ == '__main__':
    rt = BinarySearch()
    for A in ((1,), (1,5), (1, 5, 9), (1, 1, 5), [4,4,10,21]):
        n = len(A)
        for val in A:
            # idx = rt.getPos(A, n, val)
            # print('find %3s in %10s: index=%s' % (val, A, idx))

            # 支持最左，最右二分查找的修改Plus版本
            idx = rt.getPosPlus(A, n, val)
            print('find %3s in %10s: index=%s' % (val, A, idx))
            idx = rt.getPosPlus(A, n, val, -1)
            print('find %3s in %10s: index=%s' % (val, A, idx))

寻找斜率为K的点对¶

算法题：

有一个数组,数组每个元素是一个对象,每个对象有x和y两个值,这个数组记录为A: A = [{x1, y1}, {x2, y2}, …];我们把数组A中任意两个满足以下关系的元素叫做“点对”:(y2-y1)/(x2-x1) = K, K是一个常数。编写程序:给定A与K,返回A中点对的数目。

from itertools import groupby

K = 1 # 斜率

def kpairs(A, k=K):
    '''
    分析：计算一遍点到直线y=kx距离 |Kx - y| / √(k*k+1)，距离等两点的可能与y=kx平行。先验证y=kx上的，距离等不一定平行。
    技巧：结合题目实际，可不开平方pow运算，不取绝对值。
    '''
    print('debug: kpairs(%s, %s)' % (k, A))
    result = 0
    distance = [ (k*x-y) / (k**2+1) for (x, y) in A ]
    point_distance = sorted(zip(A, distance), key=lambda x: x[1])  # 距离排序，取点

    for distance, pointiter in groupby(point_distance, key=lambda x: x[1]):
        points = list(x[0] for x in pointiter)
        count = len(points)
        print('debug: line:y=%3sx, got %3s point distance=%7.3s: %s' % (k, count, distance, points)) # debug
        if count > 1:
            result += count*(count-1)/2 # 组合数 4 -> 6

    return result

if __name__ == '__main__':
    A = [(0,3), (3,0), (3,3), (0,0)]  # 正方形
    assert kpairs(A) == 1, 'check and debug kpairs(%s)'%A
    assert kpairs(A, 10) == 0, 'check and debug kpairs(%s)'%A

    A = [(3,9), (9,9), (20,20), (10,16), (22,28)]
    assert kpairs(A) == 4, 'check and debug kpairs(%s)'%A
    assert kpairs(A, 4) == 1, 'check and debug kpairs(%s)'%A

参考¶

点到直线距离公式的几种推导 https://zhuanlan.zhihu.com/p/26307123

RSA原理：欧几里德算法与奥数内容辗转相除法——挑战PythonTip

2017-12-17T23:00:00+08:00

PythonTip 里未攻克的题目，如RSA密码方程，如今积累工作经验之后从新挑战，仍然失败未成功了。把过程记录分享下。

描述:¶

在RSA密码体系中,欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 (x*a) % n = 1 这种方程。其中，x,a,n皆为正整数。现在给你a和n的值(1 < a,n < 140000000)，请你求出最小的满足方程的正整数解x（保证有解）. 如：a = 1001, n = 3837，则输出23。

分析：¶

没头绪，在讨论里看时恍然，用到小学奥术内容辗转相除法（求最大公约数）了。如果 (x*a) % n = 1 变成 (x*a) % n = 0 ，那x*a就是a和n公倍数了。如果这是小学奥数题，就先用辗转相除法得最大公约数，而最小公倍数用两数积除以最大公约数得出来。 rsa的原理数学基础欧几里得算法和小学奥数有着这样的联系，发现这点让我觉得不可思议又略有惊叹。看来学小学奥数有用，至少是可以为算法编程做准备的，学到了最朴素的数论。

辗转相除法（朴素欧几里得算法，中国余数定理，韩信点兵）¶

（引用自数论——欧几里得算法）

欧几里得算法，又名辗转相除法，是求最大公约数的算法。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

题目语义转化¶

求这样一个数x*a，能被a整除，被n整除余1。

这就很形似 有一个数除以3余2，除以5余3，除以7余4，除以9余5．这个数至少是? 被称为中国余数定理

扩展欧几里德算法¶

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

证明：设 a>b。

1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；

2，ab!=0 时

设 ax1+by1=gcd(a,b);

bx2+(a mod b)y2=gcd(b,a mod b);

根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);

则:ax1+by1=bx2+(a mod b)y2;

即:ax1+by1=bx2+(a-(a/b)b)y2=ay2+bx2-(a/b)by2;

根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;

这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

…

同余方程 ax≡b (mod n)对于未知数 x 有解，当且仅当 gcd(a,n) | b。且方程有解时，方程有 gcd(a,n) 个解。

求解方程 ax≡b (mod n) 相当于求解方程 ax+ ny= b, (x, y为整数)

我的一个另类编程解法（融合了辗转相除法思想）。¶

算法描述¶

(x*a) % n = 1 对应方程 ax - ny = 1 的整数解

（a,n必定互质。如不互质可提取公因子，公因子*X=1，与X为整数矛盾）

化简降解方程分两情况：

a>=n 时变形为方程 (a mod n)x - n(y-[a/n]x) = 1 有整数解
a<n 时变形为方程 a(x-[n/a]a) - (n mod a)y = 1 有整数解

无论那一种都变回 ax - ny = 1 的形式。所以重复化简，因a,n互质，最后会到达a,n其一是1的情况。

例子说明：求能被9整除，被7除余1的最小数¶

9x=1(mod7) 对应方程 9x - 7y = 1 的整数解
变形有2x - 7(y-x) = 1 然后令 x_1=x, y_1=y-x 得方程 2x_1 - 7y_1 = 1
变形有2(x_1-3y_1) - y_1 = 1 然后令 x_2=x_1-3y_1, y_2=y_1 得方程 2x_2 - y_2 = 1 显然有解 x_2=1 y_2=1
好了，往上一步一步回溯得最初的x,y值 (x_2,y_2), (x_1,y_1), (x,y) 分别为(1,1),(4,1),(4,5)
9x = (94 mod 97) = 36 答：求能被9整除，被7除余1的数是36

python语言是弱递归化语言， python之父说递归都可以转成循环。所以我用递归后，转循环了。

Python代码:¶

################################################################################
# print "F: 答案错误 循环解法"
################################################################################
def gcd(a,n): # 辗转相除求最大公约数
    if a < n: a,n = n,a
    while n != 0: a,n = n,a%n
    return a

def exgcd(a, n): # ax=1(mod n) 即 ax-ny=1 求x,y     
    # print a,n
    if gcd(a,n) != 1:   raise Exception('fei hu zhi') # 先检查是否互质
    l = []
    while a!=1 and n!=1: # a,n总会有个先到1，触底条件就是1
        l.append((a,n))
        if a>n: a,n = a%n,n
        else:   a,n = a,n%a
    if a==1:    p = (n+1, 1)
    elif n==1:  p = (1, a-1)

    for a,n in l[::-1]:
        if a>n: p = (p[0] % n, (a//n*p[0]+p[1]) % a) # 这个值也是解，但没有最简：return (p[0], a//n*p[0]+p[1])
        else:   p = ((p[0]+n//a*p[1]) % n, p[1] % a) # 这个值也是解，但没有最简：return (p[0]+n//a*p[1], p[1])
    return p

print exgcd(a,n)

################################################################################
# print "F: 答案错误 递归解法"
################################################################################
def gcd_r(a,n): # 辗转相除求最大公约数
    if a * n == 0: return a+n
    return gcd_r(a%n,n) if a>=n else gcd_r(a,n%a)
# print gcd(a,n)

def exgcd_r(a, n): # ax=1(mod n) 即 ax-ny=1 求x,y     # a,n总会有个先到1，触底条件就是1
    # print a,n
    if gcd_r(a,n) != 1:   raise Exception('fei hu zhi') # 先检查是否互质
    if a==1: return (n+1, 1)
    if n==1: return (1, a-1)
    if a>n:     
        p = exgcd_r(a%n, n)
        return (p[0] % n, (a//n*p[0]+p[1]) % a) # 这个值也是解，但没有最简：return (p[0], a//n*p[0]+p[1])
    else:
        p = exgcd_r(a, n%a) 
        return ((p[0]+n//a*p[1]) % n, p[1] % a) # 这个值也是解，但没有最简：return (p[0]+n//a*p[1], p[1])

print exgcd_r(a,n)

小学初中就知道数论，数论真有魅力，非常漂亮。

参考¶

数论——欧几里得算法 https://xuanwo.org/2015/03/11/number-theory-gcd/

欧几里德与扩展欧几里德算法 http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

欧几里得算法（辗转相除法） https://my.oschina.net/u/1780798/blog/646739

https://zhidao.baidu.com/question/406531667.html?qbl=relate_question_3

威佐夫博弈：取石子游戏算法——挑战PythonTip

2017-12-16T16:30:00+08:00

PythonTip 里未攻克的题目，如取石子游戏，如今积累工作经验之后从新挑战，成功了。把过程记录分享下。

描述:¶

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目a和b，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你是胜者，输出Win,否则输出Loose。例如，a=3,b=1, 则输出Win(你先在a中取一个，此时a=2，b=1,此时无论对方怎么取，你都能将所有石子都拿走).

分析（动态规划）：¶

我的思路是转变成图形化表示，二维表中点(x,y)用W表示会赢，L表示为输。

(x,y)的结果显然决定与前面已填好的(m,n) , 其中m,n 分别小于 x,y 。所以可以用动态规划。根据之前失败坐标的集合推算本行的失败坐标。

并且每行至多有一个失败坐标。所以能保证动态规划的时间复杂度不会很高。

当我从(0,0)开始，填到(a,b)时就知道结果了。

明显(x,y)和(y,x)结果一样，因此我刚开始只填半个表，导致结果不准，看了其他人的奇异坐标才明白到自己的错误。从新填好。

错误填表分析过程¶

我根据这个过程写出版本一代码。

正确填表分析过程¶

我本来猜测需要推到前面代码从来。幸运的是，运行正常的版本二的代码只在版本一加一行就可以了。

下面是我的算法代码，比较简洁。动态规划确实强大，另外还有分治法也强。

Python代码:¶

################################################################################
# print "T: 二维坐标表示法, 每行至多有一个失败坐标。二维表只填半边导致失误，改正" 
################################################################################
if a < b: a,b = b,a

m = [(0,0)]  # 失败的坐标纪录池
for i in range(1,a+1):
    for j in range(i+1):
        # if i == j or j == 0: # win
        #     continue

        for x in m:
            if (i-x[0]) == (j-x[1]) or i == x[0] or j == x[1]: # win
                break
        else:  # else 是for的部分，break for的时候也break了else
            m.append((i,j)) # 版本一：二维表只填半边，所以只有这行代码
            m.append((j,i)) # 版本二：二维表两边都填，多加这一行就OK了
        #print i,j,m

print "Loose" if (a,b) in m else "Win"

Python解无穷大数除法算法——挑战PythonTip

2017-12-15T16:30:00+08:00

PythonTip提供了一个不错的学习算法平台，大学毕业前挑战进入了前几名pythonwood解题数量。

当时有些未攻克的题目，比如密码生成题目，如今积累工作经验之后从新挑战，成功了。把过程记录分享下。

描述:¶

生活在当代社会，我们要记住很多密码，银行卡，qq，人人，微博，邮箱等等。小P经过一番思索之后，发明了下面这种生成密码方法：给定两个正整数a和b, 利用a / b我们会得到一个长度无限的小数(若a / b不是无限小数，比如1/2=0.5,我们认为0.5是0.5000000…，同样将其看做无限长的小数），小P将该小数点后第x位到第y位的数字当做密码，这样，无论密码有多长，小P只要记住a,b,x,y四个数字就可以了，牢记密码再也不是那么困难的事情了。现在告诉你a,b,x,y（0 < a,b <= 20132013, 0 < x <= y < 100000000000),请你输出密码。例如：a = 1, b = 2, x = 1, y = 4, 则 a / b = 0.5000000…, 输出小数点后第1到4位数字，即5000

分析：¶

计算机浮点计算有精度问题，所以直接除法得结果的思路不通。这次我想到小学的列竖式除法算法本身是可以解无穷除法的。于是，这道题就是把我们小学早已学过的算法，用代码表示出来。

下面包含几个算法，都比较简介，比较pythonic（在网上看到是算法代码普遍臃肿）。只有最后的循环记录法是在规定时间内通过的。

Python代码:¶

#! /usr/bin/env python
#coding: utf8

# 返回a除以b的商的小数部分的第x位到第y位
a = 22; b = 300003; x = 1; y = 50

################################################################################
print "F: 不能引入sys 模拟手工除法"
################################################################################
import sys

t = a % b

for c in range(y):
    t *= 10
    if c+1 >= x:
        sys.stdout.write( str(t//b) )
    t %= b
print

################################################################################
print "F: 时间复杂度不足 同上"
################################################################################
code = ""
t = a % b

for c in range(y):
    t *= 10
    if c+1 >= x:
        code += str(t//b) 
    t %= b
print code


################################################################################
print "F: 时间复杂度不足 变除为乘补零难"
################################################################################
t = a % b
lzero = ""
_t = t * 10
while _t < b:
    lzero += "0"
    _t *= 10
print lzero + str(t * 10 ** y // b)[x-1:]


################################################################################
print "F: 时间复杂度不足 同上"
################################################################################
t = a % b
lzero = ""
_t = t * 10
while _t < b:
    lzero += "0"
    _t *= 10
print lzero + str(int( str(t) + '0' * y ) // b)[x-1:]


################################################################################
print "T: 挑战成功 循环小数记录法"
################################################################################

code = "" # 遇见循环即止
rep = ""  # 循环体
left = [] # 余数池
t = a % b

for c in xrange(y):
    if t in left:
        rep = code[left.index(t):]
        break
    else:
        left.append(t)
    t *= 10
    code += str(t//b) 
    t %= b
else:
    print code[x-1:]

print ( code + rep * ( (y - len(code))/len(rep) ) + rep[: ( (y - len(code))%len(rep) ) ] )[x-1:]

【实习记】2014-08-29算法学习Boyer-Moore和最长公共子串（LCS）问题——阿里校招题

2014-08-29T21:23:00+08:00

最长公共子串问题分析¶

其实这是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧：”bab”和”caba”(当然我们现在一眼就可以看出来最长公共子串是”ba”或”ab”)

b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　1

a　　0　　1　　0

我们看矩阵的斜对角线最长的那个就能找出最长公共子串。

不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。

b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　2

a　　0　　2　　0

这样矩阵中的最大元素就是最长公共子串的长度。

在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。

代码实践¶

根据以上算法使用C语言实践了一下。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int comfix(const char* stra, const char* strb);
int main(void){
    const char
        *stra = "hello world",
        *strb = "malloc";
    printf("%s,%s: %d\n", stra, strb, comfix(stra, strb));
    return 0;
}

int comfix(const char* stra, const char* strb){
    /*
     * 变量第一字符
     * c:char*, l:len
     * 变量第二字符
     * s:small, l:large
     */
    const char
        *cs  = stra,
        *cl  = strb;
    int ret = 0,
        la  = strlen(stra),
        lb  = strlen(strb),
        ls  = la,
        ll  = lb;
    /* 如果不对，就调换呗 */
    if (lb<la)
        cs = strb, ls = lb, cl = stra, ll = la;
    /* 矩阵，只保存矩阵的一行即可动态之 */
    int *pint = (int*)malloc((ls+1)*4);
    memset(pint ,0 , (ls+1)*4);
    int i, j;
    for (i=0; i<ll; i++){
        /* 生成下一行，同时上一行内容被回收 */
       for (j=ls; j>ret; j--)
           if (cl[i]==cs[j])
               pint[j] = pint[j-1]+1;
       /* 如果有更大就更新ret */
       for (j=ls; j>ret; j--)
           if (pint[j]>ret)
               ret = pint[j];
    }
    return ret;
}

这种算法非常巧妙地化繁为简，有时换一个思路，就会扩然开朗！

比较喜欢这种锻炼。

参考¶

研究了求最长公共子串问题，顺便研究了字符串匹配

字符串匹配的Boyer-Moore算法 http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

字符串匹配的KMP算法 http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

动态规划算法之：最长公共子序列 & 最长公共子串（LCS） http://my.oschina.net/leejun2005/blog/117167

Linux迷+Python粉 - 算法

面试算法编程选记2题之二分法-寻找斜率为K的2点

二分查找¶

寻找斜率为K的点对¶

参考¶

RSA原理：欧几里德算法与奥数内容辗转相除法——挑战PythonTip

描述:¶

分析：¶

辗转相除法（朴素欧几里得算法，中国余数定理，韩信点兵）¶

题目语义转化¶

扩展欧几里德算法¶

我的一个另类编程解法（融合了辗转相除法思想）。¶

算法描述¶

例子说明： 求能被9整除，被7除余1的最小数¶

Python代码:¶

参考¶

威佐夫博弈：取石子游戏算法——挑战PythonTip

描述:¶

分析（动态规划）：¶

错误填表分析过程¶

正确填表分析过程¶

Python代码:¶

Python解无穷大数除法算法——挑战PythonTip

描述:¶

分析：¶

Python代码:¶

【实习记】2014-08-29算法学习Boyer-Moore和最长公共子串（LCS）问题——阿里校招题

最长公共子串问题分析¶

代码实践¶

参考¶

例子说明：求能被9整除，被7除余1的最小数¶