日韩久久在线观看,天天日www久久久搞

往期回顧：LeetCode 單周賽第 344 場 · 手寫遞歸函數(shù)的通用套路

T1. 老人的數(shù)目（Easy）

標(biāo)簽：模擬、計數(shù)

T2. 矩陣中的和（Medium）

標(biāo)簽：模擬、排序

T3. 最大或值（Medium）

標(biāo)簽：動態(tài)規(guī)劃、前后綴分解、貪心

T4. 英雄的力量（Hard）

標(biāo)簽：排序、貪心、動態(tài)規(guī)劃、數(shù)學(xué)

T1. 老人的數(shù)目（Easy）

https://leetcode.cn/problems/number-of-senior-citizens/

簡單模擬題，直接截取年齡字符后計數(shù)即可：

class Solution {
    fun countSeniors(details: Array<String>): Int {
        return details.count { it.substring(11, 13).toInt() > 60 }
    }
}

除了將字符串轉(zhuǎn)為整數(shù)再比較外，還可以直接比較子串與 “60” 的字典序：

class Solution {
    fun countSeniors(details: Array<String>): Int {
        return details.count { it.substring(11, 13) > "60" }
    }
}

復(fù)雜度分析：

時間復(fù)雜度： $O(n)$ 其中 n 為 details 數(shù)組的長度；
空間復(fù)雜度： $O(1)$ 僅使用常量級別空間。

T2. 矩陣中的和（Medium）

https://leetcode.cn/problems/sum-in-a-matrix/

簡單模擬題。

先對每一行排序，再取每一列的最大值。

class Solution {
    fun matrixSum(nums: Array<IntArray>): Int {
        var ret = 0
        for (row in nums) {
            row.sort()
        }
        for (j in 0 until nums[0].size) {
            var mx = 0
            for (i in 0 until nums.size) {
                mx = Math.max(mx, nums[i][j])
            }
            ret += mx
        }
        return ret
    }
}

復(fù)雜度分析：

時間復(fù)雜度： $O(nmlgm + nm)$ 其中 n 和 m 分別為矩陣的行數(shù)和列數(shù)，排序時間 $O(nmlgm)$ ，掃描時間 $O(nm)$ ；
空間復(fù)雜度： $O(lgm)$ 排序遞歸?？臻g。

T3. 最大或值（Medium）

https://leetcode.cn/problems/maximum-or/

題目描述

給你一個下標(biāo)從 0 開始長度為 n 的整數(shù)數(shù)組 nums 和一個整數(shù) k 。每一次操作中，你可以選擇一個數(shù)并將它乘 2 。

你最多可以進行 k 次操作，請你返回 **nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示兩個整數(shù) a 和 b 的 按位或 運算。

示例 1：

輸入：nums = [12,9], k = 1
輸出：30
解釋：如果我們對下標(biāo)為 1 的元素進行操作，新的數(shù)組為 [12,18] 。此時得到最優(yōu)答案為 12 和 18 的按位或運算的結(jié)果，也就是 30 。

示例 2：

輸入：nums = [8,1,2], k = 2
輸出：35
解釋：如果我們對下標(biāo) 0 處的元素進行操作，得到新數(shù)組 [32,1,2] 。此時得到最優(yōu)答案為 32|1|2 = 35 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 15

問題結(jié)構(gòu)化

1、概括問題目標(biāo)

計算可以獲得的最大或值。

2、分析問題要件

在每次操作中，可以從數(shù)組中選擇一個數(shù)乘以 2，亦相當(dāng)于向左位移 1 位。

3、觀察問題數(shù)據(jù)

數(shù)據(jù)量：問題數(shù)據(jù)量上界為 $10^5$ ，要求算法時間復(fù)雜度低于 $O(n^2)$ ；
數(shù)據(jù)大小：元素值的上界為 $10^9$ ，操作次數(shù) k 的上界為 15（這個性質(zhì)有什么用呢？）；
輸出結(jié)果：以長整型 Long 的形式返回結(jié)果。

4、觀察測試用例

以示例 1 nums=[12, 9], k = 1 為例，最優(yōu)答案是對 9 乘以 2，說明操作最大值并不一定能獲得最大或值。

5、提高抽象程度

權(quán)重：二進制位越高的位對數(shù)字大小的影響越大，因此我們應(yīng)該盡量讓高位的二進制位置為 1；
是否為決策問題？由于每次操作有多種位置選擇，因此這是一個決策問題。

