精品视频97,舔舔国产欧美不卡久久

周賽 358

T1. 數(shù)組中的最大數(shù)對(duì)和（Easy）

標(biāo)簽：數(shù)學(xué)、分桶

T2. 翻倍以鏈表形式表示的數(shù)字（Medium）

標(biāo)簽：鏈表

T3. 限制條件下元素之間的最小絕對(duì)差（Medium）

標(biāo)簽：雙指針、平衡樹

T4. 操作使得分最大（Hard）

標(biāo)簽：貪心、排序、中心擴(kuò)展、單調(diào)棧、快速冪

T1. 數(shù)組中的最大數(shù)對(duì)和（Easy）

https://leetcode.cn/problems/max-pair-sum-in-an-array/

題解一（分桶 + 數(shù)學(xué)）

枚舉每個(gè)元素，并根據(jù)其最大數(shù)位分桶；
枚舉每個(gè)分桶，計(jì)算最大數(shù)對(duì)和。

class Solution {
public:
    int maxSum(vector<int>& nums) {
        int U = 10;
        // 分桶
        vector<int> buckets[U];
        for (auto& e: nums) {
            int x = e;
            int m = 0;
            while (x > 0) {
                m = max(m, x % 10);
                x /= 10;
            }
            buckets[m].push_back(e);
        }
        // 配對(duì)
        int ret = -1;
        for (int k = 0; k < U; k++) {
            if (buckets[k].size() < 2) continue;
            sort(buckets[k].rbegin(), buckets[k].rend());
            ret = max(ret, buckets[k][0] + buckets[k][1]);
        }
        return ret;
    }
};

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(nlgn)$ 瓶頸在排序，最壞情況下所有元素進(jìn)入同一個(gè)分桶；
空間復(fù)雜度： $O(n)$ 分桶空間；

題解二（一次遍歷優(yōu)化）

最大數(shù)對(duì)和一定是分桶中的最大兩個(gè)數(shù)，我們只需要維護(hù)每個(gè)分桶的最大值，并在將新元素嘗試加入分桶嘗試更新結(jié)果。

class Solution {
public:
    int maxSum(vector<int>& nums) {
        int U = 10;
        int ret = -1;
        int buckets[U];
        memset(buckets, -1, sizeof(buckets));
        for (auto& e: nums) {
            int x = e;
            int m = 0;
            while (x > 0) {
                m = max(m, x % 10);
                x /= 10;
            }
            if (-1 != buckets[m]) {
                ret = max(ret, buckets[m] + e);
            }
            buckets[m] = max(buckets[m], e);
        }
        return ret;
    }
};

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(n)$ 線性遍歷；
空間復(fù)雜度： $O(U)$ 分桶空間。

T2. 翻倍以鏈表形式表示的數(shù)字（Medium）

https://leetcode.cn/problems/double-a-number-represented-as-a-linked-list/

題解一（模擬）

面試類型題，有 $O(1)$ 空間復(fù)雜度的寫法：

先反轉(zhuǎn)鏈表，再依次順序翻倍，最后再反轉(zhuǎn)回來；
需要注意最后剩余一個(gè)進(jìn)位的情況需要補(bǔ)足節(jié)點(diǎn)。

class Solution {
    fun doubleIt(head: ListNode?): ListNode? {
        // 反轉(zhuǎn)
        val p = reverse(head)
        // 翻倍
        var cur = p
        var append = 0
        while (cur != null) {
            append += cur.`val` * 2
            cur.`val` = append % 10
            append = append / 10
            cur = cur.next
        }
        // 反轉(zhuǎn)
        if (0 == append) return reverse(p)
        return ListNode(append).apply {
            next = reverse(p)
        }
    }
    
