C++数据结构总览_c++数据结构总结

数据结构

你好！ 这是基于LeetCode上题目和定义总结出来的一篇关于C++数据结构的个人总结。(施工中~
使用:---------:居中
使用:----------居左
使用----------:居右

撤销：Ctrl/Command + Z
重做：Ctrl/Command + Y
加粗：Ctrl/Command + B
斜体：Ctrl/Command + I
标题：Ctrl/Command + Shift + H
无序列表：Ctrl/Command + Shift + U
有序列表：Ctrl/Command + Shift + O
检查列表：Ctrl/Command + Shift + C
插入代码：Ctrl/Command + Shift + K
插入链接：Ctrl/Command + Shift + L
插入图片：Ctrl/Command + Shift + G
查找：Ctrl/Command + F
替换：Ctrl/Command + G

队列 & 栈

设计循环队列

数组和字符串

链表

解决链表问题最好的办法就是把问题链表在纸上画出来

面试要点
链表时一个包含零个或多个元素的数据结构。每个元素都包含一个值和到另一个元素的链接。根据链接数的不同，可以分为单链表，双链表和多重链表。

单链表是最简单的一种，它提供了在常数时间内的 addAtHead 操作和在线性时间内的 addAtTail 的操作。双链表是最常用的一种，因为它提供了在常数时间内的 addAtHead 和 addAtTail 操作，并且优化的插入和删除。

双链表在 Java 中的实现为 LinkedList，在 Python 中为 list。这些结构都比较常用，有两个要点：

• 哨兵节点：

哨兵节点在树和链表中被广泛用作伪头、伪尾等，通常不保存任何数据。

我们将使用伪头来简化我们简化插入和删除。

• 双链表的双向搜索：我们可以从头部或尾部进行搜索。

设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。 addAtIndex(index,val)：在链表中的第
• index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index有效，则删除链表中的第 index 个节点。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

提示：

所有val值都在 [1, 1000] 之内。
操作次数将在 [1, 1000] 之内。
请不要使用内置的 LinkedList 库。
其一 单链表

class MyLinkedList {
public:
        /** Initialize your data structure here. */
        MyLinkedList(): size(0) {
            dummy_node = new SinglyListNode(-1);
        }

        /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
        int get(int index) {
            if (index < 0 || index >= size) {
                return -1;
            }

            SinglyListNode *curr = dummy_node;
            for (int i = 0; i < index + 1; ++i) {
                curr = curr->next;
            }
            return curr->val;
        }

        /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
        void addAtHead(int val) {
            addAtIndex(0, val);
        }

        /** Append a node of value val to the last element of the linked list. */
        void addAtTail(int val) {
            addAtIndex(size, val);
        }

        /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
        void addAtIndex(int index, int val) {
            if (index > size) return;

            if(index < 0) index = 0;

            SinglyListNode *prev = dummy_node;
            for (int i = 0; i < index; ++i) {
                prev = prev->next;
            }

            SinglyListNode *newNode = new SinglyListNode(val);
            newNode->next = prev->next;
            prev->next = newNode;

            size++;
        }

        /** Delete the index-th node in the linked list, if the index is valid. */
        void deleteAtIndex(int index) {
            if (index < 0 || index >= size) return;

            SinglyListNode *prev = dummy_node;
            for (int i = 0; i < index; ++i) {
                prev = prev->next;
            }

            SinglyListNode *deletedNode = prev->next;
            prev->next = prev->next->next;

            delete deletedNode;
            deletedNode = nullptr;

            --size;
        }

private:
        // Definition for singly-linked list.
        struct SinglyListNode {
            int val;
            SinglyListNode *next;
            SinglyListNode(int x) : val(x), next(NULL) {}
        };
        SinglyListNode *dummy_node; // 哑结点
        int size; // 链表的长度
};

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

其二 双链表

class MyLinkedList {
private:
        struct MyListNode
        {
            int val;
            MyListNode* prev;
            MyListNode* next;     
            MyListNode(int x): val(x),prev(nullptr),next(nullptr){}
        };    
        int size;
        MyListNode *head,*tail;   
public:
    /** Initialize your data structure here. */
    //head->node0->node1->...->nodex->tail

        MyLinkedList() {
        size = 0;
        //null pointer for head&tail
        head = new MyListNode(0);
        tail = new MyListNode(0);
        head->next = tail;
        tail->prev = head;
        }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
        //if the index is invalid
        if(index>=size||index<0)return -1;
        
        //choose the fast way to get the index-th node in the linked list
        //curr node = the index-th node
        MyListNode* curr = getNode(index);
        if(curr==nullptr)return -1;
        else
        return curr->val;

    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    void addAtHead(int val) {
            addAtIndex(0,val);
            return;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
            addAtIndex(size,val);  
            return;
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    void addAtIndex(int index, int val) {
        if(index>size)return;

        if(index<=0)
        {
            index = 0;
        }
        MyListNode *curr = head;
        if(size/2 >= index)
        {
            //target = index;
            for(int i = 0; i < index+1; i++) 
            {
                curr = curr -> next;
            }
        }
        else
        {
            //target = size - index - 1;
            curr = tail;
            for(int i = 0; i < size - index; i++)
                curr = curr -> prev;
        }
        
        //insert node to list  
        size++;
        MyListNode *prev, *succ;
        prev = curr->prev;
        succ = curr;
        MyListNode *toAdd = new MyListNode(val);
        toAdd->prev = prev;
        toAdd->next = succ;
        prev->next = toAdd;
        succ->prev = toAdd;

        return;
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    //pred->toDelete->succ
    void deleteAtIndex(int index) {
        if(index>=size||index<0)return;

        MyListNode *pred, *succ;
        pred = getNode(index)->prev;
        succ = getNode(index)->next;
        //delete node
        size--;
        pred->next = succ;
        succ->prev = pred;
        return;
    }
    MyListNode* getNode(int index) //获得目标节点位置，因为是双向链表，通过判断目标点位置在前半段还是后半段来决定从head开始搜索还是从tail搜索
    {
        if(index >= size || index < 0)  return nullptr;
        MyListNode* node;
        if(size/2 >= index)
        {
            //target = index;
            node = head;
            for(int i = 0; i < index+1; i++) 
            {
                node = node -> next;
            }
        }
        else
        {
            //target = size - index - 1;
            node = tail;
            for(int i = 0; i < size - index; i++)
                node = node -> prev;
        }
        return node;
    }

};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

双指针技巧

环形列表

让我们从一个经典问题开始：

给定一个链表，判断链表中是否有环。

你可能已经使用哈希表提出了解决方案。但是，使用双指针技巧有一个更有效的解决方案。在阅读接下来的内容之前，试着自己仔细考虑一下。

我们在链表中使用两个速度不同的指针时会遇到的情况：

• 如果没有环，快指针将停在链表的末尾。
• 如果有环，快指针最终将与慢指针相遇。

所以剩下的问题是：

这两个指针的适当速度应该是多少？

一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

在此基础上，我们如何检测链表中是否存在环？

方法一：哈希表

思路

我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表。

算法

我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_map <ListNode *,int> m;
        while(head)
        {
            m[head]++;
            if(m[head] > 1)      return true;
            head = head->next;
        }
        return false;
    }
};

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

复杂度分析

• 时间复杂度：O(n)，对于含有 n 个元素的链表，我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 O(1)
  的时间。
• 空间复杂度：O(n)，空间取决于添加到哈希表中的元素数目，最多可以添加 n 个元素。

方法二：双指针

思路

想象一下，两名运动员以不同的速度在环形赛道上跑步会发生什么？

算法

通过使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。慢指针每次移动一步，而快指针每次移动两步。

如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。

现在考虑一个环形链表，把慢指针和快指针想象成两个在环形赛道上跑步的运动员（分别称之为慢跑者与快跑者）。而快跑者最终一定会追上慢跑者。这是为什么呢？考虑下面这种情况（记作情况 A）- 假如快跑者只落后慢跑者一步，在下一次迭代中，它们就会分别跑了一步或两步并相遇。

其他情况又会怎样呢？例如，我们没有考虑快跑者在慢跑者之后两步或三步的情况。但其实不难想到，因为在下一次或者下下次迭代后，又会变成上面提到的情况 A。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr)return false;
        ListNode *slow,*fast;
        slow= head;
        fast= head;
        //iteration once
        while(fast->next!=nullptr)
        {
            slow= slow->next;
            if(fast->next==nullptr||fast->next->next==nullptr)return false;
            fast= fast->next->next;
            if(slow==fast)
            {
                return true;            
            }
        }
        return false;
    }
};
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

复杂度分析

时间复杂度：O(n)，让我们将 nn 设为链表中结点的总数。为了分析时间复杂度，我们分别考虑下面两种情况。

• 链表中不存在环： 快指针将会首先到达尾部，其时间取决于列表的长度，也就是 O(n)。
• 链表中存在环：** 我们将慢指针的移动过程划分为两个阶段：非环部分与环形部分：

因此，在最糟糕的情形下，时间复杂度为 O(N+K)，也就是 O(n)。

空间复杂度：O(1)，我们只使用了慢指针和快指针两个结点，所以空间复杂度为 O(1)。

接下来我们考虑另一个问题：

如何找到链表中环的起始点？

方法 1：哈希表
想法

如果我们用一个 Set 保存已经访问过的节点，我们可以遍历整个列表并返回第一个出现重复的节点。

算法

首先，我们分配一个 Set 去保存所有的列表节点。我们逐一遍历列表，检查当前节点是否出现过，如果节点已经出现过，那么一定形成了环且它是环的入口。否则如果有其他点是环的入口，我们应该先访问到其他节点而不是这个节点。其他情况，没有成环则直接返回 null 。

算法会在遍历有限个节点后终止，这是因为输入列表会被分成两类：成环的和不成环的。一个不成欢的列表在遍历完所有节点后会到达 null - 即链表的最后一个元素后停止。一个成环列表可以想象成是一个不成环列表将最后一个 null 元素换成环的入口。

