🤔力扣好题记录

# 🤔力扣好题记录

# 前端算法与数据结构面试：底层逻辑解读与大厂真题训练 (opens new window) 刷题日记

22/1/30 大三寒假过半，备战春招，系统地再刷一下修言老师的这本小册！（同时还在写每日一题&总结HOT100之后准备刷的题）

看到这里的有缘人也许可以参考下这条复习路径？

# day1 chapter1-6 基础知识学习

1/30打卡！停工不停学！刷题准备走起来！

数组 (opens new window)基础知识
栈、队列 (opens new window)基础知识；数组的增、删API；链表基础知识
树以及简单的二叉树前中后序遍历
时间复杂度、空间复杂度

# day2 chapter7 数组

1/31 2/1打卡！除夕打卡的狠人在此！数组老朋友了啊，再来刷一遍这些经典题！

# 1. 两数之和 (opens new window)

哈希表

var twoSum = function(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    let res = target - nums[i];
    if (map.has(res)) {
      return [map.get(res), i]
    } else {
      map.set(nums[i], i);
    }
  }
};

# 88. 合并两个有序数组 (opens new window)

双指针遍历-开辟额外空间

var merge = function(nums1, m, nums2, n) {
  const ans = [];
  let i = 0, j = 0;
  while(i < m || j < n) {
    if (nums1[i] <= nums2[j] && i < m || j === n) {
      ans.push(nums1[i]);
      i++;
    } else {
      ans.push(nums2[j])
      j++;
    }
  }
  for (let [index, item] of ans.entries()) {
    nums1[index] = item
  }
};

反向双指针
- 很巧妙的方法，从尾部开始往前遍历，使用了else让自己减少讨论了两种情况：
  - p1到头
  - p2到头
- 空间复杂度优于第一种方法

var merge = function(nums1, m, nums2, n) {
  let p1 = m - 1, p2 = n - 1;
  for (let i = m + n - 1; i >= 0; i--) {
   
    if (nums1[p1] >= nums2[p2] || p2 === -1) {
      nums1[i] = nums1[p1];
      p1--;
    } else {
      nums1[i] = nums2[p2];
      p2--;
    }
  }
};

# 15. 三数之和 (opens new window)

对撞指针——“有序”和“数组”。没错，见到这两个关键字，立刻把双指针法调度进你的大脑内存。普通双指针走不通，立刻想对撞指针！

定指针+对撞双指针
- 巧妙利用对撞双指针
- 重复元素的跳过是重点

var threeSum = function(nums) {
  const ans = []
  nums.sort((a, b) => a - b); 
  for (let i = 0; i < nums.length - 2; i++) {
    // 每轮固定的指针i 与一对反向指针 m n 一起进行遍历寻找 注意应该避免重复！
    if (i >= 1 && nums[i - 1] === nums[i]) {
      // 注意这里也要做一个防止重复的操作！
      continue;
    }
    let m = i + 1, n = nums.length - 1;
    while(m < n) {
      let sum = nums[m] + nums[n] + nums[i];
      if (sum === 0) {
        ans.push([nums[m], nums[n], nums[i]]);
        // 防止答案重复 移动双指针时需要做验证
        m++;
        while (nums[m] === nums[m - 1]) {
          m++;
        }
        n--;
        while (nums[n] === nums[n + 1]) {
          n--;
        }
      }

      // 对撞指针相向而行 
      else if (sum < 0) {
        m++;
        while (nums[m] === nums[m - 1]) {
          m++;
        }
      }
      else if (sum > 0) {
        n--;
        while (nums[n] === nums[n + 1]) {
          n--;
        }
      }
    }
  }
  return ans;
};

# day3 chapter8 字符串

2/1 2/2打卡失败😶‍🌫️低估了自己的低迷状态

2/3打卡！

# 344. 反转字符串 (opens new window)

对撞双指针+解构赋值

var reverseString = function(s) {
  let p1 = 0, p2 = s.length - 1;
  while(p1 < p2) {
    [s[p1], s[p2]] = [s[p2], s[p1]];
    p1++;
    p2--;
  }
  return s;
};

# 680. 验证回文字符串 Ⅱ (opens new window)

对撞双指针+最多删除一个字符情况下的巧妙判断
- 字符串题干中若有“回文”关键字，那么做题时脑海中一定要冒出两个关键字——对称性 和 双指针。这两个工具一起上，足以解决大部分的回文字符串衍生问题。
- 转变成 局部回文 问题

