By Long Luo

This article is the solution 2 Approaches: Brute Force and Binary Exponentiation of Problem 372. Super Pow .

Intuition

This problem is to find a integer raised to the power a very large number whose length may be \(200\) or more.

Brute Froce

We multiply \(a\) to itself \(b\) times. That is, \(a^b = \underbrace{a \times a \dots \times a}_b\) .

We can write such code easily.

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

public static int superPow(int a, int[] b) {
    if (a == 1) {
        return 1;
    }

    int ans = a;
    int len = b.length;
    for (int i = len - 1; i >= 0; i--) {
        int base = (int) Math.pow(10, len - 1 - i);
        int num = b[i] * base;
        for (int j = 1; j < num; j++) {
            ans = ((ans % 1337) * (a % 1337)) % 1337;
        }
    }

    return ans;
}

Analysis

• Time Complexity: \(O(10^mb_i)\) , \(m\) is the length of array b.
• Space Complexity: \(O(1)\)

Obiviously, it will exceed time limit, so we have to find a more efficiently algorithm.

By Long Luo

Leetcode 438. 找到字符串中所有字母异位词 题目如下：

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

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

	示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

	示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 

提示:
1 <= s.length, p.length <= 3 * 10^4
s 和 p 仅包含小写字母

看到这道题，首先想到方法就是：

1. 统计字符串 \(\textit{p}\) 字母及其数量；
2. 使用双指针 + 滑动窗口，如果当前窗口的不同字母种类及其数量和字符串 \(\textit{p}\) 字符串一致，将当前下标增加为答案；
3. 扫描到字符串 \(\textit{s}\) 结束。

方法一：HashMap + 滑动窗口

思路与算法：

使用 \(\texttt{HashMap}\) 存储字符串 \(\textit{p}\) 的不同字母种类及其数量。

在字符串 \(\textit{s}\) 中构造一个长度为与字符串 \(\textit{p}\) 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 \(\textit{p}\) 中每种字母的数量相同时，则说明当前窗口为字符串 \(\textit{p}\) 的异位词。

代码如下所示：

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

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ans = new ArrayList<>();
    int pLen = p.length();
    int sLen = s.length();
    if (pLen > sLen) {
        return ans;
    }

    Map<Character, Integer> patMap = new HashMap<>();
    for (char ch : p.toCharArray()) {
        patMap.put(ch, patMap.getOrDefault(ch, 0) + 1);
    }

    int left = 0;
    int right = left + pLen;

    // Sliding Window
    Map<Character, Integer> winMap = new HashMap<>();
    for (int i = left; i < right; i++) {
        char ch = s.charAt(i);
        winMap.put(ch, winMap.getOrDefault(ch, 0) + 1);
    }

    if (patMap.equals(winMap)) {
        ans.add(left);
    }

    while (right < sLen) {
        char chLeft = s.charAt(left);
        winMap.put(chLeft, winMap.get(chLeft) - 1);
        if (winMap.get(chLeft) == 0) {
            winMap.remove(chLeft);
        }

        char chRight = s.charAt(right);
        winMap.put(chRight, winMap.getOrDefault(chRight, 0) + 1);

        left++;
        right++;
        if (patMap.equals(winMap)) {
            ans.add(left);
        }
    }

    return ans;  
}

复杂度分析：

• 时间复杂度：\(O(m+(n-m) \times \Sigma)\)，其中 \(n\) 为字符串 \(\textit{s}\) 的长度，\(m\) 为字符串 \(\textit{p}\) 的长度，\(\Sigma\) 为所有可能的字符数。需要 \(O(m)\) 来统计字符串 \(\textit{p}\) 中每种字母的数量；需要 \(O(m)\) 来初始化滑动窗口；需要判断 \(n-m+1\) 个滑动窗口中每种字母的数量是否与字符串 \(\textit{p}\) 中每种字母的数量相同，每次判断需要 \(O(\Sigma)\)。因为 \(\textit{s}\) 和 \(\textit{p}\) 仅包含小写字母，所以 \(\Sigma=26=26\)。

