當前位置：首頁 > 编程资源 > 综合教程 >内容正文

综合教程

[微软面试100题]8190

發布時間：2023/12/15 综合教程 31 生活家

生活随笔收集整理的這篇文章主要介紹了 [微软面试100题]8190 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

第八十一題：

1、求數組中大于左邊所有元素，小于右邊素有元素的數。只能用一個額外數組。

思路：從左往右遍歷先把max記錄在額外數組中。從右往左遍歷記錄當前min在一個變量中。對比min和max和當前即可。

//復雜度O（n），2次迭代,使用1個數組
void helper(int *a,int n){
    int nowmax=a[0],nowmin=a[n-1];
    int max[n];
    for(int i=0;i<n;++i){
        if(a[i]>nowmax)nowmax=a[i];
        max[i]=nowmax;
    }
    for(int i=n-1;i>=0;--i){
        if(a[i]<nowmin)nowmin=a[i];
        if(a[i]>=max[i] && a[i]<=nowmin)cout<<a[i]<<endl;
    }
}

2、一千萬條字符串，找出所有系相反的字符串。

思路：先hash所有字符串，然后一條一條翻轉再hash，沖突則輸出即可。

第八十二題：

1、用C++模擬類似SQL的存儲以及查詢功能

class col
{
public:
    string name;
    int age;
    int index;
    static int nowindex;
    col(string name,int age);
};
int col::nowindex=0;//靜態成員類外初始化
class table
{
    vector<col> cols;//用序號對vector隨機存取
    map<string,int> name2index;//用一個hashtable關聯名字和序號
public:
    void insert(string name,int age);
    int find_age(string name);
    void find_name(char c,int age);
};
col::col(string name,int age){
    index=nowindex;
    nowindex++;
    this->name=name;
    this->age=age;
}
void table::insert(string name,int age){
    col tmp(name,age);
    cols.push_back(tmp);
    name2index[name]=tmp.index;
}
int table::find_age(string name){
    if(name2index.find(name)!=name2index.end()){//判斷map元素是否存在方法
    int index=name2index[name];
    return cols[index].age;
    }
    return -1;
}
void table::find_name(char c,int age){
    int len=cols.size();
    bool has_result=false;
    if(c=='='){
        for(int i=0;i<len;++i)
            if(cols[i].age==age){
                has_result=true;
                cout<<cols[i].name<<endl;
            }
    }else if(c=='>'){
        for(int i=0;i<len;++i)
            if(cols[i].age>age){
                has_result=true;
                cout<<cols[i].name<<endl;
            }
    }else if(c=='<'){
        for(int i=0;i<len;++i)
            if(cols[i].age<age){
                has_result=true;
                cout<<cols[i].name<<endl;
            }
    }else cout<<"error"<<endl;
    if(!has_result)cout<<"not found"<<endl;
}

2、100億條記錄，包括兩個字段{URL,SIZE},用shell抓取出包含baidu的size，并根據size排名

shell以后再復習。。。忘記了。。

思路：如果是C++的話，先找出含有baidu的，然后用堆排序。

第八十三題：實現memcpy函數

PS:注意區間重疊的情況即可

void* memmove(void* dest,const void* src,size_t n){
    if(dest==NULL || src==NULL)return NULL;
    char* byte_src=(char*)src;
    char* byte_dest=(char*)dest;
    int step=1;
    if((size_t)dest<(size_t)src+n){//防止原內存區間與目標區間重疊
        byte_src+=n-1;
        byte_dest+=n-1;
        step=-1;
    }//目標區間比原區間后，則需從最后開始復制
    //雖然重疊但目標在原區間前，則不會沖突
    for(size_t i=0;i<n;++i){
        *byte_dest=*byte_src;
        byte_dest+=step;
        byte_src+=step;
    }
    return dest;
}

第八十四題：

1、用最快的方法找出相同的字符串

思路：（1）hash（2）字典樹

2、字符串中子串的個數

思路：（1）從左往右掃不斷對比，復雜度O（mn）；（2）從左往右的hash，復雜度O（m）

第八十六題：二叉樹存放有序數組

思路：死記硬背不好，只要那個1到7的數組寫出它的前序、中序、后序遍歷二叉樹就知道程序怎么寫了。

//前序遍歷順序。根節點是第一個元素，后面的元素分開兩半，分別遞歸即可。
void BinaryTreeNode::buildfirst(int *a,int n){
    this->m_nValue=a[0];
    int lenleft=(n-1)/2;
    if(lenleft>0){
        this->m_pLeft=new BinaryTreeNode;
        this->m_pLeft->buildfirst(a+1,lenleft);
    }
    if(n-1-lenleft>0){
        this->m_pRight=new BinaryTreeNode;
        this->m_pRight->buildmid(a+1+lenleft,n-lenleft-1);
    }
}

//中序遍歷順序。根節點是中間元素，前后兩段元素分別遞歸即可。
void BinaryTreeNode::buildmid(int *a,int n){
    int mid=n/2;
    this->m_nValue=a[mid];
    if(mid>0){
        this->m_pLeft=new BinaryTreeNode;
        this->m_pLeft->buildmid(a,mid);
    }
    if(n-mid-1>0){
        this->m_pRight=new BinaryTreeNode;
        this->m_pRight->buildmid(a+mid+1,n-mid-1);
    }
}

