By Long Luo

Leetcode 458. 可怜的小猪 题解。

这道题让我想起了一个经典面试题：1000瓶药水，其中1瓶有毒，最少要几只老鼠？ ，答案如下：

1. 给 \(1000\) 瓶药水按 \(0 \dots 999\) 编号，把十进制转为二进制，每一只老鼠喝掉对应为 \(1\) 的药水；
2. 再根据老鼠“死活”的状态确定药水的编号。

总共需要 \(10\) 只就够了， \(2^{10} = 1024 > 1000\) 。

然后受了这个思维定势，以为需要将 \(\textit{buckets}\) 瓶液体转成二进制，按照类似方法进行处理，然而却迟迟行不通，那么问题出在哪里呢？为什么这道面试题可以转成二进制进行处理？具体到这道题目却不行呢？

信息论

同样有一道面试题 N个乒乓球中有一个和其他的质量不同，用天平最少几次一定能称出来？ ，这道题本质上是考察信息论。

假设 \(n\) 个球中有一个坏球，不知道轻重，并且记坏球出现在位置 \(i\) 的概率为 \(p_i\) ，其中 \(\sum_{i=1}^np_i=1\) 。那么从信息论的角度来看，其中蕴含的平均信息量为 \(H_{total} = -\sum_{i=1}^np_i \log_2(p_i)\) 。

当 \(H_{total}\) 取到极大值时，需要满足 \(p_1 = p_2 = \dots = p_{n-1} = p_n = \frac{1}{n}\) ，此时 \(H_{total} = \log_2n\) 。

每次天平称重会产生 \(3\) 种结果，分别记为 \(p_{equal}\) ，\(p_{left}\) ，\(p_{right}\) 每次称重可以获得的平均信息量为：

\[ H_{new} = - \left ( p_{equal} \log_2(p_{equal}) + p_{left} \log_2(p_{left}) + p_{right} \log_2(p_{right}) \right ) \]

，且满足 \(p_{equal} + p_{left} + p_{right} = 1\) 。

那么可以得到 \(H_{new} \le \log_2(3)\) ，当且仅当 \(p_{equal} = p_{left} = p_{right} = \frac{1}{3}\) 时取到等号。

所以题中要求选出 \(12\) 个球中的坏球，在最坏的情况下至少需要的次数 \(T_{min} = \lceil \frac {max_{H_{total}}}{max_{H_{new}}} \rceil = \lceil \log_3(12) \rceil = 3\) 。同理，最坏情况下要分辨出坏球并且推断出坏球是轻是重至少需要的次数为 \(T_{min}' = \lceil \log_3(25) \rceil = 3\) ，因为最坏情况坏球轻或重的概率相等且为 \(\dfrac {1}{2}\) 。但是怎样才能取到这个最小值呢？

每次都选平均信息增量最大的称法。

By Long Luo

Leetcode 423. 从英文中重建数字 题解。

方法一：按照独占性依次确定每一个数字的次数

思路与算法：

最开始，看到这道题我是懵逼的，字符串怎么变成一串数字，按照什么规律，认真读了几遍，参考示例才明白啥意思。

每个数字都对应一个英文单词，\(zero, one, two, three, four, five, six, seven, eight, nine\)，统计每个英文字母在这些单词中出现的情况，发现有些字母只出现在某一个单词里，而有些字母则会出现在很多单词里。

比如 \(z\) 就只出现在 \(zero\) 里，\(g\) 只出现在 \(eight\) 里。 而 \(i\) 则同时出现在了 \(five, six, eight, nine\) 中，那么我们需要先求出乱序的字符串中每个数字包含了多少个，然后按照升序进行排列。

那么我们先对乱序字符串遍历计数，按照独占性，先把特定数字中的单词数量找出来，比如出现多少个 \(z\)，就一定有多少个 \(0\)。然后再把 \(0\) 中出现的字母去掉，逐步消元。

那么我们可以先统计每个字母的个数，然后减去对应数字的单词字母数，直至都为 \(0\)。

By Long Luo

Leetcode 859. 亲密字符串 。

方法一：模拟

思路与算法：

虽然这个题目很简单，根据题意，但需要考虑一些边界情况：

1. 如果字符串长度不一致，很明显不是亲密字符串；
2. 如果字符串长度\(len < 2\)，不是亲密字符串；
3. 如果两个字符串一摸一样，但是必须更换位置，此时合法的情况只能交换两个一样的字母，意味着有字母至少出现两次；
4. 一般情况，我们找到两个字符串字符不同的位置，但不能多于两个，同时他们可以互换。

那么针对这两种情况：

1. 字符串不相同：遍历比较两个串，记录下不同的位置，判断这两个位置是不是正好满足互换关系即可。如果有超过两个不同的位置可以直接返回false。

2. 字符串相同：遍历字符串，对每个字母计数；如果两个串没有不同的地方，必须有字母在字符串中出现不止一次。

代码如下所示：

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

public boolean buddyStrings(String s, String goal) {
    if (s == null || goal == null || s.length() <= 1 || goal.length() <= 1
            || s.length() != goal.length()) {
        return false;
    }

    int len = s.length();
    int first = -1;
    int second = -1;
    if (s.equals(goal)) {
        int[] count = new int[26];
        for (int i = 0; i < len; i++) {
            count[s.charAt(i) - 'a']++;
            if (count[s.charAt(i) - 'a'] > 1) {
                return true;
            }
        }
        return false;
    } else {
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) != goal.charAt(i)) {
                if (first == -1) {
                    first = i;
                } else if (second == -1) {
                    second = i;
                } else {
                    return false;
                }
            }
        }
    }

    if (first != second && first >= 0 && second >= 0 && s.charAt(first) == goal.charAt(second) && s.charAt(second) == goal.charAt(first)) {
        return true;
    }

    return false;
}

