字节秋招高频算法汇总（基础篇）

更多大厂面试内容可见 -> http://11come.cn

字节秋招高频算法汇总

接下来讲一下 字节秋招 中的高频算法题，分为三个部分： 基础篇 、 中级篇 、 进阶篇

目的就是为了应对秋招中的算法题，其实过算法题的诀窍就在于 理解的基础上 + 背会

看到一个题目，首先要了解题目考察的算法是什么，这个算法要理解，至于具体实现的话，就靠背会了（多写、多练），没有什么捷径，可以 尝试一个题目手写 3-5 遍 ，加强一下记忆！

还有一点要注意的是，在大厂的笔试中， 可能考察算法的方式是 ACM 模式 ，这一点和力扣上不同，ACM 模式需要我们自己去引入对应的包，以及自己写算法，力扣是将方法框架给定，只需要在方法内写代码就可以了，这一点要注意！

基础篇

字节的算法题相对于阿里来说更加丰富一些，之前在阿里的算法题中是没有包含 快速查找 、二分查找 的题目的，所以这里可以重点看一下，考察算法有：

• 贪心
• DFS 、 BFS ：使用 DFS 搜索树、反转字符串、BFS 遍历节点、DFS 返回二叉树右视图
• 双指针
• 快速排序
• 二分查找

LC 455. 分发饼干（简单）

题目描述：

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
1
2
3
4
5
6

这道题目是典型的 贪心 问题

题目要求 饼干尺寸 > 孩子的胃口 才可以满足孩子，那么可以对 饼干尺寸 、孩子的胃口 都 从小到大 进行排序

贪心来做 的话，将小饼干优先分给胃口小的孩子，这样可以将尺寸大的饼干留在后边给更大胃口的孩子吃

证明这个 贪心算法 正确性的话，可以这么想，如果将一个较大的饼干分给这个胃口较小的孩子，那么为什么不将一个较小的饼干分给这个胃口较小的孩子？显然先分配较小的饼干，可以将大饼干留给后边胃口较大的孩子， 这样既可以满足这个胃口较小的孩子，也可以更大几率满足后边胃口较大的孩子

贪心类的问题虽然看着很简单，但是要证明我们这样贪心去做是正确的比较难，因此看到一个题目发现像贪心题，可以先尝试贪心做一下，如果通过不了，说明贪心不是正解，再尝试其他方法

代码如下 ：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // 对饼干、孩子的胃口进行排序
        Arrays.sort(g);
        Arrays.sort(s);
        int n = g.length;
        int m = s.length;
        // 记录结果
        int res = 0;
        // 记录遍历的孩子的下标
        int idx = 0;
        // 遍历饼干
        for (int i = 0; i < m; i ++) {
            // 如果第 i 个饼干可以喂饱第 idx 个孩子，就将结果 + 1
            if (idx < n && g[idx] <= s[i]) {
                res ++;
                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

LC 199. 二叉树的右视图（中等）

题目描述：

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
1
2

这道题目需要拿到二叉树的 右视图 ，也就是右边的第一个节点，不过要注意右边的第一个节点不一定是右节点，也有可能右节点为空，那么就是左节点了，如下：

那么解题思路的话，有两种 dfs 或者 bfs

DFS 解决

先说 dfs 解决的思路，可以按照 根节点 -> 右节点 -> 左节点 的顺序进行遍历

由于每一层我们只需要加最右边的节点，但是遍历的话，会遍历这一层的多个节点

因此通过一个 depth 变量来记录遍历的深度，由于每一层都会添加一个节点，这里假设节点放在 res 数组中了，那么如果 depth == res ，说明上一层刚遍历完，现在遍历的是新的一层的第一个节点，我们定义的递归顺序就是先便利右节点，因此一定会先遍历 右视图 的节点，将该节点加入 res 中即可

代码如下 ：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0);
        return res;
    }
    public boolean dfs(TreeNode root, int depth) {
        // 设置递归终止条件
        if (root == null) {
            return false;
        }
		// 如果当前遍历的节点的新的一层的第一个节点
        if (depth == res.size()) {
            res.add(root.val);
        }
        // 先遍历右节点，深度 + 1
        dfs(root.right, depth + 1);
        // 再遍历左节点，深度 + 1
        dfs(root.left, depth + 1);
        return true;
    }
}
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

