目录选举Bully算法Raft算法ZAB算法共识POW(proof of work)POS(proof of stake)DPOS(Delegate proof of stake)事务基于XA(xtented architect)协议的刚性事务二阶段提交三阶段提交柔性事务TCCSAGA本地消息表MQ最终一致性锁zookeeper实现排他锁共享锁 选举 Bully算法 选取存活的节点中id最大的做为主节点。MongoDB就是用的这种算法。 缺点：当故障节点恢复后重新加入集群，会导致切换主节点，可能引起频繁切主。 Raft算法 有3种类型的节点: Leader, Candidate and Fol...

本文为"Algorithms"一书的笔记 fibonacci 书上给出了另外一种我想不到的解法： #include <stdio.h> #define MAXN 100 int fib[MAXN]; int get_fib(int num); int main(int argc, char *argv[]) { printf("%d\n", get_fib(10)); return 0; } int get_fib(int num) { int i; fib[0] = 0; fib[1] = 1; ...

动机 看了一本叫做《C/C++面试题》的电子书，里面提到找子字符串的算法，最好的是KMP， 于是开始了KMP之旅！ 在网上看了好几篇中文文章，没一篇看得懂，最后找到了2篇英文文章，深有启发： searching-for-patterns-set-2-kmp-algorithm the-knuth-morris-pratt-algorithm-in-my-own-words 特别是第2篇，让我深刻理解了KMP中的预处理，而第1篇则让我学会了如何用高效的方法 实现预处理。 于是，我也来写一篇文章，用自己的理解来实现KMP算法。 在哪里优化？ 如果要让我写一个程序来找到子串，唯一能想到的方法就是...

基本代数 加法 十进制有一个很傻逼但是很有趣的性质： 任意3个个位数相加的和最多是两位数 事实上，对于任意进制，都有这个性质。 另外一个很有用的性质： 对于一个基数为b的k位数，它能表示的最大数为bk−1b^{k^ {-1}}bk−1 想要知道一个基数为b的数有多少位k，则： k=logb(N+1)k = log_b(N + 1)k=logb​(N+1) 乘法和除法 这里出现了一种神奇的乘法算法，对于计算机来说效率非常高， 引用wikipedia 的例子： Decimal: Binary: 11 3 1011 11 5 6 101 110 2 ...

There is an interview problem. Given a string without duplicate characters, return all permutations of the string. First Try The straightforward idea is using recursive algorithms. We enum all characters for the first position and concatate the permutations of the rest substring. However, the speed ...

