代码随想录刷题
数组
二分查找
- 思路: 有序数组,数组中无重复元素
移除元素
-
思路: 数组在内存地址中是连续的,不能单独删除某个数组中的某个元素,只能覆盖
-
快慢指针法,用于数组、链表、字符串等的操作
-
双向指针法,更优,移动更少的元素
-
-
注意:
-
补充快慢指针法的代码
-
交换时候注意只有在交换的时候,左右数组的下标才额外在交换之后移动一位,用left–和right++
-
有序数组的平方
-
思路: 复数有可能成为最大值,左右比较,放到一个新的数组里面
- 双向指针法:时间复杂度为o(n)
- sort的时间复杂度为o(nlogn)
-
注意: 这个里面先求出大的数,因此想得到递增序列之只能从后往前存储。
长度最小的子数组
-
思路: 暴力算法时间复杂度十分高,会超时
考虑用更优的算法-
暴力解法:如果用暴力解法,两个for循环,时间复杂度为o(n^2)
-
滑动窗口解法:设置一个窗口,不断的移动头和尾,很类似于双指针法
每一个元素都被操作了两次,是o(n)级别的算法
-
-
注意:
- 设置最开始的窗口值要设置成最大的数,防止出现第一次的窗口值很大,小于返回值的初始值,导致无法更新返回值的情况
- INT32_MAX是c++中定义的宏常量,代表int类型32位整数的最大值
-
代码:
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { //初始化滑动窗口的大小尾0 //INT32_MAX是c++标准库中定义的一个宏函数,代表32位有符号整数的最大值 //这里把窗口值的初始值设置为最大 //防止第一次出现的窗口过于大,导致第一次窗口的值无法赋给返回值的情况 int min_sub_array_len = INT32_MAX; int left = 0; //初始化sum的值 int sum = 0; //循环遍历找大于target的窗口 for (int i = 0; i < nums.size(); i++) { sum += nums[i]; while (sum >= target) { //更新最小窗口值 min_sub_array_len = (min_sub_array_len < (i - left + 1)) ? min_sub_array_len : (i - left + 1); //将窗口左边右移,并且将左值减去 sum -= nums[left++]; } } return min_sub_array_len == INT32_MAX ? 0 : min_sub_array_len; } };
螺旋矩阵
-
思路: 坚持循环不变量原则
-
注意: 考察对代码的控制
-
代码:
class Solution { public: vector<vector<int>> generateMatrix(int n) { //二维数组中螺旋矩阵,遵循循环不变量原则 //都左闭右开,1-n^2,总共有n行n列 vector<vector<int>> res(n, vector<int>(n, 0)); //总共要转n/2圈 int loop = n / 2; //定义每次打印的初始边界 int starx = 0, stary = 0; //填充的元素 int count = 1; //右边界,每次循环有边界收缩一位 int offset = n; //总共转loop圈 while (loop--) { int i = starx; int j = stary; //填充从左到右 //左闭右开,右边最后一个元素不填充 for (j = stary; j < offset - 1; j++) { res[i][j] = count; count++; } //填充从上到下 for (i = starx; i < offset - 1; i++) { res[i][j] = count; count++; } //填充从右到左 for (; j > starx; j--) { res[i][j] = count; count++; } //填充从下到上 for (; i > stary; i--) { res[i][j] = count; count++; } //第二圈的时候,起始位置++ starx++; stary++; //收缩右边的值 offset--; } //当n为奇数的时候,单独填充中间的元素 if (n % 2 != 0) { res[n / 2][n / 2] = count; } return res; } };
-
总结:
-
数组中的元素是不能删除的,只能覆盖
-
vector 和 array的区别:
vector的底层实现是array,vector严格上说只是容器,不是数组
-
数组的经典算法
-
二分法
注意界限的控制
注意循环不变量原则
看left==right的时候有没有定义成不成立
时间复杂度是O(logn)
暴力解决的时间复杂度是O(n)
-
双指针法
快慢指针法
时间复杂度是O(n)
暴力解决的时间复杂度是O(n^2)
-
滑动窗口
一种特殊的双指针法
时间复杂度为O(n)
暴力解决的时间复杂度是O(n^2)
-
模拟行为
注意循环不变量原则
主要考察对代码的控制力
链表
移除链表元素
-
代码:
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) { //如果头节点的值等于val //删除头节点 while (head != NULL && head->val == val) { ListNode* temp = head; head = head->next; //delete用于释放内存 delete temp; } //删除非头节点 ListNode* curr = head; //检查的是curr的下一个是不是val while (curr != NULL && curr->next != NULL) { if (curr->next->val == val) { ListNode* temp = curr->next; curr->next = curr->next->next; delete temp; } else { curr = curr->next; } } return head; } };
设计链表
-
思路: 两种方法
- 带头节点
- 不带头节点:实际上应用中都没有头节点
翻转链表
- 思路: 不需要额外空间,直接定义指针
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//翻转链表
//保存curr下一个结点
ListNode* temp;
ListNode* curr = head;
ListNode* pre = NULL;
//当temp不等于NULL的时候
while (curr){
temp = curr->next;
curr->next = pre;
pre = curr;
curr = temp;
}
return pre;
}
};
两两交换链表中的节点
- 思路: 如果没有虚拟头结点,第一次对于头节点的处理会比较困难
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
//设置一个虚拟头节点
//设置虚拟头节点和头指针有什么区别?
//如果设置头节点指针,仍然第一个要对头节点进行操作
//操作不统一
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
//操作要从虚拟节点开始
ListNode* curr = dummyhead;
ListNode* temp1 = NULL;
ListNode* temp2 = NULL;
while (curr->next != NULL && curr->next->next != NULL) {
temp1 = curr->next;
temp2 = curr->next->next->next;
curr->next = curr->next->next;
curr->next->next = temp1;
temp1->next = temp2;
curr = temp1;
}
return dummyhead->next;
}
};
删除链表的倒数第N个结点
- 思路: 利用快慢指针,让fast指针先走n步,等fast指针指向末尾的时候,slow就指向了倒数第n个结点,要存储slow的pre结点
- 注意: 这个题目在Leecode中free结点编译不通过
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummynode = new ListNode(0);
dummynode->next = head;
ListNode* fast = dummynode, * slow = dummynode;
//让fast先走n+1步
for (int i = 0; i < n+1; i++) {
if (fast == NULL) {
return dummynode->next;
}
fast = fast->next;
}
//当fast到末尾的时候。slow指针指向了倒数第n-1个结点
while (fast) {
fast = fast->next;
slow = slow->next;
}
//slow结点现在指向了删除节点的上一个结点
//ListNode* temp;
//temp = slow->next;
slow->next = slow->next->next;
//free(temp);
return dummynode->next;
}
};
链表相交
-
思路: 遍历求出两个链表的长度,然后从后往前比较结点的地址是不是相同的
-
注意:
- 注意应该是地址相同,而不是内容相同。
- 链表只能单向移动,无法从后往前移动
- 写代码要细心,不要总是丢失条件
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
int lenA = 0;
int lenB = 0;
ListNode* currA = headA;
ListNode* currB = headB;
while (currA != NULL)
{
lenA++;
currA = currA->next;
}
while (currB != NULL)
{
lenB++;
currB = currB->next;
}
//此时currA和currB链表指针都在末尾
//现在知道了链表的长度
//让长链表先走差值步
//直接设置,lenA指向长指针
currA = headA;
currB = headB;
if (lenA < lenB) {
swap(lenA,lenB);
swap(currA,currB);
}
//长指针先走n步
int gap = lenA - lenB;
while (gap--) {
currA = currA->next;
}
//此时让两个指针一起行动,直到相等
while (currA!=NULL)
{
if (currA == currB) {
return currA;
}
currA = currA->next;
currB = currB->next;
}
return NULL;
}
};
环形链表II
- 思路:
- 快慢指针,先判断是不是有环
- 如果有环的话,计算环的大小
- 快慢指针回到原点,快指针先走环的大小
- 快慢指针同时走
- 相遇的地方就是环的入口
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
int circle_size = 0;
//判断是不是有环
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
//证明有环
//计算环的大小
slow = slow->next;
circle_size++;
while (fast != slow) {
slow = slow->next;
circle_size++;
}
//再次跳进时候已经计算得到了circle_size
//将fast向前走circle_size距离
fast = head;
slow = head;
while (circle_size--)
{
fast = fast->next;
}
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
//再次跳出是相遇在结点
return fast;
}
}
return NULL;
}
};
链表经典题目
-
虚拟头节点
一些头节点需要单独判断是不是为空的操作
-
反转链表
递归和迭代,设置头节点会简单很多
-
删除倒数第N个节点
-
链表相交
-
环形链表
哈希表
哈希表理论基础
-
哈希函数就是一种数组的映射
-
可以用来快速的判断一个元素是否出现集合里
数组查询的时间复杂度为O(n)
哈希表查询的时间复杂读为O(1),以空间换时间
-
哈希碰撞
解决哈希碰撞的两种方法
拉链法:链表
线性探测法:talesize大于datesize,不然就没有位置去存放冲突的数据了
-
常见的三种哈希结构
数组
set(集合)
map(映射)
有效的字母异位词
-
思路:
暴力解法:两层for循环哈希表:空间为O(n),时间复杂度为O(1)
-
注意: 利用ASCII值进行计算
-
代码:
class Solution { public: bool isAnagram(string s, string t) { //申请一个大小为26的数组 int arr[26] = { 0 }; //这个大小位26的数组初始值为0 //遍历s,将其映射到数组中 for (int i = 0; i < s.size(); i++) { arr[s[i] - 'a']++; } for (int i = 0; i < t.size(); i++) { arr[t[i] - 'a']--; } for (int i = 0; i < 26; i++) { if (arr[i] != 0) { return false; } } return true; } };
两个数组的交集
-
思路:利用unorder_set,底层实现是哈希表,无序,key无序,key值不可重复,查询效率为O(1)
-
注意:利用数组做哈希表的,都是有大小的数,无大小的数用来做哈希表,容易造成空间的浪费。
-
代码:
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { //用unorder_set数据结构 //存放结果,用哈希set主要是为了给结果去重 unordered_set<int> result_set; //括号里加入的是插入nums_set数组的范围 unordered_set<int> nums_set(nums1.begin(), nums1.end()); //循环遍历nums2 for (int num : nums2) { //可以理解为尾部的指针,如果找不到num就返回一个尾部的指针 if (nums_set.find(num) != nums_set.end()) { result_set.insert(num); } } //是一个函数,相当于把result_set的值复制到一个新的数组中 //这里复制到一个新的数组中是应为函数返回值类型为vector<int> return vector<int>(result_set.begin(), result_set.end()); } };
快乐数
-
思路:
如果sum值重复出现,那就进入无限循环了
否则就一计算,计算到sum=1为止
如果不适用哈希表,每次都进行查找,那么时间复杂度会为n^2
-
注意:
-
代码:
class Solution { public: int getSum(int n) { int sum = 0; //当n不等于0的时候 while (n) { sum += (n % 10) * (n % 10); n = n / 10; } return sum; } bool isHappy(int n) { //定义了一个sum_set数组 unordered_set<int> sum_set; //循环运行 while (1) { int sum = getSum(n); //是快乐数的返回值 if (sum == 1) { return true; } //跳出循环的条件 if (sum_set.find(sum) != sum_set.end()) { return false; } else { //插入sum值 sum_set.insert(sum); } n = sum; } } };
两数之和
-
思路:
数组、set、map这三种哈希表的结构中,只有map是key,value对应的
数组、set、map这三种哈希表的结构都有三种底部实现
底层实现是红黑树的都是要求key有序
底层实现是哈希表的查询效率和增删效率都最高,但是是无序实现
-
注意:
-
代码:
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { //定义一个map数组 unordered_map<int,int> map; //遍历数组,在已经访问过的map中寻找是不是有target-nums[i]的数组 for (int i = 0; i < nums.size(); i++) { auto iter = map.find(target - nums[i]); if (iter != map.end()) { return { iter->second,i }; } //没找到就把数值插入进map中 //其中pair<int,int>代表插入一个有序的键值对,模板参数 map.insert(pair<int,int>(nums[i], i)); } //都没找到返回一个空数组 return {}; } };
四数相加
-
思路:
四个独立的数组,不用考虑有重复的四个元素相加的情况
和计算两数之和一样,先将一个和存放到数组中,然后对比target-和
-
注意:
此题不用考虑不许重复出现
这个题中的unorder_map的用法同上一问不同
-
代码:
class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { //定义一个哈希map unordered_map<int, int> map; int size = nums1.size(); //循环遍历插入map //map中的key为和,value为出现的次数 for (int a : nums1) { for (int b : nums2) { map[a + b]++; } } int count = 0; //这个时候map里面就存着两数之和了 for (int c : nums3) { for (int d : nums4) { if (map.find(0 - (c + d)) != map.end()) { //找到了累加 //这个时候map里面就代表着key,数组的值就代表着value count += map[0 - (c + d)]; } } } return count; } };
赎金信
-
思路:
暴力枚举:两层for循环
哈希解法:如果用map的话,底层实现是红黑树和哈希表,map消耗的空间比较大
因此用数组更加直接
-
注意:
-
代码:
class Solution { public: bool canConstruct(string ransomNote, string magazine) { //ransomNote中的字母要在magzine中出现 int map[26] = {0}; for (int i = 0; i < magazine.size(); i++) { //将字符减a作为下标 int idex = magazine[i] - 'a'; map[idex]++; } //遍历递减,如果出现负数,跳出 for (int i = 0; i < ransomNote.size(); i++) { int idex = ransomNote[i] - 'a'; map[idex]--; if (map[idex] < 0) { return false; } } return true; } };
三数之和
-
思路:
-
哈希法:(思路)
不好去重,用哈希法来确定a-b的值
时间复杂度是O(n^2)
哈希表的额外空间复杂度是O(n)
-
双指针法
时间复杂度O(n^2)
空间复杂度O(1)
-
-
注意:
-
去重的逻辑思考,剪枝操作
-
总共有一轮剪枝
两轮去重
第一轮去重是控制第一个元素不要重复
第二轮去重是控制剩下两个元素不要重复
-
-
代码:
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { //定义一个返回的数组值 vector<vector<int>> result; //首先对数组进行排序 sort(nums.begin(), nums.end()); //进行循环 for (int i = 0; i < nums.size(); i++) { //第一轮剪枝,如果第一个数值大于零,则不存在三数之和为0的情况 if (nums[i] > 0) { return result; } //第一轮去重,结果的一元数组不可以相同,但是一元数组内的元素可以相同 //如果当前位置和下一个位置进行比对,会出现,-1,-1,2 //因此去重操作应该是当前位置和前面的元素进行比较 if (i > 0 && nums[i] == nums[i - 1]) { continue; } //每一轮开始遍历 int left = i + 1; int right = nums.size() - 1; //只要遍历基点n的值确定不重复,那就可以确定不重复 //基点右边是一个二分查找 while(left<right) { //如果大于0要将数值减小 if (nums[i] + nums[left] + nums[right] > 0) { right--; } //小于零要将数值增大 else if (nums[i] + nums[left] + nums[right] < 0) { left++; } //等于零要将值存进三元组,同时收缩left和right else { result.push_back(vector<int>{nums[i], nums[left], nums[right]}); //第二次去重,对三元组中的两个元素进行去重 //这里面把指针移动到唯一的right和left处 //再进行加一,进行下一个循环 while (right > left && nums[right] == nums[right - 1]) { right--; } while (right > left && nums[left] == nums[left + 1]) { left++; } right--; left++; } } } return result; } };
四数之和
-
思路:
四数之和的思路和三数之和的思路一样
这两个之间就是通过双指针法把原本的时间复杂度降低一个等级
-
注意:
-
注意剪枝和去重
剪枝得时候注意,由于target是未知的,不可以直接用首元素大于target来进行剪枝
不然会出现-4>-10,但是数组接下来的几个数都是负数
但是还是可以进行剪枝
剪枝的本质就是正数的大于是无法再合成targrt的,不用target>0是因为剪枝不彻底,会漏掉target<0,但是第一个元素已经大于0的情况,用首元素大于0,且大于target是合理的。
-
注意四数之和相加得时候会出现数组越界,这个时候要用long,不然比较溢出
-
-
代码:
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { //定义一个返回的数组值 vector<vector<int>> result; //首先对数组进行排序 sort(nums.begin(), nums.end()); //第一层循环 for (int i = 0; i < nums.size(); i++) { //第一层剪枝 //如果第一个数就大于0,那就一定不会有四数之和等于0 //这里不可以直接用这个剪枝,因为target是一个未确定的值 if (nums[i] > target && nums[i] >= 0) { //这里用break,最后再统一返回 break; } //第一次去重 if (i > 0 && nums[i] == nums[i - 1]) { continue; } //第二层循环 for (int j = i + 1; j < nums.size(); j++) { //第二次剪枝,如果最开始的两个数加在一起都大于target if (nums[i] + nums[j] > target && nums[i] >= 0) { //跳出当前所有循环 break; } //第二次去重 if (j > i + 1 && nums[j] == nums[j - 1]) { //继续本次循环的下一次循环 continue; } //寻找两个数的和 int left = j + 1; int right = nums.size() - 1; while (left < right) { if ((long)nums[i] + nums[j] + nums[left] + nums[right] > target) { right--; } else if ((long)nums[i] + nums[j] + nums[left] + nums[right] < target) { left++; } else { //将此数组存进result中 result.push_back(vector<int>{nums[i], nums[j], nums[right], nums[left]}); //第三次去重 while (left < right && nums[left] == nums[left + 1]) { left++; } while (left < right && nums[right] == nums[right - 1]) { right--; } left++; right--; } } } } return result; } };
双指针总结
- 数组
- 数组不可以凭空消失,只能进行覆盖,移除查找的时候用双指针法
- 字符串
- 双指针法
- 链表
- 快慢指针法
- 双指针法
- N数之和法
- 双指针法
- 哈希法(其实用双指针法可以解决,但是用双指针法求下标不太ok,双指针会将表先进行排序,打乱下标,如果进行映射的话还会占用额外空间)
栈与队列
栈与队列理论基础
-
栈和队列是STL(c++标准库)里面的两个数据结构
-
STL是有多个版本的,只有知道使用的STL是哪个版本的才能知道对应的栈和队列的实现原理
三个最为普遍的STL版本:
- HP STL其他版本的C++ STL,一般是以HP STL为蓝本实现的,HP STL是C++ STL的第一个实现版本,且开放源代码
- P.J.Planger STL是由P.J.Plaunger参照HP STL实现出来的,被Visual C++编译器所采用,不是开源的
- SGL STL是由Silicon Graphics Computer Systems公司参照HP STL实现,被Linux的C++编译器GCC所采用,SGL STL是开源软件,源码可读性甚高。
-
关于SGI STL里面的数据结构
-
栈
栈先进后出,提供push和pop等接口,不提供走访功能,不提供迭代器。
栈是以底层容器来完成其所有的工作,对外提供统一的接口,底层容器是可插拔的(也就是说我们可以控制使用哪种容器来实现栈的功能)。
STL一般不被归为容器,而是容器适配器(container adapter)
栈的内部结构可以是vector, deque, list,主要就是数组和链表的底层实现
-
SGI STL如果没有指定底层实现的话,默认是以deque为缺省情况下栈的底层结构。
deque是一个双向队列,只要封住一段,开通另一端就可以实现栈的逻辑了
-
-
-
用栈实现队列
- 思路:用栈,一个模仿进队列,一个模仿出队列
- 注意:
- 代码:
用队列实现栈
-
思路:用一个队列,将最后一个元素前面的元素重新插入队列,
-
注意:
-
代码:
class MyStack { public: queue<int> que; MyStack() { } void push(int x) { que.push(x); } int pop() { //将队首元素重新插回到队尾 int size = que.size(); size--; for (int i = 0; i < size; i++) { int temp = que.front(); que.push(temp); que.pop(); } int num = que.front(); que.pop(); return num; } int top() { int size = que.size(); size--; for (int i = 0; i < size; i++) { int temp = que.front(); que.push(temp); que.pop(); } int num = que.front(); que.pop(); que.push(num); return num; } bool empty() { return que.empty(); } };
有效的括号
-
思路:利用栈的特性实现括号匹配
-
注意:通过一些巧妙的方式利用栈,多练,无他
-
代码:
class Solution { public: bool isValid(string s) { //如果括号是偶数,一定不符合条件 if (s.size() % 2 != 0) { return false; } stack<char> string; for (int i = 0; i < s.size(); i++) { if (s[i] == '(') { string.push(')'); } else if (s[i] == '[') { string.push(']'); } else if (s[i] == '{') { string.push('}'); } else { if (string.empty()||string.top() != s[i]) { return false; } string.pop(); } } return string.empty(); } };
删除字符串中的所有相邻重复项
-
思路:同括号匹配原理相似
-
注意:用字符串也可以实现栈的功能
-
代码:
class Solution { public: string removeDuplicates(string S) { string result; for (char s : S) { //当字符串为空或者当前字符不相等的时候 if (result.empty() || result.back() != s) { result.push_back(s); } else { result.pop_back(); } } return result; } };
逆波兰表达式求值
-
思路:后缀表达式求和思想
-
注意:注意弹栈时候进行加减乘除的时候num1和num2是有顺序的
stoll()函数是把字符串转化成longlong类型
-
代码:
class Solution { public: int evalRPN(vector<string>& tokens) { stack<long long> st; long long num1; long long num2; int size = tokens.size(); for (int i = 0; i < size; i++) { if(tokens[i] == "+"||tokens[i] == "-"|| tokens[i] == "*"|| tokens[i] == "/"){ num1 = st.top(); st.pop(); num2 = st.top(); st.pop(); if (tokens[i] == "+") st.push(num2 + num1); if (tokens[i] == "-") st.push(num2 - num1); if (tokens[i] == "*") st.push(num2 * num1); if (tokens[i] == "/") st.push(num2 / num1); } else { //stoll()将字符串转成longlong的整数 st.push(stoll(tokens[i])); } } return st.top(); } };
滑动窗口最大值(困难)
-
思路:
单调队列:保证队列里的元素单调递增或单调递减的原则
-
注意:
- if主要用于判断,while用于迭代
- 实际上时间复杂度是O(n)
-
代码:
class Solution { private: class MyQueue { public: deque<int> que; //每次弹出的时候,比较当前要弹出的数值是否等于队列出口的元素的数值,如果相等则弹出 //pop之前要判断队列是否为空 void pop(int value) { //相等的时候可以弹出,如果不相等,证明这个数现在不是最大值,没有在队列里面或者在后面 //可以不用弹出 //如果相等说明最大值弹出了 if (!que.empty() && value == que.front()) { que.pop_front(); } } //push是从后往前插入 void push(int value) { while (!que.empty() && que.back() < value) { que.pop_back(); } que.push_back(value); } //查询当前的最大值直接返回前端就可以了 int front() { return que.front(); } }; public: //实现一个单调队列 vector<int> maxSlidingWindow(vector<int>& nums, int k) { MyQueue que; vector<int> result; //首先将前n个放入数组中 for (int i = 0; i < k; i++) { que.push(nums[i]); } //开始将第一轮的最大元素输入到result result.push_back(que.front()); //迭代 for (int i = k; i < nums.size(); i++) { //移动滑动窗口 que.pop(nums[i-k]); que.push(nums[i]); //记录当前的最大值 result.push_back(que.front()); } return result; } };
前K个高频元素(思路)
-
思路:
- 首先构建map,map用来统计数值出现的次数
- 再将map中的元素进行排序寻找到前K个高频元素
- 用小顶堆,小顶堆弹出最小的n个值,最终得到了前K个高频元素
- 为什么不能用有序map呢?
-
注意:
- map和小顶堆的实现
- 有很多新的语法
-
代码:
class Solution { public: //定义了一个比较规则 class mycomparion { public: //pair是c++标准模板库中定义的一个模板类,用于表示一对值 //这个函数其实是定义了一种比较规则,按照两个pair数组的secound值的降序进行比较 bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) { //如果lhs的secound值大于rhs的secound值,就返回true return lhs.second > rhs.second; } }; vector<int> topKFrequent(vector<int>& nums, int k) { //用map统计元素出现的频率 unordered_map<int, int> map; for (int i = 0; i < nums.size(); i++) { //这个里面key值是nums[i] //value是key出现的次数 //对key进行排序并没有意义 //因此用无序map map[nums[i]]++; } //对value值进行排序 //定义一个小顶堆,大小为k //将所有频率的数值存进去,小的数值自然就被弹出 //priority_queue是一个容器适配器,用于实现基于某种比较的排序 //其底层实现逻辑是堆,保证头部永远是优先级最高的元素 //三个参数分别为,比较对象,存储比较对象的容器,比较逻辑 priority_queue < pair<int, int>, vector<pair<int, int>>,mycomparion> pri_que; //用固定大小为k的小顶堆,扫描所有频率的数值 //::是作用域解析符用来指定特定的命名空间或类的成员 //iterator是unordered_map<int,int>数据结构中定义的迭代器,用于遍历map for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) { //把其中的it指向的内容放进去 pri_que.push(*it); if (pri_que.size() > k) { pri_que.pop(); } } //小顶堆先输出的是最小的,采用倒叙来输出数组 vector<int> result(k); for (int i = k - 1; i >= 0; i--) { result[i] = pri_que.top().first; pri_que.pop(); } return result; } };
栈与队列的总结
-
栈与队列的理论基础
- 容器
- deque(双端队列)
- list(列表)
- vector(数组)
- 容器适配器
- stack(栈)
- queue(队列)
- priority_queue{元素,元素容器,优先级规则},(优先级队列)
- 栈与队列的问题
- 容器
- 总结
- 单调队列
- 优先级队列
二叉树
二叉树理论基础篇
-
题目分类
- 二叉树的遍历方式
- 二叉树的属性
- 二叉树的修改与构造
- 求二叉树的搜索属性
- 二叉树的公共祖先问题
- 二叉搜索树的修改与构造
-
二叉树的类型
-
满二叉树
-
完全二叉树
-
二叉搜索树
-
平衡二叉搜索树
C++中map、set、multimap,multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作时间时间复杂度是logn,unordered_map、unordered_set,unordered_map、unordered_set底层实现是哈希表。
-
-
二叉树的存储方式
- 链式存储
- 顺序存储
-
二叉树的遍历方式
栈其实就是递归的一种实现结构
- 深度优先遍历
- 前序遍历(递归法,迭代法)
- 中序遍历(递归法,迭代法)
- 后序遍历(递归法,迭代法)
- 广度优先遍历
- 层次遍历(迭代法)
- 深度优先遍历
-
二叉树的定义方式
struct TreeNode { int val; TreeNode *left; TreeNode *right; //初始化的时候左右指针为空 TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
-
总结
二叉树是一种基础数据结构
二叉树的递归遍历
-
思路:
递归的思路:
1.确定递归函数的参数和返回值
2.确定中止条件
3.确定单层递归逻辑
-
注意:
-
代码:
二叉树的迭代遍历
- 思路:
- 注意:
- 代码:
二叉树的统一迭代法
- 思路:
- 注意:
- 代码:
二叉树层序遍历
二叉树的层序遍历
-
思路:层序遍历的底层逻辑是队列,先进先出
-
注意:
-
代码:
模板代码(打十个)
vector<vector<int>> levelOrder(TreeNode* root) { //定义一个存放Treenode指针的队列 queue<TreeNode*> que; //如果root不为空的时候将,root入队 if (root != NULL) { que.push(root); } //返回的是每一层 vector<vector<int>> result; //遍历直到队列为空 while (!que.empty()) { int size = que.size(); vector<int> layer; for (int i = 0; i < size; i++) { TreeNode* temp = que.front(); que.pop(); layer.push_back(temp->val); if (temp->left != NULL) { que.push(temp->left); } if (temp->right != NULL) { que.push(temp->right); } } result.push_back(layer); } return result; }
二叉树的层序遍历II
-
思路:
这种方式会超出内存限制
用一个栈去存储结果
队列出队顺序层,右,左
入栈之后再出栈顺序,左,右,层
如果用栈的话如何进行分层呢
直接用队列,然后最后将result数组进行反转
-
注意:
反转数组的函数
二叉树的右视图
-
思路:
层次遍历,但是只把最右的节点入栈,把每一层的最后一个节点入栈
-
注意:代码细节注意
二叉树的层平均值
- 思路:每一层的数相加,相除
- 注意:
N叉树的层序遍历
-
思路:
Node的数据结构是,存储节点的值,存储一个children数组
-
注意:
在每个树行中找最大值
-
思路:
层次遍历,找每一层的最大值
-
注意:
//INT_MIN是c++标准库中定义的宏常量,通常是一个最小的负数值,用来求最大值的时候定义初始量 int max = INT_MIN;
填充每个节点的下一个右侧节点指针
-
思路:
将next指针指向同层的下一个节点
层次遍历,每一层队列不为空的时候指向下一个节点,队列为空的时候指向NULL
-
注意:
填充每个节点的下一个右侧节点指针II
- 思路:完全二叉树和非完全二叉树没有什么区别
- 注意:
二叉树的最大深度
- 思路:
- 层次遍历,计算总共有多少层
- 递归,求左子树和右子树的最大深度,取最大值+1返回depth
- 注意:
二叉树的最小深度
- 思路:
- 层次遍历,如果有一个节点是叶节点就返回深度
- 递归,注意与求最大深度的单层递归逻辑不同,如果左子树为空,右子树不为空,返回的值应该是右子树的深度+1,而不是深度为1
- 注意:
翻转二叉树(拓展部分,中序遍历不可以)
-
思路:
递归实现
-
注意:
注意递归出口和递归条件
-
代码:
TreeNode* invertTree(TreeNode* root) { //递归出口 if (root == NULL) { return root; } //递归体 swap(root->left, root->right); invertTree(root->left); invertTree(root->right); }
对称二叉树
-
思路:
-
递归
-
确定递归函数的参数和返回值
比较左右两棵子树是不是对称的
比较的不是左右孩子,而是左右子树的对称节点
-
确定终止条件
首先处理空结点,非空结点比较的是数值
左节点为空,右节点不为空,false
左节点不为空,右节点为空,false
左右节点都为空,对称,返回true
-
确定单层递归逻辑
处理节点不为空的时候,比较val的值
并且将左节点的左孩子和右节点的右孩子进行比较
左节点的右孩子和右节点的左孩子进行比较
-
-
队列
-
栈
-
-
注意:注意代码细节
-
代码:
- 递归法
bool compare(TreeNode* left, TreeNode* right) { //判出条件 if (left == NULL && right == NULL) { return true; } else if (left == NULL && right != NULL) { return false; } else if (left != NULL && right == NULL) { return false; } else if (left->val != right->val) { return false; } //此时是左右节点都不为空,且数值相同的情况 //此时做递归判断 //只有左右递归都返回true的时候才返回true; bool L = compare(left->left, right->right); bool R = compare(left->right, right->left); return L && R; } bool isSymmetric(TreeNode* root) { if (root == NULL) { return true; } return compare(root->left, root->right); }
完全二叉树的节点个数
-
思路:
- 递归:分别计算左子树和右子树有多少个节点,再相加
- 层序遍历:统计总共遍历了多少层
-
注意:
//这样的代码是错误的 //忽略掉了一些情况 int countRecursion(TreeNode* left, TreeNode* right) { //判出条件 if (left == NULL && right != NULL) { return 1 + countRecursion(right->left, right->right); } else if (left != NULL && right == NULL) { return 1 + countRecursion(left->left, left->right); } else if (left == NULL && right == NULL) { return 1; } //这个时候就是左右节点都非空结点 int num = countRecursion(left->left, right->right) + 1; return num; } int countNodes(TreeNode* root) { if (root == NULL) { return 0; } return countRecursion(root->left, root->right); }
-
代码:
int countNodes(TreeNode* root) { //判出条件 if (root == NULL) { return 0; } int left = countNodes(root->left); int right = countNodes(root->right); int num = left + right + 1; return num; }
平衡二叉树
-
思路:
-
平衡二叉树:左右两棵子树的高度之差小于1
-
递归:一棵树是平衡二叉树,它的左右子树也是平衡二叉树
如果直接返回true和false逻辑很复杂
应该直接把函数分成两步,判断树是不是平衡二叉树,将左右两个树的判断结果进行与运算
//存在逻辑错误的代码 bool isBalanced(TreeNode* root) { //递归出口 if (root == NULL) { return true; } else { int lefthigh = treeHigh(root->left); int righthigh = treeHigh(root->right); if (lefthigh >= righthigh) { //在这一行会直接返回,永远不会达到right && left return (lefthigh - righthigh) <= 1; } else { return (righthigh - lefthigh) <= 1; } } bool right = isBalanced(root->right); bool left = isBalanced(root->left); return right && left; }
-
迭代:手动实现一个栈,用迭代的方法再写一遍
-
-
注意:
-
代码:
int treeHigh(TreeNode* root) { //用层次遍历求树的高度 queue<TreeNode*> que; int num = 0; if (root != NULL) { que.push(root); } TreeNode* temp; while (!que.empty()) { int size = que.size(); for (int i = 0; i < size; i++) { temp = que.front(); que.pop(); if (temp->left != NULL) { que.push(temp->left); } if (temp->right != NULL) { que.push(temp->right); } } //执行一次for循环就证明遍历了一个层 num++; } return num; } bool isBalanced(TreeNode* root) { //递归出口 if (root == NULL) { return true; } else { int lefthigh = treeHigh(root->left); int righthigh = treeHigh(root->right); if (lefthigh >= righthigh) { if (lefthigh - righthigh > 1) { return false; } } else { if (righthigh - lefthigh > 1) { return false; } } } bool right = isBalanced(root->right); bool left = isBalanced(root->left); return right && left; }
二叉树的所有路径
-
思路:
回溯
回溯和递归是一一对应的,有一个递归就要有一个回溯,递归和回溯要永远在一起
这道题目要求从根节点到叶子的路径,用前序遍历
递归:
1.要传入根节点,记录每一条路径的path和存放结果集的string
2.确定递归的终止条件
本题是要找到叶子节点,不让cur指向NULL
中止的时候,把vector 中的数据转化称string存入vector 数组中,函数进行回溯调用,继续寻找下一条路径。
3.先存根节点
如果根节点的左右节点为控,递归的时候就不进行下一层递归了
否则将左右节点加入,进行下一层递归,当达成判出条件的时候,要进行回溯
一个递归一个回溯,因此这里递归要加在花括号之前
//错误写法 //只有一条路径,最后pop_back一个数据,并没有起到回溯的作用 if (cur->left) { traversal(cur->left, path, result); } if (cur->right) { traversal(cur->right, path, result); } path.pop_back(); //正确写法 //回溯的时候,先往右走,然后右节点如果存在,再递归加入右节点的路径 if (cur->left) { traversal(cur->left, path, result); path.pop_back(); // 回溯 } if (cur->right) { traversal(cur->right, path, result); path.pop_back(); // 回溯 }
-
注意:
精简代码,二刷时候看一下
-
代码:
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) { //将cur压入栈中 path.push_back(cur->val); //判出条件 if (cur->left == NULL && cur->right == NULL) { string spath; for (int i = 0; i < path.size() - 1; ++i) { spath += to_string(path[i]); spath += "->"; } spath += to_string(path[path.size() - 1]); result.push_back(spath); } //递归体 //左 if (cur->left != NULL) { traversal(cur->left, path, result); path.pop_back(); } //右 if (cur->right != NULL) { traversal(cur->right, path, result); path.pop_back(); } } vector<string> binaryTreePaths(TreeNode* root) { vector<int> path; vector<string> result; if (root == NULL) { return result; } traversal(root, path, result); return result; }
左叶子之和
-
思路:
首先判断什么是左叶子,左叶子首先是左孩子,其次左右节点为空
因此判断是不是左叶子要看它的父节点
-
注意:
-
代码:
int sumOfLeftLeaves(TreeNode* root) { //判出条件 if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 0; } //递归体 int leftValue = sumOfLeftLeaves(root->left); //当左子树是左叶子的时候,修改左子树的值 if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) { leftValue = root->left->val; } int rightValue = sumOfLeftLeaves(root->right); return leftValue + rightValue; }
找树左下角的值(二刷用递归写)
-
思路:
层序遍历:最后一层中的第一个节点
递归:
递归到最左边要判断是不是最后一行
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单层递归的逻辑
-
注意:
-
代码:
层序遍历
int findBottomLeftValue(TreeNode* root) { queue<TreeNode*> que; int result; que.push(root); while (!que.empty()) { int size = que.size(); TreeNode* left = que.front(); result = left->val; for (int i = 0; i < size; i++) { TreeNode* temp = que.front(); que.pop(); if (temp->left != NULL) { que.push(temp->left); } if (temp->right != NULL) { que.push(temp->right); } } } return result; }
递归
路径总和
-
思路:
递归+回溯
如果父节点不拎出来判断,root = NULL并不是返回的条件,叶子节点才是返回的条件
栈模拟:有空写一下
-
注意:
-
代码:
bool travel(TreeNode* root, int count) { //递归出口 if (root->left == NULL && root->right == NULL) { return count == 0; } //左节点 if (root->left != NULL) { count -= root->left->val; if (travel(root->left, count)) { return true; } //如果到这一步证明该节点下不存在路径,回溯 count += root->left->val; } //右节点 if (root->right != NULL) { count -= root->right->val; if (travel(root->right, count)) { return true; } count += root->right->val; } //遍历到这证明左右子树都没有路径 return false; } bool hasPathSum(TreeNode* root, int targetSum) { if (root == NULL) { return false; } //这个时候已经把根节点加入路径了 return travel(root, targetSum - root->val); }
路经总和II
-
思路:
同路径总和不同的是,这个需要找出所有的路径,递归不要返回值
-
注意:
注意根节点的处理,先把根节点放入path中,如果path递归到最后count不为0,这个path不会放到result中。
-
代码:
class Solution { private: vector<vector<int>> result; vector<int> path; void travel(TreeNode* root, int count) { //当遇到叶子节点的时候 if (!root->left && !root->right && count == 0) { //路径结束,且是正确路径 result.push_back(path); } //左节点 if (root->left) { //先将左节点入栈 path.push_back(root->left->val); count -= root->left->val; travel(root->left, count); count += root->left->val; path.pop_back(); } //右节点 if (root->right) { path.push_back(root->right->val); count -= root->right->val; travel(root->right, count); count += root->right->val; path.pop_back(); } return; } public: vector<vector<int>> pathSum(TreeNode* root, int targetSum) { if (root == NULL) { return result; } path.push_back(root->val); travel(root, targetSum - root->val); return result; } };
从中序与后序遍历序列构造二叉树
-
思路:
- 后序的最后一个元素确定根
- 中序根据根进行切分,然后将后序分成两个部分
- 递归,分成的左右两个部分分别重复1,2步骤直到后序剩最后一个元素
-
注意:
- 切割数组的时候要遵循一个原则,不然会漏掉元素,和二分法的准则一样。
- 中序数组和后序数组的大小相等。
-
代码:
- 代码遵循左闭右开 的原则。
class Solution
{
private:
// traversal函数的目的是找到当前队列的根节点,并且返回的是左右指针已经链接好的根节点
TreeNode *traversal(vector<int> &inorder, int inorderBegin, int inorderEnd, vector<int> &postorder, int postorderBegin, int postorderEnd)
{
// 判出条件
if (postorderEnd - postorderBegin == 0)
{
return NULL;
}
// 取出后序遍历的最后一个节点
int rootValue = postorder[postorderEnd-1];
TreeNode *root = new TreeNode(rootValue); // 构造函数初始化就是左右指针指向空
// 当后序遍历只剩下这一个节点的时候证明是叶子节点,入队
if (postorderEnd - postorderBegin == 1)
{
return root;
}
// 找到中序遍历的切割点下标
int inorderIndex;
for (inorderIndex = 0; inorderIndex < inorder.size(); ++inorderIndex)
{
if (inorder[inorderIndex] == rootValue)
break;
}
// 切割中序数组,得到中序左数组和中序右数组
// 左中序区间
int leftInorderBegin = inorderBegin;
int leftInorderEnd = inorderIndex;
// 右中序区间
int rightInorderBegin = inorderIndex + 1;
int rightInorderEnd = inorderEnd;
// 切割后序数组,得到后序左数组和后序右数组
// 后序左数组
int leftPostorderBegin = postorderBegin;
int leftPostorderEnd = postorderBegin + leftInorderEnd - leftInorderBegin; // 起始位置加上中序遍历的元素个数
// 后序右数组
int rightPostorderBegin = postorderBegin + leftInorderEnd - leftInorderBegin ;
int rightPostorderEnd = postorderEnd - 1;
// 遍历得到左右子树
root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, postorder, leftPostorderBegin, leftPostorderEnd);
root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);
return root;
}
public:
//buildTree返回的就是要入队的根节点
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
{
if(inorder.size() == 0||postorder.size() == 0){
return NULL;
}
return traversal(inorder,0,inorder.size(),postorder,0,postorder.size());
}
};
补充:105.从前序与中序遍历序列构造二叉树