导读

刷算法题需要一定的节奏，同样对待每一道算法题也需要认真的对待不可操之过急，否则会导致：算法虐我千万遍，我待算法如初恋！如果这句话是从对算法态度上说爱如初恋那必须得肯定你的态度，但如果是每一道算法题，反复都能虐你千万遍，那这个初恋的滋味肯定不好受。我们应该是面对新题对待如初恋，对待已经做过的题应该是勾勾手指，手到擒来的老司机，否则就是白刷。不仅浪费时间而且浪费精力，所以刷题必须讲究方式方法，建议反复阅读此文跟我学：LeetCode刷题大法。下面这里通过一张思维导图帮助大家整理这道题的思路。思维导图一方面罗列了本文的大纲，另一方面也是希望读者朋友可以保存图片至自己的复习资料里，以便随时通过该大纲去复习，注意关注标红的重点解法。

看题总结

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

Related Topics

哈希表

双指针

字符串

Sliding Window

通过对题目的阅读，我们可以得出以下几个结论

1. 题目类型为数组
2. 要求是返回最长的不含重复字母的子串长度
3. 输入的字符串可能为空串，输入判断

多解法及复杂度分析

解法一：暴力法，多重循环

首先希望读者能写出双重循环的模板代码，在此再次强调此代码是数组问题暴力法的套路墙裂建议背诵默写，如果还是不能随手写出回过头看一下此文跟我学：LeetCode刷题之1.两数之和，好了继续此问题的暴力解决法就是通过双重循环，加内部一层循环判断[i,j]之间的元素是否是唯一的，然后做相应的移动和记录最大值。注意此处的双重循环的i，j范围，是由于allUnique()方法的for循环范围。

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

public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }

复杂度分析

时间复杂度：O(n^3)，三重循环

空间复杂度：O(min(n, m))O(min(n,m))，我们需要 O(k)的空间来检查子字符串中是否有重复字符，其中 k 表示 Set 的大小。而 Set 的大小取决于字符串 n 的大小以及字符集/字母 m 的大小。

解法二：双指针+滑动串口

该题的实现思路主要是基于：滑动窗口。

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！如左出右进变为bca

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

• 哈希法的实现可以基于Map定义key为字符串的中的每个字符，value为该字符的位置i+1(方便计算长度）
• 通过数组实现，应为字符串由字母组成所以可以根据ASCII码的字符大小128，存放字符的位置i+1。

这里推荐使用数组，数组的存取都是O(1)的实现，当然Map在此种情况下也是的。代码如下

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

public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] hash = new int[128];
        int start = 0;
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            start = Math.max(ans, hash[s.charAt(i)]);
            ans = Math.max(ans, i - start + 1);
            hash[s.charAt(i)] = i + 1;
        }
        return ans;
    }

复杂度分析

时间复杂度：O(n)，只进行一次遍历

空间复杂度：O(m)，m 是字符集的大小128

两种解法，充分体现了以空间换时间思想的，来一次加快算法处理速度。所以在算法题中哈希表数组和Map的代码也需要背诵记忆，才能游刃有余。

同类题相关

992. K 个不同整数的子数组

若你反复AC，且充分理解了本题解法，可以尝试去解答同类题992该题是困难题不过无妨，同类题的意思就是变形，往往是增加了特定的条件或者是针对不同的场景。所以同类题的目的是，透过现象看本质，一时的解不出不碍事，按我说的方法跟我学：LeetCode刷题大法，通过此种方法一定是越来越自信的刷题。

技巧与心得

1. 开一个github仓库用来记录各种题解
2. 在idea或者vscode中都提供了leecode的插件刷题，方便调试断走流程
3. 遇到不会的题不要慌，稳住心态直接看题解
4. 文字类的表述不如视图类的直观，图文并茂精选图解优先或者参考leetcode国际站的大牛题解
5. 图解依旧看着吃力也无妨，可以在哔哩哔哩或者YouTube上，通过leecode + 题号，搜索高收视率的视频观看
6. 多看几次本文跟我学：跟我学：LeetCode刷题大法，相信我你肯定能越刷越自信

