剣指Offer 06テーマ解析&C++stack&C++vector

タイトル
チェーンテーブルのヘッダノードを入力し、各ノードの値を末尾から逆に返します(配列で返します).
例1:
入力:head=[1,3,2]出力:[2,3,1]
制限:
0<=チェーンテーブル長<=10000
作者:Krahetsリンク:https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dt66m/出典:力扣(LeetCode)著作権は作者の所有である.商業転載は著者に連絡して許可を得てください.非商業転載は出典を明記してください.
構想
構想一:スタック、先進的な後出の構造特徴実現過程の流れ:

要素リストから出入りスタック

を取り出す

スタックから取り出しvector

に入れる
考え方二:再帰法の流れ:

はまずチェーンテーブル末端

に渡す.

遡及時に、ノード値を順次リストに加えることで、チェーンテーブル値の逆順出力

を実現することができる.
広がる
C++ vector

vectorとは何ですか?

ベクトル(Vector)は、ダイナミックサイズ配列をカプセル化したシーケンシャルコンテナである.他のタイプのコンテナと同様に、さまざまなタイプのオブジェクトを格納できます.ベクトルは任意のタイプの動的配列を格納できると簡単に考えられる.

容器特性

1 .シーケンス順序コンテナの要素は、厳密な線形順序でソートされます.対応する要素には、要素のシーケンス内の位置からアクセスできます.
2.動的配列は、シーケンス内の任意の要素への迅速な直接アクセスをサポートし、ポインタの計算によってもこの操作を行うことができます.操作は、シーケンスの最後に要素を比較的迅速に追加/削除する操作を提供します.
3.メモリディスペンサを感知できる(Allocator-aware)コンテナは、メモリディスペンサオブジェクトを使用して、メモリ要件を動的に処理します.

基本関数実装

1.コンストラクタ

vector():     vector
vector(int nSize):    vector,     nSize
vector(int nSize,const t& t):    vector，     nSize,    t
vector(const vector&):      
vector(begin,end):  [begin,end)            vector 
 

2.関数の追加

void push_back(const T& x):          X
iterator insert(iterator it,const T& x):                 x
iterator insert(iterator it,int n,const T& x):             n      x
iterator insert(iterator it,const_iterator first,const_iterator last):                       [first,last)    

3.関数の削除

iterator erase(iterator it):             
iterator erase(iterator first,iterator last):     [first,last)    
void pop_back():            
void clear():         

4.遍歴関数

reference at(int pos):  pos       
reference front():        
reference back():        
iterator begin():       ，       
iterator end():       ，                
reverse_iterator rbegin():     ，        
reverse_iterator rend():     ，            

5.判定関数

bool empty() const:        ，   ，       

6.サイズ関数

int size() const:          
int capacity() const:                
int max_size() const:        vector     

7.その他の関数

void swap(vector&):            
void assign(int n,const T& x):      n      x
void assign(const_iterator first,const_iterator last):   [first,last)            

8.はっきり見える
1.push_back配列の最後にデータを追加
2.pop_back配列の最後のデータを削除
3.at番号付け位置のデータを得る
4.begin配列ヘッダを得るポインタ
5.end配列の最後のセル+1を得るポインタ
6.front配列ヘッダの参照を得る
7.back配列の最後のセルの参照を得る
8.max_size vectorを得る最大サイズはどれくらいですか?
9.capacity現在のvector割り当てのサイズ
10.size現在使用されているデータのサイズ
11.resize現在使用されているデータのサイズを変更し、現在使用されているデータより大きい場合はデフォルト値を入力します.
12.reserve現在のvecotrに割り当てられている空間のサイズを変更する
13.eraseポインタが指すデータ項目の削除
14.clear現在のvectorをクリア
15.rbegin vector反転後の開始ポインタを返す(実は元のend-1)
16.rend vector反転構造の終了ポインタを返す(実は元のbegin-1)
17.empty vectorが空かどうかを判断する
18.swapは別のvectorとデータを交換する

簡単な紹介

#include < vector> 
using namespace std;
 Vector<  >   
Vector<  >   (    )
Vector<  >   (    ,     )
Int i[5]={
     1,2,3,4,5}
Vector<  >vi(I,i+2);//  i    3    
Vector< vector< int> >v;     //     <>    。               

参照:参照1
C++ stack

概要

このデータ構造はLIFO技術を用い,LIFOは後進先出を表す.最初に挿入した要素は、最後に抽出されます.「top」という要素があります.一番上の位置にある要素です.すべての挿入と削除操作は、スタックの上部要素自体で行われます.
適用領域のスタックは、コンテナアダプタであることを示します.
コンテナは、次のアクションリストをサポートする必要があります.
empty
size
back
push_back
pop_back

構文

  template<class T, class Container = deque<T> > class stack;

T:パラメータコンテナアダプタが保持する要素のタイプを指定します.
Container:パラメータはコンテナの内部オブジェクトを指定し、スタックの要素を収容します.

関数

 (constructor)	           。
empty()	             。      ，      true，    false。
size()	            ，                 。
top()	              。            ，                      。
push()	               。
pop()	         ，           。
emplace()	                       。
swap()	                 。
relational operators	                 。
uses allocator<stack>	    ，             。

参照:参照1
ソースコード

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 //F1：    ，              ；      0(N)      O(N)
class Solution {
     
public:
    vector<int> reversePrint(ListNode* head) {
     

        vector<int> res;
        stack<int> sta;


        //    ，     
        ListNode* work = head;
        while (work) {
     
            sta.push(work->val);
            work = work->next;
        }
        //       ，    
        while (!sta.empty()) {
     
            //       ，  vector  
            res.push_back(sta.top());
            sta.pop();
        }
        return res;
    }
};
//F2:   :    ，        ；   ，          ，            。
//      O(N)：     ，   N  
//      O(N)：          O(N)    。
class Solution {
     
private:
    vector<int>res;
public: 
    vector<int> reversePrint(ListNode* head) {
     
        recurent(head);
        return res;
    }
    void recurent(ListNode* head) {
     
        if (head == nullptr) {
     
            return;
        }
        recurent(head->next);
        res.push_back(head->val);
    }
    
};