【100题】第七十一题~第七十五题

2024-04-05 01:18
文章标签 100 十五 第七 第七十一

本文主要是介绍【100题】第七十一题~第七十五题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一，数值的整数次方。

1）题目：实现函数double Power(double base, int exponent)，求base 的exponent 次方。不需要考虑溢出。

2）分析：这是一道看起来很简单的问题。却暗藏玄机

3）源码：

       第一反应：我想这个代码应该都能写出来吧

#include  <iostream>
using namespace std;
double Power(double base, int exponent)
{
double result = 1.0;
for(int i = 1; i <= exponent; ++i)
result *= base;
return result;
}
int main()
{
double result= Power(2, 4);
cout<<result<<endl; 
}

        面试不会仅仅考察这么简单的问题吧？是不是要考虑代码的鲁棒性呢？

      1>  exponent=0 ，则结果为 1

      2>  exponent<0 ，则结果应该是另一种求法

      3>  base = 0 或 base =1 应该单独考虑，base =0 exponent<0 相当于 0作为分母，这是错误的输入

      4>  判断double 变量是否为0 不能直接使用（==）因为计算机表达的 小数存在误差

     
   改进后的代码：

        注意判断double 类型相等不能直接使用 ==

#include <iostream>
#include <stdlib.h>
using namespace std;
bool isInvalidInput=false;
double PowerWithUnsingedExponent(double base,unsigned int absExp)
{
double result=1.0; //这里初始化为1.0 ，当 absExp==0时候，直接返回结果 1 
for(int i=0;i<absExp;i++)
result*=base;
return result;
}
//由于精度原因，double类型的变量不能用等号判断两个数是否相等，因此需要写equsl函数
bool equal(double a,double b)
{
if((a-b>-0.000001)&&(a-b<0.000001))
return true;
else
return false;
}
double Power(double base,int exponent)
{
//如果底数为0且指数小于0，则表明是非法输入。
if(equal(base,0.0) && exponent<=0)
{
isInvalidInput=true;
return 0;
}
unsigned int absExp;
//判断指数正负，去指数的绝对值
if(exponent<0)
absExp=(unsigned int)(-exponent);
else
absExp=(unsigned int)exponent;
double result=PowerWithUnsingedExponent(base,absExp);
//如果指数小于0则取倒数
if(exponent<0)
result=1/result;
return result;
}
int main()
{
double a=Power(2.0,13);
cout<<a<<endl;
system("pause");
}

 

其实这里PowerWithUnsingedExponent(double base,unsigned int absExp) 可以改进的，思想是：

比如求X16,可以分解成：X16=X8*X8，于是，只要求出X8，再做一个乘积就可得到X16，同理，X8=X4*X4，……依次类推。所以求X16，只需要做4次乘积：X*X、X2*X2、X4*X4、X8*X8。如果用上面代码所述方法，要进行15次乘积。

现在问题变成，怎么把exponent分解成2的若干个整数次方，尤其是当exponent不是2的整数次方时，比如6。这里就用到了二进制的一些特点，比如6的二进制为0110，6可以分解为4+2，二进制熟悉的话，这里应该是一眼可以看出来的，就是对应二进制为1的位所表示的数的和。则X6=X4*X2。

 

double PowerWithUnsingedExponent(double base,unsigned int absExp)
{
if(absExp==0)
return 1;
else if(absExp==1)
return base;
double result=1.0*base;
for(int i=2;i<=absExp;i=i*2)
result*=result;
if(absExp%2==1)//如果指数为奇数，还得再乘一次底数
result*=base;
return result;
}


 

二，单例模式

1）题目：设计一个类，我们只能生成该类的一个实例。

2）分析：只能生成一个实例的类是实现了Singleton模式的类型

3）源码：

class Singleton 
{
private:
Singleton();
~Singleton();
static Singleton *instance; 
public:
static Singleton* getSingleton (); 
}; 
Singleton::instance=NULL;
Singleton::Singleton()
{
} 
Singleton::~Singleton()  
{  
if(instance != NULL)  
{  
delete instance;  
}  
}  
Singleton*  Singleton::getSingleton()
{
if(instance==NULL) 
instance=new Singleton();
return instance; 
}


 


 

三，对称字符串的最大长度。

1）题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