var validPalindrome = function(s) {
  let p1 = 0, p2 = s.length - 1;
  while (p1 < p2 && s[p1] === s[p2]) {
    p1++;
    p2--;
  }
  
  if (!isPlaindrome(s, p1 + 1, p2) && !isPlaindrome(s, p1, p2 - 1)) {
    return false;
  } else {
    return true;
  }
};
// 判断字符串str从索引i至索引j是否回文
var isPlaindrome = function(str, i, j) {
  while (i < j) {
    if (str[i] !== str[j]) {
      console.log(str[i], str[j])
      return false;
    }
    i++;
    j--;
  }
  return true;
}

# 211. 添加与搜索单词 - 数据结构设计 (opens new window)

RegExp+哈希表记录对应长度数组

var WordDictionary = function() {
  this.map = new Map();
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
  if(this.map.has(word.length)) {
    this.map.set(word.length, [...this.map.get(word.length), word]);
  } else {
    this.map.set(word.length, [word])
  }
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
  const len = word.length;
  if(!this.map.has(len)) {
    return false;
  }
  if (!word.includes('.')) {
    return this.map.get(len).includes(word);
  }

  // 如果search传入了包含 '.' 的字符串 则创建正则表达式对象 使用test API进行匹配
  const reg = new RegExp(word);

  // 对应数组长度中有一个匹配正则表达式的字符串 即返回true
  return this.map.get(len).some((item) => {
    return reg.test(item)
  })
};

# 8. 字符串转换整数 (atoi) (opens new window)

这道正则忒复杂了我正则基础还不太会呢先跳过了😶‍🌫️

# day4 chapter9 链表

2/5打卡！

# 21. 合并两个有序链表 (opens new window)

题解&图解：【数据结构入门每日刷题打卡15/33】经典环形链表问题——合并两个有序链表 - 合并两个有序链表 (opens new window)

开辟额外空间存储+虚拟头结点

var mergeTwoLists = function(l1, l2) {
  let dummyHead = new ListNode(0);
  let ans = dummyHead;
  while (l1 !== null && l2 !== null) {
    if (l1.val <= l2.val) {
      ans.next = l1;
      l1 = l1.next;
    } else {
      ans.next = l2;
      l2 = l2.next;
    }
    ans = ans.next;
  }
  ans.next = l1 === null ? l2 : l1;
  return dummyHead.next;
};

简洁递归法
- 着重思考最内层（【2】）（递归调用栈栈顶的函数）即可（也就是达成边界条件的那一步）！

var mergeTwoLists = function(list1, list2) {
  if (list1 === null) {
    // 👇【2】抵达最内层-递归调用栈栈顶函数返回值-递结束 开始归
    return list2;
  }
  if (list2 === null) {
    return list1;
  }
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    // list2.next=返回值
    return list1;
  } else {
    // 👇【1】递的过程——将对应函数放入递归调用栈
    list2.next = mergeTwoLists(list1, list2.next);
    // 👇【3】归的过程——按序从递归调用栈出栈并执行函数
    // list1.next=返回值
    return list2;
  }
};

# 83. 删除排序链表中的重复元素 (opens new window)

经典删除问题