6、具體化解決手段

1、貪心：結(jié)合「數(shù)據(jù)大小」分析，由于操作次數(shù) k 的上界為 15 次，無論如何位移都不會溢出 Long。因此，我們可以將 k 次位移操作作用在同一個數(shù)字上，盡可能讓高位的位置置為 1；
2、動態(tài)規(guī)劃（背包）：假設(shè)已經(jīng)計算出數(shù)組前 i - 1 個元素能夠組成的最大或值，那么考慮拼接 nums[i]，可以選擇不操作 nums[i]，也可以選擇在 nums[i] 上操作 x 次，那么問題就變成「前 i - 1 個元素中操作 k - x 次的最大或值」與「num[i] 操作 x 次的或值」合并的或值?！盖?i - 1 個元素中操作 k - x 次的最大或值」這是一個與原問題相似但規(guī)模更小的子問題，可以用動態(tài)規(guī)劃解決，更具體地可以用背包問題模型解決。

題解一（貪心 + 前后綴分解）

枚舉所有數(shù)字并向左位移 k 次，計算所有方案的最優(yōu)解：

class Solution {
    fun maximumOr(nums: IntArray, k: Int): Long {
        val n = nums.size
        // 前后綴分解
        val pre = IntArray(n + 1)
        val suf = IntArray(n + 1)
        for (i in 1 .. n) {
            pre[i] = pre[i - 1] or nums[i - 1]
        }
        for (i in n - 1 downTo 0) {
            suf[i] = suf[i + 1] or nums[i]
        }
        var ret = 0L
        for (i in nums.indices) {
            ret = Math.max(ret, (1L * nums[i] shl k) or pre[i].toLong() or suf[i + 1].toLong())
        }
        return ret
    }
}

由于每個方案都需要枚舉前后 n - 1 個數(shù)字的或值，因此這是一個 $O(n^2)$ 的解法，會超出時間限制。我們可以采用空間換時間的策略，預(yù)先計算出每個位置（不包含）的前后綴的或值，這個技巧就是「前后綴分解」。

在實現(xiàn)細(xì)節(jié)上，我們可以把其中一個前綴放在掃描的時候處理。

class Solution {
    fun maximumOr(nums: IntArray, k: Int): Long {
        val n = nums.size
        // 前后綴分解
        val suf = IntArray(n + 1)
        for (i in n - 1 downTo 0) {
            suf[i] = suf[i + 1] or nums[i]
        }
        var ret = 0L
        var pre = 0L
        for (i in nums.indices) {
            ret = Math.max(ret, pre or (1L * nums[i] shl k) or suf[i + 1].toLong())
            pre = pre or nums[i].toLong()
        }
        return ret
    }
}

復(fù)雜度分析：

時間復(fù)雜度： $O(n)$ 其中 n 為 nums 數(shù)組的長度；
空間復(fù)雜度： $O(n)$ 后綴或值數(shù)組長度空間。

題解二（動態(tài)規(guī)劃）

使用背包問題模型時，定義 dp[i][j] 表示在前 i 個元素上操作 k 次可以獲得的最大或值，則有：

狀態(tài)轉(zhuǎn)移方程： $dp[i][j] = max{dp[i-1][j], dp[i - 1][j - x] | (nums[i] << x)}$
終止條件： $dp[n][k]$

 class Solution {
    fun maximumOr(nums: IntArray, k: Int): Long {
        val n = nums.size
        // 以 i 為止，且移動 k 次的最大或值
        val dp = Array(n + 1) { LongArray(k + 1) }
        for (i in 1 .. n) {
            for (j in 0 .. k) {
                for (m in 0 .. j) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - m] or (1L * nums[i - 1] shl m) /* 移動 m 次 */)
                }
            }
        }
        return dp[n][k]
    }
}

另外，這個背包問題可以取消物品維度來優(yōu)化空間：

class Solution {
    fun maximumOr(nums: IntArray, k: Int): Long {
        val n = nums.size
        // 以 i 為止，且移動 k 次的最大或值
        val dp = LongArray(k + 1)
        for (i in 1 .. n) {
            // 逆序
            for (j in k downTo 0) {
                for (m in 0 .. j) {
                    dp[j] = Math.max(dp[j], dp[j - m] or (1L * nums[i - 1] shl m) /* 移動 m 次 */)
                }
            }
        }
        return dp[k]
    }
}