• 空间复杂度：\(O(\Sigma)\)。用于存储字符串 \(\textit{p}\) 和滑动窗口中每种字母的数量。

By Long Luo

Leetcode 519. 随机翻转矩阵 题目如下：

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

519. 随机翻转矩阵

给你一个m x n的二元矩阵matrix，且所有值被初始化为0。请你设计一个算法，随机选取一个满足matrix[i][j] == 0 的下标(i, j)，并将它的值变为1。所有满足matrix[i][j] == 0的下标(i,j)被选取的概率应当均等。

尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

实现Solution类：
Solution(int m, int n)使用二元矩阵的大小m和n初始化该对象
int[] flip() 返回一个满足matrix[i][j] == 0的随机下标[i, j]，并将其对应格子中的值变为1
void reset() 将矩阵中所有的值重置为 0
 
示例：
输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip();  // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip();  // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip();  // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0 ，并可以再次选择下标返回
solution.flip();  // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
 
提示：
1 <= m, n <= 10^4
每次调用flip 时，矩阵中至少存在一个值为0的格子。
最多调用1000次flip和reset方法。

这道题和 384. 打乱数组 类似，考察的都是随机数的有用，下面我们用暴力法和哈希表 \(2\) 种方法来解决这个问题。

方法一：暴力 + 随机数

思路与算法：

首先就想到的是新建一个矩阵 \(\textit{matrix}\)，调用 \(\texttt{reset()}\) 时重置 \(\textit{matrix}\)。

但是调用 \(\texttt{flip()}\) 呢？

1. 生成一个 \(0\) 到 \(\textit{total}\) 的随机数 \(\textit{seed}\)；
2. 如果当前数组元素值为 \(1\)，说明已经被调用过，需要重新生成一个随机数，返回上一步；
3. 如果当前数组元素值为 \(0\)，对其置 \(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
32

class Solution {
    int[][] matrix;
    int row;
    int col;
    int total;
    Random random = new Random();

    public Solution(int m, int n) {
        matrix = new int[m][n];
        row = m;
        col = n;
        total = row * col;
    }

    public int[] flip() {
        int rand = random.nextInt(total);
        while (matrix[rand / col][rand % col] == 1) {
            rand = random.nextInt(total);
        }

        matrix[rand / col][rand % col] = 1;
        return new int[]{rand / col, rand % col};
    }

    public void reset() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                matrix[i][j] = 0;
            }
        }
    }
}

复杂度分析：

• 时间复杂度：
  • \(\texttt{flip}\)：\(O(mn)\)。
  • \(\texttt{reset}\)：\(O(mn)\)。
• 空间复杂度：\(O(mn)\)，需要 \(mn\) 的空间来存储矩阵。

By Long Luo

Leetcode 700. 二叉搜索树中的搜索 题目如下：

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

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。 如果节点不存在，则返回NULL。

例如，
给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和值: 2
你应该返回如下子树:

      2     
     / \   
    1   3
在上述示例中，如果要找的值是5，但因为没有节点值为5，我们应该返回NULL。

方法一：递归

思路与算法

首先想到的是递归，因为二叉搜索树的特点：

• 左子树所有节点的元素值均小于根的元素值；
• 右子树所有节点的元素值均大于根的元素值。

如果树为NULL或者节点值等于目标值，返回此节点。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11

public TreeNode searchBST(TreeNode root, int val) {
	if (root == null || root.val == val) {
		return root;
	}

	if (val < root.val) {
		return searchBST(root.left, val);
	} else {
		return searchBST(root.right, val);
	}
}

复杂度分析：

• 时间复杂度：\(O(N)\) ，其中 \(N\) 为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要递归\(N\)次。

• 空间复杂度：\(O(N)\) ，递归需要 \(N\) 个函数栈，最坏情况下递归需要 \(O(N)\) 的栈空间。

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}\) 。但是怎样才能取到这个最小值呢？

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