解決面試題的思路--5

　　前言：很多面試題都很抽象，不是很容易找到解決的辦法。畫圖可以幫助自己去分析、推理面試題。下面用幾個例題進行舉例。

　　面試題19：

　　鏡像對于很多人來說是一個新的概念，未必一下子能想出來樹的鏡像；于是可以自己畫一下，代碼如下：

#include<iostream>
#include<cstdlib>
using namespace std;

struct BinaryTreeNode
{
    int data;                                                    //節點資料
    BinaryTreeNode *lchild,*rchild;        //左孩子、右孩子
};
typedef struct BinaryTreeNode tree_t;

/******
    構造一個二叉樹 遞歸實作
    參數：形參1：開始值，形參2：結束值
 ******/
tree_t *CreateTree(int i, int max) 
{
    //遞歸結束條件
    if(i > max)
    {
        return NULL;  //  == return 0;
    }
    
    tree_t *T;

    T = (tree_t *)malloc(sizeof(tree_t));    

    T->data = i;
    T->lchild = CreateTree(2*i, max); 
    T->rchild = CreateTree(2*i+1, max);
    return T;
}

//先序周遊輸出二叉樹
void FirstRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return ;
    cout << " " << p->data;    
    FirstRoot_DLR(p->lchild);
    FirstRoot_DLR(p->rchild);
}

//中序周遊輸出二叉樹 程式中未使用
void MiddleRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return;
    
    MiddleRoot_DLR(p->lchild);
    cout << " " << p->data;    
    MiddleRoot_DLR(p->rchild);
}

//後序周遊輸出二叉樹 程式中未使用
void LastRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return;
    
    LastRoot_DLR(p->lchild);    
    LastRoot_DLR(p->rchild);
    cout << " " << p->data;
}

void MirrorRecursively(tree_t *pNode)
{
    if((pNode==NULL) || (pNode->lchild==NULL&&pNode->rchild==NULL))
        return;

    tree_t *pTemp = pNode->lchild;
    pNode->lchild = pNode->rchild;
    pNode->rchild = pTemp;

    if(pNode->lchild)
        MirrorRecursively(pNode->lchild);
        
    if(pNode->rchild)
        MirrorRecursively(pNode->rchild);
}

int main()
{
    tree_t *T1 = CreateTree(1,3);
    FirstRoot_DLR(T1);
    cout << endl;
    MirrorRecursively(T1);    
    FirstRoot_DLR(T1);
    cout << endl; 
    
    return 0;
}

　　面試題20：

　　題目如下：

　　代碼如下：

#include<iostream>
using namespace std;

void printNum(int num)
{
    cout << " " << num;
}

void PrintMatrixInCircle(int (*numbers)[4],int col,int row,int start)
{
    int endX = col-1-start;
    int endY = row-1-start;

    //從左到右列印一行
    for(int i=start;i<endX;++i)
    {
        int num = numbers[start][i];
        printNum(num);
    }
    //從上到下列印一行
    if(start < endY)
    {
        for(int i=start+1;i<=endY;++i)
        {
            int num = numbers[i][endX];
            printNum(num);
        }
    }
    //從右到左列印一行
    if(start<endX && start<endY)
    {
        for(int i=endX-1;i>=start;--i)
        {
            int num = numbers[endY][i];
            printNum(num);
        }
    }
    //從下到上列印一行
    if(start<endX && start<endY-1)
    {
        for(int i=endY-1;i>=start+1;--i)
        {
            int num = numbers[i][start];
            printNum(num);
        }
    }
}

void PrintMatrixClockwisely(int (*numbers)[4],int col,int row)
{
    
    if(numbers==NULL || col<=0 || row<=0)
        return;

    int start = 0;
    

    while(col>start*2 && row>start*2)
    {
        PrintMatrixInCircle(numbers,col,row,start);
        ++start;
    }
    
}

