|
面试心态:
1. 如果遇到做过，非常熟悉的算法题，和面试官沟通清楚题意，讲清楚思路，然后开始写代码，做到bug free.
2. 如果遇到见过，但不是那么容易的算法题，比如Leetcode 4题， 将中文数字转换为数字，那么不要急，多列举一些case，和面试官多交流，沟通。尽可能说清楚思路，然后把代码写出来。
3. 如果遇到从来没见过的题目，不要慌，冷静下来，慢慢想，一个小时的时间，先沟通清楚题目，想清楚思路，然后和面试管说思路，如果实在不会，问面试管又没有提示，然后我们自己把代码写出来。
1. 链表深拷贝（可能有环，可能无环）
Easy，用hashmap记录新拷贝节点与原始节点
2. 给定一个sorted array，整型，要求输出缺失的数字。比如输入[5,6,7,11,13]，输出8,9,10,12
Easy，开一个辅助空间，或者额外变量
3. 剑指offer 46，输出是所有的可生成的字符串，但是a是对应的1，所以要考虑字符串以0开头和连续两个0的情况
Medium 偏easy， dfs回溯，注意沟通无效情况。
4. 判断一个输入字符串是不是有效的ipv4地址（要考虑很多情况返回False的，c++还有大数问题）
Medium 255.1.225.1, 分为用split和不用split解析两种，C++实现略有难度，边界情况比较多。
5. 检查一棵二叉树是否是平衡二叉树
Easy 在求最大深度的同时，判断是否是平衡二叉树。
6. 一组柱状图中最大矩形的面积
Medium偏hard 枚举最大高度，然后单调栈优化，时间复杂度O(n^2) 优化到O(n）
7. 数字三角形找最大和路径
easy dp
8. 二叉树中找两个节点的最近公共祖先节点
Medium，经典题目
9. 找给定二叉树中的特定节点中序遍历后的下一个节点
1
2 3
3 4 5 6
5
如果这个二叉树有右子数，那么右子数最左侧的节点就是他的下一个节点
如果这个树没有右子数，并且是父节点的左子数，那么下一个节点就是父亲节点，如果不是，就要一直向上找，直到找到
10. 124. 二叉树中的最大路径和
分解，每次函数求从根节点出发，到左子数或者右子数任意节点的最大值，然后再递归的同时，记录答案
class Solution {
public:
int res = INT_MIN;
int maxPathSum(TreeNode* root) {
dfs(root);
return res;
}
int dfs(TreeNode* root){
// 这个函数返回从root出发到任意一个节点最大路径和
if(root==NULL) return 0;
int left = max(0,dfs(root->left));
int right = max(0,dfs(root->right));
res = max(res,left+right+root->val);
return max(left,right)+root->val;
}
};
11.有n个二维平面上的点和距离d，将它们分成k组。若两点间的距离小于等于d，则这两个点在一组；如果点A和点B在一组，点B和点C在一组，则点A和点C在一组。算法返回每个点所在组的编号(0..k-1)
并查集， 并查集在find的同时做路径压缩：
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool isSameSet(int x, int y){
return find(x) == find(y);
}
void union(int x, int y){
p[find[x]] = y;
}
12.最长回文子串
中心枚举法和动态规划方法
13. 反转链表
easy
14. string转double
15. 二叉树的之字形遍历
BFS
16. 找出正整数数组中和=K的连续子数组数量
前缀和处理
17. 删除二叉搜索树的根节点
18. 大数加法
简单模拟
19. 要求这些区间如果有交集的要合并，返回合并后的区间集合
20. 枚举子集
回溯，递归
21. 给一个数组，求所有连续子序列的最小值的和
22. 非递归中序遍历二叉树
23. LeetCode 26，三数之和
24. 第一题是给定一个数组，求数组当中的峰值，所谓峰值就是这个数比他左右两边的数都大
25. 第二题是给定一组用户和每个用户的好友列表，输出每个用户之间的共同好友的关系。比如A与B有3个共同好友，就输出A,B: 3 并查集
26. 第三题是给定一组数字，然后把数字分为三组，其中两组总和相等，要求第三组的总和尽可能小。
27. 现在有一个M*N的点阵，问从左下角走到右上角的最短路径一共有多少条。
28. 给一个不含重复元素的数组，如果该数组满足下面两个条件中的任意一个，就返回true
29. 最简单的股票交易问题
30. 二分 在排序数组中用二分查找找到某数字的第一个位置
31. 一个数组中，除了一个数出现三次，其余都出现四次，找出这个数
32. 现给出一个扩展字符和一系列原始字符，求出原始字符中哪些可以是该扩展字符的原始字符
33. 判断单向链表中时候有环
Easy
34. 给出两棵二叉树，判断一棵树是否为另一棵树的子树。
35. 二十六进制转换成十进制
36. 旋转数组中找到最小的元素 (二分）
37. 二维数组二分排序
38. 定一个数组找到一个点，使得这个点两边的和相同，
39. 字符串反转：字符串中用空格分隔每个单词，空格数量至少一个，输出反转后的字符串，要求反转后单词之间的数量与之前不变。
40. 机器人走棋盘
41. 求无序数组中前K个最大值 topK问题
42. 输入一个字符串，输出去掉所有空格后的字符串
双指针
43. 一个字符串大整数，判断是否可以通过交换任意字符被8整除？
44.
| 给一个数组 A = [2, 4, 8, 3] 输出一个数组 B，其中 B[i] 值为 A 中小于 A[i] 的元素值之和，B 应该为 [0, 5, 9, 2] |
45. Leetcode 283， 双指针算法
46. 二叉树直径，LeetCode 543
47. 乐扣的767题 贪心题目
48. 一千二百万亿五百万六千七百零二十，转化为数字
49.
| 
转播
