企业网站建设怎么选择空间,网站排名消失,互联网网站案例,嘉兴北京网站建设算法模板总结滑动窗口双指针算法数组相关合并两个有序数组左右指针技巧快慢指针技巧字符串相关左右指针反转字符串问题快慢指针替换空格字符问题链表相关快慢双指针删除链表的倒数第N个节点链表相交环形链表链表操作几数之和两数之和四个数组的四数之和三数之和同一数组中四数之…
算法模板总结滑动窗口双指针算法数组相关合并两个有序数组左右指针技巧快慢指针技巧字符串相关左右指针反转字符串问题快慢指针替换空格字符问题链表相关快慢双指针删除链表的倒数第N个节点链表相交环形链表链表操作几数之和两数之和四个数组的四数之和三数之和同一数组中四数之和KMP字符串前缀表如何计算前缀表使用next数组匹配栈定义常见问题括号匹配删除字符串中所有相邻重复项逆波兰表达式队列普通队列定义双端队列优先级队列大小顶堆经典问题前k个高频元素单调队列经典问题求滑动窗口最大值二叉树二叉树的前序中序后序遍历递归法非递归法迭代法层序遍历输出ListListT 类型结果求二叉树的属性求是否对称求最大深度求最小深度求有多少个节点判断二叉树是否平衡求从根节点到叶子节点的所有路径左叶子之和求左下角的值最后一行最左边路径求和二叉树的修改与构造翻转二叉树构造二叉树合并两个二叉树求二叉搜索树BST的属性判断是不是二叉搜索树BST的最小绝对差BST的众数BST转为累加树二叉树公共祖先问题BST的修改和构造BST中插入BST删除单个节点BST修剪可能删除多个改变rootMapmap.getOrDefault(key,默认值)map.put(key,value)map.containsKey(key); //判断是否包含指定的键值map.get(key); //获取指定键所映射的值map.remove(key)map.entrySet(); 遍历mapSetset.add()set.contains(key)set.clear()动态数组List list操作List转换为数组一维int型数组不可以list.toArray()数组转为List当题目要求返回ListT res 时怎么每次向列表头部插入LinkedList可以直接向index位置插入val可变字符串Char[]转回String只使用常量额外空间 位运算时间复杂度前缀树回溯算法所有排列-组合-子集问题组合排列子集切割问题棋盘问题N皇后填数独安排行程贪心算法贪心常识题455. 分发饼干1005. K 次取反后最大化的数组和860. 柠檬水找零贪心找规律题376. 摆动序列738. 单调递增的数字两个维度权衡问题135. 分发糖果406. 根据身高重建队列区间贪心452. 用最少数量的箭引爆气球435. 无重叠区间55. 跳跃游戏二加油站监控二叉树状态动态规划动规基础dp五部曲746. 使用最小花费爬楼梯343.整数拆分96. 不同的二叉搜索树背包问题01背包物品只能用一次416. 分割等和子集1049. 最后一块石头的重量2完全背包物品可以重复使用求组合494. 目标和求排列377. 组合总和139. 单词拆分求最小数打家劫舍系列198. 打家劫舍213. 打家劫舍II337. 打家劫舍III股票系列121. 买卖股票的最佳时机122. 买卖股票的最佳时机II123. 买卖股票的最佳时机III188.买卖股票的最佳时机IV309. 含冷冻期问题714. 含手续费子序列问题编辑距离子序列不连续1035. 不相交的线子序列连续编辑距离115. 不同的子序列72. 编辑距离回文647. 回文子串单调栈42. 接雨水84. 柱状图中最大的矩形单例模式饿汉模式懒汉模式简单工厂定义抽象产品类同时定义抽象方法定义具体的产品类统一继承抽象类定义产品具体工厂*使用工厂类排序相关快速排序O(nlgn)O(nlgn)O(nlgn)归并排序工具IntStream、LongStream 和 DoubleStream创建IntStream流(IntStream中的静态方法of / builder/ range / rangeClosed / generate / iterate)filter() 方法过滤出符合条件的数据map()方法对流中所有元素执行某个修改操作mapToObj / mapToLong / mapToDouble / asLongStream / asDoubleStreamforEach / forEachOrdereddistinct()方法sorted() 方法skipsum / min / max / count / average / summaryStatisticsboxed()toArray()例子滑动窗口
摘自labuladong算法小抄
滑动窗口一般用来解决寻找子串问题
int left 0, right 0;while (right s.size()) {// 增大窗口window.add(s[right]);right;while (window needs shrink) {// 缩小窗口window.remove(s[left]);left;}
}
双指针算法
数组相关
合并两个有序数组
设置两个指针p1p2分别指向数组头部再设置一个指针p3指向新数组头部 分别比较p1 p2的大小小的指针前移且赋值于p3
左右指针技巧
就是两个指针相向而行或者相背而行
两数相加和target (有序数组) 左右指针分列两端和target ⇒ right–反之left和target ⇒ 记录并左右同时收缩直到left ! right
快慢指针技巧
使用一快一慢同向指针
在有序数组中去重 我们让慢指针 slow 走在后面快指针 fast 走在前面探路找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。这样就保证了 nums[0…slow] 都是无重复的元素当 fast 指针遍历完整个数组 nums 后nums[0…slow] 就是整个数组去重之后的结果 原地删除/修改数组 如果 fast 遇到值为 val 的元素则直接跳过否则就赋值给 slow 指针并让 slow 前进一步。
字符串相关
左右指针
反转字符串问题
左右指针从两端向中间移动保持leftright
快慢指针
替换空格字符问题
慢指针slow0快指针遍历字符串 当str[fast]! 时快慢指针同时前移赋值注意慢指针要在每个单词前加上空格(除了第一个)
private char[] deleteSpace(char[] str){int slow 0;for(int fast 0; faststr.length; fast){if(str[fast] ! ){ //只处理非空格if(slow 0){str[slow] ;//额外加上单词间的空格}while(fast str.length str[fast] ! ){str[slow] str[fast];}}}char[] newStr new char[slow];for(int i 0; i slow; i){newStr[i] str[i];}return newStr;
}链表相关
快慢双指针
删除链表的倒数第N个节点
快指针先前进n步之后快慢指针同时前进当快指针指向最后一个节点时慢指针的下一个节点就是要删除的点
链表相交
快指针在长链表上前进长链表长度-短链表长度步慢指针指向短链表头部之后只要快!慢就同时前进
环形链表
快慢指针快指针一次两步慢指针一次一步如果fastslow说明有环此时一个指针放在head一个指针在相交处每次向前同时移一步相交处即为入环的第一个节点
链表操作
链表操作一般都要设置一个虚拟头节点这样不用特殊处理原头节点 特别是操作后还需要返回新的头节点时
几数之和
两数之和
使用HashMap存储数字和对应的idx 依次遍历数组如果存在keytarget-num则返回当前num的idx和找到的key的idx
四个数组的四数之和
使用HashMap存储数字和与对应和出现的次数 先遍历前两个数组存储每一个和与出现的次数 之后遍历后两个数组找map里是否有target-(num3num4) 有的话对应的次数
for(int num1 : nums1){for(int num2: nums2){int temp num1num2;map.put(temp, map.getOrDefault(temp, 0) 1);}
}
for(int num3 : nums3){for(int num4 : nums4){int temp num3num4;if(map.containsKey(0-temp)){res map.get(0-temp);}}
}三数之和 答案中不能包涵重复的三元组 不需要返回原来排序前的idx 现将数组排序然后外层for循环i从0开始同时定义左右指针lefti1right末尾之后保持leftright状态左右逼近 此时还需要去重
public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);ListListInteger res new ArrayList();for(int i 0; inums.length-2; i){int left i1, right nums.length-1;if(nums[i] 0) break; //剪枝if(i0 nums[i] nums[i-1]) continue; //去重awhile(left right){int temp nums[i] nums[left] nums[right];if(temp 0){ListInteger path new ArrayList();path.add(nums[i]);path.add(nums[left]);path.add(nums[right]);res.add(path);// 去重bc同时不会出现 当遇到[0,0,0,0]时,不记录一组解 的情况while(leftright nums[right-1] nums[right]) right--;while(leftright nums[left1] nums[left]) left;left;right--; //同时收缩}else if(temp 0){left;}else{right--;}}}return res;
}同一数组中四数之和 答案中不能包涵重复的三元组 不需要返回原来排序前的idx 和三数差不多 abcdtarget 这里还要多去重一个b
for(int i 0; i nums.length-3; i){for(int j i1; j nums.length-2; j){if(nums[i] target nums[i] 0) break;if(i 0 nums[i] nums[i-1]) continue; //去重aif(j i1 nums[j] nums[j-1]) continue; //去重bint left j1, right nums.length-1;while(left right){int temp nums[i] nums[j] nums[left] nums[right];if(temp target){left;}else if(temp target){right--;}else{ListInteger path new ArrayList();path.add(nums[i]);path.add(nums[j]);path.add(nums[left]);path.add(nums[right]);res.add(path);while(leftright nums[right-1] nums[right]) right--;while(leftright nums[left1] nums[left]) left; //去重cdleft;right--;}}}
}如果target 0这里不能再剪枝nums[i]target因为还有可能越加越小 可以if(nums[i] target nums[i] 0) break; KMP字符串
KMP算法是一个快速查找匹配串的算法作用如何快速在「原字符串」中找到「匹配字符串」。leetcode28题 如果逐一循环套循环的朴素解法时间复杂度O(m∗n)O(m*n)O(m∗n)而KMP算法的复杂度为O(mn)O(mn)O(mn)。 KMP 能在「非完全匹配」的过程中提取到有效信息进行复用以减少「重复匹配」的消耗。不用每一次都从头再次循环查找
举例
此时’a’ 和‘f’匹配不上朴素解法会从原串的匹配起始位置1的’b‘开始重新和匹配串匹配。而KMP不会重新匹配
先了解什么是next数组
前缀表
next数组其实是一个前缀表用来回退的它记录了模式串与主串(文本串)不匹配的时候模式串应该从哪里开始重新匹配。 什么是前缀表记录下标i之前包括i的字符串中有多大长度的相同前缀后缀。 刚才的例子中KMP会利用前缀表从‘e’开始继续匹配。匹配串中相同前缀的后面
如何计算前缀表 在计算出前缀表后如何利用前缀表跳转 模式串与前缀表对应位置的数字表示的就是下标i之前包括i的字符串中有多大长度的相同前缀后缀。
很多KMP算法的时间都是使用next数组来做回退操作那么next数组与前缀表有什么关系呢 next数组就可以是前缀表但是很多实现都是把前缀表统一减一右移一位初始位置为-1之后作为next数组。 具体实现中next数组既可以就是前缀表也可以是前缀表统一减一右移一位初始位置为-1。
使用next数组匹配
以下我们以前缀表统一减一之后的next数组来做演示。 有了next数组就可以根据next数组来 匹配文本串s和模式串t了。
class Solution {
public:void getNext(int* next, const string s) {int j -1;next[0] j;for(int i 1; i s.size(); i) { // 注意i从1开始while (j 0 s[i] ! s[j 1]) { // 前后缀不相同了j next[j]; // 向前回退}if (s[i] s[j 1]) { // 找到相同的前后缀j;}next[i] j; // 将j前缀的长度赋给next[i]}}int strStr(string haystack, string needle) {if (needle.size() 0) {return 0;}int next[needle.size()];getNext(next, needle);int j -1; // // 因为next数组里记录的起始位置为-1for (int i 0; i haystack.size(); i) { // 注意i就从0开始while(j 0 haystack[i] ! needle[j 1]) { // 不匹配j next[j]; // j 寻找之前匹配的位置}if (haystack[i] needle[j 1]) { // 匹配j和i同时向后移动j; // i的增加在for循环里}if (j (needle.size() - 1) ) { // 文本串s里出现了模式串treturn (i - needle.size() 1);}}return -1;}
};
参考题解 链接https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/575568/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/
栈
定义
StackT st new Stack();
st.push();
st.pop();
st.peek();
st.isEmpty();常见问题
括号匹配
设置一个栈存放左括号遇到右括号时弹出匹配此时如果栈为空也是false最后栈中无元素为true
删除字符串中所有相邻重复项
设置栈存放字符如果和现有栈顶元素重复则弹出
逆波兰表达式
把所有数字存在栈中遇到符号就弹出两个数做运算再把结果压回栈内
队列
普通队列定义
QueueT que new LinkedList();
que.offer();
que.poll();
que.peek();
que.size();双端队列
DequeT que new LinkedList();
que.add(val);
// 队头出队
que.poll();
// 队尾出队
que.removeLast();
// 获取队头元素
que.peek()
// 获取队尾元素
que.getLast();优先级队列大小顶堆
QueueT que new PriorityQueue((x,y)-(y-x)); //大顶堆
QueueT que new PriorityQueue(); //小顶堆经典问题
前k个高频元素
优先级队列的排序规则可以自定义如下存储数组根据数组第二个元素排序
Queueint[] que new PriorityQueue((pair1,pair2)-(pair2[1]-pair1[1]));//定义大根堆根据次数排序
for(Map.EntryInteger,Integer entry : map.entrySet()){que.offer(new int[]{entry.getKey(), entry.getValue()}); //存储[num, cnt]数组
}单调队列
经典问题
求滑动窗口最大值
如何求窗口内的最大值如果窗口过大每次求最大值会超时。 如果使用大顶堆优先级队列窗口是移动的而大顶堆每次只能弹出最大值我们无法移除其他数值大顶堆不能动态维护滑动窗口里面的数值。所以不能用大顶堆 因此需要一个单调队列随着窗口的移动队列也一进一出每次移动之后队列告诉我们里面的最大值是什么。
怎么每次移除窗口最左端元素而不是最大最小值呢
其实队列没有必要维护窗口里的所有元素只需要维护有可能成为窗口里最大值的元素就可以了同时保证队列里的元素数值是由大到小的。 设计单调队列的时候pop和push操作要保持如下规则
pop(value)如果窗口移除的元素value等于单调队列的出口元素那么队列弹出元素否则不用任何操作push(value)如果push的元素value大于入口元素的数值那么就将队列入口的元素弹出直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则每次窗口移动的时候只要问que.front()就可以返回当前窗口的最大值。 自定义数据结构实现单调队列
class MyQueue {DequeInteger deque new LinkedList();//弹出元素时比较当前要弹出的数值是否等于队列出口的数值如果相等则弹出//同时判断队列当前是否为空void poll(int val) {if (!deque.isEmpty() val deque.peek()) {deque.poll();}}//添加元素时如果要添加的元素大于入口处的元素就将入口元素弹出//保证队列元素单调递减//比如此时队列元素3,12将要入队比1大所以1弹出此时队列3,2void add(int val) {while (!deque.isEmpty() val deque.getLast()) {deque.removeLast();}deque.add(val);}//队列队顶元素始终为最大值int peek() {return deque.peek();}
}二叉树
一般遍历整个树的没有返回值遍历单条路径的有返回值
二叉树的前序中序后序遍历
递归法
前序
ListInteger res new ArrayList();
public ListInteger preorderTraversal(TreeNode root) {//递归方法preOrder(root);return res;
}private void preOrder(TreeNode root){if(root null) return;res.add(root.val); //根preOrder(root.left); //左preOrder(root.right); //右
}非递归法迭代法
用栈存储类似递归的结果
前序后序类似
ListInteger res new ArrayList();
public ListInteger preorderTraversal(TreeNode root) {//迭代法if(root null) return res;StackTreeNode st new Stack();st.push(root);while(!st.isEmpty()){TreeNode temp st.pop();res.add(temp.val);if(temp.right ! null){ //右st.push(temp.right);}if(temp.left ! null){ //左st.push(temp.left);}}return res;
}中序
public ListInteger inorderTraversal(TreeNode root) {ListInteger res new ArrayList();//非递归法StackTreeNode st new Stack();if(root null) return res;TreeNode cur root;while(cur ! null || !st.isEmpty()){if(cur ! null){st.push(cur);cur cur.left;}else{if(!st.isEmpty()){cur st.pop();res.add(cur.val);cur cur.right;}}}return res;
}层序遍历输出ListListT 类型结果
使用que.size()来循环每层
ListListInteger res new ArrayListListInteger();
if(root null) return res;
QueueTreeNode q new LinkedList();
q.add(root);
while(!q.isEmpty()){ListInteger itemRes new ArrayList();int len q.size();while(len-- 0){TreeNode cur q.poll();itemRes.add(cur.val);if(cur.left ! null) q.add(cur.left);if(cur.right ! null) q.add(cur.right);}res.add(itemRes);
}
return res;求二叉树的属性
一般是中序通过递归函数的返回值计算
求是否对称
后序递归的检查每个节点的左右孩子节点是否相同
求最大深度
后序求左子树右子树的最大深度root的深度max(left, right)1
private int getMaxDep(TreeNode root){if(root null) return 0;int depL getMaxDep(root.left);int depR getMaxDep(root.right);return Math.max(depL, depR)1;
}求最小深度
后序但此时不能求左右孩子的Math.min()1因为只有左孩子或者只有右孩子时强制为单边1只有左右孩子齐全时才和最大深度一样。
private int getMinDep(TreeNode root){if(root null) return 0;int leftL getMinDep(root.left);int rightL getMinDep(root.right);if(root.left null) return rightL 1;if(root.right null) return leftL 1;return Math.min(leftL, rightL) 1;
}求有多少个节点
后序先求左右子树的节点数root leftright1
判断二叉树是否平衡
后序递归判断每个节点的左右孩子的最大高度差是否为1
求从根节点到叶子节点的所有路径
前序方便让父节点指向子节点涉及回溯处理根节点到叶子的所有路径 定义ListInteger path;边界条件当root为叶子结点时把path加入res集合return 之后根path.add(root.val) 递归处理左右递归后需要加 path.remove(path.size()-1) 做回溯
左叶子之和
后序必须三层约束条件来判断是否是左叶子
if(root.left null root.right null flag true){return root.val;
}
int leftSum sumLeaves(root.left, true);
int rightSum sumLeaves(root.right, false);return leftSum rightSum;求左下角的值最后一行最左边
还要再加一层深度的判断此时当只有右孩子时不一定最左边的值是左叶子
private void leftValue(TreeNode root, boolean flag, int curDep){if(root null) return;if(root.left null root.right null flag true){if(curDep maxDep){res root.val;maxDep curDep;}}if(root.left null){leftValue(root.right, true, curDep1);}else{leftValue(root.left, true, curDep1);leftValue(root.right, false, curDep1);}
}路径求和
是否有从根节点到叶子的路径之和等于目标和 后序先判断
boolean leftPath pathSum(root.left, curSum);
boolean rightPath pathSum(root.right, curSum);
return leftPath || rightPath;二叉树的修改与构造
一定是前序先构造根节点
翻转二叉树
前序交换左右孩子
构造二叉树
前序要点都是先从数组中找到根的位置然后递归从根前数组和根后数组建立 root.left 和 root.right
合并两个二叉树
前序同时操作两个树的节点注意合并的规则
求二叉搜索树BST的属性
中序利用BST中序为升序数组的特性
判断是不是二叉搜索树
后序递归判断每个节点的前驱节点和后继节点是不是位于当前root的两边
// 寻找根的前驱节点
private TreeNode findPre(TreeNode root){TreeNode pre root.left;TreeNode cur pre.right;while(cur ! null){pre cur;cur cur.right;}return pre;
}//寻找根的后继节点
private TreeNode findLast(TreeNode root){TreeNode pre root.right;TreeNode cur pre.left;while(cur ! null){pre cur;cur cur.left;}return pre;
}BST的最小绝对差
中序BST中序遍历后为升序数组用一个指针TreeNode pre; 指向每次root的前一个遍历的节点 递归更新差值
public void traversal(TreeNode root){if(root null) return;traversal(root.left);if(pre ! null){res Math.min(res, root.val-pre.val);}pre root;traversal(root.right);
}BST的众数
中序BST中序遍历后为升序数组重复的数字都在一起可以记录cnt次数来判断是否是众数用一个指针TreeNode pre; 指向每次root的前一个遍历的节点 但要注意一个特殊情况树中每个节点都出现1次都是众数
private void inorder(TreeNode root){if(root null) return;inorder(root.left);if(pre ! null){if(pre.val root.val){curCnt;}else{curCnt 1;}}pre root;if(curCnt maxCnt){maxCnt curCnt;res new ArrayList();res.add(root.val);}else if(curCnt maxCnt){res.add(root.val);}inorder(root.right);
}BST转为累加树
遍历顺序后中左用一个指针TreeNode pre; 指向每次root的前一个遍历的节点代表要加的值
二叉树公共祖先问题
后序自底向上如果root的左右子树中分别能找到 TreeNode p, TreeNode q那么root就为公共祖先。特殊情况rootp/q此时root直接就是公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null || root p || root q) return root;TreeNode l lowestCommonAncestor(root.left, p, q); //递归向左子树找p qTreeNode r lowestCommonAncestor(root.right, p, q); //递归向右子树找p qif(l null r null){return null;}else if(l null){return r;}else if(r null){return l;}else{return root;}
}BST的修改和构造
BST中插入
先利用BST规则进行左右子树的查找当查到rootnull时进行插入新节点
if(root null){return new TreeNode(val);
}
if(root.val val){root.left insertIntoBST(root.left, val);
}else if(root.val val){root.right insertIntoBST(root.right, val);
}BST删除单个节点
前序。如果删除的节点时叶子结点直接删除如果是非叶子结点同时左右子树俱在需要把root的右子树放在root的前驱右边把root的左子树覆盖为新的root节点
if(root.val key){if(root.left null root.right null){return null;}else if(root.left ! null root.right null){return root.left;}else if(root.left null root.right ! null){return root.right;}else{ //把root的右子树放在root的前驱右边把root的左子树覆盖为新的root节点TreeNode temp root.left; //前驱while(temp.right ! null){temp temp.right;} temp.right root.right;root root.left;return root;}
}BST修剪可能删除多个改变root
前序需要递归的删除多个甚至是改变当前root
public TreeNode trimBST(TreeNode root, int low, int high) {if(root null) return null;if(root.val low){return trimBST(root.right, low, high); //把右子树重新做为根来求trinBST}else if(root.val high){return trimBST(root.left, low, high); //把左子树重新当根}else{root.left trimBST(root.left, low, high);root.right trimBST(root.right, low, high);}return root;
}Map
map.getOrDefault(key,默认值)
Map.getOrDefault(key默认值)
Map中会存储一一对应的key和value。 如果 在Map中存在key则返回key所对应的的value。 如果 在Map中不存在key则返回默认值。
可以使用 map.getOrDefault(key, new ArrayList()); 来初始化
map.put(key,value)
map.containsKey(key); //判断是否包含指定的键值
map.get(key); //获取指定键所映射的值
map.remove(key)
map.entrySet(); 遍历map
//使用增强for遍历
for (Map.EntryString, String s : map.entrySet()) {//①可以直接输出 s 得到键值对System.out.println(s);//②也可以使用Entry类的方法 单独取出 键和值String keys.getKey(); //获取键String values.getValue(); //获取值System.out.println(key value); //输出键值
}Set
set.add()
set.contains(key)
set.clear()
动态数组List list
操作
List list new ArrayList();
list.add()
list.get(i)
list.remove(idx)List转换为数组一维int型数组不可以list.toArray()
List变String[]String[] ans res.toArray(new String[]{});
二维list转数组res.toArray(new int[res.size()][]);
数组转为List
将数组转化为list集合: Arrays.asList(对象型数据的数组)
当题目要求返回ListT res 时怎么每次向列表头部插入
把List声明为LinkedList LinkedListListInteger res new LinkedList(); 此时有方法res.addFirst() 实现每次头插入 最后仍可直接返回 res
LinkedList可以直接向index位置插入val
LinkedListint[] que new LinkedList();
que.add(index, val)可变字符串
如果字符串需要频繁修改/追加StringBuilder
StringBuilder sb new StringBuilder();
sb.append()//追加char c或者StringBuilder sb或String
sb.toString() //转换回String
sb.get(i)
sb.deleteCharAt(sb.length()-1);Char[]转回String
return new String(char[]);
只使用常量额外空间 位运算
交换律a ^ b ^ c a ^ c ^ b任何数于0异或为任何数 0 ^ n n相同的数异或为0: n ^ n 0
var a [2,3,2,4,4]
2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 0 ^ 0 ^3 3判断数偶 奇数 x % 2 1 偶数x % 2 0两数取平均(除2): mid (leftright)/2 等价于 mid (leftright) 1清除最低位的1: x x(x-1)得到最低位的1: n x -x清零: x~xa^b 是无进制相加 ab是进位信息与运算 可获取二进制数字 num 的最右一位num 1 可以获得最右边一位无符号右移 可获取 num 所有位的值num 1;
时间复杂度
时间复杂度 O(logN) 考虑使用二分法
归并排序、快速排序 O(NlogN)
链表在O(nlgn)时间和常数空间内排序 归并排序最佳且稳定 找中间点用快慢指针 左半部分排序 把mid.nextnull,这样直接传入head
前缀树
包含三个单词 “sea”,“sells”,“she” 的 Trie
总结出 Trie 的几点性质
Trie 的形状和单词的插入或删除顺序无关也就是说对于任意给定的一组单词Trie 的形状都是唯一的。查找或插入一个长度为 L 的单词访问 next 数组的次数最多为 L1和 Trie 中包含多少个单词无关。Trie 的每个结点中都保留着一个字母表这是很耗费空间的。如果 Trie 的高度为 n字母表的大小为 m最坏的情况是 Trie 中还不存在前缀相同的单词那空间复杂度就为 O(mn)O(m^{n})O(mn)
最后关于 Trie 的应用场景希望你能记住 8 个字一次建树多次查询。
class Trie {class TireNode {private boolean isEnd;TireNode[] next;public TireNode() {isEnd false;next new TireNode[26];}}private TireNode root;public Trie() {root new TireNode();}public void insert(String word) {TireNode node root;for (char c : word.toCharArray()) {if (node.next[c - a] null) {node.next[c - a] new TireNode();}node node.next[c - a];}node.isEnd true;}public boolean search(String word) {TireNode node root;for (char c : word.toCharArray()) {node node.next[c - a];if (node null) {return false;}}return node.isEnd;}public boolean startsWith(String prefix) {TireNode node root;for (char c : prefix.toCharArray()) {node node.next[c - a];if (node null) {return false;}}return true;}
}回溯算法 所有排列-组合-子集问题
无论是排列-组合还是子集问题都是从序列 nums 中以给定规则取若干元素解集不重复有以下几种
形式一、元素无重不可复选即 nums 中的元素都是唯一的每个元素最多只能被使用一次这也是最基本的形式。 以组合为例如果输入 nums [2,3,6,7]和为 7 的组合应该只有 [7]。 此时不需要树层去重如果是组合和子集需要树枝去重排列则不需要
形式二、元素可重不可复选即 nums 中的元素存在重复每个元素最多只能被使用一次。 以组合为例如果输入 nums [2,5,2,1,2]和为 7 的组合应该有两种 [2,2,2,1] 和 [5,2]。 如果元素顺序可以改变那么可以先把nums排序这样相同的数字排在一起 然后使用i0 nums[i] nums[i-1] used[i-1]false 来树层去重。 如果是组合和子集需要树枝去重排列则不需要 以40题组合总和三为例
class Solution {ListListInteger res new ArrayList();ListInteger path new ArrayList();boolean[] used; //标记数组private int[] candidates;private int target;public ListListInteger combinationSum2(int[] candidates, int target) {this.candidates candidates;this.target target;used new boolean[candidates.length];Arrays.sort(candidates);backtracking(0, 0);return res;}private void backtracking(int idx, int sum){if(sum target) return;if(sum target){res.add(new ArrayList(path));return;}for(int i idx; i candidates.length; i){if(i 0 candidates[i] candidates[i-1] used[i-1] false) continue; //去重path.add(candidates[i]);sum candidates[i];used[i] true;backtracking(i1, sum);used[i] false;sum - candidates[i];path.remove(path.size()-1);}}
}但如果nums顺序不能改变时我们需要在每次横向遍历的操作之前设置一个MapInteger, Integer map 查看当前层是否已经使用过重复的数字不能再使用used[i-1] false 因为两个相同数字可能不相邻。
组合
需要树枝去重当遍历到叶子结点时返回结果。
for(int i idx; i candidates.length; i){.....backtracking(idx1);//树枝去重
}排列
不需要树枝去重遍历到叶子结点时返回结果
for(int i 0; i candidates.length; i){.....backtracking();
}子集
需要树枝去重每次递归都记录一下结果结果集在树枝中每个节点上而不只在叶子结点。
private void backtracking(int idx){res.add(new ArrayList(path)); //每次记录结果if(idx nums.length){return;}for(int i idx; i nums.length; i){...backtracking(i1);...}
}切割问题
遍历切割第几个位置idx 131.分割回文串
class Solution {ListListString res new ArrayList();ListString path new ArrayList();String s;public ListListString partition(String s) {this.s s;backtracking(0);return res;}private void backtracking(int idx){if(idx s.length()){ //切到最后res.add(new ArrayList(path));return;}for(int i idx; is.length(); i){ //往后切横向遍历每一个切割位置String subStr s.substring(idx, i1);if(isSimiliar(subStr)){path.add(subStr);}else{continue;}backtracking(i1); path.remove(path.size()-1);}}private boolean isSimiliar(String str){ //判断str是否是回文串if(str.length() 1) return true;int left 0, right str.length()-1;while(left right){if(str.charAt(left) ! str.charAt(right)){return false;}left;right--;}return true;}
}棋盘问题
N皇后 递归的深度是棋盘的高度每次操作一行for循环的宽度是棋盘的宽度 如何递归表示棋盘 使用char[][] checkbox; 来存储棋盘 51.N皇后 输入n 4 输出[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]] class Solution {ListListString res new ArrayList();ListInteger path new ArrayList();private int n;char[][] checkbox;public ListListString solveNQueens(int n) {this.n n;checkbox new char[n][n];for(char[] line : checkbox){Arrays.fill(line, .);}backtracking(0);return res;}private void backtracking(int row){if(row n){//存入一个答案res.add(new ArrayList(chars2List(checkbox)));return;}for(int col 0; col n; col){if(isValid(row, col)){checkbox[row][col] Q;backtracking(row 1);checkbox[row][col] .;}}}private boolean isValid(int row, int col){for(int r 0; r row; r){if(checkbox[r][col] Q) return false; // 同列}for(int r row-1, c col-1; r0 c0; r--, c--){if(checkbox[r][c] Q) return false; //左对角线}for(int r row-1, c col1; r0 c n; r--, c){if(checkbox[r][c] Q) return false; //右对角线}return true;}private ListString chars2List(char[][] checkbox){ListString ans new ArrayList();for(char[] line : checkbox){String temp new String(line);ans.add(temp);}return ans;}
}填数独
37.解数独 前面的递归都是一维递归n皇后每行递归时只需要确定一个 而解数独是二维递归每一个位置都要放一个数字并检查数字是否合法解数独的树形结构要比N皇后更宽更深
private boolean backtracking(){
for(int row 0; row 9; row){ //还需要加上行来遍历每个位置for(int col 0; col 9; col){if(board[row][col] .){for(int num 1; num 9; num){if(isValid(row, col, num)){board[row][col] (char)(num 0);if(backtracking()) return true;board[row][col] .;}}return false;}}
}
return true;安排行程
332.重新安排行程 如何存储遍历的行程机票MapString, MapString, Integer map new HashMap(); //{from : {to1:cnt1, to2:cnt2, ...}} 如何使结果的行程按字典序升序MapString, Integer temp new TreeMap(); // 实现按字典序排序 使用TreeMap
class Solution {ListString res new ArrayList();MapString, MapString, Integer map new HashMap(); //{from : {to1:cnt1, to2:cnt2, ...}}ListListString tickets;public ListString findItinerary(ListListString tickets) {this.tickets tickets;for(ListString t : tickets){MapString, Integer temp;String from t.get(0);if(map.containsKey(from)){temp map.get(from);temp.put(t.get(1), temp.getOrDefault(t.get(1), 0)1);}else{temp new TreeMap(); // 实现按字典序排序temp.put(t.get(1), 1);}map.put(from, temp);}res.add(JFK);backtracking();return res;}private boolean backtracking(){if(res.size() tickets.size()1){return true;}String from res.get(res.size()-1);if(map.containsKey(from)){for(Map.EntryString, Integer tolist : map.get(from).entrySet()){int cnt tolist.getValue();if(tolist.getValue() 0){res.add(tolist.getKey());tolist.setValue(cnt-1);if(backtracking()) return true;tolist.setValue(cnt);res.remove(res.size()-1);}}}return false;}
}贪心算法
贪心常识题
455. 分发饼干 对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。 两个数组分别排序然后用小饼干喂小胃口
for(int i 0; i s.length; i){if(cnt g.length g[cnt] s[i]) cnt;
}1005. K 次取反后最大化的数组和 给你一个整数数组 nums 和一个整数 k 按以下方法修改该数组选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。重复这个过程恰好 k 次。可以多次选择同一个下标 i 。以这种方式修改数组后返回数组 可能的最大和 。 把数组按绝对值大小从大到小排序然后遍历时遇到负数取反。 如果还有多的k那么全用在最小的数字上
nums IntStream.of(nums).boxed().sorted((o1,o2) - Math.abs(o2)-Math.abs(o1)).mapToInt(Integer::intValue).toArray();860. 柠檬水找零 找零钱问题 给你一个整数数组 bills 其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零返回 true 否则返回 false 。 遇到5块钱five 遇到10块钱ten five– 遇到20块钱首先用10元找零ten– five– 没有10元的话five -3
贪心找规律题
376. 摆动序列 给你一个整数数组 nums 返回 nums 中作为 摆动序列 的 最长子序列的长度 。 将数字按大小画出来摆动序列应该数字在峰顶峰底交替 使用dp动态规划dp[i][0]:第i个数在山谷的最长子序列长度, dp[i][1]:第i个数在山峰的最长子序列长度
由于摆动子序列可以不连续所以dp数组递归赋值时需要每次都往前从头找一次来循环赋值
for(int i 1; i nums.length; i){ // 递归赋值dpdp[i][0] dp[i][1] 1; //i 自己可以成为波峰或者波谷for(int j 0; j i; j){ // 子序列可以不连续每次都要从头if(nums[j] nums[i]){ //遍历赋值山谷找到之前最大的山顶1dp[i][0] Math.max(dp[i][0], dp[j][1]1);}if(nums[j] nums[i]){ //遍历赋值山峰找到之前最大的山谷1dp[i][1] Math.max(dp[i][1], dp[j][0]1);}}
}
return Math.max(dp[nums.length-1][0], dp[nums.length-1][1]);738. 单调递增的数字 给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。 如果遇到nums[i-1] nums[i]那么nums[i-1] -1, nums[i] 9 循环从后往前递归判断由于可能发生多次变化在这里使用flag标记开始为9的位置最后再循环赋值9
两个维度权衡问题
135. 分发糖果 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求给这些孩子分发糖果每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。 此时需要中间的数字比左边和右边都大。 因此需要进行两次遍历一次确定一个维度。
从前往后遍历一边比左大再从后往前遍历一边比右大保证如果孩子比左右分数都高时糖果数比左右都大。
for(int i 1; icandies.length; i){if(ratings[i] ratings[i-1]) candies[i] candies[i-1] 1;
}
for(int i candies.length-2; i 0; i--){if(ratings[i] ratings[i1]) candies[i] Math.max(candies[i], candies[i1] 1);
}如果题目增加了一个条件小朋友围成了一个环 在首尾补充两个元素首部补充原尾部元素尾部补充原首部元素计算方法还是一样的只是最后求和的时候刨去添加的首尾
406. 根据身高重建队列 假设有打乱顺序的一群人站成一个队列数组 people 表示队列中一些人的属性不一定按顺序。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi 前面 正好 有 ki 个身高大于或等于 hi 的人。 先根据身高h从大到小排序然后再根据k从高往低把people放到第k个位置这样每次插入的都是大值第k个位置前的都比自己大。
// 身高从大到小排身高相同k小的站前面
Arrays.sort(people, (a,b)-{if(a[0] b[0]) return a[1]-b[1];else return b[0]-a[0];
});
LinkedListint[] que new LinkedList();
for(int[] p : people){que.add(p[1], p);
}
return que.toArray(new int[que.size()][2]);区间贪心
452. 用最少数量的箭引爆气球
用最少的弓箭射爆所有气球其本质就是找到不重叠区间数。
现将区间按左节点从小到大排序 int cnt 1;
int startY points[0][1];
for(int i 1; ipoints.length; i){if(points[i][0] startY){cnt;startY points[i][1];}else{startY Math.min(points[i][1], startY);}
}435. 无重叠区间 给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。 计算重叠区间每次保存重叠区间的最小右节点来保证移除的最少
int cnt 0;
int startY intervals[0][1];
for(int i 1; iintervals.length; i){if(intervals[i][0] startY){cnt;startY Math.min(startY, intervals[i][1]);}else{startY intervals[i][1];}
}55. 跳跃游戏二
每次保存当前能到达的最大距离如果到了尽头还没到终点那么跳跃次数增加更新最大距离
int curLoc 0; // 当前跳转步数能走的最大距离
int farLoc 0; // 不断更新到尽头前下次跳转的最大距离
int cnt 0;
for(int i 0; i nums.length-1; i){ //注意这里是num.length-1,如果在倒数第二个位置还没有到达curLoc那么肯定能到达末尾且无需跳转// if(farLoc i nums[i]){// farLoc i nums[i];// cnt;// }farLoc Math.max(farLoc, i nums[i]);if(i curLoc){ //到达当前能走的最大范围curLoc farLoc;//此时更新走过的数组中能跳转的最远距离cnt;}
}加油站
此问题不能使用两层循环会超时 可以换思路 首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。 每个加油站的剩余量rest[i]为gas[i] - cost[i]。 i从0开始累加rest[i]和记为curSum一旦curSum小于零说明[0, i]区间都不能作为起始位置因为这个区间选择任何一个位置作为起点到i这里都会断油那么起始位置从i1算起再从0计算curSum
那么局部最优当前累加rest[i]的和curSum一旦小于0起始位置至少要是i1因为从i之前开始一定不行。全局最优找到可以跑一圈的起始位置
int total_rest 0;
int cur_rest 0;
int start 0;
for(int i 0; igas.length; i){total_rest (gas[i]-cost[i]);cur_rest (gas[i]-cost[i]);if(cur_rest 0){start i1;cur_rest 0;}
}return total_rest 0 ? -1: start;监控二叉树状态
每个节点有三种状态0:未被监控1:已被监控2:此节点有照相机
递归自底向上来根据节点状态判断是否需要加照相机
class Solution {int res 0;public int minCameraCover(TreeNode root) {if(backtracking(root) 0) res;return res;}private int backtracking(TreeNode root){if(root.left null root.right null) return 0; //root没有被监视int leftV 0, rightV 0;if(root.left ! null root.right ! null){leftV backtracking(root.left);rightV backtracking(root.right);}else if(root.left null){rightV backtracking(root.right);leftV rightV;}else if(root.right null){leftV backtracking(root.left);rightV leftV;}if(leftV 0 rightV 0){res;return 2; //root放摄像头}else if(leftV 0 || rightV 0){res;return 2; //root放摄像头}else if(leftV 2 || rightV 2){return 1; //root被摄像头监视}else{ //(left:1, right:1)return 0;}}
}动态规划
动规基础
dp五部曲
定义dp数组含义递推公式初始化dp数组根据递推公式 确定遍历顺序举例推导dp数组
746. 使用最小花费爬楼梯 给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 public int minCostClimbingStairs(int[] cost) {int[] dp new int[cost.length1];dp[0] 0; //一开始不跳不花费dp[1] 0;for(int i 2; i cost.length; i){ //顶楼还有一层需要跳到cost.length层才可以dp[i] Math.min(dp[i-2]cost[i-2], dp[i-1]cost[i-1]);}return dp[cost.length];
}相当于顶层还有一层目的地需要跳到dp[cost.length]
343.整数拆分 给定一个正整数 n将其拆分为至少两个正整数的和并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 public int integerBreak(int n) {int[] dp new int[n1];dp[2] 1;for(int i 3; in; i){for(int j 1; j i/2; j){ // 10-最多55dp[i] Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));}}return dp[n];
}从1遍历j然后有两种渠道得到dp[i]
一个是j * (i - j) 直接相乘。 拆成两个数一个是j * dp[i - j]相当于是拆分(i - j) 拆成多个数
96. 不同的二叉搜索树 给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。 dp[3]就是 元素1为头结点搜索树的数量 元素2为头结点搜索树的数量 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量元素2为头结点搜索树的数量 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量元素3为头结点搜索树的数量 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。 有1个元素的搜索树数量就是dp[1]。 有0个元素的搜索树数量就是dp[0]。
所以dp[3] dp[2] * dp[0] dp[1] * dp[1] dp[0] * dp[2]
其递推关系 dp[i] dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] j相当于是头结点的元素从1遍历到i为止。 所以递推公式dp[i] dp[j - 1] * dp[i - j]; j-1 为j为头结点左子树节点数量i-j 为以j为头结点右子树节点数量
public int numTrees(int n) {int[] dp new int[n1];dp[0] 1;for(int i 1; in; i){for(int j 1; j i; j){dp[i] dp[j-1] * dp[i-j];}}return dp[n];
}背包问题
01背包物品只能用一次
一维dp数组
递推公式 dp[j] max(dp[j], dp[j-weight[i]]value[i]);遍历顺序先遍历物品后遍历背包且背包时从后往前遍历一个物品只能装一个不能覆盖上一次遍历的结果
416. 分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 target sum(nums)/2sum无法整除的直接返回false 需要判断是否存在一种方案使用nums物品可以装满容量为target的背包且总价值和也为target
for(int i 0; i nums.length; i){ //遍历物品for(int j target; j nums[i]; j--){ //逆序遍历背包容量因为1维dp正序的话会被每次覆盖dp[j-nums[i]]dp[j] Math.max(dp[j], dp[j-nums[i]] nums[i]);}
}if(dp[target] target) return true;
return false;1049. 最后一块石头的重量2 一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下 如果 x y那么两块石头都会被完全粉碎 如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。 最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。 假设存在两堆石头它们各自和都相等且为target sum(stones)/2;此时粉碎后正好为0
我们尽量把石头分为这样的两堆因此计算用stones物品装满背包容量target后的最大价值
此时结果则为(sum - dp[target])-dp[target]
完全背包物品可以重复使用
求组合
求有多少种不同的组合不强调元素的顺序填满背包有多少种方式 dp数组递推时需要求和且先遍历物品后遍历背包从前往后遍历 递推公式dp[j] dp[j-nums[i]]为了求和初始化dp[0]1
494. 目标和 给你一个整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘’ 或 ‘-’ 然后串联起所有整数可以构造一个 表达式 例如nums [2, 1] 可以在 2 之前添加 ‘’ 在 1 之前添加 ‘-’ 然后串联起来得到表达式 “2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 left——正数和right——负数和(无符号) left-righttarget leftrightsum left (targetsum) / 2
填满容量为left的背包用nums物品有多少种不同的方式
if(left0) return 0;int[] dp new int[left1]; // 容量为left的背包填满有多少种方式
dp[0] 1; //初始化
for(int i 0; i nums.length; i){for(int j left; j nums[i]; j--){dp[j] dp[j-nums[i]]; //所有求组合装满背包有多少种方式都用这个递推方程}
}
return dp[left];求排列
元素顺序不同也为不同的排列方法因此外层遍历背包内层遍历物品。
如果把遍历nums物品放在外循环遍历target的作为内循环的话举一个例子计算dp[4]的时候结果集只有 {1,3} 这样的集合不会有{3,1}这样的集合因为nums遍历放在外层3只能出现在1后面
dp[i] dp[i - nums[j]]初始化dp[0]1
377. 组合总和 给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。顺序不同的序列被视作不同的组合。 // 求排列个数问题要先遍历背包再遍历物品
for(int i 1; i target; i){ //遍历背包for(int j 0; j nums.length; j){if(i nums[j]) dp[i] dp[i-nums[j]];}
}139. 单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 boolean[] dp new boolean[n1];
dp[0] true;for(int i 1; in; i){for(int j 0; ji; j){String substr s.substring(j,i);if(wordDict.contains(substr) dp[j]){dp[i] true;break;}}
}求最小数
求装满背包所有物品的最小个数 dp[j] min(dp[j-coins[i]], dp[j]);
打家劫舍系列
设置dp数组为二维 [nums.length][2] 其中第二维表示偷/不偷两种状态下的最大金额
198. 打家劫舍
普通版本
public int rob(int[] nums) {int[][] dp new int[nums.length][2];dp[0][0] 0;dp[0][1] nums[0];for(int i 1; inums.length; i){dp[i][0] Math.max(dp[i-1][1], dp[i-1][0]);dp[i][1] dp[i-1][0] nums[i];}return Math.max(dp[nums.length-1][0], dp[nums.length-1][1]);
}213. 打家劫舍II
所有的房屋都围成一圈
需要把收尾状态分情况讨论
不考虑首元素 不考虑尾元素
两种情况分别进行打家劫舍计算结果再取一个最大值
//把环分成两个数组[0,n-1]和[1,n]然后返回最大值
int maxRes1 oriRob(nums, 0, nums.length-2); //闭区间
int maxRes2 oriRob(nums, 1, nums.length-1);
return Math.max(maxRes1, maxRes2);337. 打家劫舍III
树形DP 需要后序遍历利用左右子结点计算出的结果计算root
每次传回一个长度为2的数组作为递归结果偷/不偷
public int rob(TreeNode root) {int[] resDp treeDp(root);return Math.max(resDp[0], resDp[1]);
}private int[] treeDp(TreeNode root){int[] dp new int[2];if(root null) return dp; //到达空节点此时没值return [0,0]int[] leftDp treeDp(root.left);int[] rightDp treeDp(root.right); //后序//处理根dp[0] Math.max(leftDp[0], leftDp[1]) Math.max(rightDp[0], rightDp[1]); //不偷dp[1] leftDp[0] rightDp[0] root.val; //偷return dp;
}股票系列
121. 买卖股票的最佳时机
只能买卖一次dp二维数组 dp[length][2]表示持有股票和不持有股票两种
如果第i天持有股票即dp[i][0] 那么可以由两个状态推出来
dp[i][0] max(dp[i-1][0], -prices[i]); // 持有(前一天就持有, 今天买入)
dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i]); //不持有(前一天就不持有,今天卖出)122. 买卖股票的最佳时机II
不限制股票买卖次数dp二维数组 dp[length][2]表示持有股票和不持有股票两种
与只买卖一次不同的是买入时需要考虑 dp[i-1][1] - prices[i]
dp[i][0] max(dp[i-1][0], dp[i-1][1]-prices[i]); // 持有(前一天就持有, 今天买入)
dp[i][1] max(dp[i-1][1], dp[i-1][0] prices[i]); //不持有(前一天就不持有,今天卖出)123. 买卖股票的最佳时机III
最多买卖2次dp二维数组 dp[length][4]分为四种状态
第一次持有股票 (初始化-price[0])第一次不持有股票第二次持有股票 (初始化-price[0])第二次不持有股票
dp[i][1] max(dp[i-1][1], -prices[i]); //第一次买入
dp[i][2] max(dp[i-1][2], dp[i-1][1]prices[i]); //第一次卖出
dp[i][3] max(dp[i-1][3], dp[i-1][2]-prices[i]); //第二次买入
dp[i][4] max(dp[i-1][4], dp[i-1][3]prices[i]); //第二次卖出188.买卖股票的最佳时机IV
最多买卖K次 int[][] dp new int[n][2*k];
for(int idx 1; idx k; idx){dp[0][2*idx-1] -prices[0]; //初始化
}dp数组分奇数偶数状态分别买入卖出
for(int i 1; in; i){for(int j 1; j k; j){dp[i][2*j-2] Math.max(dp[i-1][2*j-2], dp[i-1][2*j-1] prices[i]);if(j 2){dp[i][2*j-1] Math.max(dp[i-1][2*j-1], dp[i-1][2*(j-1)-2] - prices[i]);}else{dp[i][2*j-1] Math.max(dp[i-1][2*j-1], -prices[i]);}}
}
return dp[n-1][2*k-2];309. 含冷冻期问题
可以多次交易此时可以分为三种状态持有不持有在冷冻期
for(int i 1; i prices.length; i){dp[i][0] Math.max(Math.max(dp[i-1][2], dp[i-1][0]), dp[i-1][1] prices[i]); //卖出手无dp[i][1] Math.max(dp[i-1][1], dp[i-1][2] - prices[i]); //买入手持dp[i][2] dp[i-1][0]; //冷静期状态
}714. 含手续费
卖出时完成一笔交易需要减去手续费
for(int i 1; iprices.length; i){dp[i][0] Math.max(dp[i-1][0], dp[i-1][1] prices[i] - fee);dp[i][1] Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
}子序列问题编辑距离
子序列不连续
1035. 不相交的线 其实就是求最长公共不连续子序列长度
dp[i][j]长度为[0,i-1]的字符串text1与长度为[0,j-1]的字符串text2的最长公共子序列长度
for(int i 1; i nums1.length; i){for(int j 1; jnums2.length;j){if(nums1[i-1] nums2[j-1]){ //相等dp[i][j] dp[i-1][j-1] 1;}else{ //不相等dp[i][j] Math.max(dp[i-1][j], dp[i][j-1]);}}
}子序列连续
连续则只能由前一个状态推导出来
for(int i 1; inums1.length; i){for(int j 1; jnums2.length; j){if(nums1[i-1] nums2[j-1]){dp[i][j] dp[i-1][j-1] 1;}else{dp[i][j] 0; // 子数组不是子序列必须连续//Math.max(dp[i-1][j], dp[i][j-1]);}res Math.max(res, dp[i][j]);}
}编辑距离
115. 不同的子序列 给定一个字符串 s 和一个字符串 t 计算在 s 的子序列中 t 出现的个数。 即s字符串执行多少种不同的删除字符操作可以变为t字符串
int[][] dp new int[s.length()1][t.length()1]; //在s中删除字符匹配t//初始化
for(int i 0; i s.length(); i){dp[i][0] 1; //以i-1为结尾的s可以随便删除元素出现空字符串的个数
}for(int i 1; i s.length(); i){for(int j 1; j t.length(); j){if(s.charAt(i-1) t.charAt(j-1)){//相等时可以使用s[i - 1]来匹配或者删除s[i - 1]bagg - bagdp[i][j] dp[i-1][j-1] dp[i-1][j]; //用s[i-1]和不用}else{dp[i][j] dp[i-1][j];}}
}72. 编辑距离 给你两个单词 word1 和 word2请你计算出将 word1 转换成 word2 所使用的最少操作数 。 有三种操作1.插入一个字符2.删除一个字符3.替换一个字符
word2添加一个元素相当于word1删除一个元素
因此考虑只用两种状态删除和替换
for(int i 1; i word1.length(); i){for(int j 1; j word2.length(); j){if(word1.charAt(i-1) word2.charAt(j-1)){dp[i][j] dp[i-1][j-1];}else{// 删一个字符和插入一个字符的操作数一样可以合并考虑// 只用考虑删和替换int del Math.min(Math.min(dp[i-1][j]1, dp[i][j-1]1), dp[i-1][j-1]2); // 删除dp[i][j] Math.min(del, dp[i-1][j-1]1); //删除替换}}
}回文
647. 回文子串 给定一个字符串你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。 当s[i]与s[j]不相等那没啥好说的了dp[i][j]一定是false。 当s[i]与s[j]相等时这就复杂一些了有如下三种情况 情况一下标i 与 j相同同一个字符例如a当然是回文子串情况二下标i 与 j相差为1例如aa也是回文子串情况三下标i 与 j相差大于1的时候例如cabac此时s[i]与s[j]已经相同了我们看i到j区间是不是回文子串就看aba是不是回文就可以了那么aba的区间就是 i1 与 j-1区间这个区间是不是回文就看dp[i 1][j - 1]是否为true。
for(int i s.length()-1; i0; i--){for(int j i; j s.length(); j){if(s.charAt(i) s.charAt(j)){if((j-i) 1){cnt;dp[i][j] true;}else if(dp[i1][j-1]){dp[i][j] true;cnt;}}}
}单调栈
通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了
单调栈的本质是空间换时间
更直白来说就是用一个栈来记录我们遍历过的元素存放idx数组下标
如果求一个元素右边第一个更大元素单调栈就是从栈底到栈顶递减的如果求一个元素右边第一个更小元素单调栈就是从栈底到栈顶递增的
使用单调栈主要有三个判断条件。
当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
42. 接雨水 求右边第一个更大元素 从栈底到栈顶递减
public int trap(int[] height) {//单调栈从栈底到栈顶递减int res 0;StackInteger st new Stack(); //存放indexst.push(0);for(int i 1; iheight.length; i){if(height[i] height[st.peek()]){st.push(i);}else if(height[i] height[st.peek()]){st.pop();st.push(i);}else{while(!st.isEmpty() height[i] height[st.peek()]){ //这里要用while如果弹出过一次后将新元素压入后还要再次判断是否要再弹出int mid st.pop();if(!st.isEmpty()){int left st.peek();int h Math.min(height[left], height[i]) - height[mid];int w i - left -1;res h * w;}}st.push(i);}}return res;
}84. 柱状图中最大的矩形
求右边第一个比自己小的从栈底到栈顶递增
同时这里需要考虑第一个和最后元素栈内全部计算因此需要在原数组前后加[0,xxx,0]
public int largestRectangleArea(int[] heights) {//因为需要找右边第一个小于mid的所以从低到栈顶是递增的int res 0;StackInteger st new Stack();//在前后加0来保证第一个和最后一个的最大矩阵也计算到int[] newHeights new int[heights.length 2];newHeights[0] 0;for(int i 1; inewHeights.length-1; i){newHeights[i] heights[i-1];}newHeights[newHeights.length-1] 0;st.push(0);for(int i 1; inewHeights.length; i){if(newHeights[i] newHeights[st.peek()]){st.push(i);}else if(newHeights[i] newHeights[st.peek()]){st.pop();st.push(i);}else{while(!st.isEmpty() newHeights[i] newHeights[st.peek()]){int mid st.pop();int w i - st.peek() - 1;res Math.max(res, (newHeights[mid]*w));}st.push(i);}}return res;
}单例模式
单例模式Singleton Pattern保证一个类只有一个实例对象并提供一个访问它的全局访问点。
把构造方法私有化类本身要对外提供访问入口全剧唯一static
饿汉模式
先创建后使用 (还没有使用该单例对象就已经被加载到内存中)线程安全占用内存。
public class EagerSingleton{private static final EagerSingleton INSTANCE new EagerSingleton();private EagerSingleton(){}public static EagerSingleton getInstance(){return INSTANCE;}
}懒汉模式
用的时候才创建线程不安全创建或获取单例对象时加锁会影响效率。
使用双重校验锁模式来方式线程不安全和指令重排序的问题同时效率比synchronized声明同步方法高。
public class LazySingleton {private static volatile LazySingleton INSTANCE null; //防止指令重排序private LazySingleton(){}public static LazySingleton getInstance(){if(INSTANCE null){synchronized(LazySingleton.class){if(INSTANCE null){ //防止前后两个线程进入等待锁之后覆盖初始化INSTANCE new LazySingleton(); }}}}
}简单工厂
简单工厂模式又称为静态工厂模式定义一个工厂类他可以根据参数的不同返回不同类的实例被创建的实例通常都具有相同的父类。 定义抽象产品类同时定义抽象方法
/**
* 产品的抽象类
**/
public abstract class Product{// 描述产品的品类public abstract void show();
}定义具体的产品类统一继承抽象类
/**
* 产品品系A
**/
public class ProductA extends Product{Overridepublic void show(){System.out.println(ProductA);}
}/**
* 产品品系B
**/
public class ProductB extends Product{Overridepublic void show(){System.out.println(ProductB);}
}定义产品具体工厂
/**
* 产品工厂 --可以选哪几种产品
**/
public class SimpleProductFactory{/*** 店里产品的种类**/public static Product createProduct(int type){switch (type){case 1:return new ProductA(); //产品Acase 2:return new ProductB(); //产品Bdefault:return null;}}
}*使用工厂类
public class Customer{public static void main(String[] args){Product p SimpleProductFactory.createProduct(1);p.show();}
}简单工厂的核心是工厂类在没有工厂类之前客户端一般会使用new关键字之间创建对象而引入工厂类之后客户端可以通过工厂类来创建产品。
排序相关
快速排序O(nlgn)O(nlgn)O(nlgn)
public void quickSort(int[] nums, int low, int high){if(low high){int p partition(nums, low, high);quickSort(nums, low, p-1);quickSort(p1, high);}
}public int partition(int[] nums, int left, int right){int temp nums[left];while(left right){while(left right nums[right] temp) right--;nums[left] nums[right];while(left right nums[left] temp) left;nums[right] nums[left];}nums[left] temp;return left;
}归并排序
public void mergeSort(int[] nums, int low, int high){if(low high){int mid low (high - low) 2;mergeSort(nums, low, mid);mergeSort(nums, mid1, high);merge(nums, low, mid, mid1, high);}
}public void merge(int[] nums, int l1, int r1, int l2, int r2){int[] temp new int[r2-l11];int idx 0;int i1 l1, i2 l2;while(i1 r1 i2 r2){if(nums[i1] nums[i2]){temp[idx] nums[i1];}else{temp[idx] nums[i2];}}while(i1 r1) temp[idx] nums[i1];while(i2 r2) temp[idx] nums[i2];for(int i 0; i idx; i){nums[l1i] temp[i];}
}工具IntStream、LongStream 和 DoubleStream
这三个原始流在 java.util.stream 命名空间下并提供了大量的方法用于操作流中的数据同时提供了相应的静态方法来初始化它们自己
创建IntStream流(IntStream中的静态方法of / builder/ range / rangeClosed / generate / iterate)
IntStream.of()方法
IntStream intStream IntStream.of(1);
IntStream intStream IntStream.of(1,2,3,4,5);IntStream.range()、IntStream.rangeClosed()方式 range()前闭后开区间 rangeClosed()前闭后闭区间
IntStream range IntStream.range(1, 100); // 返回 1,2,3,4,......,99
IntStream range IntStream.rangeClosed(1, 100); // 返回 1,2,3,4,......,99,100IntStream.iterate()方式 根据指定规则生成一串int流使用iterate()方式也是无限连续的流需使用limit()来限制元素的数量)
// 规则生成2的幂次方int流
IntStream intStream11 IntStream.iterate(1,x-2 * x).limit(6);IntStream.concat()方式 (将两个int流合并成一个流)
IntStream range1 IntStream.range(1, 5); // A流
IntStream range2 IntStream.range(10, 15); // B流
IntStream concat IntStream.concat(range1, range2); // 合并后的流filter() 方法过滤出符合条件的数据
用于过滤数据返回符合过滤条件的数据是一个非终结方法 可以通过 filter() 方法将一个流转换成另一个子集流。该接口接收一个 Predicate 函数式接口参数(可以是一个 Lambda 或 方法引用) 作为筛选条件。因为 filter() 是一个非终结方法所以必须调用终止方法。
// 获取1-9的int流
IntStream intStream IntStream.range(1, 10);
// 通过filter方式过滤掉小于5的数字,并输出
intStream.filter(x-x5).forEach(System.out::println);map()方法对流中所有元素执行某个修改操作
IntStream 中的map()方法用于对流中的所有元素执行某个修改操作这与 Stream 中的map()方法有所不同
IntStream intStream IntStream.range(1, 10);
intStream.map(o - 2 * o).forEach(System.out::println);mapToObj / mapToLong / mapToDouble / asLongStream / asDoubleStream
1.mapToObj将 int 流转换成其他类型的流 (其他类型可以使自定义对象类型也可以是List类型等) 2.mapToLong将 int 流转换成Long类型的流不可指定返回值规则 3.mapToDouble将 int 流转换成Double类型的流不可指定返回值规则 4.asLongStream将 int 流转换成Long类型的流该方法遵循标准的int到指定类型的转换规则不能指定规则比如说将int流对象先 乘以2再返回 5.asDoubleStream将 int 流转换成Double类型的流该方法遵循标准的int到指定类型的转换规则不能指定规则比如说将int流对象先 乘以2再返回
IntStream intStream IntStream.range(1, 10);
// mapToObj():将int流转换成Person对象
intStream.mapToObj(val - new Person(val, Mary val)).forEach(System.out::println);IntStream intStream IntStream.range(1, 10);
// mapToLong()方法(可指定返回值规则)
intStream.mapToLong(val - 2 * val).forEach(System.out::println);// mapToDouble()方法(可指定返回值规则)
intStream.mapToDouble(val - 2 * val).forEach(System.out::println);// asDoubleStream()方法(不可指定返回值规则)
intStream.asDoubleStream().forEach(System.out::println);// asLongStream()方法(不可指定返回值规则)
intStream.asLongStream().forEach(System.out::println);forEach / forEachOrdered
用来遍历流中的元素是一个终结方法 1.forEach遍历流中的元素 2.forEachOrderedforEachOrdered同forEach的区别在于并行流处理下forEachOrdered会保证实际的处理顺序与流中元素的顺序一致而forEach方法无法保证默认的串行流处理下两者无区别都能保证处理顺序与流中元素顺序一致。
IntStream intStream IntStream.of(2,6,3,5,9,8,1);
intStream.forEach(x-{System.out.println(forEach-x);
});distinct()方法
可以用来去除重复数据。因为 distinct() 方法是一个非终结方法所以必须调用终止方法
IntStream intStream IntStream.of(1, 2, 3, 4, 5, 6, 1, 4, 5, 2);
intStream.distinct().forEach(System.out::println);sorted() 方法
用来对 Stream 流中的数据进行排序 Stream流中的sorted()方法还允许我们自定义Comparator规则进行排序参考:JDK8新特性(三)集合之 Stream 流式操作 中的sorted()方法 IntStream流中的sorted()方法就是纯粹对int数值进行排序所以也没有Comparator自定义比较器排序的必要
IntStream.of(nums).boxed() //转为Stream流.sorted((o1, o2) - Math.abs(o2) - Math.abs(o1))skip
如果希望跳过前几个元素去取后面的元素则可以使用 skip()方法获取一个截取之后的新流它是一个非终结方法。参数是一个 long 型如果 Stream 流的当前长度大于 n则跳过前 n 个否则将会得到一个长度为 0 的空流。因为 limit() 是一个非终结方法所以必须调用终止方法。
IntStream intStream IntStream.of(1, 9, 4, 35, 5, 2);
// skip()跳过流中前2个元素,获取剩下的元素
intStream.skip(2).forEach(System.out::println);sum / min / max / count / average / summaryStatistics
sum求和 min求最小值 max求最大值 count计算IntStream流中元素个数 average求平均值 summaryStatistics该方法一次调用获取上述5个属性值
boxed()
boxed翻译过来是盒子被包装的意思。即返回由IntStream流中的元素组成的Stream流每个box 都装着Integer类 在Stream流中是没有boxed()方法的 只有在IntStream、DoubleStream、LongStream 这三种类型的流中才有boxed()方法
// 1.通过mapToObj()方法的方式返回Streamxxx类型
IntStream intStream IntStream.of(1, 9, 4, 35, 5, 2);
intStream.mapToObj(Integer::valueOf).collect(Collectors.toList()).forEach(System.out::println);// 2.通过boxed()方法的方式返回StreamInteger类型
IntStream intStream1 IntStream.of(1, 9, 4, 35, 5, 2);
StreamInteger boxed intStream1.boxed(); // 看这里,通过boxed返回的是StreamInteger类型
ListInteger collect boxed.collect(Collectors.toList()); // 转换成ListInteger类型//3.通过mapToInt()方法把Stream流转IntStream
boxed.mapToInt(Integer::intValue)toArray()
将IntStream流中的元素转换成一个数组
IntStream intStream IntStream.of(1, 9, 4, 35, 5, 2);
// toArray:将IntStream流中的元素转换成一个数组
int[] intArray intStream.toArray();例子
将数组按照绝对值大小从大到小排序
int[] nums {4,-2,3,-9,1};
nums IntStream.of(nums).boxed().sorted((o1,o2)- Math.abs(o2)- Math.abs(o1)).mapToInt(Integer::intValue).toArray();