也可以另外一种写法：

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

bool buddyStrings(string s, string goal) {
    int lenSrc = s.length();
    int lenGoal = goal.length();
    if (lenSrc != lenGoal || lenSrc <= 1) {
        return false;
    }

    vector<char> cntSrc(26);
    vector<char> cntGoal(26);
    int diffCnt = 0;
    for (int i = 0; i < lenSrc; i++) {
        int chSrc = s.at(i) - 'a';
        int chGoal = goal.at(i) - 'a';
        cntSrc[chSrc]++;
        cntGoal[chGoal]++;
        if (chSrc != chGoal) {
            diffCnt++;
        }
    }

    bool isSame = false;
    for (int i = 0; i < 26; i++) {
        if (cntSrc[i] != cntGoal[i]) {
            return false;
        }

        if (cntSrc[i] > 1) {
            isSame = true;
        }
    }

    return diffCnt == 2 || (diffCnt == 0 && isSame);
}

复杂度分析

• 时间复杂度：\(O(N)\) ，其中 \(N\) 为字符串的长度。
• 空间复杂度：\(O(C)\) ，需要常数个空间保存字符串的字符统计次数，我们统计所有小写字母的个数，因此 \(C = 26\) 。

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

By Long Luo

Leetcode 384. 打乱数组 题解。

对于一个数组，所有的排列一共存在多少种呢？根据排列组合，对 \(n\) 个不同元素进行排列，从第 \(1\) 位开始枚举，选择 \(1~n\) 中的某一个，然后进行第 \(2\) 位的枚举，选择剩下的 \(n-1\) 个中的某一个，依次直到选取最后一个元素，很容易知道这样的排列总数为 \(n!\)。

洗牌算法的核心在于能等概率的产生所有可能的排列情况。

方法一：暴力 + 随机数

思路与算法：

看到这个题目，首先就想到的是新建一个数组 \(\textit{src}\)，用于存储原始数组，然后调用reset()时直接返回这个数组 \(\textit{src}\)。

然后，如何随机打乱一个数组呢？

新建一个数组，因为数组元素初始值都是 \(0\)，用一个变量 \(\textit{idx}\) 标记新数组索引，获取一个 \([0, \textit{len}]\) 的随机数 \(\textit{seed}\)，当判断新数组元素为 \(0\) 时，新数组 \(\textit{res[seed]}\) 等于 \(\textit{src[idx]}\)，然后 \(\textit{idx}\) 加 \(1\)。

