数据结构算法题目（一）：数组、链表、栈队列与二叉树
以下所有内容编排按照Carl开源的算法攻略进行，感谢博主悉心的内容挑选和顺序编排。编程语言为C++；
数组篇
1. 原地删除某个元素值
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。不需要考虑数组中超出新长度后面的元素。
快慢指针： 1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0; //慢指针
for(int fast=0; fast<nums.size(); fast++){
if(nums[fast]==val)
continue;
nums[slow] = nums[fast]; //不等才拷贝快指针
slow++;
}
nums.resize(slow);
return slow;
}
};
2. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方组成的新数组，要求也按非递减顺序排序。
要求：需要O(n)时间复杂度，即不能使用排序算法，最优的排序算法时间复杂度至少是Ologn。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> result(nums.size(),0);
int left =0;
int right=nums.size()-1;
for(int i=nums.size()-1;i>=0;i--){
int lm=nums[left]*nums[left];
int rm=nums[right]*nums[right];
if(lm>rm){
result[i]=lm;
left++;
}
else{
result[i]=rm;
right--;
}
}
return result;
}
};
3. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
example: 输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
1.暴力超时版
这道题的暴力方法逻辑也比较复杂，使用C语言写了几版还是不对，转到C++，逻辑没有太大问题就是十分暴力超时了：使用了双层循环进行累加计数，使用了单层循环+条件判断挑选返回值，非常任性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24int minSubArrayLen(int target, vector<int>& nums) {
vector<int> temp; //存储每个数据的和
vector<int> length;//存储数据长度
temp.resize(nums.size()); //初始化数据为0
length.resize(nums.size()); //初始化数据为0
for(int i=0;i<nums.size();i++){
for(int j=i;j<nums.size();j++){
if(temp[i]<target){ //两层循环，从当前位置元素开始累加后面的元素，直至和大于target
temp[i]+=nums[j]; //记录和，小于继续累加
length[i]++; //记录已经累加的长度
}
}
}
int min=nums.size();
for(int i=0;i<nums.size();i++){
if(length[i]==nums.size()&&temp[i]<target){
return 0; //长度以及最大而且和小于target，返回0
}
if(temp[i]>=target&&length[i]<min){
min=length[i]; //和大于target，寻找最小长度
}
}
return min; //返回最小长度
}
2. 滑动窗口版
窗口末尾通过循环移动，从头开始遍历求和，当和大于target时，计算长度，记录最小长度，窗口起点移动，减去第一个元素，进入循环直到又大于target，最后完成全部后返回最小的计算长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23int minSubArrayLen(int target, vector<int>& nums) {
int begin=0;
int length=0;
int min=nums.size()+1; //最小值初始化为nums.size()+1，正常长度肯定是达不到的，最后还是这个就返回0
int sum=0;
//vector<int>result_record; //如果需要记录子数组
for(int i=0;i<nums.size();i++){ //窗口末尾循环移动
sum+=nums[i]; //随着末尾移动相加,直到sum>=target
while(sum>=target){
length=i-begin+1;//计算长度
min=length<min?length:min; //记录最小长度
sum-=nums[begin++]; //滑动窗口核心：实际上就是sum-=nums[begin];begin++;
//result_record.assign(nums.begin()+begin,nums.begin()+i+1); //如果需要子数组
}
}
min=min==nums.size()+1?0:min; //最小长度不是设定的最大值返回min，是则返回0
//验证子数组
//for(auto i:result_record)
// cout<<i<<" ";
return min;
}
4.螺旋矩阵
给你一个正整数 n ，生成一个包含 1 到
意思是将一个1到n方的数组绕成一个正方形矩阵，逐行输出元素，看官网更加清晰： 螺旋矩阵
没有什么特别的地方，主要是二维矩阵的遍历，需要控制每次循环开始的地方都是没有被遍历过的，另外一个重要的点是，这里我们通过标记result[i][j]==0来判断每次拐弯的边界，就不会在一个圈内死循环了，另一种方法是手动更新边界，内存和效率都有所提高，但代码可读性略复杂，所以就使用了这种写法：
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
36class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int i=0;
int j=0;
vector<vector<int>>result(n,vector<int>(n,0));
int fill=1;
while(fill<=n*n){
//从左到右
while(j<n&&result[i][j]==0){
result[i][j++]=fill++;
}
j--; //最后的++需要减回来，后面的也是同理；
i++; //i++，提取移动一格，确保进入循环前踩着那格没有被填充
//从上到下
while(i<n&&result[i][j]==0){
result[i++][j]=fill++;
}
i--;
j--;
//从右往左
while(j>=0&&result[i][j]==0){
result[i][j--]=fill++;
}
j++;
i--;
//从下往上
while(i>=0&&result[i][j]==0){
result[i--][j]=fill++;
}
i++;
j++;
}
return result;
}
};
镜像问题：给出矩阵求其螺旋顺序
螺旋矩阵Ⅱ：给出矩阵，求其顺时针的螺旋顺序。
和上面是一致的，为了标记拐弯位置，使用了新的二维数组walked来标记遍历过的位置，防止重复循环。
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
38class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int row=matrix.size();//行数
int col=matrix[0].size();//列数
vector<int>result;
int i=0;
int j=0;
vector<vector<bool>>walked(row,vector<bool>(col,false));
while(result.size()<col*row){
while(j<col&&walked[i][j]==false){
walked[i][j]=true;
result.push_back(matrix[i][j++]);
}
j--;
i++;
while(i<row&&walked[i][j]==false){
walked[i][j]=true;
result.push_back(matrix[i++][j]);
}
i--;
j--;
while(j>=0&&walked[i][j]==false){
walked[i][j]=true;
result.push_back(matrix[i][j--]);
}
j++;
i--;
while(i>=0&&walked[i][j]==false){
walked[i][j]=true;
result.push_back(matrix[i--][j]);
}
i++;
j++;
}
return result;
}
};
链表篇
1. 去除链表的所有匹配元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
example： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
解决思路：使用了快慢两个指针分别指向链表的前后一位，当走在前面的指针值和val相等，就把跳过这个fast并且把fast的下一位链接到slow的下一位，释放fast的空间。其次，结合数据结构的习惯中，删除操作使用带头节点的链表比较方便，这样就无需移到最后一位的时候再进行分类讨论，因此创建了new_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/**
* 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* removeElements(ListNode* head, int val) {
ListNode* new_node = new ListNode();
new_node->next = head;
ListNode*slow = new_node;
ListNode*fast = new_node->next;
while(fast!=nullptr){
if(fast->val==val){ //快指针需要删除
slow->next = fast->next; //删除fast
fast->next = nullptr;
delete fast;
fast = slow->next;
}
else{ //不需要删除，正常后移
slow = slow->next;
fast = fast->next;
}
}
return new_node->next;
}
};
2. 设计链表
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
合适选择临时变量temp能够规避不必要的错误排除，例如在删除、插入操作时，将temp起始值置为H，按序号查找时，因为序号从0开始，查找的总是序号前一个的元素，因此能够在其前面进行插入，删除则是temp->next的元素；而查找get函数，不需要找前一个元素，因此temp直接置为H->next，这样返回时就是序号的元素，开始时i==0，与H->next的0下标对应。
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
92class MyLinkedList {
public:
//链表结构
typedef struct ListNode{
int val;
struct ListNode*next;
ListNode():val(0),next(nullptr){}
}*Linklist;
//成员变量：
Linklist H;
MyLinkedList() { //构造函数初始化成员变量
H = new ListNode(); //头结点
}
int get(int index) { //根据index索引结点，index=0是H后第一个数据结点
if(index<0)
return -1;
int i=0;
Linklist temp=H->next; //第一个数据结点，即下标0结点
while(i<index&&temp!=nullptr){
temp=temp->next;
i++;
}
if(temp==nullptr)
return -1;
return temp->val;//temp是下标index
}
void addAtHead(int val) { //头插法
Linklist new_node=new ListNode();
new_node->val=val;
new_node->next=H->next;
H->next=new_node;
}
void addAtTail(int val) { //尾插法
Linklist new_node = new ListNode();
new_node->val=val;
new_node->next=nullptr;
Linklist temp=H;
while(temp->next!=nullptr)
temp=temp->next;
temp->next=new_node; //temp后面为空，说明是末尾
}
void addAtIndex(int index, int val) { //插在索引结点的前面
if(index<0)
return;
int i =0;
Linklist temp=H; //头结点
while(i<index&&temp!=nullptr){
temp=temp->next;
i++;
} //temp为index-1结点
if(temp==nullptr)
return;
Linklist new_node=new ListNode(); //在index-1结点后插入
new_node->val=val;
new_node->next=temp->next;
temp->next=new_node;
}
void deleteAtIndex(int index) { //删除索引结点
if(index<0)
return;
int i=0;
Linklist temp=H;
while(i<index&&temp!=nullptr){
temp=temp->next;
i++;
} //temp为index-1结点
if(temp==nullptr||temp->next==nullptr) //index-1结点或index为空，无需删除
return;
Linklist temp1=temp->next; //删除index结点
temp->next=temp1->next;
delete temp1;
temp1=nullptr;
}
};
/**
* 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);
*/
3. 链表的反转
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
在原链表上进行操作，空间复杂度低。首先一刀两段，将第一个结点和其他结点分开，用temp和temp1记录2和3，头插法将2插入1的前面，temp、temp1后移，循环使用头插法插入即可。
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/**
* 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* reverseList(ListNode* head) {
if(head==nullptr||head->next==nullptr){ //没有结点或者单一结点，无需反转
return head;
}
ListNode *new_head=new ListNode(0,nullptr);
new_head->next=head; //增加头结点
ListNode *temp=head->next; //temp记录2
head->next=nullptr;
ListNode *temp1=temp->next; //temp1记录3
while(temp1!=nullptr){ //至少还有两个元素插入
temp->next=new_head->next; //插入temp元素
new_head->next=temp;
temp=temp1; //下次循环插入temp1元素
temp1=temp1->next;
}
temp->next=new_head->next; //temp1为空，只剩下temp需要插入
new_head->next=temp;
return new_head->next;
}
};
4. 交换相邻链表结点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换），也即每两个元素进行交换，奇数个元素则末尾元素不变。
example: 输入：head = [1,2,3,4] 输出：[2,1,4,3]
假设加入头结点链表为new_node->1->2->3->4，初始时temp指向1，temp1指向3，第一步起点cur指向new_node，首先将cur->next指向2，然后将2的next指向1，最后将1的next指向3，链表成为new_node->2->1->3->4，完成一对交换，然后cur指向1，能完成3、4交换；如果链表再多了一个元素5，则不符合两两交换原则，不会进行交换，最后结果也是new_node->2->1->4->3->5；
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/**
* 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* swapPairs(ListNode* head) {
ListNode* new_node = new ListNode();
new_node->next = head;
//调换结点1、2，需要先找到1、2前的结点，即头结点和1结点
ListNode *slow = new_node;
ListNode* fast = slow->next;
while(fast!=nullptr&&fast->next!=nullptr){ //单独结点无需变顺序
//改变指针指向
slow->next = fast->next;
fast->next = fast->next->next;
slow->next->next = fast;
//处理下两个结点
slow = slow->next->next;
fast = slow->next;
}
return new_node->next;
}
};
5.删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
example: 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
快慢指针方法容易解决，要删除倒数第n个元素，就要先标记倒数n+1个元素，fast、slow指针开始时先指向虚拟头结点，fast未到末尾，就一直移动，并且n--，直到n<1情况下slow开始移动，这样保证了fast指向最后一位元素的时候，slow指向的是倒数n+1个元素，再执行删除操作即可。
1 | /** |
6. 寻找两链表相交的第一个点
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
链表相交，代表地址相同，ListNode *相等。
暴力遍历
首先最简单是极其暴力解法，遍历A，每遍历一个元素指针就和B的所有指针比较，直到找到相等的，时间复杂度显然是二者长度乘积。
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/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *tempA=headA;
ListNode *tempB=headB;
while(tempA!=nullptr){
while(tempA!=tempB&&tempB!=nullptr){
tempB=tempB->next;
}
if(tempA==tempB){
return tempA;
}
if(tempB==nullptr){
tempB=headB;
}
tempA=tempA->next;
}
return nullptr;
}
};
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = 0;
int lenB = 0;
ListNode*tempA = headA;
ListNode*tempB = headB;
//获取二者长度
while(tempA!=nullptr){
tempA = tempA->next;
lenA++;
}
while(tempB!=nullptr){
tempB = tempB->next;
lenB++;
}
tempA = headA;
tempB = headB;
//A比较长，tempA先走去平差
if(lenA>=lenB){
int sub = lenA-lenB;
while(sub--){
tempA = tempA->next;
}
}
//B比较长，tempB先走去平差
else{
int sub = lenB-lenA;
while(sub--){
tempB = tempB->next;
}
}
//一起走，边走边比较
while(tempA!=tempB&&tempA!=nullptr){ //或判断tempB
tempA = tempA->next;
tempB = tempB->next;
}
if(tempA==tempB)
return tempA;
return nullptr;
}
};
7. 环形链表寻找入环点
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
条件：不允许修改链表。
example: 
注意这个入环点指的是第一次出环回溯的点，而不是开始进入环的点。
一般判断链表是否有环并不难，只需要遍历链表，边遍历边标记，要么通过链表存放的数据标记，要么新开辟一个标记域，但是这两种方法都修改了链表结构和内容，不符合规定。当然一种很骚气的方法是改变数据，找到入环结点、出环结点后再遍历一次，修改回去......但是这个明显只是钻了评测系统的空子，并不值得采用。
7.1 环形链表理论
不涉及标记数据的环形链表需要使用几个结论用于解决这样类型的问题：
1. 判断链表是否存在环
fast、slow指针指向表头，slow每次移动1，fast每次移动2，如果二者相遇，则链表存在环。这个不难理解，如果有环就是追及问题，快指针必然追上慢指针。需要注意的是，这里有个更逆天的结论：也即slow、fast相遇时，一定是在slow一次环都没有走完的情况下，这在下面2会说明。
2. 判断入环点位置
从头结点出发一个指针index1，从slow、fast相遇位置出发一个指针index2，每次均移动1个结点，二者相遇的位置就是入环点位置。
推导：环形链表有三个重要点：头结点、入环点、slow、fast相遇的点。记头结点————入环点距离为x，入环点到环内相遇点距离为y，相遇点回到第二次入环点（另外半圆回去）为z。
假设1结论是成立的，也即slow走过的路程是x+y,fast走过的路程是x+y+n(y+z),假设slow已经走过环了，那么slow路程也应该表示成x+y+m(y+z),m、n可以抵消一部分，意味着x+y必然匹配到某个x+y+n(y+z)，所有相遇时一定是slow没有完整经过第一次环的。
且slow、fast路程关系是1：2的关系，所以有：
(x+y)*2=x+y+n(y+z); 整理得：
x=(n-1)(y+z)+z
注意这是路程的概念，如果使用链表位移，因为(y+z)的路程带来是环形，位移是0，因此有 >x=z
也即头结点到入环点距离x就是相遇点到第二次入环点距离z，与fast经过了多少次环(n)、第几次相遇均没有关系。
7.2 实现
1 | /** |
哈希表篇
1. 判断是否异位字符
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
example: 输入: s = "anagram", t = "nagaram" 输出: true
multiset方法，该容器比较暴力，将第一个字符元素存储于树结构中，第二个字符查找并删除（不使用迭代器直接删除元素会导致重复元素被一次删除），最终树为空则说明两个词是异位的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size()!=t.size()){ //长度不等肯定不是异位符
return false;
}
std::multiset<char> s1;
for(int i=0;i<s.size();i++){
s1.insert(s[i]); //一个字符串插入multiset
}
for(int i=0;i<t.size();i++){
std::multiset<char>::iterator pos=s1.find(t[i]);
if(pos!=s1.end()){
s1.erase(pos); //一个字符串用于删除
}
}
if(s1.empty()){
return true; //插和删抵消，为异位符
}
return false;
}
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size()!=t.size())
return false;
vector<int>temp(26);
for(int i=0; i<s.size(); i++){
temp[s[i]-'a']++;
temp[t[i]-'a']--;
}
for(auto i:temp){
if(i!=0)
return false;
}
return true;
}
};
2. 两个数组交集
给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
example: 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的
输出时结果唯一，所以可以考虑set和unordered_set，综合查找性能选后者；
返回值数组可以使用set的迭代器+vector赋值进行，不一定使用vector的插入操作，优雅。
1 | class Solution { |
3.快乐数判别
「快乐数」 定义为： 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1;
如果这个过程 结果为 1，那么这个数就是快乐数。如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
example: 输入：n = 19 输出：true 解释：
- 断定一个数不是快乐数：看平方和是否和前面的平方和重复循环了，使用unordered_set判断是否重复，重复时插入时会失败；
- 判断一个数是快乐数：和为1的时候跳出循环即可。
语法：哈希表unordered_set的插入insert会返回一个pair对象，pair.first是迭代器，指向插入元素的位置，pair.second是bool，返回插入是否成功。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
bool isHappy(int n) {
unordered_set<int>st;
while(1){
int sum = 0;
while(n){ //n不等于0
int off = n%10; //从个位开始取值
n /= 10;
sum += off*off; //sum存入个、十、百等各个位置的平方和
}
if(sum==1) //和为1说明为快乐数，返回true
return true;
pair<unordered_set<int>::iterator,bool> ret=st.insert(sum); //插入哈希表
if(ret.second==false) //插入失败，说明已经重复，不可能是快乐数
return false;
n = sum; //重置下一次计算的n
}
}
};
4. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
example: 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
注意：题目设计是：每个数组只可能返回两个元素是满足条件的。
由于只可能出现两个数满足条件，因此只需要一边查找一边插入即可：遍历数组，在哈希表中查找与当前元素相加恰好为target的元素，如果没有找到，那么就把当前元素写入哈希表，继续遍历后面的元素如果存在与其相加为target的就会从哈希表找到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map<int,int>m1;
for(int i=0;i<nums.size();i++){
int target_other=target-nums[i]; //相减另一个目标值
std::unordered_map<int,int>::iterator pos=m1.find(target_other);//在哈希表中查找
if(pos!=m1.end()){ //找到返回两个下标
return {i,(*pos).second}; //也可pos->second
}
else{
m1.insert(make_pair(nums[i],i)); //没找到，将当前元素加入哈希表
}
}
return {};
}
};
5. 满足四数之和为0的元组个数
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
example:输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
注意题目设计：重复的元素组合是允许的，只需要每次i、j、k、l中值不完全相同即可。只有这种允许重复元素的情况下才可以使用哈希表的方法，否则对哈希表进行去重是比较复杂的，后面的三数之和、四数之和就涉及了这个问题。
该题思路和两数之和是一致的，首先将使用双层循环将num1、num2所有组合的和存储在哈希表中，重复的和使用++递增记录次数（注意这种++方法仅对单值unordered_map、map有效，对multimap是不允许的，因为multimap允许多值不知道哪个值++）；
对num3、num4求和，一边遍历其和，一边从哈希表中查找其负数，查到了说明四数之和必定为0，并且记录它的重复次数，继续遍历，因为后面还可能出现重复的次数。
1 | class Solution { |
6.赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false ,magazine 中的每个字符只能在 ransomNote 中使用一次。
example: 输入：ransomNote = "a", magazine = "b" 输出：false
比题目还有意思是这个标题：绑匪为了防止查字迹，通常从杂志（magazine）剪下字符贴成赎金信（ransomNote），所以要考虑ransomNote 能不能由 magazine 里面的字符构成，且每个magazine字符只能用一次。
思路比较简单：将magazine的字符全部存入哈希表，并记录其出现次数，ransomNote要用时次数--即可，如果出现负数那就说明ransomNote使用了未在magazine出现的字符，判断false即可。
这里一个点是：因为magazine元素会重复，总是首先想到multimap，实际上unordered_map+次数记录也可以处理某些重复元素问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
std::unordered_map<char,int>m1;
for(int i=0;i<magazine.size();i++){
m1[magazine[i]]++;
}
for(int i=0;i<ransomNote.size();i++){
m1[ransomNote[i]]--;
}
for(std::unordered_map<char,int>::iterator pos=m1.begin();pos!=m1.end();pos++){
if((*pos).second<0){
return false;
}
}
return true;
}
};
7. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
example: 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
三数之和是一个有挑战的问题，关键在于两个地方，其一是如何表示三数运算的过程；其二是如何按照题目要求去重；
对于运算表示问题，通常使用双重指针的方法，首先将数组从小到大排序，i指针负责从头开始循环遍历数组，这里的i地位就是三数中的low指针；mid取i+1，high取数组末尾元素，当和分别大于和小于目标值时，分别移动high和mid指针，这种情况下能找到给定i指针的所有满足三数和，当找到等于目标值时，push_back元组。
去重问题：三数之和另一个复杂方面在于去重，这里采取了两个手段：i和前一个i一样时，跳过，因为前一个i对应的mid和high组合找出来了，后一个i只能重复，保留一个即可；其次，当mid和下一个mid相等、high和上一个high相等时，也跳过该值，因为给定了low，mid和high无论谁取相等值，得到的元组必然也是重复的。
单循环+双指针+去重
注意low、mid、high均要去重，其中i、high均和i-1、high-1比较，mid和mid+1比较，其中low移动时保证low是唯一的，但是high、mid移动完了会指向一个重复的元素，因此还需要执行mid++、high--；
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
38class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
if(nums.size()<3){ //没有三数直接返回
return {};
}
sort(nums.begin(),nums.end()); //变成有序
vector<vector<int>>result;
for(int i=0;i<nums.size();i++){
int mid=i+1;
int high=nums.size()-1;
if(i>0&&nums[i]==nums[i-1]){ //当前的i和上一个是一样的，直接跳过这个循环，因为必然找到相同的mid和high
continue;
}
if(nums[i]+nums[high]+nums[high-1]<0){ //当前循环最大三数相加小于0，mid、high无论怎么移动肯定小于该数，也就不用循环了；必须移动i
continue;
}
while(mid<high){ //进入i循环，mid小于high
int sum=nums[i]+nums[mid]+nums[high];
if(sum==0){
result.push_back({nums[i],nums[mid],nums[high]}); //等于0的入组
while(mid<high&&nums[mid]==nums[mid+1]) mid++; //mid和下个元素一样，额外移动一次跳过相等元素
while(mid<high&&nums[high]==nums[high-1]) high--; //同mid
mid++; //否则移动mid和high（注意一起移动不是必须的，只移动一个也会在下次循环移动另一个，效果是等效的）
high--;
}
else if(sum<0){
mid++; //和小于0，mid要变大
}
else { //和大于0，high要变小
high--;
}
}
}
return result;
}
};
时间复杂度：每次i都尝试和low和high配对，low和high复杂度是O(n)，可见加上i维度是n方，
； 时间复杂度：二维数组，最多
暴力超时：回溯+去重
做了回溯算法回头看，发现三数之和是《组合总和II》的子问题，只需要加上“size==3”的限制即可，而且数组没有限定正整数，因此不能sum>0提前剪枝。但是遗憾通过率是308/313。毕竟是递归，时间复杂度比较高，要通过只能使用上面的方法了，好处是对mid、high的处理更简单，不失为一种保底方法。
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
28class Solution {
public:
vector<int> temp;
vector<vector<int>> result;
int sum;
void travel(vector<int>& nums_sort,int start){
int sum = accumulate(temp.begin(),temp.end(),0);
if(temp.size()==3&&sum==0){
result.push_back(temp);
return;
}
else if(temp.size()>=3)
return;
for(int i=start; i<nums_sort.size(); i++){
if(i>start&&nums_sort[i-1]==nums_sort[i]) //排序、去重
continue;
temp.push_back(nums_sort[i]);
travel(nums_sort,i+1);
temp.pop_back();
}
}
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
travel(nums,0);
return result;
}
};
8. 四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
example:输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,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
37class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>>result;
if(nums.size()<4){
return{};
}
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
if(i>0&&nums[i]==nums[i-1])
continue;
for(int j=i+1;j<nums.size();j++){
if(j>i+1&&nums[j]==nums[j-1])
continue;
int mid=j+1;
int high=nums.size()-1;
while(mid<high){
long sum =(long)nums[i]+(long)nums[j]+(long)nums[mid]+(long)nums[high];
if(sum==target){
result.push_back({nums[i],nums[j],nums[mid],nums[high]});
while(mid<high&&nums[mid]==nums[mid+1]) mid++;
while(mid<high&&nums[high]==nums[high-1]) high--;
mid++;
high--;
}
else if(sum<target){
mid++;
}
else{
high--;
}
}
}
}
return result;
}
};
暴力：回溯算法+去重
四数之和同样是《组合问题Ⅱ》的子问题，不同的是size==4以及其有可能出现负数、int越界和，不能使用sum>0提前剪枝或者accumulate算法，但总归是通过测试了，然而时间复杂度是垫底的，仅作参考方法：
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
29class Solution {
public:
vector<int> temp;
vector<vector<int>> result;
long sum = 0;
void travel(vector<int>& nums_sort,int target,int start){
if(temp.size()==4&&sum==target){
result.push_back(temp);
return;
}
else if(temp.size()>=4)
return;
for(int i=start; i<nums_sort.size(); i++){
if(i>start&&nums_sort[i-1]==nums_sort[i]) //排序、去重
continue;
temp.push_back(nums_sort[i]);
sum += nums_sort[i];
travel(nums_sort,target,i+1);
temp.pop_back();
sum -= nums_sort[i];
}
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
travel(nums,target,0);
return result;
}
};
字符串篇
1. 字符串反转
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
example： 输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]
平平无奇循环+二分对换 1
2
3
4
5
6
7
8
9class Solution {
public:
void reverseString(vector<char>& s) {
int n = s.size();
for(int i=0; i<n/2; i++){
swap(s[i],s[n-i-1]);
}
}
};
2. 按规则反转字符串
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
example:输入: s = "abcdefg", k = 2 输出: "bacdfeg"
规则很绕，咋一看是三种情况，实际上只有两种情况，每次只需要判断剩下的字符是k个以上还是k以下，k个以下则反转现在的i到末尾，k个以上则反转k个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
string reverseStr(string s, int k) {
int i,temp;
for(int i=0;i<s.size();i+=2*k){
if(i+k<s.size()){
reverse(s.begin()+i,s.begin()+i+k);
}
else{
reverse(s.begin()+i,s.end());
}
}
return s;
}
};
3. 翻转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。 s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意： 输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
example: 输入：s = "a good example" 输出："example good a"
一般思路
总体思路是将空格全部保留1个，整体字符串反转，在将单词逐个反转回来。
- 首先先处理空格问题；字符串、数组的去除某个val元素较优的做法是通过快慢指针解决，快指针负责循环，如果检测没有val值则赋值给慢指针，慢指针++，最后重要的是需要对vector或者string重新resize（slow），因为慢指针有可能达不到末尾，慢指针之外的元素不应该被纳入新数组。
while循环略过字符串开头的空格，for循环中，如果快指针和前一位都是空格，那么这个空格就跳过（continue），只保留第一个空格；至此，字符串前、中间的空格、后面大于一个的空格就被去除了，最后一步处理字符串后的字符空格，空格的数量只可能是1个或者0个，因此使用一次if判断就能去掉，slow-1是空格，则保留0slow-2，反之slow-1是有效字母，保留0slow-1；
- 颠倒字符，通过空格判断是否到达一个单词截断位置，颠倒并更新新的起点即可。最后颠倒最后的空格到末尾，完成。
1 | class Solution { |
输入流处理简化操作
使用sstream对输入流进行处理，使用栈反转单词，优化了操作：
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
26class Solution {
public:
string reverseWords(string s) {
stack<string>temp; //栈结构反转
stringstream ss;
ss<<s;
string str;
while(getline(ss,str,' ')){ //注意：这步只能跳过一个空格
if(!str.empty()) //其余空格也不存在，才执行插入
temp.push(str);
}
vector<string>result;
while(!temp.empty()){
result.push_back(temp.top()); //result是无空格的翻转字符串
temp.pop();
}
//将vector<string>转化string，并且添加空格间隔
string result1;
for(int i=0; i<result.size()-1; i++){ //字符串
result1 += result[i];
result1.push_back(' '); //添加空格间隔
}
result1 += result[result.size()-1]; //最后一个无需间隔
return result1;
}
};
4. 查找子串
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
example: 输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。
4.1 暴力解法
i遍历原串，temp从i位置开始，与模式串进行匹配，如果原串的temp指针与模式串的j指针一直相等，直到j到模式串末尾，匹配成功，这种方法对每个i都需要进行n-i长度的匹配，可见其时间复杂度是1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int strStr(string haystack, string needle) {
for(int i=0;i<haystack.size();i++){
int j=0;
int temp=i; //temp从i开始尝试匹配
while(j<needle.size()&&haystack[temp]==needle[j]){ //当前匹配则后移，直到j移到末尾
temp++;
j++;
}
if(j==needle.size()) //如果是因为到末尾跳出循环，则说明成功匹配，返回第一个匹配位置，即temp的起始位置i
return i;
}
return -1;
}
};
4.2 KMP算法基本思想
一个人能走得多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。（KMP算法，摘自B站网友）
从暴力解法看出，在长度为n的字符串中查找长度为m的子字符串，需要时间复杂度为O(n*m)，例如在“aabaaf”中查找“aaf”，首先对比“a”和“a”，相等了对比“aa”，“aa”，再对比“aab”和“aaf”，这时候发现字符串不匹配，则新的匹配会从“abaaf”开始匹配“aaf”，这样一来每次对比最长的情况是m次，n个字符都要比较，因此耗时比较多；
有什么有效的手段能够避免这个耗时呢？1977年，Knuth、Morris、Pratt三人联合发表一篇论文，正式提出了一种算法，该算法用于字符串匹配，能够实现O(m+n)的时间复杂度，该算法取三人名字排列，称为KMP算法。
KMP算法的基本思路是使用next数组用于记录模式串（查找的子串）每次需要重新匹配的位置，使用i指针指针遍历原串，j指针遍历模式串，当遇到不匹配时，i指针会从当前位置继续匹配，j指针会跳转到重新匹配的位置匹配，直到原串遍历完成或者模式串匹配完成。
next数组实际上是一个前缀表，记录了字符的最长公共前后缀：所谓前缀，就是字符串不包含最后一位的子串，后缀是字符串不包含最开始一位的子串；例如"aabaa"，前缀就有“aaba”、“aab”、“aa”、“a”，后缀有“abaa”、“baa”、“aa”、“a”，最长公共前后缀就是“aa”，长度为2；同理可以计算"aababaaba"字符串的所有最长公共前缀(从字符串起点到该字符形成的子串的最长公共前缀):
| 模式串下标 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 字符 | a | a | b | a | a |
| 最长公共前后缀 | 0 | 1 | 0 | 1 | 2 |
该最长公共前缀形成的数组，就是前缀表，也是next数组（也有不少实现方法将前缀表整体减一再形成next数组）；该数组的作用是定义了模式串重新匹配的位置；
给定任意字符串，例如从"aababaabaa"需要查找"aabaa"：
1.
开始匹配：原串"aabab"与模式串"aabaa"从原串下标4的b、模式串的最后一个a开始不匹配，模式串a对应前缀表的前一个数是1，因此模式串重新匹配的位置是下标1；
2.
重新匹配：原串下标4的"b"与模式串下标1的"a"不匹配，"a"对应数组的前一位是0，所以下次重新匹配是从模式串的起点开始；
3.
重新匹配，原串下标4的"b"与模式起点都不匹配，原串指针下移（与模式串起点不匹配直接移动i，而不是考虑模式串新的起点），"aabaa"与"aabaa"匹配，匹配完成。
第二个例子，假设从"aababaabaa"查找的是“abaa”,记：
| 模式串下标 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 字符 | a | b | a | a |
| 最长公共前后缀 | 0 | 0 | 1 | 1 |
- 开始匹配：原串"aa"与"ab"不匹配，b对应数组前一位是0，下次仍从头匹配；
- 从模式串头开始匹配，原串"abab"与模式串“abaa”的第四位不匹配，对应next的前一位是1，下次匹配从模式串下标1开始；
- 模式串“baa”与原串“baa”匹配，找到匹配项，完成匹配。
总而言之：两个细节：
1.
每次遇到不匹配的，i指针会停下，等待模式串查表回到重新匹配位置，与不匹配的i指针进行重新匹配；
2.
如果最后回到模式串首，或者开始匹配的模式串就是完整的模式串，那么i指针会移到下一个指针进行匹配；
总而言之，i指针不会向前访问原串已经遍历过的元素。
4.3 KMP算法实现
关键还是理解next数组，手写出next数组是很简单的事情，但是用程序表达是比较困难的，首先模式串的每一位next数组值，只和前面的字符串相关，因此从i==1开始遍历（i==0,next固定为0）生成next数组，i==1数组取决于j==0时，needle[j]是否等于needle[i]，如果相等，j++且next[1]=1，开始计算i==2的，这时就需要比较next[i==2]和next[j==1]，如果相等，i和j会依次叠加下去，next[i] = j随之叠加下去，但是一旦遇到不相等的情况，会参考j前一位的next值（也即重新匹配的下标），注意这个跳转逻辑是while，因此会跳转直至j==0（从头匹配）或者下标匹配，重新计算前缀值。
这个next数组实际上就是匹配模式串的最长公共前缀，如果在haystack串查找，实际上就是寻找needle在haystack是否有长度为needle.size()长度的最长公共前缀，如果有，needle就是haystack的子串，所以使用next数组，实际上就是将i对象换成了haystack，但注意此时i从0开始，否则会错过i==0的匹配结果。
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
35class Solution {
public:
vector<int> getNext(string needle){ //得到next数组
vector<int> next(needle.size(),0);
int j=0;
next[0]=j;
for(int i=1;i<needle.size();i++){
while(j>0&&needle[i]!=needle[j]){ //不匹配跳转至next[j-1]下标继续匹配，或者j==0
j=next[j-1];
}
if(needle[i]==needle[j]){ //匹配累计最长公共前缀
j++;
}
next[i]=j;
}
return next;
}
int strStr(string haystack, string needle) {
vector<int>next=getNext(needle);
int j=0; //j是模式串的匹配位置
for(int i=0;i<haystack.size();i++){ //遍历源串
while(j>0&&haystack[i]!=needle[j]){ //不是匹配位置
j=next[j-1]; //跳到前缀表尝试重新匹配
}
if(haystack[i]==needle[j]){ //匹配，匹配位置移动
j++;
}
if(j==needle.size()){ //匹配位置到达末尾
return i-j+1; //说明匹配成功，i-j+1就是haystack的匹配起始点
}
}
return -1;
}
};
5. 重复的字符串
给定一个非空的字符串s，检查是否可以通过由它的一个子串重复多次构成。
example:输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。
5.1 暴力解法
虽然是暴力解法，但是需要注意的细节也很多。暴力解法的思想是假设重复子串长度为i（i长度取值是1到len/2，因为重复字符至少重复两次，不需要遍历到len），假如字符串长度能够整除子串长度i，那么该子串有可能就是重复子串，使用j遍历查看相隔i的字符是否相等，如果j循环到末尾仍相等，说明这就是重复的子串，返回true；
1 | class Solution { |
5.2 KMP算法
使用前缀表判断重复串组成的字符串是比较简单的，重复子串构成的字符串有这样一个特点：即：字符串总长度-前缀表最后一位的值=重复字符串的长度。重复字符串前缀表的特点是从第二个重复字符串周期开始前缀表值是不递减的（假如重复字符串最长公共前后缀是000，例如"abc"这样的，那么从第二个周期开始就是从1开始递增；如果重复子串最长公共前后缀本身有值，例如"aabaa"是01012，那么从第二个周期开始会有一次重复的现象，确保后续重复是继续递增直到最后一位，总而言之，这个规律对重复字符串是恒成立的），例如"abccabccabcc",前缀表为"000012345678"，因此重复子串长度 = 12-8 =4。
因此只需要建立next数组，计算周期，如果能整除，并且确保前缀表最后一个值不为0(如果为0，(len%times)==0是恒成立的，例如"abac"这种就不能排除)，说明为重复字符串。
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
26class Solution {
public:
vector<int> getNext(string s){
int j=0;
vector<int>next(s.size(),0);
for(int i=1;i<s.size();i++){
while(j>0&&s[i]!=s[j]){
j=next[j-1];
}
if(s[j]==s[i]){
j++;
}
next[i]=j;
}
return next;
}
bool repeatedSubstringPattern(string s) {
vector<int>next=getNext(s);
int len=s.size();
int times=len-next.back();
if((len%times)==0&&next.back()!=0)
return true;
return false;
}
};
栈与队列篇
1. 用两个栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false
两个栈实现队列，只需要写一下如何去除队头元素即可，难度不大；但是这里其实还是考虑一种实现思想：输入栈和输出栈表示队列的思想，当输出栈为空时就从输入栈导入数据，否则就一直在输出栈取数据。这种思路比将栈数据拷贝另一个、取出top、再装回去性能高多了。
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
32class MyQueue {
public:
stack<int>stk_in;
stack<int>stk_out;
MyQueue() {
}
void push(int x) { //输入之间压输入栈
stk_in.push(x);
}
int pop() {
if(stk_out.empty()){ //输出栈为空，从输入栈压入全部数据
while(!stk_in.empty()){
stk_out.push(stk_in.top());
stk_in.pop();
}
}
int result = stk_out.top(); //输出栈不为空，直接取数据，取的顺序自然就是队列顺序
stk_out.pop();
return result;
}
int peek() { //取队首元素
int result = this->pop();
stk_out.push(result); //只取不pop，压回输出栈
return result;
}
bool empty() { //双栈为空
return stk_in.empty()&&stk_out.empty();
}
};
2. 用两个队列实现栈
这个就没有优化方法了，只能一个做备份量和中间空间，另一个负责存储数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class MyStack {
public:
queue<int> que1; //主队列
queue<int> que2; //中间队列，暂存
MyStack() {
}
void push(int x) { //入主队
que1.push(x);
}
int pop() {
int n = que1.size()-1;
while(n--){
que2.push(que1.front()); //压入size-1
que1.pop();
}
int result = que1.front(); //最后一个队尾，也即栈顶
que1.pop();
while(!que2.empty()){ //暂存队重新入主队
que1.push(que2.front());
que2.pop();
}
return result;
}
int top() { //栈顶=队尾
return que1.back();
}
bool empty() { //主队为空
return que1.empty();
}
};
3. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s
，判断字符串是否有效。 有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。
此外，括号的匹配必须按照不参差排列的规则，例如: 1
\{(\{{})}\}
example: 输入：s = "()[](]" 输出：false 输入：s = "({()})()" 输出：true
栈匹配括号：就像一个消消乐游戏，i遍历字符串，遇到左符号就将右符号入栈，遍历到右符号如果当前栈顶是对应的右符号（注意：不参差随意排布的括号一定能保证当前栈顶和右符号是对应的），就弹出，最后如果消消乐结果为空，那么就是完全匹配。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
bool isValid(string s) {
if(s.size()%2==1) return false;//符号是成对的，奇数肯定不对
stack<char> stk;
for(int i=0;i<s.size();i++){
if(s[i]=='{') stk.push('}');
else if(s[i]=='[') stk.push(']');
else if(s[i]=='(') stk.push(')');
else if(!stk.empty()&&stk.top()==s[i]) stk.pop();
else return false;
}
if(stk.empty())
return true;
return false;
}
};
4. 删除字符串相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
消消乐问题，还是栈专业对口，问题是如何把栈的元素返回成string，以下通过vector实现，浪费了性能和内存，实际上可以使用string的pop_back和push_back来模拟栈，总体思路是一致的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
string removeDuplicates(string s) {
vector<int>temp;
stack<char>stk;
for(int i=0; i<s.size(); i++){
if(!stk.empty()&&stk.top()==s[i]){
stk.pop();
}
else
stk.push(s[i]);
}
//统计栈结果
while(!stk.empty()){
temp.push_back(stk.top());
stk.pop();
}
reverse(temp.begin(),temp.end()); //颠倒
return {temp.begin(),temp.end()};
}
};
5. 逆波兰表达式求值
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
example:输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
逆波兰表达式是典型的PC计算器计算原理，其将我们常用的中缀表达式转换成后缀表达的方式，根据后缀表达式，可以按照括号的优先级进行计算，在计算机中，逆波兰的表达式是按照栈的方式进行存储和计算的，其原理是：遍历后缀表达式，如果遇到数字就将数字入栈，如果一旦遇到计算符号（加减乘除都是二元运算符），就弹出两个元素进行运算，将结果重新存入栈，如此类推进行计算。
知道原理后容易写出: 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
27class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int>stk;
for(int i=0; i<tokens.size(); i++){ //遇到的不是符号，数字先入栈
if(tokens[i]!="+"&&tokens[i]!="-"&&tokens[i]!="*"&&tokens[i]!="/"){
stk.push(stoi(tokens[i]));
}
else{ //遇到符号则计算
int temp1 = stk.top();
stk.pop();
int temp2 = stk.top();
stk.pop();
if(tokens[i]=="+")
stk.push(temp2+temp1);
else if(tokens[i]=="-")
stk.push(temp2-temp1);
else if(tokens[i]=="*")
stk.push(temp2*temp1);
else if(tokens[i]=="/")
stk.push(temp2/temp1);
}
}
return stk.top();
}
};
6. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
example:输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]
6.1 暴力超时版
最蠢的方法：将nums每三个放入一个deque中，使用辅助函数findmax找出每次deque的最大值存入结果数组(但是这种方法在大数组中是无法ac的)
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
30class Solution {
public:
int findmax(deque<int> dqe){
int max=dqe.front();
for(int i=0;i<dqe.size();i++){
if(dqe[i]>max)
max=dqe[i];
}
return max;
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int>dqe;
vector<int> result;
int max;
for(int i=0;i<k;i++){
dqe.push_back(nums[i]);
}
int i=k;
while(i<nums.size()){
max=findmax(dqe);
result.push_back(max);
dqe.pop_front();
dqe.push_back(nums[i]);
i++;
}
max=findmax(dqe);
result.push_back(max);
return result;
}
};
6.2 优先队列（推荐）
开始时先计算k个最大值，窗口移动，序号过小的从优先队列排除，不断读入根结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
vector<int>result;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
priority_queue<pair<int,int>>pq; //大顶堆
for(int i=0; i<k; i++){ //初始时k个元素入队
pq.push(make_pair(nums[i],i));
}
result.push_back(pq.top().first);
for(int i=k; i<nums.size(); i++){
while(!pq.empty()&&pq.top().second<=i-k) //second序号过期，小于i-k，滑动窗口已经离开元素
pq.pop(); //弹出
pq.push(make_pair(nums[i],i));
result.push_back(pq.top().first);
}
return result;
}
};
6.3 单调队列版
维护一个单调队列，这个队列的队首始终存储着滑动窗口的最大值：这个队列的插入法则是：
1. 如果队列为空，插入元素；
2.
如果插入元素大于队尾元素，循环从尾部弹出，直到队尾元素为空或者大于要插入的元素；
这个队列需要同时兼顾头部、尾部删除功能，因此不能使用真的队列queue结构，应该使用双端数组deque；
为了体验这个队列与滑动窗口的关系，描述通过滑动窗口寻找数组[7,2,3,1,4]，k=2的最大值数组（易知答案[7,3,3,4]）;
- 队列为空，7入队，2小于7，2正常入队，元素个数为2，第一次入队完成，当前队首为7，第一个结果为7；
- 窗口向后滑动，7出队，插入3，2<3，所以2要尾部弹出，3入队，当前队首为3，第二个结果为3；
- 窗口滑动，2出队（注意出队是取决于数组元素，而不是队列元素，2已经弹出，因此该步不会改变队列结果），1<3，1入队，此时队首仍为3，第三个结果为3；
- 窗口滑动，3出队，1<4，1尾部弹出，4入队，队首为4，结果为4，至此得到结果数组[7,3,3,4]；
具体代码： 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
40class SingleQueue{
public:
deque<int> dqe;
void mypush_back(int Elem){
while(!dqe.empty()&&dqe.back()<Elem){ //插入元素大于队尾，队尾持续出队直到空
dqe.pop_back();
}
dqe.push_back(Elem);
}
void mypop_front(int Elem){
//dqe.front()==Elem是因为插入时有可能某个元素已经从队尾弹出，窗口移动时应该出队的是弹出的元素，因此要判断出队的元素是不是当前元素
if(!dqe.empty()&&dqe.front()==Elem){
dqe.pop_front();
}
}
int myfront(){
return dqe.front();
}
};
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
SingleQueue sque;
vector<int>result;
for(int i=0;i<k;i++){ //装载第一次窗口
sque.mypush_back(nums[i]);
}
result.push_back(sque.myfront()); //返回第一个结果
int i=0;
while(i+k<nums.size()){ //循环滑动，不断从front获取结果
sque.mypop_front(nums[i]);
sque.mypush_back(nums[i+k]);
result.push_back(sque.myfront());
i++;
}
return result;
}
};
7. 前K个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
example:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
7.1 哈希表+自定义数组排序排序
1 | class Solution { |
7.2 哈希表+自定义优先队列排序
优先队列是基于堆结构的一种容器适配器，如果需要将元素从小到大排序，则需要大顶堆；如果需要队列从大到小排列，则需要小顶堆（详情看C++第三篇堆排序）；
C++标准库提供了优先队列容器std::priority_queue: 1
2
3
4
5
6
7
8
9
10
11priority_queue<int> maxHeap ; //默认调用的就是less比较器,实现一个最大堆
priority_que<int,vector<int>,less<int>>maxHeap;
priority_queue<int,vector<int>,greater<int>>minHeap; //最小堆需要指定greater比较器
//如果需要自定义，仿函数类+自定义
priority_queue<int,vector<int>,Mycompare> Heap;
//如果Mycompare return left>right，则认为left是小值，此时的堆为最小堆
//如果是return left<right，则认为right是小指，那么此时的堆为最大堆
//访问优先队列元素，通过访问.top()可以获取其最大堆的队列最大值、最小堆的队列最小值（没有队列的front、back等）
自定义仿函数实现大小顶堆是一件奇怪的事情，return
left>right反而是最小堆，这里简单解释为left>right时为true，实际上就是greater，所以是最小堆；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24struct myCompare{
bool operator()(const pair<int,int>&p1 ,const pair<int,int>&p2){ //大顶堆
return p1.second < p2.second;
}
};
class Solution {
public:
vector<int> result;
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> umap;
for(int i=0; i<nums.size(); i++){ //哈希表随机存储
umap[nums[i]]++;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,myCompare>pq;
for(auto i:umap){
pq.push(i); //哈希表全部入队
}
while(k--){ //输出前k高频
result.push_back(pq.top().first);
pq.pop();
}
return result;
}
};
二叉树篇
1. 前序遍历
递归实现
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/**
* 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:
vector<int> preorderTraversal(TreeNode* root) {
if(root==nullptr)
return{};
stack<TreeNode*> stk;
stk.push(root);
vector<int>result;
TreeNode*temp;
while(!stk.empty()){
temp=stk.top();
result.push_back(temp->val);
stk.pop();
if(temp->right)
stk.push(temp->right);
if(temp->left)
stk.push(temp->left);
}
return result;
}
};
2. 后序遍历的迭代实现
和前序相比，后序的递归只是更换了两条语句顺序，结构简单不再赘述，根据前序遍历的思想，尝试写一下后序遍历的迭代方法：通过对比任意一棵二叉树的前序和后序输出结果，只需要进行两个改变：
1.
左孩子先入栈，右孩子后入栈；此时得到的最终结果就是一个颠倒的后序遍历结果；
2. 颠倒数组，就是后序遍历结果；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33/**
* 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:
vector<int> postorderTraversal(TreeNode* root) {
if(root==nullptr)
return{};
stack<TreeNode*>stk;
stk.push(root);
vector<int>result;
TreeNode* temp;
while(!stk.empty()){
result.push_back(stk.top()->val);
temp=stk.top();
stk.pop();
if(temp->left)
stk.push(temp->left);
if(temp->right)
stk.push(temp->right);
}
reverse(result.begin(),result.end());
return result;
}
};
4. 层序遍历
层序遍历需要使用队列结构，队列存储的结点就是该层要处理的数据，不同的题目设计逻辑略有不同，大体思想也是一样的，在二叉树那篇数据结构里也描述过也不过多赘述，以下记录了相关题目。
基本层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
example: 输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
1 | /** |
底层到上层的层序
。。。。reverse 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : 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:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
if(root==nullptr)
return{};
queue<TreeNode*> que;
vector<vector<int>> result;
vector<int>temp;
que.push(root);
TreeNode*r;
while(!que.empty()){
int size=que.size();
for(int i=0;i<size;i++){
r=que.front();
temp.push_back(r->val);
que.pop();
if(r->left&&r->right){
que.push(r->left);
que.push(r->right);
}
else if(r->left){
que.push(r->left);
}
else if(r->right){
que.push(r->right);
}
}
result.push_back(temp);
temp.clear();
}
reverse(result.begin(),result.end());
return result;
}
};
每层最靠右结点
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
example:输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
1 | /** |
层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
example：输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000] 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/**
* 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:
vector<double> averageOfLevels(TreeNode* root) {
if(root==nullptr)
return {};
queue<TreeNode*>que;
que.push(root);
vector<double>result;
while(!que.empty()){
int size=que.size();
double sum=0;
double result_num=0;
for(int i=0;i<size;i++){
sum+=(double)(que.front()->val);
if(que.front()->left)
que.push(que.front()->left);
if(que.front()->right)
que.push(que.front()->right);
que.pop();
}
result_num=sum/size;
result.push_back(result_num);
}
return result;
}
};
每层最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值
example:输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
1 | /** |
N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]]
1 | /* |
填充每个节点的下一个右侧节点指针
给定一个二叉树。二叉树定义如下：
struct Node { int val; Node left; Node right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL（每一层最右侧的结点都是NULL）。
初始状态下，所有 next 指针都被设置为 NULL。
思路：for循环是对单层的元素进行操作，每次for都需要弹出一位元素，边弹出边记录其值，将其与新对头元素连接，且加入它的左右孩子，这里的长度控制使用的是i<size-1,也即0到size-2的结点都被赋值，最后的元素（size-1）的值尽管没有写明是nullptr，但是仍然可以通过测试，注意条件判断不要写成deq.front()!=nullptr,因为尽管所有的结点弹出，这个位置也不是nullptr。
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
42
43
44/**
* 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:
int maxDepth(TreeNode* root) {
if(root==nullptr)
return 0;
queue<TreeNode*>que;
que.push(root);
int result=1;
int flag=0; //标志，某个结点有左右孩子，为1
while(!que.empty()){
int size = que.size();
for(int i =0;i<size;i++){
//遍历该层结点，存在左孩子就标志
if(que.front()->left){
que.push(que.front()->left);
flag=1;
}
//存在右孩子就标志
if(que.front()->right){
que.push(que.front()->right);
flag=1;
}
que.pop();
}
//有新孩子就++；
if(flag==1){
result++;
flag=0;
}
}
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
36
37/**
* 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:
int minDepth(TreeNode* root) {
if(root==nullptr)
return 0;
queue<TreeNode*>que;
que.push(root);
int result=1;
while(!que.empty()){
int size = que.size();
for(int i =0;i<size;i++){
if(!(que.front()->left)&&!(que.front()->right))
return result;
if(que.front()->left){
que.push(que.front()->left);
}
if(que.front()->right){
que.push(que.front()->right);
}
que.pop();
}
result++;
}
return result;
}
};
5. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
输入：root = [1,2,2,3,4,4,3] 输出：true
递归法
递归法退出的条件：左右孩子为空，说明当前已经到达叶结点了，没有必要递归，前面也没有return false，这时候就return true就好。
递归逻辑：if(!left&&!right)和else
if(!left||!right||left->val!=right->val)都会触发return，所以剩下的只有一种可能，也即左右孩子都存在且元素相等，就递归到下一层，比较下一层的四个相关元素即可。
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/**
* 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:
bool compare(TreeNode*left,TreeNode*right){
if(!left&&!right) //都为空直接返回true，因为说明该子树已经到了底层了
return true;
//子树一侧为空或者元素不相等返回
else if(!left||!right||left->val!=right->val)
return false;
//该层不空，结构和元素又符合，就递归下一层比较，下一层是四个元素的比较
bool outside = compare(left->left,right->right);
bool inside = compare(left->right,right->left);
return outside&&inside;
}
//调用递归
bool isSymmetric(TreeNode* root) {
if(root==nullptr)
return true;
bool Syme=compare(root->left,root->right);
return Syme;
}
};
迭代法
使用迭代的基本判断和递归是相似的，每次处理队列两个元素，这两个元素由入队顺序决定，要么来自左子树的左边+右子树的右边，要么来自左子树的右边+右子树的左边，如果为空（到达叶子结点）那就continue，因为队列里可能还有来自其他子树的元素，如果结构、元素不对直接判断不对称，直到所有的结点都被处理了。
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/**
* 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:
bool isSymmetric(TreeNode* root) {
if(root==nullptr)
return true;
queue<TreeNode*>que;
que.push(root->left);
que.push(root->right);
TreeNode*leftNode;
TreeNode*rightNode;
while(!que.empty()){
leftNode=que.front();
que.pop();
rightNode=que.front();
que.pop();
if(leftNode==nullptr&&rightNode==nullptr)
continue;
else if(!leftNode||!rightNode||leftNode->val!=rightNode->val)
return false;
//核心部分
que.push(leftNode->left);
que.push(rightNode->right);
que.push(leftNode->right);
que.push(rightNode->left);
}
return true;
}
};
6. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树（翻转后与原来的树呈轴对称），并返回其根节点。
翻转：每到达一个根结点，翻转其子树，进入下层结点，翻转其子树......直到叶子结点，所得的就是翻转的树，因此可以通过递归实现：
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/**
* 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:
TreeNode* exchange(TreeNode* root){
if(root==nullptr)
return nullptr;
swap(root->left,root->right);
exchange(root->left);
exchange(root->right);
return root;
}
TreeNode* invertTree(TreeNode* root) {
TreeNode* result=exchange(root);
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/**
* 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:
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr)
return nullptr;
stack<TreeNode*>stk;
stk.push(root);
TreeNode* temp;
while(!stk.empty()){
temp=stk.top();
swap(temp->left,temp->right);
stk.pop();
if(temp->left)
stk.push(temp->left);
if(temp->right)
stk.push(temp->right);
}
return root;
}
};