Python
Java
PHP
IOS
Android
Nodejs
JavaScript
Html5
Windows
Ubuntu
Linux
数组双指针法汇总
指针移动方向 相向夹逼 同向移动 维护的是一个区间还是只是关心指针指向的两个元素 同向移动的 维护一个区间的双指针法即滑动窗口法 2Sum 排序后两头往中间夹逼的双指针法 指针为什么可以不回退 即为什么可以i只 j只 当A i A j
算法
线性表数组
双指针
同类问题汇总
Palindrome Partitioning II
Calculate and maintain 2 DP states pal i j which is whether s i j forms a pal d i which is the minCut for s i n 1 Once w
算法
线性表数组
Remove Duplicates from Sorted Array II
还是原地重写法 保留的条件是A j A i 2 注意后面的下标是i 2 不是j 2 int removeDuplicates int A int n if n lt 3 return n int i 2 for int j 2 j
算法
线性表数组
LeetCode
二分查找题目汇总
1 Search In Rotated Array 2 Search In Rotated Array if A begin A mid begin skip 就可以了 3 Search For a Range 1 标准二分 左右扩展 最坏
算法
二分法
线性表数组
LeetCode
Search in rotated sorted Array
算法框架和普通折半查找一样 主要变量就是begin end mid 考虑的区间也一样 都是 begin mid mid mid end 这三种情况 只是判断条件的部分不同 1 若target A mid 返回mid 2 之后只有两种情况 t
算法
线性表数组
LeetCode
打表法经典2题:小于n的质数和第k个丑数
1 求小于n的所有质数 1 开一个大小为n的bool数组A 下标代表整数 值true代表被mark过 有因子 非素数 2 i 从 2开始到n 1 如果A i 没被mark A i 就是质数 然后mark有A i 因子的数 2 A i 3 A
线性表数组
同类问题汇总
算法
数学
partition算法的3种形态
1 原地重写法 条件是小于轴 不符合交换到后面 int partition1 int a int begin int end if end begin lt 1 return end begin int i begin 1 for int
算法
线性表数组
关于各种merge 的心得
合并两个线性表 包括合并两个有序线性表 两个线性表相加等 第一 遍历两个表的时候 用 代替 空的那一方取0参与计算就可以了 这样就不用后面处理长的那个表剩下来的部分了 第二 对于进位 也放到 里去 这样不用后面处理最后是否有进位了
算法
链表
线性表数组
原地重写法
原地重写法有2种常见应用 1 线性表删除元素 2 线性表partition 基于swap i 代表新数组下一个要写的位置 j 用来遍历原数组 数组分成3部分 0 i 是已经重写的 满足条件的部分 i j 是已经处理 不满足条件的部分 j n
线性表数组
算法
merge sort 一些变种、应用
1 逆序对数目 分治公式 总的逆序对个数 前半部分逆序对个数 后半部分逆序对个数 merge时候每取一次后半部分的数 累加一次前半部分剩余的数的个数 int countInvertion vector
线性表数组
算法
同类问题汇总
排序
4sum
基本的 穷举前面的数的组合 后两个数夹逼法的算法 O n 3 1 排序 2 主循环穷举前两个数的组合 保证数组至少剩下2个数 i 0 i
算法
LeetCode
线性表数组
子串/子段问题总结
1 一般子串问题 求一个串中满足某种条件的子串 1 如果所求子串的条件是一个值 比如sum 则考虑子段问题 注意这样一个性质 子段 前缀差 子段和 前缀和的差 vector
字符串
线性表数组
算法
同类问题汇总