var deleteDuplicates = function(head) {
  let cur = head;
  while (cur !== null && cur.next !== null) {
    if (cur.val === cur.next.val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }
  return head;
};

补充一道很有趣的题~

# 237. 删除链表中的结点 (opens new window)

很有趣的一道题！你真的很熟悉链表的删除嘛？来试一试~
var deleteNode = function(node) {
    // 本题关键：无法要删除“node”，没关系！把node.next赋值给node，再删掉node.next即可！
    let nodeNext = node.next;// 暂存下一个结点
    node.val = nodeNext.val;// 把node.next赋值给node
    node.next = nodeNext.next;// 再删掉node.next
};
评论区热评——

很贴切有木有！！

# 82. 删除排序链表中的重复元素 II (opens new window)

一趟遍历,巧妙删除
- 时刻注意跳过重复元素因为要全删所以不要着急进行 cur = cur.next 删掉所有相邻的元素（eg:55566）再往下挪

var deleteDuplicates = function(head) {
  let dummyHead = new ListNode(0, head);
  let cur = dummyHead;
  // 当 cur 的后面有至少两个结点时 进行判断 否则（不可能重复了）直接返回结果
  while (cur.next && cur.next.next) {
    if (cur.next.val === cur.next.next.val) {
      const del = cur.next.val;
      // 这里注意要判断cur.next不为null 要不然遍历到尾部会报错！
      while (cur.next && cur.next.val === del) {
        cur.next = cur.next.next;
      }
    } else {
      cur = cur.next;
    }
  }
  return dummyHead.next;
};

# 力扣HOT100

力扣HOT100 公认的必刷题，面试中很容易遇到原题的题目们~

除了快速突击面试以外，还可以用于检验我们对这些专题的掌握程度~

# 数组 (opens new window)

# 1. 两数之和 (opens new window)

哈希表

var twoSum = function(nums, target) {
    let map = new Map()
    for(let i = 0; i < nums.length; i++) {
        if(map.has(target - nums[i])) {
            return [i, map.get(target - nums[i])]
        }
        else {
            map.set(nums[i], i)
        }
    }
};

# 53. 最大子数组和 (opens new window)

贪心法

var maxSubArray = function(nums) {
    let maxSum = nums[0]
    let sum = nums[0]
    for(let i = 1; i < nums.length; i++) {
        if(sum < 0) {
            sum = nums[i]
        }
        else {
            sum += nums[i]
        }
        maxSum = Math.max(sum, maxSum)
    }
    return maxSum
};

# 121. 买卖股票的最佳时机 (opens new window)

贪心法

var maxProfit = function(prices) {
    let maxProfit = 0
    let minPrice = prices[0]
    for (let i = 0; i < prices.length - 1; i++) {
        minPrice = minPrice < prices[i] ? minPrice : prices[i]
        maxProfit = Math.max(maxProfit, prices[i + 1] - minPrice)
    }
    return maxProfit
};

# 136. 只出现一次的数字 (opens new window)

异或位运算

var singleNumber = function(nums) {
    let ans = nums[0]
    for (let i = 1; i < nums.length; i++) {
        ans ^= nums[i]
    }
    return ans
};

# 169. 多数元素 (opens new window)

# 283. 移动零 (opens new window)

# 448. 找到所有数组中消失的数字 (opens new window)

# 字符串 (opens new window)

# 125. 验证回文串 (opens new window)

hot100里没有但我觉得挺好也比较热门的一题 hot100中字符串easy 唯一的一题是有效的括号，我把它算在“栈”里了

细致地分情况讨论+对撞双指针

var isPalindrome = function(s) {
  let p1 = 0, p2 = s.length - 1;
  s = s.toLowerCase();
  while (p1 < p2) {
    if (isLetter(s[p1]) && isLetter(s[p2]) && s[p1] !== s[p2]) {
      return false;
    } else if (!isLetter(s[p1])) {
      p1++;
      continue;
    } else if (!isLetter(s[p2])) {
      p2--;
      continue;
    }
    p1++;
    p2--;
  }
  return true;
};
var isLetter = function(str) {
  return ('a' <= str && str <= 'z') || ('0' <= str && str <= '9') 
}

利用简单正则表达式+反转判断

var isPalindrome = function(s) {
  // 利用正则表达式筛选出来符合条件的字符串,得到一个字符串数组
  let str = s.toLowerCase().match(/[a-z0-9]+/g);
  if (!str) {
    return true;
  }
  let validStr = str.join("");
  return validStr.split("").reverse().join("") === validStr;
};

# 链表 (opens new window)

# 21. 合并两个有序链表 (opens new window)

迭代法 按照题意使用一个preHead 将两个链表按序串联起来

var mergeTwoLists = function(list1, list2) {
    let preHead = new ListNode(0)
    let cur = preHead
    while(list1 !== null && list2 !== null) {
        if(list1.val <= list2.val) {
            cur.next = list1
            list1 = list1.next
        }
        else {
            cur.next = list2
            list2 = list2.next
        }
        cur = cur.next
    }
    cur.next = list1 === null ? list2 : list1
    return preHead.next
};

# 141. 环形链表 (opens new window)

快慢指针

var hasCycle = function(head) {
    let slow = head
    let fast = head
    while(fast !== null && fast.next !== null) {
        slow = slow.next
        fast = fast.next.next   
        if(slow === fast) {
            return true
        } 
    }  
    return false
};

# 160. 相交链表 (opens new window)

# 206. 反转链表 (opens new window)

一前一后的双指针

var reverseList = function(head) {
    let pre = null
    let cur = head
    while(cur !== null) {
        let next = cur.next
        // 下面三步让局部的两个结点指向反转&各自前进一个结点
        cur.next = pre
        pre = cur
        cur = next
    }
    return pre
};

# 234. 回文链表 (opens new window)

# 2. 两数相加 (opens new window)

# 19. 删除链表的倒数第 N 个结点 (opens new window)

# 二叉树 (opens new window)

# 94. 二叉树的中序遍历 (opens new window)思路 (opens new window)

DFS递归

var inorderTraversal = function(root) {
    const res = []
    function dfs(root) {
        if(root === null) {
            return;
        }
        dfs(root.left)
        res.push(root.val)
        dfs(root.right)
    }
    dfs(root)
    return res
};

# 101. 对称二叉树 (opens new window)

DFS递归

var isSymmetric = function(root) {
    function dfs(left, right) {
        if(left === null && right === null) {
            return true
        }
        if(left === null || right === null) {
            return false
        }
        if(left.val !== right.val) {
            return false;   
        }
        return dfs(left.left, right.right) && dfs(left.right, right.left)
    }
    return dfs(root.left, root.right)
};

# 104. 二叉树的最大深度 (opens new window)

DFS递归

var maxDepth = function(root) {
    function dfs(root) {
        if(root === null) {
            return 0
        }
        let leftDepth = dfs(root.left)
        let rightDepth = dfs(root.right)
        return Math.max(leftDepth, rightDepth) + 1
    }
    return dfs(root)
};

# 226. 翻转二叉树 (opens new window)

DFS递归

var invertTree = function(root) {
    function dfs(root) {
        if(root === null) {
            return null// 到达最底部时需要返回null-意味着空节点
        }
        // 将当前遍历到的root的左右孩子换位置
        [root.left, root.right] = [dfs(root.right), dfs(root.left)]
        return root
    }
    return dfs(root)
};

# 543. 二叉树的直径 (opens new window)

DFS递归

var diameterOfBinaryTree = function(root) {
    let ans = 1
    // 求深度的DFS方法，顺带着把ans（最大直径）更新了~
    function dfs(root) {
        if(root === null) {
            return 0
        }
        let left = dfs(root.left)
        let right = dfs(root.right)
        ans = Math.max(ans, left + right + 1)
        return Math.max(left, right) + 1
    }
    dfs(root)
    return ans - 1
};

# 栈相关 (opens new window)

# 20. 有效的括号 (opens new window)

哈希表+栈

var isValid = function(s) {
    const map = new Map([
        ['{', '}'],
        ['[', ']'],
        ['(', ')'],
    ])
    const stack = []
    for(let str of s) {
        if(map.has(str)) {
            stack.push(str)
        }
        else {
            if(map.get(stack.pop()) !== str) {
                return false
            }
        }
    }
    return !stack.length
};

# 94. 二叉树的中序遍历 (opens new window)思路 (opens new window)

借助栈的DFS迭代

var inorderTraversal = function(root) {
    const stack = []
    const res = []
    while(stack.length || root !== null) {
        // 01 DFS到最深层(最深处的左孩子节点) 栈中的顺序为中序遍历的结果
        while(root !== null) {
            stack.push(root)
            root = root.left
        }
        // 02 将栈中内容依次弹出
        root = stack.pop()
        res.push(root.val)
        // 03 遍历右子树
        root = root.right
    }
    return res
};

# 155. 最小栈 (opens new window)

一趟遍历法

var MinStack = function() {
  this.stack = []  
};

MinStack.prototype.push = function(val) {
    this.stack.push(val)
};

MinStack.prototype.pop = function() {
    this.stack.pop()
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};

MinStack.prototype.getMin = function() {
    const { stack } = this// 解构赋值~
    let min = stack[0]
    for(let i = 1; i < stack.length; i++) {
        min = stack[i] < min ? stack[i] : min
    }
    return min
};

辅助单调栈-空间换时间

// 初始化栈结构
var MinStack = function() {
    this.stack = [];
    this.stack2 = [];// 辅助d栈
};
// 入栈操作
MinStack.prototype.push = function(val) {
    this.stack.push(val);
    // 本方法的关键——如何维护辅助作用的单调栈！
        // 当辅助栈为空时入栈val & val比辅助栈栈顶元素小时入栈
    if(this.stack2.length === 0 || val <= this.stack2[this.stack2.length - 1]){
        this.stack2.push(val);
    }
};

// 出栈操作
MinStack.prototype.pop = function() {
    if(this.stack.pop() === this.stack2[this.stack2.length - 1]){
        // 若出栈元素和目前辅助栈栈顶元素相同则将其从辅助栈出栈
        this.stack2.pop();
    }
};

// 获取栈顶元素
// 这里没变化~
MinStack.prototype.top = function() {
    if(this.stack === null || this.stack.length === 0){
        // 熟练地完成边界条件判断可能不是必要地，但在不少时候可能会救你一命XD
        return;
    }
    return this.stack[this.stack.length - 1];
};

// 获取栈中最小值
MinStack.prototype.getMin = function() {
    return this.stack2[this.stack2.length - 1];// 直接取栈顶元素即可！
};

# 队列相关 (opens new window)

# 剑指Offer

待启动…

# 每日一题

有些题目做起来还是挺有收获的~这里记录下比较有收获的每日一题吧 2021/1/6

# 71. 简化路径 (opens new window) 22/1/6

栈+字符串

// 挺不错的一道栈相关的题目 用时二十分钟左右
var simplifyPath = function(path) {
    let pathS = path.split('/')
    let stack = []
    for (let item of pathS) {
        if (item === '.' || !item) {
            continue
        }
        else if (item === '..') {
            stack.pop()
        }
        else {
            stack.push(DataTransferItem)
        }
    }
    console.log(stack)
    // let res = stack.join('')
    // return !res ? "/" : res 
    return '/' + stack.join('/')// 这个方法不错~解决了 stack为空时无返回值的问题~
};

# 747. 至少是其他数字两倍的最大数 (opens new window) 22/1/14

简单模拟题

记录最大值、次大值、最大值下标即可~

这里最开始还想着搞单调栈搞优先队列后来发现就需要给两个元素做单调即可！考虑不够全面哦！

var dominantIndex = function(nums) {
    let gg = -1, dd = -1// 没错就是哥哥和弟弟
    let index = 0// 记录最大值下标
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > gg) {
            dd = gg// 时刻确认弟弟是次大值
            gg = nums[i]
            index = i
        } else if (nums[i] > dd) {
            dd = nums[i]
        }
    }
    return gg >= dd * 2 ? index : -1
};

