leetcode中剑指offer的习题 C++语言实现（1）

面试题5 替换空格

第一种方法使用str的成员函数replace来完成。
第二种方法先创建一个容量足够大的string，然后将源字符串中的元素一个一个加进去，如果遇到空格，则加入%20.

因为返回值是string需要调用构造函数，但是返回值后，局部变量将被销毁，所以调用std::move()将返回值转化为右值，使其调用移动构造函数，可以提高运行速度。

// #include<algorithm>
class Solution {
public:
    // string replaceSpace(string s) {
    //     size_t index = 0;
	// while (true) {
	// 	index = s.find(" ", index);
	// 	if (index!=-1)
	// 	{
	// 		s.replace(s.begin() + index, s.begin() + index + 1, "%20");
	// 	}
	// 	else {
	// 		break;
	// 	}
	// }
    // return s;
    // }
    string replaceSpace(string s) {
size_t count = 0;
	for (size_t i=0;i<s.size();++i)
	{
		if (s[i]==' ')
		{
			++count;
		}
	}
	
	string new_s(s.size()+count*2,' ');
	size_t index = 0;
	for (size_t i = 0; i < s.size(); ++i)
	{
		if (s[i]==' ')
		{
			new_s[index++] = '%';
			new_s[index++] = '2';
			new_s[index++] = '0';
		}
		else {
			new_s[index++] = s[i];
		}
	}
	// cout << new_s << endl;
    //使用move调用移动构造函数
    return std::move(new_s);
    }
};

面试题6 从头到尾打印链表

方法1，使用一个vector保存每一个链表的指针，遍历完链表之后反向输出即可。
方法2，使用递归，将值保存在vector容器中（书中的方法和这种类似）
方法3，因为只强调了逆序输出，所以可以顺序保存，只要将容器中的内容逆向输出即可。

第三种方法需要仔细想一下，因为看到逆序输出我们的直觉往往是先从链表本身开始考虑，但是这道题可以从保存的序列上考虑。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        // vector<int> vec;
        //method 1 使用一个容器保存顺序
        if(head==nullptr){
            vector<int> vec;
            return std::move(vec);
        }
        // vector<ListNode*> arr;
        // // arr.reserve(10000);
        // ListNode* temp=head;
        // while(temp){
        //     arr.push_back(temp);
        //     temp = temp->next;
        // }
        // vector<int> vec(arr.size());
        // size_t index = 0;
        // std::for_each(arr.rbegin(),arr.rend(),[&vec,&index](const ListNode* temp){
        //     vec[index++] = temp->val;
        // });
        // return std::move(vec);
        //method2 使用递归  但是有栈溢出的风险
        // vector<int>vec;
        // get_value(vec,head);
        // return std::move(vec);
        //method3 直接打印，但是逆序输出
        vector<int> vec;
        ListNode* temp=head;
        while(temp){
            vec.push_back(temp->val);
            temp=temp->next;
        }
        std::reverse(vec.begin(),vec.end());
        return vec;
    }
    // void get_value(vector<int>& vec,ListNode* p){
    //     if(p==nullptr){
    //         return;
    //     }else{
    //         get_value(vec,p->next);
    //         // std::cout<<p->val<<std::endl;
    //         vec.push_back(p->val);
    //     }
    // }
};

第三种方法的执行时间最短

面试题7 重建二叉树

和书上的思路差不多，我自己写的还可以优化

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 /*
 思路：
 使用递归的思想

 首先确定第一个根节点，然后再中序遍历中找到这个根结点的位置，以确定左右子树的范围

 有了左右子树的范围，就在子树中寻找根节点，然后在中序遍历中找到这个根节点的位置，再确定左右子树范围

 目前的缺点：其实不用确定范围，只需要确定左右子树的节点数量就可以了。

 如果节点数量为0，那么表示该子树为nullptr。
如果不为零，则继续往下遍历

 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0){
            return nullptr;
        }

        //method1  使用递归的方法
        int cur_index = 0;
        //获取根节点
        TreeNode * p = new TreeNode(preorder[cur_index]);
        //找到根节点在中序遍历中的位置
        size_t inorder_index=  std::find(inorder.begin(), inorder.end(), preorder[cur_index]) - inorder.begin();
        cout<<inorder_index<<endl;
        //确定左右子树在中序遍历中的范围
        int left_begin=0;
        int left_end = inorder_index-1;
        int right_begin = inorder_index+1;
        int right_end = inorder.size()-1;
        //构建左子树
        build(p->left,preorder,inorder,cur_index,left_begin,left_end);
        //构建 右子树
        build(p->right,preorder,inorder,cur_index,right_begin,right_end);
        
        return p;
    }

    void build(TreeNode* &p,vector<int>& preorder, vector<int>& inorder,int &cur_index,int begin,int end){
        //判断当前节点是否应该为空
        // cout<<"cur_index"<<begin<<":"end<<endl;
        // return;
        if(begin>end){
            p=nullptr;
            return;
        }
        ++cur_index;
        //得到当前节点的值
        p = new TreeNode(preorder[cur_index]);
        //找到根节点在中序遍历中的位置
        size_t inorder_index=  std::find(inorder.begin(), inorder.end(), preorder[cur_index]) - inorder.begin();

        //确定左右子树在中序遍历中的范围
        int left_begin=begin;
        int left_end = inorder_index-1;
        int right_begin = inorder_index+1;
        int right_end =end;
         //构建左子树
        build(p->left,preorder,inorder,cur_index,left_begin,left_end);
        //构建 右子树
        build(p->right,preorder,inorder,cur_index,right_begin,right_end);
    }
};