简述

下面是关于程序员面试100题的相关笔记。不全面但是自己可以供参考

题目

题目1

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何 新的结点,只调整指针的指向

方案1 先完成左子树的转换，链接中间节点后，再完成右子树的转换，然后链接中间节点和右子树

方案2 中序遍历

注 中序遍历的算法

题目2

定义栈的数据结构,要求添加一个 min 函数,能够得到栈的最小元素。要求函数 min、push 以及 pop 的时间复杂度都是 O(1)

解析

方案

注

题目3

输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个 子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为 O(n)

解析

方案

注

题目4

题目11

输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于 右子树的结点。用递归和循环两种方法完成树的镜像转换

解析

对于递归，类似递归遍历方式，在递归前交换左右子树；至于非递归，可以用循环可以用一个栈 来模拟递归操作。

题目12

输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印

解析

就是用队列层次遍历

题目13

在一个字符串中找到第一个只出现一次的字符。如输入 abaccdeff,则输出 b

解析

简单来说O(n^{2)的依次比较。可以用哈希。类似的题目，找出相同的字符，相同字符} 的次数，出现次数最多的字符。在一个巨大的文件内出现次数最多的k个成员等等

题目14

n 个数字(0,1,…,n-1)形成一个圆圈,从数字 0 开始,每次从这个圆圈中删除第 m 个数字(第一个 为当前数字本身,第二个为当前数字的下一个数字) 。当一个数字删除后,从被删除数字的下一个继续删除 第 m 个数字。求出在这个圆圈中剩下的最后一个数字

解析

约瑟夫问题，可以直接用stl::list模拟行为，然后直接操作。或者利用推导完成递归公式。

题目15

关于类中的深浅拷贝问题，需要自定义拷贝构造函数以及重载等号，另外为了避免指针 被外面别的类删除，可以考虑用引用计数的方式

题目16

用最快的方法求fibonacci数列的第 n 项

解析

由于递归会重复计算很多次相同的值，那么可以考虑从0到n的计算，这样可以省去重复的 次数，复杂度是o(n)

可以有利用数学归纳发发现log(n)的算法

题目17

输入一个表示整数的字符串,把该字符串转换成整数并输出。例如输入字符串”345”,则输出整数 345

解析

问题不难，在c/c++ java python中都有现成的方法，但是大都不够严谨全面。

可以考虑用一个全局变量来标识是否输入合法，标准c中的atoi就是这样做的。

题目18

-用两个栈实现队列

解析

一个栈出一个栈入，出栈非空一直出，空则将入栈内的数据导入其中

注

如何用两个队列实现一个栈，可以考虑n个数先入一个队列，一旦要出的话，将前n-1个都 出队，然后入队进另一个队列。每次操作都如此

题目19

输入一个链表的头结点,反转该链表,并返回反转后链表的头结点

需要保存反转节点的子节点

题目20

如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字 符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数, 输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个字符串 BDCABA 和 ABCBDAB,字符串 BCBA 和 BDAB 都是是它们的最长公共子串,则 输出它们的长度 4,并打印任意一个子串

解析

经典的动态规划问题。

题目 26

输入一个正数 n,输出所有和为 n 连续正数序列

类似10题

27

输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度

递归遍历二叉树

28

递归的考察

似乎穷举和动态规划的方式

值得深入思考下

29

输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数 组的后半部分。要求时间复杂度为 O(n)

和快速排序类似，但是这个比较的时候不是比较大小，而是除以2看余数是否为0

值得注意的是结构的安排和算法不同部分的解耦

30

给出如下 CMyString 的声明,要求为该类型添加赋值运算符函数

1
2
3
4
5
6
7
8
9

class CMyString
{
  public:
  CMyString(char* pData = NULL);
  CMyString(const CMyString& str);
  ~CMyString(void);
  private:
  char* m_pData;
};

除了需要注意的4点外，能够更好的设计结构，利用析构函数更好

31

输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下

me:顺序访问，然后用个栈

解析:

可以用递归，也是用栈，但是是在函数层次的栈

32

用 C++设计一个不能被继承的类。

me: 固定类大小，静态类？

解析：

构造和析构私有

利用模板和虚继承

33

给定链表的头指针和一个结点指针,在 O(1)时间删除该结点

me:

1
2
3
4

phead->value=pdelete->value;
ptr = phead;
phead=phead->next;
delete(ptr);

解析：

们需要需要把给定的结点的下一个结点的数据拷 贝到给定的结点中

34

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个 只出现一次的数字。要求时间复杂度是 O(n) ,空间复杂度是 O(1)

me: 类似bit排序，扫描放入，但是空间复杂度是o(n)

解析：

如果一个数组中只有一个出现一次，其他出现两次，连续异或后只剩下出现一次的数字

(me: 首先连续异或，然后用异或后的数字分别异或所有的值能够出现在数组内的两个值就是)

我们在结果数字中找到第一个为 1 的位的位置,记为第 N 位。现在我们以第 N 位是不是 1 为标准把原数组中的数字分成两个子数组,第一个子数组中每个数字的第 N 位都为 1,而第二个子数组的每个数字的第 N 位都为 0

35

两个单向链表,找出它们的第一个公共结点

me: 组成两个环，一个每次步进1，一个每次步进2，相遇的那一点

可能会遇到后面的公共点

解析：

我们先要分别遍历两个链表得到它们的长度,并求出两个长度之差。在长的 链表上先遍历若干次之后,再同步遍历两个链表,知道找到相同的结点

#

参考