最后的最后

看到最后，我相信你对本题应该有不一样的感受了吧！在此若有不对之处或建议等，留言告诉我；若有疑惑或者不一样的看法，也请告诉我，我们可以一起探讨学习！

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！

导读

本题是LeetCode第二题，难度标记为中等。此题为链表题，不出意外遇到链表题都是画图解题，因为链表题的核心是在符合条件下的链表next指针的变化，除了链表的增删改查之外，如何反转链表的代码，我墙裂建议你先理解背诵，刷链表题基础必备代码，如下

1
2
3
4
5
6
7
8
9
10
11

pubic ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;

    while(cur != null){
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
}

这里通过一张思维导图帮助大家整理思路。思维导图一方面罗列了本文的大纲，另一方面也是希望读者朋友可以保存图片至自己的复习资料里，以便随时通过该大纲去复习。

看题总结

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

1
2
3

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

Related Topics

链表

数学

通过对题目的阅读，我们可以得出以下几个结论

• 题目类型为链表
• 用两个链表表示两个整数，整数在链表中的存储方式是逆序的，通过链表实现两整数的相加操作，返回值也是用逆序的链表存储的整数。
• 非空链表，非负数整数，除了0之外整数不会以0开头，输入是合法的

多解法及复杂度分析

解法一：非递归实现

1. 定义一个哑结点dummy（可以避免对头结点的处理），指向当前节点cur，然后定义一个保存进位数值的 carry（因为两数相加可能会产生进位，便用 carry 来保存）
2. 当 l1 或 l2 不为空时进行遍历，即二者都为空时才退出循环，
3. 通过设置默认值为 0 的 x和 y，使得当二者中有一个为空时，使用 0 来与另一位相加
4. 得到 sum 后，将 sum 的个位数连接到链表中，并将十位数赋给 carry,
5. 移动 cur 使其一直指向链表的尾部

最后要判断 carry 是否大于 0，因为例如 (1 -> 2 -> 3) + (7 -> 8 -> 9) 会得到结果 8 -> 0 -> 3 -> 1，所以在最后判断 l1 和 l2 都已经为空了，但是此时 carry 大于 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

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0; // 保存进位数值的 carry
        while (l1 != null || l2 != null) {
          	// 用0补齐，链表长度
            int x = l1 != null ? l1.val : 0;
            int y = l2 != null ? l2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            ListNode newNode = new ListNode(sum % 10);

            curr.next = newNode;
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        }
  
  			// 存在两链表长度相等，且最高位计算和大于10，需进位创建新节点
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }

        return dummy.next;
    }

解法二：递归实现

首先我们需要理解递归，墙裂建议背诵默写递归的模板代码，递归解法的套路如下

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

public void recur(int level, Param param) {
  	// 递归终止条件
    if (level > MAX_VALUE) {
        //process result
        return;
    }

    // 当前层处理处理
    process(param);

    // 进入下一层递归
    recur(level, newParam);

    // 非必要的数据恢复
}

这题使用递归很好理解，两链表的节点从左往右进行相加，进位，直到两链表都到达尾部。

1. 递归终止条件：两链表都到达尾部
2. 当前层处理：链表节点相加计算和，得到余数，及carry进位
3. 进入下一次递归：传入新节点及进位值。

最后代码如下

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

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }

    private ListNode add(ListNode a, ListNode b, int carry) {
        // terminator 终止条件
        if (a == null && b == null) {
            return carry > 0 ? new ListNode(1) : null;
        }

        // current logic  当前层逻辑处理
        // 如果当前节点a,b其中一个为null，则赋值为ListNode(0)，方便计算
        a = a == null ? new ListNode(0) : a;
        b = b == null ? new ListNode(0) : b;

        // 当前两链表节点的和
        int sum = a.val + b.val + carry;
        carry = sum / 10;
        // 将取模结果保存在第一个链表中
        a.val = sum % 10;
        // driil down   进入下一层递归
        a.next = add(a.next, b.next, carry);
        return a;
    }

