- Algorithm：每周至少做一个 leetcode 的算法题
- Review：阅读并点评至少一篇英文技术文章
- Tip：学习至少一个技术技巧
- Share：分享一篇有观点和思考的技术文章
ARTS挑战
Algorithm
43. Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
1
2
|
Input: num1 = "2", num2 = "3"
Output: "6"
|
Example 2:
1
2
|
Input: num1 = "123", num2 = "456"
Output: "56088"
|
Note:
- The length of both num1 and num2 is < 110.
- Both num1 and num2 contain only digits 0-9.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
该题本身有限定条件：
- 两数长度小于110，其实这个条件对算法的实现没太大意义，就算是更大的长度也要能算，只不过耗时更久点吧
- 两个数都是数字，那样我们就不用校验了，并且没有符号的，表示都是正数
- 两个数没有前导的0，除了本身就是0，这样也少了一步去除前导0的步骤
但是下面的算法是假设没有这些限定条件的，也就是说，会有如下情况：
- 字符串可能不合法，有非数字的字符
- 有符号位，可正可符，例如：-99，+99
- 有前导0，例如：-0099，+0099， 0099
在这样的前提下，代码如下。
Runtime: 7 ms, faster than 78.84% of Java online submissions for Multiply Strings.
Memory Usage: 38.8 MB, less than 38.50% of Java online submissions for Multiply Strings.
主要的问题在于内存占用比较大，原因是很多直接对字符串进行操作，需要对字符串进行拷贝，所以占用了空间，可以通过预先分配字符数组的方式，通过操作数组减少内存分配。
另外Discussion中点赞最多的答案, 很巧妙，定义了一个成绩图，通过找到两数中i,j位乘积与乘积图的位置关系，让代码非常简介。Easiest JAVA Solution with Graph Explanation
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
class Solution {
public String multiply(String num1, String num2) {
// 校验参数，leetcode本题有限定条件，是不需要校验的
String num1c = numCheckAndRemoveHeadZero(num1);
String num2c = numCheckAndRemoveHeadZero(num2);
if (num1c == null || num2c == null) {
throw new IllegalArgumentException("参数不合法");
}
if (num1c.equals("0") || num2c.equals("0")) {
return "0";
}
// 处理结果的符号
boolean negative = false;
int negativeCount = 0;
if (num1c.charAt(0) == '-') {
negativeCount++;
num1c = num1c.substring(1);
}
if (num2c.charAt(0) == '-') {
negativeCount++;
num2c = num2c.substring(1);
}
if (negativeCount == 1) {
negative = true;
}
String result = "0";
char[] mRes = new char[num2c.length() + 1];
StringBuilder appendZero = new StringBuilder();
// 按照乘法运算规则，循环相乘相加
for (int i = num1c.length() - 1; i >= 0; i--) {
int multiplyUpNum = 0;
int oneNum = num1c.charAt(i) - '0';
if (i < num1c.length() - 1) {
appendZero.append("0");
}
for (int j = num2c.length() - 1; j >= 0; j--) {
int twoNum = num2c.charAt(j) - '0';
int jNum = oneNum * twoNum + multiplyUpNum;
if (jNum > 9) {
multiplyUpNum = jNum / 10;
mRes[j + 1] = (char) (jNum % 10 + '0');
} else {
multiplyUpNum = 0;
mRes[j + 1] = (char) (jNum + '0');
}
}
if (multiplyUpNum == 0) {
result = add(new String(mRes, 1, mRes.length - 1) + appendZero, result);
} else {
mRes[0] = (char) (multiplyUpNum + '0');
result = add(new String(mRes) + appendZero, result);
}
}
return negative ? '-' + result : result;
}
/**
* 两个正数相加
*/
private String add(String num1, String num2) {
String max;
String min;
if (num1.length() > num2.length()) {
max = num1;
min = num2;
} else {
max = num2;
min = num1;
}
int minIndex = min.length() - 1;
char[] result = new char[max.length() + 1];
boolean addUp = false;
for (int maxIndex = max.length() - 1; maxIndex >= 0; maxIndex--) {
int iChar;
if (minIndex < 0) {
iChar = addUp ? max.charAt(maxIndex) + 1 : max.charAt(maxIndex);
} else {
int i1 = max.charAt(maxIndex) + min.charAt(minIndex--) - '0';
iChar = addUp ? i1 + 1 : i1;
}
addUp = iChar > '9';
result[maxIndex + 1] = (char) (addUp ? iChar - 10 : iChar);
}
if (addUp) {
result[0] = '1';
return new String(result);
} else {
return new String(result, 1, result.length - 1);
}
}
/**
* 带符号的数字检查，并去除前导0
*/
private String numCheckAndRemoveHeadZero(String num) {
if (num.length() == 0) {
return null;
}
char firstChar = num.charAt(0);
boolean negative = false;
int numBegin = 0;
if (firstChar == '-') {
negative = true;
numBegin = 1;
} else if (firstChar == '+') {
numBegin = 1;
}
if (numBegin > num.length() - 1) {
return null;
}
int headZeroIndex = numBegin - 1;
boolean headZeroRemoved = false;
for (int i = numBegin; i < num.length(); i++) {
char aChar = num.charAt(i);
if (aChar < '0' || aChar > '9') {
return null;
}
if (!headZeroRemoved) {
if (aChar == '0' && i < num.length() - 1) {
headZeroIndex = i;
} else {
headZeroRemoved = true;
}
}
}
String result = num.substring(headZeroIndex + 1);
if (negative) {
if (result.equals("0")) {
result = "0";
} else {
result = '-' + result;
}
}
return result;
}
}
|
415. Add Strings
上题中包含了两大数相乘, 直接把add方法拷过去就可以，结果如下：
Runtime: 1 ms, faster than 100.00% of Java online submissions for Add Strings.
Memory Usage: 37.2 MB, less than 95.20% of Java online submissions for Add Strings.
用wait-notify写一个解决生产消费者问题
最主要的就是阻塞的条件需要是循环检测，并且在锁代码块内。因为条件，buff这些参数伴随多线程生产消费是会变化的，如果对这些参数的读取和修改不加锁就会产生问题。
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
public class WaitNotifyImpl {
String[] buff = new String[10];
int index = -1;
final Object lock = new Object();
class Producer implements Runnable {
int id = 0;
@Override
public void run() {
String threadName = Thread.currentThread().getName();
while (true) {
synchronized (lock) {
while (index == buff.length - 1) {
try {
System.out.println("生产者：" + threadName + ", 缓存满了，等待");
lock.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
String name = threadName + "：" + id;
buff[++index] = name;
System.out.println("生产数据：" + name + ", index:" + index);
lock.notify();
}
id++;
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
class Consumer implements Runnable {
@Override
public void run() {
String threadName = Thread.currentThread().getName();
while (true) {
synchronized (lock) {
while (index < 0) {
try {
System.out.println("消费者：" + threadName + ", 缓存空了，等待");
lock.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println("消费数据：" + buff[index] + ", index:" + index);
index--;
lock.notify();
}
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
public void start() {
for (int i = 0; i < 10; i++) {
new Thread(new Producer()).start();
new Thread(new Consumer()).start();
}
}
public static void main(String[] args) {
new WaitNotifyImpl().start();
}
}
|
Review
原文：In Search of an Understandable Consensus Algorithm (Extended Version)
这是之前看的，做过一次分享，来复习下。PPT: 分布式共识算法Raft
两个概念，共识(Consensus)和一致性(Consistency), Consensus是达成一致的过程，是手段；Consistency是数据的状态，是结果。达成某种共识不意味着保障了一致性，只能说共识机制能实现某种程度的一致性。
共识是过程，那这个过程怎么进行会有一个共识算法, 通常的共识算法就是对某个提案（Proposal），大部分节点达成一致意见的过程。Proposal可以是事件发生的顺序、某个键值对的值、谁是主节点等。
如何达成不同节点对提案的共识呢，这里引出复制状态机（State-Machine-Replication）,假设每个节点从相同的初始状态开始接收相同顺序的指令，则可以保证相同的结果状态。进而推导出共识的关键是对多个事件（指令）的顺序进行共识，即排序。
复制状态机的架构，保存来自客户端的指令log，然后状态机执行这些来自log的顺序唯一的指令序列，最终每个节点产生相同的输出。
那么如何保证所有节点都接收到相同顺序的指令呢？如果不同的指令分散到不同的机器上，我们唯一能确定顺序的就只有时间了，但是机器的时间不是很精确，除非使用原子钟，就算这样也只是在原子钟误差范围内的顺序。所以要想保证真正的顺序，只能让所有的请求都由一台机器来处理，这台机器就是leader，然后让把排好序的指令同步给其它节点，防止自己挂了之后丢消息。
考虑到节点之间通过网络通信，总会有一些节点下线或者没有回应，那么当指令过来时，leader节点先进行持久化，然后把数据同步给其它节点，其实只要获得多数节点的回应既可以认为是安全的，因为共识算法会保证在重新选主的时候多数人能占优势，一定是接收了leader最新消息的节点选主胜出。
Raft共识算法的三个角色：Leader（领导者）、Follower（跟随者）、Candidate（候选人）
更多细节下次再写吧。。。
Tip
工作上的一个坑：
Java正则替换异常问题
Share
NotImplementException