# 539. 最小时间差 (opens new window) 22/1/18

排序+挨个计算对字符串的操作要熟练

var findMinDifference = function(timePoints) {
    timePoints.sort()
    let t0Minutes = getMinutes(timePoints[0]);
    let preMinutes = t0Minutes;
    let ans = Number.MAX_VALUE;
        for (let i = 1; i < timePoints.length; ++i) {
        const minutes = getMinutes(timePoints[i]);
        ans = Math.min(ans, minutes - preMinutes); // 相邻时间的时间差
        preMinutes = minutes;
    }
    ans = Math.min(ans, t0Minutes + 1440 - preMinutes); // 首尾时间的时间差
    return ans
};
// 根据 "xx:xx" h
const getMinutes = (t) => {
    return ((t[0].charCodeAt() - '0'.charCodeAt()) * 10 + (t[1].charCodeAt() - '0'.charCodeAt())) * 60 + (t[3].charCodeAt() - '0'.charCodeAt()) * 10 + (t[4].charCodeAt() - '0'.charCodeAt());
}

# 1996. 游戏中弱角色的数量 (opens new window) 22/1/28

巧用排序

先将攻击力降序防御力升序然后再遍历如果防御力有低的就弱角色（攻防都比最高的那个低）+1~

var numberOfWeakCharacters = function(properties) {
  // 攻击力相同->防御力低的在前面（防御力升序排列！）；攻击力不相同->攻击力高的在前面（攻击力降序排列！）
  properties.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]);
  let count = 0;
  let max = -1;
  for (let i = 0; i < properties.length; i++) {
    if (properties[i][1] < max) {
      count += 1;
    }
    max = Math.max(max, properties[i][1])
  }
  return count;
};

