這個(gè)周末感覺(jué)學(xué)習(xí)狀態(tài)不錯(cuò)(飄了)，于是在leetcode上開(kāi)了一場(chǎng)周賽玩玩。。。結(jié)果換來(lái)的是被大佬們虐。。。鏈表太久沒(méi)寫(xiě)了在第三題卡了好久， 第四題考慮了一下中心擴(kuò)散法寫(xiě)復(fù)雜度太高超時(shí)了。。。

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.

一開(kāi)始還在想O(n)的解法，怒推一波兩個(gè)等差數(shù)列的求和式相等時(shí)的規(guī)律，又想起這里是leetcode 不是 codeforces(n 的范圍最大就100), 果斷選擇模擬暴力法:

時(shí)間復(fù)雜度 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.

題目大概問(wèn)你在 s 中追加多少個(gè)字符(最小值)使得 t 為 s 的子序列, 一般子序列的樸素解法就是開(kāi)雙指針(當(dāng)然偶爾也會(huì)來(lái)一手動(dòng)態(tài)規(guī)劃), 這題不例外，開(kāi)個(gè)雙指針就行了, i 指向 s的元素, j 指向 t的元素, 如果兩個(gè)元素相等則i和j同時(shí)移動(dòng)， 如果不相等則移動(dòng) i,? 最后的答案就是 t的長(zhǎng)度 - j:

時(shí)間復(fù)雜度: O(n)

三:?remove-nodes-from-linked-list(單調(diào)棧 || 遞歸)

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.

方法一: 單調(diào)棧

注意到題目需要移除的是嚴(yán)格大于strictly greater某個(gè)值前面的元素， 我們發(fā)現(xiàn)單調(diào)棧滿足這一特性， 我們需要一個(gè)從棧底到棧頂遞減的單調(diào)棧: 遍歷之后棧中留下的就是刪除后的值惹。

注意數(shù)組轉(zhuǎn)化為鏈表時(shí)一定要開(kāi)虛擬節(jié)點(diǎn)(在比賽時(shí)沒(méi)開(kāi)出bug, 返回值老是空的，?卡了我好久。。。)

時(shí)間復(fù)雜度O(n):

方法二:遞歸

我們可以從鏈表的后面往前面想，如果當(dāng)前節(jié)點(diǎn)的值為 x , 那么要?jiǎng)h除的就是與 x 前面連接且小于? x 的值，那么我們可以分解出子問(wèn)題: 對(duì)鏈表中的每一個(gè)元素?i?都進(jìn)行以上操作。

由遞歸的性質(zhì)可以得到， 我們先進(jìn)行遞歸到最后節(jié)點(diǎn)(也就是<<算法導(dǎo)論>>里面所說(shuō)的子問(wèn)題的根節(jié)點(diǎn))，在最小規(guī)模的子問(wèn)題解得到會(huì)向上推出最后答案。

時(shí)間復(fù)雜度: O(n):

?四:?count-subarrays-with-median-k(數(shù)學(xué)?+ 哈希表)

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題, 直接暴力肯定不行。

我們先來(lái)觀察一下子數(shù)組中位數(shù)是 k 會(huì)出現(xiàn)哪些性質(zhì)?

先討論子數(shù)組長(zhǎng)度為奇數(shù)的情況，注意到我們的 k 一定是在子數(shù)組里面的, 我們可以以?k?為軸，考慮左側(cè)與右側(cè)情況:

例如:?

如果我們找到一個(gè)子數(shù)組的中位數(shù)是 k 的， 由于子數(shù)組的長(zhǎng)度為奇數(shù)，那么這個(gè)子數(shù)組中比 k 大的數(shù)和比 k 小的數(shù)是相等的，也就是說(shuō)?比k小的數(shù)個(gè)數(shù) = 比k大的數(shù)個(gè)數(shù)

由于是子數(shù)組要求是連續(xù)的, 要求我們排序后滿足上述等式就可以了，那么對(duì)上等式繼續(xù)推導(dǎo)可以得到 左側(cè)比 k 小的個(gè)數(shù) + 右側(cè)比 k 小的個(gè)數(shù) = 左側(cè)比 k 大的個(gè)數(shù)+ 右側(cè)比 k 大的個(gè)數(shù)

合并同類(lèi)項(xiàng)一下得到:

+ 左側(cè)比 k 小的個(gè)數(shù) -?左側(cè)比 k 大的個(gè)數(shù)? = + 右側(cè)比 k 大的個(gè)數(shù) - 右側(cè)比 k 小的個(gè)數(shù)

這樣我們就轉(zhuǎn)化為一個(gè)數(shù)學(xué)問(wèn)題了，我們先求出等式的右邊.

我們可以用一個(gè)哈希表mp來(lái)存儲(chǔ)次數(shù)， 我們接下來(lái)初始化ans = mp[0] + mp[1], 首先考慮了長(zhǎng)度為1和長(zhǎng)度為2的情況。

然后我們?cè)偾蟪龅仁降淖筮?/p>

將其中左側(cè)與右側(cè)相等的1的次數(shù)統(tǒng)計(jì)起來(lái)，答案就為 3?了!?

下面來(lái)考慮子數(shù)組長(zhǎng)度為奇數(shù)的情況，實(shí)際上很簡(jiǎn)單:

左側(cè)比 k 小的個(gè)數(shù) + 右側(cè)比 k 小的個(gè)數(shù) + 1= 左側(cè)比 k 大的個(gè)數(shù)+ 右側(cè)比 k 大的個(gè)數(shù)

繼續(xù)推導(dǎo)得:

+?左側(cè)比?k 小的個(gè)數(shù) -?左側(cè)比?k 大的個(gè)數(shù)??+ 1=?+?右側(cè)比 k 大的個(gè)數(shù) - 右側(cè)比 k 小的個(gè)數(shù)

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

時(shí)間復(fù)雜度O(n):

總結(jié)

優(yōu)化算法的時(shí)間復(fù)雜度要多多考慮實(shí)際情況中隱藏的數(shù)學(xué)關(guān)系!