BFS 解决

BFS 来解决的话，可以将每一层的节点加入到队列中，先加入左节点，再加入右节点，那么队列中的最后一个元素肯定就是 右视图 了，加入到结果集中即可

代码如下 ：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    public List<Integer> rightSideView(TreeNode root) {
        // 如果根节点是空的话，就直接返回就好了
        if (root == null) return res;

        // 先将根节点加入，进行 bfs
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 计算队列中元素的数量 size，这些元素都是同一层的节点，对他们进行遍历，拿到下一层的节点
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                // 弹出元素，加入左、右子节点
                TreeNode cur = queue.poll();
                // 如果左、右节点不为空的话，就加入队列
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                // 如果是当前队列的最后一个节点，就是右视图的节点，加入结果中
                if (i == (size - 1)) {
                    res.add(cur.val);
                }
            }
        }
        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
32
33
34
35
36
37
38
39
40
41
42

LC 169. 多数元素（简单）

题目描述：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入：nums = [3,2,3]
输出：3
1
2

这道题目要找出数组中的多数元素，最简单的解题思路 就是直接对 nums 数组进行排序，那么这个多数元素一定在数组中间的位置，也就是 [n/2] 的位置

还有一个思路就是 摩尔投票法思路 ：先初始化一个候选人 candidate ，这个候选人默认为 nums[0] ，初始化一个投票数 count 为 1，那么每当碰到相同的数，就将 count + 1 ，碰到不同的数，就将 count - 1 ，如果 count 减为 0 之后，就更换候选人，并将票数 count 置为 1

这样子由于数组中一定有一个 多数元素 ，这个多数元素和其他元素抵消，最后一定会剩余一个 多数元素 ，作为候选者返回即可！

直接排序做的话，时间复杂度是 O(NlogN) ，使用摩尔投票法做的话，时间复杂度是 O(N)

这里写一下 摩尔投票法 的代码：