同类型题相关

若你反复AC，且充分理解了本题的两种题解，我敢保证下面这题解出来只是时间长短问题。

在这里还是提醒刷题的朋友，多看几次本文跟我学：LeetCode刷题大法

LeetCode 445. 两数相加 II

技巧与心得

1. 开一个github仓库用来记录各种题解
2. 在idea或者vscode中都提供了leecode的插件刷题，方便调试断走流程
3. 遇到不会的题不要慌，稳住心态直接看题解
4. 文字类的表述不如视图类的直观，图文并茂精选图解优先或者参考leetcode国际站的大牛题解
5. 图解依旧看着吃力也无妨，可以在哔哩哔哩或者YouTube上，通过leecode + 题号，搜索高收视率的视频观看
6. 多看几次本文跟我学：LeetCode刷题大法，相信我你肯定能越刷越自信

最后的最后

看到最后，我相信你对本题应该有不一样的感受了吧！在此若有不对之处或建议等，留言告诉我；若有疑惑或者不一样的看法，也请告诉我，我们可以一起探讨学习！

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！

闲聊

不想赘述算法与数据结构本身存在的重要性以及对工作面试的重要性。我只想谈谈如何通过解决一道道算法题，慢慢的改变自己对算法的态度，并且从算法中获得自信，如果以下论述我们产生了些许共鸣！请关注我，让我们一起努力，一起刷爆leetcode吧。

坚定想法

曾几何时，在无数个瞬间。可曾遇到过这些情况

• 算法很重要，我要刷一刷算法；
• 背了几题，但不刷刷算法我还是慌的；
• 算法虽很重要，但我工作上没怎么用上；
• 我刷过了，但面试我怎么打不出来；
• 刷了几题，太难了，我放弃；
• ….

放弃的理由千千万万

讲真放弃的理由千千往往，坚持的理由我觉得只有兴趣和生存。只要是抱着生存的理由，那放弃的理由分分钟淹没他，除非真的找不到工作活不下去，就算如此，还能转行，直接逃避……，说这些就是想让自己和大家认清本质，坚定一下刷算法的的信念，走出第一步告诉自己：我需要刷题，我要刷题！

如何刷题到自信

当看到这里，我相信刷过题的人都有过类似经验

1. 第一次平静的打开某算法库官网(这个主要是LeetCode)，
2. 然后打开第一个题，看了题目有点思路，一写代码结果各种输入判断，代码编译上的错误都会遇到
3. 千辛万苦ac后发现只打败了30%的人。完全没有考虑过时间复杂度，空间复杂度，不过好歹过了
4. 然后继续刷，没过多久就遇到了一题懵逼或者死磕磕不出的题，然后看题解
5. 看懂的题解我们会惊呼怎么想到的，没看懂的题解会沮丧这也太难了，半天看不懂的题解完全就打击到了自信心
6. 最终刷题结束，然后可能没有然后了，或者过几天再来挣扎一下。
7. 那些挣扎过并坚持下来的人，我相信算法面试稳了但不一定自信，除非养成了刷题的习惯

这经历完全是自我打击的过程，说到底还是打开的姿势不对。没有找准刷题的基本思想和步骤，试试下面的刷题步骤

1. 打开一题算法，先看题目，5-10分钟毫无思绪或者无法解决，
2. 直接看题解，题解一般会有多种解法，找最优解看懂了背下来
3. 然后不看题解去解题，ac后不急，多默写几遍ac几遍，直到相信自己明天起床也能稳稳的ac
4. 接着可以再去看题解，去比较其他解法，分析他们的时间复杂度和空间复杂度，看最优解做的优化
5. 通过比较，肯定是可以加深最优解的印象。最后重新打开这道题
6. 看题，思考给出各种解法的思路以及复杂度，最后选出最优解，把它写下来。
7. ac的那一刻，你的自信就来了。
8. 当隔了一星期，你再来解这道题一次ac，稳如狗就更自信了。否则也不会沮丧，只是查漏补缺而已，几分钟后依旧ac。