2）分析：找出字符串中最长的回文子串

3）源码：注意string 的应用

#include <iostream>
#include <cstring> 
using namespace std;
bool isPalindrome(string str)
{
int i=0; 
int j=str.length()-1;
while(i<=j)
{
if(str.at(i)==str.at(j)) 
{
i++;
j--; 
} 
else
return false; 
} 
return true; 
} 
int  getResult(string str)
{
string temp; 
int position; 
int length=1; 
for(int i=0;i<str.length();++i)
{
for(int j=i+1;j<str.length();++j)
{	
temp=str.substr(i,j-i+1);//注意这里的个数  j-i+1
cout<<temp<<endl; 
if(isPalindrome(temp)) 
{  
length=max(length,j-i+1); //注意这里的个数  j-i+1
position=i; 
} 
} 
} 
return length; 
} 
int main()
{
cout<<getResult("google")<<endl; //4 
cout<<getResult("abcdeffedcba")<<endl;// 12
}

 

四，数组中超过出现次数超过一半的数字【精华】

1）题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

2）分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司都曾经采用过这个题目。

                解法一：O(n^2)         排序，则中间数为所求

                解法二：O（nlogn）堆排序，则中间数为所求

                解法三：O(n)             抵消法，temp记录假设的 目标数，count 记录该数个数，当遇到不同值时 count--。 遇到相同值时 count++。count == 0时更换一个假设目标

3）源码：

#include <iostream>
#include <cstring> 
using namespace std;
int getMajor(int a[], int n)
{
int asume;
int count=0;
for(int i=0;i<n;++i)
{
if(count==0)
{
asume=a[i];
count++; 
} 
else if(asume == a[i])
count++;
else
count--; 
} 
return asume; 
}
int main()
{
int s[]={1,2,1,3,1}; 
cout<<getMajor(s, 5)<<endl; //4 
}

 

五，二叉树两个结点的最低共同父结点

1）题目：二叉树的结点定义如下：

struct TreeNode

{

         int     m_nvalue;

        TreeNode*  m_pLeft;

        TreeNode* m_pRight;

};

输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。

2）分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。

      第一个变种：是二叉树是一种特殊的二叉树，查找二叉树。也就是树是排序过的，位于左子树上的结点都比父结点小，而位于右子树的结点都比父结点大。

                  求解：我们只需要从根结点开始和两个结点进行比较。

                             如果当前结点的值比两个结点都大，则最低的共同父结点一定在当前结点的左子树中。

                             如果当前结点的值比两个结点都小，则最低的共同父结点一定在当前结点的右子树中。

     第二个变种：是树不一定是二叉树，每个结点都有一个指针指向它的父结点。于是我们可以从任何一个结点出发，得到一个到达树根结点的单向链表。因此这个问题转换为两个单向链表的第一个公共结点。我们在本面试题系列的第35题讨论了这个问题。

     现在我们回到这个问题本身。所谓共同的父结点，就是两个结点都出现在这个结点的子树中。因此我们可以定义一函数，来判断一个结点的子树中是不是包含了另外一个结点。这不是件很难的事，我们可以用递归的方法来实现：

      

bool HasNode(TreeNode* pHead, TreeNode* pNode)
{
if(pHead == pNode)
return true;
bool has = false;
if(pHead->m_pLeft != NULL)
has = HasNode(pHead->m_pLeft, pNode);
if(!has && pHead->m_pRight != NULL)
has = HasNode(pHead->m_pRight, pNode);
return has;
}

        我们可以从根结点开始，判断以当前结点为根的树中左右子树是不是包含我们要找的两个结点。如果两个结点都出现在它的左子树中，那最低的共同父结点也出现在它的左子树中。如果两个结点都出现在它的右子树中，那最低的共同父结点也出现在它的右子树中。如果两个结点一个出现在左子树中，一个出现在右子树中，那当前的结点就是最低的共同父结点。基于这个思路，我们可以写出如下代码：

    

