2.面试中的算法模板

书：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