Leetcode 100 刷题记录

day 1 2024/3/14

---

<失败>leetcode 1.两数之和

暴力解O(n^2) + T(1) / 哈希表O(n) + T(n)

只做出来暴力解

哈希表的方式为将数组存储的值作为哈希表的键，将原数组下标作为哈希表的值，这样哈希表成为一个类似以值为下标的数组。

哈希表可以看成是数组的逆映射

day 2 2024/3/15

---

leetcode 2.搜索插入位置

调API Collections.binarySearch / 二分查找

day 3 2024/3/23

---

leetcode 3.字母异位词分组

哈希表

原始想法：hm = new Hashmap<String, List<List>>, 将输入的词重排列后作为键，原始的词作为值，加入到hm中，没加入一个新的词，判断和已有的重排列键是否一样，如果一样，利用Hashmap的特性获取到被覆盖的值列表，将新加入的键加进去。

题解：大致思想差不多，但是作为键之后，添加值只需要查询当前hashmap是否包含键就可以，我真是个傻逼

day 4 2024/3/25

---

leetcode 4.最长连续序列

哈希？

原始想法：空间换时间，每一个原始数组元素值映射为新数组的索引，但是有些值特别大会超内存

题解：hashset去重，先看是否包含当前值减一的元素，不包含的情况下，从该元素值开始依次找大1的连续串，只有个别元素会进入这个过程，看起来是O(n^2), 实际上不是，这个想不出来

day 5 2024/3/26

---

leetcode 5.移动零

双指针

原始想法：冒泡，遇到0将移动到末尾，设置high标记记录剩余需要清楚零元素的个数， 但是时间用时比较多， 时间复杂度O(n^2)

题解：快慢指针，满指针始终指向待交换的0元素，快指针指向非零元素的时候需要和慢指针交换，当快慢指针指向同一个元素时不交换，时间复杂度O(n)， 像快排？

day 6 2024/3/27

---

leetcode 6.盛水最多的容器

双指针

原始想法：暴力解，两个for遍历所有面积求最大，超时

题解：双指针，左右边界作为边界之后就不会，看比较小的那个height，移动对应所指的指针

day 7 2024/3/28

---

leetcode 7.最大子序列之和

动态规划/分治（不会）

原始想法：暴力解，超时

题解：1.动态规划，记以第i个结尾的子序列的最大和为f(i)，那么题目转化为求解0<=i<=n-1中最大的f(i)，当n = 1 时，f(i) = nums[0],以此为起点，对于f(i), f(i) = max(nums[i], nums[i] + f(i-1)), 即，f(i) 要么会在f(i-1)的基础上吸收nums[i], 要么就是nums[i], 再用一个maxSum记录各个f(i) 中的最大值，问题解决。

2.分治，看不懂，线段树是什么东西

day 8 2024/3/29

---

leetcode 8.爬楼梯

动态规划

原始想法：递归或者动态规划， 递归超时， 改用动态规划解决

题解：动态规划/ 矩阵快速幂（不会） / 斐波那契数列通项公式（不会）

day 8 2024/3/29

---

leetcode 9.杨辉三角

动态规划

原始想法：尝试计算阶乘，但是数值太大.leetcode不让用BigInteger存储，放弃。后面直接创建大的二维数组，在数组中找规律存储每一层，成功

题解：大致思想差不多

day 9 2024/3/30

---

leetcode 10.打家劫舍

动态规划

原始想法：对于相邻两个元素不能同时偷窃，那么需要考虑的是f(i) = max(f(i - 1), f(i - 2) + nums[i], f(i - 3) + nums[i]),动态规划， 成功

题解：大致思想差不多

day 10 2024/4/2

---

leetcode 11.完全平方数

动态规划

原始想法：没有想出来用dp怎么做，一开始的设想是每个数依次减去自己数值范围内最大的平方数，循环sqrt(n)此，每次将得到的一组元素放在一个列表中，最后求每个列表的长度的最小值，但是没什么说法，有20多个用例过不了。