TreeNode* LastCommonParent_1(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)
{
if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL; 
// check whether left child has pNode1 and pNode2
bool leftHasNode1 = false;
bool leftHasNode2 = false;
if(pHead->m_pLeft != NULL)
{
leftHasNode1 = HasNode(pHead->m_pLeft, pNode1);
leftHasNode2 = HasNode(pHead->m_pLeft, pNode2);
}
if(leftHasNode1 && leftHasNode2)
{
if(pHead->m_pLeft == pNode1 || pHead->m_pLeft == pNode2)
return pHead;
return LastCommonParent_1(pHead->m_pLeft, pNode1, pNode2);
}
// check whether right child has pNode1 and pNode2
bool rightHasNode1 = false;
bool rightHasNode2 = false;
if(pHead->m_pRight != NULL)
{
if(!leftHasNode1)
rightHasNode1 = HasNode(pHead->m_pRight, pNode1);
if(!leftHasNode2)
rightHasNode2 = HasNode(pHead->m_pRight, pNode2);
}
if(rightHasNode1 && rightHasNode2)
{
if(pHead->m_pRight == pNode1 || pHead->m_pRight == pNode2)
return pHead;
return LastCommonParent_1(pHead->m_pRight, pNode1, pNode2);
}
if(    (leftHasNode1 && rightHasNode2)
|| (leftHasNode2 && rightHasNode1))
return pHead;
return NULL;
}


 

         接着我们来分析一下这个方法的效率。函数HasNode的本质就是遍历一棵树，其时间复杂度是O(n)（n是树中结点的数目）。由于我们根结点开始，要对每个结点调用函数HasNode。因此总的时间复杂度是O(n2)。

我们仔细分析上述代码，不难发现我们判断以一个结点为根的树是否含有某个结点时，需要遍历树的每个结点。接下来我们判断左子结点或者右结点为根的树中是否含有要找结点，仍然需要遍历。第二次遍历的操作其实在前面的第一次遍历都做过了。由于存在重复的遍历，本方法在时间效率上肯定不是最好的。

前面我们提过如果结点中有一个指向父结点的指针，我们可以把问题转化为求两个链表的共同结点。现在我们可以想办法得到这个链表。我们在本面试题系列的第4题中分析过如何得到一条中根结点开始的路径。我们在这里稍作变化即可：

 

// Get the path form pHead and pNode in a tree with head pHead

 

bool GetNodePath(TreeNode* pHead, TreeNode* pNode, std::list<TreeNode*>& path)
{
if(pHead == pNode)
return true;
path.push_back(pHead);
bool found = false;
if(pHead->m_pLeft != NULL)
found = GetNodePath(pHead->m_pLeft, pNode, path);
if(!found && pHead->m_pRight)
found = GetNodePath(pHead->m_pRight, pNode, path);
if(!found)
path.pop_back();
return found;
}


由于这个路径是从跟结点开始的。最低的共同父结点就是路径中的最后一个共同结点：

// Get the last common Node in two lists: path1 and path2

TreeNode* LastCommonNode(const std::list<TreeNode*>& path1, 
const std::list<TreeNode*>& path2)
{
std::list<TreeNode*>::const_iterator iterator1 = path1.begin();
std::list<TreeNode*>::const_iterator iterator2 = path2.begin();
TreeNode* pLast = NULL;
while(iterator1 != path1.end() && iterator2 != path2.end())
{
if(*iterator1 == *iterator2)
pLast = *iterator1;
iterator1++;
iterator2++;
}
return pLast;
}

有了前面两个子函数之后，求两个结点的最低共同父结点就很容易了。我们先求出从根结点出发到两个结点的两条路径，再求出两条路径的最后一个共同结点。代码如下：

// Find the last parent of pNode1 and pNode2 in a tree with head pHead

