Cao Lin's Blog.

CPP vector 简介

C++ 剑指offer
Word count: 817Reading time: 3 min
2020/04/03 Share

1、题目

image-20200403134846769

如上题所示，我们可以观察到右上角和左下角是有规律的；

例如左下角：

  • 若当前vector的值比target大，那么就应该往上移动，这一行都不可能查找到target；

  • 若当前vector的值比target小，则应该往右边移动，这一列都不可能查找到target；

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
class Solution {
public:
    // 利用 w++(右)/--(左) , h++(下)/--(上)控制遍历方向；

    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (!matrix.size()) { return false;}
        
        int w = matrix[0].size() -1; //宽，列数
        int h = matrix.size() - 1;   //高，行数
        int i=0 ;

        while(h >= 0 && i <= w)
        {
            if (matrix[h][i] > target) {--h;}
            else if (matrix[h][i] < target) {++i;}
            else if (matrix[h][i] == target) {return true;}
        }
        return false;
    }
};

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

以左下角为起点进行遍历，思路如上所述；

3、讲讲vector

cplusplus.com

3.1 Overview and feature
  • vector 是可以改变大小的序列容器，一样的连续的储存方式也就是说可以利用指针偏移进行访问，效率和数组相同；
  • vector 容器可能会分配一些额外的存储空间以适应可能的增长，因此，该容器的实际容量可能会大于包含其元素（即其大小）所严格要求的存储容量，以避免每一次添加新元素都进行内存分配。
  • 与数组相比，向量消耗更多的内存以换取管理存储和以有效方式动态增长的能力。
  • 其他动态序列容器（双端队列，列表和forward_lists）相比，向量可以像数组一样访问其元素方面非常有效，并且从其末尾添加或删除元素都相对高效。对于涉及在末尾以外的位置插入或删除元素的操作，它们的性能比其他方法差，并且与list和forward_lists相比，迭代器和引用的一致性更差。
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:

  • size

    Return size (public member function )

  • max_size

    Return maximum size (public member function )

  • resize

    Change size (public member function )

  • capacity

    Return size of allocated storage capacity (public member function )

  • empty

    Test whether vector is empty (public member function )

  • reserve

    Request a change in capacity (public member function )

  • shrink_to_fit

    Shrink to fit (public member function )

Element access:

  • operator[ ]

    Access element (public member function )

  • at

    Access element (public member function )

  • front

    Access first element (public member function )

  • back

    Access last element (public member function )

  • data

    Access data (public member function )

Modifiers:

  • assign

    Assign vector content (public member function )

  • push_back

    Add element at the end (public member function )

  • pop_back

    Delete last element (public member function )

  • 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_back

    Construct and insert element at the end (public member function )

Allocator:

3.3、 Non-member function overloads

  • relational operators

    Relational operators for vector (function template )

  • swap

    Exchange contents of vectors (function template )

3.4、 Template specializations

  • vector

    Vector of bool (class template specialization )

Author：Cao Lin

原文链接：http://www.cao-lin.top/2020/04/03/CPPvector%E6%93%8D%E4%BD%9C/

发表日期：April 3rd 2020, 1:42:04 pm

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

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

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