工作几年,🤔突然发现自己的短板是对计算机算法与数据结构、计算机基础知识、底层原理了解甚少🤔!!刚开始还挺习惯研究些什么花里胡哨的框架工具。。后面特喵的我顿悟了!!这些初中小学生都会用?🤣
一、会框架那些真没什么竞争优势了🤣
二、大道至简、地基扎实、房子才能造的更扎实、实用且更好看..
三、英语听说读写真的要好(很多好代码都是老外开源的)
四、面试的时候能不用暴力解法(每个语言增删改查的Api运用)就不要用,很明显!!面试官的不考这些
我很幸运能到遇到一个宝藏算法哔哩哔哩 Up主-卡尔: https://programmercarl.com/ 手把手教我写算法-讲的很细致、很好..特此写篇文章来反复总结
动态规划篇-一维动规
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
// 其实递归公式的话,无非是先理解dp[i]或dp[i][j]的含义..
// 而后相继去递推出dp[i] 与dp[i-1]的关系公式..
// 再根据题意去初始化dp[0]的含义..
// 一般来说外层for循环遍历物品,内层for遍历背包或者外层for遍历背包,内层for循环遍历物品都是可以的!
例如118、119及刷的一些简单中等困难题都离不开这5步,有时候主要是还没理解清楚题意及这5步如何推演而来,有思路,但不知从何下手,说明题还是练得少及选了一些不符合自己水平得题目…
数组篇-二分查找法
二分查找-很多人都一看就很简单一写就废,哪怕工作几年的人或者在校生..因为没有彻底搞懂边界条件
保持循环不变量原则:
1、左闭右闭区间
// [left, right]
// right是数组最后一个数的下标,num[right]在查找范围内,是左闭右闭区间
let mid, left = 0, right = nums.length - 1;
// 当left=right时,由于nums[right]在查找范围内,所以要包括此情况
while (left <= right) {
// 位运算 + 防止大数溢出
mid = left + ((right - left) >> 1);
// 如果中间数大于目标值,要把中间数排除查找范围,所以右边界更新为mid-1;如果右边界更新为mid,那中间数还在下次查找范围内
if (nums[mid] > target) {
right = mid - 1; // 去左面闭区间寻找
} else if (nums[mid] < target) {
left = mid + 1; // 去右面闭区间寻找
} else {
return mid;
}
}
return -1;
2、左闭右开区间
let mid, left = 0, right = nums.length;
while (left < right) {
// 位运算 + 防止大数溢出
mid = left + ((right - left) >> 1);
// 如果中间值大于目标值,中间值不应在下次查找的范围内,但中间值的前一个值应在;
// 由于right本来就不在查找范围内,所以将右边界更新为中间值,如果更新右边界为mid-1则将中间值的前一个值也踢出了下次寻找范围
if (nums[mid] > target) {
right = mid; // 去左区间寻找
} else if (nums[mid] < target) {
left = mid + 1; // 去右区间寻找
} else {
return mid;
}
}
数组篇-双指针法(一个循环就能完成的事情)
双指针法(快慢指针法)在数组和链表的操作中是非常常见的,很多考察数组、链表、字符串等操作的面试题,都使用双指针法。
还有三指针法,类似原地合并数组之类的题目:一般都是快指针指需合并数组,慢指针指的是被合并数组双比较,再放入合并指针末尾
for(let i = 0;i < nums.length;i++){
if(nums[i] != val){
nums[k++] = nums[i]
}
}
function removeElement(nums: number[], val: number): number {
let slowIndex: number = 0; let fastIndex:number = 0;
while(fastIndex<nums.length) {
if(nums[fastIndex] !== val) {
nums[slowIndex++] = nums[fastIndex];
}
fastIndex++;
}
return slowIndex;
};
数组篇-滑动窗口(双指针的变向)
- 窗口内是什么?–题意中给到的连续长度数组
- 如何移动窗口的起始位置?—一般窗口内的数组满足不了条件,扩大范围
- 如何移动窗口的结束位置?-for循环里的索引结束指针
let left: number = 0, right: number = 0;
let res: number = nums.length + 1;
let sum: number = 0;
while (right < nums.length) {
sum += nums[right];
if (sum >= target) {
// 不断移动左指针,直到不能再缩小为止
while (sum - nums[left] >= target) {
sum -= nums[left++];
}
res = Math.min(res, right - left + 1);
}
right++;
}
return res === nums.length + 1 ? 0 : res;
数组篇-模拟过程
一般来说搞不懂循环的边界条件就要保持保持循环不变量原则:
// 坚持左闭右开 正方形矩形考虑转多少圈、及中间最后一个数值、还要考虑奇数、偶数的情况!!
while (loop--) {
for (; col < n - offset; col++) {
res[row][col] = count++;
}
// 右列从上到下(左闭右开)
for (; row < n - offset; row++) {
res[row][col] = count++;
}
// 下行从右到左(左闭右开)
for (; col > startY; col--) {
res[row][col] = count++;
}
// 左列做下到上(左闭右开)
for (; row > startX; row--) {
res[row][col] = count++;
}
// 更新起始位置 // 转多少圈
startX++;
startY++;
offset+=2;
}
链表篇-虚拟头节点
// 单链表 C++
struct ListNode {
int val; // 节点上存储的元素
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};
// 单链表 JavaScript
class ListNode {
val;
next = null;
constructor(value) {
this.val = value;
this.next = null;
}
}
// 主要通过虚拟头节点Virtual HeadNode 改变指针指向,如:删B,则改变B->next 指针指向
const data = new ListNode(0, head);
function removeElements(head: ListNode | null, val: number): ListNode |null {
let pre = data, cur = data.next;
while(cur) {
if(cur.val === val) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
}
链表篇-链表基本增删改查
// 创建链表
class LinkNode {
constructor(val, next) {
this.val = val;
this.next = next;
}
}
var MyLinkedList = function () {
this._size = 0;
this._tail = null;
this._head = null;
};
// 从链表尾巴添加节点时要考虑 是否只有一个节点
MyLinkedList.prototype.addAtTail = function(val) {
const node = new LinkNode(val, null);
this._size++;
if(this._tail) {
this._tail.next = node;
this._tail = node;
return;
}
this._tail = node;
this._head = node; //
};
// 按节点索引添加时要考虑 是否只有一个节点、还是说添加到尾节点
MyLinkedList.prototype.addAtIndex = function(index, val) {
if(index > this._size) return;
if(index <= 0) {
this.addAtHead(val);
return;
}
if(index === this._size) {
this.addAtTail(val);
return;
}
// 获取目标节点的上一个的节点
const node = this.getNode(index - 1);
node.next = new LinkNode(val, node.next);
this._size++;
};
// 要考虑尾节点及删除索引节点的前一节点
MyLinkedList.prototype.deleteAtIndex = function(index, val) {
if(index < 0 || index >= this._size) return;
if(index === 0) {
this._head = this._head.next;
// 如果删除的这个节点同时是尾节点,要处理尾节点
if(index === this._size - 1){
this._tail = this._head
}
this._size--;
return;
}
// 获取目标节点的上一个的节点
const node = this.getNode(index - 1);
node.next = node.next.next;
// 处理尾节点
if(index === this._size - 1) {
this._tail = node;
}
this._size--;
}
链表篇
----指针翻转----
// 采用双指针、翻转时记得保存指针指向..
let temp = null, pre = null, cur = head;
while(cur) {
temp = cur.next; // 变量指向的丢失及保存
cur.next = pre;
pre = cur;
cur = temp;
}
----删除第N个节点----
// 要注意的是快慢指针移动时的边界条件..保证的是fast指针走N(N+1)步后,slow指针指向被删N个节点的前一个
while(n--) fast = fast.next;
while (fast.next !== null) {
fast = fast.next;
slow = slow.next
};
----找链表相交的话----
要注意链表A、B的长度,B比A长的话需要交换下头节点与链表长度..
后使链表A移动与链表B指针位置对齐一致,后同时双指针比较
字符串篇
字符串的解法很多是双指针及KMP(太冗余了,先不看!)后续有时间再攻克!!先说双指针..
// 在使用双指针时,会有slow,fast,left,right等指针。。会指向链表、字符串数组,
// 要明白指针遍历时指向哪(赋什么值?什么时候结束?遍历的过程中需要注意什么?这些都是要考虑的..
// 关于三数之和
1、注意的是第一个数是无法大于0(iNum > 0) 以及 结果集里(iNum === nums[i-1])不能重复(反向思维就是nums[i+1)--不能错过,直接continue😓-剪枝
2、还有左右指针同时遍历 left-1与right-1相等的话就要去重
// 关于四数之和
在于如何去重和剪枝
1、要先排序使最小数排最前。。
2、再分别进行i、j、l、r 分别进行去重和剪枝
3、如何区分循环循环条件值及L、R去重
//设计链表
最好有个dummyHead 虚拟头节点-为了方便操作
let cur = new LinkNode(0, this._head);
在添加或删除节点时要判断头和尾,都要获取到头节点前的前一节点要从虚拟头节点开始绕
const node = this.getNode(index - 1);
node.next= new LinkNode(val, node.next);
// 反转字符串中的单词..
双指针运用的极限,
1、移除空格时——快慢指针的边界条件(什么时字符串为null)
2、翻转字符串里每个单词时要暂存当前翻转的位置..
3、翻转字符串快慢指针的起始位置