검 지 offer 의 데이터 구조

#ifndef _LD_ARRAY_H_
#define _LD_ARRAY_H_

#include <stack>
#include <queue>

using namespace std;

//  offer，   3，P38，        
bool Find(int *matrix, int rows, int columns, int number){
    bool found = false;

    if (matrix!=nullptr && rows>0 && columns>0)
    {
        int row = 0;
        int column = columns - 1;
        while (row < rows && column >= 0){
            if (matrix[row*columns + column] == number){
                found = true;
                break;
            }
            else if (matrix[row*columns + column]>number){
                column--;
            }
            else{
                row++;
            }
        }
    }

    return found;
}

//   4,    
//   ：      O(N2)
void ReplaceBlank1(char* str, int length){
    if (str != nullptr && length>0){
        cout << str << endl;
        int len = 0;
        int i = 0;
        while (str[i] != '\0'){
            len++;
            i++;
        }
        for (int i = 0; i < len; i++){
            if (str[i] == ' '){
                for (int j = len; j>i; j--){
                    str[j + 2] = str[j];
                }
                str[i] = '%';
                str[i + 1] = '2';
                str[i + 2] = '0';
                len += 2;
            }
        }

        for (int i = 0; i < len; i++){
            cout << str[i];
        }
    }
}
//   ：      O(N)
void ReplaceBlank2(char str[], int length){
    if (str != NULL && length>0){
        int original_length = 0;
        int blank_number = 0;
        int i = 0;

        while (str[i] != '\0'){
            original_length++;
            if (str[i] == ' '){
                blank_number++;
            }
            i++;
        }

        int new_length = original_length + blank_number * 2;
        int index_of_original = original_length;
        int index_of_new = new_length;
        while (index_of_original >= 0 && index_of_new > index_of_original){
            if (str[index_of_original] == ' '){
                str[index_of_new--] = '0';
                str[index_of_new--] = '2';
                str[index_of_new--] = '%';
            }
            else{
                str[index_of_new] = str[index_of_original];
                index_of_new--; 
            }
            index_of_original--;
        }

    }
}

//    
//A1           ,      
void MergeTwoArrays(int A1[], int m, int A2[], int n){
    if (A2 != NULL && n > 0){

        int index1 = m - 1;
        int index2 = n - 1;
        int new_index = m + n - 1;
        while (index1 >= 0 && index2 >= 0){
            if (A1[index1] >= A2[index2]){
                A1[new_index--] = A1[index1--];
            }
            else{
                A1[new_index--] = A2[index2--];
            }
        }
        while (index2 >= 0){
            A1[index2] = A2[index2];
            index2--;
        }
        /*if (index2 > 0){ for (int i = 0; i <= index2; i++){ A1[i] = A2[i]; } }*/


        for (int i = 0; i < m+n; i++){
            cout << A1[i] << ends;
        }
    }
}

//   6,     
struct BinaryTreeNode{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

BinaryTreeNode* ConstructCore(int* start_preorder, int* end_preorder,
    int* start_inorder, int* end_inorder);

BinaryTreeNode* Construct(int preorder[], int inorder[], int length){
    if (preorder == NULL || inorder == NULL || length <= 0){
        return NULL;
    }
    else{
        return ConstructCore(preorder,preorder+length-1,inorder,inorder+length-1);
    }
}

BinaryTreeNode* ConstructCore(int* start_preorder, int* end_preorder,
    int* start_inorder, int* end_inorder){

    //     。
    int root_value = start_preorder[0];
    BinaryTreeNode* root = new BinaryTreeNode();
    root->m_nValue = root_value;
    root->m_pLeft = root->m_pRight = NULL;

    if (start_preorder == end_preorder){
        return root;
    }

    int* root_inorder = start_inorder;
    while (root_inorder <= end_inorder && *root_inorder != root_value){
        root_inorder++;
    }

    int left_length = root_inorder - start_inorder;
    int* left_end_preorder = start_preorder + left_length;
    if (left_length > 0){
        root->m_pLeft=ConstructCore(start_preorder+1, left_end_preorder, start_inorder, root_inorder - 1);
    }
    if (left_length < end_preorder - start_preorder){
        root->m_pRight = ConstructCore(start_preorder + left_length + 1, end_preorder, root_inorder + 1, end_inorder);
    }

    return root;

}
//       
void visit1(BinaryTreeNode* T){
    if (T != NULL){
        BinaryTreeNode* P = new BinaryTreeNode();
        P = T;
        cout << P->m_nValue << ends;
        visit1(P->m_pLeft);
        visit1(P->m_pRight);
    }
}
//       
void visit2(BinaryTreeNode* T){
    if (T != NULL){
        BinaryTreeNode* P = new BinaryTreeNode();
        P = T;

        visit2(P->m_pLeft);
        cout << P->m_nValue << ends;
        visit2(P->m_pRight);
    }
}


//   7，        
template<typename T>
class CQueue{
public:
    CQueue() = default;
    ~CQueue()=default;

    void Push(const T& node){
        stack1.push(node);
    }

    T Pop(){
        T t;
        if (!stack2.empty()){
            t = stack2.top();
            stack2.pop();
        }
        else{
            for (int i = stack1.size(); i > 0; i--){
                stack2.push(stack1.top());
                stack1.pop();
            }
            t = stack2.top();
            stack2.pop();
        }
        return t;
    }

private:
    stack<T> stack1;
    stack<T> stack2;
};

//template<typename T>
//void CQueue::Push(const T& node){
// stack1.push(node);
//}
//
//template<typename T>
//T CQueue::Pop(){
// T t;
// if (!stack2.empty()){
// t = stack2.pop();
// }
// else{
// for (int i = stack1.size(); i > 0; i--){
// stack2.push(stack1.pop());
// }
// t = stack2.pop();
// }
// return t;
//}

//    ，          
template<typename T>
class CStack{
public:
    CStack() = default;
    ~CStack() = default;

    void Push(const T& element){
        queue1.push(element);
    }
    T Pop(){
        T t;
        size_t size;
        if (!queue1.empty()){
            size=queue1.size();  
            //queue1.size()      ，
            //     for(size_t i=1;i<queue1.size();i++), queue1.size()          ，        size 。
            for (size_t i = 1; i < size; i++){
                t = queue1.front();
                queue1.pop();
                queue2.push(t);
            }
            t = queue1.front();
            queue1.pop();
        }
        else if (!queue2.empty()){
            size = queue2.size();
            for (int i = 1; i < size; i++){
                t = queue2.front();
                queue2.pop();
                queue1.push(t);
            }
            t = queue2.front();
            queue2.pop();
        }
        else{
            t = NULL;
        }

        return t;
    }

public:
    queue<T> queue1;
    queue<T> queue2;
};


#endif