题解：动态规划，具体思想：每一个数都由一些平方和组成，假设某个数为f(i), 它包含某个 j * j, 那么它的最小平方和个数就等于f(i - j * j) + 1, 这是显然的，于是可得动态回归方程。

day 10 2024/4/2

---

leetcode 12.零钱兑换

动态规划

原始想法：和完全平方数很想，但是这李要考虑数组越界的情况，动态回归方程f(i) = min(f(i - coins[j])) + 1, 成功

题解：基本一致

day 11 2024/4/3

---

leetcode 13.零钱兑换

动态规划

原始想法：和零钱兑换相似的想法，都是为了凑整，这题想的是从前往后凑，对于某些单词正好和dict里面的单词一致就复制为true，当遇到后缀和字典里的单词一致的情况，dp[i] = dp[i = wordDict.get(j)], 只要某一次达成这种情况即可，所以dp[i] |= dp[i = wordDict.get(j)]；

题解：用的另一种相似思路，前面如果从前往dp[j] = true, 那么只要判断，s(j, i]是否存在于词表之中即可，更快速一点

day 11 2024/4/3

---

leetcode 14.最长递增子序列

动态规划

原始想法：常见的动态规划，dp[i] = max(dp[j]) + 1; O(n^2)

题解：二分+贪心，这个比较经典，需要仔细看一下，核心是维护当前最长递增子序列莫为最小元素值，保证有序，用二分插入，时间O(nlogn)

day 11 2024/4/7

---

leetcode 14.成绩最大子数组

动态规划

原始想法：失败，想用类似最长递增子序列和来计算，但是最大成绩包含正负数，不是常见的最优子问题

题解：用两个数组分别维护最大子序列和最小子序列，对当前的nums[i]分正负情况讨论

day 12 2024/4/8

---

leetcode 14.三数之和

双指针

原始想法：失败，想用一个数作为和，做n次两数之和的操作，但是重复子序列的问题解决不了

题解：1.先排序，如果第一个数大于0，则肯定无解；2.三数之和必定需要至少三个数，选择nums[i+1]作为临时中间数，nums[i]作为临时最小数，nums[n-1],三数之和为0则可以存入list，否则看和的大小，小于0则i++,大于0则k--

day 13 2024/4/9

---

leetcode 14.合并区间

水题

原始想法：成功

day 13 2024/4/9

---

leetcode 15.轮转数组

水题

原始想法：成功

day 14 2024/4/10

---

leetcode 16.除自身以外数组的乘积

原始想法：失败，没做出来

题解：用一个L数组记录从左开始的一次乘积，用一个R数组记录从右边开始的依次乘积，这样每一个对应的i位置上的answer[i]正好是L[i] * R[i];

day 14 2024/4/10

---

leetcode 17.除自身以外数组的乘积

原始想法：失败，没做出来，艹

题解：对于一个长度为n的数组，其中最小缺失的正数一定是在[1,N+1]之间，而要想在O(n)时间内个O(1)空间内完成，就必须利用原本的数组进行查找

1. 首先将数组中的所有负数全部替换为n+1；2.其次利用哈希思想，对于某一个出现的整数，对其对应哈希位置的前一个位置打上标签，这个标签就是对该位置上的元素添加一个负号，对于某一个位置上的元素，如果其已经是负数，则代表他已经被标记过，不再参与标记；3. 返回第一次出现的整数的下标的位置+1；太几把坑了。做不出来。

day 14 2024/4/10

---

leetcode 18.矩阵置零

原始想法：我艹尼玛，什么垃圾题目，出生里的出生

题解：难点，不能一次性覆盖全部行列，会导致连锁覆盖，一开始的想法被原地算法迷惑了，是把出现的位置所在的行列全部选取一个特殊值覆盖，遇到0就跳过，最后对于所有出现特殊值的地方用0替代，但是测试用例里面考虑到了特殊值

