剑指offer例题分享--6-阿里云开发者社区

剑指offer例题分享--6

2018-08-14 1115

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 　　前言：继续整理例题，快速做完这部分，然后继续用C++去刷数据结构和算法的题。　　面试题28：　　　　　　代码如下：　　　　#include#includeusing namespace std;void Permutation(char *pStr,char *pBegin)...

　　前言：继续整理例题，快速做完这部分，然后继续用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;
}