一、Java相关 1.时间复杂度 https://blog.csdn.net/xy010902100449/article/details/46537507 https://blog.csdn.net/zhen921/article/details/80212625
2.刷题顺序 数组-> 链表-> 哈希表->字符串->栈与队列->树->回溯->贪心->动态规划->图论->高级数据结构
基础篇（30 天） 基础永远是最重要的，先把最最基础的这些搞熟，磨刀不误砍柴工。 数组，队列，栈 链表 树与递归 哈希表 双指针 思想篇（30 天） 这些思想是投资回报率极高的，强烈推荐每一个小的专题花一定的时间掌握 二分 滑动窗口 搜索（BFS，DFS，回溯） 动态规划 提高篇（31 天） 收益不明显,需要技术积累,使用技巧 贪心 分治 位运算 KMP & RK 并查集 前缀树 线段树 堆
3.Java中数组为空和数组长度为0的区别 为空: 会NullPointerException 为0: 无事发生
if(array == null || 0 == array.length) {...} // 这种写法正确，因为执行到 “0 == array.length”则说明数组不为空，不会产生空指针异常。 if (0 == array.length || array == null) {...} // 这种写法可能会产生空指针异常。
int[] n; //只声明了一数组变量； int[] nil = null; //声明一数组变量，并赋值 null,nil是一个数组类型的空引用，不指向任何对象； int[] zero = new int[0]; //声明并创建一数组对象，长度是0； 对于上面三条语句，一个比一个做的动作多，系统占用也是后面的多： 语句一变量还没初始化，打印 n 会出错：“可能尚未初始化变量 n”； 语句二虽已初始化，打印“nil.length”会出现异常：NullPointerException；
4.ACM模式: 输入中有一个数组 ，且有数组的长度 7 1 2 3 4 5 6 7 联想: BufferedReader-->readLine-->trim+split-->Integer.parseInt
// 创建一个BufferedReader对象 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 读取第一行数据 String line = br.readLine(); // trim(" ")将字符串根据空格进行分隔 //public String trim():去掉字符串两端空格 String[] strings = line.trim().split(" "); // 分别将其中的每个数值读出 //- public static int parseInt(String s)：将字符串参数转换为对应的int基本类型。 int n = Integer.parseInt(strings[0]); int v = Integer.parseInt(strings[1]); // 读取第二行数据 line = br.readLine(); strings = line.trim().split(" "); // 创建一个int型的数组用来储存第二行的多个数字 int[] nums = new int[n]; for (int i = 0; i < n; i ++) { nums[i] = Integer.parseInt(strings[i]); } // 测试输入是否正确 for (int num: nums) { System.out.print(num + " "); }
5.java安全防溢出的两整数平均值算法 public static int mean(int a, int b){ return (x & y) + ((x ^ y) >> 1); }
6.static修饰成员的访问特点 1.不管在不在同一个类中,想要访问非静态的,都可以new对象调用 2.不管在不在同一个类中,想要访问静态的,都可以类名直接调用
7.数组 704. 二分查找 循环不变量原则------------------------->坚持对区间的定义 27. 移除元素 双指针法（快慢指针法）------------------->通过一个快指针和慢指针在一个for循环下完成两个for循环的工作 209.长度最小的子数组 滑动窗口--------------------->根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n) 59.螺旋矩阵II 循环不变量原则-------------------------->二维数组
8.链表 cur-> next = cur->next->next 左边是指针,右边是结点 翻转链表是现场面试，白纸写代码的好题
203.移除链表元素 虚拟头结点————————>解决头结点的情况都要单独处理(增删)的问题
环形链表 II 快慢指针 相对性——————–>判断链表是否有环
9.哈希表 当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。数组 哈希值比较小,范围可控时用 eg: 都是小写字母 √ 0 <= nums1[i]<= 1000 哈希值比较少、特别分散、跨度非常大,使用数组就造成空间的极大浪费×set 数值很大时,去重 里面放的元素只能是一个key————哈希值比较少、特别分散、跨度非常大map key-value map的空间消耗要比数组大
242.有效的字母异位词 包含小写字母————————————–用数组, 数组就是简单的哈希表，但是数组的大小是受限的
10.字符串 善用StringBuilder ------------>拼接字符串 1.概述:java自带的类 2.作用:主要作用就是拼接字符串 3.拼接字符串特点: a.自带一个缓冲区,长度默认16,在这个缓冲区中拼接字符串,不会产生新的String对象,始终就这一个StringBuilder对象 b.不浪费内存,不会产生新的串 c.底层是一个char[] value 没有被final修饰,扩容时其实是采用的是数组复制 d.如果要是扩容的话,为2倍+2 先整体反转再局部反转 先局部反转再 整体反转 善用反转a+再反转b+再反转ab
344.反转字符串 双指针 剑指Offer 05.替换空格 双指针----------------------------------------从后往前遍历,减少时间复杂度 很多数组（字符串）填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。 541. 反转字符串 II for循环--------------------------------------- i += (2 * k) 151. 反转字符串中的单词 先整体反转再局部反转 剑指Offer58-II.左旋转字符串 先局部反转再整体反转 28. 找出字符串中第一个匹配项的下标 KMP匹配问题-----------------------------------在一个串中查找是否出现过另一个串 459. 重复的子字符串 KMP-----------------------------------------寻找重复子串,即最长相等前后缀所不包含的那一个子串
11.栈和队列 栈----------------------------------------------------------------对称匹配,匹配问题 eg: 20. 有效的括号 map---------------------------------------------------------------统计元素出现的频率,特别好用 PriorityQueue-----------------------------------------------------小顶堆(完全二叉树) 单调队列(自己造出来)--------------------------------------------------239. 滑动窗口最大值 优先级队列(披着队列外衣的堆PriorityQueue)------------------------------347.前 K 个高频元素 对部分数据进行排序O(logk)
Deque: 两端元素插入和移除的线性集合 Deque有一个致命缺陷：不适合遍历 Deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的 ArrayDeque 当用作堆栈时， 此类可能比Stack更快，并且当用作队列时快于LinkedList 。 PriorityQueue public PriorityQueue(Comparator<? super E> comparator) Stack push pop peek Queue add/offer poll peek remove Deque addLast pollFirst peekFirst 都有xxxLast版本 ArrayDeque (poll)pollFirst/pollLast 返回并删除头/尾 addFirst/addLast(add) 插入到头/尾 getFirst/getLast 获得头/尾元素 (Boolean) offer/offerFirst/offerLast 插入到头/尾 add和offer的区别: offer()直接调用了add()方法。所以在ArrayDeque/LinkedList中add（）与offer（）的使用相当于是一样的。 Queue中: add:在不违背队列的容量限制的情况, 添加成功返回true, 失败抛出IllegalStateException异常 offer:在不违背队列的容量限制的情况,添加成功返回true,失败返回false remove和poll的区别: remove不能删null, poll可以 总结: 需要链接元素到队列尾时优先用offer() 删除元素优先使用poll() 查看元素优先使用peek() 特别情况： 想要在指定索引位置链接元素可以使用add(int index, E element) 修改指定索引的元素可以使用set(int index, E newElement) 获取指定索引的元素可以使用get(int index) ArrayDeque和LinkedList区别: 前者不能插入/删除null, 后者可以
239. 滑动窗口最大值---------------------队列, 随着窗口的移动，队列也一进一出
12.二叉树 存储方式: 数组/链表(常) 前中后序-------------------------------深度优先遍历 层序----------------------------------广度优先遍历 就是迭代法 递归底层-------------------------------栈 迭代法中究竟什么时候用队列，什么时候用栈？ 前中后序-------------------------------栈 注意: 压栈顺序: 前序:中右左 后序:中左右后reverse 层序遍历-------------------------------队列, 用size记录当前层结点数, 然后每弹一个就把它的左右孩子放入队列 当然还是其他情况，那么就是 先用队列试试行不行，不行就用栈。
二叉树的递归遍历 递归算法的三个要素: 1.确定递归函数的参数和返回值 2.确定终止条件 3.确定单层递归的逻辑 针对二叉树的问题，解题之前一定要想清楚究竟是前中后序遍历，还是层序遍历。
递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点： 1.如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii） 2.如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先中介绍） 3.如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（112路径总和） 递归函数什么时候加if，什么时候不加if 一般情况来说：如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。
用数组构造二叉树 每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。
什么时候用后序遍历---------------------------------------需要收集孩子们的信息向上一层返回 101. 对称二叉树 如何遍历完全二叉树: 完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。 情况一: 可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1 情况二: 分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算 那么, 如何去判断一个左子树或者右子树是不是满二叉树呢？ 在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。反之则不是
101. 对称二叉树 判断是不是对称的二叉树----------------------------判断左右孩子(子树)是否可以翻转//遍历两棵树,即内外侧 只能用后序遍历-----------------------------------因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等 104. 二叉树的最大深度 根结点的高度即二叉树的最大深度----------------------后序求高度, 前序求深度 (前序代码复杂) 深度:123(结点到根结点的距离) 高度:321(结点到叶子结点的距离)
13.回溯算法 解决的问题: 组合问题：N个数里面按一定规则找出k个数的集合 切割问题：一个字符串按一定规则有几种切割方式 子集问题：一个N个数的集合里有多少符合条件的子集 排列问题：N个数按一定规则全排列，有几种排列方式 棋盘问题：N皇后，解数独等等
回溯法模板: 回溯函数模板返回值以及参数 回溯函数终止条件 回溯搜索的遍历过程 还要强调一下，回溯法中递归函数参数很难一次性确定下来，一般先写逻辑，需要啥参数了，填什么参数。
模板框架: void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
回溯法解决的问题都可以抽象为树形结构（N叉树）: 集合长度n相当于树的宽度，k个数相当于树的深度
对于组合问题，什么时候需要startIndex呢？(仅组合, 排列另说) 如果是一个集合来求组合的话，就需要startIndex，例如：77.组合，216.组合总和III。 如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合
startIndex和i的理解: startIndex可以理解为树枝的深度, i可以理解为树层
树枝去重和数层去重: 我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下： used[i - 1] == true，说明同一树枝candidates[i - 1]使用过 used[i - 1] == false，说明同一树层candidates[i - 1]使用过
排列问题与组合问题的不同: 每层都是从0开始搜索而不是startIndex 需要used数组记录path里都放了哪些元素了
14.动态规划 五步曲: 1.确定dp数组（dp table）以及下标的含义: 看题目要求的是什么定义即可,选/不选 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组
如果代码写出来了，一直AC不了，灵魂三问： 1.这道题目我举例推导状态转移公式了么？ 2.我打印dp数组的日志了么？ 3.打印出来了dp数组和我想的一样么？
什么类型的题目可以用01背包？ 既是重量又是价值 分割成等和子集
求装满背包有几种方法的情况下，递推公式一般为： dp[j] += dp[j - nums[i]];
01背包问题： 每个物品只有一个（选/不选） 二维数组解法：(第二个维度表示有几种状态,一般有选/不选两种状态就是[2]) 1.确定dp数组（dp table）以及下标的含义 dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。 2.确定递推公式 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 3.dp数组如何初始化 第一行和第一列： dp[0][j] 和 dp[i][0] // 创建dp数组 int goods = weight.length; // 获取物品的数量 int[][] dp = new int[goods][bagSize + 1]; // 初始化dp数组 // 创建数组后，其中默认的值就是0 for (int j = weight[0]; j <= bagSize; j++) { dp[0][j] = value[0]; } 4.确定遍历顺序 其实都可以！！ 但是先遍历物品更好理解 // weight数组的大小 就是物品个数 for(int i = 1; i < weight.size(); i++) { // 遍历物品 for(int j = 0; j <= bagweight; j++) { // 遍历背包容量 if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } } 5.举例推导dp数组
01背包问题： 每个物品只有一个（选/不选） 一维数组解法：（理解：把dp[i - 1]那一层拷贝到dp[i]上） 1.确定dp数组（dp table）以及下标的含义 dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j] 2.确定递推公式 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 3.dp数组如何初始化 //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值 int[] dp = new int[bagWeight + 1]; dp[0] = 0; 假设物品价值都是大于0的,dp数组都初始为0就可以了 4.确定遍历顺序 先遍历物品,后遍历背包 且背包是从大到小倒序遍历： 倒序遍历是为了保证物品i只被放入一次！ for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } 5.举例推导dp数组
完全背包: 和01背包的区别是内层循环是正序不是倒序 如果是纯完全背包问题------>2层for循环是可以上下颠倒的 如果求装满背包有几种方法--->如果是组合则先物品后背包,如果是排列则先背包后物品
二、其他 1.刷leetcode要打开的网站 https://leetcode.cn/problemset/algorithms/?page=1
https://gitee.com/programmercarl/leetcode-master#/programmercarl/leetcode-master/blob/master/problems/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md
https://www.programmercarl.com/
https://github.com/azl397985856/leetcode
https://snailclimb.gitee.io/javaguide/#/?id=%e5%9f%ba%e7%a1%80
https://blog.csdn.net/KingGue/article/details/123335283?ops_request_misc=&request_id=&biz_id=102&utm_term=acm%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BAjava&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-123335283.142^v44^control&spm=1018.2226.3001.4187
https://www.bilibili.com/video/BV1kd4y1o7on/?spm_id_from=333.788&vd_source=f9b75c65a744e55bbd4dd8315fb6415d
数据结构pdf file:///E:/Java_study/books/2021%E5%A4%A9%E5%8B%A4%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E3%80%90%E5%B0%8F%E9%BA%A6%E9%BA%A6%E8%B5%84%E6%96%99%E5%BA%93%E3%80%91.pdf
2.如何做题 1.看到题想10分钟 2.做不出来看思路再想10分钟 3.再做不出来看解析后做10分钟 先写核心代码, 复制到leetcode上报错再写输入输出调试
3.Java快捷键 idea 查看一个类的所有子类以及子类的子类并以层级关系显示: Navigate -----> Type Hierarchy 或者Ctrl+H 查接口实现类: ctrl+alt+B 跳到上一个位置: Ctrl + [ 跳到下一个位置: Ctrl + ]
4.ArrayList与 HashSet 互相转换 传参即可 ArrayList<String> arrList = new ArrayList<>(animalSet); Set set = new HashSet(list); List list = new ArrayList(set);
5.好用的API String String message = String.join("-", "Java", "is", "cool"); // message returned// is: "Java-is-cool" static String join(CharSequence delimiter, CharSequence... elements) 返回一个由连接在一起的 CharSequence elements副本组成的新字符串，并附带指定的 delimiter的副本 static String join(CharSequence delimiter, Iterable<? extends CharSequence> elements) "hamburger".substring(4, 8) returns "urge" public String substring(int beginIndex, int endIndex) O(n)
Map map.getOrDefault(num,0) default V getOrDefault(Object key, V defaultValue) 返回指定键映射到的值，如果此映射不包含该键的映射值，则返回 自定义值defaultValue 。 map.entrySet() Map.entrySet() 这个方法返回的是一个Set<Map.Entry<K,V>>，Map.Entry 是Map中的一个接口，他的用途是表示一个映射项（里面有Key和Value），而Set<Map.Entry<K,V>>表示一个映射项的Set。Map.Entry里有相应的getKey和getValue方法，即JavaBean，让我们能够从一个项中取出Key和Value。 eg: //第三种：推荐，尤其是容量大时 System.out.println("通过Map.entrySet遍历key和value"); for (Map.Entry<String, String> entry : map.entrySet()) { System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue()); }
Arrays Arrays.asList(nums[i],nums[j],nums[l],nums[r]); static <T> List<T> asList(T... a) 返回一个受指定数组支持的固定大小的列表 static int binarySearch(int[] a, int key) ->按照二分查找方式去搜索 static void sort(int[] a) ->排序(升序)(On（logn）) static int[] copyOf(int[] original, int newLength) ->数组扩容
Collections Collections.reverse(wordList); static void reverse(List<?> list) 反转指定列表中元素的顺序。
6.JAVA中字符与字符异或的问题 https://bbs.csdn.net/topics/390982019
7.力扣没刷的题 8.char类型转换成int类型的两种方法 https://blog.csdn.net/weixin_40422192/article/details/123521114 https://blog.csdn.net/weixin_43902063/article/details/104784690
方法一：在char后面 -“0”
public class Main { public static void main(String[] args) { char numChar = '3'; int intNum = numChar - '0'; System.out.println(numChar + ": " + intNum); } }
方法二: 复杂 利用Integer包装类的方法Integer.parseInt Copychar ch = '9'; if (Character.isDigit(ch)){ // 判断是否是数字 int num = Integer.parseInt(String.valueOf(ch)); System.out.println(num); }
9.集合和数组的互相转换 1.集合转换为类型一致的数组toArray List<String> list = new ArrayList<>(2); list.add("guan"); list.add("bao"); String[] array = list.toArray(new String[0]);
2.数组转换为类型一致的集合asList Integer [] arr2={1,2,3}; // 传入的参数类型为 Integer时，返回泛型参数就是Integer List<Integer> list2 = Arrays.asList(arr2); // 新建一个java.util包下的List的实现类即可 List<Integer> list=new ArrayList<>(list2); list.add(4); System.out.println(list);
10.HashMap转为List https://blog.csdn.net/xHibiki/article/details/82938480
key简单，vaue较为费劲
key：
Set set=phone.keySet(); Object[] arr=set.toArray(); Arrays.sort(arr); for (Object key:arr){ System.out.println(key); }
value：
//转换为list List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>(phone.entrySet()); //转换为list