如果 while 循环终止，我们返回 null 因为我们已经将所有的节点遍历了一遍且没有遇到重复的节点，这种情况下，列表是不成环的。对于循环列表， while 循环永远不会停止，但在某个节点上， if 条件会被满足并导致函数的退出。

复杂度分析

时间复杂度：O(n)

不管是成环还是不成环的输入，算法肯定都只会访问每个节点一次。对于非成环列表这是显而易见的，因为第 nn 个节点指向 null ，这会让循环退出。对于循环列表， if 条件满足时会导致函数的退出，因为它指向了某个已经访问过的节点。两种情况下，访问的节点数最多都是 nn 个，所以运行时间跟节点数目成线性关系。

空间复杂度：O(n)

不管成环或者不成欢的输入，我们都需要将每个节点插入 Set 中一次。两者唯一的区别是最后访问的节点后是 null 还是一个已经访问过的节点。因此，由于 Set 包含 nn 个不同的节点，所需空间与节点数目也是线性关系的。

方法 2：Floyd 算法
想法

当然一个跑得快的人和一个跑得慢的人在一个圆形的赛道上赛跑，会发生什么？在某一个时刻，跑得快的人一定会从后面赶上跑得慢的人。

算法

Floyd 的算法被划分成两个不同的 阶段 。在第一阶段，找出列表中是否有环，如果没有环，可以直接返回 null 并退出。否则，第二个阶段用 相遇节点 来找到环的入口。

阶段 1

这里我们初始化两个指针 - 快指针和慢指针。我们每次移动慢指针一步、快指针两步，直到快指针无法继续往前移动。如果在某次移动后，快慢指针指向了同一个节点，我们就返回它。否则，我们继续，直到 while 循环终止且没有返回任何节点，这种情况说明没有成环，我们返回 null 。

下图说明了这个算法的工作方式：

证明：

阶段 2

给定阶段 1 找到的相遇点，阶段 2 将找到环的入口。首先我们初始化额外的两个指针： ptr1 ，指向链表的头， ptr2 指向相遇点。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点。

下面的图将更好的帮助理解和证明这个方法的正确性。

我们利用已知的条件：慢指针移动 1 步，快指针移动 2 步，来说明它们相遇在环的入口处。（下面证明中的 tortoise 表示慢指针，hare 表示快指针）

因为 F=b ，指针从 h 点出发和从链表的头出发，最后会遍历相同数目的节点后在环的入口处相遇。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr)return NULL;
        ListNode *slow,*fast;
        slow= head;
        fast= head;
        //iteration once
        while(fast->next!=nullptr)
        {
            slow= slow->next;
            if(fast->next==nullptr||fast->next->next==nullptr)return NULL;
            fast= fast->next->next;
            if(slow==fast)
            {
                ListNode *ptr = head;
                while(ptr!=slow)
                {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;            
            }
        }
        return NULL;        
    }
};
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

时间复杂度为O(n),空间复杂度为O(1)。

相交链表

接下来我们将思考另一个问题

如何判断相交链表以及两链表之间的相交点？

方法一: 暴力法
对链表A中的每一个结点ai，遍历整个链表 B 并检查链表 B 中是否存在结点和ai相同。

复杂度分析

• 时间复杂度 : O(mn)。
• 空间复杂度 : O(1)。

方法二: 哈希表法
遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点bi
是否在哈希表中。若在，则bi为相交结点。

复杂度分析

• 时间复杂度 : O(m+n)。
• 空间复杂度 : O(m) 或 O(n)。

方法三：双指针法
创建两个指针 pA 和 pB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。
当 pA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pB 到达链表的尾部时，将它重定位到链表 A 的头结点。若在某一时刻 pA 和 pB 相遇，则 pA/pB 为相交结点。

方法3初看很难理解，但是细想就会发现很简单很巧妙 A和B两个链表长度可能不同，但是A+B和B+A的长度是相同的。假设A表长度为a+x，B表长度为b+x，x为共同长度（a>b），则遍历A和遍历B一遍后，pA经过的路程为a+x,pB经过的路程为b+x+(a-b) = a+x,再经过路程b后同时到达交点共经过a+b+x总路程。
如果两个链表存在相交，它们末尾的结点必然相同。因此当 pA/pB 到达链表结尾时，记录下链表 A/B 对应的元素。若最后元素不相同，则两个链表不相交。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pA,*pB;
        int valA,valB;
        pA = headA;
        pB = headB;
        while(pA!=pB)
        {
			//特别注意是在指针指需要指向另一个链表时的条件，不然很容易死循环，都是泪呀。
            //A+B = B+A
            pA = (pA==NULL)?headB:pA->next;
            pB = (pB==NULL)?headA:pB->next;
        }
        return pA;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析

• 时间复杂度 : O(m+n)。
• 空间复杂度 : O(1)。

删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

方法一：两次遍历算法
思路

我们注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第 (L - n + 1)个结点，其中 L
是列表的长度。只要我们找到列表的长度 L，这个问题就很容易解决。

算法

首先我们将添加一个哑结点作为辅助，该结点位于列表头部。**哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。**在第一次遍历中，我们找出列表的长度 LL。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 (L - n)个结点那里。我们把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2)个结点，完成这个算法。

复杂度分析

时间复杂度：O(L)，该算法对列表进行了两次遍历，首先计算了列表的长度 L 其次找到第(L−n) 个结点。 操作执行了 2L-n 步，时间复杂度为 O(L)。

空间复杂度：O(1)，我们只用了常量级的额外空间。

。
方法二：一次遍历算法

算法

上述算法可以优化为只使用一次遍历。我们可以使用两个指针而不是一个指针。第一个指针从列表的开头向前移动 n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n个结点。删除时，我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //dummy node is used as a buffer head node
        //dummy->next = head
        ListNode *dummy = new ListNode();
        dummy->next = head;
        //double pointer
        ListNode *p1,*p2;
        p1 = dummy;
        p2 = dummy;
        // Advances first pointer so that the gap between first and second is n nodes apart
        for(int i=0;i<n+1;++i)
        {p2 = p2->next;}
        // Move first to the end, maintaining the gap between p1 and p2 is n
        while(p2!=nullptr)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        //delete p1->next node
        p1->next =p1->next->next;  
        
        return dummy->next;

    }
};
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

小结 - 链表中的双指针

在这里，我们为你提供了一个模板，用于解决链表中的双指针问题。

// Initialize slow & fast pointers
ListNode* slow = head;
ListNode* fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow && fast && fast->next) {
    slow = slow->next;          // move slow pointer one step each time
    fast = fast->next->next;    // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意事项
链表与我们在数组中学到的内容类似。但它可能更棘手而且更容易出错。你应该注意以下几点：

1. 在调用 next 字段之前，始终检查节点是否为空。

获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。

2. 仔细定义循环的结束条件。

运行几个示例，以确保你的结束条件不会导致无限循环。在定义结束条件时，你必须考虑我们的第一点提示。

复杂度分析
空间复杂度分析容易。如果只使用指针，而不使用任何其他额外的空间，那么空间复杂度将是 O(1)。但是，时间复杂度的分析比较困难。为了得到答案，我们需要分析运行循环的次数。

在前面的查找循环示例中，假设我们每次移动较快的指针 2 步，每次移动较慢的指针 1 步。
如果没有循环，快指针需要 N/2 次才能到达链表的末尾，其中 N 是链表的长度。
如果存在循环，则快指针需要 M 次才能赶上慢指针，其中 M 是列表中循环的长度。
显然，M <= N 。所以我们将循环运行 N 次。对于每次循环，我们只需要常量级的时间。因此，该算法的时间复杂度总共为 O(N)。

自己分析其他问题以提高分析能力。别忘了考虑不同的条件。如果很难对所有情况进行分析，请考虑最糟糕的情况。

经典问题

反转链表

让我们从一个经典问题开始：

反转一个单链表。

方法一：迭代
一种解决方案是按原始顺序迭代结点，并将它们逐个移动到列表的头部。
在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！

在该算法中，每个结点只移动一次。因此，时间复杂度为 O(N)，其中 N 是链表的长度。我们只使用常量级的额外空间，所以空间复杂度为 O(1)。

这个问题是你在面试中可能遇到的许多链表问题的基础。如果你仍然遇到困难，我们的下一端中将更多地讨论实现细节。还有许多其他的解决方案。您应该熟悉至少一个解决方案并能够实现它。

方法二：递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr)return head;

        ListNode *p = reverseList(head->next);
        //nk+1->next = nk   
        // tail node: n1->next = nullptr
        head->next->next = head;
        head->next = nullptr;
        return p;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度分析

时间复杂度：O(n)，假设 n 是列表的长度，那么时间复杂度为 O(n)。
空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。

删除链表元素：哨兵节点简化

哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们是纯功能的，通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。

算法：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *sentinel = new ListNode(0);
        sentinel->next = head;
        ListNode *prev, *curr, *toDelete;
        prev = sentinel;
        curr = head;
        while(curr!=nullptr)
        {
            if(curr->val ==val)
            {
                toDelete = curr;
                prev->next = curr->next;
            }else prev = curr;
            
            curr = curr->next;
            //Delete node
            if(toDelete!=nullptr)
            {
                delete toDelete;
                toDelete = nullptr;
            }
        }
        return sentinel->next;
    }
};
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

奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
示例 1:

输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

说明:

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

解法

将奇节点放在一个链表里，偶链表放在另一个链表里。然后把偶链表接在奇链表的尾部。

算法

这个解法非常符合直觉思路也很简单。但是要写一个精确且没有 bug 的代码还是需要进行一番思索的。