将出现0的位置的行列分别存在两个数组中，最后对这两个数组中出现的行列作清零操作，这他妈都新建两个数组了，空间复杂度都是O(n+m)了还能算原地算法？

day 14 2024/4/11

---

leetcode 19.螺旋矩阵

原始想法：用一个新的数组记录走过的路径，走过的路径不能再走，方向右下左上循环，暴力解成功

题解：设定上下左右边界，走过的路径到头直接调整边界，不用一个新的数组记录走过的路径

day 14 2024/4/11

---

leetcode 20.旋转图像

原始想法：找到旋转后的每一列行对应的每一列的位置，写出每个旋转后位置的公式

题解：相似

day 14 2024/4/11

---

leetcode 21.搜索二维矩阵 II

原始想法：二分查找+遍历 O(mlogn)

题解：Z字查找，O(m+n)，利用行列的有序特性，从右上角开始查找，喵喵喵

day 14 2024/4/11

---

leetcode 22.搜索二维矩阵 I

原始想法：二分查找+遍历 O(mlogn)

题解：由于每一愿所有元素依次递增，可以将所有行元素在逻辑上拼接在一起，即二分查找的时候high = m * n-1, 鸟鸟鸟鸟鸟；或者先从第一列二分，再从找出的位置所在的行继续二分，两种方法都是(O(logm + logn) = O(logmn))

day 15 2024/4/12

---

leetcode 23.在排序数组中查找元素的第一个和最后一个位置

原始想法：二分查找 查找到指定位置元素分别向前向后遍历，获取start,end

题解：相似

day 16 2024/4/13

---

leetcode 24.搜索旋转排序数组

原始想法：二分查找 想到了一定有两部分局部有序，但是不知道怎么写下去

题解：二分查找 + 局部有序 对于两个局部有序的递增子序列来说，nums[0] < nums[mid] 或者nums[mid] < nums[nums.length - 1] 都能保证0-mid-length-1 之间的数组元素递增有序，此时考察target是否落在nums[0]-nums[mid] 和nums[mid]-nums[nums.lenth - 1]之间，在这两个之间直接用二分查找就行，不在这两个之间就重新调整low，high的值。

day 16 2024/4/13

---

leetcode 25.寻找旋转排序数组中的最小元素

原始想法：二分查找 + 局部有序，找拐点，记录最小值，实现比较复杂，时间复杂度还行

题解：二分查找 + 局部有序 对于两个局部有序的数组来说，寻找最小值的过程就是遍历达到low>=high的过程，每次看mid和两边局部有序数组之间的关系就行

day 17 2024/4/15

---

leetcode 26.相交链表

暴力成功

原始想法：暴力遍历两个链表

题解：1.用hashset存储链表A，看B中的某个元素是否在hashset中，时间o(n+m), 分别需要遍历依次链表A和链表B，空间O(m);2.双指针，AB链表若相交，设相交后的元素数目为x, A链表相交前的数目为y,B相交前的数目为z,那么分别便利A和B，变量完成之后分别从另一个链表头开始遍历，那么相交处的位置一定为x + y + z;

day 17 2024/4/15

---

leetcode 27.反转链表

dummynode

原始想法:dummynode+头插法

题解：用递归的思想

day 17 2024/4/15

---

leetcode 27.回文链表

原始想法:翻转链表，比较反转前后结果 O(n), O(n)

题解：只翻转一半，反转完毕之后还要讲原始链表复原

day 18 2024/4/16

---

leetcode 28.环形链表

原始想法:快慢指针

题解：哈希去重或者快慢指针

day 18 2024/4/16

---

leetcode 29.环形链表II

原始想法:哈希表去重

题解：快慢指针， 鸟鸟鸟 假设有环，环入口距离head为a, slow 和fast相遇出分别讲环的周长切割为b,c两段，已知fast速度是slow速度的两倍；则在fast slow相遇时有 a + n(b+c) + b = 2 * (a + b)； a + (n+1)b + nc = 2a + 2b； a = (n-1)b + nc = (n - 1)(b + c) + c； 所以当slow，fast相遇之后，再来一个ptr指针从头开始和slow同时next，即可找到环入口。

