算法总结c++

基本概念

时间复杂度

略

空间复杂度

略

基本结构

	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

https://www.cnblogs.com/QG-whz/p/5152963.html#_label4_0

1. 数组

数组是一种线性数据结构，使用一组连续的内存空间存储一组具有相同类型的数据。

特性：

1. 随机访问，即通过下标快速定位到数组中的元素，且时间复杂度是O(1)
2. 插入数据和删除数据效率低
3. 编译时预先申请内存空间，数组空间利用率低，不能动态拓展
4. 在不够使用的时候需要扩容，涉及到需要把旧数组中的所有元素向新数组中搬移

题：

前缀和

计算并返回⼀个索引区间之内的元素和，适用于数组值固定

用 n + 1长数组记录前项和，

class NumArray {vector<int> presum;
public:NumArray(vector<int>& nums) {int n = nums.size();presum.resize(n + 1);presum[0] = 0;for(int i=1; i<=n; ++i){presum[i] = presum[i - 1] + nums[i - 1];}}int sumRange(int left, int right) {return presum[right + 1] - presum[left];}
};

https://leetcode.cn/problems/range-sum-query-immutable/
https://leetcode.cn/problems/range-sum-query-2d-immutable/

差分数组

数组长度固定，多次在区间内加相同常数，求最终数组。适用于变化前后区间内部元素差值不变的情况

// 差分数组⼯具类
class Difference {// 差分数组private int[] diff;/* 输⼊⼀个初始数组，区间操作将在这个数组上进⾏ */public Difference(int[] nums) {assert nums.length > 0;diff = new int[nums.length];// 根据初始数组构造差分数组diff[0] = nums[0];for (int i = 1; i < nums.length; i++) {diff[i] = nums[i] - nums[i - 1];}}/* 给闭区间 [i, j] 增加 val（可以是负数）*/public void increment(int i, int j, int val) {diff[i] += val;if (j + 1 < diff.length) {diff[j + 1] -= val;}}/* 返回结果数组 */public int[] result() {int[] res = new int[diff.length];// 根据差分数组构造结果数组res[0] = diff[0];for (int i = 1; i < diff.length; i++) {res[i] = res[i - 1] + diff[i];}return res;}
}

构建与原数组等长的差分数组，处理区域变化时仅对头尾（+1）做加减，最终恢复正常数组时反向操作

https://leetcode.cn/problems/car-pooling/
https://leetcode.cn/problems/corporate-flight-bookings/

快慢指针(索引)

快慢指针解决有序数组的去重（快指针探路，慢指针填数）

class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if(n < 2)return n;int slow = 0;for(int fast = 0; fast < n; ++fast){if(nums[slow] != nums[fast])      nums[++slow] = nums[fast]; 注意++i还是i++}return slow + 1;}
};

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/comments/
https://leetcode.cn/problems/remove-element/submissions/
https://leetcode.cn/problems/move-zeroes/submissions/

左右指针（索引）

盛水容器

两个指针指向两头，由于短板效应，两条边的最短一条决定了面积，此时如果长边内移则面积一定减少，所以就让短边内移

int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1;int area = 0;while(left < right){area = height[left] < height[right] ? max(area, (right - left) * height[left++]): max(area, (right - left) * height[right--]);}return area;}

https://leetcode.cn/problems/container-with-most-water/

三数之和

给出数组中a + b + c = 0的全部情况（不能重复，ijk不相同）

先排序，然后可以遍历i（0~n-2），使用双指针，其中left=i+1，right=n-1，二者往内移动，注意跳过三个指针重复的情况，去掉ai > target的情况。

vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> anns;if(nums.empty() || nums.size() < 3)return anns;std::sort(nums.begin(), nums.end());for(int i = 0; i < nums.size() - 2; ++i){if(nums[i] > 0)return anns;if(i > 0 && nums[i] == nums[i - 1])continue;int left = i + 1;int right = nums.size() - 1;while(left < right){if(nums[i] + nums[left] + nums[right] == 0){anns.push_back({nums[i], nums[left], nums[right]});while(left < right && nums[left] == nums[left + 1])left++;while(left < right && nums[right] == nums[right - 1])right--;left++;right--;}else if(nums[i] + nums[left] + nums[right] > 0){right--;}else if(nums[i] + nums[left] + nums[right] < 0){left++;}}}return anns;}

https://leetcode.cn/problems/3sum/submissions/

最长回文子串

回文串是中心对称的，只需要设置中心，用左右指针向两边扩散即可，当左右指针值相同时，就是回文，注意中心可以是一个元素，也可以是俩，遍历中心即可。

class Solution {
public:string longestPalindrome(string s) {for(int i = 0; i < s.size(); ++i){func(s, i, i);func(s, i, i + 1);}return s.substr(left, len);}
private:int left = 0;int right = 0;int len = 0;void func(string& s, int i, int j){while(i >= 0 && j < s.size() && s[i] == s[j]){if(j - i + 1 > len){len = j - i + 1;left = i;}i--;j++;}}
};

复杂度$O(n^2)$

https://leetcode.cn/problems/longest-palindromic-substring/

