5
14
2014
0

《剑指offer》笔记

1.《剑指offer》 44页 替换空格。题目:给一个字符串"we are young",把其中空格替换为"%20".即变为"we%20are%20young"

   key:先遍历字符串,统计空格数目,然后从后往前替换。在原空间上把空间加大。

2.《剑指offer》 51页 从尾到头打印链表。

 思路一:顺序遍历一遍,并把结点压入栈中,然后从栈中pop出结点

 思路二:递归,每访问一个结点,先递归输出其后面的结点,再输出自身的结点。

3.《剑指offer》55页,由先序遍历和中序遍历构建二叉树。

 key 先序遍历第一个为根。找到根后可以再中序遍历中找到根的左子树和右子树。左右子树再利用相同的思想,于是关键就是递归了。

4.《剑指offer》59页。利用两个栈实现一个队列。

  key 插入则放入stack1中,删除,则从stack2中删除。其中stack2中的元素是从stack1中pop后在push到stack2中的。

5,《剑指offer》65页。实现O(n)时间复杂度的排序算法。

  key 问清楚排序数字的范围,数据的多少。然后具体问题具体分析。题目对几万员工的年龄排序。故可以建立timesOfAge[oldestAge+1]的数据,里面存放每一个岁数的人员个数

6.《剑指offer》66页。旋转数组中最小的数字

 key 用二分查找法可以使时间复杂度降低到log(n)

 

7.《剑指offer》75页斐波那契数列。定义f(n)=f(n-1)+f(n-2)。

解决问题:一只青蛙一次可以跳一级台阶同时也可以跳两级台阶。请问跳n 阶台阶共有多少种跳法。分析,在跳到n阶台阶前有两种情况,1:处在n-1阶台阶上,跳1级到达n阶台阶。2:处在n-2阶台阶上,跳2级到达n接台阶。故f(n)=f(n-1)+f(n-2)

8.《剑指offer》78页二进制数中1的个数

解法1 负数右移最高位补1,防止该现象,用flag=1左移的结果与n做按位与操作。当flag为负数时,按位与操作结束。

解法2 key 把一个整数减1,与原来的数做与运算,则能把左右边的1变为0,则一个整数的二进制表示中有多少个1,就能进行多少次这个操作。

9. 《剑指offer》82页判断一个数是不是2的整数次方。

  key 2的整数次方的二进制表示只有一个1,故可以使用8中的解法2

10.两个整数m和n,计算m需要改变多少个二进制位的个数才能得到n,如10的二进制表示1010,13的二进制表示1101,则要改变3个

 key 做抑或操作后,看二进制中1的个数

11《剑指offer》96 未懂

12《剑指offer》99页 已知一个单向链表的头指针和一个节点的指针,要求在O(1)的时间复杂度内删除这一个节点

  key 常规方法从头遍历找到该节点前驱为O(n)。故通过给出该节点的指针找到该节点的后继节点,然后把值赋值到该节点,删除该节点后一个节点的存储空间。

13《剑指offer》102页 调整整数组顺序使奇数位于偶数的前面

  key p1,p2两个指针(即数字),p1从前往后移,p2从后往前移。前者遇到偶数停下,后者遇到奇数停下。然后交换顺序。直到p1>p2。前者遇到偶数停下,后者遇到奇数停下是根据题目"使奇数位于偶数的前面"设定的。题目不同则停下条件不同。故这儿的条件判断可以写成函数形式,通过函数返回值判断

14《剑指offer》119页 未懂

15《剑指offer》127 顺时针打印矩阵

  key 一圈一圈的打印,要点1:判断该圈是否要打即,(cloumns>starts*2&&rows>starts*2),其中starts初始值为0,每打印一圈,start值自增一次;要点二:每圈有四条路径,即左到右,上到下,右到左,下到上。若该圈需要打,则一定会有第一条路径,接着判断其余三条路径是否需要打印。

16《剑指offer》132 自定义栈数据结构。在该栈中能得到该栈中最小的元素min函数。在该栈中,调用min,push,pop的时间复杂度都为1

key:使用一个辅助栈,每向栈中push一次,辅助栈push入栈中当前最小的元素。栈每pop一次,辅助栈pop出栈顶的元素。这样min值就为辅助栈中的栈顶的值