技巧与心得

1. 遇到不会的题不要慌，看题解
2. 文字类的表述不如视图类的直观，尽量找图文并茂精选图解，或者看leetcode国际站的大牛题解
3. 图解依旧看着吃力，可以在哔哩哔哩或者YouTube上，通过leecode + 题号，搜索高收视率的视频观看
4. 反复研读观看，相信我你最终会懂的

最后的最后

我想说且是重点的，未来我将带领各位盆友一起刷算法题，后续我会通过视频+图文的方式来分享每一题的思路和多种解法代码。同时教会大家更方便，高效的刷题。

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！

导读

该题是leetcode的第一题，也是简单题。但无论题目简单难否，答案却是各式各样。有些题解代码精简明了，有些却是又臭又长；有些题解另辟蹊径，有些却是奇技淫巧，前者代码是需要我们学习，而后者是我们需要知道然后避免的。在本文我将为大家讲解该题前者代码的几种解法，后者代码解法大家充分理解本题后可以去官网逛逛评论或者题解，没准能博君一笑。这里通过一张思维导图帮助大家整理思路。思维导图一方面罗列了本文的大纲，另一方面也是希望读者朋友可以保存图片至自己的复习资料里。以便随时通过该大纲去复习。

看题总结

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

1
2
3
4

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Related Topics

数组

哈希表

通过对题目的阅读，我们可以得出以下几个结论

1. 题目类型是数组类型
2. 题意在数组中找到和为目标值的两个元素，并返回数组下标。例如num[i] + nums[j] = target。
3. 每种输入都会有对应的一个答案，意味着输入数组nums肯定是有效的，输入是合法的
4. 不能重复利用数组中的元素，即满足条件的量元素数组下标不同 i != j，输出要排除i==j的答案

多解法及复杂度分析

解法一：暴力法：双重循环

从题意分析得出的结论,我们只需要在数组中找到下标i，j两个元素。最简单直接的方法就是通过双重循坏，第一重循环确定元素nums[i], 第二重循坏在[i+1, nums.length)中找num[j], 符合条件为nums[j] = target - nums[i];别忘了i ！= j因为j的最大值是nums.length-1, 所以i的最大值为num.length-2

针对下面的模板代码墙裂建议理解背诵默写，能通过双重循环暴力法解决的题目都可以套用

1
2
3
4
5
6

for (int i = 0; i < nums.length - 1; i++) {
  for (int j = i + 1; j < nums.length; j++) {
    // 条件
    .....
  }
}

完整代码如下

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

public int[] twoSum(int[] nums, int target) {
  if (nums == null || nums.length < 2) {
    return new int[0];
  }

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

  return new int[0];
}

复杂度分析：

时间复杂度为O(n^2)：对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。

空间复杂度为O(1)：没有使用辅助空间

解法二：哈希表 + 双指针

针对这种方法只要哈希表和双指针各自的作用

1. 哈希表，该题通过Map<Integer, List> map存储key为元素值，value为元素值相同的数组下标的集合。
2. 双指针，针对有序数组，定义左右头尾指针left = 0，right = nums.length - 1。通过条件nums[left] + nums[right] 与 target的比较大小，因为是有序数组，若nums[left] + nums[right] < target则left++，否则right–。直到两者相等则存在解。
3. 因为双指针的是针对有序组求目标值， 所以我们需要对输入数组排序，排序后的元素下标会发生改变，所以我们需要提前用哈希表记录元素下标，元素可能相同所以需要用集合存储。

理解了上面步骤代码遍不难写出

哈希表部分

1
2
3
4
5
6
7
8
9
10

Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
  if (map.containsKey(nums[i])) {
    map.get(nums[i]).add(i);
  } else {
    List<Integer> list = new ArrayList<>();
    list.add(i);
    map.put(nums[i], list);
  }
}

