leetcode赛后补题: 周赛321题解

这个周末感觉学习状态不错(飘了)，于是在leetcode上开了一场周赛玩玩。。。结果换来的是被大佬们虐。。。链表太久没写了在第三题卡了好久， 第四题考虑了一下中心扩散法写复杂度太高超时了。。。

https://leetcode.cn/contest/weekly-contest-321/

一： find-the-pivot-integer(模拟 + 暴力)

Given a positive integer n, find the pivot integer x such that:

The sum of all elements between 1 and x inclusively equals the sum of all elements between x and n inclusively.

Return the pivot integer x. If no such integer exists, return -1. It is guaranteed that there will be at most one pivot index for the given input.

Example 1:

Input: n = 8

Output: 6

Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21.

Example 2:

Input: n = 1

Output: 1

Explanation: 1 is the pivot integer since: 1 = 1.

一开始还在想O(n)的解法，怒推一波两个等差数列的求和式相等时的规律，又想起这里是leetcode 不是 codeforces(n 的范围最大就100), 果断选择模拟暴力法:

时间复杂度 O(n^2):

二: append-characters-to-string-to-make-subsequence(双指针)

You are given two strings s and t consisting of only lowercase English letters.

Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Example 1:

Input: s = "coaching", t = "coding"

Output: 4

Explanation: Append the characters "ding" to the end of s so that s = "coachingding".

Now, t is a subsequence of s ("coachingding").

It can be shown that appending any 3 characters to the end of s will never make t a subsequence.

Example 2:

Input: s = "abcde", t = "a"

Output: 0

Explanation: t is already a subsequence of s ("abcde").

Example 3:

Input: s = "z", t = "abcde"

Output: 5

Explanation: Append the characters "abcde" to the end of s so that s = "zabcde".

Now, t is a subsequence of s ("zabcde").

It can be shown that appending any 4 characters to the end of s will never make t a subsequence.

题目大概问你在 s 中追加多少个字符(最小值)使得 t 为 s 的子序列, 一般子序列的朴素解法就是开双指针(当然偶尔也会来一手动态规划), 这题不例外，开个双指针就行了, i 指向 s的元素, j 指向 t的元素, 如果两个元素相等则i和j同时移动， 如果不相等则移动 i,  最后的答案就是 t的长度 - j:

时间复杂度: O(n)

三: remove-nodes-from-linked-list(单调栈 || 递归)

You are given the head of a linked list.

Remove every node which has a node with a strictly greater value anywhere to the right side of it.

Return the head of the modified linked list.

Example 1:

Input: head = [5,2,13,3,8]

Output: [13,8]

Explanation: The nodes that should be removed are 5, 2 and 3.

- Node 13 is to the right of node 5.

- Node 13 is to the right of node 2.

- Node 8 is to the right of node 3.

Example 2:

Input: head = [1,1,1,1]

Output: [1,1,1,1]

Explanation: Every node has value 1, so no nodes are removed.

方法一: 单调栈

注意到题目需要移除的是严格大于strictly greater某个值前面的元素， 我们发现单调栈满足这一特性， 我们需要一个从栈底到栈顶递减的单调栈: 遍历之后栈中留下的就是删除后的值惹。

注意数组转化为链表时一定要开虚拟节点(在比赛时没开出bug, 返回值老是空的， 卡了我好久。。。)

时间复杂度O(n):

方法二:递归

我们可以从链表的后面往前面想，如果当前节点的值为 x , 那么要删除的就是与 x 前面连接且小于  x 的值，那么我们可以分解出子问题: 对链表中的每一个元素 i 都进行以上操作。

由递归的性质可以得到， 我们先进行递归到最后节点(也就是<<算法导论>>里面所说的子问题的根节点)，在最小规模的子问题解得到会向上推出最后答案。

时间复杂度: O(n):

 四: count-subarrays-with-median-k(数学 + 哈希表)

You are given an array nums of size n consisting of distinct integers from 1 to n and a positive integer k.

Return the number of non-empty subarrays in nums that have a median equal to k.

Note:

The median of an array is the middle element after sorting the array in ascending order. If the array is of even length, the median is the left middle element.

For example, the median of [2,3,1,4] is 2, and the median of [8,4,3,5,1] is 4.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [3,2,1,4,5], k = 4

Output: 3

Explanation: The subarrays that have a median equal to 4 are: [4], [4,5] and [1,4,5].

Example 2:

Input: nums = [2,3,1], k = 3

Output: 1

Explanation: [3] is the only subarray that has a median equal to 3.

题目很好理解， 但这是一道hard题, 直接暴力肯定不行。

我们先来观察一下子数组中位数是 k 会出现哪些性质?

先讨论子数组长度为奇数的情况，注意到我们的 k 一定是在子数组里面的, 我们可以以 k 为轴，考虑左侧与右侧情况:

例如: 

如果我们找到一个子数组的中位数是 k 的， 由于子数组的长度为奇数，那么这个子数组中比 k 大的数和比 k 小的数是相等的，也就是说 比k小的数个数 = 比k大的数个数

由于是子数组要求是连续的, 要求我们排序后满足上述等式就可以了，那么对上等式继续推导可以得到 左侧比 k 小的个数 + 右侧比 k 小的个数 = 左侧比 k 大的个数+ 右侧比 k 大的个数

合并同类项一下得到:

+ 左侧比 k 小的个数 - 左侧比 k 大的个数  = + 右侧比 k 大的个数 - 右侧比 k 小的个数

这样我们就转化为一个数学问题了，我们先求出等式的右边.

我们可以用一个哈希表mp来存储次数， 我们接下来初始化ans = mp[0] + mp[1], 首先考虑了长度为1和长度为2的情况。

然后我们再求出等式的左边

将其中左侧与右侧相等的1的次数统计起来，答案就为 3 了! 

下面来考虑子数组长度为奇数的情况，实际上很简单:

左侧比 k 小的个数 + 右侧比 k 小的个数 + 1= 左侧比 k 大的个数+ 右侧比 k 大的个数

继续推导得:

+ 左侧比 k 小的个数 - 左侧比 k 大的个数  + 1= + 右侧比 k 大的个数 - 右侧比 k 小的个数

答案加上哈希表mp[c+1]就可以了!

时间复杂度O(n):

总结

优化算法的时间复杂度要多多考虑实际情况中隐藏的数学关系!