- 我会在README里面写总结跟一些技巧 大量的细节跟注释都在代码附近，遵从一个知识离代码最近的原则
- 包名包含了问题的名字，所有的类都是Solution 兼容leetcode，通常一个包下 只有一个Solution类
- 建议clone下来配合IDEA跟README食用
- 最近看了很多题解深感国内大厂受硅谷白板编程之风所害， 纷纷搞起了算法面试题，在这里分享一些我做题的经验， 先声明我自己也是一个菜鸡，我个人的算法能力局限于 二分查找 快速排序 图搜索 生成树 skip-list 等简易中等难度的范畴， 仅能应付常规面试题。
-
在面试3-5年的Java开发岗位，算法面试可能大多着重于对基础数据结构 ArrayList LinkedList Stack Queue Map 的应用跟原理的掌握，这个我不推荐大家去读JDK的源代码， 里面具体的实现 其实涉及到生产实践中大量的改进，细节十分多，例如JDK8的HashMap 在达到8个hash冲突链表后会转成红黑树， 而在理论学习的阶段中，应该了解除 头接链表法解决hash冲突 其它解决hash冲突的方式， 这里我推荐大家阅读 <<算法>> 第四版，里面有对基础的数据结构算法有详细的介绍， 这本书着重于应用跟理解，不像算法导论大篇幅的描述算法的数学证明。 从工程师的角度来讲，工程师在掌握算法的原理以及实现的思想后，能够熟练运用这些工具解决问题即可， 至于在数学的基础上对算法做出正确性的推导，我觉得并不是一个工程师应该所必须掌握的能力。
-
leetcode应偏向中等跟简单难度的题目，这些题目出现的概率比较大，应该尽量把这些题目都覆盖掉。
-
待补充
-
了解基本的算法复杂度分析，了解O(N) O(N^2) O(LogN) 等复杂度
-
递归不好写，容易写错， 必须要掌握写对递归的三要素 1.递归一定要有一个终结条件，例如dfs搜索，必然会有一个节点其子节点为空，此时就是递归调用的出口 2.每一次递归之后，问题的解空间是在不断缩小的 3.父调用的解空间不能与其子调用的问题重叠 （这个很难文字解释清楚，后续可能会做视频）
-
二分搜索有模板，可以背下来，如果不确定，可以把目标值跟 mid low指针上的元素都比较一下
-
一些题目其实是有一固定解题套路的，例如在你掌握一个深度搜索 广度搜索的模板之后， 可以通过这个模板来解决大量图相关的问题，当然可能在这上面可能又涉及到减枝 用HashMap去重等操作。
-
很多算法都是从朴素算法出发演化来的，例如KMP求子字符串，同样时间复杂度的RK求字符串，也都是根据朴素的双重循环比对 字符串是否相等演化而来，在学习任何算法前，可以先了解其相关朴素算法的实现，可以加深对算法数据结构的认识
-
手写代码跟白板代码，一定要着重于可理解性，一个著名的观点是代码是写给人看的，顺便让机器执行一下，在算法面试中，如果 面试官对 空间复杂度 时间复杂度没有特殊要求，应该尽量选最好解释且最容易实现的方式去写，如果你写的代码不能通过简单的test case证明其正确性， 那么面试可能会大打折扣，其实短短几十分钟的时间，很难让你写出一个炫技的实现。
-
无论任何时候先处理dirty-case，就是防御式编程，不相信任何人提交参数的正确性，这种编程思维会让你受益终身。
-
通常应该写一个问题规模比较小的test-case验证思路
-
待补充
-
算法题的解答，其实要在白板编程时写出正确的代码，最好结合算法的思想去背诵一些模板，
-
二分查找模板
public class BinarySearch { //二分查找模板
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target){
return mid;
}
// 如果你面试记不住 可以顺便比较一下 if nums[low] == target
else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
//
//循环条件： left <= right
//中间位置计算： mid = left + ((right -left) >> 1)
//左边界更新：left = mid + 1
//右边界更新： right = mid - 1
//返回值： mid / -1- bfs广度搜索优先模板
public class Solution {
class TreeNode {
public int val;
public TreeNode(int val) {
this.val = val;
}
public TreeNode left;
public TreeNode right;
}
// 0 <- 第一次从队列里面取到0 然后把子节点1放回去
// / \
// 1 null <- 第二次从队列里面取到1 然后把子节点 3 4 放回去
// / \
// 3 4 <- 第三次从队列里面取到3，4 因为其没有子节点 所以队列为空 返回 得到count = 3
// null -> layer
// 这里其实思路很简单，因为bfs是层序遍历，每次针对队列的循环，都是取得同层级别的节点，除开二叉树 多叉树亦是如此
//求二叉树的最大层数 算是bfs模板题
public int calculateBinaryTreeLayer(TreeNode node) {
if (node == null) {
return 0;
}
//不管怎么样通常bfs是要进队的
Queue<TreeNode> queue = new LinkedList<>();
queue.add(node);
int count = 0;
while (!queue.isEmpty()) {
List<TreeNode> polls = new ArrayList<>();
//这个是取出当前这一层所有的左右节点 实际上针对多叉树 其思想也是一样
while (!queue.isEmpty()) {
polls.add(queue.poll());
}
//把所有节点的子节点再塞回去
polls.forEach(poll -> {
if (poll.right != null) {
queue.add(poll.right);
}
if (poll.left != null) {
queue.add(poll.left);
}
});
//计数+1
count++;
}
return count;
}
/**
* not full binary tree
*/
@Test
public void testCalculateBinaryTreeTestCase2() {
TreeNode top = new TreeNode(0);
top.left = new TreeNode(1);
top.right = new TreeNode(2);
top.left.left = new TreeNode(3);
top.left.right = new TreeNode(4);
Assert.assertEquals(3, calculateBinaryTreeLayer(top));
}
/**
* full binary tree
*/
@Test
public void testCalculateBinaryTreeTestCase1() {
// 0
// / \
// 1 2
// / \ / \
// 3 4 5 6
// null -> layer
TreeNode top = new TreeNode(0);
top.left = new TreeNode(1);
top.right = new TreeNode(2);
top.left.left = new TreeNode(3);
top.left.right = new TreeNode(4);
top.right.left = new TreeNode(5);
top.right.right = new TreeNode(6);
Assert.assertEquals(3, calculateBinaryTreeLayer(top));
}
}