双指针部分，划个重点双指针代码墙裂建议背诵默写，数组问题必备结题法

1
2
3
4
5
6
7
8
9
10
11

Arrays.sort(nums);
int left = 0, right = nums.length - 1;
while (left < right) {
    if (nums[left] + nums[right] == target) {
        return new int[]{map.get(nums[left]).get(0), nums[left] == nums[right] ? map.get(nums[right]).get(1) : map.get(nums[right]).get(0)};
    } else if (nums[left] + nums[right] > target) {
        right--;
    } else {
        left++;
    }
}

复杂度分析：

时间复杂度O(nlogn)：双指针是基于有序数组从两端查找结果时间复杂度为O(n)，在这里需要注意数组的排序是通过Arrays.sort(nums)内部会根据数据大小选择插入排序或者双轴快速排序实现，具体可参考源码，也就是说在某些条件下,可以按线性时间对数据进行排序时间复杂度为O(nlogn)，因此最最终的时间复杂度为O(nlogn)

空间复杂度O(m)：使用了额外的map辅助空间，其中m为nums数组中不同元素的数量。

解答三：一次遍历哈希表

该方法为本题的最优解，需多记多背。思路很简单很实用，类似于签到找人。如在大型网恋线下见面会上，到场的男男女女第一步是先问一下前台签到人员：我的网恋对象到了吗？前台签到人员查了下签到表，发现他的网恋对象到了则由工作人员带他到对方处，找人成功，否则进行签到安排就做。当他的对象到了就能直接通过签到表由工作人员直接带到他面前。

签到表即为哈希表用于记录，遍历元素，int num = target - nums[i];若num在map表中则找人成功，否则加入哈希表map.put(nums[i], i);

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