    fun reverse(head: ListNode?): ListNode? {
        var p: ListNode? = null
        var q = head
        while (null != q) {
            val next = q.next
            q.next = p
            p = q
            q = next
        }
        return p
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(n)$ 反轉(zhuǎn)與翻倍是線性時(shí)間復(fù)雜度；
空間復(fù)雜度： $O(1)$ 僅使用常量級(jí)別空間。

題解二（一次遍歷優(yōu)化）

我們發(fā)現(xiàn)進(jìn)位只發(fā)生在元素值大于 4 的情況，我們可以提前觀察當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)的元素值是否大于 4，如果是則增加進(jìn)位 1。特別地，當(dāng)首個(gè)元素大于 4 時(shí)需要補(bǔ)足節(jié)點(diǎn)。

class Solution {
    fun doubleIt(head: ListNode?): ListNode? {
        if (head == null) return null
        // 補(bǔ)足
        val newHead = if (head.`val` > 4) {
            ListNode(0).also { it.next = head}
        } else {
            head
        }
        // 翻倍
        var cur: ListNode? = newHead
        while (null != cur) {
            cur.`val` *= 2
            if ((cur?.next?.`val` ?: 0) > 4) cur.`val` += 1
            cur.`val` %= 10
            cur = cur.next
        }
        return newHead
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(n)$ 線性遍歷；
空間復(fù)雜度： $O(1)$ 僅使用常量級(jí)別空間。

相似題目：

445. 兩數(shù)相加 II

T3. 限制條件下元素之間的最小絕對(duì)差（Medium）

https://leetcode.cn/problems/minimum-absolute-difference-between-elements-with-constraint/

題解（雙指針 + 平衡樹）

滑動(dòng)窗口的變型題，常規(guī)的滑動(dòng)窗口是限定在窗口大小在 x 內(nèi)，而這道題是排除到窗口外。萬變不離其宗，還得是雙指針。
其次，為了讓元素配對(duì)的差值絕對(duì)值盡可能小，應(yīng)該使用與其元素值相近最大和最小的兩個(gè)數(shù)，可以用平衡樹在 O(lgn) 時(shí)間復(fù)雜度內(nèi)求得，整體時(shí)間復(fù)雜度是 O(ngln)；

class Solution {
    fun minAbsoluteDifference(nums: List<Int>, x: Int): Int {
        if (x == 0) return 0 // 特判
        var ret = Integer.MAX_VALUE
        val n = nums.size
        val set = TreeSet<Int>()
        for (i in x until n) {
            // 滑動(dòng)
            set.add(nums[i - x])
            val q = set.floor(nums[i])
            val p = set.ceiling(nums[i])
            if (p != null) ret = Math.min(ret, Math.abs(p - nums[i]))
            if (q != null) ret = Math.min(ret, Math.abs(nums[i] - q))
        }
        return ret 
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(mlgm)$ 其中 m = n - x，內(nèi)層循環(huán)二分搜索的時(shí)間復(fù)雜度是 $O(lgm)$ ；
空間復(fù)雜度： $O(m)$ 平衡樹空間。

T4. 操作使得分最大（Hard）

https://leetcode.cn/problems/apply-operations-to-maximize-score/

題解一（貪心 + 排序 + 中心擴(kuò)展 + 單調(diào)棧 + 快速冪）

這道題難度不算高，但使用到的技巧還挺綜合的。

閱讀理解： 可以得出影響結(jié)果 3 點(diǎn)關(guān)鍵信息，我們的目標(biāo)是選擇 k 個(gè)子數(shù)組，讓其中質(zhì)數(shù)分?jǐn)?shù)最大的元素 nums[i] 盡量大：
- 1、元素大小
- 2、元素的質(zhì)數(shù)分?jǐn)?shù)
- 3、左邊元素的優(yōu)先級(jí)更高
預(yù)處理： 先預(yù)處理數(shù)據(jù)范圍內(nèi)每個(gè)數(shù)的質(zhì)數(shù)分?jǐn)?shù)，避免在多個(gè)測(cè)試用例間重復(fù)計(jì)算；

