ARTS-Week-5
- Algorithm：每周至少做一个 leetcode 的算法题
- Review：阅读并点评至少一篇英文技术文章
- Tip：学习至少一个技术技巧
- Share：分享一篇有观点和思考的技术文章
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:
Input: num1 = "2", num2 = "3"
Output: "6"
Example 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
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这些参数伴随多线程生产消费是会变化的，如果对这些参数的读取和修改不加锁就会产生问题。
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