2. 链表

链表，也是一种线性数据结构，为了保证链表中元素的连续性，一般使用一个指针来找到下一个元素。

特性：

1. 任意位置插入元素和删除元素的速度快
2. 内存利用率高，不会浪费内存
3. 链表的空间大小不固定，可以动态拓展
4. 随机访问效率低，时间复杂度为0(N)

链表主要分为以下几类：

1. 单向链表，包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
2. 双向链表，也叫双链表，双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针，这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点。
3. 循环链表，中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。

双指针

删除链表的倒数第 n 个结点

前后指针差n位即可。

ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* tmp = new ListNode(0, head);ListNode* left = tmp;ListNode* right = head; for(int i = 0; i < n; ++i){right = right->next;}while(right){right = right->next;left = left->next;}left->next = left->next->next;ListNode* ans = tmp->next;delete tmp;return ans;}

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

翻转链表

左指针指向null，右指针指向头，使用tmp指针记录右指针的下一个节点，让右指针指向左指针，然后左右指针右移，

ListNode* reverseList(ListNode* head) {ListNode* left = nullptr;ListNode* right = head;while(right){ListNode* tmp = right->next;right->next = left;left = right;right = tmp;}return left;}

https://leetcode.cn/problems/reverse-linked-list/

递归

递归函数必须要有终止条件，否则会出错；
递归函数先不断调用自身，直到遇到终止条件后进行回溯，最终返回答案。

将两个升序链表合并为一个新的 升序 链表

利用递归法，每次比较两个头节点的大小，并让小头->next指向后部分的结果

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(!list1)return list2;if(!list2)return list1;if(list1->val < list2->val){list1->next = mergeTwoLists(list1->next, list2);return list1;}else{list2->next = mergeTwoLists(list1, list2->next);return list2;}}

https://leetcode.cn/problems/merge-two-sorted-lists/

链表翻转

递归可以回溯

递归到最后的节点后返回，返回后，此时head是倒数第二个节点，令倒数第二个节点的next的next（最后一个节点）指向自己，然后让倒数第二个节点的next=null。

ListNode* reverseList(ListNode* head) {if(head == nullptr || head->next == nullptr)return head;auto newhead = reverseList(head->next);head->next->next = head;head->next = nullptr;return newhead;}

https://leetcode.cn/problems/reverse-linked-list/

3. 散列表

散列表也叫作哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)

通过哈希函数，把Key和数组下标进行转换，即可实现快速查询。最简单的哈希函数是按照数组长度进行取模运算:
$$index=HashCode(Key)\%Array.length$$

但存在哈希冲突，解决办法：

1. 开放寻址法，即后移一位
2. 链表法
   

当哈希冲突过多时，就需要扩容操作：
3. 当HashMap.Size 大于等于 HashMap的当前长度Capacity 乘以 HashMap的负载因子LoadFactor（默认值为0.75f），进行扩容。
4. 创建一个新的Entry空数组，长度是原数组的2倍。重新Hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中。

twoSum

如果假设输入一个数组 nums 和一个目标和 target，请你返回 nums 中能够凑出 target 的两个元素的值，
使用hashtable记录nums[i]和i，然后遍历nums，查询target - nums[i]是否存在，复杂度O(n)

vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hashtable;for(int i = 0; i < nums.size(); ++i){auto it = hashtable.find(target - nums[i]);if(it == hashtable.end()){hashtable[nums[i]] = i;}else{return {i, it->second};}}return {};}

https://leetcode.cn/problems/two-sum/

无重复的最长字符子串

滑窗法：用散列表或者unordered_set（可快速查询）存储字符是否出现，左指针右移一位，就把原值从unordered_set删除，然后右指针向右移动至出现重复字符。

int lengthOfLongestSubstring(string s) {unordered_set<char> contain;int right = -1; int ans = 0;int n = s.size();for(int left = 0; left < n; ++left){if(left != 0){contain.erase(s[left - 1]);}while(right + 1 < n && !contain.count(s[right + 1])){contain.emplace(s[++right]);}ans = max(ans, right - left + 1);}return ans;}

时间复杂度O(n)

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

4. 栈stack

• 线性数据结构
• 先入后出

栈最主要的功能就是回溯。

回溯法解决组合问题

电话号码字符组合

组合问题是经典需要回溯功能的问题，可以用栈实现。本题中使用递归来回溯号码，使用栈来配合

class Solution {
public:vector<string> letterCombinations(string digits) {vector<string> ans;if(digits.size() == 0)return ans;unordered_map<char, string> phonemap{{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}};string combination;back(ans, combination, 0, digits, phonemap);return ans;}void back(vector<string>& ans, string& combination, int index, string& digits, unordered_map<char, string>& phonemap){if(index == digits.size()){ans.push_back(combination);}else{char x = digits[index];string strings = phonemap.at(x);for(auto& s: strings){combination.push_back(s);back(ans, combination, index + 1, digits, phonemap);combination.pop_back();}}}
};

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

括号匹配问题

括号是否有效

栈先进后出，正好符合括号匹配：