day 18 2024/4/16

---

leetcode 30.合并两个有序链表

原始想法:迭代

题解：递归或者迭代，递归每次连接的节点

day 18 2024/4/16

---

leetcode 31.两数相加

原始想法:用新链表进位模拟 O(n) + O(n)

题解：直接在某一个链表上相加 O(n) + O(1)

day 18 2024/4/16

---

leetcode 32.删除链表的倒数第N个节点

原始想法:用新链表进位模拟 两次遍历

题解：用栈，先加哑节点，再全部进栈，倒数第N个节点实际上就是pop N次之后，栈顶元素的下一个，直接删除即可

day 18 2024/4/16

---

leetcode 33.两两交换链表中的节点

原始想法:递归或者迭代，递归空间复杂度高一点，但是代码简单点

题解：递归或者迭代

day 18 2024/4/16

---

leetcode 33.K 个一组翻转链表

第一次自己做出hard

原始想法:分组反转链表+哑节点，注意节点指向

题解：相似

day 19 2024/4/17

---

leetcode 34.随机链表的复制

原始想法:把原始链表复制到一个新的List里面，用新的newList重建原始链表

题解：1.哈希加回溯，用哈希新建链表，用回溯连接新链表中的各个元素；2，在原始链表每个节点的后面新复制一个相同节点，两次遍历分别重建random和next，注意尾部节点

day 19 2024/4/17

---

leetcode 35.排序链表

原始想法:把原始链表复制到一个新的数组里面，直接排序再重新赋值链表

题解：1.自顶向下归并，2.自底向上归并， 第一种要先用快慢指针分拆，找到左右两个子序列都只包含一个元素的情况，然后再向上合并，第二种用for循环直接一组一组合并

day 20 2024/4/21

---

leetcode 36.LRU缓存

数据结构类型的题

原始想法:利用linkedlist作弊

题解：用双向链表+哈希表

day 21 2024/4/22

---

leetcode 37.二叉树的中序遍历

原始想法:递归

题解：1.递归 2.迭代 3. morris遍历（不会）

day 21 2024/4/22

---

leetcode 38.二叉树的最大深度

原始想法:递归

题解：1.递归

day 22 2024/4/22

---

leetcode 39.翻转二叉树

原始想法:递归

题解：1.递归

day 22 2024/4/22

---

leetcode 40.对称二叉树

原始想法:递归

题解：1.递归

day 22 2024/4/22

---

leetcode 41.二叉树的直径

原始想法:丑陋 算每一个二叉树的左右子树的最大深度，计算最大深度之和最大的节点的长度，作为直径

题解：相似的想法，但是很简单的做法，计算最大深度的时候，分别拆分了左右子树的最大深度

day 22 2024/4/22

---

leetcode 42.二叉树的层序遍历

原始想法:队列 + 新建List

题解：相似的想法，但是用循环来产生新建List，很简洁的做法

day 23 2024/4/24

---

leetcode 43.验证二叉搜索树

原始想法:队列 + 新建List

题解：递归或者栈

day 23 2024/4/24

---

leetcode 44.验证二叉搜索树

原始想法:队列 + 新建List / 栈

题解：和上一题很像

day 24 2024/4/24

---

leetcode 44.二叉树的右视图

原始想法:层序遍历，取每层最后一个

题解：差不多

day 25 2024/4/25

---

leetcode 45.二叉树展开成链表

原始想法:利用栈进行先序遍历

题解：递归或者栈迭代

day 26 2024/4/29

---

leetcode 46.中序先序建树

原始想法:不会做

题解：将中序序列的值和索引构建一个map，对于先序序列中的某个节点，在中序序列中可以利用map找到它的左右子树，每一个子树都可以以此递归构建

day 26 2024/4/29

---

leetcode 47.路径总和III

原始想法:不会做，焯

题解：只看了递归解法。。。