没有合适的资源?快使用搜索试试~ 我知道了~
首页二元查找树转排序链表:程序员面试题解
"程序员面试题精选100题文档主要针对的是程序员在求职过程中可能会遇到的面试问题,特别是关于C++编程和数据结构方面的问题。其中一道具体的题目是将给定的二元查找树(Binary Search Tree, BST)转换成一个排序的双向链表(Double-Linked List)。这个问题考察了面试者对递归算法和树数据结构的理解以及实现能力。 该题目要求考生利用现有的BST节点结构(包含值、左右子节点的指针),不创建新节点的情况下,通过调整节点间的指针关系,将树转化为有序的链表。提供了两种递归思路: 1. 思路一:递归调整法 - 从根节点开始,首先处理左子树,将其转换为排序的左子链表,然后处理当前节点及其右子树。关键在于找到左子树的最大结点(即链表的最右结点)和右子树的最小结点,使得它们成为新链表中的适当位置。这个过程会一直递归到每个子树的叶子节点。 2. 思路二:中序遍历法 - 这种方法通过中序遍历BST,按照升序顺序访问结点。每次访问时,将当前结点插入到已排序链表的末尾。这样遍历结束后,整个BST就构成了一个有序的链表。 参考代码给出了BST节点结构的定义,并展示了思路一的具体实现,这部分代码展示了如何根据子树是否为右子节点来决定返回最大或最小节点。实际的代码实现可能还包括函数定义、递归调用和链表连接等步骤,以及在思路二中如何保存遍历状态并保持链表有序。 这道题目不仅测试了候选人的编程技能,还考察了他们对数据结构操作的熟练度和抽象思维能力,因为需要理解和应用递归算法来解决复杂的数据结构问题。掌握这类面试题有助于提升应聘者的竞争力,因为在实际工作中,解决这类问题的能力对于高效编程和算法优化至关重要。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/88479614/bg10.jpg)
16
{
if(squence[i] > root)
break;
}
// the nodes in the right sub-tree are greater than the root
int j = i;
for(; j < length - 1; ++ j)
{
if(squence[j] < root)
return false;
}
// verify whether the left sub-tree is a BST
bool left = true;
if(i > 0)
left = verifySquenceOfBST(squence, i);
// verify whether the right sub-tree is a BST
bool right = true;
if(i < length - 1)
right = verifySquenceOfBST(squence + i, length - i - 1);
return (left && right);
}
![](https://csdnimg.cn/release/download_crawler_static/88479614/bg11.jpg)
17
程序员面试题精选 100 题(07)-翻转句子中单词的顺序
题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。句子中单词以空格符隔开
。
为
简单起见,标点符号和普通字母一样处理。
例如输入“I am a student.”,则输出“student. a am
I
”
。
分析:由于编写字符串相关代码能够反映程序员的编程能力和编程习惯,与字符串相关的问题一直是程序
员笔试、面试题的热门题目。本题也曾多次受到包括微软在内的大量公司的青睐。
由于本题需要翻转句子,我们先颠倒句子中的所有字符。这时,不但翻转了句子中单词的顺序,而且单词
内字符也被翻转了。我们再颠倒每个单词内的字符。由于单词内的字符被翻转两次,因此顺序仍然和输入
时的顺序保持一致。
还是以上面的输入为例子。翻转“I am a student.”中所有字符得到“.tneduts a ma
I
”,
再翻转每个单词
中字符的顺序得到“students. a am I”,正是符合要求的输出。
参考代码:
/////////////////////////////////////////////////////////////////////
//
// Reverse a string between two pointers
// Input: pBegin - the begin pointer in a string
// pEnd - the end pointer in a string
/////////////////////////////////////////////////////////////////////
//
void Reverse(char *pBegin, char *pEnd)
{
if(pBegin == NULL || pEnd == NULL)
return;
while(pBegin < pEnd)
{
char temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
pBegin ++, pEnd --;
}
}
/////////////////////////////////////////////////////////////////////
//
// Reverse the word order in a sentence, but maintain the character
// order inside a word
// Input: pData - the sentence to be reversed
/////////////////////////////////////////////////////////////////////
![](https://csdnimg.cn/release/download_crawler_static/88479614/bg12.jpg)
18
//
char* ReverseSentence(char *pData)
{
if(pData == NULL)
return NULL;
char *pBegin = pData;
char *pEnd = pData;
while(*pEnd != '\0')
pEnd ++;
pEnd--;
// Reverse the whole sentence
Reverse(pBegin, pEnd);
// Reverse every word in the sentence
pBegin = pEnd = pData;
while(*pBegin != '\0')
{
if(*pBegin == ' ')
{
pBegin ++;
pEnd ++;
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;
}
![](https://csdnimg.cn/release/download_crawler_static/88479614/bg13.jpg)
19
程序员面试题精选 100 题(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;
};
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 转换
![](https://csdnimg.cn/release/download_crawler_static/88479614/bg14.jpg)
20
为 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);
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);
}
另外我们还可以让编译器帮我们来完成类似于递归的运算,比如如下代码:
剩余183页未读,继续阅读
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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://profile-avatar.csdnimg.cn/7386ab88f5ce450e8817b9541ae085eb_caryxp.jpg!1)
小小哭包
- 粉丝: 1926
- 资源: 4032
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-1.c8e153b4.png)
下载权益
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-2.8b825a4e.png)
电子书特权
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-3.fc5e5fb6.png)
VIP文章
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-4.320a6894.png)
课程特权
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-icon.fe0226a8.png)
开通VIP
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Vue实现iOS原生Picker组件:详细解析与实现思路
- Arduino蓝牙小车:参数调试与功能控制
- 百度Java面试精华:200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南:CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略:44步详解流程
- RecyclerView全面解析:替代ListView的新选择
- Android开发:自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发:BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0:Android事件总线详解与实战应用
- Android FileUtil:全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](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)