By Long Luo

Leetcode 172. 阶乘后的零 题解：

方法一：用大数暴力求解并计算末尾0的数量

因为 \(n!\) 得到的数字会非常大，所以需要使用BigInteger，得到结果之后，再计算末尾 \(0\) 的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import java.math.BigInteger;

class Solution {
    public int trailingZeroes(int n) {
        BigInteger nFactorResult = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            nFactorResult = nFactorResult.multiply(BigInteger.valueOf(i));
        }

        int ans = 0;
        while (nFactorResult.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
            ans++;
            nFactorResult = nFactorResult.divide(BigInteger.TEN);
        }

        return ans;        
    }
}

复杂度分析

• 时间复杂度：\(O(n)\), 实际上应该是 \(O(n + \log n)\)，但 \(\log n\) 很快，只有 \(O(1)\)，所以 \(O(n)\) 。
• 空间复杂度：\(O(1)\)。

方法二：计算1到n中全部5因子数量

思路与算法：

考虑到计算阶乘末尾的每个 \(0\) 表示乘以 \(10\)，那么在我们在计算 \(n!\) 时乘以 \(10\) 的次数是多少？ 考虑到两个数字 \(a\) 和 \(b\) 相乘，例如，要执行 \(15 \times 24 = 360\)，我们可以将其分解为：

\[ 15 \times 24 = 3 \times 5 \times 2 \times 2 \times 2 \times 3 = 360 \]

从上面可以得出，我们只需要考虑 \(2 \times 5\) 的因子有多少对。同时，因为 \(2\) 的因子数比 \(5\) 的因子数要多，所以我们只需要计算 \(1\) 到 \(n\) 的 \(5\) 的因子数有多少即可。

By Long Luo

Leetcode 2. 两数相加 题解。

方法一：模拟链表操作

思路与算法：

最开始我的思路是将 \(2\) 个数字都读出来，然后相加，再逆向写入回去，但是发现链表数字太长，这个方法不可行。

由于两个链表长度不一致，还需要考虑不同位数对齐的问题，但是由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

那么只需要同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 \(n_1\) ，\(n_2\) ，进位值为 \(\textit{carry}\) ，则它们的和为 \(n_1 + n_2 + \textit{carry}\) 。

其中，答案链表处相应位置的数字为 \((n_1 + n_2 + \textit{carry}) mod 10\) ，而新的进位值为 \(\textit{sum} - 10\) 。

需要注意的是：如果链表遍历结束后，有 \(\textit{carry} \gt 0\) ，还需要在答案链表的后面附加一个节点，节点的值为 \(\textit{carry}\) 。

于是就有了那么的第一版代码：

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

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode pNode1 = l1;
	ListNode pNode2 = l2;
	ListNode dummyNode = new ListNode(-1);
	ListNode pNode = dummyNode;
	int carry = 0;
	while (pNode1 != null && pNode2 != null) {
		int sum = pNode1.val + pNode2.val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}
		ListNode node = new ListNode(sum);
		pNode.next = node;
		pNode = pNode.next;

		pNode1 = pNode1.next;
		pNode2 = pNode2.next;
	}

	while (pNode1 != null) {
		int sum = pNode1.val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}
		ListNode node = new ListNode(sum);
		pNode.next = node;
		pNode = pNode.next;

		pNode1 = pNode1.next;
	}

	while (pNode2 != null) {
		int sum = pNode2.val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}
		ListNode node = new ListNode(sum);
		pNode.next = node;
		pNode = pNode.next;
		pNode2 = pNode2.next;
	}

	if (carry > 0) {
		ListNode node = new ListNode(carry);
		pNode.next = node;
	}

	return dummyNode.next;
}

实际上，上述代码可以优化，去掉多余的变量。如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 \(0\) ，得到了下面的优化代码：

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

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode dummyNode = new ListNode(-1);
	ListNode pNode = dummyNode;
	int carry = 0;
	while (l1 != null || l2 != null) {
		int num1 = l1 != null ? l1.val : 0;
		int num2 = l2 != null ? l2.val : 0;
		int sum = num1 + num2 + carry;
		carry = sum / 10;
		pNode.next = new ListNode(sum % 10);
		pNode = pNode.next;

		if (l1 != null) {
			l1 = l1.next;
		}

		if (l2 != null) {
			l2 = l2.next;
		}
	}

	if (carry > 0) {
		pNode.next = new ListNode(carry);
	}

	return dummyNode.next;
}

复杂度分析

• 时间复杂度：\(O(\max(m,n))\) ，其中 \(m\) 和 \(n\) 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 \(O(1)\) 的时间。
• 空间复杂度：\(O(1)\) 。

By Long Luo

1. 两数之和 题解。

方法一：暴力枚举

思路及算法：

最容易想到的方法是使用两层循环，第一层循环枚举数组中的每一个数 \(x\)，下一层循环在 \(x\) 之后的元素中寻找数组中是否存在 \(\textit{target} - x\)。

1
2
3
4
5
6
7
8
9
10
11
12

    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

复杂度分析

• 时间复杂度：\(O(N^2)\) ，其中 \(N\) 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
• 空间复杂度：\(O(1)\) 。

1. 褚老师经历过人生最低谷吗？你信命信风水吗？

褚老师经历过人生最低谷吗？你信命信风水吗？未来哪些行业有赚钱机会？

一

我是一个挺迷信的人。

比如我一直坚信好事一旦说出来肯定会泡汤。写了一篇感觉很好的论文，投出去千万别到处说，尤其是不能说「感觉不错，这篇估计要中」之类的话——说要中肯定中不了，不管你理论多牛逼实验多周到结果多惊人文笔多流畅，一定会在你意想不到的地方出漏子。