TreeNode* LastCommonParent_2(TreeNode* pHead, TreeNode* pNode1, TreeNode* pNode2)
{
if(pHead == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
std::list<TreeNode*> path1;
GetNodePath(pHead, pNode1, path1);
std::list<TreeNode*> path2;
GetNodePath(pHead, pNode2, path2);
return LastCommonNode(path1, path2);
}

这种思路的时间复杂度是O(n)，时间效率要比第一种方法好很多。但同时我们也要注意到，这种思路需要两个链表来保存路径，空间效率比不上第一个方法。

  

还有一种给力的 后续递归求解

TreeNode* getLCA(TreeNode* root, TreeNode* X, TreeNode *Y) 
{
if (root == NULL) 
return NULL;
if (X == root || Y == root) 
return root;
TreeNode * left = getLCA(root->m_pLeft, X, Y);
TreeNode * right = getLCA(root->m_pRight, X, Y);
if (left == NULL) 
return right;
else if (right == NULL) 
return left;
else 
return root;
}


 

这篇关于【100题】第七十一题~第七十五题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/877300。

相关文章

【LeetCode热题100】前缀和

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目，分别是：【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci
阅读更多...
牛客小白月赛100部分题解

牛客小白月赛100部分题解

比赛地址：牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>
阅读更多...
牛客小白月赛100（A,B,C,D,E,F三元环计数）

牛客小白月赛100（A,B,C,D,E,F三元环计数）

比赛链接 官方讲解 这场比较简单，ABC都很签到，D是个不太裸需要预处理的 B F S BFS BFS 搜索，E是调和级数暴力枚举，F是三元环计数。三元环考的比较少，没见过可能会偏难。 A ACM中的A题 思路： 就是枚举每个边变成原来的两倍，然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2，比如 1 4 8 这组数据，也不能只给第二短边乘 2 2 2，比
阅读更多...
诺瓦星云校招嵌入式面试题及参考答案（100+面试题、10万字长文）

诺瓦星云校招嵌入式面试题及参考答案（100+面试题、10万字长文）

SPI 通信有哪些内核接口？ 在嵌入式系统中，SPI（Serial Peripheral Interface，串行外设接口）通信通常涉及以下内核接口： 时钟控制接口：用于控制 SPI 时钟的频率和相位。通过设置时钟寄存器，可以调整 SPI 通信的速度以适应不同的外设需求。数据发送和接收接口：负责将数据从主机发送到从机以及从从机接收数据到主机。这些接口通常包括数据寄存器，用于存储待发
阅读更多...
【重学 MySQL】十五、过滤数据

【重学 MySQL】十五、过滤数据

【重学 MySQL】十五、过滤数据 基本用法使用`AND`、`OR`和`NOT`使用`IN`操作符使用`BETWEEN`操作符使用`LIKE`操作符使用`IS NULL`和`IS NOT NULL` 在MySQL中，过滤数据主要通过WHERE子句来实现。WHERE子句允许你指定条件来过滤从表中检索出来的行。只有当行满足WHERE子句中的条件时，这些行才会被包含在查询结果中。
阅读更多...
多个线程如何轮流输出1到100

多个线程如何轮流输出1到100

多个线程如何轮流输出1到100的值 这个面试问题主要考察如何让线程同步，首先线程同步必会用到的就是互斥锁，互斥锁保证多个线程对数据的同时操作不会出错。但是线程同步还会用到条件变量condition_variable，condition_variable（条件变量）是 C++11 中提供的一种多线程同步机制，它允许一个或多个线程等待另一个线程发出通知，以便能够有效地进行线程同步。 conditi
阅读更多...
【最新华为OD机试E卷-支持在线评测】机器人活动区域(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)

【最新华为OD机试E卷-支持在线评测】机器人活动区域(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解 💻 ACM金牌🏅️团队| 多次AK大厂笔试 ｜ 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测，专栏文章质量平均 94 分 最新华为OD机试目录: https://blog.
阅读更多...
华为OD机试 - 最大利润（Java 2024 E卷 100分）

华为OD机试 - 最大利润（Java 2024 E卷 100分）

华为OD机试 2024E卷题库疯狂收录中，刷题点这里 专栏导读 本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。 刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。 一、题目描述
阅读更多...
Python精选200Tips：91-100

Python精选200Tips：91-100

To do a good job, one must first sharpen their tools. 091 sys092 os093 json094 re邮箱地址手机号身份证号数字（整数和浮点数）匹配科学计数法汉字大、小写字母年月日 095 itertools096 datetime097 math098 random099 collectionsCounterdequedefa
阅读更多...
【最新华为OD机试E卷-支持在线评测】分糖果(100分)-多语言题解-(Python/C/JavaScript/Java/Cpp)

【最新华为OD机试E卷-支持在线评测】分糖果(100分)-多语言题解-(Python/C/JavaScript/Java/Cpp)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解 💻 ACM金牌🏅️团队| 多次AK大厂笔试 ｜ 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测，专栏文章质量平均 94 分 最新华为OD机试目录: https://blog.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2