質(zhì)因數(shù)分解： 求解元素的質(zhì)數(shù)分?jǐn)?shù)需要質(zhì)因數(shù)分解，有兩種寫法：

暴力寫法，時(shí)間復(fù)雜度 $O(n·\sqrt{n})$ ：

val scores = IntArray(U + 1)
for (e in 1 .. U) {
    var cnt = 0
    var x = e
    var prime = 2
    while (prime * prime <= x) {
        if (x % prime == 0) {
            cnt ++
            while (x % prime == 0) x /= prime // 消除相同因子
        }
        prime++
    }
    if (x > 1) cnt ++ // 剩余的質(zhì)因子
    scores[e] = cnt
}

基于質(zhì)數(shù)篩寫法，時(shí)間復(fù)雜度 O(n)：

val scores = IntArray(U + 1)
for (i in 2 .. U) {
    if (scores[i] != 0) continue // 合數(shù)
    for (j in i .. U step i) {
        scores[j] += 1
    }
}

排序： 根據(jù)關(guān)鍵信息「1、元素大小」可知，我們趨向于選擇包含較大元素值的子數(shù)組，且僅包含數(shù)組元素最大值的子數(shù)組是子數(shù)組分?jǐn)?shù)的上界；
中心擴(kuò)展： 我們先對(duì)所有元素降序排序，依次枚舉子數(shù)組，計(jì)算該元素對(duì)結(jié)果的貢獻(xiàn)，直到該元素?zé)o法構(gòu)造更多子數(shù)組。以位置 i 為中心向左右擴(kuò)展，計(jì)算左右兩邊可以記入子數(shù)組的元素個(gè)數(shù) leftCnt 和 rightCnt。另外，根據(jù) 「左邊元素的優(yōu)先級(jí)更高」的元素，向左邊擴(kuò)展時(shí)不能包含質(zhì)數(shù)分?jǐn)?shù)相同的位置，向右邊擴(kuò)展時(shí)可以包含；
乘法原理： 包含元素 nums[i] 的子數(shù)組個(gè)數(shù)滿足乘法法則（leftCnt * rightCnt）；
單調(diào)棧： 在中心擴(kuò)展時(shí)，我們相當(dāng)于在求「下一個(gè)更大值」元素，這是典型的單調(diào)棧問題，可以在 $O(n)$ 時(shí)間復(fù)雜度內(nèi)求得所有元素的下一個(gè)更大值；
```
val stack = ArrayDeque<Int>()
for (i in 0 until n) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        stack.pop()
    }
    stack.push(i)
}
```

快速冪： 三種寫法：

暴力寫法，時(shí)間復(fù)雜度 O(n)，由于題目 k 比較大會(huì)超出時(shí)間限制：

fun pow(x: Int, n: Int, mod: Int): Int {
    var ret = 1L
    repeat (n){
        ret = (ret * x) % mod
    }
    return ret.toInt()
}

分治寫法，時(shí)間復(fù)雜度是 O(lgn)：

fun pow(x: Int, n: Int, mod: Int): Int {
    if (n == 1) return x
    val subRet = pow(x, n / 2, mod)
    return if (n % 2 == 1) {
        1L * subRet * subRet % mod * x % mod
    } else {
        1L * subRet * subRet % mod
    }.toInt()
}

快速冪寫法，時(shí)間復(fù)雜度 O(C)：

private fun quickPow(x: Int, n: Int, mod: Int): Int {
    var ret = 1L
    var cur = n
    var k = x.toLong()
    while (cur > 0) {
        if (cur % 2 == 1) ret = ret * k % mod
        k = k * k % mod
        cur /= 2
    }
    return ret.toInt()
}

組合以上技巧：

class Solution {
    companion object {
        private val MOD = 1000000007
        private val U = 100000
        private val scores = IntArray(U + 1)
        
        init {
            // 質(zhì)數(shù)篩
            for (i in 2 .. U) {
                if (scores[i] != 0) continue // 合數(shù)
                for (j in i .. U step i) {
                    scores[j] += 1
                }
            }
        }
    }
    