一个 LinkedList 需要一个头指针和一个尾指针来支持双端操作。我们用变量 oddhead 和 odd 保存奇链表的头和尾指针。 evenHead 和 even 保存偶链表的头和尾指针。算法会遍历原链表一次并把奇节点放到奇链表里去、偶节点放到偶链表里去。遍历整个链表我们至少需要一个指针作为迭代器。这里 odd 指针和 even 指针不仅仅是尾指针，也可以扮演原链表迭代器的角色。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head||!head->next)return head;
        
        ListNode *oddhead, *odd;
        ListNode *evenhead, *even;
        int i = 0;
        oddhead = new ListNode(0);
        odd = oddhead;
        evenhead = new ListNode(0);
        even = evenhead;
        
        ListNode *curr = head;
        while(curr)
        {
            i++;            
            if(i%2==1)
            {
                odd->next =curr ; 
                odd = curr;
            }else
            {
                even->next =curr ; 
                even = curr;                
            }
            curr = curr->next;
        }
        //connect odd list and even list
        //make sure head node is right and the tail node is null
        odd->next = evenhead->next;
        head = oddhead->next;
        even->next = nullptr;
        
        delete oddhead;
        delete evenhead;
        
        return head;
    }
};
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
48
49
50

复杂度分析

时间复杂度： O(n) 。总共有 n 个节点，我们每个遍历一次。

空间复杂度： O(1) 。我们只需要 4 个指针。

回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2 输出: false
示例 2:

输入: 1->2->2->1 输出: true

方法一：

将值复制到数组中后用双指针法

算法：

我们可以分为两个步骤：

1. 复制链表值到数组列表中。
2. 使用双指针法判断是否为回文。

复杂度分析

时间复杂度：O(n)，其中 n指的是链表的元素个数。
第一步： 遍历链表并将值复制到数组中，O(n)。
第二步：双指针判断是否为回文，执行了 O(n/2)次的判断，即 O(n)。
总的时间复杂度：O(n)+O(n) = O(n)。
空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。

方法二：递归
为了想出使用空间复杂度为 O(1)的解决方案，你可能想过使用递归来解决，但是这仍然是 O(n)的空间复杂度。让我们来看看为什么不是 O(1)的空间复杂度。

递归为我们提供了一种优雅的方式来方向遍历节点。

function print_values_in_reverse(ListNode head)
    if head is NOT null
        print_values_in_reverse(head.next)
        print head.val
1
2
3
4

如果使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文。

算法：
currNode指针是快节点，由于递归的特性再从后往前进行比较。slow 是递归函数外的指针。若 currNode->val != slow ->val 则返回 false。反之，slow 向前移动并返回 true。

之所以起作用的原因是递归处理节点的顺序是相反的（记住上面打印的算法）。由于递归，从本质上，我们同时在正向和逆向迭代。

class Solution {
public:
    ListNode *slow;
    bool isPalindrome(ListNode* head) {
        slow = head;
        return checkcurrsive(head);
    }    
    bool checkcurrsive(ListNode* currNode)
    {
        if(currNode)
        {
        //Recursion
        if(!checkcurrsive(currNode->next))return false;    
        if(slow->val!=currNode->val)
        {
           return false; 
        }
        slow = slow->next;
        return true; 
        }
        return true;
    }

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

复杂度分析

时间复杂度：O(n)，其中 n 指的是链表的大小。
空间复杂度：O(n)，其中 n 指的是链表的大小。我们要理解计算机如何运行递归函数，在一个函数中调用一个函数时，计算机需要在进入被调用函数之前跟踪它在当前函数中的位置（以及任何局部变量的值），通过运行时存放在堆栈中来实现（堆栈帧）。在堆栈中存放好了数据后就可以进入被调用的函数。在完成被调用函数之后，他会弹出堆栈顶部元素，以恢复在进行函数调用之前所在的函数。在进行回文检查之前，递归函数将在堆栈中创建 n 个堆栈帧，计算机会逐个弹出进行处理。所以在使用递归时要考虑堆栈的使用情况。
这种方法不仅使用了 O(n)的空间，且比第一种方法更差，因为在许多语言中，堆栈帧很大（如 Python），并且最大的运行时堆栈深度为 1000（可以增加但是有可能导致底层解释程序内存出错）。为每个节点创建堆栈帧极大的限制了算法能够处理的最大链表大小。

方法三：

避免使用 O(n) 额外空间的方法就是改变输入。
我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，因为使用该函数的人不希望链表结构被更改。

算法：

我们可以分为以下几个步骤：

1. 找到前半部分链表的尾节点。
2. 反转后半部分链表。
3. 判断是否为回文。
4. 恢复链表。
5. 返回结果。

执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。

或者可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针到链表的中间。通过慢指针将链表分为两部分。

若链表有奇数个节点，则中间的节点应该看作是前半部分。

步骤二可以使用在反向链表问题中找到解决方法来反转链表的后半部分。

步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。

步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。

算法：

我们可以分为以下几个步骤：

1. 找到前半部分链表的尾节点。
2. 反转后半部分链表。
3. 判断是否为回文。
4. 恢复链表。
5. 返回结果。

执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。
或者使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针到链表的中间。通过慢指针将链表分为两部分。

若链表有奇数个节点，则中间的节点应该看作是前半部分。

步骤二可以使用在反向链表问题中找到解决方法来反转链表的后半部分。

步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。

步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。

class Solution {
public:

    bool isPalindrome(ListNode* head) {
        if(head == nullptr||head->next==nullptr)return true;
        ListNode *slow, *fast;
        slow = fast = head;

        //Find the end of the first half
        //reverse second half list
        while(fast->next!=nullptr&&fast->next->next!=nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *endofFirstHalf = slow;
        ListNode *startofSecondHalf= reverseList(endofFirstHalf->next);
        
        //check if the fist half list equals the second one
        ListNode *p1 = startofSecondHalf;
        ListNode *p2 = head;
        bool result = true;
        while(p1!=nullptr&&result)
        {
            if(p1->val!=p2->val)
            {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }     
        //restore second half list and return result
        slow->next = reverseList(startofSecondHalf);
        return result;
        
    }    
    
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr)return head;

        ListNode *p = reverseList(head->next);
        //nk+1->next = nk   
        // tail node: n1->next = nullptr
        head->next->next = head;
        head->next = nullptr;
        return p;
    }

};
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
48
49

复杂度分析

时间复杂度：O(n)，其中 n 指的是链表的大小。
空间复杂度：O(1)，我们是一个接着一个的改变指针，我们在堆栈上的堆栈帧不超过 O(1)。

该方法的缺点是，在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执执行过程中链表暂时断开。

小结：链表

让我们简要回顾一下单链表和双链表的表现。

它们在许多操作中是相似的。

1. 它们都无法在常量时间内随机访问数据。
2. 它们都能够在 O(1) 时间内在给定结点之后或列表开头添加一个新结点。
3. 它们都能够在 O(1)时间内删除第一个结点。

但是删除给定结点(包括最后一个结点)时略有不同。

• 在单链表中，它无法获取给定结点的前一个结点，因此在删除给定结点之前我们必须花费 O(N) 时间来找出前一结点。
• 在双链表中，这会更容易，因为我们可以使用“prev”引用字段获取前一个结点。因此我们可以在 O(1) 时间内删除给定结点。

对照
这里我们提供链表和其他数据结构（包括数组，队列和栈）之间时间复杂度的比较：

经过这次比较，我们不难得出结论：

如果你需要经常添加或删除结点，链表可能是一个不错的选择。
如果你需要经常按索引访问元素，数组可能是比链表更好的选择。

附加题

1. 合并两个有序链表

方法一：递归
思路

对于升序链表合并，我们可以自上而下地将问题分解为l1或l2链表中最小的一个值加上合并链表，因此可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

l1[0] + Merge( l1[1], l2 )
l2[0] + Merge( l2[1], l1 )

也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

算法

我们直接将以上递归过程建模，同时需要考虑边界情况。

如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==nullptr)return l2;
        if(l2==nullptr)return l1;
        if(l1->val<l2->val)
        {
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }else
        {
            l2->next = mergeTwoLists(l2->next,l1);
            return l2;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析

时间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。

空间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。

方法二：迭代
思路

我们可以简单粗暴地用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2
哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。

算法

首先，我们设定一个哨兵节点 newList，这可以在最后让我们比较容易地返回合并后的链表。 我们维护一个 curr 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 curr 节点的后面同时将 l1 指针往后移一位。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 curr向后移一位。

在循环终止的时候， l1 和 l2 至多有一个是非空的。 由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //dummyNode used for egde judge
        ListNode *newList = new ListNode(-1);
        ListNode *curr = newList;
        while(l1!=nullptr&&l2!=nullptr)
        {
            if(l1->val<l2->val)
            {
                curr->next = l1;
                l1 = l1->next;
            }else
            {
                curr->next = l2;
                l2 = l2->next;                
            }
            curr =  curr->next ;
        }
        curr->next = l1==nullptr?l2:l1;
        return newList->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析

时间复杂度：O(n+m) ，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。

空间复杂度：O(1) 。我们只需要常数的空间存放若干变量。

2. 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

方法：初等数学+迭代或递归
思路

我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。

算法

就像你在纸上计算两个数字的和那样，我们首先从最低有效位也就是列表 l1 和 l2 的表头开始相加。由于每位数字都应当处于 0…9 的范围内，我们计算两个数字的和时可能会出现 “溢出”。例如，5 + 7 = 125+7=12。在这种情况下，我们会将当前位的数值设置为 2，并将进位 carry=1 带入下一次迭代。进位 carry 必定是 0 或 1，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9 + 9 + 1 = 19。

使用哑结点能避免边界问题，同时在分解子问题得到递归公式时，根据l1 和 l2节点是否为空的情况分类讨论，得到递归子公式

l1->next = addTwoList(l1->next, l2->next, carry);

PS：如果将链表直接转化为整数加减运算会出现int类型位数不足而数据溢出的情况。

代码如下：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = addTwoList(l1,l2,0);
        return dummy->next;
    }
    ListNode *addTwoList(ListNode* l1, ListNode* l2, int Carry)
    {
        int carry =0;
        if(l1!=nullptr&&l2!=nullptr)
        {
            carry = (l1->val+l2->val+Carry-10)>=0?1:0;
            l1->next = addTwoList(l1->next,l2->next,carry);
            l1->val = (l1->val+l2->val+Carry)%10;
            return l1;
        }
        if(l1==nullptr&&l2!=nullptr)
        {
            carry = (l2->val+Carry-10)>=0?1:0;
            l2->next = addTwoList(nullptr,l2->next,carry);
            l2->val = (l2->val+Carry)%10;
            return l2;
        }
        if(l2==nullptr&&l1!=nullptr)
        {
            carry = (l1->val+Carry-10)>=0?1:0;            
            l1->next = addTwoList(l1->next,nullptr,carry);
            l1->val = (l1->val+Carry)%10;        
            return l1;
        }
        if(Carry!=0)
        {
            return new ListNode(Carry);
        }else
        return nullptr;
    }
};
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

