算法回顾

[bxb100]

Leetcode 错题集

update on Wednesday, April 19th 2023

• [ ] 299. 猜数字游戏 这道只需要不需要用哈希表来复杂化解决

• [ ] 844. 比较含退格的字符串 这道题用栈做了, 实际上没考虑到 # 是从后向前启作用的

• [ ] 394. 字符串解码 想到了使用栈, 但是没有写出来, 这道题应该直接从左到右考虑问题, 使用双栈存储

• [ ] 1046. 最后一块石头的重

  • 先排序一下, 然后取出最大的两个, 然后递归
  • 使用最大堆 PriorityQueue 最大堆的概念可以参看
    • https://zhuanlan.zhihu.com/p/39615266
    • (数组从 1 开始)节点的左子节点为 2 * i + 1, 右子节点为 2 * i + 2, 父节点为 (i - 1) / 2

• [ ] 2487. 从链表中移除节点

  • 单调栈的几种写法: 栈, 递归

• [ ] 1758. 生成交替二进制字符串的最少操作数 这道题就 2 种情况, 并且相互互斥, 期望是 N, 那么只要算出一种可能, 然后拿 N 减去就可以了, 不要想复杂了

• [ ] 1769. 移动所有球到每个盒子所需的最小操作数 没有弄清楚 i 和 i+1 之间的关联关系, 虽然一开始是看懂题目了, 但是没想到左边是 +1, 右边是 -1 这个简单的逻辑关系

• [x] 1796. 字符串中第二大的数字 第二大, 不是第二个最大的

• [ ] 1774. 最接近目标价格的甜点成本 想到暴力求解, 但是没写出来 DFS; 动态规划解释见此

• [ ] 🧩1687. 从仓库到码头运输箱子

  • 不会写, 使用滑动窗口的来写更容易理解

• [ ] 1805. 字符串中不同整数的数目 指针的边界条件没想到 r - l > 1 来判断

• [ ] 1775. 通过最少操作次数使数组的和相等 没想到简化问题, 这题目的重点是尽量减小大的, 增加小的

  • 比较妙的解法: 记录最小最大的操作量

• [ ] 🧩1691. 堆叠长方体的最大高度

  • DP 写错^1
  • 判断条件想错, 诸如排序箱子 i 和箱子 j 没考虑到 i_0 >= j_0 不一定推导出 i_1 >= j_1

• [ ] 6258. 数组中最长的方波

  • 一般解法使用 Math.sqrt 但是使用 * 的话速度会快一点
  • 但是使用乘法的话, 需要从后往前, 注意需要当溢出值范围时, 要将数组初始化为 1, 毕竟自己也是包含在子序列里面的

• [ ] 1781. 所有子字符串美丽值之和

  • 没考虑到可能存在的重复子串

• [x] 1832. 判断句子是否为全字母句

  • 日常回顾位运算的用法 ^, |, &

• [ ] 🧩1697. 检查边长度限制的路径是否存在

  • 不会写

• [x] 1945. 字符串转化后的各位数字之和 重复做

• [x] 1785. 构成特定和需要添加的最少元素

  • 向上取整, 因为 sum + n * limit + c = goal, 所以 n = ⌈(goal - sum) / limit⌉ 大意了, 一开始用贪心算法

• [ ] 1764. 通过连接另一个数组的子数组得到一个数组 大意了

• [ ] 1026. 节点与其祖先之间的最大差值