    fun maximumScore(nums: List<Int>, k: Int): Int {
        val n = nums.size
        // 貢獻(xiàn)（子數(shù)組數(shù)）
        val gains1 = IntArray(n) { n - it }
        val gains2 = IntArray(n) { it + 1}
        // 下一個(gè)更大的分?jǐn)?shù)（單調(diào)棧，從棧底到棧頂單調(diào)遞減）
        val stack = ArrayDeque<Int>()
        for (i in 0 until n) {
            while (!stack.isEmpty() && scores[nums[stack.peek()]] < scores[nums[i]]) {
                val j = stack.pop()
                gains1[j] = i - j
            }
            stack.push(i)
        }
        // 上一個(gè)更大元素（單調(diào)棧，從棧底到棧頂單調(diào)遞減）
        stack.clear()
        for (i in n - 1 downTo 0) {
            while(!stack.isEmpty() && scores[nums[stack.peek()]] <= scores[nums[i]]) { // <=
                val j = stack.pop()
                gains2[j] = j - i
            }
            stack.push(i)
        }
        // 按元素值降序
        val ids = Array<Int>(n) { it }
        Arrays.sort(ids) { i1, i2 ->
            nums[i2] - nums[i1]
        }
        // 枚舉每個(gè)元素的貢獻(xiàn)度
        var leftK = k
        var ret = 1L
        for (id in ids.indices) {
            val gain = Math.min(gains1[ids[id]] * gains2[ids[id]], leftK)
            ret = (ret * quickPow(nums[ids[id]], gain, MOD)) % MOD
            leftK -= gain
            if (leftK == 0) break
        }
        return ret.toInt()
    }
    
    // 快速冪
    private fun quickPow(x: Int, n: Int, mod: Int): Int {
        var ret = 1L
        var cur = n
        var k = x.toLong()
        while (cur > 0) {
            if (cur % 2 == 1) ret = ret * k % mod
            k = k * k % mod
            cur /= 2
        }
        return ret.toInt()
    }
}

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(nlgn)$ 其中預(yù)處理時(shí)間為 $O(U)$ ，單次測(cè)試用例中使用單調(diào)棧計(jì)算下一個(gè)更大質(zhì)數(shù)分?jǐn)?shù)的時(shí)間為 $O(n)$ ，排序時(shí)間為 $O(nlgn)$ ，枚舉貢獻(xiàn)度時(shí)間為 $O(n)$ ，整體瓶頸在排序；
空間復(fù)雜度： $O(n)$ 預(yù)處理空間為 $O(U)$ ，單次測(cè)試用例中占用 $O(n)$ 空間。

題解二（一次遍歷優(yōu)化）

在計(jì)算下一個(gè)更大元素時(shí)，在使用 while 維護(hù)單調(diào)棧性質(zhì)后，此時(shí)棧頂即為當(dāng)前元素的前一個(gè)更大元素：

while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
    stack.pop()
}
// 此時(shí)棧頂即為當(dāng)前元素的前一個(gè)更大元素
stack.push(i)

因此我們可以直接在一次遍歷中同時(shí)計(jì)算出前一個(gè)更大元素和下一個(gè)更大元素：

val right = IntArray(n) { n } // 下一個(gè)更大元素的位置
val left = IntArray(n) { -1 } // 上一個(gè)更大元素的位置

計(jì)算貢獻(xiàn)度的方法： $(i - left[i]) * (right[i] - i)$ ，其中 $left[i]$ 和 $right[i]$ 位置不包含在子數(shù)組中。