复杂度分析

时间复杂度：O(max(m, n))，假设 m 和 n 分别表示 l1 和 l2 的长度，上面的算法最多重复 max(m, n) 次。

空间复杂度：O(max(m, n))， 新列表的长度最多为max(m,n)+1。

3. 扁平化多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：输入的多级列表如下图所示：
1—2—NULL
|
3—NULL

提示：
节点数目不超过 1000
1 <= Node.val <= 10^5

方法一：递归的深度优先搜素
我们可能会疑问什么情况下会使用这样的数据结构。其中一个场景就是 git 分支的简化版本。通过扁平化多级列表，可以认为将所有 git 的分支合并在一起。

通过将列表旋转90°，我们就能发现这种数据结构的本质——二叉树。

算法：
现在我们要做的就是模拟在二叉树进行深度优先搜索。

我们知道实现深度优先搜索通常有两种方式：递归和迭代。我们先从递归开始。

递归的深度优先搜索算法如下：

1. 首先，我们定义递归函数 flatten_dfs(prev, curr)，它接收两个指针作为函数参数并返回扁平化列表中的尾部指针。curr指针指向我们要扁平化的子列表，prev 指针指向 curr 指向元素的前一个元素。在函数 flatten_dfs(prev,curr)，我们首先在 prev 和 curr 节点之间建立双向连接。 然后在函数中调用 flatten_dfs(curr,curr.child) 对左子树（curr.child 即子列表）进行操作，它将返回扁平化子列表的尾部元素 tail，
2. 再调用 flatten_dfs(tail, curr.next) 对右子树进行操作。
3. 为了得到正确的结果，我们还需要注意两个重要的细节： （1）在调用 flatten_dfs(curr, curr.child) 之前我们应该复制 curr.next 指针，因为 curr.next 可能在递归函数中改变。 （2）在扁平化 curr.child 指针所指向的列表以后，我们应该删除 child 指针，因为我们最终不再需要该指针。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution {
public:
    Node* flatten(Node* head) {
        if(head==nullptr)return head;
        Node *dummy = new Node(-1,nullptr,head,nullptr);
        flattenDPS(dummy,head);
        
        //detach dummy node
        dummy->next->prev = nullptr;
        return dummy->next;
    }
    
    //precursion
    //connect prev node and curr node in DPS order
    Node* flattenDPS(Node *prev,Node *curr)
    {
        if(curr==nullptr) return prev;
        prev->next = curr;
        curr->prev = prev;
        
        //warnning!!! the curr->next node will be tempered in precursion
        Node *tempnext = curr->next;
        //left node first
        Node *tail = flattenDPS(curr,curr->child);
        //warnning!!! the child node need to be delete    
        curr->child = nullptr;
        //then right node     
        return flattenDPS(tail,tempnext);
        
    }
};
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

复杂度分析

时间复杂度：O(N)。N 指的是列表的节点数，深度优先搜索遍历每个节点一次。
空间复杂度：O(N)，N 指的是列表的节点数，二叉树很可能不是个平衡的二叉树，若节点仅通过 child 指针相互链接，则在递归调用的过程中堆栈的深度会达到 N。

方法二：迭代的深度优先搜索

我们还可以使用迭代的方式完成深度优先搜索。

关键是使用 stack 数据结构，元素遵循后进先出的原则。
stack 与递归不同，遵循先右再左规律帮我们维持一个迭代序列，它用于摸拟深度优先遍历DPS的行为，这样我们就可以不使用递归来获得相同的结果。

算法：

1. 首先我们创建 stack，然后将头节点压栈。利用 prev 变量帮助我们记录在每个迭代过程的前继节点。
   然后我们进入循环迭代 stack 中的元素，直到栈为空。
2. 在每一次迭代过程中，首先在 stack 弹出一个节点（叫做 curr）。再建立 prev 和 curr 之间的双向链接，再顺序处理 curr.next 和 curr.child 指针所指向的节点（），严格按照此顺序执行。
   如果 curr.next 存在（即存在右子树），那么我们将 curr.next 压栈后进行下一次迭代。
   如果 curr.child 存在（即存在左子树），那么将 curr.child 压栈，与 curr.next 不同的是，我们需要删除 curr.child 指针，因为在最终的结果不再需要使用它。

class Solution {
public:
    Node* flatten(Node* head) {
        if(head==nullptr)return head;
        stack<Node*> stk;
        stk.push(head);
        
        Node *prev = nullptr;
        Node *curr ;
        
        while(!stk.empty())
        {
            curr= stk.top();
            stk.pop();
            if(curr->next!=nullptr)
                stk.push(curr->next);
            if(curr->child!=nullptr)
            {
                stk.push(curr->child);  
                //warnning!!! delete child node 
                curr->child = nullptr;
            }
            //warnning!!! make head->prev node is null
            if(prev!=nullptr)
                prev->next = curr;
            curr->prev = prev;
            prev = curr;
        }
        return head;
    }
};
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

复杂度分析
时间复杂度：O(N)。
空间复杂度：O(N)。

4. 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的 深拷贝。 详情见（深拷贝）

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

方法 1：递归

想法

递归算法的第一想法是将链表想象成一张图。链表中每个节点都有 2个指针（图中的边）。因为随机指针给图结构添加了随机性，所以我们可能会访问相同的节点多次，这样就形成了环。

此方法中，我们只需要遍历整个图并拷贝它。拷贝的意思是每当遇到一个新的未访问过的节点，你都需要创造一个新的节点。遍历按照深度优先DPS进行。我们需要在回溯的过程中记录已经访问过的节点，否则因为随机指针的存在我们可能会产生死循环。

其中，我们使用字典/哈希表这一键值对数据结构来存储已访问的节点。

算法

1. 从 头 指针开始遍历整个图。我们将链表看做一张图。下图对应的是上面的有向链表的例子，Head 是图的出发节点。
2. 当我们遍历到某个点时，如果我们已经有了当前节点的一个拷贝，我们不需要重复进行拷贝。
3. 如果我们还没拷贝过当前节点，我们创造一个新的节点，并把该节点放到已访问字典中，即：unordered_map[current_node] = clone_node.
4. 我们针对两种情况进行回溯调用：一个顺着 random 指针调用，另一个沿着 next 指针调用。

复杂度分析
时间复杂度：O(N) ，其中 N 是链表中节点的数目。
空间复杂度：O(N) 。如果我们仔细分析，我们需要维护一个回溯的栈，同时也需要记录已经被深拷贝过的节点，也就是维护一个已访问字典。渐进时间复杂度为 O(N) 。

方法 2：迭代

思想

迭代算法不需要将链表视为一个图。当我们在迭代链表时，我们只需要为 random 指针和 next
指针指向的未访问过节点创造新的节点并赋值即可。

算法

1. 从 head 节点开始遍历链表。从头按照node->next的顺序遍历链表一遍，如果当前节点未被访问则创造节点副本加入字典中。
2. 对于节点的random指针，如果其随机节点不存在则拷贝一个节点并赋值给拷贝节点的random指针；如果存在则直接赋值。
3. 对于节点的next指针，如果其下一节点不存在则拷贝一个节点并赋值给拷贝节点的next指针；如果存在则直接赋值。
4. 我们重复步骤 2 和步骤 3 ，直到我们到达链表的结尾。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    unordered_map<Node*,Node*> map;
    
    Node* copyRandomList(Node* head) {
        if(head==nullptr)return nullptr;
        
        Node *curr =  head;
        Node *copy = nullptr;

        while(curr!=nullptr)
        {
            if(map[curr]==nullptr)copy = getCloneNode(curr);
            copy->next = getCloneNode(curr->next);
            copy->random = getCloneNode(curr->random);
            
            curr = curr->next;
            copy = copy->next;
        }
        return map[head];
    }
    Node* getCloneNode(Node *node)
    {
        if(node ==nullptr)return nullptr;
        if(map[node]==nullptr)
        {
                Node *copy = new Node(node->val);
                map[node] = copy; 
                return map[node];
        }else
        {
            return map[node];
        }
    }
};
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
48
49
50
51

复杂度分析
时间复杂度：O(N) 。因为我们需要将原链表逐一遍历。
空间复杂度：O(N) 。 我们需要维护一个字典，保存旧的节点和新的节点的对应。因此总共需要 N 个节点，需要 O(N) 的空间复杂度。

方法三：空间的迭代

想法

与上面提到的维护一个旧节点和新节点对应的字典不同，我们通过扭曲原来的链表，并将每个拷贝节点都放在原来对应节点的旁边。这种旧节点和新节点交错的方法让我们可以在不需要额外空间的情况下解决这个问题。让我们看看这个算法如何工作

算法

1. 遍历原来的链表并拷贝每一个节点，将拷贝节点放在原来节点的旁边，创造出一个旧节点和新节点交错的链表。
2. 迭代这个新旧节点交错的链表，并用旧节点的 random 指针去更新对应新节点的 random 指针。比方说， B 的 random 指针指向 A ，意味着 B’ 的 random 指针指向 A’ 。
3. 现在 random 指针已经被赋值给正确的节点， next 指针也需要被正确赋值，以便将新的节点正确链接同时将旧节点重新正确链接。

复杂度分析
尽管时间复杂度没有变化，但由于并没有使用任何额外的空间，所以空间复杂度为常数级。
时间复杂度：O(N)
空间复杂度：O(1)

5. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步:
5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:
输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步:
2->0->1->NULL

方法 1：结构转换

思想

链表中的点已经相连，一次旋转操作意味着：先将链表闭合成环找到相应的位置断开这个环，确定新的链表头和链表尾

