160.Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
• listA - The first linked list.
• listB - The second linked list.
• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

Example 1:

1
2
3
4
5

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2:

1
2
3
4

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

1
2
3
4

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

哈希表：

时间复杂度：O(n+m)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> hashtable;
        while(headA != nullptr) {
            hashtable.insert(headA);
            headA = headA->next;
        }
        while(headB != nullptr) {
            if (hashtable.count(headB))return headB;
            headB = headB->next;
        }
        return NULL;
    }
};

双指针：

时间复杂度：O(n+m)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};

145.Binary Tree Postorder Traversal

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Example 1:

1
2

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

1
2

Input: root = []
Output: []

Example 3:

1
2

Input: root = [1]
Output: [1]

递归法：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    void postorder(TreeNode* root, vector<int> &ans_v) {
        if (root == nullptr)return;
        else {
            postorder(root->left,ans_v);
            postorder(root->right,ans_v);
            ans_v.push_back(root->val);
        }
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans_v;
        postorder(root,ans_v);
        return ans_v;
    }
};

迭代法：

时间复杂度：O(n)

空间复杂度：O(n)

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

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode *> stk;
        TreeNode *prev = nullptr;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.emplace(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if (root->right == nullptr || root->right == prev) {
                res.emplace_back(root->val);
                prev = root;
                root = nullptr;
            } else {
                stk.emplace(root);
                root = root->right;
            }
        }
        return res;
    }
};

Morris遍历：

时间复杂度：O(n)

空间复杂度：O(1)

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

class Solution {
public:
    void addPath(vector<int> &vec, TreeNode *node) {
        int count = 0;
        while (node != nullptr) {
            ++count;
            vec.emplace_back(node->val);
            node = node->right;
        }
        reverse(vec.end() - count, vec.end());
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        TreeNode *p1 = root, *p2 = nullptr;

        while (p1 != nullptr) {
            p2 = p1->left;
            if (p2 != nullptr) {
                while (p2->right != nullptr && p2->right != p1) {
                    p2 = p2->right;
                }
                if (p2->right == nullptr) {
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else {
                    p2->right = nullptr;
                    addPath(res, p1->left);
                }
            }
            p1 = p1->right;
        }
        addPath(res, root);
        return res;
    }
};

144.Binary Tree Preorder Traversal

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

Example 1:

1
2

Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:

1
2

Input: root = []
Output: []

Example 3:

1
2

Input: root = [1]
Output: [1]

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    void preorder(TreeNode *root, vector<int> &ans_v) {
        if (root == nullptr)return;
        else {
            ans_v.push_back(root->val);
            preorder(root->left,ans_v);
            preorder(root->right,ans_v);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans_v;
        preorder(root,ans_v);
        return ans_v;
    }
};

迭代法：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (!stk.empty() || node != nullptr) {
            while (node != nullptr) {
                res.emplace_back(node->val);
                stk.emplace(node);
                node = node->left;
            }
            node = stk.top();
            stk.pop();
            node = node->right;
        }
        return res;
    }
};

Morris 遍历：

时间复杂度：O(n)

空间复杂度：O(1)

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

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        TreeNode *p1 = root, *p2 = nullptr;

        while (p1 != nullptr) {
            p2 = p1->left;
            if (p2 != nullptr) {
                while (p2->right != nullptr && p2->right != p1) {
                    p2 = p2->right;
                }
                if (p2->right == nullptr) {
                    res.emplace_back(p1->val);
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else {
                    p2->right = nullptr;
                }
            } else {
                res.emplace_back(p1->val);
            }
            p1 = p1->right;
        }
        return res;
    }
};

141.Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

1
2
3

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

1
2
3

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

1
2
3

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

哈希表：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool hasCycle(ListNode* head) {
        unordered_set<ListNode*> hashtable;
        while (head != nullptr)
        {
            if (hashtable.count(head))return true;
            hashtable.insert(head);
            head = head->next;
        }
        return false;
    }
};

快慢指针：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

136.Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

1
2

Input: nums = [2,2,1]
Output: 1

Example 2:

1
2

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

1
2

Input: nums = [1]
Output: 1

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) {
            int temp = *it;
            it++;
            if (it == nums.end()||temp != *it)return temp;
        }
        return 0;
    }
};

位运算：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8

class Solution {
    public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e: nums) ret ^= e;
        return ret;
    }
};

常用容器

