Android面试题整理4 (算法）
算法高频面试题
1.什么是素数
素数的定义看起来很简单，如果⼀个数如果只能被 1 和它本⾝整除，那么这个数就是素数。
不要觉得素数的定义简单，恐怕没多少⼈真的能把素数相关的算法写得⾼效。⽐如让你写这样⼀个函数：
// 返回区间 [2, n) 中有⼏个素数
int countPrimes(int n)
/
/ ⽐如 countPrimes(10) 返回 4
/ 因为 2,3,5,7 是素数
/
你会如何写这个函数？我想⼤家应该会这样写：
int countPrimes(int n) {
int count = 0;
for (int i = 2; i < n; i++)
if (isPrim(i)) count++;
return count;
}
// 判断整数 n 是否是素数
boolean isPrime(int n) {
for (int i = 2; i < n; i++)
if (n % i == 0)
// 有其他整除因⼦
return false;
return true;
}这样写的话时间复杂度 O(n^2)，问题很⼤。⾸先你⽤ isPrime 函数来辅助的思路就不够⾼效；⽽且就算你要⽤ isPrime 函数，这样写算法也是存在计算冗余的。
2. 如何⾼效寻找素数
先来简单说下如果你要判断⼀个数是不是素数，应该如何写算法。只需稍微修改⼀下上⾯的 isPrim 代码中的 for 循环条件：
boolean isPrime(int n) {
for (int i = 2; i * i <= n; i++)
...
}换句话说， i 不需要遍历到 n ，⽽只需要到 sqrt(n) 即可。为什么呢，我们举个例⼦，假设 n = 12.
12 = 2 × 6
12 = 3 × 4
12 = sqrt(12) × sqrt(12)
12 = 4 × 3
12 = 6 × 2
可以看到，后两个乘积就是前⾯两个反过来，反转临界点就在 sqrt(n) 。
换句话说，如果在 [2,sqrt(n)] 这个区间之内没有发现可整除因⼦，就可以直接断定 n 是素数了，因为在区间 [sqrt(n),n] 也⼀定不会发现可整除因⼦。
现在， isPrime 函数的时间复杂度降为 O(sqrt(N))，但是我们实现countPrimes 函数其实并不需要这个函数，以上只是希望读者明⽩sqrt(n) 的含义，因为等会还会⽤到。
⾼效实现 countPrimes
⾼效解决这个问题的核⼼思路是和上⾯的常规思路反着来：
⾸先从 2 开始，我们知道 2 是⼀个素数，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8…
都不可能是素数了。
然后我们发现 3 也是素数，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12… 也都不可能
是素数了。
如何⾼效寻找素数
看到这⾥，你是否有点明⽩这个排除法的逻辑了呢？先看我们的第⼀版代码：
int countPrimes(int n) {
boolean[] isPrim = new boolean[n];
// 将数组都初始化为 true
Arrays.fill(isPrim, true);
for (int i = 2; i < n; i++)
if (isPrim[i])
// i 的倍数不可能是素数了
for (int j = 2 * i; j < n; j += i)
isPrim[j] = false;
int count = 0;
for (int i = 2; i < n; i++)
if (isPrim[i]) count++;
return count;
}如果上⾯这段代码你能够理解，那么你已经掌握了整体思路，但是还有两个细微的地⽅可以优化。
⾸先，回想刚才判断⼀个数是否是素数的 isPrime 函数，由于因⼦的对称性，其中的 for 循环只需要遍历 [2,sqrt(n)] 就够了。这⾥也是类似的，我们外层的 for 循环也只需要遍历到 sqrt(n) ：
for (int i = 2; i * i < n; i++)
if (isPrim[i])
...除此之外，很难注意到内层的 for 循环也可以优化。我们之前的做法是：
for (int j = 2 * i; j < n; j += i)
isPrim[j] = false;如何⾼效寻找素数
这样可以把 i 的整数倍都标记为 false ，但是仍然存在计算冗余。
如 n = 25 ， i = 4 时算法会标记 4 × 2 = 8，4 × 3 = 12 等等数字，但是
⽐这两个数字已经被 i = 2 和 i = 3 的 2 × 4 和 3 × 4 标记了。
我们可以稍微优化⼀下，让 j 从 i 的平⽅开始遍历，⽽不是从 2 * i
开始：
for (int j = i * i; j < n; j += i)
isPrim[j] = false;这样，素数计数的算法就⾼效实现了，其实这个算法有⼀个名字，叫做Sieve of Eratosthenes。看下完整的最终代码：
int countPrimes(int n) {
boolean[] isPrim = new boolean[n];
Arrays.fill(isPrim, true);
for (int i = 2; i * i < n; i++)
if (isPrim[i])
for (int j = i * i; j < n; j += i)
isPrim[j] = false;
int count = 0;
for (int i = 2; i < n; i++)
if (isPrim[i]) count++;
return count;
}该算法的时间复杂度⽐较难算，显然时间跟这两个嵌套的 for 循环有关，其操作数应该是：
n/2 + n/3 + n/5 + n/7 + … = n × (1/2 + 1/3 + 1/5 + 1/7…)
括号中是素数的倒数。其最终结果是 O(N * loglogN)，有兴趣的读者可以查⼀下该算法的时间复杂度证明。
以上就是素数算法相关的全部内容。怎么样，是不是看似简单的问题却有不少细节可以打磨呀？
3.如何运⽤⼆分查找算法
⼆分查找到底有能运⽤在哪⾥？
最常⻅的就是教科书上的例⼦，在有序数组中搜索给定的某个⽬标值的索引。再推⼴⼀点，如果⽬标值存在重复，修改版的⼆分查找可以返回⽬标值的左侧边界索引或者右侧边界索引。
PS：以上提到的三种⼆分查找算法形式在前⽂「⼆分查找详解」有代码详解，如果没看过强烈建议看看。
抛开有序数组这个枯燥的数据结构，⼆分查找如何运⽤到实际的算法问题中呢？当搜索空间有序的时候，就可以通过⼆分搜索「剪枝」，⼤幅提升效率。
说起来⽞乎得很，本⽂先⽤⼀个具体的「Koko 吃⾹蕉」的问题来举个例⼦。
⼀、问题分析
也就是说，Koko 每⼩时最多吃⼀堆⾹蕉，如果吃不下的话留到下⼀⼩时再吃；如果吃完了这⼀堆还有胃⼝，也只会等到下⼀⼩时才会吃下⼀堆。在这个条件下，让我们确定 Koko 吃⾹蕉的最⼩速度（根/⼩时）。
如果直接给你这个情景，你能想到哪⾥能⽤到⼆分查找算法吗？如果没有⻅过类似的问题，恐怕是很难把这个问题和⼆分查找联系起来的。
那么我们先抛开⼆分查找技巧，想想如何暴⼒解决这个问题呢？⾸先，算法要求的是「H ⼩时内吃完⾹蕉的最⼩速度」，我们不妨称为speed ，请问 speed 最⼤可能为多少，最少可能为多少呢？
显然最少为 1，最⼤为 max(piles) ，因为⼀⼩时最多只能吃⼀堆⾹蕉。那么暴⼒解法就很简单了，只要从 1 开始穷举到 max(piles) ，⼀旦发现发现某个值可以在 H ⼩时内吃完所有⾹蕉，这个值就是最⼩速度：
如何运⽤⼆分查找算法
int minEatingSpeed(int[] piles, int H) {
// piles 数组的最⼤值
int max = getMax(piles);
for (int speed = 1; speed < max; speed++) {
// 以 speed 是否能在 H ⼩时内吃完⾹蕉
if (canFinish(piles, speed, H))
return speed;
}
return max;
}注意这个 for 循环，就是在连续的空间线性搜索，这就是⼆分查找可以发挥作⽤的标志。由于我们要求的是最⼩速度，所以可以⽤⼀个搜索左侧边界的⼆分查找来代替线性搜索，提升效率：
int minEatingSpeed(int[] piles, int H) {
// 套⽤搜索左侧边界的算法框架
int left = 1, right = getMax(piles) + 1;
while (left < right) {
// 防⽌溢出
int mid = left + (right - left) / 2;
if (canFinish(piles, mid, H)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}PS：如果对于这个⼆分查找算法的细节问题有疑问，建议看下前⽂「⼆分查找详解」搜索左侧边界的算法模板，这⾥不展开了。剩下的辅助函数也很简单，可以⼀步步拆解实现：
// 时间复杂度 O(N)
boolean canFinish(int[] piles, int speed, int H) {
int time = 0;
for (int n : piles) {
time += timeOf(n, speed);
}
return time <= H;
}
int timeOf(int n, int speed) {
return (n / speed) + ((n % speed > 0) ? 1 : 0);
}
int getMax(int[] piles) {
int max = 0;
for (int n : piles)
max = Math.max(n, max);
return max;
}⾄此，借助⼆分查找技巧，算法的时间复杂度为 O(NlogN)。
⼆、扩展延伸
类似的，再看⼀道运输问题：
要在 D 天内运输完所有货物，货物不可分割，如何确定运输的最⼩载重呢（下⽂称为 cap ）？
其实本质上和 Koko 吃⾹蕉的问题⼀样的，⾸先确定 cap 的最⼩值和最⼤值分别为 max(weights) 和 sum(weights) 。
我们要求最⼩载重，所以可以⽤搜索左侧边界的⼆分查找算法优化线性搜索：
// 寻找左侧边界的⼆分查找
int shipWithinDays(int[] weights, int D) {
// 载重可能的最⼩值
int left = getMax(weights);
// 载重可能的最⼤值 + 1
int right = getSum(weights) + 1;
while (left < right) {}4.如何⾼效解决接⾬⽔问题
接⾬⽔问题详解
接⾬⽔这道题⽬挺有意思，在⾯试题中出现频率还挺⾼的，本⽂就来步步优化，讲解⼀下这道题。
先看⼀下题⽬：
就是⽤⼀个数组表⽰⼀个条形图，问你这个条形图最多能接多少⽔。
int trap(int[] height);下⾯就来由浅⼊深介绍暴⼒解法 -> 备忘录解法 -> 双指针解法，在 O(N) 时间 O(1) 空间内解决这个问题。
如何⾼效解决接⾬⽔问题
⼀、核⼼思路
我第⼀次看到这个问题，⽆计可施，完全没有思路，相信很多朋友跟我⼀样。所以对于这种问题，我们不要想整体，⽽应该去想局部；就像之前的⽂章处理字符串问题，不要考虑如何处理整个字符串，⽽是去思考应该如何处理每⼀个字符。
这么⼀想，可以发现这道题的思路其实很简单。具体来说，仅仅对于位置i，能装下多少⽔呢？
能装 2 格⽔。为什么恰好是两格⽔呢？因为 height[i] 的⾼度为 0，⽽这⾥最多能盛 2 格⽔，2-0=2。
为什么位置 i 最多能盛 2 格⽔呢？因为，位置 i 能达到的⽔柱⾼度和其左边的最⾼柱⼦、右边的最⾼柱⼦有关，我们分别称这两个柱⼦⾼度为 l_max和 r_max ；位置 i 最⼤的⽔柱⾼度就是 min(l_max, r_max) 。更进⼀步，对于位置 i，能够装的⽔为：
water[i] = min(左边最⾼的柱⼦max(height[0..i]),右边最⾼的柱⼦max(height[i..end])-height[i])这就是本问题的核⼼思路，我们可以简单写⼀个暴⼒算法：
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
for (int i = 1; i < n - 1; i++) {
int l_max = 0, r_max = 0;
// 找右边最⾼的柱⼦
for (int j = i; j < n; j++)
r_max = max(r_max, height[j]);
// 找左边最⾼的柱⼦
for (int j = i; j >= 0; j--)
l_max = max(l_max, height[j]);
// 如果⾃⼰就是最⾼的话，
// l_max == r_max == height[i]
ans += min(l_max, r_max) - height[i];
}
return ans;
}有之前的思路，这个解法应该是很直接粗暴的，时间复杂度 O(N^2)，空间复杂度 O(1)。但是很明显这种计算 r_max 和 l_max 的⽅式⾮常笨拙，⼀般的优化⽅法就是备忘录。
⼆、备忘录优化
之前的暴⼒解法，不是在每个位置 i 都要计算 r_max 和 l_max 吗？我们直接把结果都缓存下来，别傻不拉⼏的每次都遍历，这时间复杂度不就降下来了嘛。
我们开两个数组 r_max 和 l_max 充当备忘录， l_max[i] 表⽰位置 i 左边最⾼的柱⼦⾼度， r_max[i] 表⽰位置 i 右边最⾼的柱⼦⾼度。预先把这两个数组计算好，避免重复计算：
int trap(vector<int>& height) {
if (height.empty()) return 0;
int n = height.size();
int ans = 0;
// 数组充当备忘录
vector<int> l_max(n), r_max(n);
// 初始化 base case
l_max[0] = height[0];
r_max[n - 1] = height[n - 1];
// 从左向右计算 l_max
for (int i = 1; i < n; i++)
l_max[i] = max(height[i], l_max[i - 1]);
// 从右向左计算 r_max
for (int i = n - 2; i >= 0; i--)
r_max[i] = max(height[i], r_max[i + 1]);
// 计算答案
for (int i = 1; i < n - 1; i++)
ans += min(l_max[i], r_max[i]) - height[i];
return ans;
}这个优化其实和暴⼒解法差不多，就是避免了重复计算，把时间复杂度降低为 O(N)，已经是最优了，但是空间复杂度是 O(N)。下⾯来看⼀个精妙⼀些的解法，能够把空间复杂度降低到 O(1)。
三、双指针解法
这种解法的思路是完全相同的，但在实现⼿法上⾮常巧妙，我们这次也不要⽤备忘录提前计算了，⽽是⽤双指针边⾛边算，节省下空间复杂度。
⾸先，看⼀部分代码：
int trap(vector<int>& height) {
int n = height.size();
int left = 0, right = n - 1;
int l_max = height[0];
int r_max = height[n - 1];
while (left <= right) {
l_max = max(l_max, height[left]);
r_max = max(r_max, height[right]);
left++; right--;
}
}对于这部分代码，请问 l_max 和 r_max 分别表⽰什么意义呢？很容易理解， l_max 是 height[0…left] 中最⾼柱⼦的⾼度， r_max 是height[right…end] 的最⾼柱⼦的⾼度。
明⽩了这⼀点，直接看解法：
int trap(vector<int>& height) {
if (height.empty()) return 0;
int n = height.size();
int left = 0, right = n - 1;
int ans = 0;
int l_max = height[0];
int r_max = height[n - 1];
while (left <= right) {
l_max = max(l_max, height[left]);
r_max = max(r_max, height[right]);
// ans += min(l_max, r_max) - height[i]
if (l_max < r_max) {
ans += l_max - height[left];
left++;
}else {
ans += r_max - height[right];
right--;
}
}
return ans;
}你看，其中的核⼼思想和之前⼀模⼀样，换汤不换药。但是细⼼的读者可能会发现次解法还是有点细节差异：
之前的备忘录解法， l_max[i] 和 r_max[i] 代表的是 height[0…i] 和height[i…end] 的最⾼柱⼦⾼度。
ans += min(l_max[i], r_max[i]) - height[i];
但是双指针解法中， l_max 和 r_max 代表的是 height[0…left] 和height[right…end] 的最⾼柱⼦⾼度。⽐如这段代码：
if (l_max < r_max) {
ans += l_max - height[left];
left++;
}此时的 l_max 是 left 指针左边的最⾼柱⼦，但是 r_max 并不⼀定是left 指针右边最⾼的柱⼦，这真的可以得到正确答案吗？
其实这个问题要这么思考，我们只在乎 min(l_max, r_max) 。对于上图的情况，我们已经知道 l_max < r_max 了，⾄于这个 r_max 是不是右边最⼤的，不重要，重要的是 height[i] 能够装的⽔只和 l_max 有关。
5.如何去除有序数组的重复元素
我们知道对于数组来说，在尾部插⼊、删除元素是⽐较⾼效的，时间复杂度是 O(1)，但是如果在中间或者开头插⼊、删除元素，就会涉及数据的搬移，时间复杂度为 O(N)，效率较低。
所以对于⼀般处理数组的算法问题，我们要尽可能只对数组尾部的元素进⾏
操作，以避免额外的时间复杂度。
这篇⽂章讲讲如何对⼀个有序数组去重，先看下题⽬：
显然，由于数组已经排序，所以重复的元素⼀定连在⼀起，找出它们并不难，但如果毎找到⼀个重复元素就⽴即删除它，就是在数组中间进⾏删除操作，整个时间复杂度是会达到 O(N^2)。⽽且题⽬要求我们原地修改，也就是说不能⽤辅助数组，空间复杂度得是 O(1)。
其实，对于数组相关的算法问题，有⼀个通⽤的技巧：要尽量避免在中间删除元素，那我就想先办法把这个元素换到最后去。这样的话，最终待删除的元素都拖在数组尾部，⼀个⼀个 pop 掉就⾏了，每次操作的时间复杂度也就降低到 O(1) 了。
按照这个思路呢，⼜可以衍⽣出解决类似需求的通⽤⽅式：双指针技巧。具体⼀点说，应该是快慢指针。
我们让慢指针 slow ⾛左后⾯，快指针 fast ⾛在前⾯探路，找到⼀个不重复的元素就告诉 slow 并让 slow 前进⼀步。这样当 fast 指针遍历完整个数组 nums 后， nums[0…slow] 就是不重复元素，之后的所有元素都是重复元素。
int removeDuplicates(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int slow = 0, fast = 1;
while (fast < n) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] ⽆重复
nums[slow] = nums[fast];
}
fast++;
}
// ⻓度为索引 + 1
return slow + 1;
}再简单扩展⼀下，如果给你⼀个有序链表，如何去重呢？其实和数组是⼀模样的，唯⼀的区别是把数组赋值操作变成操作指针⽽已：
ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head.next;
while (fast != null) {
if (fast.val != slow.val) {
/
/ nums[slow] = nums[fast];
slow.next = fast;
/ slow++;
/
slow = slow.next;
}
// fast++
fast = fast.next;
}
// 断开与后⾯重复元素的连接
slow.next = null;
return head;
}6. 如何⾼效进⾏模幂运算
今天来聊⼀道与数学运算有关的题⽬，LeetCode 372 题 Super Pow，让你进
⾏巨⼤的幂运算，然后求余数。
int superPow(int a, vector<int>& b);要求你的算法返回幂运算 a^b 的计算结果与 1337 取模（mod，也就是余
数）后的结果。就是你先得计算幂 a^b ，但是这个 b 会⾮常⼤，所以 b
是⽤数组的形式表⽰的。
这个算法其实就是⼴泛应⽤于离散数学的模幂算法，⾄于为什么要对 1337求模我们不管，单就这道题可以有三个难点：
⼀是如何处理⽤数组表⽰的指数，现在 b 是⼀个数组，也就是说 b 可以⾮常⼤，没办法直接转成整型，否则可能溢出。你怎么把这个数组作为指数，进⾏运算呢？
是如何得到求模之后的结果？按道理，起码应该先把幂运算结果算出来，然后做 % 1337 这个运算。但问题是，指数运算你懂得，真实结果肯定会得吓⼈，也就是说，算出来真实结果也没办法表⽰，早都溢出报错了。
⼆ 是如何⾼效进⾏幂运算，进⾏幂运算也是有算法技巧的，如果你不了解这个算法，后⽂会讲解。那么对于这⼏个问题，我们分开思考，逐个击破。如何处理数组指数⾸先明确问题：
现在 b 是⼀个数组，不能表⽰成整型，⽽且数组的特点是随机访问，删除最后⼀个元素⽐较⾼效。
不考虑求模的要求，以 b = [1,5,6,4] 来举例，结合指数运算的法则，我们可以发现这样的⼀个规律：
看到这，我们的⽼读者肯定已经敏感地意识到了，这就是递归的标志呀！因为问题的规模缩⼩了：
superPow(a, [1,5,6,4]) => superPow(a, [1,5,6])那么，发现了这个规律，我们可以先简单翻译出代码框架：
/
/ 计算 a 的 k 次⽅的结果
/ 后⽂我们会⼿动实现
/
int mypow(int a, int k);
int superPow(int a, vector<int>& b) {
/ 递归的 base case
if (b.empty()) return 1;
/ 取出最后⼀个数
/
/
int last = b.back();
b.pop_back();
// 将原问题化简，缩⼩规模递归求解
int part1 = mypow(a, last);
int part2 = mypow(superPow(a, b), 10);
// 合并出结果
return part1 * part2;
}到这⾥，应该都不难理解吧！我们已经解决了 b 是⼀个数组的问题，现在来看看如何处理 mod，避免结果太⼤⽽导致的整型溢出。
如何处理 mod 运算
⾸先明确问题：由于计算机的编码⽅式，形如 (a * b) % base 这样的运算，乘法的结果可能导致溢出，我们希望找到⼀种技巧，能够化简这种表达式，避免溢出同时得到结果。
⽐如在⼆分查找中，我们求中点索引时⽤ (l+r)/2 转化成 l+(r-l)/2 ，避免溢出的同时得到正确的结果。
那么，说⼀个关于模运算的技巧吧，毕竟模运算在算法中⽐较常⻅：
(a * b) % k = (a % k)(b % k) % k
证明很简单，假设：
a = Ak +B；b = Ck + D
其中 A,B,C,D 是任意常数，那么：
ab = ACk^2 + ADk + BCk +BD
ab % k = BD % k
⼜因为：
a % k = B；b % k = D
所以：
(a % k)(b % k) % k = BD % k综上，就可以得到我们化简求模的等式了。
换句话说，对乘法的结果求模，等价于先对每个因⼦都求模，然后对因⼦相乘的结果再求模。
那么扩展到这道题，求⼀个数的幂不就是对这个数连乘么？所以说只要简单扩展刚才的思路，即可给幂运算求模：
int base = 1337;
/ 计算 a 的 k 次⽅然后与 base 求模的结果
int mypow(int a, int k) {
/ 对因⼦求模
/
/
a %= base;
int res = 1;
for (int _ = 0; _ < k; _++) {
/
/ 这⾥有乘法，是潜在的溢出点
res *= a;
/ 对乘法结果求模
/
res %= base;
}
return res;
}
int superPow(int a, vector<int>& b) {
if (b.empty()) return 1;
int last = b.back();
b.pop_back();
int part1 = mypow(a, last);
int part2 = mypow(superPow(a, b), 10);
// 每次乘法都要求模
return (part1 * part2) % base;
}你看，先对因⼦ a 求模，然后每次都对乘法结果 res 求模，这样可以保证 res *= a 这句代码执⾏时两个因⼦都是⼩于 base 的，也就⼀定不会造成溢出，同时结果也是正确的。⾄此，这个问题就已经完全解决了，已经可以通过 LeetCode 的判题系统了。
但是有的读者可能会问，这个求幂的算法就这么简单吗，直接⼀个 for 循环累乘就⾏了？复杂度会不会⽐较⾼，有没有更⾼效地算法呢？
有更⾼效地算法的，但是单就这道题来说，已经⾜够了。
因为你想想，调⽤ mypow 函数传⼊的 k 最多有多⼤？ k 不过是 b 数组中的⼀个数，也就是在 0 到 9 之间，所以可以说这⾥每次调⽤ mypow 的时间复杂度就是 O(1)。整个算法的时间复杂度是 O(N)，N 为 b 的⻓度。但是既然说到幂运算了，不妨顺带说⼀下如何⾼效计算幂运算吧。
如何⾼效求幂
快速求幂的算法不⽌⼀个，就说⼀个我们应该掌握的基本思路吧。利⽤幂运算的性质，我们可以写出这样⼀个递归式：
这个思想肯定⽐直接⽤ for 循环求幂要⾼效，因为有机会直接把问题规模（b 的⼤⼩）直接减⼩⼀半，该算法的复杂度肯定是 log 级了。
那么就可以修改之前的 mypow 函数，翻译这个递归公式，再加上求模的运算：
int base = 1337;
int mypow(int a, int k) {
if (k == 0) return 1;
a %= base;
if (k % 2 == 1) {
// k 是奇数
return (a * mypow(a, k - 1)) % base;
}
else {
// k 是偶数
int sub = mypow(a, k / 2);
return (sub * sub) % base;
}
}虽然对于题⽬，这个优化没有啥特别明显的效率提升，但是这个求幂算法已经升级了，以后如果别⼈让你写幂算法，起码要写出这个算法。⾄此，Super Pow 就算完全解决了，包括了递归思想以及处理模运算、幂运算的技巧，可以说这个题⽬还是挺有意思的，你有什么有趣的题⽬，不妨留分享⼀下。
6.如何寻找最⻓回⽂⼦串
回⽂串是⾯试常常遇到的问题（虽然问题本⾝没啥意义），本⽂就告诉你回⽂串问题的核⼼思想是什么。
⾸先，明确⼀下什：回⽂串就是正着读和反着读都⼀样的字符串。
⽐如说字符串 aba 和 abba 都是回⽂串，因为它们对称，反过来还是和本⾝⼀样。反之，字符串 abac 就不是回⽂串。
可以看到回⽂串的的⻓度可能是奇数，也可能是偶数，这就添加了回⽂串问题的难度，解决该类问题的核⼼是双指针。下⾯就通过⼀道最⻓回⽂⼦串的问题来具体理解⼀下回⽂串问题：
string longestPalindrome(string s) {}⼀、思考
对于这个问题，我们⾸先应该思考的是，给⼀个字符串 s ，如何在 s 中找到⼀个回⽂⼦串？
有⼀个很有趣的思路：既然回⽂串是⼀个正着反着读都⼀样的字符串，那么如果我们把 s 反转，称为 s’ ，然后在 s 和 s’ 中寻找最⻓公共⼦串，这样应该就能找到最⻓回⽂⼦串。
⽐如说字符串 abacd ，反过来是 dcaba ，它的最⻓公共⼦串是 aba ，也就是最⻓回⽂⼦串。
但是这个思路是错误的，⽐如说字符串 aacxycaa ，反转之后是aacyxcaa ，最⻓公共⼦串是 aac ，但是最⻓回⽂⼦串应该是 aa 。
虽然这个思路不正确，但是这种把问题转化为其他形式的思考⽅式是⾮常值得提倡的。
下⾯，就来说⼀下正确的思路，如何使⽤双指针。
寻找回⽂串的问题核⼼思想是：从中间开始向两边扩散来判断回⽂串。对于最⻓回⽂⼦串，就是这个意思：
for 0 <= i < len(s):找到以 s[i] 为中⼼的回⽂串更新答案
但是呢，我们刚才也说了，回⽂串的⻓度可能是奇数也可能是偶数，如果是abba 这种情况，没有⼀个中⼼字符，上⾯的算法就没辙了。所以我们可以修改⼀下：
for 0 <= i < len(s):找到以 s[i] 为中⼼的回⽂串
找到以 s[i] 和 s[i+1] 为中⼼的回⽂串
更新答案
PS：读者可能发现这⾥的索引会越界，等会会处理。
⼆、代码实现
按照上⾯的思路，先要实现⼀个函数来寻找最⻓回⽂串，这个函数是有点技巧的：
string palindrome(string& s, int l, int r) {
// 防⽌索引越界
while (l >= 0 && r < s.size()
& s[l] == s[r]) {
l--; r++;
}
// 返回以 s[l] 和 s[r] 为中⼼的最⻓回⽂串
return s.substr(l + 1, r - l - 1);
}为什么要传⼊两个指针 l 和 r 呢？因为这样实现可以同时处理回⽂串⻓度为奇数和偶数的情况：
0 <# 找到以 s[i] 为中⼼的回⽂串 palindrome(s, i, i) 找到以 s[i] 和 s[i+1] 为中⼼的回⽂串 # palindrome(s, i, i + 1) 更新答案 下⾯看下 longestPalindrome 的完整代码： string longestPalindrome(string s) { string res; for (int i = 0; i < s.size(); i++) { / / 以 s[i] 为中⼼的最⻓回⽂⼦串 string s1 = palindrome(s, i, i); / 以 s[i] 和 s[i+1] 为中⼼的最⻓回⽂⼦串 string s2 = palindrome(s, i, i + 1); / res = longest(res, s1, s2) / / res = res.size() > s1.size() ? res : s1; res = res.size() > s2.size() ? res : s2; } return res; }
至此，这道最⻓回⽂⼦串的问题就解决了，时间复杂度 O(N^2)，空间复杂度 O(1)。值得⼀提的是，这个问题可以⽤动态规划⽅法解决，时间复杂度⼀样，但是空间复杂度⾄少要 O(N^2) 来存储 DP table。这道题是少有的动态规划⾮最优解法的问题。
另外，这个问题还有⼀个巧妙的解法，时间复杂度只需要 O(N)，不过该解法⽐较复杂，我个⼈认为没必要掌握。该算法的名字叫 Manacher’sAlgorithm（⻢拉⻋算法），有兴趣的读者可以⾃⾏搜索⼀下。
7.如何运用贪心思想广域玩跳跃游戏
经典贪⼼算法：跳跃游戏
经常有读者在后台问，动态规划和贪⼼算法到底有啥关系。我们之前的⽂章贪⼼算法之区间调度问题 就说过⼀个常⻅的时间区间调度的贪⼼算法问题。
说⽩了，贪⼼算法可以理解为⼀种特殊的动态规划问题，拥有⼀些更特殊的性质，可以进⼀步降低动态规划算法的时间复杂度。那么这篇⽂章，就讲LeetCode 上两道经典的贪⼼算法：跳跃游戏 I 和跳跃游戏 II。我们可以对这两道题分别使⽤动态规划算法和贪⼼算法进⾏求解，通过实践，你就能更深刻地理解贪⼼和动规的区别和联系了。
Jump Game I
跳跃游戏 I 是 LeetCode 第 55 题，难度是 Medium，但实际上是⽐较简单
的，看题⽬：
如何运⽤贪⼼思想玩跳跃游戏
不知道读者有没有发现，有关动态规划的问题，⼤多是让你求最值的，⽐如最⻓⼦序列，最⼩编辑距离，最⻓公共⼦串等等等。这就是规律，因为动态规划本⾝就是运筹学⾥的⼀种求最值的算法。
那么贪⼼算法作为特殊的动态规划也是⼀样，也⼀定是让你求个最值。这道题表⾯上不是求最值，但是可以改⼀改：
请问通过题⽬中的跳跃规则，最多能跳多远？如果能够越过最后⼀格，返回true，否则返回 false。
所以说，这道题肯定可以⽤动态规划求解的。但是由于它⽐较简单，下⼀道题再⽤动态规划和贪⼼思路进⾏对⽐，现在直接上贪⼼的思路：
bool canJump(vector<int>& nums) {
int n = nums.size();
int farthest = 0;
for (int i = 0; i < n - 1; i++) {
// 不断计算能跳到的最远距离
farthest = max(farthest, i + nums[i]);
// 可能碰到了 0，卡住跳不动了
if (farthest <= i) return false;
}
return farthest >= n - 1;
}你别说，如果之前没有做过类似的题⽬，还真不⼀定能够想出来这个解法。
每⼀步都计算⼀下从当前位置最远能够跳到哪⾥，然后和⼀个全局最优的最远位置 farthest 做对⽐，通过每⼀步的最优解，更新全局最优解，这就是贪⼼。
很简单是吧？记住这⼀题的思路，看第⼆题，你就发现事情没有这么简单。。。
Jump Game II
这是 LeetCode 第 45 题，也是让你在数组上跳，不过难度是 Hard，解法可没上⼀题那么简单直接：
现在的问题是，保证你⼀定可以跳到最后⼀格，请问你最少要跳多少次，才能跳过去。
我们先来说说动态规划的思路，采⽤⾃顶向下的递归动态规划，可以这样定义⼀个 dp 函数：
// 定义：从索引 p 跳到最后⼀格，⾄少需要 dp(nums, p) 步
int dp(vector<int>& nums, int p);
我们想求的结果就是 dp(nums, 0) ，base case 就是当 p 超过最后⼀格时，
不需要跳跃：
if (p >= nums.size() - 1) {
return 0;
}根据前⽂ 动态规划套路详解 的动规框架，就可以暴⼒穷举所有可能的跳法，通过备忘录 memo 消除重叠⼦问题，取其中的最⼩值最为最终答案：
vector<int> memo;
// 主函数
int jump(vector<int>& nums) {
int n = nums.size();
/
/ 备忘录都初始化为 n，相当于 INT_MAX
/ 因为从 0 调到 n - 1 最多 n - 1 步
/
memo = vector<int>(n, n);
return dp(nums, 0);
}
int dp(vector<int>& nums, int p) {
int n = nums.size();
// base case
if (p >= n - 1) {
return 0;
}
// ⼦问题已经计算过
if (memo[p] != n) {
return memo[p];
}
int steps = nums[p];
// 你可以选择跳 1 步，2 步...
for (int i = 1; i <= steps; i++) {
5
47如何运⽤贪⼼思想玩跳跃游戏
// 穷举每⼀个选择
// 计算每⼀个⼦问题的结果
int subProblem = dp(nums, p + i);
// 取其中最⼩的作为最终结果
memo[p] = min(memo[p], subProblem + 1);
}
return memo[p];
}这个动态规划应该很明显了，按照前⽂ 动态规划套路详解 所说的套路，状态就是当前所站⽴的索引 p ，选择就是可以跳出的步数。
该算法的时间复杂度是 递归深度 × 每次递归需要的时间复杂度，即O(N^2)，在 LeetCode 上是⽆法通过所有⽤例的，会超时。
贪⼼算法⽐动态规划多了⼀个性质：贪⼼选择性质。我知道⼤家都不喜欢看严谨但枯燥的数学形式定义，那么我们就来直观地看⼀看什么样的问题满⾜贪⼼选择性质。
刚才的动态规划思路，不是要穷举所有⼦问题，然后取其中最⼩的作为结果吗？核⼼的代码框架是这样：
int steps = nums[p];
// 你可以选择跳 1 步，2 步...
for (int i = 1; i <= steps; i++) {
// 计算每⼀个⼦问题的结果
int subProblem = dp(nums, p + i);
res = min(subProblem + 1, res);
}for 循环中会陷⼊递归计算⼦问题，这是动态规划时间复杂度⾼的根本原因。
但是，真的需要【递归地】计算出每⼀个⼦问题的结果，然后求最值吗？直观地想⼀想，似乎不需要递归，只需要判断哪⼀个选择最具有【潜⼒】即可：
不过我们常⻅的贪⼼算法题⽬，就像本⽂的题⽬，⼤多⼀眼就能看出来，⼤不了就先⽤动态规划求解，如果动态规划都超时，说明该问题存在贪⼼选择性质⽆疑了。
8.如何K个一组反转链表
如何k个⼀组反转链表
之前的⽂章「递归反转链表的⼀部分」讲了如何递归地反转⼀部分链表，有读者就问如何迭代地反转链表，这篇⽂章解决的问题也需要反转链表的函数，我们不妨就⽤迭代⽅式来解决。本⽂要解决「K 个⼀组反转链表」，不难理解：
这个问题经常在⾯经中看到，⽽且 LeetCode 上难度是 Hard，它真的有那么难吗？
对于基本数据结构的算法问题其实都不难，只要结合特点⼀点点拆解分析，⼀般都没啥难点。下⾯我们就来拆解⼀下这个问题。
⼀、分析问题
⾸先，前⽂学习数据结构的框架思维提到过，链表是⼀种兼具递归和迭代性质的数据结构，认真思考⼀下可以发现这个问题具有递归性质。
什么叫递归性质？
⽐如说我们对这个链表调⽤
reverseKGroup(head, 2) ，即以 2 个节点为⼀组反转链表：
如何k个⼀组反转链表
如果我设法把前 2 个节点反转，那么后⾯的那些节点怎么处理？后⾯的这些节点也是⼀条链表，⽽且规模（⻓度）⽐原来这条链表⼩，这就叫⼦问题。
我们可以直接递归调⽤ reverseKGroup(cur, 2) ，因为⼦问题和原问题的结构完全相同，这就是所谓的递归性质。
发现了递归性质，就可以得到⼤致的算法流程：
1、先反转以 head 开头的 k 个元素。
2、将第 k + 1 个元素作为 head 递归调⽤ reverseKGroup 函数。
3、将上述两个过程的结果连接起来。
这次使⽤迭代思路来实现的，借助动画理解应该很容易。
「反转以 a 为头结点的链表」其实就是「反转 a 到 null 之间的结点」，那么如果让你「反转 a 到 b 之间的结点」，你会不会？
只要更改函数签名，并把上⾯的代码中 null 改成 b 即可：
/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
// while 终⽌的条件改⼀下就⾏了
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
// 返回反转后的头结点
return pre;
}现在我们迭代实现了反转部分链表的功能，接下来就按照之前的逻辑编写
reverseKGroup 函数即可：
ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// 区间 [a, b) 包含 k 个待反转元素
ListNode a, b;
a = b = head;
for (int i = 0; i < k; i++) {
// 不⾜ k 个，不需要反转，base case
if (b == null) return head;
b = b.next;
}三、最后说两句
⼤家喜欢看动态规划相关的问题，可能因为⾯试很常⻅，但就我个⼈理解，很多算法思想都是源于数据结构的。我们公众号的成名之作之⼀，「学习数据结构的框架思维」就提过，什么动规、回溯、分治算法，其实都是树的遍历，树这种结构它不就是个多叉链表吗？你能处理基本数据结构的问题，解决⼀般的算法问题应该也不会太费事。
那么如何分解问题、发现递归性质呢？这个只能多练习，也许后续可以专门写⼀篇⽂章来探讨⼀下，本⽂就到此为⽌吧，希望对⼤家有帮助！
9.如何判定括号合法性
对括号的合法性判断是⼀个很常⻅且实⽤的问题，⽐如说我们写的代码，编辑器和编译器都会检查括号是否正确闭合。⽽且我们的代码可能会包含三种括号 {} ，判断起来有⼀点难度。本⽂就来聊⼀道关于括号合法性判断的算法题，相信能加深你对栈这种数据结构的理解。
题⽬很简单，输⼊⼀个字符串，其中包含 {} 六种括号，请你判断这个字符串组成的括号是否合法。
Input: “()[]{}”
Output: true
Input: “([)]”
Output: false
Input: “{[]}”
Output: true
解决这个问题之前，我们先降低难度，思考⼀下，如果只有⼀种括号() ，应该如何判断字符串组成的括号是否合法呢？
⼀、处理⼀种括号
字符串中只有圆括号，如果想让括号字符串合法，那么必须做到：每个右括号 ) 的左边必须有⼀个左括号 ( 和它匹配。⽐如说字符串 ()))(( 中，中间的两个右括号左边就没有左括号匹配，所以这个括号组合是不合法的。那么根据这个思路，我们可以写出算法：
如何判定括号合法性
bool isValid(string str) {
// 待匹配的左括号数量
int left = 0;
for (char c : str) {
if (c == '(')
left++;
else // 遇到右括号
left--;
if (left < 0)
return false;
}
return left == 0;
}如果只有圆括号，这样就能正确判断合法性。对于三种括号的情况，我⼀开始想模仿这个思路，定义三个变量 left1 ， left2 ， left3 分别处理每种括号，虽然要多写不少 if else 分⽀，但是似乎可以解决问题。
但实际上直接照搬这种思路是不⾏的，⽐如说只有⼀个括号的情况下 (())是合法的，但是多种括号的情况下， [(]) 显然是不合法的。仅仅记录每种左括号出现的次数已经不能做出正确判断了，我们要加⼤存储的信息量，可以利⽤栈来模仿类似的思路。
⼆、处理多种括号
栈是⼀种先进后出的数据结构，处理括号问题的时候尤其有⽤。我们这道题就⽤⼀个名为 left 的栈代替之前思路中的 left 变量，遇到左括号就⼊栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配。
bool isValid(string str) {
stack<char> left;
for (char c : str) {
if (c == '(' || c == '{' || c == '[')
left.push(c);
else // 字符 c 是右括号
if (!left.empty() && leftOf(c) == left.top())
left.pop();
else
// 和最近的左括号不匹配
return false;
}
// 是否所有的左括号都被匹配了
return left.empty();
}
char leftOf(char c) {
if (c == '}') return '{';
if (c == ')') return '(';
return '[';
}10. 如何寻找消失的元素
之前也有⽂章写过⼏个有趣的智⼒题，今天再聊⼀道巧妙的题⽬。
题⽬⾮常简单：
给⼀个⻓度为 n 的数组，其索引应该在 [0,n) ，但是现在你要装进去 n + 1个元素 [0,n] ，那么肯定有⼀个元素装不下嘛，请你找出这个缺失的元素。
这道题不难的，我们应该很容易想到，把这个数组排个序，然后遍历⼀遍，不就很容易找到缺失的那个元素了吗？
或者说，借助数据结构的特性，⽤⼀个 HashSet 把数组⾥出现的数字都储存下来，再遍历 [0,n] 之间的数字，去 HashSet 中查询，也可以很容易查出那个缺失的元素。
排序解法的时间复杂度是 O(NlogN)，HashSet 的解法时间复杂度是 O(N)，但是还需要 O(N) 的空间复杂度存储 HashSet。
第三种⽅法是位运算。
如何寻找缺失的元素
由于异或运算满⾜交换律和结合律，所以总是能把成对⼉的数字消去，留下缺失的那个元素的。
⾄此，时间复杂度 O(N)，空间复杂度 O(1)，已经达到了最优，我们是否就应该打道回府了呢？
如果这样想，说明我们受算法的毒害太深，随着我们学习的知识越来越多，反⽽容易陷⼊思维定式，这个问题其实还有⼀个特别简单的解法：等差数列求和公式。
题⽬的意思可以这样理解：现在有个等差数列 0, 1, 2,…, n，其中少了某⼀个数字，请你把它找出来。那这个数字不就是 sum(0,1,…n) - sum(nums)嘛？
int missingNumber(int[] nums) {
int n = nums.length;
// 公式：(⾸项 + 末项) * 项数 / 2
int expect = (0 + n) * (n + 1) / 2;
int sum = 0;
for (int x : nums)
sum += x;
return expect - sum;你看，这种解法应该是最简单的，但说实话，我⾃⼰也没想到这个解法，⽽且我去问了⼏个⼤佬，他们也没想到这个最简单的思路。相反，如果去问⼀个初中⽣，他也许很快就能想到。
做到这⼀步了，我们是否就应该打道回府了呢？如果这样想，说明我们对细节的把控还差点⽕候。在⽤求和公式计算expect 时，你考虑过整型溢出吗？如果相乘的结果太⼤导致溢出，那么结
果肯定是错误的。
刚才我们的思路是把两个和都加出来然后相减，为了避免溢出，⼲脆⼀边求和⼀边减算了。很类似刚才位运算解法的思路，仍然假设 nums =[0,3,1,4] ，先补⼀位索引再让元素跟索引配对：
我们让每个索引减去其对应的元素，再把相减的结果加起来，不就是那个缺失的元素吗？
public int missingNumber(int[] nums) {
int n = nums.length;
int res = 0;
/
/ 新补的索引
res += n - 0;
/ 剩下索引和元素的差加起来
/
for (int i = 0; i < n; i++)
res += i - nums[i];
return res;
}由于加减法满⾜交换律和结合律，所以总是能把成对⼉的数字消去，留下缺失的那个元素的。
⾄此这道算法题⽬经历九曲⼗⼋弯，终于再也没有什么坑了。
11.如何寻找缺失和重复的元素
今天就聊⼀道很看起来简单却⼗分巧妙的问题，寻找缺失和重复的元素。之前的⼀篇⽂章「寻找缺失元素」也写过类似的问题，不过这次的和上次的问题使⽤的技巧不同。
这是 LeetCode 645 题，我来描述⼀下这个题⽬：
给⼀个⻓度为 N 的数组 nums ，其中本来装着 [1…N] 这 N 个元素，⽆序。但是现在出现了⼀些错误， nums 中的⼀个元素出现了重复，也就同时导致了另⼀个元素的缺失。请你写⼀个算法，找到 nums 中的重复元素和缺失元素的值。
// 返回两个数字，分别是 {dup, missing}
vector<int> findErrorNums(vector<int>& nums);⽐如说输⼊： nums = [1,2,2,4] ，算法返回 [2,3] 。
其实很容易解决这个问题，先遍历⼀次数组，⽤⼀个哈希表记录每个数字出现的次数，然后遍历⼀次 [1…N] ，看看那个元素重复出现，那个元素没有出现，就 OK 了。
但问题是，这个常规解法需要⼀个哈希表，也就是 O(N) 的空间复杂度。你看题⽬给的条件那么巧，在 [1…N] 的⼏个数字中恰好有⼀个重复，⼀个缺失，事出反常必有妖，对吧。O(N) 的时间复杂度遍历数组是⽆法避免的，所以我们可以想想办法如何降低空间复杂度，是否可以在 O(1) 的空间复杂度之下找到重复和确实的元素呢？
思路分析
这个问题的特点是，每个元素和数组索引有⼀定的对应关系。
这个问题就基本解决了，别忘了我们刚才为了⽅便分析，假设元素是[0…N-1] ，但题⽬要求是 [1…N] ，所以只要简单修改两处地⽅即可得到原题的答案：
vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
int dup = -1;
for (int i = 0; i < n; i++) {
// 现在的元素是从 1 开始的
int index = abs(nums[i]) - 1;
if (nums[index] < 0)
dup = abs(nums[i]);
else
nums[index] *= -1;
}
int missing = -1;
for (int i = 0; i < n; i++)
if (nums[i] > 0)
// 将索引转换成元素
missing = i + 1;
return {dup, missing};
}其实，元素从 1 开始是有道理的，也必须从⼀个⾮零数开始。因为如果元素从 0 开始，那么 0 的相反数还是⾃⼰，所以如果数字 0 出现了重复或者缺失，算法就⽆法判断 0 是否被访问过。我们之前的假设只是为了简化题⽬，更通俗易懂。
最后总结
对于这种数组问题，关键点在于元素和索引是成对⼉出现的，常⽤的⽅法是排序、异或、映射。
映射的思路就是我们刚才的分析，将每个索引和元素映射起来，通过正负号记录某个元素是否被映射。
排序的⽅法也很好理解，对于这个问题，可以想象如果元素都被从⼩到⼤排序，如果发现索引对应的元素如果不相符，就可以找到重复和缺失的元素。
异或运算也是常⽤的，因为异或性质 a ^ a = 0, a ^ 0 = a ，如果将索引和元素同时异或，就可以消除成对⼉的索引和元素，留下的就是重复或者缺失的元素。可以看看前⽂「寻找缺失元素」，介绍过这种⽅法。
12.如何⾼效判断回⽂链表
我们之前有两篇⽂章写了回⽂串和回⽂序列相关的问题。
寻找回⽂串的核⼼思想是从中⼼向两端扩展：
string palindrome(string& s, int l, int r) {
// 防⽌索引越界
while (l >= 0 && r < s.size()
& s[l] == s[r]) {
l--; r++;
}
// 返回以 s[l] 和 s[r] 为中⼼的最⻓回⽂串
return s.substr(l + 1, r - l - 1);
}因为回⽂串⻓度可能为奇数也可能是偶数，⻓度为奇数时只存在⼀个中⼼点，⽽⻓度为偶数时存在两个中⼼点，所以上⾯这个函数需要传⼊⽽「l 和 r 。
判断⼀个字符串是不是回⽂串就简单很多，不需要考虑奇偶情况，只需要双指针技巧」，从两端向中间逼近即可：
bool isPalindrome(string s) {
int left = 0, right = s.length - 1;
while (left < right) {
if (s[left] != s[right])
return false;
left++; right--;
}
return true;
}以上代码很好理解吧，因为回⽂串是对称的，所以正着读和倒着读应该是⼀样的，这⼀特点是解决回⽂串问题的关键。
下⾯扩展这⼀最简单的情况，来解决：如何判断⼀个「单链表」是不是回⽂。
⼀、判断回⽂单链表
输⼊⼀个单链表的头结点，判断这个链表中的数字是不是回⽂：
/**
*单链表节点的定义：
*
*
*
*
*
public class ListNode {
int val;
ListNode next;
}
/
boolean isPalindrome(ListNode head);
输⼊: 1->2->null
输出: false
输⼊: 1->2->2->1->null
输出: true这道题的关键在于，单链表⽆法倒着遍历，⽆法使⽤双指针技巧。那么最简单的办法就是，把原始链表反转存⼊⼀条新的链表，然后⽐较这两条链表是否相同。关于如何反转链表，可以参⻅前⽂「递归操作链表」。
其实，借助⼆叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表，下⾯来具体聊聊。
对于⼆叉树的⼏种遍历⽅式，我们再熟悉不过了：
void traverse(TreeNode root) {
// 前序遍历代码
traverse(root.left);
5
76如何判断回⽂链表
// 中序遍历代码
traverse(root.right);
// 后序遍历代码
}
在「学习数据结构的框架思维」中说过，链表兼具递归结构，树结构不过是
链表的衍⽣。那么，链表其实也可以有前序遍历和后序遍历：
void traverse(ListNode head) {
// 前序遍历代码
traverse(head.next);
// 后序遍历代码
}
这个框架有什么指导意义呢？如果我想正序打印链表中的 val 值，可以在
前序遍历位置写代码；反之，如果想倒序遍历链表，就可以在后序遍历位置
操作：
/* 倒序打印单链表中的元素值 */
void traverse(ListNode head) {
if (head == null) return;
traverse(head.next);
// 后序遍历代码
print(head.val);
}说到这了，其实可以稍作修改，模仿双指针实现回⽂判断的功能：
// 左侧指针
ListNode left;
boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
boolean traverse(ListNode right) {
if (right == null) return true;
boolean res = traverse(right.next);
// 后序遍历代码
res = res && (right.val == left.val);
left = left.next;
return res;
}这么做的核⼼逻辑是什么呢？实际上就是把链表节点放⼊⼀个栈，然后再拿出来，这时候元素顺序就是反的，只不过我们利⽤的是递归函数的堆栈⽽已。⽆论造⼀条反转链表还是利⽤后续遍历，算法的时间和空间复杂度都是 O(N)。下⾯我们想想，能不能不⽤额外的空间，解决这个问题呢？
⼆、优化空间复杂度
更好的思路是这样的：
1、先通过「双指针技巧」中的快慢指针来找到链表的中点：
ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 指针现在指向链表中点2、如果 fast 指针没有指向 null ，说明链表⻓度为奇数， slow 还要再前进⼀步：
if (fast != null)
slow = slow.next;3、从 slow 开始反转后⾯的链表，现在就可以开始⽐较回⽂串了：算法总体的时间复杂度 O(N)，空间复杂度 O(1)，已经是最优的了。
我知道肯定有读者会问：这种解法虽然⾼效，但破坏了输⼊链表的原始结构，能不能避免这个瑕疵呢？
其实这个问题很好解决，关键在于得到 p, q 这两个指针位置：这样，只要在函数 return 之前加⼀段代码即可恢复原先链表顺序：p.next = reverse(q);篇幅所限，我就不写了，读者可以⾃⼰尝试⼀下。
三、最后总结
⾸先，寻找回⽂串是从中间向两端扩展，判断回⽂串是从两端向中间收缩。对于单链表，⽆法直接倒序遍历，可以造⼀条新的反转链表，可以利⽤链表的后序遍历，也可以⽤栈结构倒序处理单链表。
具体到回⽂链表的判断问题，由于回⽂的特殊性，可以不完全反转链表，⽽是仅仅反转部分链表，将空间复杂度降到 O(1)。
13.如何在无线序列中随机抽取元素
随机算法之⽔塘抽样算法
我最近在 LeetCode 上做到两道⾮常有意思的题⽬，382 和 398 题，关于⽔塘抽样算法（Reservoir Sampling），本质上是⼀种随机概率算法，解法应该说会者不难，难者不会。
我第⼀次⻅到这个算法问题是⾕歌的⼀道算法题：给你⼀个未知⻓度的链表，请你设计⼀个算法，只能遍历⼀次，随机地返回链表中的⼀个节点。这⾥说的随机是均匀随机（uniform random），也就是说，如果有 n 个元素，每个元素被选中的概率都是 1/n ，不可以有统计意义上的偏差。⼀般的想法就是，我先遍历⼀遍链表，得到链表的总⻓度 n ，再⽣成⼀个[1,n] 之间的随机数为索引，然后找到索引对应的节点，不就是⼀个随机的节点了吗？
但题⽬说了，只能遍历⼀次，意味着这种思路不可⾏。题⽬还可以再泛化，给⼀个未知⻓度的序列，如何在其中随机地选择 k 个元素？想要解决这个问题，就需要著名的⽔塘抽样算法了。
算法实现
先解决只抽取⼀个元素的问题，这个问题的难点在于，随机选择是「动态」的，⽐如说你现在你有 5 个元素，你已经随机选取了其中的某个元素 a 作为结果，但是现在再给你⼀个新元素 b ，你应该留着 a 还是将 b 作为结果呢，以什么逻辑选择 a 和 b 呢，怎么证明你的选择⽅法在概率上是
公平的呢？
先说结论，当你遇到第 i 个元素时，应该有 1/i 的概率选择该元素， 1-1/i 的概率保持原有的选择。看代码容易理解这个思路：
/* 返回链表中⼀个随机节点的值 */
int getRandom(ListNode head) {
如何在⽆限序列中随机抽取元素
5
83Random r = new Random();
int i = 0, res = 0;
ListNode p = head;
// while 循环遍历链表
while (p != null) {
// ⽣成⼀个 [0, i) 之间的整数
// 这个整数等于 0 的概率就是 1/i
if (r.nextInt(++i) == 0) {
res = p.val;
}
p = p.next;
}
return res;
}对于概率算法，代码往往都是很浅显的，但是这种问题的关键在于证明，你的算法为什么是对的？为什么每次以 1/i 的概率更新结果就可以保证结果是平均随机（uniform random）？
证明：假设总共有 n 个元素，我们要的随机性⽆⾮就是每个元素被选择的概率都是 1/n 对吧，那么对于第 i 个元素，它被选择的概率就是：第 i 个元素被选择的概率是 1/i ，第 i+1 次不被替换的概率是 1 -11/(i+1) ，以此类推，相乘就是第 i 个元素最终被选中的概率，就是/n 。
因此，该算法的逻辑是正确的。
同理，如果要随机选择 k 个数，只要在第 i 个元素处以 k/i 的概率选择该元素，以 1 - k/i 的概率保持原有选择即可。代码如下：
/* 返回链表中 k 个随机节点的值 */
int[] getRandom(ListNode head, int k) {
Random r = new Random();
int[] res = new int[k];
ListNode p = head;
// 前 k 个元素先默认选上
for (int j = 0; j < k && p != null; j++) {
res[j] = p.val;
p = p.next;
}
int i = k;
// while 循环遍历链表
while (p != null) {
/ ⽣成⼀个 [0, i) 之间的整数
int j = r.nextInt(++i);
/ 这个整数⼩于 k 的概率就是 k/i
//
if (j < k) {
res[j] = p.val;
}
p = p.next;
}
return res;
}对于数学证明，和上⾯区别不⼤：
因为虽然每次更新选择的概率增⼤了 k 倍，但是选到具体第 i 个元素的概率还是要乘 1/k ，也就回到了上⼀个推导。
以上的抽样算法时间复杂度是 O(n)，但不是最优的⽅法，更优化的算法基于⼏何分布（geometric distribution），时间复杂度为 O(k + klog(n/k))。由于涉及的数学知识⽐较多，这⾥就不列出了，有兴趣的读者可以⾃⾏搜索⼀下。
还有⼀种思路是基于「Fisher–Yates 洗牌算法」的。随机抽取 k 个元素，等价于对所有元素洗牌，然后选取前 k 个。只不过，洗牌算法需要对元素的随机访问，所以只能对数组这类⽀持随机存储的数据结构有效。
另外有⼀种思路也⽐较有启发意义：给每⼀个元素关联⼀个随机数，然后把每个元素插⼊⼀个容量为 k ⼆叉堆（优先级队列）按照配对的随机数进⾏排序，最后剩下的 k 个元素也是随机的。
这个⽅案看起来似乎有点多此⼀举，因为插⼊⼆叉堆需要 O(logk) 的时间复杂度，所以整个抽样算法就需要 O(nlogk) 的复杂度，还不如我们最开始的算法。但是，这种思路可以指导我们解决加权随机抽样算法，权重越⾼，被随机选中的概率相应增⼤，这种情况在现实⽣活中是很常⻅的，⽐如你不往游戏⾥充钱，就永远抽不到⽪肤。
最后，我想说随机算法虽然不多，但其实很有技巧的，读者不妨思考两个常⻅且看起来很简单的问题：
1、如何对带有权重的样本进⾏加权随机抽取？⽐如给你⼀个数组 w ，每个元素 w[i] 代表权重，请你写⼀个算法，按照权重随机抽取索引。⽐如w = [1,99] ，算法抽到索引 0 的概率是 1%，抽到索引 1 的概率是 99%。
2、实现⼀个⽣成器类，构造函数传⼊⼀个很⻓的数组，请你实现randomGet ⽅法，每次调⽤随机返回数组中的⼀个元素，多次调⽤不能重复返回相同索引的元素。要求不能对该数组进⾏任何形式的修改，且操作的时间复杂度是 O(1)。这两个问题都是⽐较困难的，以后有时间我会写⼀写相关的⽂章。
＿＿＿＿＿＿＿＿＿＿＿
如何在⽆限序列中随机抽取元素
14.如何调度考⽣的座位
这是 LeetCode 第 885 题，有趣且具有⼀定技巧性。这种题⽬并不像动态规划这类算法拼智商，⽽是看你对常⽤数据结构的理解和写代码的⽔平，个⼈认为值得重视和学习。
另外说句题外话，很多读者都问，算法框架是如何总结出来的，其实框架反⽽是慢慢从细节⾥抠出来的希望⼤家看了我们的⽂章之后，最好能抽时间把相关的问题亲⾃做⼀做，纸上得来终觉浅，绝知此事要躬⾏嘛。
先来描述⼀下题⽬：假设有⼀个考场，考场有⼀排共 N 个座位，索引分别是 [0…N-1] ，考⽣会陆续进⼊考场考试，并且可能在任何时候离开考场。你作为考官，要安排考⽣们的座位，满⾜：每当⼀个学⽣进⼊时，你需要最⼤化他和最近其他⼈的距离；如果有多个这样的座位，安排到他到索引最⼩的那个座位。这很符合实际情况对吧，也就是请你实现下⾯这样⼀个类：class ExamRoom {
// 构造函数，传⼊座位总数 N
public ExamRoom(int N);
// 来了⼀名考⽣，返回你给他分配的座位
public int seat();
// 坐在 p 位置的考⽣离开了
// 可以认为 p 位置⼀定坐有考⽣
public void leave(int p);
}⽐⽅说考场有 5 个座位，分别是 [0…4] ：
第⼀名考⽣进⼊时（调⽤ seat() ），坐在任何位置都⾏，但是要给他安排索引最⼩的位置，也就是返回位置 0。
第⼆名学⽣进⼊时（再调⽤ seat() ），要和旁边的⼈距离最远，也就是返回位置 4。
第三名学⽣进⼊时，要和旁边的⼈距离最远，应该做到中间，也就是座位
如果再进⼀名学⽣，他可以坐在座位 1 或者 3，取较⼩的索引 1。
刚才所说的情况，没有调⽤ leave 函数，不过读者肯定能够发现规律： 如果将每两个相邻的考⽣看做线段的两端点，新安排考⽣就是找最⻓的线段，然后让该考⽣在中间把这个线段「⼆分」，中点就是给他分配的座位。 leave(p) 其实就是去除端点 p ，使得相邻两个线段合并为⼀个。核⼼思路很简单对吧，所以这个问题实际上实在考察你对数据结构的理解。对于上述这个逻辑，你⽤什么数据结构来实现呢？
⼀、思路分析
根据上述思路，⾸先需要把坐在教室的学⽣抽象成线段，我们可以简单的⽤⼀个⼤⼩为 2 的数组表⽰。
另外，思路需要我们找到「最⻓」的线段，还需要去除线段，增加线段。但凡遇到在动态过程中取最值的要求，肯定要使⽤有序数据结构，我们常⽤的数据结构就是⼆叉堆和平衡⼆叉搜索树了。⼆叉堆实现的优先级队列取最值的时间复杂度是 O(logN)，但是只能删除最⼤值。平衡⼆叉树也可以取最值，也可以修改、删除任意⼀个值，⽽且时间复杂度都是 O(logN)。综上，⼆叉堆不能满⾜ leave 操作，应该使⽤平衡⼆叉树。所以这⾥我们会⽤到 Java 的⼀种数据结构 TreeSet ，这是⼀种有序数据结构，底层由红⿊树维护有序性。
⼀说到集合（Set）或者映射（Map），有的读者可能就想当然的认为是哈希集合（HashSet）或者哈希表（HashMap），这样理解是有点问题的。
因为哈希集合/映射底层是由哈希函数和数组实现的，特性是遍历⽆固定顺序，但是操作效率⾼，时间复杂度为 O(1)。
⽽集合/映射还可以依赖其他底层数据结构，常⻅的就是红⿊树（⼀种平衡叉搜索树），特性是⾃动维护其中元素的顺序，操作效率是 O(logN)。这⼆种⼀般称为「有序集合/映射」。我们使⽤的 TreeSet 就是⼀个有序集合，⽬的就是为了保持线段⻓度的有序性，快速查找最⼤线段，快速删除和插⼊。
⼆、简化问题
⾸先，如果有多个可选座位，需要选择索引最⼩的座位对吧？我们先简化⼀下问题，暂时不管这个要求，实现上述思路。这个问题还⽤到⼀个常⽤的编程技巧，就是使⽤⼀个「虚拟线段」让算法正确启动，这就和链表相关的算法需要「虚拟头结点」⼀个道理。
/
/ 将端点 p 映射到以 p 为左端点的线段
private Map<Integer, int[]> startMap;
/ 将端点 p 映射到以 p 为右端点的线段
private Map<Integer, int[]> endMap;
/ 根据线段⻓度从⼩到⼤存放所有线段
/
/
private TreeSet<int[]> pq;
private int N;
public ExamRoom(int N) {
this.N = N;
startMap = new HashMap<>();
endMap = new HashMap<>();
pq = new TreeSet<>((a, b) -> {
// 算出两个线段的⻓度
int distA = distance(a);
int distB = distance(b);
如何调度考⽣的座位
5
90如何调度考⽣的座位
/
/ ⻓度更⻓的更⼤，排后⾯
return distA - distB;
);
/ 在有序集合中先放⼀个虚拟线段
}
/
addInterval(new int[] {-1, N});
}
/* 去除⼀个线段 */
private void removeInterval(int[] intv) {
pq.remove(intv);
startMap.remove(intv[0]);
endMap.remove(intv[1]);
}
/* 增加⼀个线段 */
private void addInterval(int[] intv) {
pq.add(intv);
startMap.put(intv[0], intv);
endMap.put(intv[1], intv);
}
/* 计算⼀个线段的⻓度 */
private int distance(int[] intv) {
return intv[1] - intv[0] - 1;
}「虚拟线段」其实就是为了将所有座位表⽰为⼀个线段：
现在有序集合⾥有线段 [0,4] 和 [4,9] ，那么最⻓线段 longest 就是后者，按照 seat 的逻辑，就会分割 [4,9] ，也就是返回座位 6。但正确答案应该是座位 2，因为 2 和 6 都满⾜最⼤化相邻考⽣距离的条件，⼆者应该取较⼩的。
遇到题⽬的这种要求，解决⽅式就是修改有序数据结构的排序⽅式。具体到这个问题，就是修改 TreeMap 的⽐较函数逻辑：
四、最后总结
本⽂聊的这个问题其实并不算难，虽然看起来代码很多。核⼼问题就是考察有序数据结构的理解和使⽤，来梳理⼀下。
处理动态问题⼀般都会⽤到有序数据结构，⽐如平衡⼆叉搜索树和⼆叉堆，⼆者的时间复杂度差不多，但前者⽀持的操作更多。
既然平衡⼆叉搜索树这么好⽤，还⽤⼆叉堆⼲嘛呢？因为⼆叉堆底层就是数组，实现简单啊，详⻅旧⽂「⼆叉堆详解」。你实现个红⿊树试试？操作复杂，⽽且消耗的空间相对来说会多⼀些。具体问题，还是要选择恰当的数据结构来解决。
希望本⽂对⼤家有帮助。
Union-Find算法详解
现在我们的 Union-Find 算法主要需要实现这两个 API：
class UF {
/
* 将 p 和 q 连接 */
public void union(int p, int q);
* 判断 p 和 q 是否连通 */
public boolean connected(int p, int q);
* 返回图中有多少个连通分量 */
//
public int count();
}这⾥所说的「连通」是⼀种等价关系，也就是说具有如下三个性质：
1、⾃反性：节点 p 和 p 是连通的。
2、对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通。
3、传递性：如果节点 p 和 q 连通， q 和 r 连通，那么 p 和 r 也连通。
⽐如说之前那幅图，0〜9 任意两个不同的点都不连通，调⽤ connected 都
会返回 false，连通分量为 10 个。
如果现在调⽤ union(0, 1) ，那么 0 和 1 被连通，连通分量降为 9 个。
再调⽤ union(1, 2) ，这时 0,1,2 都被连通，调⽤ connected(0, 2) 也会返回
true，连通分量变为 8 个。
Union-Find算法详解
所以说上⾯这种解法， find , union , connected 的时间复杂度都是 O(N)。这个复杂度很不理想的，你想图论解决的都是诸如社交⽹络这样数据规模巨⼤的问题，对于 union 和 connected 的调⽤⾮常频繁，每次调⽤需要线性时间完全不可忍受。
问题的关键在于，如何想办法避免树的不平衡呢？只需要略施⼩计即可。
三、平衡性优化
我们要知道哪种情况下可能出现不平衡现象，关键在于 union 过程：
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// 将两棵树合并为⼀棵
parent[rootP] = rootQ;
parent[rootQ] = rootP 也可以
count--;
//Union-Find算法详解
}⽐如说 size[3] = 5 表⽰，以节点 3 为根的那棵树，总共有 5 个节点。这样我们可以修改⼀下 union ⽅法：
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// ⼩树接到⼤树下⾯，较平衡
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}这样，通过⽐较树的重量，就可以保证树的⽣⻓相对平衡，树的⾼度⼤致在 logN 这个数量级，极⼤提升执⾏效率。此时， find , union , connected 的时间复杂度都下降为 O(logN)，即便数据规模上亿，所需时间也⾮常少。
四、路径压缩
这步优化特别简单，所以⾮常巧妙。我们能不能进⼀步压缩每棵树的⾼度，使树⾼始终保持为常数？
15.Union-Find算法详解
PS：读者可能会问，这个 GIF 图的find过程完成之后，树⾼恰好等于 3 了，但是如果更⾼的树，压缩后⾼度依然会⼤于 3 呀？不能这么想。这个 GIF的情景是我编出来⽅便⼤家理解路径压缩的，但是实际中，每次find都会进⾏路径压缩，所以树本来就不可能增⻓到这么⾼，你的这种担⼼应该是多余的。
五、最后总结
我们先来看⼀下完整代码：
class UF {
// 连通分量个数
private int count;
// 存储⼀棵树
private int[] parent;
// 记录树的“重量”
private int[] size;
public UF(int n) {
this.count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// ⼩树接到⼤树下⾯，较平衡
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
private int find(int x) {
while (parent[x] != x) {
// 进⾏路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int count() {
return count;
}
}Union-Find 算法的复杂度可以这样分析：构造函数初始化数据结构需要O(N) 的时间和空间复杂度；连通两个节点 union 、判断两个节点的连通性 connected 、计算连通分量 count 所需的时间复杂度均为 O(1)。
16.Union-Find算法应用
Union-Find算法应⽤
上篇⽂章很多读者对于 Union-Find 算法的应⽤表⽰很感兴趣，这篇⽂章就拿⼏道 LeetCode 题⽬来讲讲这个算法的巧妙⽤法。
⾸先，复习⼀下，Union-Find 算法解决的是图的动态连通性问题，这个算法本⾝不难，能不能应⽤出来主要是看你抽象问题的能⼒，是否能够把原始问题抽象成⼀个有关图论的问题。
先复习⼀下上篇⽂章写的算法代码，回答读者提出的⼏个问题：
class UF {
// 记录连通分量个数
private int count;
// 存储若⼲棵树
private int[] parent;
// 记录树的“重量”
private int[] size;
public UF(int n) {
this.count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
/* 将 p 和 q 连通 */
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// ⼩树接到⼤树下⾯，较平衡
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
/* 判断 p 和 q 是否互相连通 */
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
// 处于同⼀棵树上的节点，相互连通
return rootP == rootQ;
}
/* 返回节点 x 的根节点 */
private int find(int x) {
while (parent[x] != x) {
// 进⾏路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int count() {
return count;
}
}算法的关键点有 3 个：
1、⽤ parent 数组记录每个节点的⽗节点，相当于指向⽗节点的指针，所
以 parent 数组内实际存储着⼀个森林（若⼲棵多叉树）。
2、⽤ size 数组记录着每棵树的重量，⽬的是让 union 后树依然拥有平衡性，⽽不会退化成链表，影响操作效率。
3、在 find 函数中进⾏路径压缩，保证任意树的⾼度保持在常数，使得union 和 connected API 时间复杂度为 O(1)。
有的读者问，既然有了路径压缩， size 数组的重量平衡还需要吗？这个问题很有意思，因为路径压缩保证了树⾼为常数（不超过 3），那么树就算不平衡，⾼度也是常数，基本没什么影响。我认为，论时间复杂度的话，确实，不需要重量平衡也是 O(1)。但是如果加上 size 数组辅助，效率还是略微⾼⼀些，⽐如下⾯这种情况：如果带有重量平衡优化，⼀定会得到情况⼀，⽽不带重量优化，可能出现情
况⼆。⾼度为 3 时才会触发路径压缩那个 while 循环，所以情况⼀根本不会触发路径压缩，⽽情况⼆会多执⾏很多次路径压缩，将第三层节点压缩到第⼆层。也就是说，去掉重量平衡，虽然对于单个的 find 函数调⽤，时间复杂度依然是 O(1)，但是对于 API 调⽤的整个过程，效率会有⼀定的下降。当然，好处就是减少了⼀些空间，不过对于 Big O 表⽰法来说，时空复杂度都没变。下⾯⾔归正传，来看看这个算法有什么实际应⽤。
if (board.length == 0) return;
int m = board.length;
int n = board[0].length;
// 给 dummy 留⼀个额外位置
UF uf = new UF(m * n + 1);
int dummy = m * n;
// 将⾸列和末列的 O 与 dummy 连通
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O')
uf.union(i * n, dummy);
if (board[i][n - 1] == 'O')
uf.union(i * n + n - 1, dummy);
}
// 将⾸⾏和末⾏的 O 与 dummy 连通
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O')
uf.union(j, dummy);
if (board[m - 1][j] == 'O')
uf.union(n * (m - 1) + j, dummy);
}
// ⽅向数组 d 是上下左右搜索的常⽤⼿法
int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}};
for (int i = 1; i < m - 1; i++)
for (int j = 1; j < n - 1; j++)
if (board[i][j] == 'O')
// 将此 O 与上下左右的 O 连通
for (int k = 0; k < 4; k++) {
int x = i + d[k][0];
int y = j + d[k][1];
if (board[x][y] == 'O')
uf.union(x * n + y, i * n + j);
}
// 所有不和 dummy 连通的 O，都要被替换
for (int i = 1; i < m - 1; i++)
for (int j = 1; j < n - 1; j++)
if (!uf.connected(dummy, i * n + j))
board[i][j] = 'X';
}这段代码很⻓，其实就是刚才的思路实现，只有和边界 O 相连的 O 才具有和 dummy 的连通性，他们不会被替换。
说实话，Union-Find 算法解决这个简单的问题有点杀鸡⽤⽜⼑，它可以解决更复杂，更具有技巧性的问题，主要思路是适时增加虚拟节点，想办法让元素「分门别类」，建⽴动态连通关系。
⼆、判定合法等式
这个问题⽤ Union-Find 算法就显得⼗分优美了。题⽬是这样：给你⼀个数组 equations ，装着若⼲字符串表⽰的算式。每个算式equations[i] ⻓度都是 4，⽽且只有这两种情况： ab 或者 a!=b ，其中 a,b 可以是任意⼩写字⺟。你写⼀个算法，如果 equations 中所有算式都不会互相冲突，返回 true，否则返回 false。⽐如说，输⼊ ["ab",“b!=c”,“c==a”] ，算法返回 false，因为这三个算式不可能同时正确。
再⽐如，输⼊ [“cc","bd”,“x!=z”] ，算法返回 true，因为这三个算式并不会造成逻辑冲突。
我们前⽂说过，动态连通性其实就是⼀种等价关系，具有「⾃反性」「传递性」和「对称性」，其实 == 关系也是⼀种等价关系，具有这些性质。所以这个问题⽤ Union-Find 算法就很⾃然。核⼼思想是，将 equations 中的算式根据 == 和 != 分成两部分，先处理== 算式，使得他们通过相等关系各⾃勾结成门派；然后处理 != 算式，
检查不等关系是否破坏了相等关系的连通性。
boolean equationsPossible(String[] equations) {
// 26 个英⽂字⺟
UF uf = new UF(26);
// 先让相等的字⺟形成连通分量
for (String eq : equations) {
if (eq.charAt(1) == '=') {
char x = eq.charAt(0);
char y = eq.charAt(3);
uf.union(x - 'a', y - 'a');
}17.⼀⾏代码就能解决的算法题
下⽂是我在 LeetCode 刷题过程中总结的三道有趣的「脑筋急转弯」题⽬，可以使⽤算法编程解决，但只要稍加思考，就能找到规律，直接想出答案。
⼀、Nim 游戏
游戏规则是这样的：你和你的朋友⾯前有⼀堆⽯⼦，你们轮流拿，⼀次⾄少拿⼀颗，最多拿三颗，谁拿⾛最后⼀颗⽯⼦谁获胜。
假设你们都很聪明，由你第⼀个开始拿，请你写⼀个算法，输⼊⼀个正整数n，返回你是否能赢（true 或 false）。⽐如现在有 4 颗⽯⼦，算法应该返回 false。因为⽆论你拿 1 颗 2 颗还是 3颗，对⽅都能⼀次性拿完，拿⾛最后⼀颗⽯⼦，所以你⼀定会输。⾸先，这道题肯定可以使⽤动态规划，因为显然原问题存在⼦问题，且⼦问题存在重复。但是因为你们都很聪明，涉及到你和对⼿的博弈，动态规划会较复杂。
我们解决这种问题的思路⼀般都是反着思考：
如果我能赢，那么最后轮到我取⽯⼦的时候必须要剩下 1~3 颗⽯⼦，这样我才能⼀把拿完。
如何营造这样的⼀个局⾯呢？显然，如果对⼿拿的时候只剩 4 颗⽯⼦，那么⽆论他怎么拿，总会剩下 1~3 颗⽯⼦，我就能赢。如何逼迫对⼿⾯对 4 颗⽯⼦呢？要想办法，让我选择的时候还有 5~7 颗⽯
⼦，这样的话我就有把握让对⽅不得不⾯对 4 颗⽯⼦。
如何营造 5~7 颗⽯⼦的局⾯呢？让对⼿⾯对 8 颗⽯⼦，⽆论他怎么拿，都会给我剩下 5~7 颗，我就能赢。
⼀⾏代码就能解决的算法题
20这样⼀直循环下去，我们发现只要踩到 4 的倍数，就落⼊了圈套，永远逃不出 4 的倍数，⽽且⼀定会输。所以这道题的解法⾮常简单：
···
bool canWinNim(int n) {
/
/ 如果上来就踩到 4 的倍数，那就认输吧
/ 否则，可以把对⽅控制在 4 的倍数，必胜
/
return n % 4 != 0;
}
···
⼆、⽯头游戏
游戏规则是这样的：你和你的朋友⾯前有⼀排⽯头堆，⽤⼀个数组 piles 表⽰，piles[i] 表⽰第 i 堆⽯⼦有多少个。你们轮流拿⽯头，⼀次拿⼀堆，但是只能拿⾛最左边或者最右边的⽯头堆。所有⽯头被拿完后，谁拥有的⽯头多，谁获胜。
假设你们都很聪明，由你第⼀个开始拿，请你写⼀个算法，输⼊⼀个数组piles，返回你是否能赢（true 或 false）。
注意，⽯头的堆的数量为偶数，所以你们两⼈拿⾛的堆数⼀定是相同的。⽯头的总数为奇数，也就是你们最后不可能拥有相同多的⽯头，⼀定有胜负之分。
举个例⼦， piles=[2, 1, 9, 5] ，你先拿，可以拿 2 或者 5，你选择 2。
piles=[1, 9, 5] ，轮到对⼿，可以拿 1 或 5，他选择 5。
piles=[1, 9] 轮到你拿，你拿 9。
最后，你的对⼿只能拿 1 了。
这样下来，你总共拥有 2 + 9 = 11 颗⽯头，对⼿有 5 + 1 = 6 颗⽯头，你是可以赢的，所以算法应该返回 true。你看到了，并不是简单的挑数字⼤的选，为什么第⼀次选择 2 ⽽不是 5 呢？
因为 5 后⾯是 9，你要是贪图⼀时的利益，就把 9 这堆⽯头暴露给对⼿了，那你就要输了。
这也是强调双⽅都很聪明的原因，算法也是求最优决策过程下你是否能赢。这道题⼜涉及到两⼈的博弈，也可以⽤动态规划算法暴⼒试，⽐较⿇烦。但我们只要对规则深⼊思考，就会⼤惊失⾊：只要你⾜够聪明，你是必胜⽆疑的，因为你是先⼿。
boolean stoneGame(int[] piles) {
return true;
}这是为什么呢，因为题⽬有两个条件很重要：⼀是⽯头总共有偶数堆，⽯头的总数是奇数。这两个看似增加游戏公平性的条件，反⽽使该游戏成为了⼀个割⾲菜游戏。我们以 piles=[2, 1, 9, 5] 讲解，假设这四堆⽯头从左到右的索引分别是 1，2，3，4。如果我们把这四堆⽯头按索引的奇偶分为两组，即第 1、3 堆和第 2、4 堆，那么这两组⽯头的数量⼀定不同，也就是说⼀堆多⼀堆少。因为⽯头的总数是奇数，不能被平分。
⽽作为第⼀个拿⽯头的⼈，你可以控制⾃⼰拿到所有偶数堆，或者所有的奇数堆。
你最开始可以选择第 1 堆或第 4 堆。如果你想要偶数堆，你就拿第 4 堆，这样留给对⼿的选择只有第 1、3 堆，他不管怎么拿，第 2 堆⼜会暴露出来，你就可以拿。同理，如果你想拿奇数堆，你就拿第 1 堆，留给对⼿的只有第2、4 堆，他不管怎么拿，第 3 堆⼜给你暴露出来了。
也就是说，你可以在第⼀步就观察好，奇数堆的⽯头总数多，还是偶数堆的⽯头总数多，然后步步为营，就⼀切尽在掌控之中了。知道了这个漏洞，可以整⼀整不知情的同学了。
三、电灯开关问题
这个问题是这样描述的：有 n 盏电灯，最开始时都是关着的。现在要进⾏ n轮操作：
第 1 轮操作是把每⼀盏电灯的开关按⼀下（全部打开）。
第 2 轮操作是把每两盏灯的开关按⼀下（就是按第 2，4，6… 盏灯的开关，它们被关闭）。
第 3 轮操作是把每三盏灯的开关按⼀下（就是按第 3，6，9… 盏灯的开关，有的被关闭，⽐如 3，有的被打开，⽐如 6）…
如此往复，直到第 n 轮，即只按⼀下第 n 盏灯的开关。现在给你输⼊⼀个正整数 n 代表电灯的个数，问你经过 n 轮操作后，这些电灯有多少盏是亮的？
我们当然可以⽤⼀个布尔数组表⽰这些灯的开关情况，然后模拟这些操作过程，最后去数⼀下就能出结果。但是这样显得没有灵性，最好的解法是这样的：
int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}什么？这个问题跟平⽅根有什么关系？其实这个解法挺精妙，如果没⼈告诉你解法，还真不好想明⽩。
⾸先，因为电灯⼀开始都是关闭的，所以某⼀盏灯最后如果是点亮的，必然
要被按奇数次开关。
我们假设只有 6 盏灯，⽽且我们只看第 6 盏灯。需要进⾏ 6 轮操作对吧，请问对于第 6 盏灯，会被按下⼏次开关呢？这不难得出，第 1 轮会被按，第 2轮，第 3 轮，第 6 轮都会被按。
为什么第 1、2、3、6 轮会被按呢？因为 6=16=23 。⼀般情况下，因⼦都是成对出现的，也就是说开关被按的次数⼀般是偶数次。但是有特殊情况，⽐如说总共有 16 盏灯，那么第 16 盏灯会被按⼏次?
16=116=28=4*4
其中因⼦ 4 重复出现，所以第 16 盏灯会被按 5 次，奇数次。现在你应该理解这个问题为什么和平⽅根有关了吧？
不过，我们不是要算最后有⼏盏灯亮着吗，这样直接平⽅根⼀下是啥意思呢？稍微思考⼀下就能理解了。
就假设现在总共有 16 盏灯，我们求 16 的平⽅根，等于 4，这就说明最后会有 4 盏灯亮着，它们分别是第 11=1 盏、第 22=4 盏、第 33=9 盏和第44=16 盏。
就算有的 n 平⽅根结果是⼩数，强转成 int 型，也相当于⼀个最⼤整数上界，⽐这个上界⼩的所有整数，平⽅后的索引都是最后亮着的灯的索引。所以说我们直接把平⽅根转成整数，就是这个问题的答案。
18.⼆分查找⾼效判定⼦序列
⼆分查找本⾝不难理解，难在巧妙地运⽤⼆分查找技巧。对于⼀个问题，你可能都很难想到它跟⼆分查找有关，⽐如前⽂ 最⻓递增⼦序列 就借助⼀个纸牌游戏衍⽣出⼆分查找解法。
今天再讲⼀道巧⽤⼆分查找的算法问题：如何判定字符串 s 是否是字符串t 的⼦序列（可以假定 s ⻓度⽐较⼩，且 t 的⻓度⾮常⼤）。举两个例⼦：
s = “abc”, t = “ahbgdc”, return true.
s = “axc”, t = “ahbgdc”, return false.
题⽬很容易理解，⽽且看起来很简单，但很难想到这个问题跟⼆分查找有关吧？
⼀、问题分析
首先，⼀个很简单的解法是这样的：
bool isSubsequence(string s, string t) {
int i = 0, j = 0;
while (i < s.size() && j < t.size()) {
if (s[i] == t[j]) i++;
j++;
}
return i == s.size();
}其思路也⾮常简单，利⽤双指针 i, j 分别指向 s, t ，⼀边前进⼀边匹配⼦序列：
读者也许会问，这不就是最优解法了吗，时间复杂度只需 O(N)，N 为 t的⻓度。
是的，如果仅仅是这个问题，这个解法就够好了，不过这个问题还有 followup：
如果给你⼀系列字符串 s1,s2,… 和字符串 t ，你需要判定每个串 s 是否是 t 的⼦序列（可以假定 s 较短， t 很⻓）。
isSubsequence(String[] sn, String t);``` 你也许会问，这不是很简单吗，还是刚才的逻辑，加个 for 循环不就⾏了？可以，但是此解法处理每个 s 时间复杂度仍然是 O(N)，⽽如果巧妙运⽤⼆分查找，可以将时间复杂度降低，⼤约是 O(MlogN)。由于 N 相对 M ⼤很多，所以后者效率会更⾼。 ## ⼆、⼆分思路 ⼆分思路主要是对 t 进⾏预处理，⽤⼀个字典 index 将每个字符出现的 索引位置按顺序存储下来：
int m = s.length(), n = t.length();
ArrayList
// 先记下 t 中每个字符出现的位置
for (int i = 0; i < n; i++) {
char c = t.charAt(i);
if (index[c] == null)
index[c] = new ArrayList<>();
index[c].add(i);
}
⽐如对于这个情况，匹配了 "ab"，应该匹配 "c" 了：
按照之前的解法，我们需要 j 线性前进扫描字符 "c"，但借助 index 中记录的信息，可以⼆分搜索 index[c] 中⽐ j ⼤的那个索引，在上图的例⼦中，就是在 [0,2,6] 中搜索⽐ 4 ⼤的那个索引：
这样就可以直接得到下⼀个 "c" 的索引。现在的问题就是，如何⽤⼆分查找计算那个恰好⽐ 4 ⼤的索引呢？答案是，寻找左侧边界的⼆分搜索就可以做到。
## 三、再谈⼆分查找
在前⽂ ⼆分查找详解 中，详解了如何正确写出三种⼆分查找算法的细节。
⼆分查找返回⽬标值 val 的索引，对于搜索左侧边界的⼆分查找，有⼀个特殊性质：
当 val 不存在时，得到的索引恰好是⽐ val ⼤的最⼩元素索引。
什么意思呢，就是说如果在数组 [0,1,3,4] 中搜索元素 2，算法会返回索
引 2，也就是元素 3 的位置，元素 3 是数组中⼤于 2 的最⼩元素。所以我们
可以利⽤⼆分搜索避免线性扫描。// 查找左侧边界的⼆分查找
int left_bound(ArrayList
int lo = 0, hi = arr.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (tar > arr.get(mid)) {
lo = mid + 1;
}
else {
hi = mid;
}
}
return lo;
}
以上就是搜索左侧边界的⼆分查找，等会⼉会⽤到，其中的细节可以参⻅前
⽂《⼆分查找详解》，这⾥不再赘述。
## 四、代码实现
这⾥以单个字符串 s 为例，对于多个字符串 s ，可以把预处理部分抽出来。
boolean isSubsequence(String s, String t) {
int m = s.length(), n = t.length();
// 对 t 进⾏预处理
ArrayList
for (int i = 0; i < n; i++) {
char c = t.charAt(i);
if (index[c] == null)
index[c] = new ArrayList<>();
index[c].add(i);
}
/
/ 串 t 上的指针
int j = 0;
/ 借助 index 查找 s[i]
/
for (int i = 0; i < m; i++) {
char c = s.charAt(i);
// 整个 t 压根⼉没有字符 c
if (index[c] == null) return false;
int pos = left_bound(index[c], j);
/
/ ⼆分搜索区间中没有找到字符 c
if (pos == index[c].size()) return false;
/ 向前移动指针 j
/
j = index[c].get(pos) + 1;
}
return true;
}
可⻅借助⼆分查找，算法的效率是可以⼤幅提升的。
# Android Framework方面
# 系统启动流程面试题解析
A： 当 按 电 源 键 触 发 开 机 ， 首 先 会 从 ROM 中 预 定 义 的 地 方 加 载 引 导 程 序 BootLoader 到 RAM 中 ， 并执 行 BootLoader 程 序 启 动 Linux Kernel， 然 后启 动 用户 级 别的 第 一个 进 程： init 进 程。 init 进程 会解 析 init.rc 脚 本 做一些初始化工作，包括挂载文件系统、创建工作目录以及启动系统服务进程等，其中系统服务进程包括进 程 ， 然 后 在Zygote、service manager、media 等 。在 Zygote 中 会 进 一 步 去 启 动 system_ server,system_server 进 程 中 会 启 动 AMS、WMS、PMS 等 服 务 ，等 这 些 服 务 启 动 之后 ，AMS 中 就 会 打 开 Launcher 应 用 的 home Activity， 最 终 就 看 到 了 手 机 的 "桌 面 "。
A： Zygote 作 为一 个 孵化 器 ，可 以提 前 加载 一 些资 源 ，这 样 fork() 时 基于 Copy-On-Write 机 制创 建 的其 他 进程 就能 直 接 使用 这 些资 源 ，而 不 用重 新 加载 。 比 如 system_server 就 可以 直 接使 用 Zygote 中 的 JNI 函 数、共 享库 、 常用 的类、 以及主题资源。
A： 首 先 system_server 相 比 Zygote 多 运 行 了 AMS、 WMS 等 服 务 ， 这 些 对 一 个 应 用 程 序 来 说 是 不 需 要的 。 另 外 进 程 的 fork() 对多线程不友好，仅会将发起调用的线程拷贝到子进程，这可能会导致死锁，而system_server 中肯定 是 有 很 多 线 程 的 。
在POSIX 标准中，fork 的行为是这样的：复制整个用户空间的数据 (通常使用 copy-on-write 的策略，
所以可以 实 现 的速度很快) 以及所有系统对象，然后仅复制当前线程到子进程。这里：所有父进程中别 的线程，到了子进程 中 都 是 突 然 蒸 发 掉 的对 于 锁 来说，从 OS 看，每个锁有一个所有者，即最后一次 lock 它的线程。假设这么一个环境，在 fork 之前，有 一 个 子 线程 lock 了某个锁，获得了对锁的所有权。fork 以后，在子进程中，所有的额外线程都人间蒸发了。而锁却被正常复制了，在子进程看来，这个锁没有主人，所以没有任何人可以对它解锁。
当子进程想 lock 这个锁时，不再 有 任 何 手 段 可 以 解 开 了 。 程 序 发 生 死 锁
A： Binder 机 制 中 存 在 Binder 线 程 池 ， 是 多 线 程 的 ， 如 果 Zygote 采 用 Binder 的 话 就 存 在 上 面 说 的fork() 多 线 程 的 问 题 了 。 其 实 严 格 来 说 ， Binder 机 制 不 一 定 要 多 线 程 ， 所 谓 的 Binder 线 程 只 不 过 是 在与循 环 读 取 Binder 驱 动 的 消 息 而 已 ， 只 注 册 一 个 Binder 线 程 也 是 可 以 工 作 的 ， 比 如 service manager 就是 这 样 的 。实 际 上 Zygote 尽 管 没 有 采 取 Binder 机 制 ，它 也 不 是 单 线 程 的 ，但 它 在 fork() 前 主 动 停 止 了其 他 线 程 ， fork() 后 重 新 启动了。
# Binder面试题解析
Binder是一种进程间通信机制，做 Android 开发肯定离不开跟 Binder 打交道。
在 面 试 中Binder也是经常被问的一个点，那么本篇文章就以问答的方式，带你了解一下关
于 Binder 的重要知识点。
共享内存 0次数据拷贝
Binder 1次数据拷贝
Socket/管道/消息队列 2次数据拷贝
Binder：基于C/S架构，客户端 (Client) 有什么需求就丢给服务端 (Server) 去完成，架构清晰、职责明确又相互独立，自然稳定性更好
共享内存：虽然无需拷贝，但是控制复杂，难以使用从稳定性的角度讲，Binder机制是优于内存共享的。
传统的IPC没有任何安全措施，安全依赖上层协议来确保。
传统的IPC方法无法获得对方可靠的进程用户ID/进程UI (UID/PID) ，从而无法鉴别对方身份。
传统的IPC只能由用户在数据包中填入UID/PID，容易被恶意程序利用。
传统的IPC访问接入点是开放的，无法阻止恶意程序通过猜测接收方地址获得连接。
Binder既支持实名Binder，又支持匿名Binder，安全性高。
主要是因为Linux是使用的虚拟内存寻址方式，它有如下特性：
用户空间的虚拟内存地址是映射到物理内存中的
对虚拟内存的读写实际上是对物理内存的读写，这个过程就是内存映射，这个内存映射过程是通过系统调用mmap()来实现的MMAP内存映射的实现过程，总的来说可以分为三个阶段：
1. 进程在用户空间调用库函数mmap，原型：void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
2. 在当前进程的虚拟地址空间中，寻找一段空闲的满足要求的连续的虚拟地址
3. 为此虚拟区分配一个vm_area_struct结构，接着对这个结构的各个域进行了初始化
4. 将新建的虚拟区结构 (vm_area_struct) 插入进程的虚拟地址区域链表或树中
5. 为映射分配了新的虚拟地址区域后，通过待映射的文件指针，在文件描述符表中找到对应的文件描 述
符，通过文件描述符，链接到内核“已打开文件集”中该文件的文件结构体 (struct file) ， 每个
文件结构体维护着和这个已打开文件相关各项信息。
6. 通过该文件的文件结构体，链接到file_operations模块，调用内核函数mmap，其原型为： int
mmap(struct file *filp, struct vm_area_struct *vma)，不同于用户空间库 函数。
7. 内核mmap函数通过虚拟文件系统inode模块定位到文件磁盘物理地址。
8. 通过remap_pfn_range函数建立页表，即实现了文件地址和虚拟地址区域的映射关系。此时，这 片
虚拟地址并没有任何数据关联到主存中。
注：前两个阶段仅在于创建虚拟区间并完成地址映射，但是并没有将任何文件数据的拷贝至主存。 真正的文件读取是当进程发起读或写操作时。
进程的读或写操作访问虚拟地址空间这一段映射地址，通过查询页表，发现这一段地址并不在物 理 页 面 上。因为目前只建立了地址映射，真正的硬盘数据还没有拷贝到内存中，因此引发缺页异 常。
1. 缺页异常进行一系列判断，确定无非法操作后，内核发起请求调页过程。
2. 调页过程先在交换缓存空间 (swap cache) 中寻找需要访问的内存页，如果没有则调用nopage 函
数把所缺的页从磁盘装入到主存中。
3. 之后进程即可对这片主存进行读或者写的操作，如果写操作改变了其内容，一定时间后系统会自动 回
写脏页面到对应磁盘地址，也即完成了写入到文件的过程。
注 ：修改过的脏页面并不会立即更新回文件中，而是有一段时间的延迟，可以调用msync()来强 制同步 , 这样所写的内容就能立即保存到文件里了。
1. Binder驱动
在内核空间创建一块接收缓存区，
实现地址映射：将内核缓存区、接收进程用户空间映射到同一接收缓存区
2. 发送进程通过系统调用 (copy_from_user) 将数据发送到内核缓存区。由于内核缓存区和
接收进程用户空间存在映射关系，故相当于也发送了接收进程的用户空间，实现了跨进程通信。
(1) 一个Activity通常就是一个单独的屏幕 (窗口) 。
(2) Activity之 间 通 过 Intent进 行 通 信 。
(3) android应 用 中 每 一 个 Activity都 必 须 要 在 AndroidManifest.xml配 置 文 件 中 声 明 ， 否则系统将不识别也不执行该Activity。
(1) service用于在后台完成用户指定的操作。service分为两种：
started (启动) ：当应用程序组件 (如activity) 调用startService()方法启动服务时，服务处于started状态。
bound (绑定) ：当应用程序组件调用bindService()方法绑定到服务时，服务处于bound状态。
(2) startService() 与 bindService() 区 别 ：
started service (启动服务) 是由其他组件调用startService()方法启动的，这导致服务的onStartCommand()方法被调用。当服务是started状态时，其生命周期与启动它的组件无 关，
并且可以在后台无限期运行，即使启动服务的组件已经被销毁。因此，服务需要在完成任务后 调用stopSelf()方法停止，或者由其他组件调用stopService()方法停止。
使用bindService()方法启用服务，调用者与服务绑定在了一起，调用者一旦退出，服务也就终
止，大有“不求同时生，必须同时死”的特点。
(3)开发人员需要在应用程序配置文件中声明全部的service，使用<service></service>标 签。
(4)Service通常位于后台运行，它一般不需要与用户交互，因此Service组件没有图形用户界
面。Service组件 需要 继承 Service基类 。Service组件 通常 用于 为其 他组 件提 供后 台服 务或 监控其他组件的运行状态。
(1) android平 台 提 供 了 Content Provider使一个应用程序的指定数据集提供给其他应用程
序 。 其他应用可以通过ContentResolver类从该内容提供者中获取或存入数据。
(2) 只有需要在多个应用程序间共享数据是才需要内容提供者。例如，通讯录数据被多个应用 程 序使用，且必须存储在一个内容提供者中。它的好处是统一数据访问方式。
(3) ContentProvider实 现 数 据 共 享 。 ContentProvider用 于 保 存 和 获 取 数 据 ， 并 使 其 对 所有应用程序可见。这是不同应用程序间共享数据的唯一方式，因为android没有提供所有应用共同访问的公共存储区。
(4) 开 发 人 员 不 会 直 接 使 用 ContentProvider类 的 对 象 ， 大 多 数 是 通 过 ContentResolver对 象 实现 对 ContentProvider的 操 作。
(5) ContentProvider使 用 URI来 唯 一 标 识 其 数 据 集 ， 这 里 的 URI以 content://作 为 前 缀 ， 表示 该 数 据 由 ContentProvider来 管 理 。
(1) 你的应用可以使用它对外部事件进行过滤，只对感兴趣的外部事件(如当电话呼入时，或
者 数 据 网络可用时)进行接收并做出响应。广播接收器没有用户界面。然而，它们可以启动一个
activity或 serice来 响 应它 们 收 到 的 信息 ，或 者 用 NotificationManager来 通 知用 户 。通知 可 以用很多种方式来吸引用户的注意力，例如闪动背灯、震动、播放声音等。一般来说是在状 态栏上放一个持久的图标，用户可以打开它并获取消息。
(2) 广播接收者的注册有两种方法，分别是程序动态注册和AndroidManifest文件中进行
静 态注册。
(3) 动态注册广播接收器特点是当用来注册的Activity关掉后，广播也就失效了。静态注册无
需 担 忧广播接收器是否被关闭，只要设备是开启状态，广播接收器也是打开着的。也就是说哪
怕 app本 身未启动，该app订阅的广播在触发时也会对它起作用。
Intent携 带信息的大小其实是受Binder限制。数据以Parcel对象的形式存放在Binder传递缓
存中。如果数据或返回值比传递buffer大，则此次传递调用失败并抛出TransactionTooLargeException异 常 。
Binder传 递 缓存有一个限定大小，通常是1Mb。但同一个进程中所有的传输共享缓存空间。多
个 地 方在进行传输时，即时它们各自传输的数据不超出大小限制，TransactionTooLargeException异 常 也 可 能 会 被 抛 出 。在 使 用 Intent传 递 数 据 时 ，1 Mb并 不是安全上限。因为Binder中可能正在处理其它的传输工作。不同的机型和系统版本，这个上 限值也可能会不同。
# Handler面 试 题 解 析
作 为一 个 Android开 发，Handler机 制是 一 定要 了 解的 。在 我面 试 过程 中 ，发 现很 多 人对 Handler和 Looper机 制非 常 了解 ，对
答 如流 ， 但 是 却 不 知 道 何 为 HandlerThread
1)方便使用：a. 方便初始化，b，方便获取线程looper
2) 保证了线程安全
我 们 一 般在 Thread里 面 线 程 Looper进 行初 始 化的 代 码里 面 ，必 须 要对 Looper.prepare(),同 时要 调 用Loop。loop ()；@Override
void run() {
Looper.prepare();
Looper.loop();
而我们要使用子线程中的Looper的方式是怎样的呢？看下面的代码
Thread thread = Looper looper;
Thread(
Runnable() {
@Override
void run() {
Log.d(TAG, "click2: " + Thread.cu entThread().getName( ;
Looper.prepare();
looper =Looper.myLooper();
Looper.loop();
}
}
Looper getLooper() {
looper;
}
);
thread.start();
Handler handler =
Handler(thread.getLooper());
1) 在初始化子线程的handler的时候，我们无法将子线程的looper传值给Handler,解决办法有如下办法：
a. 可 以 将 Handler的 初 始 化 放 到 Thread里 面 进 行
b. 可以创建一个独立的类继承Thread，然后，通过类的对象获
取。 这 两 种办 法 都可 以 ，但 是 ，这 个工 作 HandlerThread帮 我们 完成 了
2) 依据多线程的工作原理，我们在上面的代码中，调用 thread.getLooper () 的时候，此时的looper可能还没有初始化，
此时是 不是可能会挂掉呢？
HandlerThread 已 经 帮 我 们 完 美 的 解 决 了 ， 这 就 是 handlerThread存 在 的 必要 性 了 。void run() {
mTid = Process.myTid();
Looper.prepare();
mLooper = Looper.myLooper();
notifyAll(); 此时唤醒其他等待的锁，但是
}
Process.setThreadPriority(mPriority);
onLooperPrepared();
Looper.loop();
mTid = -1;
}
它 的 优点就在于它的多线程操作，可以帮我们保证使用Thread的handler时一定是安全的。
1.Looper 准备和开启轮循：
Looper#prepare() 初 始 化 线 程 独 有 的 Looper 以 及 MessageQueue Looper#loop() 开 启 死 循 环 读 取 MessageQueue 中下 一 个 满 足 执 行 时 间 的 Message 尚 无 Message 的 话， 调 用 Native 侧 的 pollOnce() 进 入无 限 等待 存 在 Message，
但 执行 时 间 when 尚 未满 足的话，调用 pollOnce() 时传入剩余时长参数进入有限等待
1. Message 发送、入队和出队：
Native 侧 如 果 处 于 无 限 等 待 的 话 ： 任 意 线 程 向 Handler 发 送 Message 或 Runnable 后 ， Message 将 按 照 when 条 件的 先 后 ， 被 插 入 Handler 持 有的 Looper 实 例所 对 应的 MessageQueue 中 适当 的 位置 。 MessageQueue 发 现有 合 适的Message 插 入后 将 调用Native 侧 的 wake() 唤 醒无 限 等待 的 线程 。 这将 促 使 MessageQueue 的 读取 继 续进 入 下一次 循环 ， 此刻 Queue 中 已有 满 足条 件的 Message 则 出 队返 回 给 Looper Native 侧 如果 处 于有 限 等待 的 话： 在 等待 指 定时 长后 epoll_wait 将 返回 。 线程 继 续读 取
Message 的 实 现 ：
MessageQueue， 此 刻 因 为 时 长 条 件 将 满 足 将 其 出 队 Looper 处 理
1. Looper 得到 Message 后回调 Message 的 callback 属性即 Runnable，或依据 target 属性即 Handler，去执行 Handler 的回调。
存 在 mCallback 属 性 的 话 回 调 Handler$Callback 反 之 ， 回 调 handleMessage()
Looper 实 例 被 管 理 在 静 态 属 性 sThreadLocal中 ThreadLocal 内 部 通 过 ThreadLocalMap 持 有 Looper， key 为ThreadLocal 例 本 身 ，value 即 为 Looper 实 例 每 个 Thread 都 有 一 个 自 己 的 ThreadLocalMap，这 样 可 以 保 证 每 个 线
实程 对 应 一 个 独 立 的 Looper 实 例 ，进 而保 证 myLooper() 可 以获 得 线程 独 有的 Looper 彩 蛋：
一 个 App 拥 有几 个 Looper实 例？
几 个 ThreadLocal 实 例？ 几 个 MessageQueue 实 例 ？ 几 个 Message 实 例 ？ 几 个 Handler 实 例
一 个 线 程 只 有 一 个 Looper 实 例 一 个 Looper 实 例 只 对 应 着 一 个 MessageQueue 实 例
一 个 MessageQueue 实 例 可 对应 多 个Message 实 例 ，其从 Message 静态池里获取，存在 50 的上限 一个线程可以拥有多个 Handler 实例，其Handler 只是发送和执行 任 务 逻 辑 的入 口 和出 口 ThreadLocal 实 例是 静 态的 ， 整个 进 程共 用 一个 实 例。 每 个 Looper 存
放 的 ThreadLocalMap 均 弱引 用 它作 为 key
首先要明确并非不是用来切换线程的，只是为了让每个线程方便程获取自己的 Looper 实例，见 Looper#myLooper()
后续可供 Handler 初始化时指定其所属的 Looper 线程 也可用来线程判断自己是否是主线程
区别：
Main Looper 不可 quit 主线程需要不断读取系统消息和用书输入，是进程的入口，只可被系统直接终止。进而其 Looper在创建 的 时 候 设置了不可 quit 的标志，而其他线程的 Looper 则可以也必须手动 quit Main Looper 实 例 还 被 静 态 缓 存 为 了 便 于 每 个 线 程 获 得 主 线 程 Looper 实 例 ， 见 Looper#getMainLooper()， Main Looper 实 例 还 作 为 sMainLooper 属 性 缓 存 到 了 Looper 类 中 。
相同点：
都 是通 过 Looper#prepare() 间 接调 用 Looper 构 造函 数 创建 的 实例 都 被静 态 实例 ThreadLocal 管 理， 方 便每 个 线程 获取 自己 的 Looper 实例 彩蛋：主线程为什么不用初始化 Looper？
App 的 入 口 并 非 MainActivity， 也 不 是 Application， 而 是 ActivityThread。
其 为 了 Application、 ContentProvider、 Activity 等 组 件 的 运 行 ， 必 须 事 先 启 动 不 停 接 受 输 入 的 Looper 机 制 ， 所 以 在main()执 行 的 最后 将 调用 prepareMainLooper() 创 建 Looper 并 调用 loop() 轮 循。
不需要我们调用，也不可能有我们调用。
可以说如果主线程没有创建 Looper 的话，我们的组件也不可能运行得到！
Handler 创 建 的 时 候 指 定 了 其 所 属 线 程 的 Looper， 进 而 持 有 了 Looper 独 有 的 MessageQueue Looper# loop() 会 持 续 读 取 MessageQueue 中 合 适 的Message， 没 有 Message 的 时 候 进 入 等 待当 向 Handler 发 送 Message 或 Runnable 后 ， 会 向 持 有 的 MessageQueue 中 插 入 Message Message 抵 达 并 满 足 条 件 后 会 唤 醒 MessageQueue 所 属 的 线 程 ， 并 将 Message 返 回 给 Looper Looper 接 着 回 调 Message 所 指 向 的 Handler Callback 或 Runnable， 达 到 线 程 切 换 的 目 的
简 言 之 ，向 Handler 发 送 Message 其 实 是 向 Handler 所 属 线 程 的 独 有 MessageQueue 插 入 Message。而 线 程 独 有 的Looper 又 会 持 续 读 取 该 MessageQueue。所 以 向 其 他 线 程 的 Handler 发 送 完 Message，该 线 程 的 Looper 将 自 动 响 应 。
为 了让 主 线程 持 续处 理 用户 的 输入 ， loop() 是 死循 环 ，持 续 调用 MessageQueue#next() 读 取合 适 的 Message。
但 当 没有 Message 的 时候 ， 会调 用 pollOnce() 并 通过 Linux 的 epoll 机 制进 入 等待 并 释放 资 源。 同 时 eventFd 会 监听 Message 抵达的写入事件并进行唤醒。
这 样 可以空闲时释放资源、不卡死线程，同时能持续接收输入的目的。
彩 蛋1：loop() 后的处理为什么不可执行
因 为 loop() 是死循环，直到 quit 前后面的处理无法得到执行，所以避免将处理放在 loop() 的后面。
调 用 Linux 的 epoll 机制进入等待，事实上 Java 侧打印该线程的状态，你会发现线程处于 Runnable 状态，只不过 CPU资源被 暂时释放。
读 取 合适 Message 的 MessageQueue#next() 会因为 Message 尚无或执行条件尚未满足进行两种等的等待： 无限等待尚 无 Message (队列中没有 Message 或建立了同步屏障但尚无异步 Message) 的时候，会调用 Natvie 侧的 pollOnce()传入参数 -1。
Linux 执 行 epoll_wait() 将进入无限等待，其等待合适的 Message 插入后调用 Native 侧的 wake() 向唤醒 fd 写入事件 触发唤 醒 MessageQueue 读 取 的 下 一 次 循 环
有限等待
有 限 等待的场合将下一个 Message 剩余时长作为参数交给 epoll_wait()，epoll 将等待一段时间之后自动返回，接着回到 MessageQueue 读 取 的 下 一 次 循 环享 元 设 计 模式：通过 Message 的静态方法 obatin() 获取，因为该方法不是无脑地 new，而是从单链表池子里获取实
例，并在 recycle() 后将其放回池子
好 处 在于复用 Message 实例，满足频繁使用 Message 的场景，更加高效
当然，缓存池存在上限 50，因为没必要无限制地缓存，这本身也是一种浪费 ,需 要留意缓存池是静态的，也就是整个进程共用一个缓存池MessageQueue 通 过 单 链 表 管 理 Message，不 同 于 进 程 共 用 的 Message Pool，其 是 线 程 独 有 的 通 过 Message 的 执 行时 刻 when 对 Message 进 行 排 队 和 出 队 MessageQueue 除 了 管 理 Message， 还 要 管 理 空 闲 Handler 和 同 步 屏 障
相 同点：都是通过单链表来管理 Message 实例；
Message 通 过 obtain() recycle() 向 单链 表 获取 插 入节 点
和MessageQueue 通 过 enqueueMessage()区别：
和 next() 向 单 链 表 获 取 和 插 入 节 点
Message 单 链 表 是静 态 的， 供 进程 使 用的 缓 存池 MessageQueue 单 链表 非 静态 ， 只供 Looper 线 程使 用 发 送 的 Message 都 是按 照 执行 时 刻 when 属 性的 先 后管 理 在 MessageQueue 里 延 时 Message 的 when 等 于调 用 的当 前时 刻 和
，固定为便于插入队列的 head 之 后 MessageQueue 会根据读取的时刻和 when将进行比较
when 已抵达的出队， 尚未抵达的计算出当前时刻和目标 when 的插 值 ，交由 Native 等待对应的时长，时间到了自动唤醒继续进行 Message 的读取
delay 之 和 非延时 Message 的 when 等于当前时刻 (delay 为 0) 插队 Message 的 when
事实上，无论上述哪种 Message 都不能保证在其 对应的 when 时刻执行，往往都会延迟一些！因为必须等当前执行的Message 处理完了才有机会读取队列的下一个 Message。
比 如 发 送 了非延时 Message，when 即为发送的时刻，可它们不会立即执行。都要等主线程现有的任务 (Message) 走完才能有机会 出 队，而当这些任务执行完 when 的时刻已经过了。假使队列的前面还有其他 Message 的话，延迟会更加明显！
彩 蛋 ：. onCreate() 里向 Handler 发送大量 Message 会导致主线程卡顿吗？
不 会，发送的大量 Message 并非立即执行，只是先放到队列当中而已。
onCreate() 以 及之 后 同步 调 用的 onStart()和 onResume() 处 理， 本 质上 也 是 Message。 等这 个 Message 执 行完 之 后 ，才 会进 行 读 取 Message 的 下一 次 循环 ， 这时 候 才能 回 调 onCreate 里 发送 的 Message。
需 要 说 明 的 是 ， 如 果 发 送 的 是 FrontOfQueue 将 Message 插 入 队 首 也 不 会 立 即 先 执 行 ， 因 为 onStart 和 onResume是onCreate 之 后 同步调用的，本质上是同一个 Message 的作业周期
作 为 使 用 Handler 机 制 的 入 口 ， Handler 是 发 送 Message 或 Runnable 的 起 点 发 送 的 Runnable 本 质 上 也 是Message，只 不 过 作 为 callback 属 性 被 持 有 Handler 作 为 target 属 性 被 持 有 在 Mesage 中 ，在 Message 执 行 条 件 满
足 的 时 候 供 Looper 回 调 事 实 上 ， Handler 只 是供 App 使 用 Handler 机 制的 API， 实质 来 说， Message 是 更为 重 要的 载体 。适 用 于期望空闲时候执行，但不影响主线程操作的任务
系统应用：
Activity destroy 回 调 就 放 在 了 IdleHandlerGC 操 作 App 应用：
当不重复执行中 ActivityThread 中 GCHandler 使 用 了 IdleHandler， 在 空 闲 的 时 候发 送 一个返回 true 的 IdleHandler，在 里 面 让 某 个 View 不停闪烁 ，这样当用户发呆时就可以诱导用户点击这个 View 将
某部分 初 始 化放 在 IdleHandler 里 不影 响 Activity 的 启动 彩 蛋问 题 ：
add/remove IdleHandler 的方法，是否需要成对使用？
不需要，回调返回 false 也可以移除
mIdleHanders 一直不为空时，为什么不会进入死循环？
执行过 IdleHandler 之后会将计数重置为 0，确保下一次循环
是 否可以将一些不重要的启动服务，搬移到 IdleHandler 中去处理？
最好不要，回调时机不太可控，需要搭配 remove 谨
慎使用 IdleHandle 的 queueIdle() 运 行在 那 个线 程 ？ 取 决于 IdleHandler add 到 的 MessageQueue 所 处的 线 程
异 步 Message： 设 置 了 isAsync 属 性 的 Message 实 例
可 以 用 异 步 Handler 发 送 也 可 以 调 用 Message#setAsynchronous() 直 接 设 置 为 异 步 Message 同 步 屏 障 ： 在MessageQueue 的 某个 位 置 放 一 个 target 属 性 为 null 的 Message， 确 保 此 后 的 非 异 步 Message 无 法 执 行 ， 只 能 执 行 异 步 Message
原 理 ：当 MessageQueue 轮 循 Message 时 候 发 现 建 立 了 同 步 屏 障 的 时 候 ，会 去 跳 过 其 他 Message，读 取 下 个 async 的
Message 并 执行，屏障移除之前同步 Message 都会被阻 塞
应 用 ： 比如屏幕刷新 Choreographer 就使用到了同步屏障，确保屏幕刷新事件不会因为队列负荷影响屏幕及时刷新。 注 意：同步屏障的添加或移除 API 并未对外公开，App 需要使用的话需要依赖反射机制Message 是 承 载任务的载体，在 Handler 机制中贯穿始终 Handler 则是对外公开的 API，负责发送 Message 和处理任务的回调， 是 Message 的 生 产 者 MessagQueue 负 责 管 理 待 处 理 Message 的 入 队 和 出 队 ， 是 Message 的 容 器Looper 负 责 轮 循
MessageQueue， 保 持 线 程 持 续 运 行 任 务 ， 是 Message 的 消 费 者 彩 蛋 ： 如 何 保 证MessageQueue 并 发 访 问 安 全 ？
任 何 线 程 都 可 以 通 过 Handler 生 产 Message 并 放 入 MessageQueue 中 ， 可 Queue 所 属 的 Looper 在 持 续 地 读取 并 尝 试 消 费 Message。 如何保证两者不产生死锁？
Looper 在 消 费 Message 之 前 要 先 拿 到 MessageQueue 的 锁 ，
具 体 在 于 nativePollOnce() 的 调 用 在 synchronized 方 法 块 的 外 侧 。
Message 入 队 前 也需 先 拿到 MessageQueue 的 锁， 而 这时 Looper 线 程正 在 等待 且 不持 有 锁， 可 以确 保 Message 的 成功 入队 。 入队 后 执 行 唤醒后释放锁，Native 收到 event 写入后恢复 MessagQueue 的读取并可以拿到锁，成功出队。
这 样一种在没有 Message 可以消费时执行等待同时不占着锁的机制，避免了生产和消费的死锁。
boolean enqueueMessage( Message msg, long when) {
synchronized (this) {
…
}
return true ;
}
Message next() {
…
for ( ; 😉 {
nativePollOnce( ptr, nextPollTimeoutMillis) ;
synchronized (this) {
…
}
}
}
Message next() { … for ( ; 😉 { nativePollOnce(ptr, nextPollTimeoutMillis) ; synchronized (this)
… …
}
}
NativeMessageQueue 负 责 连 接 Java 侧 的 MessageQueue，进 行 后 续 的 wait 和 wake，后 续 将 创 建 wake 的 FD，并通 过 epoll 机 制 等待 或 唤醒 。 但并 不 参与 管 理 Java 的 MessageNative 侧 也 需 要 Looper 机 制 ， 等 待 和 唤 醒 的 需 求 是 同 样 的 ， 所 以 将 这 部 分 实 现 都 封 装 到 了 JNI 的NativeMessageQueue 和 Native
的 Looper 中 ， 供 Java 和 Native 一 起 使 用Looper Native 部 分 承 担 了 Java 侧 Looper 的 等 待 和 唤 醒 ， 除 此 之 外 其 还 提 供 了 Message、MessageHandler 或 WeakMessageHandler、 LooperCallback SimpleLooperCallback这 些 部 分 可 供 Looper 被 Native 侧 直 接 调 用 ， 比 如 InputFlinger 广 泛 使 用 了 Looper或等API
主 要 方 法 是 调 用 Looper 构 造 函 数 或 prepare 创 建 Looper， 然 后 通 过 poll 开 始 轮 询 ， 接 着 sendMessage 或addEventFd， 等 待 Looper 的唤醒。使用过程和 Java 的调用思路类似
# 1.19 Handler 为什么可能导致内存泄露？如何避免？
持 有 Activity 实例的内名内部类或内部类的生命周期应当和 Activity 保持一致，否则产生内存泄露的风险。
如果Handler 使 用 不 当 ， 将 造 成 不 一 致 ， 表 现 为 ： 匿 名 内 部 类 或 内 部 类 写 法 的 Handler、 Handler$Callback、Runnable，或 者 Activity 结 束 时 仍 有 活 跃的 Thread 线程或 Looper 子线程 具体在于 ：
异步任务仍然活跃或通过发送的 Message 尚未处理完毕，将使得内部类实例的 生 命周 期 被错 误 地延 长 。造 成本 该 回收 的 Activity实 例被 别 的 Thread 或 Main Looper 占 据而 无 法及 时 回收 (活 跃的 Thread 或 静 态属 性 sMainLooper 是GC Root 对 象) 建 议的 做 法： 无 论是 Handler、Handler$Callback 还 是 Runnable，尽 量采 用 静态 内 部 类
+弱引用的写法，确保尽管发生不当引用的时候也可以因为弱引用能清楚持有关系 另外在 Activity 销毁的时候及时地终止 Thread、停 止 子 线 程 的 Looper 或 清 空 Message，确 保 彻 底 切 断 Activity 经 由 Message 抵 达 GCRoot 的 引 用 源 头 (Message 清 空 后 会其 与 Handler 的 引用 关 系， Thread 的 终止 将 结束 其 GC Root 的 源头 ) 注 意：静 态的 sThreadLocal 实 例不 持 有存 放Looper 实 例 的 ThreadLocalMap，而 是 由 Thread 持
有 。 从 这 个 角 度 上 来 讲 ， Looper 会 被 活 跃 的 GC Root Thread 持 有 ， 进 而 也 可 能导致内存泄露。
彩 蛋： 网 传的 Handler$Callback 方 案能 否 解决 内 存泄 露 ？
不能。
Callback 采 用 内 部类 或 匿名 内 部类 写 法的 话 ，默 认持 有 Activity 的 引用 ，而 Callback 被 Handler 持有 。这 最 终将 导 致 Message -> Handler -> Callback -> Activity 的 链 条 仍 然 存 在 。
特别广泛，比如：
Activity 生 命 周 期 的 管 理 屏 幕 刷 新 HandlerThread、IntentService AsyncTask 等 。 主 要 利 用 Handler 的 切换 线 程 、主 线 程 异 步 Message 的 重 要特 性 。注 意：Binder 线程非主线程，但很多操作比如生命周期的管理都要回到主线程，所以很多 Binder 调用 过 来 后 都 要 通 过 Handler 切 换 回 主 线 程 执 行 后 续 任 务 ， 比 如
ActviityThread$H 就 是 extends Handler。
Android中 UI 非线程安全，并发访问的话会造成数据和显示错乱。
但 此限 制 的检 查 始于 ViewRootImpl#checkThread()，其 会在 刷 新等 多 个访 问 UI 的 时机 被 调用 ，去 检查 当 前线程 ，非 主 线程 的 话抛 出异常。
而ViewRootImpl 的创建在 onResume() 之后，也就是说如果在 onResume() 执行前启动线程访问 UI 的话是不会报错的，这点需 要留意！
彩 蛋：onCreate() 里子线程更新 UI 有问题吗？为什么？
不会。
因 为异常的检测处理在 ViewRootImpl 中，该实例的创建和检测在 onResume() 之后进行。
让 我们共同维护这几十个问题，彻底吃透 Handler 机制！
如 果 对 Message 创建和复用的细节感兴趣，可以查阅《Handler 的 Message 实例怎么创建，为什么不是直接new？》。 如果并不 确 定 Message 有多少种、 已经背后执行的细节，或者对空闲 Handler、同步屏障等特殊用法不了解的话，建议阅读《万字复盘
的理由和背后原理好奇的话，可以参考《Looper 需要手动Handler 内存泄漏的问题存在疑惑，想要一次性搞清楚的话，可以试着看看这篇文Handler 中 各式 Message 的使用和原理》 。 如果对 Looper quitquit， 那 主线程 Looper 呢？》。 如果对于文章 ：《重新理解为什么Handler 可能导致内存泄露？》。
# AMS面试题解析
ActivityManagerService 主 要负责系统中四大组件的启动、切换、调度及应用进程的管理和调度等工作 ，其 职责与操作系统中的进程管理和调度模块类似。ActivityManagerService进行初始化的时机很明确就是在 SystemServer进 程开启的时候 ，就会初始化，ActivityManagerService。
(系 统 启 动 流 程 )如 果打开一个App的话 ，需要AMS去通知zygote进程 ，所 有 的 Activity的 生 命 周 期 AMS来 控 制ActivityThread 在 Android中 它 就 代 表 了 Android的 主 线 程 ,它 是 创 建 完 新 进 程 之 后 ,main函 数 被 加 载 ， 然 后 执 行 一 个loop的 循 环使当前线程进入消息循环 ，并且作为主线程。
ApplicationThread
ApplicationThread是 ActivityThread的 内 部 类，是 一 个 Binder对 象 。 在 此 处 它 是 作 为 IApplicationThread对 象的 server端 等待 client端 的请 求 然后 进 行处 理 ， 最大 的 client就 是 AMS。
AMS与 ActivityThread之 间 诸 如 Activity的 创 建 、暂 停 等 的 交 互 工 作 实 际 上 是 由 Instrumentation具 体操 作 的 。 每个 Activity都 持 有 一 个 Instrumentation对 象 的 一 个 引 用，整 个 进 程 中 是 只 有 一 个 Instrumentation。
mInstrumentation的 初 始 化 在 ActivityThread: : handleBindApplication函 数 。
可 以用来独立地控制某个组件的生命周期。
Activity`的`startActivity`方法。
`startActivity`会调用`mInstrumentation .execStartActivity() ; mInstrumentation掉用AMS , AMS 通 过 socket 通 信 告 知 Zygote 进 程 fork 子 进 程 。
应 用启动时,Launcher进程请求AMS。用进程 客户端发送请求AMS发送创建应用进程请求 ，Zygote进程接受请求并fork应调 用 Process.start() 方法新建进程连 接 调 用 的 是 ZygoteState.connect() 方 法 ， ZygoteState 是 ZygoteProcess 的 内 部 类 。
ZygoteState里 用 的LocalSocketpublic static ZygoteState connect( LocalSocketAddress address) throws IOException {
DataInputStream zygoteInputStream = null ;
BufferedWriter zygoteWriter = null;
final LocalSocket zygoteSocket = new LocalSocket( ) ;
try {
zygoteSocket .connect(address);
zygoteInputStream = new DataInputStream(zygoteSocket .getInputStream()) ;
zygoteWriter = new BufferedWriter( new OutputStreamWriter(
zygoteSocket .getOutputStream()) , 256) ;
}
catch (IOException ex) {
try {
zygoteSocket .close() ;
}
}
}
catch (IOException ignore) {
throw ex ;
return new ZygoteState(zygoteSocket , zygoteInputStream , zygoteWriter ,
Arrays .asList(abiListString .split(“,”))) ;
}
Zygote 处理客户端请求
Zygote 服 务 端 接 收 到 参 数 之 后 调 用 ZygoteConnection.processOneCommand() 处 理 参 数 ，并fork 进 程 最 后 通 过 fifindStaticMain() 找 到 ActivityThread 类 的 main() 方 法并 执 行 ， 子进 程就 启动 了
# 1.5 ActivityRecord. TaskRecord. ActivityStack.ActivityStackSupervisor.ProcessRecord
[https://duanqz.github.io/2016-02-01-Activity-Maintenance#activityrecord](https://duanqz.github.io/2016-02-01-Activity-Maintenance#activityrecord)
[https://www.jianshu.com/p/94816e52cd77](https://www.jianshu.com/p/94816e52cd77)
[https://juejin.im/post/6856298463119409165#heading-10](https://juejin.im/post/6856298463119409165#heading-10)
**ActivityRecord**
ActivityRecord是 应 用 层 Activity组 件 在 AMS中 的 代 表 ，每一个在应用中启动的 Activity ，在AMS中 都 有一个ActivityRecord实 例 来 与 之 对 应 ，这 个 ActivityRecord伴 随 着 Activity的 启 动 而 创 建 ，也 伴 随着 Activity的 终 止 而
销毁。
**TaskRecord**
TaskRecord即 任 务 栈，每 一 个 TaskRecord都 可 能 存 在 一 个 或 多 个 ActivityRecord ， 栈 顶 的 ActivityRecord表 示 当 前可见的界面。
一 个 App是 可 能 有 多 个 TaskRecord存 在 的 一 般情况下,启动App的第一个 activity时 ， AMS为 其 创 建 一 个 TaskRecord任 务 栈特 殊 情 况 ,启 动 singleTask的 Activity ， 而 且 为 该 Activity指 定 了 和 包 名 不 同 的taskAffiffiffinity ， 也 会 为 该 activity创 建一 个 新 的 TaskRecord ActivityStack, ActivityStack是 系 统
中 用 于 管 理 TaskRecord的 ,内 部 维 护 了 一 个 ArrayList。
**ActivityStackSupervisor**
ActivityStackSupervisor内 部 有 两 个 不 同 的 ActivityStack对 象 ： mHomeStack、
mFocusedStack ，用 来 管 理 不同的 任 务 。我 们 启 动 的 App对 应 的 TaskRecord由 非 Launcher ActivityStack管 理 ，它 是 在 系 统 启 动 第 一 个app时创建的。
**ActivityStackSupervisor**
ActivityStackSupervisor管 理 着 多 个 ActivityStack ， 但 当 前 只 会 有 一 个 获 取 焦 点 (Focused)的ActivityStack; AMS对 象 只会存在一个 ，在初始化的时候 ，会 创 建 一 个 唯 一 的 ActivityStackSupervisor Activity管理的最小单位 ，它对应着一个用户界面
对象
ProcessRecord记 录 着 属 于 一 个 进 程 的 所 有 ActivityRecord ， 运 行 在 不 同TaskRecord中 的ActivityRecord可 能 是属 于 同 一 个 ProcessRecord。
关系
AMS运行在SystemServer进程中。 SystemServer进程启动时，会通过SystemServer. startBootstrapServices(）来创建一个AMS的对象：
AMS通过 Activity StackSupervisor* 管理 Activity。 AMS对象只 会存在一个，在初始化的时候，会创建一个唯一的 ActivityStackSupervisor对 象；
Activity StackSupervisor中维护了显示设备的信息。当有新的显示设备添加时 ，会创建一
个新的 ActivityDisplay对象；
ActivityStack与 显示设备的鄉定。ActivityStack的创建时 在Launcher启动时 候进行的，AMS 还未有非 Launcherg ActivityStack. 后 面的App启动时就会创建 Launcher的ActivityStack 通过 ActivityStackSupervisor来 创 建 ActivityRecord
在 ActivityStack上 创建 TaskRecord每一 个ActivityRecord都需要找到自己的宿主 TaskRecord
从桌面启动
从桌面点击图标启动一个Activity ，
会 启 动 ActivityStackSupervisor中 的 mFocusedStack ， mFocusedStack负 责
管 理 的 是 非 Launcher相 关 的 任 务 。 同 时 也 会 创 建 一 个 新 的 ActivityRecord和 TaskRecord ，
ActivityRecord放 到 TaskRecord中 ， TaskRecord则 放 进 mFocusedStack中 。
四种启动模式
**standard**
默 认模式 ， 每 次 启 动 Activity都 会 创 建 一 个 新 的 Activity实 例 。
**singleTop**
如 果要 启 动的 Activity已 经在 栈 顶 ，则 不会 重 新创 建 Activity ，只 会调 用 该该 Activity的onNewIntent()
方 法。 如 果要启动的Activity不在栈顶 ，则会重新创建该Activity的实例。
**singTask**
如 果 要启动的Activity已经存在于它想要归属的栈中 ，那么不 会创建该 Activity实例 ，将栈中位于该
Activity上的 所 有 的 Activity出 栈 ， 同 时 该 Activity的 onNewIntent()方 法 会 被 调 用 。
**singleInstance**
要 创 建在一个新栈 ，然后创建该Activity实例并压入新栈中 ，新栈中只会存在这一个Activity实例。
# 1.6 ActivityManager、ActivityManagerService、ActivityManagerrVattve、ActivityManagerProxy的 关 系
[https://www.cnblogs.com/mingfeng002/p/10650364.html](https://www.cnblogs.com/mingfeng002/p/10650364.html)
startActivity 方 法 。 startActivity 会 调 用mInstrumentation .execStartActivity(); execStartActivity
Activity的通 过 ActivityManager 的 getService 。 代 码 层 面 :
ActivityManager. getRunningServices里 通 过 ActivityManagerNative. getDefault得 到 此代 理 对 象 ActivityManagerProxy ， ActivityManagerProxy代 理 类 是
ActivityManagerNative的 内 部 类 。
ActivityManagerNative是 个 抽象 类 ， 真正 发 挥作 用 的是 它 的子 类ActivityManagerService。
介绍:
ActivityManager
ActivityManager官 方 介绍 ： 是与 系 统所 有 正在 运 行着 的 Acitivity进 行交 互 ， 对系 统 所有 运 行中 的Activity相 关 信息 ( Task ，Memory ，Service ，App ) 进行管理和维护。
ActivityManagerNative、
IActivityManager继 承 了 Interface接 口 。 而 ActivityManagerNative和 ActivityManagerPorxy 实 现 了 这 个 IActivityManager接口;
ActivityManagerProxy代 理 类 是 ActivityManagerNative的 内 部 类
ActivityManagerNative是 个 抽 象 类 ， 真 正 发 挥 作 用 的 是 它 的 子 类
ActivityManagerService
ActivityManager持 有 的 是 这 个 ActivityManagerPorxy代 理 对 象 ，这 样 ，只 需 要 操 作 这 个 代 理 对 象 就能 操 作 其 业务 实 现 的 方 法 。 那 么 真 正 实 现 其 也 业 务 的 则 是 ActivityManagerService。
ActivityManagerNative这 个 类 ， 他 继 承 了 Binder而 Binder实 现 了 IBinder接 口 。 其子 类 则 是 ActivityManagerService。
# 1.7 手写实现简化版AMS
AMS与Binder相关 ，其中要明白下面几个类的职责:
IBinder ：跨进程通信的Base接口 ，它声明了跨进程通信需要实现的一系列抽象方法 ，实现了这个接口就说明 可以 进行跨进程通信 ，所有的Binder实体都必须实现IBinder接口。
IInterface ：这也是一个Base接口 ，用来表示Server提供了哪些能力 ，是Client和Server通信的协议 ，Client和 Server都 要实现此接口。
Binder ： IBinder的 子 类 ，Java层提供服务的Server进程持有一个Binder对象从而完成跨进程间通信。
BinderProxy ： 在 Binder.java这 个 文 件 中 还 定 义 了 一 个 BinderProxy类 ， 这 个 类 表 示 Binder代 理 对 象
它 同 样 实 现了 IBinder接口。 Client中拿到的实际上是这个代理对象。
1、 首 先 定 义 IActivityManager接 口 (继 承 IInterface) ：public interface IActivityManager extends IInterface {
//binder描 述 符
String DESCRIPTOR = “android .app.IActivityManager” ;
//方法编号
int TRANSACTION_startActivity = IBinder .FIRST_CALL_TRANSACTION + 0 ;
//声明一个启动activity的方法 ，为了简化 ，这里只传入intent参数
int startActivity( Intent intent) throws RemoteException ;
}
2、 实 现 ActivityManagerService侧 的 本 地 Binder对 象 基 类:public abstract class ActivityManagerNative extends Binder implements IActivityManager {
public static IActivityManager asInterface( IBinder obj)
{
if (obj == null) {
return null;
}
IActivityManager in = ( IActivityManager)
obj .queryLocalInterface(IActivityManager .DESCRIPTOR) ;
if (in != null) {
return in ;
}
//代理对象 ，见下面的代码
return new ActivityManagerProxy( obj) ;
}
@Override
public IBinder asBinder() {
return this;
}
protected boolean onTransact(int code , Parcel data, Parcel reply , int flags) throws
RemoteException {
switch (code) {
// 获 取 binder描 述符
case INTERFACE_ TRANSACTION:
reply .writeString(IActivityManager .DESCRIPTOR) ;
return true;// 启动activity ， 从 data中 反 序列 化 出 intent参 数 后 ， 直 接调 用 子 类 startActivity方 法 启动
activity。
case IActivityManager .TRANSACTION_startActivity :
data. enforceInterface( IActivityManager. DESCRIPTOR) ;
Intent intent = Intent.CREATOR .createFromParcel( data);
int result = this .startActivity(intent) ;
reply .writeNoException() ;
reply .writeInt(result);
return true;
}
return super .onTransact(code , data, reply, flags) ;
}
}
3、实现 Client侧的代理 对象 ：public class ActivityManagerProxy implements IActivityManager {
private IBinder mRemote ;
@Override
public int startActivity( Intent intent) throws RemoteException {
Parcel data = Parcel.obtain() ;
Parcel reply = Parcel .obtain() ;
int result;
try {
// 将intent参数序列化 ，写入data中
intent .writeToParcel(data, 0) ;
调 用 BinderProxy对 象 的 transact方 法 ， 交 由 Binder驱 动 处 理 。
//
mRemote.transact(IActivityManager .TRANSACTION_startActivity , data , reply , 0) ;
reply .readException() ;
// 等待server执行结束后 ，读取执行结果
result = reply .readInt() ;
finally {
data.recycle() ;
reply .recycle() ;
}
return result ;
}
}
}
4、 实 现 Binder本 地 对 象 ( IActivityManager接 口)：public class ActivityManagerService extends ActivityManagerNative
@Override
public int startActivity( Intent intent) throws RemoteException {
{
// 启 动 activity
return 0 ;
}
}
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。
