书：cracking the coding interview 豆瓣 亚马逊
网站：careercup
代码风格
代码块可分为三大块：异常处理（空串和边界处理），主体，返回值
代码风格（可参考Google的编程语言规范）
- 变量名的命名（有意义的变量名）
- 缩进（语句块）
- 空格（运算符两边）
- 代码可读性（即使if语句只有一句也要加花括号）
《代码大全》中给出的参考
基本代码素养
- 关于空格
for，if，else，while等记得加空格符
用空行把大块代码分成逻辑上的“段落” - 关于括号
c指针中的指针符靠近类型名，如写成int* p，而不写成int *p
一个函数只专注做一件事 - 关于命名
驼峰写法
实战算法策略
- 总结归类相似题目
- 找出适合同一类题目的模板程序
- 对基础题熟练掌握
再看一道简单题
Memmove
void *memmove(void *dest, const void *src, size_t n)
{
// implementation here
}
陷阱
- 内存重叠的处理
- 临时变量太多或者没有安全释放
- 没有测试内存越界
- 指针操作不熟悉
正确写法
void *memmove(void *dest, const void *src, size_t n)
{
char *p1 = dest;
const char *p2 = src;
if (p2 < p1) {
p2 += n;
p1 += n;
while (n-- != 0)
*--p1 = *--p2;
} else {
while (n-- != 0)
*p1++ = *p2++;
}
return p1;
}
排列组合模板
Subsets
{1,2,3}
{{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
转化为程序问题
Subsets
void subsets(int[] num) {
ArrayList<Integer> path = new ArrayList<Integer>();
Arrays.sort(num);
subsetsHelper(path, num, 0);
}
void subsetsHelper(ArrayList<Integer> path, int[] num, int pos) {
outputToResult(path);
for (int i = pos; i < num.length; i++) {
path.add(num[i]);
subsetsHelper(path, num, i + 1);
path.remove(path.size() - 1);
}
}
Subsets-Sample
对递归图的理解
Unique Subsets
{1,2,2}
{{},{1},{2},{1,2},{2,2},{1,2,2}}
Unique Subsets
- 与Subsets有关，先背下Subsets的模板
- 既然要求Unique的，就想办法排除掉重复的。
- 思考哪些情况会重复？如{1,2(1),2(2),2(3)}，规定{1,2(1)}和{1,2(2)}重复，{1,2(1),2(2)}和{1,2(2),2(3)}重复。观察规律。
- 得出规律：我们只关心取多少个2，不关心取哪几个。
- 规定必须从第一个2开始连续取（作为重复集合中的代表），如必须是{1,2(1)}不能是{1,2(2)}
- 将这个逻辑转换为程序语言去判断
Unique Permutations
[1,2,2]
[1,2,2],[2,1,2],[2,2,1]
排列组合模板总结
- 使用范围
几乎所有的搜索问题 - 根据具体题目要求进行改动
什么时候输出
哪些情况需要跳过
使用该模板的题目
- Combination Sum
- Letter Combination of a Phone Number
- Palindrome Partitioning
- Restore IP Address
