剑指offer--读后总结

记录一下,看完这本书后,自己需要改进的地方。算法的技巧等等。

项目经验:

  • 简短的项目背景
  • 自己完成的任务
  • 为了完成任务做了哪些工作,怎么做的
  • 自己的贡献

技术环节

  • 扎实的基础知识:编程语言,数据结构,算法
  • 高质量的代码:代码鲁棒性,越简单的题目考官期望越高,各种特殊情形的处理考虑(边界条件,空指针,空字串,error)
  • 清晰的思路,解决复杂问题的3个方式(画图形象化,举例具体化,分解简单化)
  • 优化程序:空间优化,时间优化

应聘者提问

  • 必须提前做好准备,招聘的职位或者项目
  • 网上收集,主要业务,职位要求,需求(或者请面试官讲讲他在哪个组,做什么样的工作,常用的开发工具,语言)
  • 留心面试官说过的话。然后提问

例题

  • 第4题,替换空格,输入“we are happy”,输出“we%20are%20happy”
  • solution:先扫描一遍旧的char数组,数一下有多少个空格,新数组长度就出来了。然后从末尾向前复制。时间,空间都是O(n);

  • 第5题,从尾到头打印链表
  • solution1:如果允许改动链表,把整个链表反向
  • solution2:我自己直接想到的是用栈来存储
  • solution3:书中观点,既然能用栈,那就可以递归,代码写起来更加方便,存在问题:当链表较长,递归函数调用有可能栈溢出
  • 第7题扩展,两个队列模拟一个栈
  • 当需要出栈时,非空队列的所有元素(除开最后一个元素)进入另外一个队列,最后的那个元素算是出栈
  • 滴9题扩展
  • 青蛙跳台阶问题,条件改成:一只青蛙一次可以上一级台阶,也可以两级,也可以。n级。那么跳上一个n级台阶有多少种方法。数学归纳法:f(n) = pow(2,n-1)
  • 用n个2x1的小矩形去 覆盖一个2xn的大矩形,有多少种方法。fibonacci
  • 第10题,二进制中1的个数
  • question:右移负数时,比如0x80000000,不会直接变成0x40000000,而是最高位仍然为1,即0xC0000000,然后惨了,0xFFFFFFFF。所以不考虑原来的数右移,而是把0x00000001这个数不停的左移。
  • a & (a-1) 这个操作会把二进制数种的最右侧的一个1,变成0。
  • 用一个句子判断一个整数是不是2的整数次方:那么这个整数的二进制数种,有且仅有1位是1.根据上面那句话 执行一次就ok。
  • 两个整数mn,需要改变m的二进制表示中的多少位才能变成n,亦或之后,数1的个数
  • 由于精度的原因,不能用等号判断连个浮点数是否相等。上网查过资料之后,相减小于某一个很小的数,则近似相等
  • 功能测试,边界测试,负面测试
  • 12题,打印从1到n位的最大的数字,例如n=3,打印1到999.陷阱:n有可能很大,溢出则无法正常输出
  • 用字符串模拟大数的加1进位等操作
  • 注意:递归输出数据全排列
  • 13题,O(1)时间删除链表节点
  • 实际操作是,把下一个节点的内容复制到当前指针,删除下一个节点即可
  • 注意:该节点是末尾节点,该链表只有一个节点,确保节点在链表中
  • 26题,复杂链表的复制
  • 每个节点的复制节点直接链接在自己身后,然后再把一个链表拆成两个
  • 28题字符串的排列:之前一直不大理解,until自己亲自动手实现一遍
  • 扩展:输出n个字符的组合。用位运算的方式来实现组合。例如5个字符,那么从1到31就是00001到11111。每一个二进制数,对应这个一个组合。
  • 八皇后问题
  • 输入两个整数n和m,从数列1,2,3...n中随意取几个数,使其和等于m,要求列出所有的组合。
  • 我以后再也不纠结排列组合的题目了,上面4个题目我都一一实现了一遍


  • C/C++程序员要养成采用引用(或)指针传递复杂类型参数的习惯。如果采用值传递的方式,从形参到实参会产生一次复制操作。这样的复制是多余的,应该尽量避免
  • 29题,数组中出现次数超过一半的数字
  • 普通的类似快排的方法,已经可以解决,但是为什么是O(n)???
  • 解法二比较巧妙,充分利用了次数超过一半这个特点。遍历数组的时候存两个数,一个存数字,一个存次数。当遍历到下一个数的时候,如果下一个数字和保存数字相同,则次数++,否则次数--。若次数为0时,更换保存数字。
  • 32题,从1到n的整数中1出现的次数
  • 考虑某一位,当这一位=0时,=1时,大于1时,这一位会出现多少个1
  • 35题,第一次只出现一次的字符
  • 哈希表的应用。利用ascii码表
  • 37题,两个链表的第一个公共节点
  • 先遍历出两个链表的长度,然后长的那个先走n步,然后开始一个个节点比较
  • 39题,求二叉树的深度,判断一个二叉树是否平衡二叉树
  • 后序遍历
  • 41题,和为s的两个数字,和为s的连续n个数字。数组有序
  • 第一问其实可以秒杀,两个指针,一头一尾挪动就行。
  • 第二问着实想了一下,其实也是两个指针,只不过sum是指针之间所有数字的和而已。
  • 43题,n个骰子和为s的概率
  • 当知道所有的情况为6的n次方时,其实也就是求有多少种情况那个骰子和为s,递归显然是不可取的
  • 动态规划。当有一个骰子时,出现1到6的次数都为1
  • 记录当有n个骰子时,出现n到6n的次数分别为X(n)到X(6n)
  • 那么,当第n+1个骰子加入的时候,Y(n+1)到Y(6n+6)的递推公式如下:
  • Y(M) = X(M-1) + X(M-2) + X(M-3) + X(M-4) + X(M-5) + X(M-6)
  • 因为新的M等于,新骰子=1&&旧的n个骰子=M-1 + 新骰子=2&&旧的n个骰子=M-2 + 新骰子=3&&旧的n个骰子=M-3 + 新骰子=4&&旧的n个骰子=M-4 + 新骰子=5&&旧的n个骰子=M-5 + 新骰子=6&&旧的n个骰子=M-6
  • 怎么说着说着有点像数学里面的归纳法了,先说初始情况,然后说从n推导到n+1的情况,最后下个结论
  • 46题,圆圈中最后剩下的数字
  • 链表做法已然落伍,找到数学规律才是王道
  • n==1时,f(n,m)=0;就是只有一个数字0的时候,那就必然是它了
  • n>1时,f(n,m) = ( f(n-1,m) + m) % n
  • 46题,计算从1加到n,不用乘除法,不能用for while if else switch case等关键字
  • 由于我不大了解C++,所以只关注了函数指针解法,着实巧妙
    {% codeblock %}
    typedef unsigned int (*fun)(unsigned int);
    unsigned int solution_terminator(unsigned int n){ return 0;}
    unsigned int sum_solution( unsigned int n)
    {
        static fun f[2] = { solution3_terminator , sum_solution};
        return n+f[!!n](n-1);
    }
    {% endcodeblock %}

  • 47题,不用加减乘除做加法
  • 这个题目之前见过,所以就会了,但是还是得记录一下
  • 只好用位运算,想想自己如果手动算二进制加法,那就是不停的进位等操作了,于是有了思路
  • result = a ^ b , 进位 = (a & b) << 1;
  • 迭代,result和进位 这两个数,直到进位 为0