那么，新的链表头尾在哪里？

1. 我们这里假设 k < n
   在位置 n-k 处，其中 n 是链表中点的个数，新的链表尾就在头的前面，位于位置 n-k-1。

2. 如果 k >= n 怎么处理？
   k 可以被写成 k = (k / n) * n + k % n 两者和的形式，其中前面的部分不影响最终的结果，因此只需要考虑 k%n 的部分，这个值一定比 n 小。

则新的链表尾为n - k%n -1。

算法

1. 找到旧的尾部并将其与链表头相连 old_tail.next = head，整个链表闭合成环，同时计数得出链表的长度 n。
2. 找到新的尾部，第(n - k % n - 1) 个节点 ，新的链表头是第 (n - k % n) 个节点。
3. 断开环 new_tail.next =None，并返回新的链表头 new_head。

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==nullptr)return head;
        ListNode *oldtail, *newtail;
        oldtail = newtail = head;
        int n;
        for(n=1;oldtail->next!=nullptr;n++)
        {
            oldtail = oldtail->next;
        }
        oldtail->next = head;

        for(int i =0;i<n - k % n - 1;i++)
        {
            newtail = newtail->next;
        }

        head = newtail->next;
        newtail->next = nullptr;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析
时间复杂度：O(N)，其中 N 是链表中的元素个数
空间复杂度：O(1)，因为只需要常数的空间

哈希表

哈希表是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表：哈希集合和哈希映射。

• 哈希集合是集合数据结构的实现之一，用于存储非重复值。
• 哈希映射是映射 数据结构的实现之一，用于存储(key, value)键值对。

在标准模板库的帮助下，哈希表是易于使用的。大多数常见语言（如Java，C ++ 和 Python）都支持哈希集合和哈希映射。

哈希表的原理
哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说，

当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索。

在设计哈希表时，你应该注意两个基本因素。

• 哈希函数: 是哈希表中最重要的组件，该哈希表用于将键映射到特定的桶。目的是分配一个地址存储值。理想情况下，每个值都应该有一个对应唯一的散列值。
• 冲突解决: 哈希函数的本质就是从 A 映射到 B。但是多个 A 值可能映射到相同的 B, 这就是碰撞。因此，我们需要有对应的策略来解决碰撞。总的来说，有以下几种策略解决冲突：
  • 单独链接法：对于相同的散列值，我们将它们放到一个桶中，每个桶是相互独立的。
  • 开放地址法：每当有碰撞，则根据我们探查的策略找到一个空的槽为止。
  • 双散列法：使用两个哈希函数计算散列值，选择碰撞更少的地址。

设计哈希集合

方法一：单独链表法

哈希函数的共同特点是使用模运算符。hash = value mod base。其中，base 将决定 HashSet 中的桶数。

从理论上讲，桶越多（因此空间会越大）越不太可能发生碰撞。base 的选择是空间和碰撞之间的权衡。

此外，使用质数作为 base 是一个明智的选择。例如 769，可以减少潜在的碰撞。

对于桶的设计，我们有几种选择

1. 使用数组来存储桶的所有值。然而数组的一个缺点是需要 O(N) 的时间复杂度进行插入和删除，而不是 O(1)。因为任何的更新操作，我们首先是需要扫描整个桶为了避免重复。

2. 选择链表来存储桶的所有值是更好的选择，插入和删除具有常数的时间复杂度。

算法：

1. 我们可以使用vector可变数组容器存储桶，同时初始化哑结点方便处理边界问题。
2. 使用结构体Node构建链表，实现hash表中的桶。

class MyHashSet {
struct Node
{
    int val;
    Node *next;
    Node():val(0),next(nullptr){}
    Node(int val): val(val),next(nullptr){}
};   
    
public:
    /** Initialize your data structure here. */
    vector<Node*> array;
    const int len = 769;
    MyHashSet() {
        //creat dummy head
        array = vector(len,new Node(-1));
    }
    
    void add(int key) {
        //hash function
        int addr = key%len;
        Node *temp = array[addr];
        while(temp->next!=nullptr)
        {
            if(temp->val == key)return;
           temp = temp->next;
        }
        Node *node2add = new Node(key);
        temp->next = node2add;
        return;
    }
    
    void remove(int key) {
        //hash function
        int addr = key%len;
        Node *temp = array[addr];
        if(temp->next==nullptr)return;
        
        while(temp!=nullptr&&temp->next!=nullptr)
        {
            if(temp->next->val==key)
            {
                Node *node2delete = temp->next;      
                temp->next = node2delete->next;
                delete node2delete;
            }else
            temp = temp->next;
        }

        return;
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        //hash function
        int addr = key%len;
        Node *temp = array[addr];
        if(temp->next==nullptr)return false;
        while(temp->next!=nullptr)
        {
            if(temp->next->val==key)
            {
                return true;
            }
            else
            {
                temp = temp->next;
            }
        }

        return false;
    }
};
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

复杂度分析

时间复杂度：O(N/K)。其中 N 指的是所有可能值数量，K 指的是预定义的桶数，也就是 769。假设值是平均分布的，因此可以考虑桶的平均大小是N/K。对于每个操作，在最坏的情况下，我们需要扫描整个桶，因此时间复杂度是O(N/K)。
空间复杂度：O(K+M)，其中 K 指的是预定义的桶数，M 指的是已经插入到 HashSet 中值的数量。

分界线

方法二：使用二叉搜索树作为桶

在上述的方法中，有一个缺点，我们需要扫描整个桶才能验证一个值是否已经在桶中（即查找操作）。

我们可以将桶作为一个排序列表，可以使用二分搜索使查找操作的时间复杂度是 O(logN)，优于 上面方法中的O(N)。但是，另一方面，如果使用排序列表等连续空间的数组来实现，则会产生线性时间复杂度的更新操作，因此需要其他的方式。

那么，有数据结构具有O(logN) 时间复杂度的查找，删除，插入操作吗？
当然有，就是二叉搜索树。二叉搜索树的特性使得我们能够优化时间复杂度。
二叉搜索树的具体操作可查看C++数据结构——二叉树

class MyHashSet {
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int val): val(val),left(nullptr),right(nullptr){}
};   
    
public:
    /** Initialize your data structure here. */
    vector<TreeNode*> array;
    const int len = 769;
    MyHashSet() {
        //creat dummy head
        array = vector(len,new TreeNode(-1));
    }
    
    void add(int key) {
        if(contains(key))return;
        //hash function
        int addr = key%len;
        TreeNode *temp = array[addr];
        //temp is a dummy node & same for below
        //temp-right is the head of tree
        if(temp->val==-1)
        {
            temp->right = insertIntoBST(temp->right,key);
        }
        else insertIntoBST(temp->right,key);
        return;
    }
    
    void remove(int key) {
        //hash function
        int addr = key%len;
        TreeNode *temp = array[addr];
        if(temp->right==nullptr)return;      
        deleteNode(temp->right,key);

        return;
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        //hash function
        int addr = key%len;
        TreeNode *temp = array[addr];
        if(temp->right==nullptr)return false;
        if(searchBST(temp->right,key))
        {
            return true;
        }

        return false;
    }
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root==nullptr)return nullptr;
        if(root->val==val)return root;
        return root->val>val?searchBST(root->left,val):searchBST(root->right,val);
    }
    
    //insert into the Bucket BST Tree
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr)
        {
            return new TreeNode(val);
        }
        //insert to left tree
        if(root->val>=val)
        {
            root->left = insertIntoBST(root->left,val);
        }
        //insert to right tree
        if(root->val<val)
        {
            root->right = insertIntoBST(root->right,val);
        }
        //final return value
        return root;
    }
    TreeNode* Successor(TreeNode *root)
    {
        root = root->right;
        while(root->left!=nullptr)
            root = root->left;
        return root;
    }
    //find the precessor node
    TreeNode* Predecessor(TreeNode *root)
    {
        root = root->left;
        while (root->right != nullptr)
            root = root->right;
        return root;
    }
    
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr)return nullptr;
        //search node to delete
        if(root->val>key)root->left = deleteNode(root->left,key);
        if(root->val<key)root->right = deleteNode(root->right,key);
        
        if(root->val==key)
        {
            //situation1: a leaf
            if(root->left==nullptr&&root->right==nullptr)
            {
                root = nullptr;
            } 
            //situation2: has right child
            else if(root->right!=nullptr)
            {
                int succ = Successor(root)->val;
                root->val = succ;
                root->right = deleteNode(root->right,succ);
            }
             //situation3: has left child          
            else
            {
                int pred = Predecessor(root)->val;
                root->val = pred;
                root->left = deleteNode(root->left,pred);                
            }
        }
            
        return root;
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

复杂度分析

• 时间复杂度O(K/N)。其中 N 指的是所有可能值数量，K指的是预定义的桶数，也就是 769。 假设值是平均分布的，因此可以考虑桶的平均大小是K/N。当我们遍历二叉搜索树时，使用二分查找，最后每个操作的时间复杂度是 O(log K/N )。
• 空间复杂度：O(K+M)，其中 K 指的是预定义的桶数，M 指的是已经插入到HashSet 中值的数量。

设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射

具体地说，你的设计应该包含以下的功能

• put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个。
• get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
• remove(key)：如果映射中存在这个键，删除这个数值对。

示例：

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // 返回 1
hashMap.get(3); // 返回 -1 (未找到)
hashMap.put(2, 1); // 更新已有的值
hashMap.get(2); // 返回 1
hashMap.remove(2); // 删除键为2的数据
hashMap.get(2); // 返回 -1 (未找到)

注意：

