Posted on | In

可以把当前脚本目录下的gif转为mp4

脚本会递归目录的子目录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import moviepy.editor as mp
# vfc = mp.VideoFileClip("binary_tree_preorder_traversal.gif")
# vfc.write_videofile("binary_tree_preorder_traversal.mp4")

# vfc = mp.VideoFileClip(".\\mp/binary_tree_preorder_traversal.gif")
# vfc.write_videofile(".\\mp/binary_tree_preorder_traversal1231.mp4")

import os

def getfilelist(rlist,path, ex_filter):
    for dir,folder,file in os.walk(path):
        for i in file:
            if ex_filter not in i:
                continue
            t = "%s/%s"%(dir,i)
            rlist.append(t)

all_gif_path = []
getfilelist(all_gif_path, ".", ".gif")
print all_gif_path

for _gif_path in all_gif_path:
    vfc = mp.VideoFileClip(_gif_path)
    vfc.write_videofile(_gif_path.replace(".gif", ".mp4"))

Posted on | In

算法白话总结

推荐参考本博客总结的 algo_newbie

本文完整参考代码

https://github.com/no5ix/no5ix.github.io/blob/source/source/code/test_algo_practice.py

实战练习 pending_fini

  • 比狗线程排列题
  • 刷完剑指offer
  • 回溯法递归强化

  • 二叉树递归强化

  • lc4题-两个排序数组找中位数, 困难

  • 一个桶里面有白球. 黑球各 100 个，现在按下述的规则取球：
    i . 每次从桶里面拿出来两个球；
    ii. 如果取出的是两个同色的球，就再放入一个黑球；
    iii. 如果取出的是两个异色的球，就再放入一个白球。
    问：最后桶里面只剩下一个黑球的概率是多少？

  • 公司有内部 bbs，员工都会在上面发帖交流。据统计，有三个员工 ID 发帖很多，他们各自的发帖量都超过帖子总数 N 的 1/4。如果给到你所有帖子的发帖人 ID 列表，请写代码找出这三个 ID，要求时间复杂度 O（n），空间复杂度 O（1）。

finished

  • leetcode64题最短路径和
  • 判断是否有一个数num在有序数组中出现次数多于数组长度的一半
    • 判断num是否等于中间的数即可
  • 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
    • 根据数组特点得到时间复杂度为O(n)的算法。根据数组特点，数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现的次数之和还要多。因此，我们可以在遍历数组的时候设置两个值：一个是数组中的数result，另一个是出现次数times。当遍历到下一个数字的时候，如果与result相同，则次数加1,不同则次数减一，当次数变为0的时候说明该数字不可能为多数元素，将result设置为下一个数字，次数设为1。这样，当遍历结束后，最后一次设置的result的值可能就是符合要求的值（如果有数字出现次数超过一半，则必为该元素，否则不存在），因此，判断该元素出现次数是否超过一半即可验证应该返回该元素还是返回0。这种思路是对数组进行了两次遍历，复杂度为O(n)。
  • 给定一个含有n个元素的整型数组a，其中只有一个元素出现奇数次，找出这个元素。
    • 解决问题的关键是要想明白，按位异或运算满足结合律，偶数个异或结果是0，奇数个异或结果是本身，如1 ^ 2 ^ 3 ^ 1 ^ 2 ^ 3 ^ 3 = (3 ^ 3 ^ 3) ^ (1 ^ 1) ^ (2 ^ 2) = 3^ 0 ^ 0 = 3。
  • 一个无序数组找其子序列构成的和最大，要求子序列中的元素在原数组中两两都不相邻, 和是多少?具体是哪个子序列?
  • lc445, 两个单向链表，返回求和后的链表结构, 例如2->3->1->5，和3->6，结果返回2->3->5->1
    • 用栈
    • 反转链表再相加

  • 现有一个随机数生成器可以生成0到4的数，现在要让你用这个随机数生成器生成0到6的随机数，要保证生成的数概率均匀。

    • 别被这个题目唬住了, 其实很简单
    • 大多数利用一个等概率随机数构造另外一个等概率随机数的题目，只需两次使用概率函数即可
    • 代码如下:
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      def rand4():
      	# 这是题目给的
      	pass

      def rand6():
      	res = rand4()
      	# 只要0和1和2, 注意这个0不可少, 不然`res + rand4()`生成的数至少为1
      	while res > 2:
      		res = rand4()
      	# 这样就能保证是等概率0到4 , 等概率的加(0, 1, 2), 得到等概率的0-6
      	return res + rand4()

  • 连续整数求和(leetcode第829题, hard实际有思路就easy)，要求时间复杂度小于O(N)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution:
       def consecutiveNumbersSum(self, N: int) -> int:
           # 1个数时，必然有一个数可构成N
           # 2个数若要构成N，第2个数与第1个数差为1，N减掉这个1能整除2则能由商与商+1构成N
           # 3个数若要构成N，第2个数与第1个数差为1，第3个数与第1个数的差为2，N减掉1再减掉2能整除3则能由商、商+1与商+2构成N
           # 依次内推，当商即第1个数小于等于0时结束
           res, i = 0, 1
           while N > 0:
               res += N % i == 0
               N -= i
               i += 1
           return res