時間復(fù)雜度： $O(n·k^2)$ 其中 n 為 nums 數(shù)組的長度；
空間復(fù)雜度： $O(k)$ DP 數(shù)組空間

相似題目：

238. 除自身以外數(shù)組的乘積
416. 分割等和子集

T4. 英雄的力量（Hard）

https://leetcode.cn/problems/power-of-heroes/

題目描述

給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums ，它表示英雄的能力值。如果我們選出一部分英雄，這組英雄的力量定義為：

i0 ，i1 ，... ik 表示這組英雄在數(shù)組中的下標(biāo)。那么這組英雄的力量為 max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik]) 。

請你返回所有可能的非空英雄組的力量之和。由于答案可能非常大，請你將結(jié)果對 109 + 7 取余。

示例 1：

輸入：nums = [2,1,4]
輸出：141
解釋：
第 1 組：[2] 的力量為 22 * 2 = 8 。
第 2 組：[1] 的力量為 12 * 1 = 1 。
第 3 組：[4] 的力量為 42 * 4 = 64 。
第 4 組：[2,1] 的力量為 22 * 1 = 4 。
第 5 組：[2,4] 的力量為 42 * 2 = 32 。
第 6 組：[1,4] 的力量為 42 * 1 = 16 。
第 7 組：[2,1,4] 的力量為 42 * 1 = 16 。
所有英雄組的力量之和為 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。

示例 2：

輸入：nums = [1,1,1]
輸出：7
解釋：總共有 7 個英雄組，每一組的力量都是 1 。所以所有英雄組的力量之和為 7 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109

問題結(jié)構(gòu)化

1、概括問題目標(biāo)

計算所有組合方案的「力量」總和。

2、分析問題要件

枚舉所有子集，計算子集的力量值計算公式為 $「最大值^2*最小值」$ 。

3、觀察問題數(shù)據(jù)

數(shù)據(jù)量：問題數(shù)據(jù)量上界為 $10^5$ ，要求算法時間復(fù)雜度低于 $O(n^2)$ ；
數(shù)據(jù)大?。涸刂档纳辖鐬? $10^9$ ，乘法運算會溢出整型上界，需要考慮大數(shù)問題。

4、觀察問題測試用例：

以數(shù)組 nums=[1, 2, 3] 為例：

分析小規(guī)模問題：[] 空集的力量值是 0，只包含 1 個元素子集的力量值計算也沒有問題；

子集	最大值	最小值	力量值
{}	0	0	0
{1}	1	1	$1^2*1$
{2}	2	2	$2^2*2$
{3}	3	3	$3^2*3$

分析規(guī)模為 2 的子集問題：

子集	最大值	最小值	力量值
{1, 2}	2	1	$2^2*1$
{1, 3}	3	1	$3^2*1$
{2, 3}	3	2	$3^2*2$

分析規(guī)模為 3 的子集問題：

子集	最大值	最小值	力量值
{1, 2, 3}	3	1	$3^2*1$

5、如何解決問題

手段 1（暴力枚舉）：如果枚舉所有子集，再求每個子集的力量值，那么時間復(fù)雜度會達(dá)到非常高的 $O(n·2^n)$ ，其中有 $2^n$ 種子集（一共有 n 個數(shù)字，每個數(shù)字有選和不選兩種狀態(tài)），每個子集花費 $O(n)$ 線性掃描最大值和最小值。

至此，問題陷入瓶頸，解決方法是重復(fù)以上步驟，枚舉掌握的數(shù)據(jù)結(jié)構(gòu)、算法和技巧尋找思路，突破口在于從另一個角度來理解問題規(guī)模（動態(tài)規(guī)劃的思路）。

6、繼續(xù)觀察問題測試用例

同樣以數(shù)組 nums = [1, 2, 3] 為例：

考慮空集的力量值問題：

子集	最大值	最小值
{}	0	0

考慮到「1」為止的力量值問題：

子集	最大值	最小值
{}	0	0
{1}	1	1

考慮到「2」為止的力量值問題：

子集	最大值	最小值
{}	0	0
{1}	1	1
{2}	2	2
{1, 2}	2	1

考慮到「3」為止的力量值問題：