class Solution {
    ...
    fun maximumScore(nums: List<Int>, k: Int): Int {
        val n = nums.size
        // 貢獻(xiàn)（子數(shù)組數(shù)）
        val right = IntArray(n) { n } // 下一個(gè)更大元素的位置
        val left = IntArray(n) { -1 } // 上一個(gè)更大元素的位置
        // 下一個(gè)更大的分?jǐn)?shù)（單調(diào)棧，從棧底到棧頂單調(diào)遞減）
        val stack = ArrayDeque<Int>()
        for (i in 0 until n) {
            while (!stack.isEmpty() && scores[nums[stack.peek()]] < scores[nums[i]]) {
                right[stack.pop()] = i // 下一個(gè)更大元素的位置
            }
            if (!stack.isEmpty()) left[i] = stack.peek() // 上一個(gè)更大元素的位置
            stack.push(i)
        }
        // 按元素值降序
        val ids = Array<Int>(n) { it }
        Arrays.sort(ids) { i1, i2 ->
            nums[i2] - nums[i1]
        }
        // 枚舉每個(gè)元素的貢獻(xiàn)度
        val gains = IntArray(n) { (it - left[it]) * (right[it] - it)}
        var leftK = k
        var ret = 1L
        for (id in ids.indices) {
            val gain = Math.min(gains[ids[id]], leftK)
            ret = (ret * quickPow(nums[ids[id]], gain, MOD)) % MOD
            leftK -= gain
            if (leftK == 0) break
        }
        return ret.toInt()
    }
    ...
}

復(fù)雜度分析：

同上

相似題目：

907. 子數(shù)組的最小值之和
1856. 子數(shù)組最小乘積的最大值
2104. 子數(shù)組范圍和
2281. 巫師的總力量和

推薦閱讀

LeetCode 上分之旅系列往期回顧：

LeetCode 單周賽第 358 場(chǎng) · 結(jié)合排序不等式的動(dòng)態(tài)規(guī)劃

LeetCode 單周賽第 357 場(chǎng) · 多源 BFS 與連通性問題

LeetCode 雙周賽第 109 場(chǎng) · 按部就班地解決動(dòng)態(tài)規(guī)劃問題

LeetCode 雙周賽第 107 場(chǎng) · 很有意思的 T2 題

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

LeetCode 周賽上分之旅 #39 結(jié)合中心擴(kuò)展的單調(diào)棧貪心問題

LeetCode 周賽上分之旅 #39 結(jié)合中心擴(kuò)展的單調(diào)棧貪心問題

周賽 358

T1. 數(shù)組中的最大數(shù)對(duì)和（Easy）

題解一（分桶 + 數(shù)學(xué)）

題解二（一次遍歷優(yōu)化）

T2. 翻倍以鏈表形式表示的數(shù)字（Medium）

題解一（模擬）

題解二（一次遍歷優(yōu)化）

T3. 限制條件下元素之間的最小絕對(duì)差（Medium）

題解（雙指針 + 平衡樹）

T4. 操作使得分最大（Hard）

題解一（貪心 + 排序 + 中心擴(kuò)展 + 單調(diào)棧 + 快速冪）

題解二（一次遍歷優(yōu)化）

推薦閱讀

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

LeetCode 周賽上分之旅 #39 結(jié)合中心擴(kuò)展的單調(diào)棧貪心問題

周賽 358

T1. 數(shù)組中的最大數(shù)對(duì)和（Easy）

題解一（分桶 + 數(shù)學(xué)）

題解二（一次遍歷優(yōu)化）

T2. 翻倍以鏈表形式表示的數(shù)字（Medium）

題解一（模擬）

題解二（一次遍歷優(yōu)化）

T3. 限制條件下元素之間的最小絕對(duì)差（Medium）

題解（雙指針 + 平衡樹 ）

T4. 操作使得分最大（Hard）

題解一（貪心 + 排序 + 中心擴(kuò)展 + 單調(diào)棧 + 快速冪）

題解二（一次遍歷優(yōu)化）

推薦閱讀

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

題解（雙指針 + 平衡樹）