使用哈希map记录左右括号，左为key。左括号入栈，如果不是左括号，就判断是否是栈顶左括号对应的右括号。注意初始时就是右括号的情况，

bool isValid(string s) {int n = s.size();if(n % 2 == 1)return false;unordered_map<char, char> charmap({{'(', ')'},{'{', '}'},{'[', ']'}});stack<char> stk;for(auto& c: s){if(charmap.count(c)){stk.push(c);}else if(stk.empty() || c != charmap[stk.top()]){ //注意初始时就是右括号的情况 stk.empty()return false;}else{stk.pop();}}return stk.empty();}

https://leetcode.cn/problems/valid-parentheses/

5. 队列queue

• 线性数据结构
• 先入先出
• 队列的出口端叫作队头（front），队列的入口端叫作队尾

6. 树

满二叉树要求所有分支都是满的；
而完全二叉树只需保证最后一个节点之前的节点都齐全即可，即满二叉树的部分

存储方式：

1. 链表
2. 数组，注意数组是按满二叉树的位置存放，缺失的节点就空出来，假设一个父节点的下标是parent，那么它的左孩子节点下标就是2×parent +1；右孩子节点下标就是2×parent + 2

二叉查找树（二叉排序树）： 如果左子树不为空，则左子树上所有节点的值均小于根节点的值，如果右子树不为空，则右子树上所有节点的值均大于根节点的值， 左、右子树也都是二叉查找树。

当所有节点的值是有序时，二叉查找树就退化了，此时需要二叉树的自平衡了。二叉树自平衡的方式有多种，如红黑树、AVL树、树堆等

深度优先遍历（前序遍历、中序遍历、后序遍历）

1. 递归
2. 非递归，使用栈

####中序遍历

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;func(root, ans);return ans;}void func(TreeNode* root, vector<int>& ans){if(!root)return;func(root->left, ans);ans.push_back(root->val);func(root->right, ans);}
};

https://leetcode.cn/problems/binary-tree-inorder-traversal/

翻转二叉树

TreeNode* invertTree(TreeNode* root) {if(!root)return root;TreeNode* left = invertTree(root->left);TreeNode* right = invertTree(root->right);root->left = right;root->right = left;   return root;}

https://leetcode.cn/problems/invert-binary-tree/

广度优先遍历（层序遍历）

使用队列，令出队节点的左右子节点分别入队即可。

翻转二叉树

TreeNode* invertTree(TreeNode* root) {if(!root)return root;queue<TreeNode*> Que;Que.push(root);while(!Que.empty()){auto t = Que.front();Que.pop();auto tmp = t->left;t->left = t->right;t->right = tmp;if(t->left)Que.push(t->left);if(t->right)Que.push(t->right);}return root;}

https://leetcode.cn/problems/invert-binary-tree/

递归

树的深度

左右子树的最大深度 + 1 = root的深度

int maxDepth(TreeNode* root) {if(!root)return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}

https://leetcode.cn/problems/maximum-depth-of-binary-tree/

对称二叉树

比较根节点的左右值是否相同，如果相同，进一步比较左的左和右的右是否相同，以及左的右和右的左是否相同。

bool isSymmetric(TreeNode* root) {if(!root)return true;return func(root->left, root->right);}bool func(TreeNode* left, TreeNode* right){if(!left && !right)return true;if(!left || !right)return false;if(left->val != right->val){return false;}return func(left->left, right->right) && func(left->right, right->left);}

https://leetcode.cn/problems/symmetric-tree/

7. 二叉堆

二叉堆本质上是一种完全二叉树，二叉堆的所有节点都存储在数组中，分为两个类型。

最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值
最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值

二叉堆的根节点叫作堆顶。最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素。

插入节点：新节点插在最后，然后与父节点比较大小，进行上浮，逐级进行上述操作。
删除根节点：最后一个节点补上，然后与子节点比较，逐级下沉
把一个无序的完全二叉树调整为二叉堆：从最后一个非叶子节点开始，将所有非叶子节点与其子节点对比并下沉。

堆的插入和删除操作，时间复杂度是O(logn)。但构建堆的时间复杂度是O(n)。

二叉堆是实现堆排序及优先队列的基础

优先队列

优先队列不遵循先入先出的原则，而是分为两种情况。
最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队
最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队

优先队列入队和出队的时间复杂度也是O(logn)

以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点

堆排序

把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。

循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。最终的数组就是排序结果。

整体的时间复杂度是O(nlogn)

经典算法

1. 动态规划

• 在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决

爬楼梯

设爬x层楼，有方法f(x)个，则f(x) = f(x-1) + f(x-2)，因为每次只能爬 1 级或 2 级

int climbStairs(int n) {int dp[n + 1];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; ++i){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}

https://leetcode.cn/problems/climbing-stairs/

买卖股票

遍历卖出的天，最大利润就是在卖出天前的最低价格。

int maxProfit(vector<int>& prices) {int minprice = 1e6;int ans = 0;for(int i = 0; i < prices.size(); i++){ans = max(ans, prices[i] - minprice);minprice = min(prices[i], minprice);}return ans;}

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/