//后序遍歷順序。根節點是最后一個元素，前面的元素分開兩半，分別遞歸即可。
void BinaryTreeNode::buildlast(int *a,int n){
    this->m_nValue=a[n-1];
    int lenleft=(n-1)/2;
    if(lenleft>0){
        this->m_pLeft=new BinaryTreeNode;
        this->m_pLeft->buildlast(a,lenleft);
    }
    if(n-1-lenleft>0){
        this->m_pRight=new BinaryTreeNode;
        this->m_pRight->buildlast(a+lenleft,n-lenleft-1);
    }
}

第八十七題：大數相乘

思路：用字符串逐位相乘，累加到結果的數組中。最后處理結果數組考慮進位。

string muti(string s1,string s2){
    int len1=s1.length(),len2=s2.length();
    int *i1=new int[len1];
    int *i2=new int[len2];
    int *result=new int[len2+len1];
    memset(result,0,(len1+len2)*sizeof(int));
    for(int i=0;i<len1;++i)
        i1[i]=s1[len1-i-1]-'0';
    for(int i=0;i<len2;++i)
        i2[i]=s2[len2-i-1]-'0';

    for(int i=0;i<len1;i++){
        for(int j=0;j<len2;j++)
            result[i+j]+=i1[i]*i2[j];
    }
    for(int i=0;i<len1+len2;++i){
        if(result[i]>9){
            result[i+1]+=result[i]/10;
            result[i]=result[i]%10;
        }
    }
    string str;
    bool flag=true;
    for(int i=len1+len2-1;i>=0;--i){
        if(flag && result[i]==0)continue;
        flag=false;
        str+=result[i]+'0';
    }
    delete [] i1;
    delete [] i2;
    delete [] result;
    return str;
}

大數相加：

string add(string s1,string s2){
    int len1=s1.length(),len2=s2.length();
    int *i1=new int[len1];
    int *i2=new int[len2];
    int len3=len1>len2?len1+1:len2+1;
    int *result=new int[len3];
    memset(result,0,len3*sizeof(int));
    for(int i=0;i<len1;++i)
        i1[i]=s1[len1-i-1]-'0';
    for(int i=0;i<len2;++i)
        i2[i]=s2[len2-i-1]-'0';

    for(int i=0;i<len3-1;i++){
        if(len1<len2 && i>=len1)
            result[i]=i2[i];
        else if(len2<len1 && i>=len2)
            result[i]=i1[i];
        else result[i]=i1[i]+i2[i];
    }for(int i=0;i<len3;++i){
        if(result[i]>9){
            result[i+1]+=result[i]/10;
            result[i]=result[i]%10;
        }
    }
　　string str;
    bool flag=true;
    for(int i=len3-1;i>=0;--i){
        if(flag && result[i]==0)continue;
        flag=false;
        str+=result[i]+'0';
    }
    delete [] i1;
    delete [] i2;
    delete [] result;
    return str;
}

第八十八題：把*移到字符串前部

思路：記錄兩個坐標，一個是最后一個星，一個是最后一個字母。從后往前掃，掃到字母就與最后一個星交換。

int helper(char *s){
    int len=strlen(s);
    int i=len-1,j=len-1,count=0;
    while(j>=0){//j往前掃，直到不是*，i的位置一定是最后一個*
        if(s[j]!='*'){
            swap(s,i--,j--);//交換了以后，i-1肯定是*
            //如2個*連續則交換后顯然是*；只有1個*的話，下一個就是剛交換的*
        }else{
            count++;
            j--;
        }
    }
    return count;
}

第八十九題：刪除字符串中的數字

思路：與上題基本一致。while循環一次做cursor移動一步，不要再用while，否則代碼不簡潔。

bool is_digit(char c){
    return (c>='0' && c<='9')?true:false;
}
char* helper(char *s){
    int i=0,j=0;
    while(s[j]!='\0'){
        if(!is_digit(s[j]))s[i++]=s[j++];
        else j++;
    }
    s[i]='\0';
    return s;

第九十題：不使用臨時空間翻轉字符串

//模擬一個棧,如果只是翻轉輸出的話
void helper(char *s,int i,int n){
    if(i<n-1){
        helper(s,i+1,n);//沒到最后，先遞歸
        cout<<s[i]<<endl;//遞歸完說明此元素之后的元素已經處理完畢，可處理此元素了
    }
    else cout<<s[i]<<endl;//最后的元素，停止遞歸
}

void helper2(char *s,int n){
    int i=0,j=n-1;
    while(j>i){
        char tmp=s[i];
        s[i]=s[j];
        s[j]=tmp;
        ++i;
        --j;
    }
}

//如何真的連一個char都不能申請只能使用
//想起一種不借助臨時變量交換變量的方法
void helper3(char *s,int n){
    int i=0,j=n-1;
    while(j>i){
        s[i]^=s[j];//左包含ij的與或
        s[j]^=s[i];//右包含jij=i
        s[i++]^=s[j--];//左包含iji=j
    }
}

總結

以上是生活随笔為你收集整理的[微软面试100题]8190的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

微软

上一篇： java实验楼使用说明_Java 方法
下一篇： java sql数组_Sql数组类型解决