20181125_ARTS_W8

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一直不大会写，分享一下学心理学课看到的一段话：

注意你的思想，因为它将变成言辞；
注意你的言辞，因为它将变成行动；
注意你的行动，因为它将变成习惯；
注意你的习惯，因为它将变成性格；
注意你的性格，因为它将决定你的命运。
早点认识自己，慢慢成为自己，相信我们可以决定自己的命运

所以在平时的生活工作学习中，要完成的事情就立刻去做，不要找借口，行动起来，让优秀变成一种习惯，让习惯改善我们的生活，慢慢的改变自己的人生脚本。