Cao Lin's Blog.

CPP map 和 stack

C++ 剑指offer
Word count: 1.3kReading time: 6 min
2020/04/08 Share

1、题目

image-20200408161022984

2、解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// 详细的解释参考：https://blog.csdn.net/Yeoman92/article/details/77868367

class Solution {
typedef vector<int>::iterator ir;

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (ir iter = inorder.begin(); iter != inorder.end(); ++iter) {
            umap[*iter] = iter;
        }
        return SweapLR(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }
private:
    TreeNode* SweapLR(ir pbegin, ir pend, ir ibegin, ir iend)
    {
        if (ibegin == iend) return nullptr;
        // 新建一个节点  preorder 的第一个结点一定是根节点
        TreeNode* cur = new TreeNode(*pbegin);
        if(pend - pbegin == 1) return cur;
        //vector<int>::iterator root = find(ibegin, iend, *pbegin);
        ir root = umap[*pbegin];
        int len = root - ibegin;
        cur->left  = SweapLR(pbegin+1, pbegin+1+len, ibegin, root);
        cur->right = SweapLR(pbegin+1+len, pend, root+1, iend);
        return cur;
    }
private:
    unordered_map<int, ir> umap;

};

/*
执行用时 :20 ms, 在所有 C++ 提交中击败了82.71%的用户
内存消耗 :26.6 MB, 在所有 C++ 提交中击败了100.00%的用户
*/

前序遍历可以很容易找到根节点，然后在中序排列中查找这个根节点的索引位置；

这个位置把中序排序分为了左右部分的树，然后递归遍历即可；

需要注意的是一开始我利用

1
vector<int>::iterator root = find(ibegin, iend, *pbegin);

来查找索引，很耗时间，每次都要找一次；

然后看了一下提交的答案，可以使用一个map，利用结点作为key然后索引作为value，可以考虑为在程序开始前提前把数据读到缓存中，后续可以很快的获取索引，对于需要频繁查找的程序很有用；

但是内存消耗感觉有点大，毕竟把数据重新复制了一遍，不过这种利用map/array，消耗一部分内存以大幅度提高时间的思想值得学习。

3、讲讲map

http://www.cplusplus.com/reference/map/map/

3.1 Overview and feature

  • std::map是一种数据关联的容器，存储按特定顺序由键（key）和值（value）的组合形成的元素。

  • 在map中，key通常用于对元素进行排序和唯一标识，而value存储与该key关联的内容。

  • map通常比unordered_map通过key访问value要慢，但是map允许基于map的顺序直接对子集进行迭代。

  • 可以使用方括号运算符（（operator []）通过对应的键直接访问map中的映射值。

  • map通常实现为二进制搜索树。

3.2、 Member functions

Iterators:

  • begin

    Return iterator to beginning (public member function )

  • end

    Return iterator to end (public member function )

  • rbegin

    Return reverse iterator to reverse beginning (public member function )

  • rend

    Return reverse iterator to reverse end (public member function )

  • cbegin

    Return const_iterator to beginning (public member function )

  • cend

    Return const_iterator to end (public member function )

  • crbegin

    Return const_reverse_iterator to reverse beginning (public member function )

  • crend

    Return const_reverse_iterator to reverse end (public member function )

Capacity:

  • empty

    Test whether container is empty (public member function )

  • size

    Return container size (public member function )

  • max_size

    Return maximum size (public member function )

Element access:

  • operator [ \ ]

    Access element (public member function )

  • at

    Access element (public member function )

Modifiers:

  • insert

    Insert elements (public member function )

  • erase

    Erase elements (public member function )

  • swap

    Swap content (public member function )

  • clear

    Clear content (public member function )

  • emplace

    Construct and insert element (public member function )

  • emplace_hint

    Construct and insert element with hint (public member function )

Observers:

  • key_comp

    Return key comparison object (public member function )

  • value_comp

    Return value comparison object (public member function )

Operations:

  • find

    Get iterator to element (public member function )

  • count

    Count elements with a specific key (public member function )

  • lower_bound

    Return iterator to lower bound (public member function )

  • upper_bound

    Return iterator to upper bound (public member function )

  • equal_range

    Get range of equal elements (public member function )

Allocator:

4、讲讲stack

http://www.cplusplus.com/reference/stack/stack/

4.1 Overview and feature

基础容器可以是任何标准容器类模板或某些其他专门设计的容器类。容器应支持以下操作:

  • empty
  • size
  • back
  • push_back
  • pop_back

标准容器类vector，deque和list满足这些要求。默认情况下，如果没有为特定的stack类实例指定容器类，则使用标准容器deque。

4.2、 Member functions

  • (constructor)

    Construct stack (public member function )

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    // constructing stacks
    #include <iostream>       // std::cout
    #include <stack>          // std::stack
    #include <vector>         // std::vector
    #include <deque>          // std::deque

    int main ()
    {
      std::deque<int> mydeque (3,100);          // deque with 3 elements
      std::vector<int> myvector (2,200);        // vector with 2 elements

      std::stack<int> first;                    // empty stack
      std::stack<int> second (mydeque);         // stack initialized to copy of deque

      std::stack<int,std::vector<int> > third;  // empty stack using vector
      std::stack<int,std::vector<int> > fourth (myvector);

      std::cout << "size of first: " << first.size() << '\n';
      std::cout << "size of second: " << second.size() << '\n';
      std::cout << "size of third: " << third.size() << '\n';
      std::cout << "size of fourth: " << fourth.size() << '\n';

      return 0;
    }

    /*
    Output:
    size of first: 0
    size of second: 3
    size of third: 0
    size of fourth: 2
    */

  • empty

    Test whether container is empty (public member function )

  • size

    Return size (public member function )

  • top

    Access next element (public member function )

  • push

    Insert element (public member function )

  • emplace

    Construct and insert element (public member function )

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    // stack::emplace
    #include <iostream>       // std::cin, std::cout
    #include <stack>          // std::stack
    #include <string>         // std::string, std::getline(string)

    int main ()
    {
      std::stack<std::string> mystack;

      mystack.emplace ("First sentence");
      mystack.emplace ("Second sentence");

      std::cout << "mystack contains:\n";
      while (!mystack.empty())
      {
        std::cout << mystack.top() << '\n';
        mystack.pop();
      }

      return 0;
    }

    /*
    Output:

    mystack contains:
    Second sentence
    First sentence
    */

  • pop

    Remove top element (public member function )

  • swap

    Swap contents (public member function )

Non-member function overloads

Non-member class specializations

Author：Cao Lin

原文链接：http://www.cao-lin.top/2020/04/08/CPP%20map%20stack/

发表日期：April 8th 2020, 4:41:51 pm

更新日期：April 13th 2020, 10:22:40 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 1、题目
  2. 2. 2、解决方案
  3. 3. 3、讲讲map
    1. 3.1. 3.1 Overview and feature
    2. 3.2. 3.2、 Member functions
  4. 4. 4、讲讲stack
    1. 4.1. 4.1 Overview and feature
    2. 4.2. 4.2、 Member functions
  • Non-member function overloads
  • Non-member class specializations
    • Total : 11
    Invalid date
    2020
    Invalid date
    Invalid date
    2020
    Invalid date
    2020
    C++ 剑指offer python 视觉SLAM