leetcode321场周赛python

第一次周赛情况

完全A的只有第1题，第二题和第三题过了2/3的案例，第四题困难题题目都没有时间看。之后问了学霸，学霸A了3题。（我是小垃圾）

1.找出中枢整数（简单）

题目：
给你一个正整数 n ，找出满足下述条件的 中枢整数 x ：

1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。
返回中枢整数 x 。如果不存在中枢整数，则返回 -1 。题目保证对于给定的输入，至多存在一个中枢整数。

示例 1：
输入：n = 8
输出：6
解释：6 是中枢整数，因为 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21 。

思路和代码：
这题我写出来还是蛮快的。

class Solution:
    def pivotInteger(self, n: int) -> int:
        num = int(math.sqrt(n*(n+1)//2))
        return num if num**2 == n*(n+1)//2 else -1
1
2
3
4

2.追加字符以获得子序列（中等）

题目
给你两个仅由小写英文字母组成的字符串 s 和 t 。

现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。

子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。

示例 1：
输入：s = “coaching”, t = “coding”
输出：4
解释：向 s 末尾追加字符串 “ding” ，s = “coachingding” 。
现在，t 是 s (“coachingding”) 的一个子序列。
可以证明向 s 末尾追加任何 3 个字符都无法使 t 成为 s 的一个子序列。

思路和代码：
我自己想的复杂繁琐了许多。倒序遍历s用哈希表存字母：索引，然后再遍历t，判断当前字母在哈希表中的索引是不是大于上一个的，是的继续遍历，最后返回t的长度-跳出循环时当前遍历的位置。这存在一个逻辑漏洞就是例如s=abbbacd，t=bad。此时本来t已经在s中的，但是由于开始字典是倒序存的，a：0，b：1，遍历t的时候，本来b后面还有一个a，可此时却要跳出循环，答案出错。

看了大佬的代码，用的贪心，看完就很气啊。还有的就是用双指针，这也很好想啊，为什么自己想不到呢？

我昨天和学霸说，就是当自己想半天都想不出结果，结果看别人用几行代码很快就解决时，心里就会很难受很气。

学霸说，别气啊，我看过太多的大佬了，看多了就不会气了。

我想到我最近刷题心态确实蛮不好的，看到别人写出来的代码自己想不到就会很生气。得好好调整心态，多思考多学习总结，大佬多的是，不要和大佬比较，重要的是学习是进步，是享受思考的过程和accept的喜悦。

思路1：用贪心，其实我昨天看了别人的不到5行的代码，这简单啊。结果我刚刚去刷没有刷出来，反而想到学霸说的双指针通过了。
贪心，是对s中的每个字符遍历，判断当前字符与t[i]相等，i就+1。

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        i= 0
        for char in s:
            if i < len(t) and char == t[i]:
                i += 1
        return len(t) - i
1
2
3
4
5
6
7

另一种思路就是双指针。

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        p1, p2 = 0, 0
        while p1 < len(s) and p2 < len(t):
            if s[p1] == t[p2]:
                p1 += 1
                p2 += 1
            else:
                p1 += 1
        return len(t)-p2

1
2
3
4
5
6
7
8
9
10
11

3.从链表中移除节点（中等）

题目
给你一个链表的头节点 head 。

对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。返回修改后链表的头节点 head 。

示例 1：
输入：head = [5,2,13,3,8]
输出：[13,8]
解释：需要移除的节点是 5 ，2 和 3 。

• 节点 13 在节点 5 右侧。
• 节点 13 在节点 2 右侧。
• 节点 8 在节点 3 右侧。

示例 2：
输入：head = [1,1,1,1]
输出：[1,1,1,1]
解释：每个节点的值都是 1 ，所以没有需要移除的节点。

思路和代码：
我觉得我一开始的思路也是蛮繁琐的，就是先遍历链表，然后把值加到列表中，倒序遍历判断当前值是否大于右边的最大值。不是的话就将其删除，最后对列表剩下的元素重新建链表。

为什么我一开始没有AC，因为在处理“倒序遍历判断当前值是否大于右边的最大值。不是的话就将其删除”的时候，我不知道怎么删除，就先把不符合要求的变为-1，然后再用while循环，把-1remove掉。后面把变-1再删除的代码删掉，而是在一开始遍历的时候把满足条件的值加到一个新的列表中，然后对新列表创建链表。就，通过了。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        stack = []
        while cur:
            stack.append(cur.val)
            cur = cur.next
        max_v = stack[-1]
        res = [stack[-1]]
        for i in range(len(stack)-2,-1,-1):
            if stack[i] >= max_v:
                max_v = stack[i]
                res.append(stack[i])
        dummy = ListNode(-1)
        current = dummy
        while res:
            node = ListNode(res.pop())
            current.next = node
            current = current.next
        return dummy.next
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

这题有个大佬用的递归，那代码写的是一个优美简洁，就是破费了我一番功夫去理解递归。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head.next is None:
            return head
        node = self.removeNodes(head.next)
        #删除head 
        #head在前 node在后
        #如果后面的值比当前的值大，就返回后面的值，相当于删除了当前链表节点值
        if node.val > head.val:
            return node
        #不删除head 当前值比后面的值大
        #直接把head和后面的node连接起来
        head.next = node
        return head
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.统计中位数为 K 的子数组(困难)

题目
给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。

统计并返回 num 中的 中位数 等于 k 的非空子数组的数目。

注意：

数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。
例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
子数组是数组中的一个连续部分。

示例 1：
输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。

示例 2：
输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。

提示：
n == nums.length
1 <= n <= 105
1 <= nums[i], k <= n
nums 中的整数互不相同

思路和代码：
看不懂看不懂 摆烂

2022.12.2追更

听了大佬灵茶山艾府的讲解，再结合自己的聪明才智，茅塞顿开，我真的是太聪明了！

要找中位数，（前两天写的从两个有序数组中找到中位数也是中位数，这题用二分查找找分割线或者递归，不好理解不好理解，但是我啃下来乐，似乎懂了，我太有毅力了。）

这题的思路就是找中位数k嘛，那如果是奇数个的话，对于一个有序数组来说：

左边小于k的个数 = 右边大于k的个数。

但是对于无序的数组来说，上面式子就可以转换成：

左边小于k的个数 + 右边小于k的个数 = 左边大于k的个数 + 右边大于k的个数

进一步“合并同类项”得：

+左边小于k的个数 - 左边大于k的个数 = +右边大于k的个数 - 右边小于k的个数

如果是偶数的话，因为题目中说了返回中间靠左的元素，所以有：

左边小于k的个数 + 1 = 右边大于k的个数

同样可以转为：

左边小于k的个数 - 左边大于k的个数 +1 = 右边大于k的个数 - 右边小于k的个数

那怎么求到底有多少个以k为中位数的子数组？

我们先得到k的位置pos，然后遍历k后面的元素，用right_count来记录等号右边的值。如果右边的元素大于k那么right_count+1，如果小于k那么right_count-1。在这个过程中要记录一个哈希表，就是right_count这个值出现多少次。

然后从后往前遍历k前面的数。注意，我们此时初始化left_count为0，表示等号左边的值。如果左边的元素小于k那么left_count+1，如果大于k那么left_count-1。

好戏来了，当这个left_count值在k后面出现过，那么就得到一个以k为中位数的子数组，出现多少次就得到多少个，这也是为什么要开始遍历k值后面元素的时候用哈希表存count出现次数的原因。还有一种情况就是left_count+1 ==right_count的时候也能构成一个偶数的以k为中位数的子数组。所以往前遍历的时候，结果res += dic[left_count] + dic[left_count+1]。

再举例说明一下，如[3,2,1,4],k=2。

先初始dic[0]=1（2位置），一开始从2下一个往后面遍历，1小于2，right_count -1 = -1,dic[-1] = 1;4大于2，right_count +1=0,dic[0] = 1。

然后ans初始化为dic[0]+dic[1]= 1。再从2的前一个开始往前遍历，3大于7，left_right -1 = -1, 1的位置right_count也是-1，此时left_count = right_count,这时[3,2,1]就是一个子结果。而9的位置是0，此时left_count +1 = right_count,这时[3,2,1,4]也是一个子结果。

ans += dic[-1] + dic[0],ans为3。

这题的代码的时空复杂度都是O（n）

代码：

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pos = nums.index(k)
        dic = Counter()
        dic[0] = 1
        right_count = 0
        for i in range(pos+1,n):
            right_count += 1 if nums[i] > k else -1
            dic[right_count] += 1
        left_count = 0
        ans = dic[0] + dic[1]
        for i in range(pos-1,-1,-1):
            left_count += 1 if nums[i] < k else -1
            ans += dic[left_count] + dic[left_count+1]
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17