20181125_ARTS_W8
2018-12-05 本文已影响0人
活出野性的自己
Algorithm（至少一个算法题）
415. Add Strings
题目描述：两个用字符串表示的大数相加
解题思路：思路很简单，每位相加并用一个数表示进位即可
算法优化：每位相加后都是存到一个int数组的某一个位置，int能表示的范围为-2147483648至2147483647，其实就可以一次多位相加，int表示的最大范围为10位，为了保证不越界每次9位相加并考虑进位（9个数9个数为一组）。
优化注意点：按照优化的思路，结果数组每个元素的范围是0-999999999，而且除了最高位的元素，其他元素要补0补齐9位。
优化之后提交leetcode发现击败的百分比反而变小了，这个可能是因为优化只优化了空间复杂度，实现起来反而复杂了很多
实现代码如下：
/**
* 描述：大数相加
* <p>
* 优化点：参考BigInteger源码
* Created by xuery on 2018/11/25.
*/
public class BigDigitPlus {
public static void main(String[] args) {
BigInteger bigInteger = new BigInteger("12341243124341243412", 10);
System.out.println(optimizeAddStrings("6913259244", "71103343"));
}
/**
* 注意点1：虽然不包括前缀0，但是"0"是要考虑的
* <p>
* bug1: num1.charAt是Character类型，需要转换为数字:num1.charAt(i)-'0'
* bug2: new String(resultArr,0,len), resultArr为int[],不能这么转，需要借助StringBuilder
*/
public static String addStrings(String num1, String num2) {
int len = Math.max(num1.length(), num2.length()) + 1;
int carry = 0; //进位
int[] resultArr = new int[len];
int i = num1.length() - 1, j = num2.length() - 1, index = len - 1;
while (i >= 0 || j >= 0) {
if (i < 0) {
resultArr[index--] = (num2.charAt(j) + carry - '0') % 10;
carry = (num2.charAt(j--) + carry - '0') / 10;
} else if (j < 0) {
resultArr[index--] = (num1.charAt(i) + carry - '0') % 10;
carry = (num1.charAt(i--) + carry - '0') / 10;
} else {
resultArr[index--] = (num1.charAt(i) - '0' + num2.charAt(j) - '0' + carry) % 10;
carry = (num1.charAt(i--) - '0' + num2.charAt(j--) - '0' + carry) / 10;
}
}
resultArr[0] = carry;
StringBuilder sb = new StringBuilder(len);
for (int k = 0; k < len; k++) {
if (k == 0 && resultArr[0] == 0) {
continue;
} else {
sb.append(resultArr[k]);
}
}
return sb.toString();
}
/**
* 优化方案：适用于num1,num2的位数特别多的时候
* <p>
* 之前的方案是每次只运算一位，其实可以每次运算多位，resultArr数组位int型，int表示的范围为-2^31--2^31-1(-2147483648--2147483647)
* 可以表示10位之多，所以可以采用位表示9位运算（10位可能越界）
* 这样每次运算9位，减少空间消耗，提升计算效率，实际底层也是一位一位运算的，这种提升效率是对于运用层来说的
*/
public static String optimizeAddStrings(String num1, String num2) {
int len = (Math.max(num1.length(), num2.length()) + 1) / 9 + 1;
int[] resultArr = new int[len];
int carry = 0;
//9个为一组
int i = num1.length() - 1, j = num2.length() - 1, index = len - 1;
while (i >= 0 || j >= 0) {
if (i < 0) {
String sN2 = num2.substring(j - 8 > 0 ? j - 8 : 0, j + 1);
resultArr[index--] = (Integer.parseInt(sN2) + carry) % 1000000000;
carry = (Integer.parseInt(sN2) + carry) / 1000000000;
j -= 9;
} else if (j < 0) {
String sN1 = num1.substring(i - 8 > 0 ? i - 8 : 0, i + 1);
resultArr[index--] = (Integer.parseInt(sN1) + carry) % 1000000000;
carry = (Integer.parseInt(sN1) + carry) / 1000000000;
i -= 9;
} else {
//取9位，不够则有几位取几位
String sN1 = num1.substring(i - 8 > 0 ? i - 8 : 0, i + 1);
String sN2 = num2.substring(j - 8 > 0 ? j - 8 : 0, j + 1);
resultArr[index--] = (Integer.parseInt(sN1) + Integer.parseInt(sN2) + carry) % 1000000000;
carry = (Integer.parseInt(sN1) + Integer.parseInt(sN2) + carry) / 1000000000;
i -= 9;
j -= 9;
}
}
if (index >= 0) {
resultArr[index--] = carry;
}
StringBuilder sb = new StringBuilder(len);
boolean zeroLeadFlag = true;
boolean firstNoneZeroFlag = true;
for (int k = 0; k < len; k++) {
if (resultArr[k] != 0) {
zeroLeadFlag = false;
}
if (!zeroLeadFlag) {
//记得补齐9位
if (firstNoneZeroFlag) {
sb.append(resultArr[k]);
firstNoneZeroFlag = false;
} else {
String padZeroStr = padZero(String.valueOf(resultArr[k]));
sb.append(padZeroStr);
}
}
}
return zeroLeadFlag ? "0" : sb.toString();
}
private static String padZero(String s) {
StringBuilder sb = new StringBuilder();
for (int i = s.length(); i < 9; i++) {
sb.append('0');
}
sb.append(s);
return sb.toString();
}
}
Review（阅读一篇英文文章及读后感）
继续微服务相关文章, 参考教程用spring boot自己实现一个简易的微服务
microservices-with-spring-boot
image.png
- 两个微服务：CCS（consumer）和FS（provider）
- Feign用于rest请求
- Ribbon采用client-side模式负载均衡（在consumer端配置）
- Eureka Naming Service 用于服务发现（类似于zookeeper）
Tip（一个小技巧）
Logging with Spring Aop（通过Aop拦截器，统一打点方法被调用时的日志）
参考：https://five.agency/logging-with-spring-aop/
虽然一直在使用Spring，但是都是用公司已有框架，正好通过自己编写一个AOP日志拦截器复习下
Share（心得体会）
share一直不大会写，分享一下学心理学课看到的一段话：
注意你的思想，因为它将变成言辞；
注意你的言辞，因为它将变成行动；
注意你的行动，因为它将变成习惯；
注意你的习惯，因为它将变成性格；
注意你的性格，因为它将决定你的命运。
早点认识自己，慢慢成为自己，相信我们可以决定自己的命运
所以在平时的生活工作学习中，要完成的事情就立刻去做，不要找借口，行动起来，让优秀变成一种习惯，让习惯改善我们的生活，慢慢的改变自己的人生脚本。
