以前写的总结

框架思维：

  • 数据结构的存储方式：数组和链表
  • 任何数据结构无非遍历和访问，在不同的场合高效增删改查
  • 而遍历分为线性和非线性（for/while和递归）

算法心得：

  • 算法的本质就是无穷举
  • 数组/单链表常用：双指针，二分搜索，滑动窗口，回文子串，前缀和，差分数组
  • 二叉树常用：1.遍历一遍二叉树(递归函数无返回值) 2.分解问题计算答案(递归函数有返回值)

二叉树：

void traverse(TreeNode root) {
if (root == null) {
	return; 
} 
// 前序位置 :进入结点的时候
traverse(root.left);
// 中序位置 
traverse(root.right);
// 后序位置  :离开结点的时候
}
  • 层序遍历：竖while横for

链表：双指针

  • 设置虚拟结点，用指针来进行变化，同时新建链表注意指明最后一个结点

回溯算法：

  • 回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」
  • 我们通过保证元素之间的相对顺序来防止出现重复子集—-用start变量
  • 标记那些元素可以被选择—–用used数组
  • 重复元素中找可能解—-先排序，用num[i]==num[i-1]来减枝
  • 重复元素的全排列—-先排序，用num[i]==num[i-1]&&!used[i-1]固定相同数值位置来减枝（规则：相同则前一个必走过），且used[i]标记该数值是否被使用
  • 子集/组合问题必须用start，排列问题必用used数组

数组：

  • 双指针

  • 一维前缀和：preSum[i] 记录 nums[0..i-1] 的累加和

  • 二维前缀和：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和 对于前缀和问题：申请新数组范围是n+1，数组实际从索引1开始

  • 差分数组：差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。 后面数据靠前面的差值，diff[i] 就是 nums[i] 和 nums[i-1] 之差 如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可：

  • 链表用指针遍历，可以用坐标来标记数组是否遍历

  • 滑动窗口无法解决含有负数的数组，前缀和喜欢与HashMap搭配

递归与树的结合认知

  • 1.写代码表面有几次就会产生几个树枝，这个思想肯定要有
  • 2.返回值是下一层给上一层的值，因此代码要返回到最顶层（最初层），递归才会结束·
  • 3.递归要有结束标志，也就是递归到最底层时，就开始进行返回（这时会产生有一个虚假层）
  • 4.核心代码是虚假层与倒数第一层的之间的关系
  • 某一层如果不返回的话，就会一直递归（所以要注意空）
  • 5.写代码时就是思考什么时候停止，任意两层如何返回。

递归：

  • return后，就会进入上一层，进行递归语句的后面语句

链表

  • A指向B A.next=B

  • 左边有next可以控制指针方向，右边有next只是简单的赋值操作

  • 链表结点建立关系：要用堆去思考 例如下列情况： 对于一：p10先指向一个空间，p11再指向p10的空间,p10又去指向另一个空间p2的 结果：p10,p2同一地址，p11一地址 对于二：p10先指向一个空间，p11再指向p10的空间，p10的下一个空间为p2 结果：p10,p11同一个地址，在共同下一个地址为p2

**因此情况二才是我们平时刷题希望的结果，**共同指向同一个地址， 改变p10,p11的链表结果，都会去影响另一个

	情况一											情况二
	TreeNode1 p10=new TreeNode1();  				TreeNode1 p10=new TreeNode1();  
	TreeNode1 p11=p10;  							TreeNode1 p11=p10;  
	p10=p2;											p10.next=p2;

二叉树方面：

  • 只要找到建立好树的某个节点，去寻找其左右结点，就会按树的结点编排去找， 因此即使只知道某个结点，也是可以直接读出它的左右节点， 相当于已经在最初时建立好了关系，在任何一个时间读取，之间依旧有关系。

对与字符串问题

  • 可以使用数组，索引为每个字母，值由具体题定

对于滑动窗口问题：

  • 就需要两个while循环，循环之间是镶嵌关系 其中一个循环控制右指针，另一个循环控制左指针

在方法中定义的变量一定要有初始值

数组相邻比大小：可以先从左向右遍历，再从右向左遍历

对于方法返回值，若只有一层，只要遇到return就会返回，也就函数调用结束，没有遍历完的就不会再管了

  • 找区间交集个数，只需要排序数组末尾数字

滚动数组的空间复杂度O(1),数组的空间复杂度O(n) 滚动数组赋值时，从后往前赋值

位运算异或：0与任何数异或为任何数，相同数之间异或值为0，且异或满足交换律，结合律

数组排序可以有效的解决重复问题,看下一个数组值与当前数组值是否相等 查看相邻数组值是否相等，if(i>0&&arr[i]==arr[i-1])

  • 对于快排的思考，先找基准：例如以最左边为基准，则找排列从最右边，就是两个的方向要相反，找到基准之后，在进行排列时，
  • 记住：一定要确保每一个整体满足l<r，因此不管是交换时，还是找数字排列都要有前提条件
  • 每一个l<r的大循环结束，接下来就要思考把基准值放在应放的位置，而l==r就是那个应放的位置，因此一次函数只是将一个
  • 基准值放在应放的位置，再进行递归，因此就要思考递归结束标志

返回值int[][]和List<List<>>是不同的，不能想成一样

  • 集合在思考时写为空集长度为0，而compare在进行数组排列时，不能用>=区分，只能是>,=

要求区间是开区间，则while中不加==

1.算法的本质就是穷尽举，知道自己的目标什么，找到思考的条件，进行反向思考进行条件所有， 就比如数组时刻要序列不超过范围，二叉树时刻注意是否为空等这些条件，把无数的条件， 进行逆向思考，即可知道所有范围，满足穷举。 2.一定要知道变量和目标，时刻清晰

  • 链表不能用等于直接连接：p1=p2这是错误，但指针可以
  • 实参传值时不能i++,必须i+1

String类型比较大小：s2.compareTo(s1) len相同逐一比assic码，不同比len

list集合变字符串：res.toArray(new String[res.size()])

Pair和Map Pair是一对值，Map是集合
List<Pair<>>和Map<>类似