# 884. 两句话中的不常见单词 (opens new window) 22/1/30

哈希表

var uncommonFromSentences = function(s1, s2) {
  let arr = [...s1.split(" "), ...s2.split(" ")]
  let ans = []
  // 使用map记录两个句子中单词是否独一无二 1-只出现过一次 2-出现过多次
  let map = new Map()
  for (let i = 0; i < arr.length; i++) {
    if (!map.has(arr[i])) {
      map.set(arr[i], 1)
    } else {
      map.set(arr[i], 2)
    }
  }
  // map中值为0的值即为“不常见单词”
  for (let letter of map.keys()) {
    if (map.get(letter) === 1) {
      ans.push(letter)
    }
  }
  return ans
};

# 1763. 最长的美好子字符串 (opens new window) 22/2/1

新年快乐！

【注释详细】最长的美好子字符串 - （做完我近期用时）“最长”的一道easy题，迎接“美好”的一年！ - 最长的美好子字符串 (opens new window)

暴力枚举+位运算-数据规模并不大

var longestNiceSubstring = function(s) {
  // 枚举法
  const n = s.length;
  let ans = "";
  let maxLen = 0;
  for (let i = 0; i < n; i++) {
    // lower记录小写字母 upper记录大写字母 利用位运算，判断是否大小写字母同时在字符串中出现
    let lower = 0;
    let upper = 0;
    // 以s[i]为首字母的子字符串检查
    for (let j = i; j < n ; j++) {
      /** 这种分别对大小写字母神奇的位运算可以保证——
        * 小写字母转换得到的lower值只有“对应大写字母转换得到的upper值”才能匹配
      */ 
      if ('a' <= s[j] && s[j] <= 'z') {
        lower |= 1 << (s[j].charCodeAt() - 'a'.charCodeAt());
      } else {
        upper |= 1 << (s[j].charCodeAt() - 'A'.charCodeAt());
      }

      // 符合“大写小写同时存在” 则对答案进行更新
      if (lower === upper && j - i + 1 > maxLen) {
        maxLen = j - i + 1;
        ans = s.slice(i, j + 1);
      }
    }
  }
  return ans
};