int main()
{
    int num[4][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
    
    PrintMatrixClockwisely(num,4,4);
    cout << endl;
    
    return 0;
}

　　面試題21：

　　面試題如下：

　　分析:對于時間複雜度O(1)的實作，主要使用兩個棧來實作的，代碼如下：

#include<stack>
#include<assert.h>
#include<iostream>
#include<vector>
#include<cstdlib>
#include<string>
#include<stdexcept>
using namespace std;

//模闆類
template <typename T>
class StackWithMin{
    private:
        stack<int> m_data;    //資料棧
        stack<int> m_min;     //輔助棧
    public:
        void push(const T&);
        void pop();
        T min() const;
};

template <typename T> void StackWithMin<T>::push(const T& value)
{
    m_data.push(value);

    if(m_min.size()==0 || value<m_min.top())
        m_min.push(value);
    else
        m_min.push(m_min.top());
}

template <typename T> void StackWithMin<T>::pop()
{
    assert(m_data.size()>0 && m_min.size()>0);

    m_data.pop();
    m_min.pop();
}

template <typename T> T StackWithMin<T>::min() const
{
    assert(m_data.size()>0 && m_min.size()>0);

    return m_min.top();
}

int main()
{
    StackWithMin<int> intStack;
    
    //壓入棧
    intStack.push(2);
    intStack.push(6);
    intStack.push(1);
    intStack.push(0);
    intStack.push(9);
    //彈出棧
    intStack.pop();
    
    //取最小值
    cout << "min: " << intStack.min() << endl;

    return 0;
}

　　面試題23：

　　分析：考察對二叉樹和隊列的了解，靈活運用資料結構的特點進行碼代碼，代碼如下：

#include<iostream>
#include<cstdlib>
#include<deque>
using namespace std;

struct BinaryTreeNode
{
    int data;                                                    //節點資料
    BinaryTreeNode *lchild,*rchild;        //左孩子、右孩子
};
typedef struct BinaryTreeNode tree_t;

/******
    構造一個二叉樹 遞歸實作
    參數：形參1：開始值，形參2：結束值
 ******/
tree_t *CreateTree(int i, int max) 
{
    //遞歸結束條件
    if(i > max)
    {
        return NULL;  //  == return 0;
    }
    
    tree_t *T;

    T = (tree_t *)malloc(sizeof(tree_t));    

    T->data = i;
    T->lchild = CreateTree(2*i, max); 
    T->rchild = CreateTree(2*i+1, max);
    return T;
}

//先序周遊輸出二叉樹
void FirstRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return ;
    cout << " " << p->data;    
    FirstRoot_DLR(p->lchild);
    FirstRoot_DLR(p->rchild);
}

//中序周遊輸出二叉樹 程式中未使用
void MiddleRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return;
    
    MiddleRoot_DLR(p->lchild);
    cout << " " << p->data;    
    MiddleRoot_DLR(p->rchild);
}

//後序周遊輸出二叉樹 程式中未使用
void LastRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return;
    
    LastRoot_DLR(p->lchild);    
    LastRoot_DLR(p->rchild);
    cout << " " << p->data;
}

//STL自帶的deque(兩端都可以進出的隊列)
void PrintFromTopToBottom(tree_t *pTreeRoot)
{
    if(!pTreeRoot)
        return;

    deque<tree_t *> dequeTreeNode;
    dequeTreeNode.push_back(pTreeRoot);

    while(dequeTreeNode.size())
    {
        tree_t *pNode = dequeTreeNode.front();
        dequeTreeNode.pop_front();

        cout << " " << pNode->data;

        if(pNode->lchild)
            dequeTreeNode.push_back(pNode->lchild);
        if(pNode->rchild)
            dequeTreeNode.push_back(pNode->rchild);
    }
}

int main()
{
    tree_t *T1 = CreateTree(1,5);
    FirstRoot_DLR(T1);
    cout << endl;
    PrintFromTopToBottom(T1);
    cout << endl;    
    
    return 0;
}

　　面試題24：

　　先簡單介紹一下題目中的二叉搜尋樹的特點：左子樹總比根節點小，右子樹總比根節點大。代碼如下：

#include<iostream>
#include<cstdlib>
#include<deque>
using namespace std;

struct BinaryTreeNode
{
    int data;                                                    //節點資料
    BinaryTreeNode *lchild,*rchild;        //左孩子、右孩子
};
typedef struct BinaryTreeNode tree_t;