所有的值都在 [0, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希库。

算法分析

• 定义桶类使用链表存储pair<key, value>元素，添加添加删除和查找接口
• 定义桶数组和数组大小，初始化数组大小为一个大的质数，并创建该长度的数组用于存储桶
• 定义哈希函数使用模运算计算桶序号
• 调用桶序号对应的桶的接口实现添加删除和查找

class Bucket{
public:
    void Put(int key, int value)
    {
        for(auto iter = BucketElements.begin();iter!=BucketElements.end();++iter)
        {
            if(iter->first==key)
            {
                iter->second = value;
                return;
            }
        }
        BucketElements.push_front(make_pair(key, value));
    }
    void Remove(int key)
    {
        for(auto iter = BucketElements.begin();iter!=BucketElements.end();++iter)
        {
            if(iter->first==key)
            {
                BucketElements.erase(iter);
                return;
            }
        }
    }
    int Get(int key)
    {
        for(auto iter = BucketElements.begin();iter!=BucketElements.end();++iter)
        {
            if(iter->first==key)
            {
                return iter->second;
            }
        }
        return -1;
    }
private:
    list<pair<int,int>> BucketElements;
};

class MyHashMap {
public:

    /** Initialize your data structure here. */
    MyHashMap() {
        BucketArray = vector(len, Bucket());
    }
    int Hash(int key)
    {
        const int temp  =key%len;
        return temp;
        }
    /** value will always be non-negative. */
    void put(int key, int value) {
        const int index = Hash(key);
        BucketArray[index].Put(key,value);
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        const int index = Hash(key);
        return BucketArray[index].Get(key);
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        const int index = Hash(key);
        BucketArray[index].Remove(key);
    }
private:
    vector<Bucket> BucketArray;
    const int len = 2069;
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

复杂度分析
时间复杂度：O(n/m)，n表示元素数量，m表示桶数量
空间复杂度：O(m+k)，k表示当前元素数量

实际应用—哈希集合

1. 数组查重

给定一个整数数组，判断是否存在重复元素。

如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

方法一：哈希表
通过使用unordered_set 这一哈希表容器简单地实现查重功能

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hashset;
        for(auto iter = nums.begin();iter!=nums.end();++iter)
        {
            if(hashset.count(*iter)>0)return true;
            hashset.insert(*iter);
        }
        /*another iteration type
        for (Type num: nums) {
        	if (hashset.count(num) > 0)
            	return true;
            hashset.insert(num);
        }
        another iteration type*/
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度分析
时间复杂度：O(n)，n表示元素数量
空间复杂度：O(n)，n表示当前元素数量

2. 寻找只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

如果没有时间复杂度和空间复杂度的限制，这道题有很多种解法，可能的解法有如下几种。

• 使用集合存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。
• 使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字
• 使用集合存储数组中出现的所有数字，并计算数。组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。

上述三种解法都需要额外使用 O(n) 的空间，其中 n 是数组长度。如果要求使用线性时间复杂度和常数空间复杂度，上述三种解法显然都不满足要求。那么，如何才能做到线性时间复杂度和常数空间复杂度呢？

方法一: 哈希表（错误方法）
此方法结合了解法1和解法2。在第一次遍历数组时使用哈希表存储数字，其中，第一次出现的数据存入哈希表；但第二次出现的数字将会从哈希表中移除，剩下来的则是只出现一次的数据。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> hashset;

        for (int num: nums) {
        	if (hashset.count(num) > 0)
            {
            	hashset.erase(num);
                continue;
            }
            hashset.insert(num);
        }
        if(!hashset.empty())
        return *hashset.begin();
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析
时间复杂度：O(n)，n表示数组长度，需要遍历一次。
空间复杂度：O(n)，n表示当前数组大小。

方法二：位运算（正确方法）

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e: nums) ret ^= e;
        return ret;
    }
};
1
2
3
4
5
6
7
8

复杂度分析
时间复杂度：O(n)，n表示数组长度，需要遍历一次。
空间复杂度：O(1)。

3. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1],
nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5],
nums2 = [9,4,9,8,4]
输出：[9,4]

说明：

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

思路
这道题目中，根据主题将主要使用一种哈希数据结构，unordered_set，这个数据结构可以解决很多类似的问题。

注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序。这道题用暴力的解法时间复杂度是O(n^2)，这种解法面试官一定不会满意，那我们看看使用哈希法进一步优化。

那么可以发现，貌似用数组做哈希表可以解决这道题目，把nums1的元素，映射到哈希数组的下表上，然后在遍历nums2的时候，判断是否出现过就可以了，但实际上并不适合使用。原因主要有两个：

1. 需要注意的是，使用数组来做哈希的题目，都限制了数值的大小，例如只有小写字母，或者数值大小在[0- 10000] 之内等等。而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。
   例如说：如果我的输入样例是这样的， 难道要定义一个2亿大小的数组来做哈希表么， 不同的语言对数组定义的大小都是有限制的，即使有的语言可以定义这么大的数组，那也是对内存空间造成了非常大的浪费。
2. 使用数组存储，当我们遍历第一个数组nums1，如果出现连续重复两次数字时，我们需要查重防止重复添加，则最坏情况下时间复杂度同样为O(n2^2)

此时我们就要使用另一种结构体了，set ，关于set，C++ 给我们提供了如下三种可用的数据结构

• std::set
• std::multiset
• std::unordered_set

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，时间复杂度为O(1), 我们并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> hashset = unordered_set(nums1.begin(),nums1.end());
        unordered_set<int> result;
        for(int num: nums2)
        {
            //check whether num in nums2 is in nums1
            if(hashset.count(num)>0)
                result.insert(num);
        }
        return vector<int>(result.begin(),result.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度分析
时间复杂度：O(n2)，n2表示数组2的长度，需要遍历一次。
空间复杂度：O(n1+n2)。n1,n2为数组1,2的长度。

4. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环
但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02= 1

方法一：用 HashSet 检测循环
我们可以先举几个例子。我们从 7 开始。则下一个数字是 49（因为 7^2=49
=49），然后下一个数字是 97。我们可以不断重复该的过程，直到我们得到 1。因为我们得到了 1，我们知道 7 是一个快乐数，函数应该返回 true。

再举一个例子，让我们从 116 开始。通过反复通过平方和计算下一个数字，我们最终得到 58，再继续计算之后，我们又回到 58。由于我们回到了一个已经计算过的数字，可以知道有一个循环，因此不可能达到 1。所以对于 116，函数应该返回 false。

根据我们的探索，我们猜测会有以下三种可能。

1. 最终会得到 1。
2. 最终会进入循环。
3. 值会越来越大，最后接近无穷大。

第三个情况比较难以检测和处理。我们怎么知道它会继续变大，而不是最终得到 1 呢？我们可以仔细想一想，每一位数的最大数字的下一位数是多少。

对于 3 位数的数字，它不可能大于 243。这意味着它要么被困在 243 以下的循环内，要么跌到 1。4 位或 4 位以上的数字在每一步都会丢失一位，直到降到 3 位为止。所以我们知道，最坏的情况下，算法可能会在 243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去，所以我们排除第三种选择。

即使在代码中你不需要处理第三种情况，你仍然需要理解为什么它永远不会发生，这样你就可以证明为什么你不处理它。

算法：

1. 给一个数字 n，它的下一个数字是什么？
   按照一系列的数字来判断我们是否进入了一个循环。
   第 1 部分我们按照题目的要求做数位分离，求平方和。

2. 第 2 部分可以使用 HashSet 完成。每次生成链中的下一个数字时，我们都会检查它是否已经在 HashSet 中。

• 如果它不在 HashSet 中，我们应该添加它
• 如果它在 HashSet 中，这意味着我们处于一个循环中，因此应该返回 false。

我们使用 HashSet 而不是向量、列表或数组的原因是因为我们反复检查其中是否存在某数字。检查数字是否在哈希集中需要 O(1)的时间，而对于其他数据结构，则需要 O(n)的时间。选择正确的数据结构是解决这些问题的关键部分。

class Solution {
public:
    int HappyNum(int n)
    {
        int result = 0;
        int temp  =n;
        while(temp>0)
        {
            const int d = temp%10;
            result+=d*d;
            temp = temp/10;
        }
        return result;
    }
    bool isHappy(int n) {
        unordered_set<int> hashset;
        int temp = n;
        while(true)
        {
            temp = HappyNum(temp);
            if(temp==1)return true;
            if(hashset.count(temp)>0)return false;
            hashset.insert(temp);
        }
        return false;
    }
};
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

复杂度分析

确定这个问题的时间复杂度对于一个 “简单” 级别的问题来说是一个挑战。如果您对这些问题还不熟悉，可以尝试只计算 getNext(n) 函数的时间复杂度。

方法二：快慢指针法
通过反复调用 getNext(n) 得到的链是一个隐式的链表，问题就变成了如何通过检测链表包含环。隐式意味着我们没有实际的链表节点和指针，但数据仍然形成链表结构。起始数字是链表的头 “节点”，链中的所有其他数字都是节点。next 指针是通过调用 getNext(n) 函数获得。

意识到我们实际有个链表，那么这个问题就可以转换为检测一个链表是否有环。因此我们在这里可以使用弗洛伊德循环查找算法*(即快慢指针)。这个算法是两个奔跑选手，一个跑的快，一个跑得慢。在龟兔赛跑的寓言中，跑的快的称为 “乌龟”，跑得快的称为 “兔子”。不管乌龟和兔子在循环中从哪里开始，它们最终都会相遇。这是因为兔子每走一步就向乌龟靠近一个节点（在它们的移动方向上）。

方法三：数学(究极解法)

前两种方法是你在面试中应该想到的。第三种方法不是你在面试中会写的，而是针对对数学好奇的人，因为它很有趣。

下一个值可能比自己大的最大数字是什么？根据我们之前的分析，我们知道它必须低于 243。因此，我们知道任何循环都必须包含小于 243 的数字，用这么小的数字，编写一个能找到所有周期的强力程序并不困难。

如果这样做，您会发现只有一个循环：4→16→37→58→89→145→42→20→4。所有其他数字都在进入这个循环的链上，或者在进入 11 的链上。

因此，我们可以硬编码一个包含这些数字的散列集，如果我们达到其中一个数字，那么我们就知道在循环中。

复杂度分析

时间复杂度：O(logn)。和上面一样。
空间复杂度：O(1)，我们没有保留我们所遇到的数字的历史记录。硬编码哈希集的大小是固定的。

实际应用—哈希映射

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15],
target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

C++