暴力枚举+巧妙哈希

利用Set表不存储重复键的原理，当只存储大写字母的set2的长度为存储全部字母（大写&小写）的两倍时——满足美好字符串的要求

var longestNiceSubstring = function(s) {
  // 枚举法
  const n = s.length;
  let ans = "";
  let maxLen = 0;
  for (let i = 0; i < n; i++) {
    let set1 = new Set();
    let set2 = new Set();
    // 以s[i]为首字母的子字符串检查
    for (let j = i; j < n ; j++) {
      // 巧用哈希表判断大小写字母是否同时存在
      set1.add(s[j])
      set2.add(s[j].toUpperCase())
  
      // 符合“大写小写同时存在” 则对答案进行更新
      if (set1.size === 2 * set2.size && j - i + 1 > maxLen) {
        maxLen = j - i + 1;
        ans = s.slice(i, j + 1);
      }
    }
  }
  return ans;
};

# 1414. 和为 K 的最少斐波那契数字数目 (opens new window) 2/3

贪心法
- 这题对原理的证明 (opens new window)比较困难记个结论好了~
  - 简单来说是：m个大的能合成k，为什么还要用n个小的来合成呢？
  - 贪心一般找找反例，把题做出来就行了~
- 只要fn-1+fn-2<=fn就能用贪心，不满足就动态规划

var findMinFibonacciNumbers = function(k) {
  /** 
   * 这题主要难在证明——证明要用什么样的贪心思想获取可行解
   * [1]首先找到所有不超过 k 的斐波那契数字
   * [2]然后每次贪心地选取不超过 k 的最大斐波那契数字，将 k 减去该斐波那契数字
   * [3]重复该操作直到 k 变为 0，此时选取的斐波那契数字满足和为 k 且数目最少。
   */ 
  let fb = [];
  fb[0] = 1;
  fb[1] = 1;
  // [1]首先找到所有不超过 k 的斐波那契数字
  for (let i = 2; fb[i - 1] + fb[i - 2] <= k; i++) {
    fb[i] = fb[i - 1] + fb[i - 2];
  }
  let ans = 0;
  // 重复[2]操作直到 k 变为 0
  for (let i = fb.length - 1; i >= 0; i--) {
    if (k - fb[i] === 0) {
      ans++;
      return ans;
    } else if (k - fb[i] > 0) {
      ans++;
      k -= fb[i];
    }
  }
};

# 1725. 可以形成最大正方形的矩形数目 (opens new window) 2/4

一趟遍历法
- 第一次写这题遍历了两次，做法不够优雅！参考官方题解的一趟遍历模拟，操作二维数组更熟练了

var countGoodRectangles = function(rectangles) {
  let maxLen = 0,ans = 0;
  for (let rectangle of rectangles) {
    const a = rectangle[0], b = rectangle[1]
    const l = Math.min(a, b);
    if (l === maxLen) {
      ans++;
    } else if (l > maxLen) {
      ans = 1;
      maxLen = l;
    }
  }
  return ans;
};

# 1748. 唯一元素的和 (opens new window) 2/6

计数哈希表一行写法！

var sumOfUnique = function(nums) {
    const cnt = new Map();
    for (const num of nums) {
        cnt.set(num, (cnt.get(num) || 0) + 1);
    }
    let ans = 0;
    for (const [num, c] of cnt.entries()) {
        if (c === 1) {
            ans += num;
        }
    }
    return ans;
};

记录每个元素的状态 + 一次遍历
- 0：该元素尚未被访问；
- 1：该元素被访问过一次；
- 2：该元素被访问超过一次。

var sumOfUnique = function(nums) {
    let ans = 0;
    const state = new Map();
    for (const num of nums) {
        if (!state.has(num)) {
            ans += num;
            state.set(num, 1);
        } else if (state.get(num) === 1) {
            ans -= num;
            state.set(num, 2);
        }
    }
    return ans;
};

# 2006. 差的绝对值为 K 的数对数目 (opens new window) 2/9

超级优质哈希表写法
- 之后写哈希表都这么写吧！少一些判断，多一些优雅！
- 优雅的哈希表解法（优雅地创建哈希表，优雅地一趟遍历解题） - 差的绝对值为 K 的数对数目 (opens new window)

