移除链表元素

发表于2024-04-29更新于2024-04-28

移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

逻辑：分情况讨论
  • 情况1：链表头部元素和val相同
  • 情况2：链表非头部元素和val相同
两种情况统一的方法：在链表头部加一个虚拟节点，从虚拟节点开始，每次对当前节点的 next 元素进行判断。即可统一两种情况

如果cur.next.val == val 让cur的next指向cur.next.next 否则cur = cur.next 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var removeElements = function(head, val) {
  //虚拟节点，虚拟节点的next指向传入链表的头
  const dummy = new ListNode(0);
  dummy.next = head;
  // dummy用于返回最终结果的头部，因此不能改动。只需将其赋值给另一个变量
  let cur = dummy;
  while(cur.next){
    if(cur.next.val == val){
      cur.next =cur.next.next;
    }
    else{
      cur = cur.next;
    }
  }
  return dummy.next;
};

我抽象的将这个过程想象为一个继承的过程，如果cur.next.val == val,那么它没有继承cur的资格，直接找cur.next.next过来进行资格审查。如果通过继承cur。每一代cur都要找继承人，直到最后没人可选。

设计链表

发表于2024-04-29更新于2024-10-10

设计链表

https://leetcode.cn/problems/design-linked-list/description/

单链表

对链表的操作有两种方式：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html#%E6%80%9D%E8%B7%AF

  • 直接使用原来的链表进行操作
  • 设置一个虚拟头结点进行操作

按照索引添加和删除结点要注意遍历得到关键结点应该是index前面的结点
根据索引get对应元素时，遍历得到的关键结点应该是index这个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

var MyLinkedList = function () {
  this.val = null
  this.next = null
}

