edit from Windows third
ii-none-hello-linux-iii
使用哈希表
,n次循环,每次从哈希表查找target-nums[index0]的数据下标,如没有,则插入当前数据,然后下一次循环:复杂度O(n)
动态规划
遍历数组,对于每一个元素,找出以它结尾的最大子数组,从第一个元素递推,后一个元素的最大子数组于前一个元素最大子数组有关
动态规划
遍历数组,并递推记录当前元素前所有元素中最小的元素,更新最大的差值即可
哈希表 || 异或
使用哈希表减小复杂度或者使用异或特性
对拼消耗法
对于数组中最多的元素,遍历,相同元素加1,不同减1,最后剩下的为多数元素,若计数为0,则更新多数元素
双数组法 || 遍历替换法
数组双索引,一个索引用于遍历,另一个索引用于存储,对于非零元素依次存储,其它元素赋值0 || 依次遍历,零替换第一个非零元素,然后进入下一次循环
消数法
遍历数组,以元素值为索引,置负该索引处元素,说明以这个索引为值的元素出现,最后找出为正的元素的索引即为未出现元素
双指针贪心合拢
指针: 数组第一和最后一个元素, 选择高度小的元素向内合拢
双指针合拢
a<b<c, 选定a,b=a+1, c=size-1, b遍历增大, 则c需要减小,直到b==c
双指针二分法
指针j < i, j要最大即在最右边,i选择j元素右边的最小值,交换ij元素,j指标后快速排序
二分法
1. 一分为2,若在有序数组则直接二分,若在无需数组将无序数组再次一分为2; 或者先找出旋转的下标,分两段数组二分
二分法
用二分法分别找起始位置和结束位置
树回溯
使用循环队列或者数组元素交换确定下一个可选取元素
转置后镜像 || 坐标旋转递推
从内到外一层层旋转
贪心算法
index+1~index+nums[index]内找到下一个能到达最远的下标
快排递推
左边元素排序,然后递推
动态规划
遍历网格,该网格保存路径和,更新加上左边或上边较小的数
三指针
向中间合拢
DFS迭代
展开成一棵树,深度优先遍历,剪枝
DFS回溯
注意不能出现重复位置的元素
哈希表 DFS 前序遍历
将前序分为根节点,左子树(长度由中序中根节点下标决定),右子树,迭代
哈希表去重 O(n)遍历
只有当一个数是连续序列的第一个数的情况下才会进入内层循环->往后查找下一个连续数,保证同一个数只会进入一次循环
O(n)
0将数组分区,每个区域记录最后一个和第一个负数
动态规划
nums[i] = max{ nums[i]+nums[i-2], nums[i-1] }
DFS || 并查集
访问过的标记为'0'
快排分治 || 堆排序
快排中找出下标为numsSize-K的元素即可停止排序
动态规划
matrix[i][j] = 1 + min{ matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j] }
前缀和
每个元素保存其及其之前的元素乘积, 保存其及其之后的乘积
分治 || 二分
横向纵向循环二分 或者从右上角开始一层层拨开,小了往左移, 大了往下移 -> 最优
快排上下车问题
记录在车上的人数的最大值
快慢指针
或者二分
贪心二分 || 动态规划
遍历数组,定义一个数组New,如当前数组元素大于该数组New最后元素,则长度++,否则替换大于该元素的第一个New数组元素,因为替换的相比于原来更小
动态规划
三个维度,持有,非持有冷冻期(卖出当天),非持有非冷冻期
动态规划
dp[i] = min{dp[i-c_j]} + 1 其中c_j为所有面额中的一个 dp[i]表示面额i所需要的最小零钱数
哈希 & 快排分治
使用哈希统计各个元素出现频率, 然后排序
DFS哈希 & 查并集
a/c == a/b * b/c dfs剪枝
排序 & 贪心 & 链表
按后一位排序,对每一个后一位相同的类,根据第一位排序,依次插入链表
背包问题 动态规划
dp[i][j] 表示0-i下标中可以可以凑够和j,优化,可以将dp降为一维
背包问题 动态规划
dp[i][j] = (j-nums[i]>=-sum?dp[i-1][abs(j-nums[i])]:0) + (j+nums[i]<=sum?dp[i-1][j+nums[i]]:0);
哈希表 前缀和
k = sum(0,j) - sum(0,i), 查找是否存在相应的sum(0,i);
双指针求左右边界 || 快排
左右遍历,更新nums[i]<max 的最右边界; 右左遍历...
桶计算频率 贪心
fmax((maxExec - 1) * (n + 1) + maxCount, tasksSize)
单调栈
单调递减栈, 栈顶最小,新元素大于栈顶则弹栈,否则入栈
O(m+n)遍历
无需申请额外空间
快慢指针
fast = fast->next->next; slow = slow->next;
拼接法 || 末端对齐法
AB BA长度相同
迭代 || 递归
1->2->3 -----> 2->1->3 ----> 3->2->1
快慢指针 + 反转链表
快慢指针O(n/2)找到中间节点,反转后半部分链表比较,复原
模拟各位相加
注意最后一个进位
DFS递归 || 快慢指针 || 栈
快指针先走N步,然后快慢指针一起走直到快指针达到链表尾
DFS递归
左右子树置换 O(1)空间复杂度
快慢指针
fast = fast->next->next; slow = slow->next
until they meet each other, then slow = head, fast = fast->next, slow = slow->next
until meet up at the start of the cycle;
assume they mett up at B Node, C Node is where the fast pointer stand when slow pointer first come at cycle_start
then we have:
C + 2 x B = B + n x Z
where Z is the length of the cycle
casue C<Z and B<=Z then C + B = Z
then A + B = C + N x Z +B = (N+1) x Z
which means from Node B, if go another A step, will finally arrive at cycle_start node
哈希表 && 双向链表
对于被查询的数值对移动到链表头部,必要时删除链表尾部节点
堆栈
匹配的括号消除,对于某些情况可直接结束遍历
哈希 || 桶算法 动态规划
滑动窗口,维护当前连续的子串
中心扩展法 || 动态规划 | 暴力剪枝
以一个元素为中心扩展或者两个相邻且相同的元素为中心扩展
DFS回溯
DFS回溯
动态规划 || DFS回溯
(p)+q, len(p)+len(q)=n-1, 能无重复的表示所有组合
字符串哈希 && 排序
还需解决哈希冲突问题
动态规划 && 字符串哈希
dp[i]表示前i+1个字符组成的字符串是否能被拆分
前缀树
apple 拆分为树 a->p->p->l->e
堆栈 括号匹配
注意入栈出栈后顺序颠倒
桶算法 && 动态规划(滑动窗口)
维护一个diff_count, 遍历字符串,加一减一字符变量后更新diff_count
中心扩展法
如题58_5
DFS
中序遍历,根节点在中间
DFS
左树按中序遍历,右数按 "右根左"遍历
DFS
迭代
DFS
迭代,左右子树互换
DFS 动态规划
求树深度,依次遍历每个节点作为路径的最高点,左右子树深度之和为当前的直径
DFS+剪枝
迭代,左右子树值相加,有一个子树为空时,直接延续非空子树返回
动态规划 || 迭代
dp[i] = dp[j-1]*dp[i-j], 1<=j<=i
DFS || 中序遍历
DFS维护左右上限 || 中序遍历后应该是递增
BFS || 队列
BFS队列迭代
DFS
记录路径
DFS && 动态规划
打家劫舍动态规划类问题在于向下一个节点传递其前第1个节点为止的最大值a
和本节点为止的最大值b
,本节点为止的最大值
动态规划方程为b = max{a, pre_a + val}
DFS 前缀和 哈希表
前缀和
反序中序遍历 DFS
右-根-左遍历累加
动态规划
dp[i] = dp[i-1] + dp[i-2]
记忆化搜索
每个栈节点保存此前的最小值
动态规划
对于奇数,其为1的位数位前一个偶数的1位数加1,偶数等于其1/2的偶数左移1位,故1的位数相等
按位与 位运算
int mask = 1 << i, 0<= i <31
动态规划
dp[i][j] = dp[i-1][j] + dp[i][j-1]
拓扑排序
有向无环图,若最后数目不为节点数大小,则存在环
动态规划 || BFS剪枝
f(i) = 1 + min{f(i-j^2)}, 1 <= j <= floor(sqrt(i));
二分 && 寻找第k大个数
每次排除k/2个数
归并排序
k = (k/2)个链表对和(k%2)个单独链表,转化为merge_two_lists问题
动态规划
如[3,1,5,8]扩展为[1,3,1,5,8,1],计算长度从3开始的dp[i][j] = max{val[i]*val[k]*val[j]+dp[i][k]+dp[k][j]}(i<k<j)
动态规划
第一层: 是否为'*', 第二层: '*'前面的字符是否相等,不等则舍去两项, 否则考虑s的前一项是否匹配当前p
动态规划 || 堆栈
将字符串下标存入栈,括号匹配,或者动态规划
双指针 || 单调栈
左右指针合拢,left_max和left, right_max与right比较, 绝对当前是否在内部
动态规划
1、状态定义:
dp[i][j]表示word1的前i个字母转换成word2的前j个字母所使用的最少操作。
2、状态转移:
i指向word1,j指向word2
若当前字母相同,则dp[i][j] = dp[i - 1][j - 1];
否则取增删替三个操作的最小值 + 1, 即:
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1。
滑动窗口 桶算法
注意中间字符的替换
单调栈
从暴力法引申,某个下标i的元素高度为该矩形高度,左右扩展,找到该矩形的左边界和右边界,边界由单调递增栈得到
单调栈
同题95_84 每层累加,若为0则清0,否则累加,对每层求最大的矩形,高度即为累加值
DFS 动态规划
深度遍历,计算每个点作为最高节点的最大路径和,更新节点值为该节点和左右子树中其中一个的最大和
双端队列 单调队列
建立双向队列(队尾可弹出),若窗口中移除的元素等于队列头元素,则弹出队列头;循环剔除比新元素小的队尾元素,插入新元素,每一次循环结束的队列头即是该次的最大元素。
前序遍历 | xx遍历
左右子树用NULL表示
回溯 && 剪枝
先得到需要删除的左右括号数,依次删除检查合法性,并剪枝