17《剑指offer》134 给出一个入栈序列,判断某序列是否可能为该栈的弹出顺序。

key:元素逐一入栈,每压入一个元素,判断此时栈顶是否为即将弹出的元素,若是,则弹出该元素,继续入栈;若不是,继续入栈,若元素都入栈完毕,还不是要弹出的非弹出序列,则判断该弹出序列不可能成立

18《剑指offer》 137页。按层打印树。

key。利用队列,每打印一个结点后,再把该结点的左右儿子压入队列,然后再打印队列中的下一个元素

19《剑指offer》140页 判断一个数组,该数组是否可能是某个二叉搜索树的后序遍历序列。

key。二叉树的左子树小于根,右子树大于根,数组的最后一个元素是根。通过sequence[i]<root的条件找到左子树和右子树的分界后,在右子树的数据部分若再发现小于根的数据,则可以return false,再在分隔的左右子树数组中递归调用该函数,return left&&right;

20.《剑指offer》143页  输入一个二叉树和一个整数,打印二叉树中和为该整数的所有路径。该路径只统计从树的根节点往下一直到叶子节点的路径。

key 可以用递归思想,若当前为NULL,且当前和为0,则为有效路径。

21.《剑指offer》147页 复杂链表的复制。该链表除了有一个常规的m_pNext指针指向下一个结点外,还有一个m_pSibling指向链表中的任意结点或者NULL。请实现该复杂链表的复制。

key:由于m_pSlibing任意指向,所以若先复制m_pNext链表后再复制m_pSibling,则需要从表头定位m_pSlibing,故时间复杂度O(N^)。故正解思路如下:将复制的链表逐个插入到原结点后边,则新结点的m_pSlibing应为源节点的m_pSlibing->next。赋值好新结点的m_pSlibing后就可以重新定位p_mNext,得到新的赋值链表

22.《剑指offer》151页 输入一个二叉搜索树,将其转化为一个排序的双向链表。要求不能创建人和新的结点,只能调整数中结点指针的指向。即m_pLeft和m_pRight指向。

key:递归思想,未懂

23.《剑指offer》154页 输入一个字符串,打印该字符串的所有排列

key:把一个问题拆分为和它类似的问题后,就可以用递归的思想了。这个问题可以分为两步,首先求所有可能出现在第一个位置的字符,即把第一个字符和所有的字符交换。然后固定第一个字符,求后面所有字符的排列。显然这就是一个递归的问题。

拓展问题1:输入一个含有8个数字的数组,判断有没有可能把8个数字分别放到正方体的8个顶点上,使得正方体上三组相对的面上的4个顶点的和相等。

key。得到a1,a2,a3,a4,a5,a6,a7,a8这8个数字的所有排列,然后判断有没有一个排列符合a1+a2+a3+a4=a5+a6+a7+a8且a1+a3+a5+a7=a2+a4+a6+a8且a1+a2+a5+a6=a3+a4+a7+a8.(画一个正方体,把8个顶点用a1至a8标上,然后得到上面三组等式)

拓展问题2:在8*8的国际象棋上方8个皇后,使其不能相互攻击,即任意两个皇后不能在同一行、一列、一个对角线上。求符合条件的摆法。

key。ColumnIndex[8]中的第i个数字表示第i行的皇后所在的列好,把这8个元素用0~7初始化,即对ColumnIndex做全排列。所以对数组的两个下标i和j,判断i-j=ColumnIndex[i]-ColumnIndex[j]或者i-j=ColumnIndex[j]-ColumnIndex[i]

24.《剑指offer》163页 数组中出现次数超过一半的数字。

key1:长度过半,那么把数组排序后,若存在该数,那中间的那个数字一定是所要找的数字。step1:排序;step2:再遍历一遍数组,判断该数出现的次数。

key2:不排序,step1:遍历一次数组元素,得到可能的出现次数超过一半的数字,方法如下:当遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则次数加1;若不同,则次数减1.如果次数为零,则保存下一个数字,并把次数设为1.则若存在概述,则肯定是最后一次把次数设为1的数。step2:再遍历一遍数组,判断该数出现的次数。