子集	最大值	最小值
{}	0	0
{1}	1	1
{2}	2	2
{1, 2}	2	1
{3}	3	3
{1,3}	3	1
{2,3}	3	2
{1,2,3}	3	1

這又說明了什么呢？

關(guān)鍵點 1 - 遞推地構(gòu)造子集：

我們發(fā)現(xiàn)子集問題可以用遞推地方式構(gòu)造，當(dāng)我們增加考慮一個新元素時，其實是將已有子集復(fù)制一份后，再復(fù)制的子集里添加元素。例如我們在考慮「2」時，是將 {} 和 {1} 復(fù)制一份后添加再添加元素「2」。

關(guān)鍵點 2 - 最大值的貢獻(xiàn)：

由于我們是從小到大增加元素，所以復(fù)制后新子集中的最大值一定等于當(dāng)前元素，那么問題的關(guān)鍵就在「如何計算這些新子集的最小值」。

關(guān)鍵點 3 - 最小值的貢獻(xiàn)：

由于我們采用子集復(fù)制的方式理解子集構(gòu)造問題，容易發(fā)現(xiàn)數(shù)字越早出現(xiàn)，最小值出現(xiàn)次數(shù)越大（哆啦 A 夢的翻倍藥水）。

例如最初最小值為 1 的子集個數(shù)為 1 次，在處理「2」后最小值為 1 的子集個數(shù)為 2 次，因此在處理「3」時，就會累加 2 次以 1 為最小值的力量值： $2*(3^2*1)$ 。同理會累加 1 次以 2 為最小值的力量值： $1*(3*2*2)$ ，另外還要累加從空集轉(zhuǎn)移而來的 {3}。

至此，問題的解決辦法逐漸清晰。

7、解決問題的新手段

手段 2（動態(tài)規(guī)劃）：

考慮有 a, b, c, d, e 五個數(shù)，按順序從小到大排列，且從小到大枚舉。

當(dāng)枚舉到 d 時，復(fù)制增加的新子集包括：

以 a 為最小值的子集有 4 個：累加力量值 $4*(d^2*a)$
以 b 為最小值的子集有 2 個：累加力量值 $2*(d^2*b)$
以 c 為最小值的子集有 1 個：累加力量值 $1*(d^2*c)$

另外還有以 d 本身為最小值的子集 1 個：累加力量值 $1*(d^2*d)$ ，將 d 左側(cè)元素對結(jié)果的貢獻(xiàn)即為 s，則有 $pow(d) = d^2*(s + d)$ 。

繼續(xù)枚舉到 e 是，復(fù)制增加的新子集包括：

以 a 為最小值的子集有 8 個：累加力量值 $8*(e^2*a)$
以 b 為最小值的子集有 4 個：累加力量值 $4*(e^2*b)$
以 c 為最小值的子集有 2 個：累加力量值 $2*(e^2*c)$
以 d 為最小值的子集有 1個：累加力量值 $1*(e^2*d)$

另外還有以 e 本身為最小值的子集 1 個：累加力量值 $1*(e^2*e)$ ，將 e 左側(cè)元素對結(jié)果的貢獻(xiàn)即為 s`，則有 $pow(e) = e^2*(s` + e)$ 。

