算法知识点记录整理
算法小记
https://juejin.cn/post/7236689719077617722
数组
1.二分查找
left=0
right = nums.size-1
while(left<=right){
mid = (right+left) /2
if(nums[mid] == target){
return mid
} else if( nums[mid] < target){
//右边区间 [mid+1,right]
left = mid + 1
} else {
//左边区间 [left,mid-1]
right = mid - 1
}
}
2.移除数组元素（不开辟新空间）
1）暴力法：找到后交换元素，双重循环
2）快慢指针：
for (fast in nums.indices) {
if (nums[fast] != val) {
nums[slow] = nums[fast]
slow++
}
}
3.有序数组的平方（有正负，不开辟新的空间）
快慢指针指从左右两边依次向中间比较
4.找出数组中满足其和 ≥ s 的长度最小的 连续 子数组
如: 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组
1.暴力法
2.双指针（滑动窗口）每一次比较更新下结果，最后留下最短长度
字符串
1.反转字符串
双指针
//交换
var temp = s[left]
s[left] = s[right]
s[right] = temp
2.替换空格
扩充数组空间+双指针
从后先前将空格替换为”%20”
哈希表
1.两数之和
两数之和 = target
把数组的值和序号放入hashmap，值是key，序号是value
for(){
1.放入map
2.containsKey
val matcher = target-nums[index]
if(tempMap.containsKey(matcher))
}
2.有效的字母异位数
利用hashmap
3.两个数组的交集
数组有重复数据，使用hashset过滤重复数据
然后使用 for + contains
4.赎金信
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成
定一个26长度的数组即可
链表
1.移除链表元素
//删除节点
temp.next = temp?.next?.next
//移动指针
temp = temp.next
2.反转单链表
关键点：一个当前节点cur，一个前置节点pre
Node next = cur.next;//1
cur.next = pre;//2
pre = cur;//3
cur = next;//4
其中14移动cur，2是关键，pre指向当前，cur指向next
也可以用递归法
3.删除链表倒数第N个节点
快慢指针：如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾
4.环形链表
快慢指针，慢指针每次走1步，快指针每次走2步
二叉树
满二叉树: 如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
完全二叉树: 除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
BFS(广度优先遍历) 一层层的遍历，结合队列
DFS(深度优先遍历) 先往深走，遇到叶子节点再往回走，递归或者结合栈
前序遍历 中左右
中序遍历 左中右
后序遍历 左右中