string容器

基本概念

• string是C++风格的字符串，本质上是一个类。其内部封装了char*。

• 成员函数主要有find，copy，delete，replace，insert

构造函数

• string();//生成空string

• string(const char* s);//以字符串s初始化

• string(const string& str);//以string对象初始化另一个string对象

• string(int n, char c);//以n个字符c初始化

赋值操作

• string& operator=(const char* s);

• string& operator=(const string &s);

• string& operator=(char c);

• string& assign(const char *s)

• string& assign(const char *s, int n)

• string& assign(const string &s)

• string& assign(int n, char c);

字符串拼接

• string& operator+=(const char* str);

• string& operator+=(const char c);

• string& operator+=(const string& str);

• string& append(const char* s)

• string& append(const char* s,int n);

• string& append(const string& str);

• string& append(const string &s,int pos,int n);//字符串s中从pos开始的n个字符连接到字符串结尾

查找和替换

• int find(const string& str, int pos = 0) const;//从pos开始查找str出现的第一次位置

• int find(const char* s,int pos = 0) const//从pos开始查找s出现的第一次位置

• int fing(const char* s, int pos, int n) const;//从pos开始查找s的前n个字符出现的第一次位置

• int find(const char c,int pos = 0) const//从pos开始查找c出现的第一次位置

• int rfind(const string& str, int pos = npos) const;//从pos开始查找str出现的最后一次位置

• int rfind(const char* s,int pos = npos) const//从pos开始查找s出现的最后一次位置

• int rfind(const char* s, int pos, int n) const;//从pos开始查找s的前n个字符出现的最后一次位置

• int find(const char c,int pos = 0) const//从pos开始查找c出现的最后一次位置

• sting& replace(int pos, int n, const string& str)//替换从pos开始n个字符为字符串str

• sting& replace(int pos, int n, const char* s)//替换从pos开始n个字符为字符串s

• find是从左往右，rfind是从右往左，二者都是寻找第一次找到的字符或字符串，故从结果上来看find的结果是从左到右第一次出现的位置，rfind的结果是从左到右最后一次出现的位置。

• find和rfind找不到字符时返回-1。

• replace在替换时要指定替换的开始位置、字符数量和字符内容。

字符串比较

• 比较方式：按ASCII码进行比较。
  = 返回 0
  > 返回 1
  < 返回 -1

• int compare(const string& s) const;

• int compare(const char* s) const;

字符串存取

• char& operator[](int n);//通过[]取字符

• char& at(int n);//通过at取字符

插入和删除

• string& insert(int pos, const char* s);

• string& insert(int pos, const string& str);

• string& insert(int pos, int n, char c);//在pos位置插入n个字符c

• string& erase(int pos, int n = npos);//删除从pos开始的n个字符

• string& erase(pos);//删除pos处的一个字符

• erase(first,last);//删除从first到last之间的字符

• 插入和删除的下标都是从0开始。

子串

• string substr(int pos = 0, int n = npos) const;//返回从pos开始的n个字符组成的字符串

vector容器

基本概念

• vector数据结构和数组十分相似，也称为单端数组。

• 数组是静态空间，而vector可以动态扩展。
  动态扩展：并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间

• vector的迭代器是支持随机访问的迭代器

构造函数

• vector<T> v;//采用模板实现类实现，默认构造函数

• vector<T> v(num)//创建容量为num的vector，默认值为0

• vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身

• vector(n, elem);//将n个elem拷贝给本身

• vector(const vector& vec);//拷贝构造

赋值操作

• vector& operator=(const vector& vec);

• assign(beg, end);//将[beg, end)区间中的元素拷贝给本身

• assign(n, elem);//将n个elem拷贝给本身

容量和大小

• empty();//判断容器是否为空

• capacity();//容器的容量

• size();//容器的元素的个数

• resize(int num);//重新指定容器的长度为num。若容器变长，则以默认值填充新位置；若容器变短，则多出的元素将被删除。

• resize(int num, elem);//重新指定容器的长度为num。若容器变长，则以elem填充新位置；若容器变短，则多出的元素将被删除。

插入和删除

• push_back(elem);//尾插元素elem

• pop_back();//删除最后一个元素

• insert(const_iterator pos, elem);//迭代器指向位置pos插入元素elem

• insert(const_iterator pos, int count, elem);//迭代器指向位置pos插入count个元素elem

