代码随想录刷题
数组
二分查找
- 思路： 有序数组，数组中无重复元素
移除元素
-
思路： 数组在内存地址中是连续的，不能单独删除某个数组中的某个元素，只能覆盖
-
快慢指针法，用于数组、链表、字符串等的操作
-
双向指针法，更优，移动更少的元素
-
-
注意：
-
补充快慢指针法的代码
-
交换时候注意只有在交换的时候，左右数组的下标才额外在交换之后移动一位，用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.从前序与中序遍历序列构造二叉树
回溯
回溯算法理论基础
贪心算法
动态规划
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。