宁乡县建设局网站,电商平面设计师,wordpress首页非常慢,室内设计方案讲解思路文章目录基本概念时间复杂度空间复杂度基本结构1. 数组前缀和差分数组快慢指针(索引)左右指针#xff08;索引#xff09;盛水容器三数之和最长回文子串2. 链表双指针删除链表的倒数第 n 个结点翻转链表递归将两个升序链表合并为一个新的 升序 链表链表翻转3. 散列表twoSum无…
文章目录基本概念时间复杂度空间复杂度基本结构1. 数组前缀和差分数组快慢指针(索引)左右指针索引盛水容器三数之和最长回文子串2. 链表双指针删除链表的倒数第 n 个结点翻转链表递归将两个升序链表合并为一个新的 升序 链表链表翻转3. 散列表twoSum无重复的最长字符子串4. 栈stack回溯法解决组合问题电话号码字符组合括号匹配问题括号是否有效5. 队列queue6. 树深度优先遍历前序遍历、中序遍历、后序遍历翻转二叉树广度优先遍历层序遍历翻转二叉树递归树的深度对称二叉树7. 二叉堆优先队列堆排序经典算法1. 动态规划爬楼梯买卖股票基本概念
时间复杂度
略
空间复杂度
略
基本结构
数组链表读取O(1)O(n)插入O(n)O(1)删除O(n)O(1)https://www.cnblogs.com/QG-whz/p/5152963.html#_label4_0 1. 数组
数组是一种线性数据结构使用一组连续的内存空间存储一组具有相同类型的数据。 特性 随机访问即通过下标快速定位到数组中的元素且时间复杂度是O(1)插入数据和删除数据效率低编译时预先申请内存空间数组空间利用率低不能动态拓展在不够使用的时候需要扩容涉及到需要把旧数组中的所有元素向新数组中搬移 题
前缀和
计算并返回⼀个索引区间之内的元素和适用于数组值固定 用 n 1长数组记录前项和 class NumArray {vectorint presum;
public:NumArray(vectorint nums) {int n nums.size();presum.resize(n 1);presum[0] 0;for(int i1; in; 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(vectorint 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(vectorint 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不相同
先排序然后可以遍历i0~n-2使用双指针其中lefti1rightn-1二者往内移动注意跳过三个指针重复的情况去掉ai target的情况。
vectorvectorint threeSum(vectorint nums) {vectorvectorint 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(n2)O(n^2)O(n2) https://leetcode.cn/problems/longest-palindromic-substring/ 2. 链表
链表也是一种线性数据结构为了保证链表中元素的连续性一般使用一个指针来找到下一个元素。 特性 任意位置插入元素和删除元素的速度快内存利用率高不会浪费内存链表的空间大小不固定可以动态拓展随机访问效率低时间复杂度为0(N) 链表主要分为以下几类
单向链表包含两个域一个信息域和一个指针域。这个链接指向列表中的下一个节点而最后一个节点则指向一个空值。双向链表也叫双链表双向链表中不仅有指向后一个节点的指针还有指向前一个节点的指针这样可以从任何一个节点访问前一个节点当然也可以访问后一个节点。循环链表中第一个节点之前就是最后一个节点反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。
双指针
删除链表的倒数第 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最后一个节点指向自己然后让倒数第二个节点的nextnull。 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和数组下标进行转换即可实现快速查询。最简单的哈希函数是按照数组长度进行取模运算: indexHashCode(Key)%Array.lengthindex HashCode (Key) \% Array.lengthindexHashCode(Key)%Array.length
但存在哈希冲突解决办法
开放寻址法即后移一位链表法
当哈希冲突过多时就需要扩容操作 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)
vectorint twoSum(vectorint nums, int target) {unordered_mapint, 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_setchar 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:vectorstring letterCombinations(string digits) {vectorstring ans;if(digits.size() 0)return ans;unordered_mapchar, 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(vectorstring ans, string combination, int index, string digits, unordered_mapchar, 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_mapchar, char charmap({{(, )},{{, }},{[, ]}});stackchar 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. 树
满二叉树要求所有分支都是满的 而完全二叉树只需保证最后一个节点之前的节点都齐全即可即满二叉树的部分
存储方式
链表数组注意数组是按满二叉树的位置存放缺失的节点就空出来假设一个父节点的下标是parent那么它的左孩子节点下标就是2×parent 1右孩子节点下标就是2×parent 2 二叉查找树二叉排序树 如果左子树不为空则左子树上所有节点的值均小于根节点的值如果右子树不为空则右子树上所有节点的值均大于根节点的值 左、右子树也都是二叉查找树。
当所有节点的值是有序时二叉查找树就退化了此时需要二叉树的自平衡了。二叉树自平衡的方式有多种如红黑树、AVL树、树堆等
深度优先遍历前序遍历、中序遍历、后序遍历
递归非递归使用栈
####中序遍历
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint ans;func(root, ans);return ans;}void func(TreeNode* root, vectorint 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;queueTreeNode* 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(vectorint 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/