• erase(const_iterator pos);//删除迭代器指向的元素

• erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素

• clear();//删除容器中所有元素

数据存取

• at(int idx);//返回索引idx所指的数据

• operator[];

• front();//返回容器中的第一个元素

• back();//返回容器中的最后一个元素

互换容器

• swap(vec);//将vec与本身的元素互换

• swap可以使两个容器互换，可以达到收缩内存效果。

预留空间

• reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问

• 预留空间可以减少vector在动态扩展容量时的扩展次数。如果数据量较大，可以一开始利用reserve预留空间。

deque容器

基本概念

• vector对于头部的插入效率低，数据量越大，效率越低。deque相对而言对头部的插入速度更快。但是vector访问元素的速度更快。这与两者内部的实现有关。

• 内部工作原理：deque内部有个中控器，维护每段缓冲区的内容，缓冲区中存放真实数据。中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间。

• deque容器的迭代器也是支持随机访问的。

构造函数

• deque<T>depT;

• deque(beg,end);//将[beg, end)区间中的元素拷贝给本身

• deque(n,elem);//将n个elem拷贝给本身

• deque(const deque& dep);//拷贝构造函数

赋值操作

• deque& operator=(const deque& dep);

• assign(beg, end);//将[beg, end)区间中的元素拷贝给本身

• assign(n, elem);//拷贝构造函数

大小操作

• deque.empty();//判断容器是否为空

• deque.size();//返回容器中元素的个数

• deuqe.resize(int num);//重新指定容器的长度为num。若容器变长，则以默认值填充新位置；若容器变短，则多出的元素将被删除。

• dque.resize(int num, elem);//重新指定容器的长度为num。若容器变长，则以elem填充新位置；若容器变短，则多出的元素将被删除。

• deque容器没有容量的概念。

插入和删除

• push_back(elem);//在容器尾部添加一个数据

• push_front(elem);//在容器头部添加一个数据

• pop_back;//删除容器的最后一个数据

• pop_front;//删除容器的第一个数据