bool VerifySquenceOfBST(int data[],int len)
{
    if(data==NULL || len<=0)
        return false;

    int root = data[len-1];

    //二叉搜尋樹的左子樹節點小于根節點
    int i = 0;
    for(;i<len-1;++i)
    {
        if(data[i] > root)
            break;
    }
    //二叉搜尋樹的右子樹大于根節點
    int j = i;
    for(;j<len-1;++j)
    {
        if(data[j] < root)
            return false;
    }
    //判斷左子樹是不是二叉搜尋樹
    bool left = true;
    if(i > 0)
        VerifySquenceOfBST(data,i);

    //判斷右子樹是不是二叉搜尋樹
    bool right = true;
    if(j > 0)
        VerifySquenceOfBST(data,j);

    return (left && right);
}

int main()
{
    int data[]={5,7,6,9,11,10,8};
    cout << boolalpha << VerifySquenceOfBST(data,7) << endl;    
    
    return 0;
}

　　面試題15：

#include<iostream>
#include<cstdlib>
#include<deque>
#include<stdio.h>
#include<vector>
using namespace std;

struct BinaryTreeNode
{
    int data;                                                    //節點資料
    BinaryTreeNode *lchild,*rchild;        //左孩子、右孩子
};
typedef struct BinaryTreeNode tree_t;

/******
    構造一個二叉樹 遞歸實作
    參數：形參1：開始值，形參2：結束值
 ******/
tree_t *CreateTree(int i, int max) 
{
    //遞歸結束條件
    if(i > max)
    {
        return NULL;  //  == return 0;
    }
    
    tree_t *T;

    T = (tree_t *)malloc(sizeof(tree_t));    

    T->data = i;
    T->lchild = CreateTree(2*i, max); 
    T->rchild = CreateTree(2*i+1, max);
    return T;
}

//先序周遊輸出二叉樹
void FirstRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return ;
    cout << " " << p->data;    
    FirstRoot_DLR(p->lchild);
    FirstRoot_DLR(p->rchild);
}

//中序周遊輸出二叉樹 程式中未使用
void MiddleRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return;
    
    MiddleRoot_DLR(p->lchild);
    cout << " " << p->data;    
    MiddleRoot_DLR(p->rchild);
}

//後序周遊輸出二叉樹 程式中未使用
void LastRoot_DLR(tree_t *p)
{
    if(p == NULL)
        return;
    
    LastRoot_DLR(p->lchild);    
    LastRoot_DLR(p->rchild);
    cout << " " << p->data;
}

void FindPath(tree_t *pRoot,int num,vector<int> &path,int &cursum)
{
    cursum += pRoot->data;
    path.push_back(pRoot->data);

    //如果是根節點，并且路徑上的和等于輸入的值
    //列印出這條路徑
    bool isLeaf = pRoot->lchild==NULL && pRoot->rchild==NULL;
    if(cursum==num && isLeaf)
    {
        cout << "A path is found: ";
        vector<int>::iterator iter = path.begin();
        for(;iter!=path.end();++iter)
            printf("%d\t",*iter);

        printf("\n");
    }

    //如果不是葉節點，則周遊子節點
    if(pRoot->lchild != NULL)
        FindPath(pRoot->lchild,num,path,cursum);
    if(pRoot->rchild != NULL)
        FindPath(pRoot->rchild,num,path,cursum);

    //再傳回子節點之前,在路徑上删除目前節點
    //并在cursum中減去目前節點的值
    cursum -= pRoot->data;
    path.pop_back();
}

void FindPath(tree_t *pRoot,int num)
{
    if(pRoot == NULL)
        return;

    vector<int> path;
    int cursum = 0;
    FindPath(pRoot,num,path,cursum);
}

int main()
{
    tree_t *T1 = CreateTree(1,5);
    FirstRoot_DLR(T1);
    cout << endl;
    FindPath(T1,8);
    
    return 0;
}

　　總結：主要培養一種思想，通過舉例的方法讓抽象問題變為具體化。

作者：

柳德維

出處：

https://www.cnblogs.com/liudw-0215/

-------------------------------------------

個性簽名：獨學而無友，則孤陋而寡聞。做一個靈魂有趣的人！

如果覺得這篇文章對你有小小的幫助的話，記得在右下角點個“推薦”哦，部落客在此感謝！

萬水千山總是情，打賞一分行不行，是以如果你心情還比較高興，也是可以掃碼打賞部落客，哈哈哈(っ•̀ω•́)っ⁾⁾！

解決面試題的思路--5

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述