Algorithm

本周的 LeetCode 题目为 8. 字符串转换整数 (atoi)

题目简介：请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。具体的要求可访问上面的链接查看。

题目思路：因为 int 可能会存在溢出，因此可以先用 long 变量储存结果，而后再判断有无溢出。字符串匹配规则如下：

• （可选）开始是空格可以自动跳过
• （可选）+/- 可以用来记录是否为正负数
• （必选）isDigit(ch) == true 就是数字
  需要注意的是：
• (必然会错) 接收到 +/- 号后，接下来必须得是数字，中间其他任何字符都是不合法的（包括空格）
• （必然会错）一旦开始接收数字后，接下来必须是数字，其他字符都是不合法的

最后需要判断下结果是否超过了 int 的范围，若超过则根据题目说明进行设置，反之直接返回结果即可。

最终代码

class Solution {
    public int myAtoi(String s) {
        long ans = 0;
        boolean isPositive = true;
        boolean isStart = false;
        int isOutOfRange = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '-') {
                if (isStart == false) {
                    isPositive = false;
                } else {
                    break;
                }
                isStart = true;
            } else if (s.charAt(i) == '+') {
                if (isStart == true) {
                    break;
                }
                isStart = true;
            } else if (Character.isDigit(s.charAt(i)) == true) {
                if (isStart == false) {
                    isStart = true;
                }
                ans = ans * 10 + Character.digit(s.charAt(i), 10);
                if ((isPositive == false) && (-ans <= Integer.MIN_VALUE)) {
                    isOutOfRange = -1;
                    break;
                } else if (ans > Integer.MAX_VALUE) {
                    isOutOfRange = 1;
                    break;
                }
                else {
                    continue;
                }
            } else {
                if ((isStart == false) && s.charAt(i) == ' ' ) {
                    continue;
                }
                break;
            }
        }
        switch (isOutOfRange) {
            case 1:
                return Integer.MAX_VALUE;
            case -1:
                return Integer.MIN_VALUE;
            default:
                if (isPositive == false) {
                    return (int) -ans;
                } else {
                    return (int) ans;
                }
        }
    }
}

除了常规解法外，本题目还可以通过 确定有限状态机（deterministic finite automaton, DFA） 来进行解决，具体解法可以参考另一篇文章（目前未更新）

Review

本周 Review 的英文文章为：Social networks: It’s worse than you think。

在这篇文章中，作者介绍说，信息传播也遵循一个幂律：如果一个信息包含的字数少，它被分享的概率就会增加。这意味着，**随着网络中信息数量的增加，那些传播的信息的质量就会下降。**在我们的生活中，今天有越来越多的新闻和信息可供我们阅读，但我们获取到的、传播的信息质量却在下降。

事实上，我个人认为我们今天看到的所有信息，明天就会忘记50%，一周后就会忘记80%以上。这就是少就是多，而多就是少。

Tip

每加载一个类，JVM 就会为其创造一个 Class 类型的实例，并将二者关联起来。Class 实例在 JVM 中是唯一的，因此可以使用 Class 实例来判断是否为同一个类型。同时，Java 中内置的关键字 instanceof 也可以用来判断是否为同一个类型。那么通过 Class 实例和 instanceof 关键字判断有何不同呢？

• instanceof：此关键字不仅可以匹配类型，还会匹配是否为类型的子类。
• Class：通过使用 == 来判断两个类型的 Class 是否相等，只可以精确的判断数据类型，但并不能作子类型的比较。

示例代码如下：

public class Main {
    public static void main(String[] args) {
        Integer n = new Integer(123);

        boolean b11 = n instanceof Integer; // true，因为n(Integer)是Integer类型
        boolean b12 = n instanceof Number; // true，因为n(Integer)是Number类型的子类
        boolean b13 = n instanceof Double // false,因为n(Integer)和Double类型无继承关系

        boolean b3 = n.getClass() == Integer.class; // true，因为n.getClass()返回Integer.class
        boolean b4 = n.getClass() == Number.class; // false，因为Integer.class!=Number.class
    }
}

如果想要判断两个 Class 是否可以向上转型，需要通过调用 isAssignableFrom()：

// Integer 类是继承自 Number 类
public class Main {
    public static void main(String[] args) {
        Integer.class.isAssignableFrom(Integer.class); // true，因为Integer可以赋值给Integer
        Number.class.isAssignableFrom(Integer.class); // true，因为Integer是Number的子类
        Object.class.isAssignableFrom(Integer.class); // true，因为所有类都是Object的子类
        Integer.class.isAssignableFrom(Number.class); // false，因为Integer是Number的子类，无法用父类给子类赋值。
    }
}

Share

学会善用日程表。日常生活中每天都有各种事需要去处理，有些事在特定时间才会开始。过去的自己经常使用大脑去记忆接下来几天何时要做什么事，但随着年龄的增加和要处理的事情增加，自己的记忆力也没有从前好了，不时地会忘记一些事，有时候需要别人提醒才会想起。但是这样可能就会打乱了自己的时间安排，被动的被时间推着走。为了让自己能不忘记事情，最近两周在尝试使用日程表，这样就可以提前知道自己的哪些时间会被占用，以及安排事情时也不会让时间冲突，每天只需要看一眼当日的日程表后，在开始计划今天的时间，增强了自己对时间的掌控力。经过使用后，发现利用日程表还有一个好处，可以释放一部分脑容量空间，让本不富裕的脑容量可以存放更多有用的信息，至于何时要做什么，还是留给电脑手机等设备去记忆吧