方法一.暴力解法
暴力遍历数组两遍得到结果。
复杂度分析
算法时间复杂度O（n²）
空间复杂度O（1）

方法二. 双指针法
首先将数组从小到大排序好O（nlogn），再利用双指针法首尾递进遍历一遍O（n）得到结果。同时，为了保存下标信息另开了一个数组存储。
复杂度分析
时间复杂度O（nlogn）+O（n）=O（nlogn）
空间复杂度O（n）

方法三. 哈希表法
为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

通过以空间换取速度的方式，我们可以将查找时间从 O(n) 降低到 O(1)。哈希表正是为此目的而构建的，它支持以近似恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)。

算法：
一个简单的实现使用了两次迭代。
在第一次迭代中，我们将每个元素的值和它的索引添加到表中。
在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中。

注意，该目标元素不能是 nums[i] 本身！

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int,int> Hashmap;
        for(int i =0;i<nums.size();++i)
        {
            Hashmap.insert(make_pair(nums[i],i));
        }
        for(int i =0;i<nums.size();++i)
        {
            int leftnum = target-nums[i];
            if(Hashmap.count(leftnum)>0&&Hashmap[leftnum]!=i)
            {
                result.push_back(i);
                result.push_back(Hashmap[leftnum]);
                return result;
            }

        }
        return result;
    }
};
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> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int,int> Hashmap;
        for(int i =0;i<nums.size();++i)
        {
            int leftnum = target-nums[i];
            if(Hashmap.count(leftnum)>0)
            {
                result.push_back(i);
                result.push_back(Hashmap[leftnum]);
                return result;
            }
            Hashmap.insert(make_pair(nums[i],i));
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度分析：

时间复杂度：O(n)，
我们把包含有 n个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。

空间复杂度：O(n)，
所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。

2. 同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

输入: s = “egg”,
t = “add”
输出:true
示例 2:

输入: s = “foo”,
t = “bar”
输出: false
示例 3:

输入: s = “paper”,
t = “title”
输出: true

说明: 你可以假设 s 和 t 具有相同的长度。

解法一：双向遍历
题目描述中已经很详细了，两个字符串同构的含义就是字符串 s 可以唯一的映射到 t ，同时 t 也可以唯一的映射到 s 。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char,char> HashMap;
        unordered_map<char,char> ReverseHashMap;        
        for(int i =0;i<s.size();++i)
        {
            if(HashMap.count(s[i])>0&&HashMap[s[i]]!=t[i])
                return false;
            if(ReverseHashMap.count(t[i])&&ReverseHashMap[t[i]]!=s[i])
                return false;
            HashMap.insert(make_pair(s[i],t[i]));
            ReverseHashMap.insert(make_pair(t[i],s[i]));
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析：

时间复杂度：O(n)，
我们把包含有 n个元素的两列表各遍历一次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。

空间复杂度：O(2n)，
所需的额外空间取决于哈希表中存储的元素数量，每个表中存储了 n 个元素。

优化：方法二：第三方抽象层

解法一中，我们判断 s 和 t 是否一一对应，通过对两个方向分别考虑来解决的。

这里的话，我们找一个第三方来解决，即，按照字母出现的顺序，把两个字符串都映射到另一个集合中。

举个现实生活中的例子，一个人说中文，一个人说法语，怎么判断他们说的是一个意思呢？把中文翻译成英语，把法语也翻译成英语，然后看最后的英语是否相同即可。

将第一个出现的字母映射成 1，第二个出现的字母映射成 2

对于 egg e -> 1 g -> 2
也就是将 egg 的 e 换成 1, g 换成 2,
就变成了 122

对于 add a -> 1 d -> 2
也就是将 add 的 a 换成 1, d 换成 2,
就变成了 122

egg -> 122, add -> 122
都变成了 122，所以两个字符串异构。

代码的话，只需要将两个字符串分别翻译成第三种类型即可。我们可以定义一个变量 count = 1，映射给出现的字母，然后进行自增。

class Solution {
public:
vector<int> isIsomorphicHelper(string s) {
    unordered_map<char,int> hashmap;
    vector<int> result;
    int n = s.length();
    int count = 1; // mapping string to int
    for (int i = 0; i < n; i++) {
        char c = s[i];
        //当前字母第一次出现,赋值
        if (hashmap.count(c)<=0) {
            hashmap.insert(make_pair(c,count));
            count++;
        }
        result.push_back(hashmap[c]);
    }
    return result;
}
bool isIsomorphic(string s, string t) {
    return isIsomorphicHelper(s)==isIsomorphicHelper(t);
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析：

时间复杂度：O(n)，
我们把包含有 n个元素的两个列表各遍历一次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。

空间复杂度：O(n)，
所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。同时，由于简化了代码，减少了判断条件，不仅增强了可读性还降低了多余操作所需时间。

3. 两个列表的最小索引总和

假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。

示例 1:

输入:
[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
[ “Piatti”,“The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]
输出:
[“Shogun”] 解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:

输入: [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
[“KFC”,“Shogun”, “Burger King”]
输出: [“Shogun”]
解释:
他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

提示:

两个列表的长度范围都在 [1, 1000]内。
两个列表中的字符串的长度将在[1，30]的范围内。
下标从0开始，到列表的长度减1。
两个列表都没有重复的元素。

方法 1：使用哈希表 [Accepted]

在这种方法中，我们枚举 list1中的每一个字符串，遍历整个 list2一遍，对每一对字符串都进行比较,得到相同字符串时，选取出序列和最小的组合。

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        vector<string> result;
        unordered_map<string,int> hashmap;
        int count = 0;
        int miniIndex = 2000;
        for(int i =0;i<list1.size();i++)
        {
            if(hashmap.count(list1[i])<=0)
            {
                hashmap.insert(make_pair(list1[i],count));
                count++;
            }
        }
        count = 0;
        for(int i =0;i<list2.size();i++)
        {
            if(hashmap.count(list2[i])<=0)
            {
                hashmap.insert(make_pair(list2[i],count));
            }else if((hashmap[list2[i]]+count)<miniIndex)
            {
                miniIndex = hashmap[list2[i]]+count;
                result.clear();
                result.push_back(list2[i]);
            }else if((hashmap[list2[i]]+count)==miniIndex)
            {
                result.push_back(list2[i]);               
            }
                count++;            
        }
        return result;
    }
};
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

复杂度分析：

时间复杂度：O(l1* l2* x)，
l1,l2为字符串L1L2的长度，x为字符串的平均长度。各遍历一遍，所以时间复杂度为O(l1* l2* x)。

空间复杂度：O(l1* l2* x)，
所需的额外空间取决于哈希表中存储的元素数量。

方法 2： 不使用哈希表 [Accepted]

算法

另一种也可以遍历不同 sum (下标和)，并判断是否有字符串分别出现在 list1和 list2 中且下标和为 sum。

4. 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

s = “leetcode” 返回 0

s = “loveleetcode” 返回 2

提示：你可以假定该字符串只包含小写字母。

方法一： 按键聚合
利用哈希映射（键存储对象，值存储信息）

这道题最优的解法就是线性复杂度了，为了保证每个元素是唯一的，至少得把每个字符都遍历一遍。

算法的思路就是遍历一遍字符串，然后把字符串中每个字符出现的次数保存在一个散列表中。这个过程的时间复杂度为 O(N)，其中 N 为字符串的长度。

接下来需要再遍历一次字符串，这一次利用散列表来检查遍历的每个字符是不是唯一的。如果当前字符唯一，直接返回当前下标就可以了。第二次遍历的时间复杂度也是 O(N)。

class Solution {
public:
    int firstUniqChar(string s) {
    unordered_map<char, int> hashmap;
    for (int i =0 ;i<s.length();i++) {
        if (hashmap.count(s[i]) > 0) {
            hashmap[s[i]] +=1 ;
        }else
        {
            hashmap[s[i]] = 1;
        }       
    }
    for (int i =0 ;i<s.length();i++)
    {
        if(hashmap[s[i]] == 1)    return i;
    }
    return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度分析

时间复杂度： O(N)
只遍历了两遍字符串，同时散列表中查找操作是常数时间复杂度的。

空间复杂度： O(N)
用到了散列表来存储字符串中每个元素出现的次数。

5. 两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集.

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2] 示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。

进阶：

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
• 如果 nums2的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

方法一：哈希表
由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。

算法:
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

• 如果 nums1 的大小比 nums2 小很多，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。可以有效降低空间复杂度.

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    //choose the smaller space of hashmap
    if (nums1.size() > nums2.size()) {return intersect(nums2, nums1);}    

    unordered_map<int, int> hashmap;
    vector<int> result;
    for (int i =0 ;i<nums1.size();i++) {
        if (hashmap.count(nums1[i]) > 0) {
            hashmap[nums1[i]] +=1 ;
        }else
        {
            hashmap[nums1[i]] = 1;
        }       
    }
    //save the space that is unvalued
    for (int num : nums2) {
        if (hashmap.count(num)) {
            result.push_back(num);
            --hashmap[num];
            if (hashmap[num] == 0) {
                hashmap.erase(num);
            }
        }
    }
    return result;
    
    }
};
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

复杂度分析

时间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度。需要遍历两个数组并对哈希表进行操作，哈希表操作的时间复杂度是 O(1)，因此总时间复杂度与两个数组的长度和呈线性关系。

空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个数组的长度。对较短的数组进行哈希表的操作，哈希表的大小不会超过较短的数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。

方法二：排序

• 如果两个数组是有序的，则可以便捷地计算两个数组的交集。

算法:
首先对两个数组进行排序，然后使用两个指针遍历两个数组。

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等; 将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int length1 = nums1.size(), length2 = nums2.size();
        vector<int> intersection;
        int index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection.push_back(nums1[index1]);
                index1++;
                index2++;
            }
        }
        return intersection;
    }
};


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

复杂度分析

时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度。对两个数组进行排序的时间复杂度是 O(mlogm+nlogn)，遍历两个数组的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。

空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。不过在 C++ 中，我们可以直接创建一个 vector，不需要把答案临时存放在一个额外的数组中，所以这种实现的空间复杂度为 O(1)。

