date: 2016-06-02 14:00
剑指 offer
何海涛blog: http://zhedahht.blog.163.com/
源码: http://download.csdn.net/download/cadcisdhht/3809923
读书笔记
程序的鲁棒性很重要, 要注意 边界条件, 特殊输入(null, 空字符串), 错误处理
面试相关
- coding
思考清楚再开始编码
代码命名&缩进
能够单元测试
- 面试
规划好路线和出行时间
穿着得体
注意面试邀请函里面的面试流程
准备几个问题
- 项目经验(STAR)
situation: 简短的项目背景
task: 自己完成的任务
action: 为了完成任务做了哪些工作, 怎么做
result: 自己的贡献
简述 S, 突出 TAR
- 项目相关问题
碰到的最大问题是什么? 怎么解决的?
从项目中学到什么?
什么时候会和其他成员有冲突? 什么样的冲突? 如何解决?
- 掌握的技能
了解: 上过课或者读过书, 没有实际的项目
熟悉: 实际项目中应用
精通: 不要轻易使用
- 为什么跳槽
避免: 老板太苛刻; 同事太难相处; 加班多; 工资低
- 需要具备的素质
扎实的基础知识: 编程语言, 数据结构, 算法
高质量代码: 鲁棒, 稳定, 边界条件, 特殊输入(null, 空字符串), 错误处理
清晰的思路: 画图, 举例, 分治
优化效率: 时间&内存
综合能力: 编程能力, 技术功底, 沟通能力, 学习能力, 知识迁移, 抽象建模, 发散思维
- 提问环节
不要问和职位没有关系问题(公司未来5年规划)
薪水
面试结果
职位或者项目相关, 需要提前做功课
- 小提示
如果要修改原数据, 要提前询问
如果是在排序的数组中查找, 都可以使用二分法
通常递归实现更简洁容易实现, 如果没有特殊要求, 可以优先采用
写代码时最后使用完整的英文单词组合变量名和函数, 让人可以一眼读懂代码的意图
如果没有限定处置范围, 就要考虑是否存在 大数问题
要特别注意 鲁棒性
每一次指针操作都要注意是否可能为 NULL
摆放数字 -> 排列 + 组合
有关字符的问题都可以考虑是否可以使用 hash 表
面对面试问题主动提出高质量的问题
基础知识
- c++
sizeof
<effective C++>: 面试之前突击c++
<C++ primer>: 全面了解 c++ 语法
<inside C++ object model>
<The C++ Programming Language>: 全面深入掌握 C++
- c#
<Professional C#>: 有几章专门介绍 c# 和其他语言的区别
<CLR via C#>: 能够深入理解 装箱卸箱, 垃圾回收, 反射
- 数据结构
数组: array -> STL vector -> c++11 array
字符串: char -> STL string
链表: 单向, 环形, 双向; 添加 / 删除 节点
树: 二叉树 前/中/后 序遍历, 宽度优先遍历
栈和队列: FILO / FIFO
- 算法&数据操作
查找: 二分, 哈希表, 二叉排序树
排序: 冒泡, 插入, 快速, 归并
递归&循环
位运算: 世界上有 10 种人
代码规范
书写, 布局, 命名
代码完整性: 功能测试, 边界测试, 负面测试(错误输入)
错误处理方式: return code; 全局变量; 异常
鲁棒性: 容错性
解决问题的思路
抽象问题 -> 形象化, 画图
抽象问题 -> 具体化, 举例
复杂问题 -> 简单化(分治)
优化效率: 时间 + 空间
时间效率: 编程习惯; 循环/递归 实现; 数据结构+算法; 思维+追求完美
时间效率和空间效率平衡: 时间换空间不一定可行, 比如嵌入式设备存储有限
保存递归过程中的结果来调高时间效率
面试中的各项能力
沟通能力 / 学习能力 -> 善于提问
知识迁移能力: 稍微改变已知问题; 简单->复杂
抽象建模能力: 比如 斐波那契 f(n) = f(n-1) + f(n-2)
发散思维能力: 思维活动的多向性&变通性; 知识面的深度&广度
面试案例
案例一: 不要轻易说精通 -> 基本语法 -> 检查 空指针/空字符串 等情况 -> 错误处理方式 -> 不要主动在技术面询问薪资
案例二: 简要介绍项目(STAR) -> UML 图来分析项目 -> 树(逐渐缩小范围) -> 二叉搜索树 -> 指向根节点的指针(转化成链表) -> 使用辅助内存(转化成链表) -> 提问 项目/团队 相关的问题
problem
- singleton(单例模式)
多线程环境 -> 锁资源 -> 减少锁资源操作(添加 if)
当然上面的做法, 都没有使用 静态构造函数 简洁
class Singleton{
private static $instance;
public static function getInstance(){
if(static::$instance === null){
static::$instance = new static();
}
return static::$instance;
}
}
- sizeof + array
int getSize(int a[]){
return sizeof(a);
}
int a[] = {1,2,3,4,5};
int *b = a;
sizeof(a); // 20
sizeof(b); // 4, 指针大小都为 int
getSize(a); // 4, 作为参数传递, 会退化为指针
- 二维数组中查找
选取右上角的数字
bool find(int arr[][], int rows, int columns, int number){
bool found = false;
if(arr!=NULL && rows>0 && columns>0){ // 鲁棒性
int row=0, column=columns-1;
while(row<rows && column>=0){
if(arr[row][column] == number){ // 选取右上角的点
found = true; break;
}else(arr[row][column] < number) column--;
else row++;
}
}
return found;
}
- 替换字符串中的空格
php: str_replace()
先遍历出空格的个数, 然后用2个指针从后往前遍历
- 反向打印链表
栈
- 根据树的前序遍历和中序遍历
思路: 前序遍历第一个节点就是根节点, 根据根节点在中序遍历中获取左右子树, 然后递归
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder){
// 前序遍历的第一个元素就是根节点
int rootValue = startPreorder[0];
BinaryTreeNode* root = new BinaryTreeNode();
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = NULL;
if(startPreorder==endPreorder){
if(startInorder==endInorder && *startPreorder==*startInorder) return root;
else throw exception("invalid input");
}
// 在 中序遍历 中查找根节点
int* rootInorder = startInorder;
while(rootInorder<=endInorder && *rootInorder!=rootValue) rootInorder++;
if(rootInorder==endInorder && *rootInorder!=rootValue) throw exception("invalid input");
int leftLength = rootInorder - startInorder;
int* leftPreorderEnd = startPreorder + leftLength;
// 构建左子树
if(leftLength>0){
root->m_pLeft = ConstructCore(startPreorder+1, leftPreorderEnd, startInorder, rootInorder-1);
}
// 构建右子树
if(leftLength < endPreorder - startPreorder){
root->m_pRight = ConstructCore(leftPreorderEnd+1, endPreorder, rootInorder+1, endInorder);
}
return root;
}
BinaryTreeNode* Construct(int* preorder, int* inorder, int length){
if(preorder==NULL || inorder==NULL || length<=0) return NULL;
return ConstructCore(preorder, preorder+length-1, inorder, inorder+length-1);
}
- 2个栈实现队列
进栈: A栈进数据
出栈: B栈出数据, 如果B栈为空, 将A栈数据进栈到B, 然后出栈
- O(n) 实现排序
数据在较小范围内(比如 age), 使用辅助空间即可
- 旋转数组的最小值
二分查找
特殊情况: 有重复数字
- 斐波那契
直接递归 -> 循环(O(N)) -> 矩阵(O(logN))
类似: 青蛙一次跳1-2级; 青蛙一次跳1-n级(2^n-1); 1*2 矩阵拼图
- 一个数二进制的 1 的个数
右移 -> 负数右移会死循环
使用 1 和数字进行 & 运算, 然后 左移 1, 重复 & 运算
自减 1 后再和原数进行 & 运算, 就是把最右边的 1 置为 0
类似: 一个数是不是 2 的整数次方; 2个数需要变换几次才能二进制相同(异或)
- 实现 pow() 函数
指数为负数
使用全局变量 标识 基数指数都是 0 的情况
二分实现 n 次方
- 打印 1 到最大的 n 位数
大数问题
转化为排列问题
- O(1) 删除节点
实现当前节点替换当前节点的下一个节点
特殊情况: 只有一个节点
- 调整数组顺序, 使奇数在偶数前面
2个指针, 一个在表头, 一个在表尾
将数组分为2部分: 抽象出比较方法
- 链表中倒数第 k 个节点
2个指针, 一个先走 k-1 步
特殊情况: 链表为空, k=0, 链表是否有 k 个元素
类似: 链表中间节点; 判断链表是否有环
- 反转链表
递归, 3个指针
-
合并有序链表
-
判断 子树
先遍历查找子树的根节点, 然后遍历看是否是子树
- 数的镜像
递归, 交换左右子树
- 顺时针打印矩阵
按照 4 个方向 打印即可
特殊情况: 最后可能退化成只有 1 行/列/点
- 带 min 的栈
使用辅助栈
入栈: 压入最小元素到栈顶
出栈: 如果当前元素是最小元素, 辅助栈出栈
- 栈的 压入 / 弹出 序列
按照入栈序列入栈, 遍历弹出序列, 如果元素在 栈和辅助栈栈顶, 弹出, 继续下一个;
如果不等, 压入 栈 -> 辅助栈, 如果栈为空还没有找到, 则不是
- 层次遍历二叉树
使用 队列
类似: 图的 bfs
- 后序遍历 判断是不是 二叉搜索树
二叉搜索树: 左子树小于根节点, 右子树大于根节点
后序遍历: 左子树 -> 右子树 -> 根节点
递归
- 二叉树中和某值的路径
在遍历树的同时, 使用 vector 实现栈来保存路径
void FindPath(BinaryTreeNode* pRoot, int expectedSum, vector<int>& path, int& currentSum);
void FindPath(BinaryTreeNode* pRoot, int expectedSum){
if(pRoot==NULL) return;
vector<int> path;
int currentSum = 0;
FindPath(printArr, expectedSum, path, currentSum);
}
void FindPath(BinaryTreeNode* pRoot, int expectedSum, vector<int>& path, int& currentSum){
currentSum += pRoot->m_nValue;
path.push_back(pRoot->m_nValue);
// 满足条件: 叶节点 + currentSum
bool isLeaf = pRoot->m_pLeft==NUll && pRoot->m_pRight==NULL;
if(currentSum==expectedSum && isLeaf){
vector<int>::iterator iter = path.begin();
for(;iter!=path.end(); iter++){
cout<<*iter;
}
cout<<endl;
}
// 如果不是 叶节点
if(pRoot->m_pLeft!=NULL) FindPath(pRoot->m_pLeft, expectedSum, path, currentSum);
if(pRoot->m_pRight!=NULL) FindPath(pRoot->m_pRight, expectedSum, path, currentSum);
// 返回 父节点
currentSum -= printArr->m_nValue;
path.pop_back();
}
- 复制复杂链表
在原节点后复制一个当前节点 -> 复制节点的复杂关系 -> 根据奇偶分离 2 个链表
- 二叉搜索树 -> 排序双向链表(不能增加节点)
二叉搜索树: 中序遍历就是有序序列(太多指针操作)
- 字符串的所有排列
这里字符都是唯一的
递归: 将待排序字符串分为第一个字符和后面的字符, 将第一个字符依次和后面的字符交换
void permutation(char* pStr, char* pBegin){
if(*pBegin == '\0') cout<<pStr<<endl;
else{
for(char* pCh=pBegin; *pCh!='\0'; pCh++){
char tmp = *pCh;
*pCh = *pBegin;
*pBegin = tmp;
permutation(pStr, pBegin+1);
tmp = *pCh;
*pCh = *pBegin;
*pBegin = tmp;
}
}
}
void permutation(char* pStr){
if(pStr == NULL) return;
permutation(pStr,pStr);
}
类似:
n个字符的所有组合
从n个字符中取m个的组合 = 从n-1个字符中取m-1个字符(m包含第一个字符) + 从n-1个字符中取m个字符
8个数字放在正方形8个顶点上, 使3对面上的顶点相等
求全排列, 判断是否存在符合条件的情况
8皇后问题
- 数组中超过一半的数字
保存当前数, 遍历数组, 再次出现, 计数+1, 不等, 计数-1
int moreThanHalfNum(int* a, int n){
int res, cnt=0;
for(int i=0;i<n;i++){
if(!cnt) res = a[i];
if(a[i]==res) cnt++;
else cnt--;
}
return res;
}
- 最小的k个数
基于快排的 partition 算法, 将比a[k]小的数字移动到数组左边(需要改变原数据)
维护一个最大堆, 依次比较插入的数据(特别适合大数据场景)
- 连续子数组最大和
动态规划
- 1-n整数中1出现的次数
去掉最高位递归(和求全排列的思路一样的)
- 把正整数数组拼接成一个最小的数
规律: 2个数n,m, 只要确定 mn 和 nm 的大小, 就可以确定 m,n 的先后顺序
隐藏的大数问题: 将 m,n 转换成字符串, 然后进行比较
- 丑数
原始方法: 一次判断是不是丑数, 知道找到第1500个
空间换时间: 维护一个排序好的丑数序列, 以及3个位置(这个位置乘以2刚好比最大的丑数大)
- 第一次只出现一次的字符
通过 (int)char 维护一个hash表, 遍历一次计数, 然后再次遍历
类似:
第一个字符串中删除第二个字符串(为第二个字符串维护hash表)
删除字符串中的重复字符(为一个bool类型的hash表)
判断2个字符串是否含有相同的字符: 扫描str1增加每个字符的cnt, 扫描第二次减每个字符的cnt
- 数组中的逆序对
原数组的逆序对 = 左数组的逆序对 + 右数组的逆序对 + 求左右数组的逆序对
- 链表的公共节点
如果有公共节点, 那么肯定之后的节点一定都相同, 遍历获取2个链表的长度, 然后用2个指针遍历, 一个先走 m-n 步
- 排序数组中连续数字的第一次&最后一次出现位置
二分查找的变种
// 数第一次出现的位置
if(a[mid] == num){
if(mid==0 || (mid>0 && a[mid-1]!=num)) return mid;
else end = mid-1;
}else if(a[mid] > num) end = mid-1;
else start = mid+1;
- 二叉树的深度
int treeDepth(BinaryTreeNode* pRoot){
if(pRoot==NULL) return 0;
int nLeft = treeDepth(pRoot->m_pLeft);
int nRight = treeDepth(pRoot->m_pRight);
return (nLeft > nRight) ? (nLeft+1) : (nRight+1);
}
类似:
判断是否为平衡二叉树: 可以套用上面的方法, 但是会重复遍历, 采用后序遍历, 每次记录树的深度即可只遍历一次
bool isBalanced(BinaryTreeNode* pRoot, int* pDepth){
if(pRoot==NULL){
*pDepth = 0; return true;
}
int left, right;
if(isBalanced(pRoot->m_pLeft, &left) && isBalanced(pRoot->m_pRight, &right)){
if((left>right) && (left-right)<=1){
*pDepth = 1 + left; return true;
}
if((left<right) && (right-left)<=1){
*pDepth = 1 + right; return true;
}
}
return true;
}
- 数组中只出现一次的数字
一个数字只出现一次, 其他数字都出现2次: 异或
二个数字只出现一次, 其他数字都出现2次: 通过第一次异或的结果分组, 将问题转化为上面的类型
一个数字只出现一次, 其他数字都出现3次: 使用hash表存每位上面 1 的个数, 不能整除就说明这个1属于这个数
- 和为 s 的2个数字 vs 和为s的序列
2个指针, 一个数组投, 一个数组尾
2个指针, 一个在第一个元素, 一个在第二个元素
- 反转单词 vs 左旋转字符串
先反转整个字符串, 然后依次反转单词
先反转整个字符串, 然后反转 左边/右边 的字符串
- n个骰子的点数
当前骰子点数和上一次骰子的点数的关系: f(n) = f(n-1) + ... + f(n-6)
int n, num,i,j,k;
cin>>n;
int arrSize = 6*n+1;
int total = pow(6,n);
int a1[arrSize]={0}, a2[arrSize]={0};
for(i=1;i<=6;i++) a1[i] = 1;
for(i=2;i<=n;i++){
// 如果 i 是奇数, 通过 a2 计算 a1
if(i&1){
for(j=1;j<=6*i;j++){
a1[j] = 0;
for(k=1;k<=6 && (j-k)>=0;k++){
a1[j] += a2[j-k];
}
}
}else{
for(j=1;j<=6*i;j++){
a2[j] = 0;
for(k=1;k<=6 && (j-k)>=0;k++){
a2[j] += a1[j-k];
}
}
}
}
- 扑克牌的顺子
牌抽象成数字, 大小王抽象成 0(指代任意数字) -> 数值数组排序 -> 计算不连续 -> 和 0 来比较
- 圆圈中最后剩余的数字
可以推导出一个数学公式
- 位运算实现加法
int add(int num1, int num2){
int sum, carry;
do{
sum = num1 ^ num2;
carry = (num1 & num2) <<1;
num1 = sum;
num2 = carry;
}while(num2!=0);
return num1;
}
网友评论