LeetCode Records (Chinese)
78: 子集问题
题目大意：给定元素互不重复的集合，编程得到其所有的子集，可以以任何顺序输出。例如给定集合$[1, 2, 3]$，输出的结果应该为: $[[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]]$.
思路：对于这道题最开始是的思路是回溯，利用回溯算法来计算最终的子集输出，但是出现的问题是，输出没包括单元素的情况，原因可能是我设置的终止条件不对，我设置的终止条件是：
if (idx == nums.length) {
ret.add(new ArrayList<Integer>(path));
return;
}
这样的终止条件会导致输出没办法包括单独元素，因为必须要$idx == nums.legnth$. ![[Screenshot 2023-04-25 at 13.33.47.png]]
方法1： 采用位图法实现求取子集问题 一个有意思的结论是：一个大小为n的集合，其子集数量为$2^n$个，换一种思考角度来看即，集合中的每个元素都只有两种状态：在某个子集中，或者不在某个子集中。因此这就是一个组合的问题，其子集的可能有$2^n$种，那么我们可以很巧妙的利用二进制数的0 或者 1来表示某个元素在某个子集的情况，如下图所示： ![[Screenshot 2023-04-26 at 07.09.40.png]] 那么我们只需要两层循环就可以迭代遍历出所有的可能子集，外层循环，循环的是所有的二进制数，也即上图中的$0, 1, …, 7$，内层循环则负责查看每一位二进制数是否为一，为一则说明该位对应元素在该子集中。最终代码如下；
class solution{
List<Integer> t = new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
t.add(nums[i]);
}
}
ans.add(new ArrayList<Integer>(t));
}
return ans;
}
}
445.两数相加2
这道题要求将通过链表表示的数，相加并且同样以链表的形式输出。显然最直观的方式就是，按照我们计算加法时的顺序，先低位再高位的顺序依次相加，并且要维护一个carry来记录进位的情况。所以第一个问题是，链表是高位在前低位在后的，而且链表不支持切片等操作，只能遍历至最后，所以我们要想办法反转链表的顺序关系，可以使用两种方式：
- 栈
- 反转链表，输出一个已经反转后的链表
使用栈的方法，比较直观简单，见下面的代码，就是将链表的值依次放进栈中，并按照加法顺序求和，通过链表输出即可
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> stack1 = new ArrayDeque<>();
Deque<Integer> stack2 = new ArrayDeque<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode ans = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
int d1 = stack1.isEmpty() ? 0 : stack1.pop();
int d2 = stack2.isEmpty() ? 0 : stack2.pop();
int sum = d1 + d2 + carry;
carry = sum / 10;
ListNode curNode = new ListNode(sum % 10);
curNode.next = ans;
ans = curNode;
}
return ans;
}
}
这个记录贴主要想记录一下关于反转链表的模版
771.宝石与石头
LeetCode-771 Time: 2023.07.24
这道题目的解法非常直观，直接暴力就可以AC，我第一遍也是采用暴力的方式的方法做的，但是看到题解区有大佬用了时间复杂度更低的解法，如果直接暴力的话时间复杂度应该是$O(mn)$，其中$m, n$分别是jewels和stones的长度。下面就学习一下大佬们的做法.
首先是哈希集的做法，这种做法也比较直观，就是将jewels中的每个字符都放在哈希集中，利用哈希集来加速查找的过程，而不是像暴力做法中直接遍历。在Python3中很容易写出代码：
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
jewels_set = set(jewels)
return sum(s in jewels_set for s in stones)
还有一种来自灵神的解法，是利用位运算来进行的，但是我觉得从时间复杂度来说并没有什么提升，我觉得并不是那么喜欢，就不仔细研究了。
104.二叉树的最大深度
LeetCode.104 Time: 2023.07.24
这道题也非常的简单，就是利用深度优先索索遍历整棵二叉树，同时维护一个最大深度。
代码非常简单，二叉树的很多题目解法一般分为两种，即迭代和递归。但是我做了比较多的题目，现在思维习惯一来就想要模拟，脑子里面还没有形成不同题型归纳。对于这个题目代码非常简单，只需要递归地取两个子树中的最大深度就可以了。代码如下：
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
return 1 + max(self.maxDepth(root.right), self.maxDepth(root.left))
2208.将数组和减半的最少操作次数
LeetCode.2208 Time: 2023.07.25
这道题非常容易想到贪心的思路，即每次总是将数组中最大的数减半，这样能最快减少数组和。因此如果使用暴力做法的话，我们只需要每次将数组排序，然后从中选取最大值并减半，直到减少的部分大于等于原数组和的一半时为止。但是暴力做法每次都需要重新对数组进行排序，时间复杂度为$O(n \cdot nlogn)$ ，其中$n$为给定数组的长度。
但是其实我们非常容易想到，我们每次只关心最大值，而不关心剩下的部分，因此我们可以使用堆来维护最大值，这样可以有效降低时间复杂度，采用堆后时间复杂度会降低为$O(nlogn)$.
class Solution:
def halveArray(self, nums: List[int]) -> int:
pq = []
for num in nums:
heappush(pq, -num)
ans = 0
sum1 = sum(nums)
sum2 = 0
while sum2 < sum1 / 2:
x = -heappop(pq)
sum2 += x
ans += 1
heappush(pq, -x / 2)
return ans
2789.合并后数组中的最大元素（355场周赛Q2）
LeetCode.2789 Time: 2023.07.25
1513.仅含1的子串数
LeetCode.1513 Time: 2023.07.26
这道题的思路非常直观，我们只需要将给定的字符串中切割，得到全是1的字串就可以了，总子串数是这些独立的子串的长度$n$，计算公式为 \(Count = \frac{n \cdot (n + 1)}{2}\)
那么任务就非常明确了，就是去统计字符串中有多少个这样的子串。
可以利用while来写这个遍历的过程，代码如下：
class Solution:
def numSub(self, s: str) -> int:
n = len(s)
i = 0
ans = 0
while i < n:
if (i == 0 and s[i] == '1') or (i > 0 and s[i] == '1' and s[i - 1] == '0'):
length = 1
i += 1
while i < n and s[i] == '1':
length += 1
i += 1
ans += (length + 1) * length // 2
i += 1
ans %= (10 ** 9 + 7)
return ans
或者我们也可以使用for来完成遍历的任务，代码如下：
class Solution:
def numSub(self, s: str) -> int:
total, consectuive = 0, 0
n = len(s)
for i in range(n):
if s[i] == '0':
total += (consecutive + 1) * consectuive // 2
consecutive = 0
else:
consecutive += 1
total += (consecutive + 1) * consecutive // 2
total %= (10 ** 9 + 7)
return total
这两个写法的差异在于，如果用for来写的话，因为其判定逻辑是每次遇到'0'才会更新结果，所以需要考虑最后以'0'结尾的情况，但是如果使用while来写没有这样的问题，但是其在判断计数开始过程会更加复杂点，其统计结果是在遍历完成或子段结束时完成的，所以不需要像for一样在最后加那行代码。
2500.删除每行中的最大值
LeetCode.2500 Time: 2023.07.27
对于这道题思路过于直观不需要分析太多，只需要将每行进行升序的排列，然后取每一列的最大值即可，利用Python3的一些性质可以大大简化代码，Python3代码如下：
class Solution:
def deleteGreatesValue(self, grid: List[List[int]]) -> int:
for i in grid:
i.sort()
return sum([max(i) for i in zip(*grid)])
在这里简单介绍一下zip(*)的使用方法，* 的使用在Python3中一般充当着可变数量的参数的作用，比如如果 \(grid = [[1, 2, 4], [3, 3, 1]]\) 那么使用zip(*grid)等价于zip([1, 2, 4], [3, 3, 1]，其返回的结果是[(1, 3), (2, 3), (4, 1)]，从而达到了将grid进行转置的目的，因此我们可以总结出使用zip(*grid)可以快速将矩阵转置的结论。
848.字母移位
LeetCode.848 Time: 2023.07.27
141.环形链表
LeetCode.141 Time: 2023.07.29
这道题是比较经典的环形链表的题目，用来判断链表中是否存在环形连接，对于这样的问题最简单暴力的方法就是在每一个节点处，用while循环来判断是否存在环形连接能够将节点重新移动回该节点，但是这样的时间复杂度是$O(n^{2})$，但是同样是这个过程我们也可以用哈希表的方式来提高其算法复杂度，其代码非常简单
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
seen = set()
while head:
if head in seen():
return True
seen.add(head)
head = head.next
return True
但是对于这道题目，让我想记录这道题的做题记录的主要原因是这是一道比较经典快慢指针的题目，如何判断是否存在环形连接，快慢指针的想法非常朴素，就是我们维护两个指针，两个指针一快一慢，如果存在环形连接，那么快指针一定可以追上慢指针。因此，我们只需要维护两个指针即可解决问题，代码如下：
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
这个解法的代码中有一个值得注意的点是，while的循环结束条件是slow == fast，这是默认了存在环形连接的情况，加入不存在环形连接，那么这样的方式最终可能会导致两种可能的情况：
-
fast指针，刚好能够到达链表的尾节点 -
fast指针，能够到达尾节点前一个节点
针对这两种情况，所以我们才在while循环中，使用if来进行判定，就是为了应对这两种情况，如果fast指针，最终指向尾节点，那么fast.next == null因此会直接返回False；当fast指针指向倒数第二个节点，下一次fast将会指向null，这样就会导致另一个判别条件not fast触发，也会直接返回False。
142. 环形链表II
LeetCode.142 Time: 2023.08.04
这道题目，是建立在141.环形链表的基础之上的，141只要求我们检查是否存在环形连接，而142布景要求我们检查是否存在环形连接，同时还需要找到环形链接的开始的节点，在141中，我们已经学习过了利用快慢指针可以检查是否存在环形连接，但是仅仅利用141的代码是没有办法找到环形连接开始的节点的，当然我们还是可以利用暴力的方法来完成，我们将没见过的节点都放进一个哈希表中，当我们第一次遇见重复的（即哈希表中已存在的）节点，我们只需要返回该节点即可，这种暴力做法的时间复杂度为$O(n)$，其中$n$为链表的长度。代码如下：
public class Solution:
public ListNode detectCycle(ListNode head) {
ListNode pos = head;
Set<ListNode> visited = new HashSet<ListNode>();
while (pos != null) {
if (visited.contains(pos)) {
return pos;
} else {
visited.add(pos);
}
pos = pos.next;
}
return null;
}
}
建立在141的基础之上，我们可以通过数学得到一些结论，首先假设从链表的头节点到环形节点入口的距离为a，环形链表的长度为b，那么我们很容易得到两个结论：
- 快指针
fast前进的距离$f=$慢指针slow前进的距离$2\cdot s$； - 同时$f=s + nb$
根据这两个结论不难推导出，$s = nb$，此时我们只需要找到环形连接开始的节点即可，此时我们可以将快指针重新定位为头节点的位置，同时此时快慢指针移动速度一样那么当快指针移动到头节点时，慢节点移动距离为$s=nb+a$也会恰好移动到环形节点头部，也就是快慢指针会相遇，我们就可以使用这样的方式来找到环形连接头节点的位置，但是这样的做法并不能降低时间复杂度，但是可以减小空间复杂度，将空间复杂度降低到$O(1)$，具体代码如下：
class Solution:
def detectCycle(self, head):
fast, slow = head, head
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
if fast == slow: break
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
return fast
24 两两交换链表中的节点
LeetCode.24 Time: 2023.08.06
这道题用递归的思路其实并不难，但是其实我思考了半天的是迭代的解法，官方题解中对于迭代的解法是利用哑节点的方法来做的，也就是在头节点head前额外增加一个dummyNode。然后不断地迭代去交换temp节点，即当前处理节点的后两个节点，执行的终止条件是直到temp节点后不足两个自节点，这个思路非常的直观，代码如下：
class Solution:
def swapPairs(self, head):
dummyHead = ListNode(0)
dummyHead.next = head
temp = dummyHead
while temp.next and temp.next.next:
node1 = temp.next
node2 = temp.next.next
temp.next = node2
node1.next = node2.next
node2.next = node1
temp = node1
return dummyHead.next
但是让我非常感兴趣的是，其实这个过程我们如果不增加dummyHead，其实也完全可以做到，无非就是：
node1.next = node2.next
node2.next = node1
这样便可以交换两个节点的顺序，看似也是可以迭代的，所以我非常好奇dummyHead的引入究竟带来了什么好处，又或者说其是否是可选的，还是说没有dummyHead的引入这个思路就完不成呢？
那么我们来对比一下当我们不加入dummyHead时会发生什么，我们还是参考上面的迭代的思路，那么我们每次迭代过程中会交换相邻两个节点的顺序，也就是如上面的代码一样，那么我们需要设置循环的终止条件，同样参考题解的思路，但是这时候我们就会发现问题，在循环体里面我们可以写
# exchange two nodes
node1.next = node2.next
node2.next = node1
node1 = node1.next
node2 = node1.next.next
但是由于这个时候没有dummyHead和temp节点，我们在设置循环终止条件时就只能设置
while node1 and node1.next:
当我们复制了同样的node1作为temp节点后，我们的循环终止条件设置为：
while temp and temp.next:
但是随之而来的一个最重要的问题，也是我认为设置dummyHead最重要的原因，设置了哑节点后我们会发现，每次迭代虽然交换了两个节点，但是其实会涉及到三个节点，这样做的好处就是，我们可以使得已经交换位置后的节点最开始连接着未交换位置的两个节点，但是由于它涉及三个节点，也就是它还保存着前一个节点，这样方便我们连接上交换位置后的两个节点；反之如果我们如果不设置哑节点，那么每次只会涉及两个节点，那么交换后的节点与前一个节点还是会以错误的连接方式连接着，具体可以看下面的截图所展示的： ![[Screenshot 2023-08-06 at 08.52.11.png]]
![[Screenshot 2023-08-06 at 08.52.31.png]] 这个结果就体现了，交换后的3和4节点，确实已经交换了，但是前一个节点只连接着3节点，所以才会造成这样的结果，这个结果也反向说明了，我们需要至少三个节点的参与才能顺利解决这个问题。
437 路径总和III
LeetCode.437 Time: 2023.08.07
这道题我最初是能想到暴力遍历的，从每个节点开始都搜索一遍观察是否存在符合路径总和的节点，就将结果加一返回。我最大的问题是，我总是不熟悉怎么写深度优先搜索和广度优先搜索的返回方式，即在搜索遍历中不断被修改的数据如何能够能最终返回到需要的地方。那么首先记录一下暴力的做法，暴力的做法就如我刚才所说的，就是对每一个节点都以其为起始节点去观察是否存在符合题意的路径，编写辅助函数如下：
def rootSum(root, targetSum):
if not root:
return 0
ret = 0
if root.val == tagretSum:
ret += 1
ret += rootSum(rot.left, targetSum - root.val)
ret += rootSUm(root.right, targetSum - root.val)
return ret
这个辅助函数的编写逻辑非常简单，我们每次都以某一个节点为起始节点，不断向下地搜索，但是需要注意的是，这里的参数targetSum和题目给定的函数的参数中的targetSum意义其实并不完全相同，题目中的参数是对于要求的路径和的指定，但是辅助函数中的参数，代表着时我们总是假设在当前节点能够符合路径和时，对于当前节点我们希望的节点值，而且此时全是以最初给定的root为起始点的。正是由于这个差异，在题目的函数中我们不能仅仅：
ret = rootSum(root, targetSum)
因为这样会导致我们只搜索了以根节点为起始节点的搜索结果，我们忽略了以其他节点为起始节点的路径，完整代码如下：
class Solution:
def pathSum(root, targetSum):
if not root:
return 0
ret = rootSum(root, targetSum)
ret += self.pathSum(root.left, targetSum)
ret += self.pathSum(root.right, targetSum)
return ret
849.到最近的人的最大距离
LeetCode.849 Time: 2023.08.22 Keyword: 双指针