Linux迷+Python粉 - 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

面试高频题-LRU缓存的python实现

2019-08-22T14:00:00+08:00

过程简略： url去重的方法，数据库四种隔离级别，乐观锁悲观锁，算法题研讨。算法讨论占了很长时间，以下是把这个过程沉淀后的一遍随笔。

leetcode算法题：146. LRU缓存机制¶

https://leetcode-cn.com/problems/lru-cache/

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

思考过程简要¶

第一次遇到，没有做好题。之后总结思考如下。面试完重新整理好代码，才通过。

1、数据结构知识弱，链表随机增删复杂度O(1)，数组复杂度O(n)。使用按时间排序的双向链表。头部总是最新访问或插入的，尾巴总是最老的。使用额外maxsize限制大小，nowsize记录目前大小。

2、链表元素是key-val的进一步封装的Node类。链表是另一个类，类总head和tail表示头尾两个空的node。一直不删。

3、开头想到最小堆，用得不对。二分法等比较查找下限O(lgN)，与哈希法的O(1)差距意识不明显。而哈希函数用内置字典即可。

4、拆分小函数复用代码。比如get = 出链 + 插入头部， put = 出链 + 插入头部(update) 或者插入头部(非update)

5、之后发现python有functools.lru_cache的现成实现，值得学习。

leetcode通过提交的代码¶

class Node:
    def __init__(self, key=None, val=None):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    '''
    小函数: 删node，入head
    注意：head和tail是空的node，不能删除
    '''
    def __init__(self, maxsize=10):
        self.maxsize = maxsize
        self.nowsize = 0
        self.head = Node()
        self.tail = Node()
        self.tail.prev = self.head
        self.head.next = self.tail
        # key -> nodes.val
        self.nodes = {}

    def get(self, key):
        node = self.nodes.get(key, None)
        if node != None:
            # 2019-08-21面试时加的要求
            self.popNode(node)
            self.addNode(node)
            return node.val
        else:
            return -1

    def put(self, key, val):
        self.set(key, val)

    def set(self, key, val):
        node = self.nodes.get(key, None)

        if node != None:
            # 在链表中，update操作
            self.popNode(node) #

        self.addNode(Node(key, val))

    def delete(self, key):
        node = self.nodes.get(key, None)

        if node != None:
            self.popNode(node)


    def popNode(self, node):
        if node.val == None:
            return

        # 使用head和tail为空node时无需检查
        # if node.next:
        #     node.next.prev = node.prev
        # else:
        #     self.tail = node.next
        # if node.prev:
        #     node.prev.next = node.next
        # else:
        #     self.head = node.next
        node.next.prev = node.prev
        node.prev.next = node.next

        self.nowsize -= 1

        # 字典更新
        del self.nodes[node.key]

        return node


    def addNode(self, node):
        # 总在链表头加入
        if node.val == None:
            return

        if self.nowsize >= self.maxsize:
            # 满了，就去掉尾巴再插入
            self.popNode(self.tail.prev)

        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node # 费时的debug错误：这句之后[['c', 12]] -> []

        self.nowsize += 1

        # 字典增加
        self.nodes[node.key] = node

    @property
    def vals(self): # debug
        # node = self.head # 错误：发现用时15分钟
        node = self.head.next
        _vals = []
        # while node.val: # 2019-08-21大坑，node.val = 0时会失败！费了1小时！！！
        while node != None and node.val != None:
            _vals.append([node.key,node.val])
            node = node.next
        return _vals

    def pprint(self): # debug
        print(self.vals, flush=True)

if __name__ == '__main__':
    lru = LRUCache(3)
    lru.set('b', 12)
    lru.pprint()
    print('stage end: -----------------')
    lru.set('a', 12)
    lru.set('d', 12)
    lru.set('c', 12)
    lru.pprint()
    print('stage end: -----------------')
    print(lru.get('a'))
    print('stage end: -----------------')
    lru.delete('a')
    lru.pprint()
    print('stage end: -----------------')
    lru.set('d', 0)
    lru.pprint()
    print('stage end: -----------------')


    # leetcode的测试用例
    cache = LRUCache(2)
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1);       # 返回  1
    cache.pprint()
    cache.put(3, 3);    # 该操作会使得密钥 2 作废
    cache.pprint()
    cache.get(2);       # 返回 -1 (未找到)
    cache.pprint()
    cache.put(4, 4);    # 该操作会使得密钥 1 作废
    cache.get(1);       # 返回 -1 (未找到)
    cache.pprint()
    cache.get(3);       # 返回  3
    cache.get(4);       # 返回  4