智力题

  • 有 64 匹马，赛场只有 8 条赛道，请问最少需要比赛多少场才能确定跑得最快的那 4 匹马，不可以借助计时器给每一匹马一一计时；
  • 有 N 枚棋子，每个人一次可以拿1到 M 个，谁拿完后棋子的数量为0谁就获胜。现在有1000颗棋子，每次最多拿8个，A 先拿，那么 A 有必胜的拿法吗？
    • 这个是个智力题不是算法题, 是倍数的思想
    • 这类题得先求得 N % (M+1) 的余数, 此处为 1000 % (8+1) = 1, 求得此余数Y后, 先拿的人第一次就拿Y个, 然后假如B同学第二次拿X个比如是4个, 不管B拿多少个, A之后都拿 (M+1)-X个即 (8+1)-4=5个和B同学拿的4个凑成(8+1)=9个, 这样就保证了A是最后一个拿完棋子的人

misc

寻找第K大

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

测试样例：
[1,3,5,2,2],5,3
返回：2

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
class Solution_find_top_k_num(object):
    def find_top_k_num(self, nums_arr, nums_arr_len, top_k):
        assert nums_arr, "nums is empty."
        assert nums_arr_len > 0, "nums is empty."
        if top_k > nums_arr_len or top_k < 0:
            return None
        left_index = 0
        right_index = nums_arr_len - 1
        _p_index = self._partition(nums_arr, left_index, right_index)
        while _p_index != top_k-1:
            _p_index = self._partition(nums_arr, left_index, right_index)
            if _p_index < top_k-1:
                left_index = _p_index + 1
            elif _p_index > top_k-1:
                right_index = _p_index - 1
        return nums_arr[_p_index]

    def _partition(self, nums_arr, left_index, right_index):
        pivot_index = left_index
        _partition_index = pivot_index
        for i in range(pivot_index+1, right_index+1):
            if nums_arr[i] <= nums_arr[pivot_index]:
                nums_arr[_partition_index+1], nums_arr[i] = \
                    nums_arr[i], nums_arr[_partition_index+1]
                _partition_index += 1
        nums_arr[_partition_index], nums_arr[pivot_index] = \
            nums_arr[pivot_index], nums_arr[_partition_index]
        return _partition_index

leetcode

lc41-缺失的第一个正数

lc41, hard 缺失的第一个正数（leetcode第41题）
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3

示例 2:
输入: [3,4,-1,1]
输出: 2

示例 3:
输入: [7,8,9,11,12]
输出: 1

提示：你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

