剑指Offer.C++.code1-5

剑指offer 代码实现 C++
剑指Offer

1. 二维数组中的查找

// 每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序
// Solution: 从右上角或左下角开始查找，对比target大小可逐步排除整行/整列
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        bool flag = false;
        int row = array.size();
        if (row > 0) {
            int col = array[0].size();
            int i = 0, j = col-1;
            while(i < row && j >= 0) {
                if (array[i][j] == target) {
                    flag = true;
                    break;
                } else if (array[i][j] > target)
                    j --;
                else
                    i ++;
            }
        }
        return flag;
    }
};

2. 替换空格

// length 为字符串总容量
// Soluntion: 先统计有多少个blank，再从后向前赋值
// Attention: 1. 注意原始str空间不足的情况；2. 注意复制字符串末尾的'\0'
class Solution {
public:
    void replaceSpace(char *str,int length) {
        if (str == NULL && length <= 0) {
            return;
        }
        int oriStrLen = 0;
        int blankCount = 0;
        for (int i = 0; str[i] != '\0'; i ++) {
            if (' ' == str[i])
                blankCount ++;
            oriStrLen ++;
        }
        int newStrLen = oriStrLen + 2*blankCount;
        if (newStrLen > length) {// 原始str空间不足
            return;
        }
        int j = newStrLen;
        for (int i = oriStrLen; i >= 0; i --) {
            if (0 == blankCount)
                break;
            if (str[i] == ' ') {
                str[j --] = '0';
                str[j --] = '2';
                str[j --] = '%';
                blankCount --;
            } else {
                str[j --] = str[i];
            }
        }
    }
};

3. 从尾到头打印链表

// 返回从尾部到头部的列表值序列，例如[1,2,3]
// Attention: 要求不改变输入数据
// Solution：（1）使用先入后出的栈；（2）使用递归，但在递归层太多时可能导致函数调用栈溢出
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        stack<int> vals;
        
        ListNode* pNode = head;
        while(pNode != NULL) {
            vals.push(pNode->val);
            pNode = pNode->next;
        }
        
        vector<int> res;
        while(!vals.empty()) {
            res.push_back(vals.top());
            vals.pop();
        }
        return res;
    }
};

4. 重建二叉树

// 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
// Solution:前序遍历第一个值为根节点，中序遍历左子树的值都在根节点值左侧，右子树值在右侧，然后递归构建树
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if (pre.size() == 0 || vin.size() == 0)
            return NULL;
        return construct(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
    }
    
    TreeNode* construct(vector<int> pre, int preStart, int preEnd,
                        vector<int> vin, int vinStart, int vinEnd) {
        // 开始位置大于结束位置，已经没有需要处理的元素
        if (preStart > preEnd) {
            return NULL;
        }
        
        // 找到根节点root，及中序遍历的root_index
        int root = pre[preStart];
        int root_vin_index = vinStart;
        while (root_vin_index <= vinEnd && vin[root_vin_index] != root) {
            root_vin_index ++;
        }
        // 如果在中序遍历中找不到root值，抛出异常
        if (vin[root_vin_index] != root) {
            printf("Invalid input.");
            return NULL;
        }
        // 创建根节点并赋值
        TreeNode* node = new TreeNode(root);
        
        // 递归构建左子树，元素有left = root_vin_index - vinStart个
        // 左子树前序遍历位置[preStart+1, preStart+left]
        // 左子树中序遍历位置[vinStart, root_vin_index-1]
        node->left = construct(pre, preStart+1, preStart+root_vin_index-vinStart,
                              vin, vinStart, root_vin_index-1);
        // 递归构建右子树，元素有right = vinEnd - root_vin_index个
        // 右子树前序遍历位置[preStart+left+1, preEnd]
        // 右子树中序遍历位置[root_vin_index+1, vinEnd]
        node->right = construct(pre, preStart+root_vin_index-vinStart+1, preEnd,
                               vin, root_vin_index+1, vinEnd);
        return node;
    }
};

5. 用两个栈实现队列

// Solution: 当stack2不为空时，弹出top()；当stack2为空时，将stack1中所有元素压入stack2，再弹出top().
// Tips：两个队列实现栈，相当于每次弹出队尾的元素
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        
        if (stack2.empty()) {
            printf("Queue is empty!");
            return NULL;
        }
        
        int head = stack2.top();
        stack2.pop();
        return head;
    }

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