没有合适的资源?快使用搜索试试~ 我知道了~
首页程序员面试宝典:100题精选C语言解题策略
程序员面试宝典:100题精选C语言解题策略
需积分: 3 8 下载量 118 浏览量
更新于2024-07-31
收藏 665KB PDF 举报
"程序员面试题精选100题"是一本面向应届毕业生的面试指导书籍,主要聚焦于程序员领域的面试技巧和问题解答。作者分享了自己的求职经验,并整理了大量来自网络的程序员面试问题,特别是那些技术性强、具有代表性的题目。书中提到的核心问题是将二元查找树转化为排序的双向链表,这是一道经典的技术考察题,通常用于测试应聘者的算法思维和递归理解。 题目要求在不创建新节点的前提下,仅通过调整树节点的指针指向,将二叉查找树转化为有序的双向链表。两种推荐的解决方案包括递归思路一和中序遍历: 1. 递归思路一:从根节点开始,首先处理左子树,将其转换成一个有序的左链表,然后连接到当前节点的右侧,确保左链表的最右节点与右链表的最左节点相连。接着递归地对右子树进行同样的操作。 2. 中序遍历思路:按中序遍历顺序访问每个节点,即先访问左子节点,然后访问根节点,最后访问右子节点。每次访问一个节点时,将其插入到已排序链表的正确位置,保持链表的有序性。 作者提醒,虽然提供了两种方法,但实际面试中可能会有错误或更巧妙的解决方案,鼓励读者提出自己的见解和优化方案。这道题目不仅考验了应聘者的编程基础,还涉及数据结构和算法的理解,例如如何利用递归和迭代来管理树的结构以及如何维护链表的排序。 通过阅读这本书,求职者不仅可以学习到实际面试中的问题类型,还能提升自己的问题解决能力和逻辑思维能力,为应对激烈的就业市场做好充分准备。同时,对于提供和分享更多高质量面试题的读者,作者表示非常欢迎和感激,体现了互助和共享的精神。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/3139170/bg10.jpg)
continue;
}
// A word is between with pBegin and pEnd, reverse it
else if(*pEnd == ' ' || *pEnd == '\0')
{
Reverse(pBegin, --pEnd);
pBegin = ++pEnd;
}
else
{
pEnd ++;
}
}
return pData;
}
(08)-求 1+2+...+n
题目:求
1+2+…+n
,要求不能使用乘除法、
for
、
while
、
if
、
else
、
switch
、
case
等关键字以及条件
判断语句(
A?B:C
)。
分析:这道题没有多少实际意义,因为在软件开发中不会有这么变态的限制。但这道题却能
有效地考查发散思维能力,而发散思维能力能反映出对编程相关技术理解的深刻程度。
通常求
1+2+…+n
除了用公式
n(n+1)/2
之外,无外乎循环和递归两种思路。由于已经明确限
制
for
和
while
的使用,循环已经不能再用了。同样,递归函数也需要用
if
语句或者条件判
断语句来判断是继续递归下去还是终止递归,但现在题目已经不允许使用这两种语句了。
我们仍然围绕循环做文章。循环只是让相同的代码执行
n
遍而已,我们完全可以不用
for
和
while
达到这个效果。比如定义一个类,我们
new
一含有
n
个这种类型元素的数组,那么该
类的构造函数将确定会被调用
n
次。我们可以将需要执行的代码放到构造函数里。如下代码
正是基于这个思路:
class Temp
{
public:
Temp() { ++ N; Sum += N; }
static void Reset() { N = 0; Sum = 0; }
static int GetSum() { return Sum; }
private:
static int N;
static int Sum;
};
![](https://csdnimg.cn/release/download_crawler_static/3139170/bg11.jpg)
int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(int n)
{
Temp::Reset();
Temp *a = new Temp[n];
delete []a;
a = 0;
return Temp::GetSum();
}
我们同样也可以围绕递归做文章。既然不能判断是不是应该终止递归,我们不妨定义两个函
数。一个函数充当递归函数的角色,另一个函数处理终止递归的情况,我们需要做的就是在
两个函数里二选一。从二选一我们很自然的想到布尔变量,比如
ture
(
1
)的时候调用第一
个函数,
false
(
0
)的时候调用第二个函数。那现在的问题是如和把数值变量
n
转换成布尔
值。如果对
n
连续做两次反运算,即
!!n
,那么非零的
n
转换为
true
,
0
转换为
false
。有了上述
分析,我们再来看下面的代码:
class A;
A* Array[2];
class A
{
public:
virtual int Sum (int n) { return 0; }
};
class B: public A
{
public:
virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};
int solution2_Sum(int n)
{
A a;
B b;
Array[0] = &a;
Array[1] = &b;
int value = Array[1]->Sum(n);
![](https://csdnimg.cn/release/download_crawler_static/3139170/bg12.jpg)
return value;
}
这种方法是用虚函数来实现函数的选择。当
n
不为零时,执行函数
B::Sum
;当
n
为
0
时,
执行
A::Sum
。我们也可以直接用函数指针数组,这样可能还更直接一些:
typedef int (*fun)(int);
int solution3_f1(int i)
{
return 0;
}
int solution3_f2(int i)
{
fun f[2]={solution3_f1, solution3_f2};
return i+f[!!i](i-1);
}
另外我们还可以让编译器帮我们来完成类似于递归的运算,比如如下代码:
template <int n> struct solution4_Sum
{
enum Value { N = solution4_Sum<n - 1>::N + n};
};
template <> struct solution4_Sum<1>
{
enum Value { N = 1};
};
solution4_Sum<100>::N
就是
1+2+...+100
的结果。当编译器看到
solution4_Sum<100>
时,就是为模板类
solution4_Sum
以参数
100
生成该类型的代码。但以
100
为参数的类型
需 要 得 到 以
99
为 参 数 的 类 型 , 因 为
solution4_Sum<100>::N=solution4_Sum<99>::N+100
。这个过程会递归一直到参数
为
1
的类型,由于该类型已经显式定义,编译器无需生成,递归编译到此结束。由于这个过
程是在编译过程中完成的,因此要求输入
n
必须是在编译期间就能确定,不能动态输入。这
是该方法最大的缺点。而且编译器对递归编译代码的递归深度是有限制的,也就是要求
n
不
能太大。
大家还有更多、更巧妙的思路吗?欢迎讨论
^_^
(09)-查找链表中倒数第 k 个 点结
题目:输入一个单向链表,输出该链表中倒数第
k
个结点。链表的倒数第
0
个结点为链表的
尾指针。链表结点定义如下:
struct ListNode
{
![](https://csdnimg.cn/release/download_crawler_static/3139170/bg13.jpg)
int m_nKey;
ListNode* m_pNext;
};
分析:为了得到倒数第
k
个结点,很自然的想法是先走到链表的尾端,再从尾端回溯
k
步。
可是输入的是单向链表,只有从前往后的指针而没有从后往前的指针。因此我们需要打开我
们的思路。
既然不能从尾结点开始遍历这个链表,我们还是把思路回到头结点上来。假设整个链表有
n
个结点,那么倒数第
k
个结点是从头结点开始的第
n-k-1
个结点(从
0
开始计数)。如果我
们能够得到链表中结点的个数
n
,那我们只要从头结点开始往后走
n-k-1
步就可以了。如何
得到结点数
n
?这个不难,只需要从头开始遍历链表,每经过一个结点,计数器加一就行
了。
这种思路的时间复杂度是
O(n)
,但需要遍历链表两次。第一次得到链表中结点个数
n
,第二
次得到从头结点开始的第
n-k-1
个结点即倒数第
k
个结点。
如果链表的结点数不多,这是一种很好的方法。但如果输入的链表的结点个数很多,有可能
不能一次性把整个链表都从硬盘读入物理内存,那么遍历两遍意味着一个结点需要两次从
硬盘读入到物理内存。我们知道把数据从硬盘读入到内存是非常耗时间的操作。我们能不能
把链表遍历的次数减少到
1
?如果可以,将能有效地提高代码执行的时间效率。
如果我们在遍历时维持两个指针,第一个指针从链表的头指针开始遍历,在第
k-1
步之前,
第二个指针保持不动;在第
k-1
步开始,第二个指针也开始从链表的头指针开始遍历。由于
两个指针的距离保持在
k-1
,当第一个(走在前面的)指针到达链表的尾结点时,第二个
指针(走在后面的)指针正好是倒数第
k
个结点。
这种思路只需要遍历链表一次。对于很长的链表,只需要把每个结点从硬盘导入到内存一次。
因此这一方法的时间效率前面的方法要高。
思路一的参考代码:
/////////////////////////////////////////////////////////////////////
//
// Find the kth node from the tail of a list
// Input: pListHead - the head of list
// k - the distance to the tail
// Output: the kth node from the tail of a list
/////////////////////////////////////////////////////////////////////
//
ListNode* FindKthToTail_Solution1(ListNode* pListHead, unsigned int
k)
{
if(pListHead == NULL)
return NULL;
// count the nodes number in the list
ListNode *pCur = pListHead;
unsigned int nNum = 0;
while(pCur->m_pNext != NULL)
{
pCur = pCur->m_pNext;
![](https://csdnimg.cn/release/download_crawler_static/3139170/bg14.jpg)
nNum ++;
}
// if the number of nodes in the list is less than k
// do nothing
if(nNum < k)
return NULL;
// the kth node from the tail of a list
// is the (n - k)th node from the head
pCur = pListHead;
for(unsigned int i = 0; i < nNum - k; ++ i)
pCur = pCur->m_pNext;
return pCur;
}
思路二的参考代码:
/////////////////////////////////////////////////////////////////////
//
// Find the kth node from the tail of a list
// Input: pListHead - the head of list
// k - the distance to the tail
// Output: the kth node from the tail of a list
/////////////////////////////////////////////////////////////////////
//
ListNode* FindKthToTail_Solution2(ListNode* pListHead, unsigned int
k)
{
if(pListHead == NULL)
return NULL;
ListNode *pAhead = pListHead;
ListNode *pBehind = NULL;
for(unsigned int i = 0; i < k; ++ i)
{
if(pAhead->m_pNext != NULL)
pAhead = pAhead->m_pNext;
else
{
// if the number of nodes in the list is less than k,
// do nothing
return NULL;
}
剩余110页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![m](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
a735194357
- 粉丝: 72
- 资源: 4
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 解决Eclipse配置与导入Java工程常见问题
- 真空发生器:工作原理与抽吸性能分析
- 爱立信RBS6201开站流程详解
- 电脑开机声音解析:故障诊断指南
- JAVA实现贪吃蛇游戏
- 模糊神经网络实现与自学习能力探索
- PID型模糊神经网络控制器设计与学习算法
- 模糊神经网络在自适应PID控制器中的应用
- C++实现的学生成绩管理系统设计
- 802.1D STP 实现与优化:二层交换机中的生成树协议
- 解决Windows无法完成SD卡格式化的九种方法
- 软件测试方法:Beta与Alpha测试详解
- 软件测试周期详解:从需求分析到维护测试
- CMMI模型详解:软件企业能力提升的关键
- 移动Web开发框架选择:jQueryMobile、jQTouch、SenchaTouch对比
- Java程序设计试题与复习指南
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)