参考¶

leetcode算法题：146. LRU缓存机制 https://leetcode-cn.com/problems/lru-cache/
Python 缓存机制与 functools.lru_cache http://blog.konghy.cn/2016/04/20/python-cache/

神奇的环境bug导致python3中出现udc开头字符串

2018-11-07T15:30:00+08:00

注意：LANG=zh_CN.UTF-8与LANG=en_US.UTF-8不可混淆！¶

LANG=zh_CN.UTF-8与LANG=en_US.UTF-8有区别 ，所以不可混淆！想之前在python2时代吃过坑，没想到到了统一unicode的python3，因环境不一致也能导致编码问题！

当时环境与功能：¶

vps系统是ubutnu 14.04, 相关软件python3.4, selenium3+, chrome66, chromedriver。使用crontab启动shell， shell中启动python脚本，脚本中selenium启动chrome，……

出bug的运行流程：¶

crontab中的a.sh启动 LANG=zh_CN.UTF-8 bash a.sh
a.sh末尾调用”b中文名.py”，带中文参数”《xxx》”
b中文.py 中print(参数1) 会异常显示字符串编码问题’ascii’ codec can’t encode characters

调试发现:¶

print repr(中文参数1)，会打印\udc 开头的而非\x开头的utf8型编码。
比如”《” 正常编码是 ‘\xe3\x80\x8a’，此处确是打印了’\udce3\udc80\udc8a’ 。
改变逻辑，直接ssh到vps并执行 b中文.py 《xxx》 没有问题！

问题定位:¶

个人本机ubuntu系统测试不会出现bug，vps才出现，所以应该是shell环境或者是python环境问题。
打印执行a.sh的shell环境，对比发现本机有LANG=zh_CN.UTF-8和LANGUAGE=zh_CN:zh，vps仅有LANG=zh_CN.UTF-8。
把crontab中强加的环境变量LANG=zh_CN.UTF-8去掉，此时a.sh的环境变量为LANG=en_US.UTF-8， vps恢复正常。（2小时排查出结果了！）
总结：之前觉得LANG=zh_CN.UTF-8与LANG=en_US.UTF-8没什么不同，从此改观。

问题解决：¶

去掉LANG=zh_CN.UTF-8，之后执行过程中会自动变成默认LANG=en_US.UTF-8

原因探究：¶

待定

python repr输出udc开头字符串， print(参数)导致异常¶

'/home/maskuser/path/to/ts/\udce3\udc80\udc8a\udce9\udc80\udc97.....mp4'

Traceback (most recent call last):
  File "/home/maskuser/pathtodir/script/20181105\udce8\udca7\udc86\.....py", line 73, in <module>
    video_upload_testsite(*sys.argv[1:])
  File "/home/maskuser/pathtodir/script/20181105\udce8\udca7\udc86\.....py", line 29, in video_upload_testsite
    print (videopath)
UnicodeEncodeError: 'ascii' codec can't encode characters in position 27-50: ordinal not in range(128)

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"

Linux迷+Python粉 - python

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

二分查找¶

寻找斜率为K的点对¶

参考¶

面试高频题-LRU缓存的python实现

leetcode算法题：146. LRU缓存机制¶

思考过程简要¶

leetcode通过提交的代码¶

参考¶

神奇的环境bug导致python3中出现udc开头字符串

注意：LANG=zh_CN.UTF-8与LANG=en_US.UTF-8不可混淆！¶

当时环境与功能：¶

出bug的运行流程：¶

调试发现:¶

问题定位:¶

问题解决：¶

原因探究：¶

python repr输出udc开头字符串， print(参数)导致异常¶

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

描述:¶

分析：¶

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

题目语义转化¶

扩展欧几里德算法¶

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

算法描述¶

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

Python代码:¶

参考¶

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

描述:¶

分析（动态规划）：¶

错误填表分析过程¶

正确填表分析过程¶

Python代码:¶

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