结语
如果 nums 2的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中。那么就无法高效地对 nums 2进行排序，因此推荐使用方法一而不是方法二。在方法一中,nums2 只关系到查询操作，因此每次读取 nums 2中的一部分数据，并进行处理即可。

6. 存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:

输入: nums = [1,2,3,1], k = 3 输出: true
示例 2:

输入: nums = [1,0,1,1], k = 1 输出: true
示例 3:

输入: nums = [1,2,3,1,2,3], k = 2 输出: false

方法三 （哈希表） 【通过】
思路1:哈希表维持滑动窗口

用散列表来维护这个k大小的滑动窗口。

算法

在之前的方法中，我们知道了对数时间复杂度的 搜索 操作是不够的。在这个方法里面，我们需要一个支持在常量时间内完成 搜索，删除，插入 操作的数据结构，那就是散列表。这个算法的实现跟方法二几乎是一样的。

遍历数组，对于每个元素做以下操作：
在散列表中搜索当前元素，如果找到了就返回 true。
在散列表中插入当前元素。
如果当前散列表的大小超过了 k， 删除散列表中最旧的元素。
返回 false。

public boolean containsNearbyDuplicate(int[] nums, int k) {
    unordered_set<int> set;
    for (int i = 0; i < nums.length; ++i) {
        if (set.count(nums[i])>0) return true;
        set.insert(nums[i]);
        if (set.size() > k) {
            set.eraze(nums[i - k]);
        }
    }
    return false;
}

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

思路2:哈希映射
使用哈希映射存储键值信息—数组值和值的下标<int, vector>

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) { 

    unordered_map<int, vector<int>> hashmap;

    for (int i =0 ;i<nums.size();i++) {
        if (hashmap.count(nums[i]) > 0) {
            for(int num:hashmap[nums[i]])
            {
                if(i-num<=k)return true;
            }
        }
        hashmap[nums[i]].push_back(i);            
    }
    return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析

时间复杂度：O(n^2)
我们会做 n次 遍历，每次操作都耗费其存储下标数量级的时间。最坏情况下则为O(n^2).

空间复杂度：O(n)
开辟的额外空间取决于散列表中存储的元素的个数，也就是滑动窗口的大小 O(min(n,k))。

7. 有效的数独

题目描述

思路
一个简单的解决方案是遍历该 9 x 9 数独 三 次，以确保：

行中没有重复的数字。
列中没有重复的数字。
3 x 3 子数独内没有重复的数字。

尽管，所有这一切都可以在一次迭代中完成，但需要消耗更大的内存。P.S : 对比测试（8.1M VS 40M）

法一：三次遍历方案

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<char> horizentol;
        unordered_set<char> vertical;
        unordered_set<char> sboard;
        for(int i =0;i<9;++i)
        {
            for(int j =0;j<9;++j)
            {
                if(board[i][j]=='.')continue;
                if(horizentol.count(board[i][j])<=0)//not exist
                {
                    horizentol.insert(board[i][j]);
                }else return false;
            }
            horizentol.clear();
        }
        for(int i =0;i<9;++i)
        {
            for(int j =0;j<9;++j)
            {
                if(board[j][i]=='.')continue;
                if(vertical.count(board[j][i])<=0)//not exist
                {
                    vertical.insert(board[j][i]);
                }else return false;
            }
            vertical.clear();
        }
        for(int s=1;s<=3;++s)
        {
            for(int m=1;m<=3;++m)
            {
                for(int i =3*s-3;i<3*s;++i)
                {
                    for(int j =3*m-3;j<3*m;++j)
                    {
                        if(board[i][j]=='.')continue;
                        if(sboard.count(board[i][j])>0)//not exist
                        {
                            return false;
                        }
                        sboard.insert(board[i][j]);
                    }
                }
                sboard.clear();
            }
 
        }   
        return true;     
    }
};
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
48
49
50
51
52
53

法二： 一次遍历方案
力扣官方解答

复杂度分析

时间复杂度：O(1)，因为我们只对 81 个单元格进行了一次迭代。
空间复杂度：O(1)。

8. 寻找重复的子树

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1：

    1
   / \
  2   3
 /   / \
4   2   4
   /
  4 
  下面是两个重复的子树：

  2
 /
4 
和

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

因此，你需要以列表的形式返回上述重复子树的根结点。

方法一：二叉树递归遍历【通过】
思路

任意顺序遍历序列化二叉树。

例如上面这棵树序列化结果为 1,2,#,#,3,4,#,#,5,#,#。每棵不同子树的序列化结果都是唯一的。

算法

使用深度优先搜索，其中递归函数返回当前子树的序列化结果。把每个节点开始的子树序列化结果和出现次数保存在 map 中，然后判断是否存在重复的子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<string,int> hashmap;
    vector<TreeNode*> subtrees;

    string Tree2Serials(TreeNode* root)
    {
        if(root==nullptr)return "#";
        //using string to store the serials num is more convinent       
        string serials = to_string(root->val)+","+Tree2Serials(root->left)+","+Tree2Serials(root->right);       
        if(hashmap[serials]==1)
        {
            subtrees.push_back(root);
        }
        hashmap[serials]+=1;        
        return serials;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        if(root==nullptr)return subtrees;
        Tree2Serials(root);
        return subtrees;
    }
};
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

复杂度分析

时间复杂度：O(N^2)，其中 N 是二叉树上节点的数量。遍历所有节点，在每个节点处序列化需要时间 O(N)。

空间复杂度：O(N^2)，hashmap的大小。

P.S：还需考虑String 的 hashCode 计算，字符串越长所需的计算时间越长（考虑所有数都是 Integer.MAX_VALUE 时字符串的长度）。相对解法一，解法二在 key 长度都比解法一要小得多，所以字符串拼接、hashCode 计算都会快得多。

方法二：唯一标识符【通过】【更优】
思路

假设每棵子树都有一个唯一标识符：只有当两个子树的 id 相同时，认为这两个子树是相同的。

一个节点 node 的左孩子 id 为 x，右孩子 id 为 y，那么该节点的 id 为 (node.val, x, y)。

算法

如果三元组 (node.val, x, y) 第一次出现，则创建一个这样的三元组记录该子树。如果已经出现过，则直接使用该子树对应的 id。

class Solution {
    int t;
    Map<String, Integer> trees;
    Map<Integer, Integer> count;
    List<TreeNode> ans;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        t = 1;
        trees = new HashMap();
        count = new HashMap();
        ans = new ArrayList();
        lookup(root);
        return ans;
    }

    public int lookup(TreeNode node) {
        if (node == null) return 0;
        String serial = node.val + "," + lookup(node.left) + "," + lookup(node.right);
        //computing tree's uid increasingly
        int uid = trees.computeIfAbsent(serial, x-> t++);
        count.put(uid, count.getOrDefault(uid, 0) + 1);
        if (count.get(uid) == 2)
            ans.add(node);
        return uid;
    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/find-duplicate-subtrees/solution/xun-zhao-zhong-fu-de-zi-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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

复杂度分析

时间复杂度：O(N)，其中 N 二叉树上节点的数量，每个节点都需要访问一次。

空间复杂度：O(N），每棵子树的存储空间都为 O(1)。

设计键 - 总结

这里有一些为你准备的关于如何设计键的建议。

1. 当字符串 / 数组中每个元素的顺序不重要时，可以使用排序后的字符串 / 数组作为键。
   

2. 如果只关心每个值的偏移量，通常是第一个值的偏移量，则可以使用偏移量作为键。
   

3. 在树中，你有时可能会希望直接使用 TreeNode 作为键。 但在大多数情况下，采用子树的序列化表述可能是一个更好的主意。
   

4. 在矩阵中，你可能希望使用行索引或列索引作为键。

5. 在数独中，可以将行索引和列索引组合来标识此元素属于哪个块。
   

6. 有时，在矩阵中，您可能希望将值聚合在同一对角线中。

散列表应用题

1. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1

方法一：滑动窗口

力扣官方解答

思路和算法

我们先用一个例子来想一想如何在较优的时间复杂度内通过本题。

我们不妨以示例一中的字符串 abcabcbb 为例，找出 从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。

我们可以发现如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！因此可以用滑动窗口来解决此类问题。

• 我们使用两个指针表示字符串中的某个子串（的左右边界）。其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为结束位置。

• 在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。

• 在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；

• 在枚举结束后，我们找到的最长的子串的长度即为答案。

判断重复字符

在上面的流程中，我们还需要使用一种数据结构来判断 是否有重复的字符，常用的数据结构为哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> hashset;
        int n = s.size();
        int count=0;
        int rp = -1;// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        for(int i =0;i<n;++i)
        {
            if(i!=0)// 左指针向右移动一格，移除一个字符
            {
                hashset.erase(s[i-1]);
            }
            // 不断地移动右指针,碰到重复元素时停止进入下一循环。
            while(rp+1<n&&hashset.count(s[rp+1])<=0)
            {
                hashset.insert(s[rp+1]);
                rp++;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            count = max(count,rp-i+1);
        }
        return count;
    }
};
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

复杂度分析

时间复杂度：O(N)，其中 NN 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。

2. 四数相加 II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

例如:

输入: A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

输出: 2

解释: 两个元组如下:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

解题步骤：

1. 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
3. 定义int变量count，用来统计a+b+c+d = 0出现的次数。
4. 在遍历大C和大D数组，找到如果 0-(c+d)在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
5. 最后返回统计值 count 就可以了

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int,int> hashmap;
        int count =0;
        for(int a:A)
        {
            for(int b:B)
            {
                hashmap[a+b]++;
            }
        }
        //C+D
        for(int c : C)
        {
            for(int d:D)
            {
                if(hashmap.count(-(c+d))>0)
                {
                    count+=hashmap[-(c+d)];
                }
            }
        }
        return count;
}
};
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

复杂度分析

时间复杂度：O(N^2)，其中 N是数组的长度。4个数字ABCD分为A+B，C+D两组各遍历两次。

空间复杂度：O(4N)，最坏情况为数组内成员的总量。