• insert(pos, elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置

• insert(pos, n, elem);//在pos位置插入n个elem数据，无返回值

• insert(pos, beg, end);//在pos位置插入[beg,end)区间的数据，无返回值。

• clear();//清除所有数据

• erase(beg, end);//删除[beg, end)区间的数据u，返回下一个数据的位置

• erase(pos);//删除pos位置的数据，返回下一个数据的位置

• 插入和删除提供的位置是迭代器

数据存取

• at(int, idx);//返回索引idx所指的数据

• operator[];

• front();//返回第一个元素

• end();//返回最后一个元素

排序

• sort(iterator beg, iterator end);//对beg和end之间的元素进行排序

• sort算法使用时应包含头文件 algorithm。

stack容器

基本概念

stack是一种先进后出的数据结构，它只有一个出口。栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为。栈中进出数据称为入栈，栈中弹出数据称为出栈。

常用接口

构造函数

• stack<T> stk;

• stack(const stack& stk);//拷贝构造

赋值操作

• stack& operator=(const stack& stk);

数据存取

• push(elem);//向栈顶添加数据

• pop();//从栈顶移除一个数据

• top();//返回栈顶元素

大小操作

• empty();//判断堆栈是否为空

• size();//返回栈的大小

queue容器

基本概念

queue是一种先进先出的数据结构，它有两个出口。队列容器允许从一端新增元素，从另一端移除元素。队列中只允许队头和队尾才可以被外界使用，因此队列不允许有遍历行为。队列中进数据称为入队(push)，出数据称为出队(pop)。

构造函数

• queue<T> que;

• queue(const queue& que);//拷贝构造

赋值操作

• queue& operator=(const queue& que);

数据存取

• push(elem);//往队尾添加元素

• pop();//删除队头第一个元素

• back();//返回最后一个元素

• front();//返回第一个元素

大小操作

• empty();//判断堆栈是否为空

• size();//返回栈的大小

list容器

基本概念

• 链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针连接实现的。链表由一系列结点组成。结点有数据域和下一个结点地点的指针域组成。STL的链表是一个双向循环链表。由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器。

• list的优点是采用动态存储分配，不会造成内存浪费和溢出；链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。

• list的缺点是链表灵活，但是空间（指针域）和时间（遍历）额外耗费较大。

• list有一个重要的性质，插入和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

构造函数

• list<T> lst;

• list(beg, end);//将[beg, end)区间中的元素拷贝给本身

• list(n, elem);//将n个elem拷贝给本身

• list(const list& lst);//拷贝构造函数

赋值与交换

• assign(beg, end);//将[beg, end)区间中的元素拷贝给本身

• asign(n, elem);//将n个elem拷贝给本身

• list& operator = (const list& lst);

• swap(lst);//将lst于本身的元素互换

大小操作

• size();//返回容器中元素的个数

• empty();//判断容器是否为空

• resize();//重新指定容器的长度为num。若容器变长，则以默认值填充新位置；若容器变短，则多出的元素将被删除。

• resize(int num, elem);//重新指定容器的长度为num。若容器变长，则以elem填充新位置；若容器变短，则多出的元素将被删除。

插入和删除

• push_back(elem);//尾插一个元素

• pop_back();//删除最后一个元素

• push_front(elem);//在容器开头插入一个元素

• pop_front();//删除第一个元素

• insert(pos, elem);//在pos位置插elem元素的拷贝

• insert(pos, n, elem);//在pos位置插入n个elem

• insert(pos, beg, end);//在pos位置插入[beg, end)区间的数据，无返回值

• clear();//删除容器所有元素

• erase(beg, end);//删除[beg, end)区间的数据，返回下一个元素的位置

• erase(pos);//删除pos位置的数据，返回下一个数据的位置

• remove(elem);//删除容器中所有与elem值匹配的元素

数据存取

• front();//返回第一个元素

• back();//返回最后一个元素

• list容器中不可以通过[]或者at方式访问数据。

反转和排序

• reverse();//反转链表

• sort();//链表排序

set/ multiset容器

基本概念

• 所有元素都会在插入时自动排序。

• set/ multiset属于关联式容器，底层结构由二叉树实现。

• 区别：set不允许容器中有重复的元素；multiset允许容器中有重复元素。

构造和赋值

• set<T> st;

• set(const set& st);//拷贝构造函数

• set& operator=(const set& st);

大小和交换

• size();//返回容器中元素的个数

• empty();//判断容器是否为空

• swap();//交换两个容器

插入和删除

• insert(elem);//插入元素elem

• clear();//清空容器

• erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器

• erase(beg, end);//删除区间[beg, end)的所有元素，返回下一个元素的迭代器

• erase(elem);//删除容器中所有与elem值匹配的元素

查找和统计

• find(key);//查找key是否存在，若存在返回该元素的迭代器；若不存在返回set.end()

• count(key);//统计key的元素个数（对于set，结果为0或1）

set和multiset的区别

• set不可以插入重复数据，而multiset可以。

• set插入数据的同时会返回插入结果，表示插入是否成功。返回的内容为对组，first为迭代器，second为bool。

• multiset不会检测数据，因此可以插入重复数据。

pair对组创建

• pair<type, type> p ( value1, value2 );

• pair<type, type> p = make_pair( value, value2 );

容器排序

set/ multiset容器容器默认排序规则为从小到大，可利用仿函数改变排序规则。

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
46
47

#include <set>
#include <string>
class Person {
    public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }
    string m_Name;
    int m_Age;
};
//仿函数
class comparePerson {
    public:
    bool operator()(const Person& p1, const Person &p2) {
        //按照年龄进行排序  降序
        return p1.m_Age > p2.m_Age;
    }
};

void test01()
{
    set<Person, comparePerson> s;

    Person p1("刘备", 23);
    Person p2("关羽", 27);
    Person p3("张飞", 25);
    Person p4("赵云", 21);

    s.insert(p1);
    s.insert(p2);
    s.insert(p3);
    s.insert(p4);

    for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age << endl;
    }
}
int main() {

    test01();

    system("pause");

    return 0;
}

map/ multimap容器

基本概念

• map/ multimap容器中所有容器都是pair。

• pair中第一个元素为key，起到索引作用，第二个元素为value。

• 所有元素都会根据元素的key自动排序。

• map/ multimap容器数据关联式容器，底层结构由二叉树实现。

• 可以根据key值快速找到value值。

• 区别：map不允许容器中有重复key值元素；multimap允许容器中有重复key值元素。

构造和赋值

• map<T1, T2> mp;

• map(const map& mp);//拷贝构造函数

• map& operator=(const map& mp);

大小和交换

• size();//返回容器中元素的数目

• empty();//判断容器是否为空

