【C++】面接アルゴリズム問題C++実現

タイトル1(配列で検索)1つの2次元配列では、各行が左から右に増加する順序でソートされ、各列が上から下に増加する順序でソートされます.関数を完了し、このような2次元配列と整数を入力して、配列に整数が含まれているかどうかを判断します.

class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
    if (array.empty())return false;
    //if (target < array[0][0])return false;
    int _length = array.size();
    for (int i = 0; i < _length; i++)
    {
        if (array[i].empty())continue;
        else if(target >= array[i][0])
        {
            if (target <= array[i][array[i].size() - 1])
            {
                for (int j = array[i].size() - 1; j >= 0; j--)
                {
                    if (target == array[i][j])return 1;
                    else if (target > array[i][j])break;
                }
            }
            else {
                continue;
            }
        }
        else return false;
    }
    return false;
}
};

タイトル2(スペースの置換)では、1つの文字列のスペースを「%20」に置換する関数を実装します.たとえば、文字列がWe Are Happyの場合、置換後の文字列はWe%20 Are%20 Happyになります.

class Solution {
public:
    void replaceSpace(char *str,int length) {
         if(str==NULL)
             return ;
         int CountOfBlanks=0;
         int Originallength=0;
         for(int i=0;str[i]!='\0';i++)
             {
             Originallength++;
             if(str[i]==' ')
                 ++CountOfBlanks;
         }
         int len =Originallength+2*CountOfBlanks;
         if(len+1>length)
             return ;

         char*pStr1=str+Originallength;//     ‘\0’
         char*pStr2=str+len;
        while(pStr1if(*pStr1==' ')
                {
                *pStr2--='0';
                *pStr2--='2';
                *pStr2--='%';    
            }
            else
             {
                 *pStr2--=*pStr1;
            }
            --pStr1;
        }
    }
};

タイトル3(チェーンテーブルを印刷)チェーンテーブルを入力し、チェーンテーブルの各ノードの値を末尾から印刷します.

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution
{
public:
    vector<int> printListFromTailToHead(ListNode* head)
    {
      vector <int>  result;
      stack<int> arr;
      ListNode* p=head;
      while(p!=NULL)
      {
       arr.push(p->val);
       p=p->next;
      }
     int len=arr.size();
     for(int i=0;ireturn  result;
    }

};

タイトル4(ツリーの再構築)あるツリーの前順遍歴と中順遍歴の結果を入力し、ツリーを再構築してください.入力した前順遍歴と中順遍歴の結果に重複する数字が含まれていないと仮定します.たとえば、前順遍歴シーケンス{1,2,4,7,3,5,6}と中順遍歴シーケンス{4,7,2,1,5,3,8,8,6}を入力すると、ツリーが再構築され、戻ります.

/**

     * Definition for binary tree

     * struct TreeNode {

     *     int val;

     *     TreeNode *left;

     *     TreeNode *right;

     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

     * };

     */

    class Solution {

    public:

        struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {

            int inlen=in.size();

            if(inlen==0)

                return NULL;

            vector<int> left_pre,right_pre,left_in,right_in;

            //     ，               

            TreeNode* head=new TreeNode(pre[0]);

            //             ,     gen 

            int gen=0;

            for(int i=0;iif (in[i]==pre[0])

                {

                    gen=i;

                    break;

                }

            }

            //      ，                ，                

            //      ，          

            for(int i=0;i1]);//         

            }

            for(int i=gen+1;i// shell       ，                    

            //  ，           ，        、    ，     

           head->left=reConstructBinaryTree(left_pre,left_in);

           head->right=reConstructBinaryTree(right_pre,right_in);

           return head;

        }

    };

タイトル5(2つのスタックでキューを実装)は2つのスタックで1つのキューを実装し、キューのPushとPop操作を完了します.キューの要素はintタイプです.

class Solution{
public:
    int cou = 0;
    void push(int node) {
        stack1.push_back(node);
        stack2.push_back(cou++);
    }

    int pop() {
        int i = 0;
        while(stack2[i] == -1)
            {
            i++;
        }
        stack2[i] = -1;
        return stack1[i];
    }

private:
    vector<int> stack1;//  
    vector<int> stack2;//  
};

問題6(回転配列の最小数)1つの配列の最初のいくつかの要素を配列の末尾に移動し、配列の回転と呼ぶ.非減算配列の配列の回転を入力し、回転配列の最小要素を出力する.例えば配列{3,4,5,1,2}は{1,2,3,4,5}である.の1つの回転で、配列の最小値は1です.NOTE:与えられたすべての要素は0より大きく、配列サイズが0の場合は0を返します.

#include 
#include 
#include 
#include 
#include 
using namespace std;

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int size = rotateArray.size();
        if(size == 0){
            return 0;
        }//if
        int left = 0,right = size - 1;
        int mid = 0;
        // rotateArray[left] >= rotateArray[right]     
        while(rotateArray[left] >= rotateArray[right]){
            //    
            if(right - left == 1){
                mid = right;
                break;
            }//if
            mid = left + (right - left) / 2;
            // rotateArray[left] rotateArray[right] rotateArray[mid]    
            //                        
            //       
            if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid]){
                return MinOrder(rotateArray,left,right);
            }//if
            //               
            //                
            if(rotateArray[mid] >= rotateArray[left]){
                left = mid;
            }//if
            //               
            //                
            else{
                right = mid;
            }//else
        }//while
        return rotateArray[mid];
    }
private:
    //        
    int MinOrder(vector<int> &num,int left,int right){
        int result = num[left];
        for(int i = left + 1;i < right;++i){
            if(num[i] < result){
                result = num[i];
            }//if
        }//for
        return result;
    }
};

int main(){
    Solution s;
    //vector num = {0,1,2,3,4,5};
    //vector num = {4,5,6,7,1,2,3};
    vector<int> num = {2,2,2,2,1,2};
    int result = s.minNumberInRotateArray(num);
    //   
    cout<return 0;
}

タイトル7(フィボナッチ数列)フィボナッチ数列はみんな知っていますが、今は整数nを入力するように要求されています.フィボナッチ数列のn番目の項目を出力してください.n<=39

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int a = 0,b = 1;
        int m = 0;
        int i;
        for(i = 2;i <= n;i++){
            m = a + b;
            a = b;
            b = m;
        }
        return m;

    }
};

题目の8(階段を跳ぶ)1匹のカエルは一回1段の階段を跳ぶことができて、2段も跳ぶことができます.

class Solution {
public:
    int jumpFloor(int n) {
        int f=1,g=2;
        n--;
        while(n--)
        {
            g+=f;
            f=g-f;
        }
        return f;
    }
};

题目9(変态の阶段を跳ぶ)1匹のカエルは一度に1级の阶段を跳ぶことができて、2级を跳ぶことができます......それもn级を跳ぶことができます.このカエルが1つのn级の阶段を跳ぶことを求めて全部で何种类の跳ぶ方法があります.

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==0)
            return number;
        int total=1;
        for(int i=1;i2;
        return total;
    }
};

题目10(矩形カバー)私达は2*1の小さい矩形で横にあるいは縦にもっと大きい矩形をカバーすることができます.nつの2*1の小さい矩形で重ならずに1つの2*nの大きい矩形をカバーして、全部でいくつの方法がありますか?

class Solution {
public:
    int rectCover(int number) {
        if (number <= 0) {
            return number;
        }
        int f1 = 1;
        int f2 = 2;
        int f3;

        for (int i = 3; i <= number; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
};