华为2020校招笔试编程题 看这篇就够了(下)

背景

接上篇的背景，继续看看，首先把大纲再发一份出来。

干货（高级部分）

1. 高级数据结构概念，基本操作，以及优缺点等

1.1 二叉查找树

简单题

1. （对称二叉树）
2. （平衡二叉树）
3. （翻转二叉树）

中等题

1. （二叉树的中序遍历）
2. （不通的二叉搜索树）
3. （二叉搜索书迭代器）
4. （从二叉搜索书到更大和树）

---

1.2 堆

简单题

1. （数据流中的第K大元素）
2. （最后一块石头的重量）

中等题

1. （根据字符出现频率排序）
2. （前K个高频单词）
3. （重构字符串）

---

1.3 图论

简单题

1. （不邻接植花）
2. （找到小镇的法官）

中等题

1. （地图分析）
2. （颜色交替的最短路径）

---

2. 常用算法及思想

2.1 排序算法（快速、插入、堆排序等）

简单题

1. （数组的相对排序）
2. （两个数组的交集）
3. （两个数组的交集2）

中等题

1. （颜色分类）
2. （合并区间）
3. （重构字符串）

---

2.2 迭代、递归的思想

简单题

1. （二叉搜索树的范围和）
2. （第 N 个泰波那契数）

中等题

1. （第K个语法符号）
2. （划分为k个相等的子集）

---

2.3 分治的思想（如：二分查找、归并排序等）

简单题

1. （二分查找）
2. （x的平方根）

中等题

3. (Pow(x,y))
4. (搜索二维矩阵)
5. （寻找重复数）

---

2.4 搜索算法（深度，广度）

简单题

1. （二叉树的所有路径）
2. （对称二叉树）

中等题

1. （路径总和 II）
2. （二叉树的层次遍历）

---

2.5 贪心算法

简单题

1. （最后一块石头的重量）
2. （玩筹码）

中等题

1. （根据身高重建队列）
2. （任务调度器）

---

2.5 动态规划(背包0-1难度)

简单题

1. （爬楼梯）
2. （最大子序和）

中等题

1. （丑数2）
2. （不同的二叉搜索数）

---

附录：吐血整理的笔记

用数据结构和算法

数据结构：字符串、数组、栈、队列（包括优先队列、双端队列）、链表、哈希表、Set、二叉树。最小堆最大堆的问题都可以用优先队列来解题，堆的调整我还是有点晕的。

算法：二叉树的前/中/后序/层次遍历；图的BFS、DFS、最短路径算法、最小生成树；回溯、递归、动态规划等。排序算法基本数据结构有现成轮子，了解原理就好。

这块重点看官方的考试范围。

对于JAVA，重点搞清楚常用的几大集合类特点（是否有序、什么顺序、是否允许重复），才能在解题过程中立即想到某个特性需用哪个数据结构、哪个类库。

刷题过程中总结的典型解题思路（持续刷，有经验的请绕路）

1. 滑动窗口篇

滑动窗口是一种双指针解题思路，采用left、right左右两个指针，表示一个滑动的窗口之最左端和最右端（初始化 left = right = 0）。左右指针轮流前进，窗口大小增增减减（窗口大小可固定可动态，依据题目要求），窗口不断向右滑动，最终可实现在线性时间内获得问题最佳解。有时题目需要辅以HashMap、数组进行判存在性、可行性。

推荐文章：滑动窗口

2.链表篇

链表最基础的操作：创建、插入、删除是必须掌握的。

常用解题方法主要是采用快慢指针（仅涉及查找操作）、增加辅助头节点（涉及增删改操作），在此基础上对怎么判断链表有环及入环点、中间节点、倒数K个等解题小技巧建议熟练掌握。链表题一定要白纸上画，画出来就能写出来。

推荐文章：链表

3.图篇

推荐程序员小灰2019年关于图的几篇帖子，讲的非常通俗易懂了

4. 二叉树篇

二叉树感觉没啥技巧，基本功扎实就好。重点是前/中/后序/层序遍历，LeetCode上会基于这些生出些变种，比如Z字形打印，从前序与中序，从中序和后序遍历恢复二叉树等，剑指offer和小灰上有典型讲解。

5. 回溯法篇

回溯算法是类似枚举的搜索尝试过程，按照深度优先搜索的策略，从根结点出发深度探索解空间树，当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去；如果该节点不包含问题的解，就“回溯”返回，即退回一步重新选择，尝试别的路径。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

适应题型：求全排列组合

模板：刷题过程中看到LeetCode里有个不错的模板，待补充。

6. 动态规划篇

动态规划就是下一状态可以根据上一状态，或之前几个状态获取到的一种推理过程。可以看下详解动态规划——邹博讲动态规划一文，其中讲了路径、硬币、最长子序列。

虽然多次考到，我狠刷了七八道，自己推理状态转移方程总是晕–#，好在DP能解的问题，还有其它轮子可以解。

7. 位运算篇

位运算很基础了，典型的位运算技巧与应用，但平时工作中用的偏少，温故下：位运算