• swap(st);//交换两个容器

插入和删除

• map中所有元素都是成对出现，插入数据时候要使用对组

• insert(elem);//插入元素elem

• clear();//清除所有元素

• erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器

• erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器

• erakey(key);//删除容器中值为key的元素

查找和统计

• find(key);//查找key是否存在，若存在返回该元素的迭代器；若不存在返回map.end()

• count(key);//统计key的元素个数（对于map，结果为0或1）

容器排序

map/ multimap容器容器默认排序规则为从小到大，可利用仿函数改变排序规则。

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

#include <map>

class MyCompare {
    public:
    bool operator()(int v1, int v2) {
        return v1 > v2;
    }
};

void test01() {
    //默认从小到大排序
    //利用仿函数实现从大到小排序
    map<int, int, MyCompare> m;

    m.insert(make_pair(1, 10));
    m.insert(make_pair(2, 20));
    m.insert(make_pair(3, 30));
    m.insert(make_pair(4, 40));
    m.insert(make_pair(5, 50));

    for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
        cout << "key:" << it->first << " value:" << it->second << endl;
    }
}
int main() {

    test01();

    system("pause");

    return 0;
}

常用算法

• 算法主要是由头文件<algorithm> <functional> <numeric> 组成。

• 是所有STL头文件中最大的一个，范围涉及到比较、 交换、查找、遍历操作、复制、修改等等

• 体积很小，只包括几个在序列上面进行简单数学运算的模板函数

• 定义了一些模板类,用以声明函数对象。

常用遍历算法

for_each

• for_each(iterator beg, iterator end, _func);// beg 开始迭代器; end 结束迭代器; _func 函数或者函数对象

• 实现容器的遍历

transform

• transform(iterator beg1, iterator end1, iterator beg2, _func);//beg1 源容器开始迭代器; end1 源容器结束迭代器; beg2 目标容器开始迭代器; _func 函数或者函数对象

• 搬运容器到另一个容器中

• 搬运的目标容器必须要提前开辟空间，否则无法正常搬运

常用查找算法

find

• find(iterator beg, iterator end, value);//beg 开始迭代器; end 结束迭代器; value 查找的元素

• 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

find_if

• find_if(iterator beg, iterator end, _Pred);// beg 开始迭代器; end 结束迭代器; _Pred 函数或者谓词（返回bool类型的仿函数）

• 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

adjacent_find

• adjacent_find(iterator beg, iterator end);//beg 开始迭代器; end 结束迭代器

• 查找相邻重复元素,返回相邻元素的第一个位置的迭代器

binary_search

• bool binary_search(iterator beg, iterator end, value);// beg 开始迭代器;end 结束迭代器;value 查找的元素

• 查找指定的元素，查到 返回true 否则false

• 在无序序列中不可用

count

• count(iterator beg, iterator end, value);// beg 开始迭代器; end 结束迭代器; value 统计的元素

• 统计元素出现次数

• 统计自定义数据类型时，需要配合重载 operator==

count_if

• count_if(iterator beg, iterator end, _Pred);// beg 开始迭代器; end 结束迭代器; _Pred 谓词

• 按条件统计元素出现次数

常用排序算法

sort

• sort(iterator beg, iterator end, _Pred);//beg 开始迭代器; end 结束迭代器; _Pred 谓词

• 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

random_shuffle

• random_shuffle(iterator beg, iterator end);//beg 开始迭代器; end 结束迭代器

• 指定范围内的元素随机调整次序

• 使用时需要添加随机数种子

merge

• merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//beg1 容器1开始迭代器; end1 容器1结束迭代器; beg2 容器2开始迭代器; end2 容器2结束迭代器; dest 目标容器开始迭代器

• 容器元素合并，并存储到另一容器中

• 两个容器必须是有序的

reverse

• reverse(iterator beg, iterator end);//beg 开始迭代器; end 结束迭代器

• 反转指定范围的元素

常用拷贝和替换算法

copy

• copy(iterator beg, iterator end, iterator dest); //beg 开始迭代器; end 结束迭代器; dest 目标起始迭代器

• 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

replace

• replace(iterator beg, iterator end, oldvalue, newvalue);//beg 开始迭代器; end 结束迭代器; oldvalue 旧元素; newvalue 新元素

• 将区间内旧元素 替换成 新元素

replace_if