class Solution {
    public int majorityElement(int[] nums) {
        // 初始化候选者、票数
        int candidate = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i ++) {
            // 如果相同就 + 1
            if (nums[i] == candidate) {
                count ++;
            } else {
                // 否则就 -1
                count --;
            }
            // 如果票数为 0，就更换候选者
            if (count == 0) {
                count = 1;
                candidate = nums[i];
            }
        }
        return candidate;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

LC 215. 数组中的第K个最大元素（中等）

题目描述：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入: [3,2,1,5,6,4], k = 2
输出: 5
1
2

这道题目可以看作是一个模板题目了，选择数组中第 K 大的元素

可以借助快速排序的模板来做，快速排序的话是先将数组分为两段，一段 <=x，另一端 >=x，再对每一段继续递归分段进行排序，过程如下：

先找到数组中的一个数，定义为 x ，之后开始循环：从左边开始遍历找到第一个大于 x 的数，从右边开始遍历找到第一个小于 x 的数，将这两个数进行互换，直到 左右指针碰撞 ，则此时整个数组被分为 <= x 和 >= x 的两段区间，如下：

由于快排是从小到大进行排序，所以这里我们先假设 要找第 k 小的数 ，那么就判断 第 k 小的数 左边区间还是右边区间，之后再遍历指定区间找到第 k 小的数即可

题目中要求找 第 k 大 的数，但是我们实现的算法找的是 第 k 小 的数，因此可以令 k = (n-k+1) ，这样题目要求找第 k 大的数就转换为了找第 k 小的数

这道题目和快速排序一样，都是较常见的模板题，可以将代码直接背了

代码如下：

class Solution {
    public int findKthLargest(int[] q, int k) {
        int n = q.length;
        // 题目要求找第 k 大的数，也就是第 n-k+1 小的数，我们的算法是找第 k 小的数，所以这里转化一下
        return quickSelector(q, 0, n - 1, n-k+1);
    }
    // 找到第 k 小的数
    public int quickSelector(int[] q, int l, int r, int k) {
        // 如果左右指针碰撞，就返回 q[l]
        if (l >= r) return q[l];
        // 定义左右指针，定义 x 为数组中间的位置，遍历数组，将数组分为 <=x 和 >=x 的两段区间
        // (l + r) >> 1 表示右移一位，也就是除以 2
        int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
        while (i < j) {
            do i ++; while(q[i] < x);
            do j --; while(q[j] > x);
	        // 开始交换元素
            if (i < j) {
                int tmp = q[i];
                q[i] = q[j];
                q[j] = tmp;
            }
        }
        // 如果左边区间长度大于 k，那么第 k 小的数就在左边区间
        if ((j-l+1) >= k) return quickSelector(q, l, j, k);
        // 否则，在右边区间，将 k 减去左边区间的长度即可（左边区间的数全都小于右边区间的数）
        else return quickSelector(q, j + 1, r, k - (j-l+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

LC 103. 二叉树的锯齿形层序遍历（中等）

题目描述：

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
1
2

这道题目就是一层从左向右遍历，下一层从右向左遍历，交替进行即可

那么我们只需要记录 已经遍历的层数 depth ，就可以知道当前这一层是以什么顺序遍历了

使用 BFS 来做，先遍历左子树、再遍历右子树，只不过在记录结果的时候：

• 如果是 从左向右 遍历的话，就将节点值加入到双向链表的最后
• 如果是 从右向左 遍历的话，就将节点值加入到双向链表的最前

按题目中给的节点，遍历流程如下：

代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        // 判空
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            // 已经遍历的二叉树深度
            // 如果 depth 是偶数，从左到右遍历
            // 如果 depth 是奇数，从右到左遍历
            int depth = res.size();
            LinkedList<Integer> tmp = new LinkedList<>();
            for (int i = 0; i < n; i ++) {
                TreeNode cur = queue.poll();
                // 从左到右遍历
                if (depth % 2 == 0) tmp.addLast(cur.val);
                // 从右到左遍历
                else tmp.addFirst(cur.val);
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            res.add(tmp);
        }
        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
32
33
34
35
36
37
38
39
40
41
42
43
44

LC 33. 搜索旋转排序数组（中等）

题目描述：

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
1
2

二分查找只能在有序数组中查找 ，这道题目中的数组并不是有序的，不能直接通过 二分 来解决，因此要想办法将数组变为有序的，再使用 二分解决

数组是按照某一个节点进行旋转了，因此数组是分为了两个有序区间的，那么我们只需要判断 target 和 nums[0] 的值就可以判断目标值在哪一个有序区间了：

• 如果 target >= nums[0] ，那么目标值在左边有序区间
• 如果 target < nums[0] ，那么目标值在右边有序区间

知道目标值在哪个区间了，就可以在该区间内进行二分查找了

代码如下：

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        // 先二分，找出来第一个区间中最大值，也就是第一个区间的右端点
        int l = 0, r = n - 1;
        while (l < r) {
            // 如果 r = mid-1，这里要 mid = l + r + 1 >>1
            // 如果 r = mid，这里要 mid = l + r >> 1
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }   
        // 此时 l 和 r 就是左边区间的右端点
        // 如果需要找的值在左边区间，就将二分区间设置为[0, r]
        if (target >= nums[0]) l = 0;
        // 如果需要找的值在右边区间，就将二分区间设置为[l+1, n-1]
        else {
            l ++; 
            r = n - 1;
        }
        // 开始二分查找目标值
        while (l < r) {
            int mid = l + r + 1 >> 1;
            // 如果当前 mid 节点 <=target，说明 target 值在右边，令 l=mid
            if (nums[mid] <= target) l = mid;
            // 如果当前 mid 节点 >target，说明 target 值在左边，令 r=mid-1
            else r = mid - 1;
        }
        // 这里判断使用 r 而不是 l
        //是因为 如果数组中只有 1 个值，上边两个二分都不会走，如果走到 if 条件中执行了 l++，就会导致数组越界
        if (nums[r] == target) return l;
        return -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
33
34