25.《剑指offer》167页:输入n个整数,找出其中最小的k个数

key1:若能修改数组中数的排序,则使用partition函数来解决问题。把比K小的数放在K的左边,比K大的数放在K的右边,位于数组左边的k个数就是最小的K个数,注意这K个数不一定是排序了的。该方法会使输入的数组中的数改变顺序

key2:若要求不能修改数组中的数,则顺序遍历一次数组,把数组中读到的最小的k个数放在一个容器中。容器未满k个数时,将读到的数直接加入,满了,则比较容器中最大的数和正在遍历的数。当容器满了需要1.在k个数中找最大的数。2.可能删除该数。3.可能插入新的数字。因此对于二叉树实现这个容器,能在O(logk)实现三个操作,若n个输入数字,总效率为O(n*logk)

26.《剑指offer》170页:连续子数组的最大和。要求时间复杂度为O(n)

保存两个变量,nCurSum和nGreatestSum,若nCurSum小于0了,则其对整体和的增大不可能再有贡献。nCurSum赋值为下一个读入的数,并比较if(nCurSum>nGreatestSum) nGreatestSum = nCurSum;

27.《剑指offer》174页:从1到n出现1的次数。输入一个整数n,求1到n这n个整数的十进制表示中1出现的次数,如输入12,从1到12有1,10,11,12,共出现5次

未懂

28.《剑指offer》177页:把数组排成最小的数。输入一个正整数,把数组中所有的数字拼接起来,并打印所有数字钟最小的一个。如{3,32,321}则打印321323.

key:若求出所有可能的排列,具排列组合,则有n!种排列方法,过于复杂。故考虑另外的方法。给出数字m,n要将mn和nm比较大小。直接的数学方法要考虑拼接了m和n后的溢出问题。故考虑常规的大数问题解决方法:将数字转换成字符串。然后用qsort函数解决,自定义compare函数。

29.《剑指offer》182页:丑数。把只包含银子2,3,5的数称为丑数。从按小到大1500个丑数。如6、8是丑数,但14不是丑数。习惯上把1当成第一个丑数。

key1:从1到x,每个数字都判断是否为丑数,直到判断到第1500个。丑数判断:

while(number%2==0)number/=2;
while(number%3==0)number/=3;
while(number%5==0)number/=5;
return (number==1)?true:false;

key2:基于已经找到的丑数基础上进行乘2、3、5的操作。找到以下丑数。

30.《剑指offer》186页:第一个只出现一次的字符:在字符串中找出第一个只出现一次的字符。如出入“abaccdeff”,则输出'b'.

key1:由于字母只有26,故可以利用哈希表的键值(key)是字符,而值(value)是该字符出现的次数。然后再扫描一次字符串,输出值第一次为1的字母。

31.《剑指offer》189页:数组中的逆序对。在数组中的两个数字,如果前面一个数字大于后面一个数字,则这两个数字组成一个逆序对。输出所有逆序对。

没细看

32.《剑指offer》193页:求两个链表的第一个公共结点。

key1:因为链表的元素只有一个next,故一旦公共结点了,则后面所有的结点都是公共结点。可以遍历两个链表,把两个链表中的元素的地址压入两个不同的栈,然后再从栈中弹出元素。直到找到最后一个地址相同的元素。

key2:先遍历得到两个链表长度;长的链表先走几部;一起走,直到找到相同点。

33.《剑指offer》207页:判断二叉树是否是平衡二叉树。

key1 常规递归遍历方法,二叉树中许多结点多要反复查找

34.《剑指offer》211页:数组中只出现一次的数字。一个整形数组除了两个数字之外,其他的数字都出现了两次。请写程序找到这两个数字

key1.若除了一个数字外,其他数字都出现了两次。则可以异或,最后的结果就是要找的数字

15 《剑指offer》 237页 写一个函数,求两个整数的和,函数体内不得使用+、-、*、/  四则运算符号。

 key 先相加,后进位。相加相当于位运算的异或。进位相当于位运算中的与。只有当与结果等于0才能停止

16 《剑指offer》239页 用c++设计一个不能被继承的类

key:

Category: 算法、数据结构 | Tags: 算法;面试 | Read Count: 1234

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com