参考
我们可以采取这样的思路：就把 11 这个数放到下标为 00 的位置， 22 这个数放到下标为 11 的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第 11 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。
这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置。

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
36
37
38
39
40
41
42
43
44
45
class Solution_lc41(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        思路: 使用座位交换法
        根据题意可知，缺失的第一个整数是在 [1, len + 1] 之间，
        那么我们可以遍历数组，然后将对应的数据填充到对应的位置上去，比如 1 就填充到 nums[0] 的位置， 2 就填充到 nums[1]
        如果填充过程中， nums[i] < 1 && nums[i] > len，那么直接舍弃
        填充完成，我们再遍历一次数组，如果对应的 nums[i] != i + 1，那么这个 i + 1 就是缺失的第一个正数

        比如 nums = [7, 8, 9, 10, 11], len = 5
        我们发现数组中的元素都无法进行填充，直接舍弃跳过，
        那么最终遍历数组的时候，我们发现 nums[0] != 0 + 1，即第一个缺失的是 1 

        比如 nums = [3, 1, 2], len = 3
        填充过后，我们发现最终数组变成了 [1, 2, 3]，每个元素都对应了自己的位置，那么第一个缺失的就是 len + 1 == 4
        """ 
        if not nums:
            return 1
        n = len(nums)
        for i in range(n):
            _pending_swap_index = nums[i] - 1
            # 只有在 nums[i] 是 [1, len] 之间的数，并且不在自己应该呆的位置， nums[i] != i + 1 ，
            # 并且 它应该呆的位置没有被相同的值占有（即存在重复值占有）	nums[nums[i] - 1] != nums[i] 的时候才进行交换
            # 为什么使用 while ？ 因为交换后，原本 i 位置的 nums[i] 已经交换到了别的地方，
            # 交换后到这里的新值不一定是适合这个位置的，因此需要重新进行判断交换
            # 如果使用 if，那么进行一次交换后，i 就会 +1 进入下一个循环，那么交换过来的新值就没有去找到它该有的位置
            # 比如 nums = [3, 4, -1, 1] 当 3 进行交换后， nums 变成 [-1，4，3，1]，
            # 此时 i == 0，如果使用 if ，那么会进入下一个循环， 这个 -1 就没有进行处理
            while(n >= nums[i] >= 1 and nums[i] != i+1 and \
                    nums[i] != nums[_pending_swap_index]):
                # `nums[i] != nums[_pending_swap_index]` 是为了防止
                # nums[i] 和 nums[_pending_swap_index] 这两个数是相等的导致
                # while死循环
                self._swap(nums, i, _pending_swap_index)
                _pending_swap_index = nums[i] - 1

        for i in range(n):
            if nums[i] != i + 1:
                return i + 1                
        return n + 1
        
    def _swap(self, arr, index1, index2):
        arr[index1], arr[index2] = arr[index2], arr[index1]

Posted on | In

Cache Aside Pattern

什么是 “Cache Aside Pattern”？
答：旁路缓存方案的经验实践，这个实践又分读实践，写实践。

对于读请求

先读 cache，再读 db
如果，cache hit，则直接返回数据
如果，cache miss，则访问 db，并将数据 set 回缓存

（1）先从 cache 中尝试 get 数据，结果 miss 了
（2）再从 db 中读取数据，从库，读写分离
（3）最后把数据 set 回 cache，方便下次读命中

对于写请求

先操作数据库，再淘汰缓存（淘汰缓存，而不是更新缓存）

如上图：
（1）第一步要操作数据库，第二步操作缓存
（2）缓存，采用 delete 淘汰，而不是 set 更新

Cache Aside Pattern 为什么建议淘汰缓存，而不是更新缓存

答：如果更新缓存，在并发写时，可能出现数据不一致。

如上图所示，如果采用 set 缓存。

在 1 和 2 两个并发写发生时，由于无法保证时序，此时不管先操作缓存还是先操作数据库，都可能出现：
（1）请求 1 先操作数据库，请求 2 后操作数据库
（2）请求 2 先 set 了缓存，请求 1 后 set 了缓存
导致，数据库与缓存之间的数据不一致。
所以，Cache Aside Pattern 建议，delete 缓存，而不是 set 缓存。

Cache Aside Pattern 为什么建议先操作数据库，再操作缓存？

答：如果先操作缓存，在读写并发时，可能出现数据不一致。

如上图所示，如果先操作缓存。

在 1 和 2 并发读写发生时，由于无法保证时序，可能出现：
（1）写请求淘汰了缓存
（2）写请求操作了数据库（主从同步没有完成）
（3）读请求读了缓存（cache miss）
（4）读请求读了从库（读了一个旧数据）
（5）读请求 set 回缓存（set 了一个旧数据）
（6）数据库主从同步完成
导致，数据库与缓存的数据不一致。

所以，Cache Aside Pattern 建议，先操作数据库，再操作缓存。

Cache Aside Pattern 方案存在什么问题？

答：如果先操作数据库，再淘汰缓存，在原子性被破坏时：
（1）修改数据库成功了
（2）淘汰缓存失败了
导致，数据库与缓存的数据不一致。

个人见解：这里个人觉得可以使用重试的方法，在淘汰缓存的时候，如果失败，则重试一定的次数。如果失败一定次数还不行，那就是其他原因了。比如说 redis 故障、内网出了问题。

关于这个问题，沈老师的解决方案是，使用先操作缓存（delete），再操作数据库。假如删除缓存成功，更新数据库失败了。缓存里没有数据，数据库里是之前的数据，数据没有不一致，对业务无影响。只是下一次读取，会多一次 cache miss。这里我觉得沈老师可能忽略了并发的问题，比如说以下情况：
一个写请求过来，删除了缓存，准备更新数据库（还没更新完成）。
然后一个读请求过来，缓存未命中，从数据库读取旧数据，再次放到缓存中，这时候，数据库更新完成了。此时的情况是，缓存中是旧数据，数据库里面是新数据，同样存在数据不一致的问题。
如图：

主从同步延迟导致的缓存和数据不一致问题

答：发生写请求后（不管是先操作 DB，还是先淘汰 Cache），在主从数据库同步完成之前，如果有读请求，都可能发生读 Cache Miss，读从库把旧数据存入缓存的情况。此时怎么办呢？

数据库主从不一致
先回顾下，无缓存时，数据库主从不一致问题。

如上图，发生的场景是，写后立刻读：
（1）主库一个写请求（主从没同步完成）
（2）从库接着一个读请求，读到了旧数据
（3）最后，主从同步完成
导致的结果是：主动同步完成之前，会读取到旧数据。

可以看到，主从不一致的影响时间很短，在主从同步完成后，就会读到新数据。

缓存与数据库不一致
再看，引入缓存后，缓存和数据库不一致问题。

如上图，发生的场景也是，写后立刻读：
（1+2）先一个写请求，淘汰缓存，写数据库

（3+4+5）接着立刻一个读请求，读缓存，cache miss，读从库，写缓存放入数据，以便后续的读能够 cache hit（主从同步没有完成，缓存中放入了旧数据）

（6）最后，主从同步完成

导致的结果是：旧数据放入缓存，即使主从同步完成，后续仍然会从缓存一直读取到旧数据。

可以看到，加入缓存后，导致的不一致影响时间会很长，并且最终也不会达到一致。

问题分析

可以看到，这里提到的缓存与数据库数据不一致，根本上是由数据库主从不一致引起的。当主库上发生写操作之后，从库 binlog 同步的时间间隔内，读请求，可能导致有旧数据入缓存。

思路：那能不能写操作记录下来，在主从时延的时间段内，读取修改过的数据的话，强制读主，并且更新缓存，这样子缓存内的数据就是最新。在主从时延过后，这部分数据继续读从库，从而继续利用从库提高读取能力。

不一致解决方案

选择性读主

可以利用一个缓存记录必须读主的数据。

如上图，当写请求发生时：
（1）写主库
（2）将哪个库，哪个表，哪个主键三个信息拼装一个 key 设置到 cache 里，这条记录的超时时间，设置为 “主从同步时延”
PS：key 的格式为 “db:table:PK”，假设主从延时为 1s，这个 key 的 cache 超时时间也为 1s。

如上图，当读请求发生时：
这是要读哪个库，哪个表，哪个主键的数据呢，也将这三个信息拼装一个 key，到 cache 里去查询，如果，
（1）cache 里有这个 key，说明 1s 内刚发生过写请求，数据库主从同步可能还没有完成，此时就应该去主库查询。并且把主库的数据 set 到缓存中，防止下一次 cahce miss。
（2）cache 里没有这个 key，说明最近没有发生过写请求，此时就可以去从库查询

以此，保证读到的一定不是不一致的脏数据。

PS：如果系统可以接收短时间的不一致，建议建议定时更新缓存就可以了。避免系统过于复杂。