Algorithm
LeetCode算法题
Java 程序实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public String removeKdigits(String num, int k) {
if (num == null || num.equals("") || num.length() <= k) return "0";
int digits = num.length() - k;
char[] stack = new char[num.length()];
int top = 0;
for (int i = 0; i < num.length(); i++) {
while (k > 0 && top > 0 && stack[top - 1] > num.charAt(i)) {
top--; k--;
}
stack[top++] = num.charAt(i);
}
int initial = 0;
while (initial < digits && stack[initial] == '0') {
initial++;
}
return initial == digits ? "0" : new String(stack, initial, digits - initial);
}
}
Review
-
依赖一个第三方的全局序列发生器
-
能够实现分布式一致性算法的一个前提条件：信道可信，即非拜占庭问题，message可以重复、可以丢失，但是不可以篡改伪造；约束条件：1、局域网，程序逻辑可控；2、网络算法，如TCP数据包完整性检测
-
P1：是对Acceptor的约束，必须接受其第一个收到的Proposal
-
P1a：是对Acceptor的约束，某Acceptor Accept某Proposal的充分必要条件是没有响应过更大编号的Proposal
-
P2：是对整体系统状态的约束，一旦某Proposal被选定，后续被选定的较大编号Proposal的内容与前者Proposal的内容一致
-
P2a：是对Acceptor的约束，一旦某Proposal被选定，后续被Accept的较大编号Proposal的内容与前者Proposal的内容一致
-
P2b：是对Proposer的约束，一旦某Proposal被选定，后续提出的较大编号Proposal的内容与前者的Proposal的内容一致
-
P2c：是对Acceptor群体的约束，一旦某Proposal<n, v>被提出，一定存在这样的一个Acceptor群体的大多数：要么没有Accept编号小于n的Proposal，要么在所有Accept的Proposal中最大编号的Proposal的内容就是v
-
Learner：快速学习整体系统的状态，有三种模式：最可靠且最大流量、最脆弱且最小流量、tradeoff
-
四个阶段：Prepare-Promise-Propose-Accept
-
如果Proposer不做限制的话，极端情况下有可能会出现，两个Proposer不停的交替提出Proposal而不能被Acceptor所Accept
Tip
- 艺多不压身，T型人才，保证技术的深度与广度。