• replace_if(iterator beg, iterator end, _Pred, newvalue);//beg 开始迭代器; end 结束迭代器; _pred 谓词; newvalue 替换的新元素

• 按条件替换元素，满足条件的替换成指定元素

swap

• swap(container c1, container c2);//c1容器1; c2容器2

• 互换两个容器的元素，两个容器要同种类型

常用算术生成算法

• 算术生成算法属于小型算法，使用时包含的头文件为#include

accumulate

• accumulate(iterator beg, iterator end, value);//beg 开始迭代器； end 结束迭代器； value 起始值

• 计算容器元素累计总和

fill

• fill(iterator beg, iterator end, value); //beg 开始迭代器; end 结束迭代器; value 填充的值

• 向容器中填充指定元素

常用集合算法

set_intersection

• set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);// beg1 容器1开始迭代器; end1 容器1结束迭代器; beg2 容器2开始迭代器; end2 容器2结束迭代器; dest 目标容器开始迭代器

• 求两个集合的交集

• 两个集合必须是有序序列

• 目标容器开辟空间需要从两个容器中取小值

• set_intersection返回值既是交集中最后一个元素的位置

set_union

• set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//beg1 容器1开始迭代器; end1 容器1结束迭代器; beg2 容器2开始迭代器; end2 容器2结束迭代器; dest 目标容器开始迭代器

• 求两个集合的并集

• 两个集合必须是有序序列

• 目标容器开辟空间需要两个容器相加

• set_union返回值既是并集中最后一个元素的位置

set_difference

• set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//beg1 容器1开始迭代器; end1 容器1结束迭代器; beg2 容器2开始迭代器; end2 容器2结束迭代器; dest 目标容器开始迭代器

• 求两个集合的差集

• 两个集合必须是有序序列

• 目标容器开辟空间需要从两个容器取较大值

• set_difference返回值是差集中最后一个元素的位置

125.Valid Palindrome
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

1
2
3

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

1
2
3

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

1
2
3
4

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool isPalindrome(string s) {
        for (string::iterator it = s.begin(); it != s.end();) {
            if (*it >= 'A' && *it <= 'Z')*it += 32;
            else if ((*it < 'a' || *it>'z')  && (*it < '0' || *it>'9')) {
                s.erase(it);
                continue;
            }
            it++;
        }
        string backup = s;
        reverse(s.begin(), s.end());
        return backup == s;
    }
};

优化：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for (char ch: s) {
            if (isalnum(ch)) {
                sgood += tolower(ch);
            }
        }
        string sgood_rev(sgood.rbegin(), sgood.rend());
        return sgood == sgood_rev;
    }
};

双指针：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        int left = 0, right = n - 1;
        while (left < right) {
            while (left < right && !isalnum(s[left])) {
                ++left;
            }
            while (left < right && !isalnum(s[right])) {
                --right;
            }
            if (left < right) {
                if (tolower(s[left]) != tolower(s[right])) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
};

121.Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

1
2
3
4

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

1
2
3

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max = prices[0];
        int min = prices[0];
        int ans = 0;
        for (int price : prices) {
            if (price < min) {
                min = price;
                max = price;
            }
            if (price > max)max = price;
            if (ans < (max - min))ans = max - min;
        }
        return ans;
    }
};

119. Pascal’s Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

1
2

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

1
2

Input: rowIndex = 0
Output: [1]

Example 3:

1
2

Input: rowIndex = 1
Output: [1,1]

个人解答：

时间复杂度：O(rowIndex)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans_v(rowIndex+1);
        for (int i = 0; i <= rowIndex; ++i) {
            ans_v[0] = 1;
            ans_v[i] = 1;
            vector<int>temp_v = ans_v;
            for (int j = 1; j < i; ++j) {
                ans_v[j] = temp_v[j] + temp_v[j - 1];
            }
        }
        return ans_v;
    }
};

进一步优化（一个数组）：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            for (int j = i; j > 0; --j) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};

118.Pascal’s Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

1
2

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

1
2

Input: numRows = 1
Output: [[1]]

时间复杂度：O(numRows^2^)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans_v(numRows);
        for (int i = 0; i < numRows; ++i) {
            ans_v[i].resize(i + 1);
            ans_v[i][0] = 1;
            ans_v[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                ans_v[i][j] = ans_v[i - 1][j] + ans_v[i - 1][j - 1];
            }
        }
        return ans_v;
    }
};