觀察 s 和 s` 的關(guān)系：

$s = 4*a + 2*b + 1*c$

$s = 8*a + 4*b + 2*c + d = s*2 + d$

這說明，我們可以維護每個元素左側(cè)元素的貢獻(xiàn)度 s，并通過 s 來計算當(dāng)前元素新增的所有子集的力量值，并且時間復(fù)雜度只需要 O(1)！

[4,3,2,1]
 1 1 2 4
追加 5：
[5,4,3,2,1]
 1 1 2 4 8

題解（動態(tài)規(guī)劃）

根據(jù)問題分析得出的遞歸公式，使用遞推模擬即可，先不考慮大數(shù)問題：

class Solution {
    fun sumOfPower(nums: IntArray): Int {
        var ret = 0L
        // 排序
        nums.sort()
        // 影響因子
        var s = 0L
        for (x in nums) {
            ret += (x * x) * (s + x)
            s = s * 2 + x
        }
        return ret.toInt()
    }
}

再考慮大數(shù)問題：

class Solution {
    fun sumOfPower(nums: IntArray): Int {
        val MOD = 1000000007
        var ret = 0L
        // 排序
        nums.sort()
        // 影響因子
        var s = 0L
        for (x in nums) {
            ret = (ret + (1L * x * x % MOD) * (s + x)) % MOD // x*x 也可能溢出
            s = (s * 2 + x) % MOD
        }
        return ret.toInt()
    }
}

實戰(zhàn)中我用的是先計算最大影響因子，再累減的寫法：

class Solution {
    fun sumOfPower(nums: IntArray): Int {
        val MOD = 1000000007
        var ret = 0L
        val n = nums.size
        // 排序
        nums.sortDescending()
        // 影響因子
        var s = 0L
        var p = 1L
        for (i in 1 until n) {
            s = (s + nums[i] * p) % MOD 
            p = (2 * p) % MOD
        }
        // 枚舉子集
        for (i in 0 until n) {
            val x = nums[i]
            ret = (ret + x * x % MOD * (s + x)) % MOD
            if (i < n - 1) {
                s = (s - nums[i + 1]) % MOD
                if (s and 1L != 0L) {
                    s += MOD // 奇數(shù)除 2 會丟失精度
                }
                s = (s / 2) % MOD
            }
        }
        return ret.toInt()
    }
}

復(fù)雜度分析：

時間復(fù)雜度： $O(nlgn)$ 其中 n 為 nums 數(shù)組的長度，瓶頸在排序上，計算力量值部分時間復(fù)雜度為 O(n)；
空間復(fù)雜度： $O(lgn)$ 排序遞歸棧空間。

往期回顧

LeetCode 單周賽第 344 場 · 手寫遞歸函數(shù)的通用套路
LeetCode 單周賽第 343 場 · 結(jié)合「下一個排列」的貪心構(gòu)造問題
LeetCode 雙周賽第 103 場 · 區(qū)間求和的樹狀數(shù)組經(jīng)典應(yīng)用
LeetCode 雙周賽第 102 場· 這次又是最短路。

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

LeetCode 雙周賽 104（2023/05/13）流水的動態(tài)規(guī)劃，鐵打的結(jié)構(gòu)化思考

LeetCode 雙周賽 104（2023/05/13）流水的動態(tài)規(guī)劃，鐵打的結(jié)構(gòu)化思考

T1. 老人的數(shù)目（Easy）

T2. 矩陣中的和（Medium）

T3. 最大或值（Medium）

題目描述

問題結(jié)構(gòu)化

1、概括問題目標(biāo)

2、分析問題要件

3、觀察問題數(shù)據(jù)

4、觀察測試用例

5、提高抽象程度

6、具體化解決手段

題解一（貪心 + 前后綴分解）

題解二（動態(tài)規(guī)劃）

T4. 英雄的力量（Hard）

題目描述

問題結(jié)構(gòu)化

1、概括問題目標(biāo)

2、分析問題要件

3、觀察問題數(shù)據(jù)

4、觀察問題測試用例：

5、如何解決問題

6、繼續(xù)觀察問題測試用例

7、解決問題的新手段

題解（動態(tài)規(guī)劃）

往期回顧

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

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

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

LeetCode 雙周賽 104（2023/05/13）流水的動態(tài)規(guī)劃，鐵打的結(jié)構(gòu)化思考

T1. 老人的數(shù)目（Easy）

T2. 矩陣中的和（Medium）

T3. 最大或值（Medium）

題目描述

問題結(jié)構(gòu)化

1、概括問題目標(biāo)

2、分析問題要件

3、觀察問題數(shù)據(jù)

4、觀察測試用例

5、提高抽象程度

6、具體化解決手段

題解一（貪心 + 前后綴分解）

題解二（動態(tài)規(guī)劃）

T4. 英雄的力量（Hard）

題目描述

問題結(jié)構(gòu)化

1、概括問題目標(biāo)

2、分析問題要件

3、觀察問題數(shù)據(jù)

4、觀察問題測試用例：

5、如何解決問題

6、繼續(xù)觀察問題測試用例

7、解決問題的新手段

題解（動態(tài)規(guī)劃）

往期回顧

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

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

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

LeetCode 雙周賽 104（2023/05/13）流水的動態(tài)規(guī)劃，鐵打的結(jié)構(gòu)化思考

4、觀察測試用例

5、提高抽象程度

6、具體化解決手段

1、概括問題目標(biāo)

2、分析問題要件

3、觀察問題數(shù)據(jù)

4、觀察問題測試用例：

5、如何解決問題

7、解決問題的新手段