public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length < 2) {
        return new int[0];
    }

    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int num = target - nums[i];
        if (map.containsKey(num)) {
            return new int[]{map.get(num), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

复杂度分析

时间复杂度O(n)：针对n长度的数组只进行了一次遍历，且在表中进行的每次查找只花费O(1) 的时间。

空间复杂度O(n)：所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

同类题相关

若你反复AC，且充分理解了本题的3种解法，我敢保证下面三题解出来只是时间长短问题。

在这里还是提醒刷题的朋友，多看几次本文跟我学：LeetCode刷题大法

LeetCode 15. 三数之和

LeetCode 16. 最接近的三树之和

LeetCode 18. 四数之和

技巧与心得

开一个github仓库用来记录各种题解，例如本人的https://github.com/ZhengYangxin/LeetCode

刷题不建议直接在网页上刷，在idea或者vscode中都提供了leecode的插件，谁用谁知道

遇到不会的题不要慌，直接看题解

文字类的表述不如视图类的直观，尽量找图文并茂精选图解，或者看leetcode国际站的大牛题解

图解依旧看着吃力，可以在哔哩哔哩或者YouTube上，通过leecode + 题号，搜索高收视率的视频观看

反复研读观看，相信我你最终会懂的

最后的最后

看到最后，我相信你对本题应该有不一样的感受了吧！come on 动起来，就是干！在此若有不对之处或建议等，留言告诉我；若有疑惑或者不一样的看法，也请告诉我，我们可以一起探讨学习！

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！

最近在在深入Framwork学习，希望我的学习分享能帮到你。首先我们看一下关于Zygote我们应该如何去分析，这里通过一张思维导图帮助大家整理思路。思维导图一方面罗列了本文的大纲，另一方面也是希望读者朋友可以保存图片至自己的复习资料里。以便随时通过该大纲去复习！

谈谈对Zygote的理解

当遇到这样一道面试题，我们应该分析面试官想考察的是什么？

• 了解Zygote的作用，初级的要求，答出来后方能深入
• 熟悉Zygote的启动流程，中级要求，主要是启动中做的事有哪些关键步骤
• 深刻理解Zygote的工作原理，高级要求，主要是怎么启动进程的，怎么与其他进程通讯

Zygote的作用

他的作用非常简单就两点

• 启动SystemServer
• 孵化应用进程

如果答出了这两点那就是及格了。但可能大部分朋友只知道第二点，第一点就不是那么清楚。其实SystemServer也是Zygote启动的，因为SystemServer需要用到Zygote准备好的系统资源：包括我们常用的一些类、注册的JNI函数、主题资源及一些共享库等等，直接从Zygote继承过来自己就不需要重新加载过来，那么对性能将会有很大的提升。

Zygote的启动流程

在说Zygote启动流程之前，我们可以明确一个概念：启动三段式，这个可以理解为Android中进程启动的常用套路，分为三步骤

1. 进程启动
2. 准备工作
3. LOOP循环

其中LOOP作用是不停的接受消息，处理消息，消息的来源可以是Soket、MessageQueue、Binder驱动发过来的消息，但无论消息从哪里来，它总的流程都是去接受消息，处理消息。

这个启动三段式，他不光是Zygote进程是这样的，只要是有独立进程的，比如说系统服务进程，自己的应用进程都是这样的。

Zygote进程是怎么启动的？

Zygote进程的启动，得感谢init进程。init进程是它是linux启动之后用户空间的第一个进程。下面看一下启动流程

1. linux启动init进程
2. 加载init.rc配置文件
3. 启动配置文件中定义的系统服务，其中Zygote服务就是定义在配置中的
4. init进程通过fork + execve 系统调用启动Zygote

在分析具体系统源码实现之前，我分享一个看源码很方便网站Android社区：www.androidos.net.cn

下面列举了本文需要阅读的源码文件路径，供大家方便查找。

1
2
3
4
5
6

platform/system/core/rootdir/init.zygoteXX.rc
platform/system/core/rootdir/init.rc
platform/frameworks/base/cmds/app_process/app_main.cpp
platform/frameworks/base/core/jni/AndroidRuntime.cpp
platform/libnativehelper/JniInvocation.cpp
platform/frameworks/base/core/java/com/android/internal/os/ZygoteInit.java

加载Zygot的启动配置

在init.rc 文件中会import /init.${ro.zygote}.rc，init.zygoteXX,XX指的是32或者64，对我们没差我们直接看init.zygote32.rc即可。配置文件比较长，我这里做了截取保留了Zygot相关的部分。

1
2
3
4
5
6
7

service zygote /system/bin/app_process -Xzygote /system/bin --zygote --start-system-server
    class main
    socket zygote stream 660 root system
    onrestart write /sys/android_power/request_state wake
    onrestart write /sys/power/state on
    onrestart restart audioserver
    writepid /dev/cpuset/foreground/tasks

• service zygote：是进程名称，
• /system/bin/app_process：可执行程序的路径，用于init进程fork，execve调用
• -Xzygote /system/bin –zygote –start-system-server 为它的参数

启动方式

获取到启动配置后才会进行正式启动，启动方式有两种

• fork + handle
• fork + execve

首先都会调用fork创建新的进程，比较奇特的是它会返回两次。

• 子进程一次，返回的pid是0 父进程一次，返回的pid是子进程的pid
• 对于handle默认的情况，子进程会继承父进程的所有资源，但当通过execve去加载二进制程序时，那父进程的资源则会被清除

信号处理-SIGCHLD。

当父进程fork子进程后，父进程需要关注这个信号。当子进程挂了，父进程就会收到SIGCHLD，这时候父进程就可以做一些处理。例如Zygote进程如果挂了，那父进程init进程就会收到信号将Zygote进程重启

Zygote进程启动后做了什么

主要分为两部分Native层处理和Java层处理。

先来看一下Native层的处理

• 启动Android虚拟机
• 注册Android的JNI函数
• 进入Java层

在app_main.cpp文件，AndroidRuntime.cpp文件。我们可以找到几个主要函数名

1
2
3
4

JNI_CreateJavaVM   // 创建启动虚拟机
jniRegisterNativeMethods(env, "com/android/internal/os/ZygoteInit",
        methods, NELEM(methods)) // 通过反射获取ZygoteInit对象
env->CallStaticVoidMethod(startClass, startMeth, strArray);//调用main函数,进入Java层

在应用进程中并不需要创建虚拟机，因为应用进程是Zygote进程孵化出来的，继承了父进程的拥有虚拟机，只需要重置数据即可。

接着看一下Java层的处理，具体可参考ZygoteInit文件的main方法

• 预加载资源，常用类库、主题资源及一些共享库等
• 启动SystemServer进程
• 进入Socket 的Loop循环 会看到的ZygoteServer.runSelectLoop(…)调用

Zygote的工作原理

Zygote的LOOP循环会一直监听Socket中的内容，所以Zygote与其他进程的通信是通过Socket的，工作原理举个例子

1. 桌面应用点击某应用图标，若应用没有启动进程
2. AMS会通过Socket通知Zygote进程
3. Zygote进程接受到消息后fork出一个应用进程
4. 执行应用进程的ActivityThread的main方法

要注意的细节

Zygote fork要单线程进行，在fork时Zygote会将除主进程外的所有线程都停了成功后重启，因为对于新创建的子进程而言只有主线程，避免多线程的死锁问题

Zygote的IPC没有采用binder，而是本地Socket

最后

看到最后，我相信你一定对Zygote有一定了解了吧。回头看看第一部分的考查内容讲讲呗，对于每一个点的重点我都细心的为你做了高亮。还有纸上得来终觉浅，绝知此事要躬行。本文参考了Android api28的源码，希望你也去踩着点过一遍源码，肯定能加深理解！

OSI 七层网络模型

1. 应用层： 为用户进程提供网络服务
2. 表示层：负责数据的转化，数据的压缩/解压，数据的加密/解密等
3. 会话层：负责会话的建立，管理，销毁等服务
4. 传输层：基于TCP/UDP进行 端口对端口的传输
5. IP层：数据打包成IP数据报，在路由器/交换机上传输
6. 数据链路层:
7. 物理层：

TCP/IP 网络模型

1. 应用层
2. 传输层
3. IP层
4. 数据链路层

DNS解析

DNS解析过程

HTTPDNS优化

HTTP 的版本区别

HTTP1.0与 HTTP1.1

1. 缓存优化
2. 网络带宽及网络连接都优化
3. host请求头添加
4. 支持长连接（串行单线程处理请求，可以同时发起多个请求，但必须等待前一个请求处理完，才会处理新的请求，否则只能被阻塞）

HTTP1.1与HTTP2.0

1. 新的二进制文件
2. 多路复用（多个请求可以在一个连接上并行执行，某个请求耗时严重，不会影响到其他连接的正常执行）
   1. 做到了延迟的优化，TCP连接是慢启动，因此突发性和短时性的http连接不高效，通过复用连接可以更有效的使用TCP
3. Header压缩 （一个页面有100个资源要加载，而每次请求都有1kb的消息头，则至少要消耗100kb获取请求头，http2.0，维护了一个字典，用以差量更新http头部）
4. 服务端推送（服务端会主动把客户端所需要的资源一起发给客户端）

TCP 与UDP

TCP 是面向连接的，可靠，慢，占用头部字节20多

UDP是无连接的，尽最大交付，快，占用头部字节少8

TCP三次握手

TCP四次挥手

TCP与UDP比较

算法的学习

跟我学：LeetCode刷题大法

什么是算法

算法面试准备

刷题

自己的LeetCode代码库

比较好的算法总结

题目索引

跟我学：LeetCode刷题之1.两数之和

跟我学：LeetCode刷题之2.两数相加

跟我学：LeetCode刷题之3. 无重复字符的最长子串

protocol buffer 使用和原理

深入学习Android Framework

跟我学：深入Android Framework之谈谈对Zygote的理解

跟我学：Android高级面试之说说Android系统的启动流程