📕力扣刷题(LeetCode)Reamark

工作几年,🤔突然发现自己的短板是对计算机算法与数据结构、计算机基础知识、底层原理了解甚少🤔!!刚开始还挺习惯研究些什么花里胡哨的框架工具。。后面特喵的我顿悟了!!这些初中小学生都会用?🤣

一、会框架那些真没什么竞争优势了🤣

二、大道至简、地基扎实、房子才能造的更扎实、实用且更好看..

三、英语听说读写真的要好(很多好代码都是老外开源的)

四、面试的时候能不用暴力解法(每个语言增删改查的Api运用)就不要用,很明显!!面试官的不考这些

我很幸运能到遇到一个宝藏算法哔哩哔哩 Up主-卡尔: https://programmercarl.com/ 手把手教我写算法-讲的很细致、很好..特此写篇文章来反复总结

动态规划篇-一维动规

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导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、翻转字符串快慢指针的起始位置

You may also like...

发表回复

您的电子邮箱地址不会被公开。