var countKDifference = function(nums, k) {
  const map = new Map();
  let ans = 0;
  for (let i = 0; i < nums.length; i++) {
    /**
     * 每次迭代都回头看看前面的元素有没有符合要求的 
     * nums[i] - 符合要求的键 = k
     * 符合要求的键 - nums[i] = k
     * @example
     * [1,2,2,1] k = 1 遍历完之后 Map(2) { 1 => 1, 2 => 2 }
     * 如果末尾再加入一个1 则答案+map.get(2)
     */ 
    ans += (map.get(nums[i] - k) || 0) + (map.get(nums[i] + k) || 0); 
    map.set(nums[i], (map.get(nums[i]) || 0) + 1);
  }
  return ans;
};

# 2100. 适合打劫银行的日子 (opens new window) 3/6

动态规划 - 来自官方题解
- time = 2
  - left: [4, 3. √1]
  - right: [√1, 3, 4]
- 构造出如上的数组然后进行遍历

function goodDaysToRobBank(security: number[], time: number): number[] {
  // 预先计算出第 i 天前警卫数目连续非递增的天数以及第 i 天后警卫数目连续非递减的天数即可判断第 i 天是否适合打劫
  const n = security.length;
  const left = new Array(n).fill(0);
  const right = new Array(n).fill(0);
  for (let i = 1; i < n; i++) {
    if (security[i] <= security[i - 1]) {
      left[i] = left[i - 1] + 1;
    }
    if (security[n - i - 1] <= security[n - i]) {
      right[n - i - 1] = right[n - i] + 1; 
    }
  }

  const ans = [];
  for (let i = time; i < n - time; i++) {
    if (left[i] >= time && right[i] >= time) {
      ans.push(i);
    }
  }
  return ans;
};

# 599. 两个列表的最小索引总和 (opens new window) 3/14

哈希表

function findRestaurant(list1: string[], list2: string[]): string[] {
  const map = new Map();
  // 第一遍初始化字典 两个列表的比较都可以使用两次循环来完成~ 而不是双重循环！
  for (let i = 0; i < list1.length; i++) {
    map.set(list1[i], i);
  }
  let minGap = Number.MAX_SAFE_INTEGER;
  const ans = [];
  // 第二遍遍历list2 获取ans
  for (let j = 0; j < list2.length; j++) {
    if (map.has(list2[j])) {
      let gap = map.get(list2[j]) + j; 
      if (minGap > gap) {
        minGap = gap;
        ans.length = 0; // 清空ans数组
        ans.push(list2[j]);
      } else if (minGap === gap) {
        ans.push(list2[j]);
      }
    }
  }
  return ans;
};

# 力扣周赛

# 22/1/16单周赛

# 5980. 将字符串拆分为若干长度为 k 的组 (opens new window)

简单模拟

很简单也很棒的字符串题目~

之前做字符串的题总是先将其转变为数组再去思考，就很复杂！这样子多简单！

var divideString = function(s, k, fill) {
    const ans = []
    let str = ""
    for (const word of s) {
        str += word
        if (str.length === k) {
            ans.push(str)
            str = ''
        }
    }
    if (str.length > 0 && str.length < k) {
        while (str.length < k) {
            str += fill
        }
        ans.push(str)
    }
    return ans
};

# 5194. 得到目标值的最少行动次数 (opens new window)

逆向思维

var minMoves = function(target, maxDoubles) {
    let count = 0
    while (target !== 1) {
        // 能整除（偶数） 就整除
        if (target % 2 === 0 && maxDoubles > 0) {
            target /= 2
            maxDoubles -= 1
            count++
        }
        // 暂且无法整除（是奇数） 但是还有整除的机会
        else if (maxDoubles > 0) {
            target -= 1
            count++
        }
        // 已经没有次数了，就直
        else {
            count += target - 1
            target = 1
        }   
    }
    return count
};

# 22/1/30 单周赛

# 5993. 将找到的值乘以 2 (opens new window)

利用find API进行循环模拟

var findFinalValue = function(nums, original) {
  let flag = nums.find((num) => num === original)
  while(flag !== undefined) {
    original *= 2
    flag = nums.find((num) => num === original)
  }
  return original
};

# 5981. 分组得分最高的所有下标 (opens new window)

这题竞赛时候没想出来思路，，感觉暴力解应该时间和空间都会爆炸，就没写勒

每个索引处存了0的情况和1的情况

好巧妙的思路！学习到了！