/**
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function (index) {
  let cur = this
  for (let i = 0; i <= index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return -1
    }
  }
  return cur.val
}

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  newNode.next = this.next
  // 从这一行可以清楚的看出，这是添加虚拟节点的操作方式
  this.next = newNode
}

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  newNode.next = null
  let cur = this
  while (cur.next) {
    cur = cur.next
  }
  cur.next = newNode
}

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  let cur = this
  for (let i = 0; i < index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return
    }
  }
  newNode.next = cur.next
  cur.next = newNode
}

/**
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
  let cur = this
  for (let i = 0; i < index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return
    }
  }
  if (!cur.next) return
  cur.next = cur.next.next
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

双链表

双链表多了一个prev要处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
var MyLinkedList = function () {
  this.prev = null
  this.val = null
  this.next = null
}


MyLinkedList.prototype.get = function (index) {
  let cur = this
  for (let i = 0; i <= index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return -1
    }
  }
  return cur.val
}

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  newNode.next = this.next
  newNode.prev = this
  this.next = newNode
}

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  newNode.next = null
  let cur = this
  while (cur.next) {
    cur = cur.next
  }
  newNode.prev = cur
  cur.next = newNode
}

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  let cur = this
  for (let i = 0; i < index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return
    }
  }
  newNode.next = cur.next
  newNode.prev = cur
  cur.next = newNode
}

/**
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
  let cur = this
  for (let i = 0; i < index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return
    }
  }
  if (!cur.next) return
  cur.next.prev = cur
  cur.next = cur.next.next
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

有序数组的平方

发表于2024-04-28更新于2024-04-26

有序数组的平方

图 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var sortedSquares = function(nums) {
  // 初始化两个指针
  let left =0;
  let right = nums.length - 1;
  // 初始化存放结果的数组
  let res = new Array(nums.length);
  // 从后往前依次填满res
  let point = right
  while(left <= right){
    if(nums[left]**2 > nums[right]**2){
      res[point] = nums[left]**2;
      left++;
    }
    else{
      res[point] = nums[right]**2;
      right--;
    }
    point--
  }
  return res
};

长度最小的有序数组

发表于2024-04-28更新于2024-04-26

长度最小的有序数组

https://leetcode.cn/problems/minimum-size-subarray-sum/description/

图 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var minSubArrayLen = function(target, nums) {
  //初始化
  const n = nums.length;
  let ans = Number.MAX_SAFE_INTEGER;
  let left = 0; right = 0;
  // 核心部分
  while(right<n){  //终止条件
    target -= nums[right];
    while(target <= 0){ // 满足条件的情况
      ans = Math.min(ans, right-left+1);
      target += nums[left];
      left++;
    }
    right++
  }
  return ans === Number.MAX_SAFE_INTEGER ? 0 : ans;
};

移除元素

发表于2024-04-26更新于2024-04-26

移除元素

https://leetcode.cn/problems/remove-element/description/

单指针法

图 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var removeElement = function (nums, val) {
  // 单指针
  let size = nums.length
  let i = 0
  while (i < size) {
    if (nums[i] === val) {
      for (let j = i; j < size; j++) {
        nums[j] = nums[j + 1]
      }
      size--
    } else {
      i++
    }
  }
  return size
}
由于题目没有要求顺序问题，所以不一定要和上面一样，把所有数字往前移。 核心逻辑，发现和目标值一样的数，用数组的最后一位代替当前数，然后数组size-- 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var removeElement = function(nums, val) {
  // 单指针
  let size = nums.length
  let i=0
  while(i<size){
    if (nums[i] === val){
      nums[i] = nums[size-1]
      size--
    }
    else{
      i++
    }
  }
  return size
};

双指针法

图 1

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
var removeElement = function (nums, val) {
  // 双指针法
  let slow =0;
  let fast = 0;
  while(fast < nums.length){
    if(nums[fast] !== val){
      nums[slow] = nums[fast];
      slow++;
    }
    fast++;
  }
  return slow;
}

螺旋矩阵II

发表于2024-04-26更新于2024-04-26

螺旋矩阵II

https://leetcode.cn/problems/spiral-matrix-ii/description/

循环不变量

每次循环处理的区间是有规律的
左闭右开

1
2
3
4
5
6
o . . . 1 o
1 . . . . .
. . . . . .
. . . . . .
. . . . . 1
o 1 . . . o

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var generateMatrix = function(n) {
  // 初始化行列位置
  let startx = 0, starty = 0;
  let end = n-1;
  count = 1;
  let matrix = new Array(n).fill(0).map(()=>new Array(n).fill(0));
  while(Math.floor(n/2)){
    // 这里面的四个for循环戴白哦这上节示意图中的一个o-1的过程
    // 要想通这里的控制过程，并且知道startx，starty，和end的意思，以及他们在每一次循环中如何变化，n如何变化。
    for (let j=starty;j<end;j++){
      matrix[startx][j] = count++;
    }
    for(let i = startx;i<end;i++){
      matrix[i][end] = count++;
    }
    for(let j=end;j>starty;j--){
      matrix[end][j] = count++;
    }
    for(let i=end;i>startx;i--){
      matrix[i][starty] = count++;
    }
    end--;
    startx++;
    starty++;
    n-=2;
  }
  //应对n为奇数的情况
  if (n) {
    matrix[startx][starty] = count;
  }
  return matrix;
};

回文字符串

发表于2024-04-25更新于2024-04-26

回文字符串

什么是回文字符串

回文字符串：是一个正读和反读都一样的字符串。

判断回文字符串的方法

双指针法

这是最直观的方法。我们可以设置两个指针，一个从字符串的开始位置开始，一个从字符串的结束位置开始，然后同时向中间移动。在移动的过程中，如果两个指针指向的字符不相等，那么这个字符串就不是回文字符串。如果两个指针都移动到了中间位置，那么这个字符串就是回文字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let str = 'abba';
let str2 = 'abdc';

function isPalindrome(s) {
  let left = 0,right = s.length-1
  while(left<right){
    if(s[left] != s[right]){
      return false
    }
    left++
    right--
  }
  return true
}

console.log(isPalindrome(str)) // true
console.log(isPalindrome(str2)) // false

反转字符串

我们可以将字符串反转，然后比较反转后的字符串和原字符串是否相等。如果相等，那么这个字符串就是回文字符串。

1
2
3
4
5
6
7
8
9
10
let str = 'abba';
let str2 = 'abdc';

function isPalindrome(s) {
  // 反转字符串
  let reverseStr = s.split('').reverse().join('')
  return s === reverseStr
}
console.log(isPalindrome(str)) // true
console.log(isPalindrome(str2)) // false

递归

我们可以递归地判断一个字符串是否为回文字符串。如果字符串的首字符和尾字符相等，并且去掉首字符和尾字符后的字符串仍然是回文字符串，那么这个字符串就是回文字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let str = 'abba';
let str2 = 'abdc';

function isPalindrome(s) {
  if (s.length <= 1) {
    return true;
  }
  if (s[0] !== s[s.length - 1]) {
    return false;
  }
  return isPalindrome(s.slice(1, s.length - 1));
}

console.log(isPalindrome(str)) // true
console.log(isPalindrome(str2)) // false

滑动窗口

发表于2024-04-22更新于2024-04-26

滑动窗口

算法题应用场景

满足***条件的（计算结果、出现次数），包含最长/最短 子串/子数组/子序列

滑动窗口的思路

图 0

滑动窗口模板

1
2
3
4
5
6
7
8
9
10
// 找最长的模板
// 初始化left，right，result，bestresult
while(右指针到达结尾处){
  窗口逐渐扩大，加入right对应元素，更新result
  while(result不满足要求){
    窗口缩小、移除left对应元素，left右移
  }
  更新最优结果bestresult
  right++
}
1
2
3
4
5
6
7
8
9
10
// 找最短模板
// 初始化left，right，result，bestresult
while(右指针到达结尾处){
  窗口扩大，加入right对应元素，更新result
  while(result满足条件){
    更新最优结果bestresult
    窗口缩小，移除left对应元素，left右移
  }
  right++
}

题目

无重复字符串的子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

重点在于如何判断无重复字符串

判断是否有重复字符串,使用字典map和调整left位置实现无重复子串。

图 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var lengthOfLongestSubstring = function(s) {
  // 初始化
  let p=0;q=0;max=0;
  let map = new Map();
  // 右指针逐渐向结尾处移动
  while(q<s.length){
    // 当结果不满足条件
    if(map.has(s[q])){
      p = Math.max(map.get(s[q])+1,p)
    }
    map.set(s[q],q);
    max = Math.max(max,q-p+1);
    q++;
  }
}

串联所有单词的子串

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
var findSubstring = function(s, words) {
  let res = []
  let wordLen = words[0].length
  let wordNum = words.length
  let wordMap = new Map()
  for (let word of words) {
    wordMap.set(word, wordMap.has(word) ? wordMap.get(word) + 1 : 1)
  }
  // 这里i的设置比较难理解，但是如果理解了后面while中的逻辑，就懂了
  // 从i开始，right直接到最后可能的位置，也就是for中的一次遍历可以找到0或多个res，而不是1个
  for (let i = 0; i < wordLen; i++){
    let left = i
    let right = i
    let window = new Map()
    let count = 0
    while (right + wordLen <= s.length) {
      let w = s.slice(right, right + wordLen)
      right += wordLen
      if (!wordMap.has(w)) {
        window.clear()
        count = 0
        left = right
      } else {
        window.set(w, window.has(w) ? window.get(w) + 1 : 1)
        count++
        while (window.get(w) > wordMap.get(w)) {
          let l = s.slice(left, left + wordLen)
          left += wordLen
          window.set(l, window.get(l) - 1)
          count--
        }
        if (count === wordNum) {
          res.push(left)
        }
      }
    }
  }
  return res
}
Text
1
2
3
4
5
6
7
8
9
10
11
12
13
这段代码的主要逻辑是使用滑动窗口来遍历字符串 s，并检查每个窗口是否包含 words 中的所有单词。

1、let left = i 和 let right = i：初始化滑动窗口的左右边界。
2、let window = new Map()：创建一个哈希映射 window 来存储当前窗口中每个单词出现的次。
3、let count = 0：初始化一个计数器 count 来存储当前窗口中的单词总数。
4、while (right + wordLen <= s.length)：当窗口的右边界加上单词的长度不超过字符串 s 的长度时，继续循环。
5、let w = s.slice(right, right + wordLen)：获取窗口右边界的单词 w。
6、right += wordLen：将窗口的右边界向右移动一个单词的长度。
7、if (!wordMap.has(w))：如果 w 不在 wordMap 中，那么清空 window，重置 count，并将窗口的左边界移动到 right。
8、else：如果 w 在 wordMap 中，那么更新 window 和 count，并检查 window 中 w 的数量是否超过了 wordMap 中 w 的数量。如果超过了，那么从窗口的左边移除单词，直到 window 中 w 的数量不超过 wordMap 中 w 的数量。
9、if (count === wordNum)：如果 count 等于 wordNum，那么将窗口的左边界添加到结果数组 res 中。

这个滑动窗口的策略确保了我们能够有效地遍历字符串 s，并找出所有包含 words 中所有单词的子串的起始索引。

两数相加

发表于2024-04-20更新于2024-04-22

链表的定义和分类

单链表

图 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
自定义链表节点
function ListNode(val,next){
  this.val = (val===undifined ? 0 : val)
  this.next = (next === undefined ? 0 : val)
}

class ListNode{
  val;
  next = null;
  constructor(value){
    this.val = value;
    this.next = null
  }
}
1
2
3
4
5
6
7
8
class ListNode{
  public val : number;
  public next : ListNode|null = null
  constructor(value:number){
    this.val = value;
    this.next = null;
  }
}

双链表

图 1

循环链表

图 2

链表相关题目

两数相加

https://leetcode.cn/problems/add-two-numbers/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var addTwoNumbers = function(l1, l2) {
// 首先新建一个节点
  let res = new ListNode(0)
  // 将节点赋值给变量curr，最终返回res.next就是链表的头，
  // p和q分别是第一个和第二个链表的头
  let curr = res, p = l1, q = l2
  //进位的时候需要的carry
  let carry = 0
  //循环终止的条件是两个链表元素都被遍历完
  while(p != null || q != null){
    // 将长度较短的链表后面补0，直到达到较长链表的长度
    let x = (p === null) ? 0 : p.val
    let y = (q === null) ? 0 : q.val
    // 求对应位置两数的和
    let sum = x + y + carry
    // 和大于0说明需要进位，进位数为sum/2
    carry = Math.floor(sum/10)
    // 保存在链表中的应该是余数，且应该创建一个ListNode
    curr.next = new ListNode(sum%10)
    // 让curr指向curr.next
    curr = curr.next
    // p和q都指向下一个结点
    if (p != null) p = p.next
    if (q != null) q = q.next
  }
  // 最后有可能出现两数的和的长度大于两数最长的哪个数的位数
  if (carry > 0){
    curr.next = new ListNode(carry)
  }
  return res.next
};

Array.from

发表于2024-04-12更新于2024-10-13

Array.from用法

Array.from() 是一个静态方法，它从类数组或可迭代对象创建一个新的数组实例。
以下是一些使用 Array.from() 的例子：

从字符串创建数组：

1
2
3
let str = 'hello';
let arr = Array.from(str);
console.log(arr); // 输出：['h', 'e', 'l', 'l', 'o']

从 Set 创建数组：

1
2
3
let set = new Set(['a', 'b', 'c']);
let arr = Array.from(set);
console.log(arr); // 输出：['a', 'b', 'c']

从 Map 创建数组：

1
2
3
let map = new Map([[1, 'a'], [2, 'b'], [3, 'c']]);
let arr = Array.from(map);
console.log(arr); // 输出：[[1, 'a'], [2, 'b'], [3, 'c']]

从类数组对象创建数组：

1
2
3
let obj = {0: 'a', 1: 'b', 2: 'c', length: 3};
let arr = Array.from(obj);
console.log(arr); // 输出：['a', 'b', 'c']

使用映射函数：

1
2
let arr = Array.from([1, 2, 3], x => x * x);
console.log(arr); // 输出：[1, 4, 9]

在你的代码中，Array.from({length:n},()=>Array.from({length:n},()=>’.’)) 创建了一个 n x n 的二维数组，所有元素都被初始化为 ‘.’。