剑指offer例题分享--6
前言：继续整理例题，快速做完这部分，然后继续用C++去刷数据结构和算法的题。
面试题28：
代码如下：
#include<iostream> #include<stdio.h> using namespace std; void Permutation(char *pStr,char *pBegin) { if(*pBegin == '\0') { printf("str:%s\n",pStr); } else { for(char *pCh=pBegin;*pCh!='\0';++pCh) { char temp = *pCh; *pCh = *pBegin; *pBegin = temp; Permutation(pStr,pBegin+1); temp = *pCh; *pCh = *pBegin; *pBegin = temp; } } } void Permutation(char *pStr) { if(pStr == NULL) return; Permutation(pStr,pStr); } int main() { char buf[32]="asd"; Permutation(buf); return 0; }
面试题29：
代码如下：
/************************************************************************* > File Name: 29.cpp > Author: ma6174 > Mail: ma6174@163.com > Created Time: Tue 14 Aug 2018 09:45:42 AM CST ************************************************************************/ #include<iostream> using namespace std; bool g_bInputInvalid =false; bool CheckInvalidArray(int *numbers,int len) { if(numbers==NULL && len<=0) g_bInputInvalid = true; return g_bInputInvalid; } bool CheckMoreThanHalf(int *numbers,int len,int num) { int times = 0; for(int i=0;i<len;++i) { if(numbers[i] == num) times++; } bool isMoreThanHalf = true; if(times*2 < len) { g_bInputInvalid = true; isMoreThanHalf = false; } return isMoreThanHalf; } int MoreThanHalfNum(int *numbers,int len) { if(CheckInvalidArray(numbers,len)) return 0; int result = numbers[0]; int times = 1; for(int i=1;i<len;++i) { if(times == 0) { result = numbers[i]; times = 1; } else if(numbers[i] == result) times++; else times--; } if(!CheckMoreThanHalf(numbers,len,result)) result = 0; return result; } int main() { int data[]={1,2,5,6,2,2,2}; cout << "num: " << MoreThanHalfNum(data,7) << endl;; return 0; }
面试题30：
分析：一定要对C++的STL熟悉，才能看明白如下代码：
#include<iostream> #include<set> #include<vector> #include<algorithm> #include<iterator> using namespace std; //greater<int>()是一个预定义函数对象，将multiset容器从大到小排序 typedef multiset<int,greater<int> > intSet; typedef multiset<int,greater<int> >::iterator setIterator; void GetLeastNumbers(const vector<int> &data,intSet &leastNumbers,int k) { //清空容器 leastNumbers.clear(); if(k<1 || data.size()<k) return; //创建迭代器 vector<int>::const_iterator iter = data.begin(); for(;iter!=data.end();++iter) { //小于k插入容器 if((leastNumbers.size())<k) leastNumbers.insert(*iter); else{ setIterator iteraCreatest = leastNumbers.begin(); //如果插入的数比容器中的最大值小，则删除 if(*iter < *(leastNumbers.begin())) { leastNumbers.erase(iteraCreatest); leastNumbers.insert(*iter); } } } } int main() { vector<int> data(4); data[0] = 1; data[1] = 8; data[2] = 9; data[3] = 2; intSet set; GetLeastNumbers(data,set,2); //iterate over all elements and print them intSet::iterator pos; for (pos = set.begin(); pos != set.end(); ++pos) { cout << *pos << ' '; } cout << endl; return 0; }
作者：
柳德维
-------------------------------------------
个性签名：独学而无友，则孤陋而寡闻。做一个灵魂有趣的人！
如果觉得这篇文章对你有小小的帮助的话，记得在右下角点个“推荐”哦，博主在此感谢！
万水千山总是情，打赏一分行不行，所以如果你心情还比较高兴，也是可以扫码打赏博主，哈哈哈(っ•̀ω•́)っ⁾⁾！