var maxScoreIndices = function(nums) {
  let ans = [], len = nums.length;
  // 存储从0开始到index处（不包含）（所以初次迭代过程arr1[i+1]被赋值）有多少个0
  const arr1 = new Array(len + 1).fill(0)
  // 存储索引从len-1到index(包含)处有多少个1
  const arr2 = new Array(len + 1).fill(0)
  // 左边0的数量 左->右
  let sum1 = 0
  for (let i = 0; i < len; i++) {
    if (nums[i] === 0) {
      sum1++;
    }
    arr1[i + 1] = sum1;
  }
  // 右边1的数量 右->左
  let sum2 = 0
  for (let i = len - 1; i >= 0; i--) {
    if (nums[i] === 1) {
      sum2++;
    }
    arr2[i] = sum2;
  }
  // 根据arr1和arr2计算分组得分
  let sum = 0, max = 0
  for (let i = 0; i <= len; i++) {
    sum = arr1[i] + arr2[i]
    if (sum === max) {
      ans.push(i);
    }
    if (sum > max) {
      ans = []
      ans.push(i)
    }
    max = max > sum ? max : sum;
  }
  return ans
};

# 5994. 查找给定哈希值的子串 (opens new window)

这题俺放弃了orz

下次做类似的题（涉及到Math.pow(xx, xx)时，注意不能出现太大的数 2**好几十这样）

最大值越界了，，

var subStrHash = function(s, power, modulo, k, hashValue) {
  for (let i = 0; i <= s.length - k; i++) {
    let str = s.slice(i, i + k)
    let calcu = calcuHash(str, power, modulo)
    if (calcu === hashValue) {
      return str
    }
  }
};
var calcuHash = function(str, power, modulo) {
  let count = 0
  for(let i = 0; i < str.length; i++) {
    let hash = str[i].charCodeAt() - 'a'.charCodeAt() + 1;
    let counting = hash * (Math.pow(power, i))
    let higher = Math.floor((count + counting) / modulo)
    count += counting - higher * modulo
    console.log('count:', count,'每轮给count加上:', counting - higher * modulo,'消除越界用的因数:', higher)
  }
  console.log(str, count % modulo)
  return count % modulo;
}

得出结论不能硬算😂

换BigInt数据类型暴力解再挣扎一下

由于在 Number (opens new window) 与 BigInt 之间进行转换会损失精度，因而建议仅在值可能大于2^53^ 时使用 BigInt 类型，并且不在两种类型之间进行相互转换。

居然还是不行？？

var subStrHash = function(s, power, modulo, k, hashValue) {
  for (let i = 0; i <= s.length - k; i++) {
    let str = s.slice(i, i + k)
    let calcu = calcuHash(str, power, modulo)
    console.log(calcu)
    if (calcu === BigInt(hashValue)) {
      return str
    }
  }
};
var calcuHash = function(str, power, modulo) {
  let count = BigInt(0)
  for(let i = 0; i < str.length; i++) {
    let hash = str[i].charCodeAt() - 'a'.charCodeAt() + 1;
    let counting = hash * (Math.pow(power, i))
    count += BigInt(counting)
    console.log(count)
  }
  console.log(str, count % BigInt(modulo))
  return count % BigInt(modulo);
}

测试用例

貌似仍然是丧失了精度。。

前端必会算法技巧 22年第一季度的每日一题

前端知识库@敲代码的小提琴手

🤔力扣好题记录

# 🤔力扣好题记录

# 前端算法与数据结构面试：底层逻辑解读与大厂真题训练 (opens new window) 刷题日记

# day1 chapter1-6 基础知识学习

# day2 chapter7 数组

# day3 chapter8 字符串

# day4 chapter9 链表

# 力扣HOT100

# 剑指Offer

# 每日一题

# 71. 简化路径 (opens new window) 22/1/6

# 747. 至少是其他数字两倍的最大数 (opens new window) 22/1/14

# 539. 最小时间差 (opens new window) 22/1/18

# 1996. 游戏中弱角色的数量 (opens new window) 22/1/28

# 884. 两句话中的不常见单词 (opens new window) 22/1/30

# 1763. 最长的美好子字符串 (opens new window) 22/2/1

# 1414. 和为 K 的最少斐波那契数字数目 (opens new window) 2/3

# 1725. 可以形成最大正方形的矩形数目 (opens new window) 2/4

# 1748. 唯一元素的和 (opens new window) 2/6

# 2006. 差的绝对值为 K 的数对数目 (opens new window) 2/9

# 2100. 适合打劫银行的日子 (opens new window) 3/6

# 599. 两个列表的最小索引总和 (opens new window) 3/14

# 力扣周赛

# 22/1/16单周赛

# 22/1/30 单周赛