import random def max_value_recursive(weights, values, max_weight, i): if len(weights) == i: return 0 if max_weight - weights[i] <= 0: return 0 value_not_pick = max_value_recursive(weights, values, max_weight, i + 1) value_pick = max_value_recursive(weights, values...

最近在做leetcode时，发现了另外一种二叉树遍历的方法，于是总结回之前掌握的遍历方法，做此笔记。 建树 首先定义一棵树，val为元素的值，left是左节点，right是右节点。 并做最基本的建树操作，传入一个数组，构造一棵二分查找树。 class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None class BinaryTree: def __init__(self, arr): self.r...

import numpy as np import matplotlib.pyplot as plt %matplotlib notebook N = 10 OBSTALE = '1' ROAD = '*' START = 'S' END = 'E' game_map = np.array([[ROAD] * 10] * 10) game_map[1:5, 1] = OBSTALE game_map[8:10, 1] = OBSTALE game_map[2:6, 3] = OBSTALE game_map[7:10, 3] = ...

最近在《编程珠玑》上看到一道很有趣的题目: 假设我们在开发一个编辑器，要实现一个功能，将下面代码的2个函数调换位置，该怎么做呢？如果空间复杂度要求O(1)O(1)O(1)，又应该怎么做呢？ texts = [ 'def add(a, b):', ' return a + b', ' ', 'def sub(a, b):', ' retturn a - b', ' ' ] 其实这就是数组左旋转的问题，将数组的前3个元素移到数组的结尾。我最直接的想法...

场景 假设有一个手机号数组，要求对这个数组进行排序，怎么样排序最快呢？ 一般我们会用快排来实现，现场写一个快排: from collections import deque def swap(strs, i, j): temp = strs[i] strs[i] = strs[j] strs[j] = temp def quick_sort(strs): queue = deque([0, len(strs) - 1]) while len(queue) > 0: start = queue.popleft() ...

最近在学习KD树，研究了一天，终于是搞懂了！把自己实现的代码记录下来。 KNN的算法思想非常简单，但是暴力的计算距离，计算量非常大，而KD树这种数据结构的使用，可以将KNN的时间复杂度从O(KN)O(KN)O(KN)降低到O(KlogN)O(KlogN)O(KlogN)，这也是我非常感兴趣的一点。 学习的过程中，发现还有一种叫ball树，是为了解决KD树在高维时计算慢的问题，学无止境啊，这个就得后面慢慢研究了。 原理就不记录了，可以参考这个链接, 下面是我实现的代码: import numpy as np import timeit import matplotlib.pyplot as pl...

在看《算法导论》，思考题里面提到霍纳规则，出于好奇，查一下这个陌生的名词，结果发现了新大陆，原来在中国这个叫秦九韶算法，好像在中学的时候看过，现在肯定是忘光了，复习一下。 原来是一种计算一元多次函数的高效算法。比如给一个函数f(x)=1+2x+3x2+4x3+5x4f(x) = 1 + 2x + 3x^2 + 4x^3 + 5x^4f(x)=1+2x+3x2+4x3+5x4, 让我来写代码来计算，我一定是暴力计算，直接用求幂函数pow来算x，然后加起来。 现在就体现了算法的重要性，如果用上面的暴力算法，时间复杂度是O(n2)O(n^2)O(n2)，如果应用霍纳规则，时间复杂度居然可以达到O(n...

这是一篇内部小型技术分享的文章。 这次我们要来学习一个求近似平方根的快速方法: 牛顿法。 先上代码: def sqrt(n): ret = n while ret * ret > n: ret = (ret + n / ret) / 2 return ret print(sqrt(4)) print(sqrt(2)) 2.0 1.414213562373095 代码很简短，很神奇，为什么这样子可以求出来平方根呢？下面来推导一下。 设n的平方根为x， 则有 x2=nx^2 = nx2=n, 即x2−n=0x^2 - n = 0x2−n=0, 写成...

最近在看《集体智慧编程这本书》，再次学习k-means算法，虽然之前接触过很多，但是没有完全自己实现过，这次就试着根据算法思想，手写k-means算法。 这里使用的数据是书里面的博客数据，第一行是表头，第一列是博客名称，后面的列是每个单词出现的次数，大概长这样： Blog be not your Signal v. Noise - Medium 46 32 47 Eschaton 13 21 1 k-means算法的思想大概是这样子的： 先随机初始化k个点，称为中心点 对于数据集中的每条记录，计算它与每个中心点的距离，把它归到距离它最近的中心点的分组中 对于每个分组，通过均值计算中心点，得...

判断一个链接有没有环，很著名的算法是Floyd判圈算法，也叫龟兔算法。但是，原来还有一种算法，可以比Floyd更快一点，这种算法叫做Brent判圈算法。 算法思想 用2个指针rabbit和turtle从链表头出发。 rabbit先一步一步走，最多走2步，如果走到尽头，则无环，如果和turtle相遇，则有环，否则，本轮结束。 这个时候，把turtle放到rabbit当前位置，rabbit继续一步一步走，但是最多走4步，如果走到尽头，则无环，如果和turtle相遇，则有环，否则，本轮结束。 然后，把turtle放到rabbit当前位置，rabbit继续一步一步走，但是最多走8步，如果走到尽头，则...

summary : 面试中经常会让你写出三种遍历中的一种的非递归版本，通常是中序遍历和后序遍历，前序 遍历很少，因为前序遍历毕竟比较简单。 以我的智商，没有做过的话，只能想出来前序遍历的非递归版本，而中序遍历和后序遍历则 是绞尽脑汁都想不出来。最终参考了别人的做法，才理解并写出来了，算是记忆，估计再过 一段时间我又忘了。不过到时可以翻开我的这篇文章看看。 前序遍历 这个是最简单的。用一个栈存储节点，先输出栈顶元素的值，再把左右孩子的节点入栈（如 果有的话）。由于在遍历的时候是先遍历左子树再遍历右子树，那么反过来，在入栈的时候， 就先把右孩子入栈，再把左孩子入栈。 中序遍历 有难度。得先从...

summary : 面了两家公司，都是这个题，都不会做。不管以后还去不去面试，我都 一定 要把这 货给解决！ 学了四年计算机，四年了，始终无法理解动态规划的精妙，能看懂，但是叫我想，我想不 出来。贪心思想，都能说，但是真正要运用，却不会。有的时候，智商问题就是无解。 假定给一个序列为：-10 1 2 3 4 -5 -23 3 7 -21。 开始分析。不管是用暴力方法还是用动态规划的方法，都必须要用一个数存放目前最大的 子段和，就用sum来记录吧。每得到一个临时的子段和，都要和这个最大的子段和比较， 如果临时的子段和较大，则更新，这个临时的子段和就叫temp_sum吧。有的时候，可能 要求...

summary : 这是我去人人面试的时候遇到的题，当时我写出来健壮性不好，立马就被刷了。 题目 给出两个单链表，升序排序好了，要求合并两个链表，合并之后还是升序排序，而且去重。 链表的节点结构如下： struct Node { : int value; struct Node \*next; }; 分析 没啥好分析，合并加去重，关键是要注意很多特殊情况，要写多一些测试用例。这里，我 用的是递归的方式实现，每次取得两个链表比较之后的头节点，并放到合并之后的链表的 后面。 我的代码 ::: {.code-include lexer="cpp"} ./merge...

summary : 题目 输入数字n，打印从1到最大的n位十进制数。如输入3,则打印1, 2, 3 ... 999。 分析 考虑特殊情况，n是否可以是负数或0。问面试官，n是否可以很大？如果n可以是很大，则 不能用int, long long来存，这个时候变成了高精度数据的问题，应该用字符串。而从 1到最大的N位数，其实就是这么多位数字的从0到9的全排列，于是可以递归地打印出来。 代码 ::: {.code-include lexer="cpp"} ./print_one_to_max_n_digit_number.cpp :::...

summary : 很经典的一道题，而且是很多位运算的题目的鼻祖，掌握它，很多问题的变种就可以解决 了。 题目 实现一个函数，输入一个整数，返回这个整数的二进制表示中1的个数。 分析 对于正数和0，很简单，先和0x1进行与运算，如果结果是1,则最低位是1。然后不断右移， 进行相同的判断，直到这个数变成0为止。 但是对于负数，就不能像上面那样做了，因为右移的话，左边会补1,则无法判断什么时候 结束了。这样有两种方法： 对于负数，规定右移31次就结束。 对于负数，先用0x1和这个数进行与运算，然后把0x1左移一位，变成了0x2，再进行 与运算，直到变成了0。这样也是移动了31次。 更好的...