比如你认识了一个美女，感觉特好约她周末出来吃晚饭，而且她居然答应了。你千万别一高兴就跟同宿舍的哥们儿汇报战果，一旦说了，你瞧着吧，就在礼拜六约好的时间前你一定会收到美女的微信，说哎呀抱歉我有事来不了了咱们以后再约吧。

比如我一直有一个强迫症，在街上走路碰到井盖一定要从井盖上踩过去，有时候就算井盖在马路的中间而马路上有车，我还是会忍不住冒险去踩那个井盖，最糟糕的是如果路上连着有好几个井盖而且位置还忽左忽右，在旁观者眼里我一定看起来像个疯子。

忘了一个细节，我不仅要踩到井盖，而且必须是踩井盖的左半边。如果不是这样，我会觉得很不吉利。

我类似的迷信还有好多，比如做一件重要的大事之前不能理发，比如不能拿自己珍惜的人或东西的名字当密码，比如……

作为一个学物理的「科学工作者」，我当然知道这些绝不是什么理性的举动，当然，更毫无科学依据可言，用你的话说，我的各种迷信纯属——脑残。

可是，我还是不敢把好事提前说出来，我还是会忍不住去踩井盖。

我想说的是，我不信风水，可是我很能理解那些信风水的朋友，以及风水能够给人带来的安慰——生活中不确定的东西太多，而每个人又都渴望得到确定的答案，希望自己能为改变不能改变的命运做点儿什么，如果能踩井盖给自己带来点儿好运气，如果把卧室里的床换个位置就会事业上升走桃花运之类的，我想谁都会有难以拒绝的时候吧。

而且，比起踩井盖来说，风水也许还更靠谱一点。

二

先告诉你一个坏消息吧，你没法说服一个信风水的人。

单从这一点上看，风水这东西很像中医，一个人一旦信了中医，不管你怎么摆事实、讲道理或者采取什么冷招数想说服他都基本没戏。

但是，我想说的是：风水跟中医太不一样了！

鲁迅老师说过：「中医不过是一些有意无意的骗子。」风水师不是什么「有意无意」的骗子，这帮人无一例外都是有意的骗子。

在现代医学出现之前，一个中国人要是生病了，你只有一个选择——看中医。说句公道话，虽然中医癌症心脏病肝炎肺炎还有各种传染病什么的大病小病都治不了，但是你得了感冒让你退个烧出个汗还是可以做到的，所以不能说完全没用。我相信古时候的中医很多还是真心想给病人治病的，问题不是缺德，而是无知。

现代的中医则是另外一回事。前一段一个傻逼中医假装提问想跟我叫板，我写了一篇长文讲解了中医的问题，有空你看看吧，我就不在这儿重复了。

简单说吧，现代的中医都缺德。

中医属于那种过去有过用，后来被更有用的替代了的东西。而风水则不同，风水属于那种以前就没用，现在也没用，以后也不会有用的彻头彻尾的骗局。

风水师都是骗子，但是——他们没中医那么缺德。

因为风水不杀人。

风水造成的损失顶多像你问题里说的，买坟地的时候花点儿冤枉钱之类的，除了让一些弱智自愿破财以外对当事人基本无害，作为一种智商罚款，我觉得对社会总的来说还有好处。

从更深一层看，风水师提供的其实是一种有极大市场需求的服务。你说风水师是卖什么的？卖「风水」的？错！

风水师是卖「希望」的。

你想职场得意、生意发达、家庭幸福、孩子上名校，哪件事不都是需要费了大劲才能实现的？现在有人跟你说，有一个简单的解决方案——你只需要把家里的家具重新摆一摆就万事大吉了——这得多有吸引力啊！要是真有这样的好事，我也会马上掏腰包。

从这个角度来看，风水师跟网上那些卖「财富自由、年薪百万」秘籍的所谓「知识付费」骗子其实没什么差别，套路都是说只要你花点儿钱，就能迎来人生转折，梦想成真。

再往深一层看，风水师其实比卖「财富自由」的还要高明一些，那些成功秘籍骗了你的钱之后还是让你自己去努力去瞎费劲。但是你知道吗，决定成功的最大因素是机遇——是那些偶然的、不受你控制的东西。

我想其实每个人心里都隐隐地感到了这一点，所以才会去为风水、烧香这样的虚幻的东西付费。像你说的，越是成功的明星、商人就越容易信风水，因为这类人最清楚，自己的成功来得莫名其妙。

风水存在的根本原因，就是成功主要靠运气这个真理。牛逼！

中医骗了你的钱把你害死，卖财富自由的骗了你的钱让你瞎忙，只有风水师，骗了你的钱就基本没事儿了。

还是风水好哇！

By Long Luo

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，算法复杂度为：O(log2n)。但是，折半查找要求线性表必须采用顺序存储结构 ，而且表中元素按关键字有序排列。

1. 必须采用顺序存储结构；
2. 必须按关键字大小有序排列。

二分查找充分利用了元素间的次序关系，采用分治策略。算法的基本思想是(假设数组arr呈升序排列)：

1. 将n个元素分成个数大致相同的两半；
2. 取arr[n/2]与欲查找的x作比较，如果x = arr[n/2]则找到x，算法终止；
3. 如果x < arr[n/2]，则只要在数组arr的左半部继续搜索x；如果x > arr[n/2]，则我们只要在数组a的右半部继续搜索x。

二分查找常见有2种实现方式，迭代和递归，下面我们来实现这2种方式：

迭代

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * Returns the index of the specified target in the specified array.
 *
 * @param arr    the array of integers, must be sorted in ascending order
 * @param target the search target
 * @return index of key in array {@code arr} if present; {@code -1} otherwise
 */
public static int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else if (arr[mid] > target) {
            high = mid - 1;
        }
    }

    return -1;
}