代码如下所示：

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

class Solution {

    int len;
    int[] src;

    public Solution(int[] nums) {
        len = nums.length;
        src = new int[len];
        System.arraycopy(nums, 0, src, 0, len);
    }

    public int[] reset() {
        return src;
    }

    public int[] shuffle() {
        int[] res = new int[len];
        int seed = len - 1;
        Random random = new Random();
        int idx = 0;
        while (idx < len) {
            seed = random.nextInt(len);
            while (res[seed] == 0) {
                res[seed] = src[idx];
                idx++;
            }
        }

        return res;
    }
}

上述代码比较晦涩难懂，优化为下面的代码：

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

class Solution {
    int len;
    int[] original;
    Random random = new Random();

    public Solution(int[] nums) {
        this.len = nums.length;
        original = new int[len];
        System.arraycopy(nums, 0, original, 0, len);
    }

    public int[] reset() {
        return original;
    }

    public int[] shuffle() {
        int[] shuffled  = new int[len];
        List<Integer> numsList = new ArrayList<>();
        for (int x : original) {
            numsList.add(x);
        }

        for (int i = 0; i < len; i++) {
            int idx = random.nextInt(numsList.size());
            shuffled[i] = numsList.get(idx);
            numsList.remove(idx);
        }

        return shuffled;
    }
}

复杂度分析：

• 时间复杂度：
  • 初始化：\(O(n)\)，需要 \(O(n)\) 来初始化 \(\textit{original}\)
  • \(\texttt{reset}\)：\(O(1)\)。
  • \(\texttt{shuffle}\)：\(O(n^2)\)。需要遍历 \(n\) 个元素，每个元素需要 \(O(n-k)\) 的时间从 \(\textit{nums}\) 中移除第 \(k\) 个元素。
• 空间复杂度： \(O(n)\) ，记录初始状态和临时的乱序数组均需要存储 \(n\) 个元素。

By Long Luo

Leetcode 559. N叉树的最大深度 题解。

方法一：递归

思路与算法：

类似树的深度问题，都可以使用递归实现：

1. 确定递归的参数和返回值：参数就是传入树的根节点，返回值就是树的深度；
2. 确定终止条件：如果为空节点的话，就返回0，表示高度为0；
3. 确定单层递归的逻辑：如果是二叉树，那么先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值，最后再+1（加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

具体到N叉树，代码如下所示：

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

// Recursion time: O(n) space: O(n)
public int maxDepth(Node root) {
	if (root == null) {
		return 0;
	}

	int ans = 0;
	for (Node child : root.children) {
		ans = Math.max(ans, maxDepth(child));
	}

	return ans + 1;
}

复杂度分析

• 时间复杂度：\(O(n)\)，其中\(n\)为\(N\)叉树节点的个数。每个节点在递归中只被遍历一次。
• 空间复杂度：\(O(\textit{height})\)，其中\(\textit{height}\)表示\(N\)叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于\(N\)叉树的高度。

方法二：DFS迭代

二叉树的遍历，其实也是DFS的一种方式，我们可以参考二叉树的遍历，使用迭代的方式进行遍历，最后更新\(N\)叉树的最大深度。

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

// DFS time: O(n) space: O(n)
class Pair {
	Node node;
	int depth;

	Pair(Node node, int depth) {
		this.node = node;
		this.depth = depth;
	}
}

public int maxDepth_dfs(Node root) {
	if (root == null) {
		return 0;
	}

	int ans = 0;
	Stack<Pair> stack = new Stack<>();
	stack.push(new Pair(root, 1));
	while (!stack.empty()) {
		Pair top = stack.pop();
		Node node = top.node;
		int depth = top.depth;
		for (Node childNode : node.children) {
			stack.push(new Pair(childNode, depth + 1));
		}

		ans = Math.max(ans, depth);
	}

	return ans;
}

复杂度分析

• 时间复杂度：\(O(n)\)，其中\(n\)为\(N\)叉树节点的个数。
• 空间复杂度：\(O(n)\)，每个节点都需要入栈出栈一次。