本文已收錄到 AndroidFamily,技術(shù)和職場問題,請關(guān)注公眾號(hào) [彭旭銳] 提問。
大家好,我是小彭。
這周比較忙,上周末的雙周賽題解現(xiàn)在才更新,雖遲但到哈。上周末這場是 LeetCode 第 101 場雙周賽,整體有點(diǎn)難度,第 3 題似乎比第 4 題還難一些。
周賽大綱
2605.?從兩個(gè)數(shù)字?jǐn)?shù)組里生成最小數(shù)字(Easy)
- 題解一:散列表 $O(n + m)$ 空間
- 題解二:位運(yùn)算 $O(1)$ 空間
2606.?找到最大開銷的子字符串(Medium)
- 動(dòng)態(tài)規(guī)劃 O(n)
2607.?使子數(shù)組元素和相等(Medium)
- 題解 1:拼接數(shù)組 + 中位數(shù)貪心 · 錯(cuò)誤
- 題解 2:數(shù)組分組 + 中位數(shù)貪心 $O(nlgn)$
- 題解 3:裴蜀定理 + 中位數(shù)貪心 $O(nlgn)$
- 題解 4:裴蜀定理 + 中位數(shù)貪心 + 快速選擇 $O(n)$
2608.?圖中的最短環(huán)(Hard)
- 題解 1:枚舉邊 + Dijkstra 最短路 + 最小堆 $O(m + m^2·lgn)$
- 題解 2:枚舉邊 + BFS $O(m + m^2)$
2605.?從兩個(gè)數(shù)字?jǐn)?shù)組里生成最小數(shù)字(Easy)
題目地址
https://leetcode.cn/problems/form-smallest-number-from-two-digit-arrays/description/
題目描述
給你兩個(gè)只包含 1 到 9 之間數(shù)字的數(shù)組?nums1
?和?nums2
?,每個(gè)數(shù)組中的元素?互不相同?,請你返回?最小?的數(shù)字,兩個(gè)數(shù)組都?至少?包含這個(gè)數(shù)字的某個(gè)數(shù)位。
題解一(散列表)
簡單模擬題,需要對 API 比較熟悉才能寫出精煉的代碼。
思路:優(yōu)先選擇兩個(gè)數(shù)組交集的最小值,否則取兩個(gè)數(shù)組的最小值再拼接。
class Solution {
fun minNumber(nums1: IntArray, nums2: IntArray): Int {
val set1 = nums1.toHashSet()
val set2 = nums2.toHashSet()
// 優(yōu)先選擇交集
val set = set1.intersect(set2)
if (!set.isEmpty()) return Collections.min(set)
// 選擇最小值
val min1 = Collections.min(set1)
val min2 = Collections.min(set2)
// 拼接
return Math.min(10 * min1 + min2, 10 * min2 + min1)
}
}
復(fù)雜度分析:
- 時(shí)間復(fù)雜度:$O(n + m)$ 其中 $n$ 是 $nums1$ 數(shù)組的長度,$m$ 是 $nums2$ 數(shù)組的長度;
- 空間復(fù)雜度:$O(n + m)$ 散列表空間
題解二(位運(yùn)算)
使用二進(jìn)制位標(biāo)記代替散列表
class Solution {
fun minNumber(nums1: IntArray, nums2: IntArray): Int {
var flag1 = 0
var flag2 = 0
for (num in nums1) {
flag1 = flag1 or (1 shl num)
}
for (num in nums2) {
flag2 = flag2 or (1 shl num)
}
// numberOfTrailingZeros:最低位連續(xù) 0 的個(gè)數(shù)
// 交集
val flag = flag1 and flag2
if (flag > 0) return Integer.numberOfTrailingZeros(flag)
// 最小值
val min1 = Integer.numberOfTrailingZeros(flag1)
val min2 = Integer.numberOfTrailingZeros(flag2)
// 拼接
return Math.min(10 * min1 + min2, 10 * min2 + min1)
}
}
復(fù)雜度分析:
- 時(shí)間復(fù)雜度:$O(n + m)$ 其中 $n$ 是 $nums1$ 數(shù)組的長度,$m$ 是 $nums2$ 數(shù)組的長度;
- 空間復(fù)雜度:$O(1)$ 散列表空間
2606.?找到最大開銷的子字符串(Medium)
題目地址
https://leetcode.cn/problems/find-the-substring-with-maximum-cost/
題目描述
給你一個(gè)字符串?s
?,一個(gè)字符?互不相同?的字符串?chars
?和一個(gè)長度與?chars
?相同的整數(shù)數(shù)組?vals
?。
子字符串的開銷?是一個(gè)子字符串中所有字符對應(yīng)價(jià)值之和??兆址拈_銷是?0
?。
字符的價(jià)值?定義如下:
- 如果字符不在字符串?
chars
?中,那么它的價(jià)值是它在字母表中的位置(下標(biāo)從?1?開始)。- 比方說,
'a'
?的價(jià)值為?1
?,'b'
?的價(jià)值為?2
?,以此類推,'z'
?的價(jià)值為?26
?。
- 比方說,
- 否則,如果這個(gè)字符在?
chars
?中的位置為?i
?,那么它的價(jià)值就是?vals[i]
?。
請你返回字符串?s
?的所有子字符串中的最大開銷。
題解(動(dòng)態(tài)規(guī)劃)
簡單動(dòng)態(tài)規(guī)劃問題。
先根據(jù)題意維護(hù) a-z
每個(gè)字母的開銷,再求 53. 最長子數(shù)組和 問題。
定義 dp[i] 表示以 [i] 為結(jié)尾的最大子數(shù)組和,則有
- 與 $a[0, i - 1]$ 拼接:$dp[i] = dp[i - 1] + vals[i]$
- 不與 $a[i - 1]$ 拼接(單獨(dú)作為子數(shù)組):$dp[i] = vals[i]$
class Solution {
fun maximumCostSubstring(s: String, chars: String, vals: IntArray): Int {
// 初值
val fullVals = IntArray(26) { it + 1 }
// 更新
for ((i, c) in chars.withIndex()) {
fullVals[c - 'a'] = vals[i]
}
// 動(dòng)態(tài)規(guī)劃
val n = s.length
var max = 0
val dp = IntArray(n + 1)
for (i in 1..n) {
val curValue = fullVals[s[i - 1] - 'a']
dp[i] = Math.max(curValue, dp[i - 1] + curValue)
max = Math.max(max, dp[i])
}
return max
}
}
滾動(dòng)數(shù)組優(yōu)化:
class Solution {
fun maximumCostSubstring(s: String, chars: String, vals: IntArray): Int {
// 初值
val fullVals = IntArray(26) { it + 1 }
// 更新
for ((i, c) in chars.withIndex()) {
fullVals[c - 'a'] = vals[i]
}
// 動(dòng)態(tài)規(guī)劃
val n = s.length
var max = 0
var pre = 0
for (i in 1..n) {
val curValue = fullVals[s[i - 1] - 'a']
pre = Math.max(curValue, pre + curValue)
max = Math.max(max, pre)
}
return max
}
}
另一種理解,視為 vals[i] 總與前序子數(shù)組拼接,而前序子數(shù)組的權(quán)值不低于 0:
- $dp[i] = Math.max(dp[i - 1], 0) + vals[i]$
class Solution {
fun maximumCostSubstring(s: String, chars: String, vals: IntArray): Int {
// 初值
val fullVals = IntArray(26) { it + 1}
// 更新
for ((i, c) in chars.withIndex()) {
fullVals[c - 'a'] = vals[i]
}
// 動(dòng)態(tài)規(guī)劃
val n = s.length
var max = 0
var pre = 0
for (i in 1..n) {
pre = Math.max(pre, 0) + fullVals[s[i - 1] - 'a']
max = Math.max(max, pre)
}
return max
}
}
2607.?使子數(shù)組元素和相等(Medium)
題目地址
https://leetcode.cn/problems/make-k-subarray-sums-equal/
題目描述
給你一個(gè)下標(biāo)從?0?開始的整數(shù)數(shù)組?arr
?和一個(gè)整數(shù)?k
?。數(shù)組?arr
?是一個(gè)循環(huán)數(shù)組。換句話說,數(shù)組中的最后一個(gè)元素的下一個(gè)元素是數(shù)組中的第一個(gè)元素,數(shù)組中第一個(gè)元素的前一個(gè)元素是數(shù)組中的最后一個(gè)元素。
你可以執(zhí)行下述運(yùn)算任意次:
- 選中?
arr
?中任意一個(gè)元素,并使其值加上?1
?或減去?1
?。
執(zhí)行運(yùn)算使每個(gè)長度為?k
?的?子數(shù)組?的元素總和都相等,返回所需要的最少運(yùn)算次數(shù)。
子數(shù)組?是數(shù)組的一個(gè)連續(xù)部分。
問題分析
分析 1: 先不考慮循環(huán)數(shù)組的前提,分析數(shù)據(jù)約束 “對于滿足每個(gè)長度為 k 的子數(shù)組的和相等”,那么
$a[i]+a[i+1] +…+a[i+k-1] == a[i+1]+a[i+2]+…+a[i+k-1]+a[i+k]$
等式兩邊化簡得:
$a[i]=a[i+k]$
也就是說,數(shù)組上每間隔 k 的元素要相等。因此我們需要將每間隔 k 的元素分為一組,再將組內(nèi)元素調(diào)整為相等值;
分析 2: 如何將組內(nèi)元素調(diào)整為相等值呢?可以證明選擇中位數(shù)的貪心做法是最優(yōu)的。
分析 3: 考慮循環(huán)數(shù)組的前提,對于 i + k ≥ len(arr) 的情況,需要對數(shù)組下標(biāo)取模來模擬循環(huán)
題解一(拼接數(shù)組 + 中位數(shù)貪心 · 錯(cuò)誤)
循環(huán)數(shù)組有拼接一倍數(shù)組的模擬做法,我們模擬出 2*n 長度的數(shù)組,在訪問每個(gè)位置時(shí),將所有同組的數(shù)組分為一組,再排序取中位數(shù)。
不過,這個(gè)思路在這道題里是不對的,因?yàn)橥粋€(gè)分組有可能循環(huán)多輪才會(huì)遇到。即使不考慮錯(cuò)誤,在這道題的數(shù)據(jù)范圍上也會(huì)內(nèi)存溢出。
錯(cuò)誤測試用例:$arr = [1, 5, 8, 10], k = 3$
class Solution {
fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
val n = arr.size
var ret = 0L
// 延長一倍數(shù)組
val visited = BooleanArray(2 * n)
for (i in 0 until 2 * n) {
if (visited[i]) continue
// 分組
val bucket = ArrayList<Int>()
for (j in i until 2 * n step k) {
bucket.add(arr[j % n])
visited[j] = true
}
// 排序
Collections.sort(bucket)
// println(bucket.joinToString())
// 中位數(shù)貪心
val midVal = bucket[bucket.size / 2]
for (element in bucket) {
ret += Math.abs(element - midVal)
}
}
return ret / 2 // 擴(kuò)充了一倍數(shù)組,所以操作數(shù)也翻倍了
}
}
題解二(數(shù)組分組 + 中位數(shù)貪心)
既然不能使用數(shù)組,那么可以在內(nèi)存循環(huán)中一直循環(huán)取同分組為止,直到出現(xiàn)回環(huán)后退出:
class Solution {
fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
val n = arr.size
var ret = 0L
val visited = BooleanArray(n)
for (i in 0 until n) {
if (visited[i]) continue
// 分組
val bucket = ArrayList<Int>()
var j = i
while (!visited[j]) {
bucket.add(arr[j % n])
visited[j] = true
j = (j + k) % n
}
// 排序
Collections.sort(bucket)
// 中位數(shù)貪心
val midVal = bucket[bucket.size / 2]
for (element in bucket) {
ret += Math.abs(element - midVal)
}
}
return ret
}
}
復(fù)雜度分析:
- 時(shí)間復(fù)雜度:$O(nlgn)$ 其中 $n$ 為 $arr$ 數(shù)組長度,每個(gè)元素最多訪問一次,且排序一次,所以整體時(shí)間是 $O(nlgn)$;
- 空間復(fù)雜度:$O(n + lgn)$ 標(biāo)記數(shù)組空間 + 排序遞歸??臻g。
題解三(裴蜀定理 + 中位數(shù)貪心)
根據(jù)前文分析,我們需要保證最終數(shù)組是以 $k$ 為循環(huán)周期的,而循環(huán)數(shù)組本身又是以 $n$ 為循環(huán)周期的。根據(jù) 裴蜀定理 ,如果一個(gè)數(shù)組存在周期 $k$ 和周期 $n$,那么必然存在周期 $gcb(k, n)$,而 $gcb(k, n)$ 必然小于 $n$,我們就將問題變成非循環(huán)數(shù)組問題。
- 裴蜀定理:設(shè) a,b 是不全為零的整數(shù),則存在整數(shù) x , y,使得 ax + by = gcb(a,b)
class Solution {
fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
val n = arr.size
// 最大公約數(shù)
val m = gcb(n, k)
var ret = 0L
// 最多只有 m 組
for (i in 0 until m) {
// 分組
val bucket = ArrayList<Int>()
for (j in i until n step m) {
bucket.add(arr[j])
}
// 排序
Collections.sort(bucket)
val midVal = bucket[bucket.size / 2]
for (element in bucket) {
ret += Math.abs(element - midVal)
}
}
return ret
}
private fun gcb(a: Int, b: Int): Int {
if (b == 0) return a
return gcb(b, a % b)
}
}
復(fù)雜度分析:
- 時(shí)間復(fù)雜度:$O(nlgn)$ 其中 $n$ 為 $arr$ 數(shù)組長度,每個(gè)元素最多訪問一次,且排序一次,所以整體時(shí)間是 $O(nlgn)$;
- 空間復(fù)雜度:$O(n + lgn)$ 分組空間 + 排序遞歸??臻g,分組空間最大為 $n$;
題解四(裴蜀定理 + 中位數(shù)貪心 + 快速選擇)
排序是為了尋找中位數(shù),沒必要對整個(gè)分組排序,可以優(yōu)化為快速選擇,時(shí)間復(fù)雜度優(yōu)化到 $O(n)$,Nice!
class Solution {
fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
val n = arr.size
// 最大公約數(shù)
val m = gcb(n, k)
var ret = 0L
// 最多只有 m 組
for (i in 0 until m) {
// 分組
val bucket = ArrayList<Int>()
for (j in i until n step m) {
bucket.add(arr[j])
}
// 快速選擇
quickSelect(bucket)
val midVal = bucket[bucket.size / 2]
for (element in bucket) {
ret += Math.abs(element - midVal)
}
}
return ret
}
// 快速選擇中位數(shù)
private fun quickSelect(bucket: ArrayList<Int>) {
val mid = bucket.size / 2
var left = 0
var right = bucket.size - 1
while (true) {
val pivot = partition(bucket, left, right)
if (mid == pivot) {
break
} else if (pivot < mid) {
left = pivot + 1
} else {
right = pivot - 1
}
}
}
// return:分區(qū)
private fun partition(bucket: ArrayList<Int>, left: Int, right: Int): Int {
var p = left
for (i in left until right) {
if (bucket[i] < bucket[right]) {
bucket.swap(p++, i)
}
}
bucket.swap(p, right)
return p
}
private fun <T> ArrayList<T>.swap(first: Int, second: Int) {
val temp = this[first]
this[first] = this[second]
this[second] = temp
}
// 迭代寫法
private fun gcb(a: Int, b: Int): Int {
var x = a
var y = b
while (y != 0) {
val temp = x % y
x = y
y = temp
}
return x
}
}
復(fù)雜度分析:
- 時(shí)間復(fù)雜度:$O(n)$ 其中 $n$ 為 $arr$ 數(shù)組長度,每個(gè)元素最多訪問一次;
- 空間復(fù)雜度:$O(n)$ 分組空間,分組空間最大為 $n$;
相似題目:
- 462. 最小操作次數(shù)使數(shù)組元素相等 II
2608.?圖中的最短環(huán)(Hard)
題目地址
https://leetcode.cn/problems/shortest-cycle-in-a-graph/
題目描述
現(xiàn)有一個(gè)含?n
?個(gè)頂點(diǎn)的?雙向?圖,每個(gè)頂點(diǎn)按從?0
?到?n - 1
?標(biāo)記。圖中的邊由二維整數(shù)數(shù)組?edges
?表示,其中?edges[i] = [ui, vi]
?表示頂點(diǎn)?ui
?和?vi
?之間存在一條邊。每對頂點(diǎn)最多通過一條邊連接,并且不存在與自身相連的頂點(diǎn)。
返回圖中?最短?環(huán)的長度。如果不存在環(huán),則返回?-1
?。
環(huán)?是指以同一節(jié)點(diǎn)開始和結(jié)束,并且路徑中的每條邊僅使用一次。
題解一(枚舉邊 + Dijkstra 最短路 + 最小堆)
這道題是 最小環(huán) 模板題:給出一個(gè)圖,問圖中邊權(quán)和最小的環(huán)是多大,圖的最小環(huán)也稱圍長。
暴力解法:對于每條邊 $(u, v)$,求不經(jīng)過 $(u,v)$ 邊從 $u$ 到 $v$ 的最短路 $len$,那么包含 $(u,v)$ 的最短環(huán)就是 $len + 1$。枚舉所有邊,則所有答案的最小值就是圖的最小環(huán)。
class Solution {
private val INF = Integer.MAX_VALUE
fun findShortestCycle(n: Int, edges: Array<IntArray>): Int {
// 建圖
val graph = Array(n) { ArrayList<Int>() }.apply {
for (edge in edges) {
this[edge[0]].add(edge[1])
this[edge[1]].add(edge[0])
}
}
// 枚舉邊
var ret = INF
for (edge in edges) {
ret = Math.min(ret, dijkstra(graph, edge[0], edge[1]))
}
return if (INF == ret) -1 else ret
}
private fun dijkstra(graph: Array<ArrayList<Int>>, u: Int, v: Int): Int {
// 最短路長度
val dis = IntArray(graph.size) { INF }.apply {
this[u] = 0
}
// 最小堆
val heap = PriorityQueue<Int>() { e1, e2 ->
dis[e1] - dis[e2]
}.apply {
this.offer(u)
}
// BFS
outer@ while (!heap.isEmpty()) {
// 使用 O(lgn) 找出已選集中最短路長度最小的節(jié)點(diǎn)
val x = heap.poll()
// 松弛相鄰點(diǎn)
for (y in graph[x]) {
// 忽略 (u, v) 邊
if (x == u && y == v) continue
if (dis[x] + 1 /* 邊權(quán)為 1 */ < dis[y]) {
dis[y] = dis[x] + 1
heap.offer(y)
}
// 找到 u -> v 的最短路
if (y == v) break@outer
}
}
return if(INF == dis[v]) INF else dis[v] + 1
}
}
復(fù)雜度分析:
- 時(shí)間復(fù)雜度:$O(m + m^2·lgn)$ 其中 $n$ 為頂點(diǎn)個(gè)數(shù),$m$ 為邊個(gè)數(shù),每條邊跑 Dijkstra 最短路每輪迭代以 $O(lgn)$ 取出已選集中最短路長度最小的節(jié)點(diǎn),每次 Dijkstra 的時(shí)間是 $O(m·lgn)$;
- 空間復(fù)雜度:$O(m + n)$ 圖空間 + 最小堆空間,使用鄰接表可以降低空間到 $O(m + n)$。
題解二(枚舉邊 + BFS)
由于這道題的邊權(quán)是 1,所以不需要使用高級(jí)的圖論算法也能做。
為什么呢,因?yàn)槊總€(gè)邊權(quán)的長度是 1,所以已經(jīng)訪問過的節(jié)點(diǎn)是不會(huì)存在更短路徑的。所以我們不需要使用堆,直接使用隊(duì)列,最先進(jìn)入隊(duì)列中的節(jié)點(diǎn)一定是最短路長度最短的節(jié)點(diǎn)。文章來源:http://www.zghlxwxcb.cn/news/detail-405868.html
class Solution {
private val INF = Integer.MAX_VALUE
fun findShortestCycle(n: Int, edges: Array<IntArray>): Int {
// 建圖
val graph = Array(n) { ArrayList<Int>() }.apply {
for (edge in edges) {
this[edge[0]].add(edge[1])
this[edge[1]].add(edge[0])
}
}
// 枚舉邊
var ret = INF
for (edge in edges) {
ret = Math.min(ret, bfs(graph, edge[0], edge[1]))
}
return if (INF == ret) -1 else ret
}
private fun bfs(graph: Array<ArrayList<Int>>, u: Int, v: Int): Int {
// 最短路長度
val dis = IntArray(graph.size) { INF }.apply {
this[u] = 0
}
// 最小堆
val queue = LinkedList<Int>().apply {
this.offer(u)
}
// BFS
outer@ while (!queue.isEmpty()) {
// 取隊(duì)頭
val x = queue.poll()
// 松弛相鄰點(diǎn)
for (y in graph[x]) {
// 忽略 (u, v) 邊
if (x == u && y == v) continue
// 已經(jīng)訪問過的節(jié)點(diǎn)不會(huì)存在更短路
if (INF != dis[y]) continue
dis[y] = dis[x] + 1
queue.offer(y)
// 找到 u -> v 的最短路
if (y == v) break@outer
}
}
return if (INF == dis[v]) INF else dis[v] + 1
}
}
復(fù)雜度分析:文章來源地址http://www.zghlxwxcb.cn/news/detail-405868.html
- 時(shí)間復(fù)雜度:$O(m + m^2)$ 在每輪 BFS 中,每條邊最多訪問 2 次,因此每輪 BFS 的時(shí)間復(fù)雜度是 $O(m)$;
- 空間復(fù)雜度:$O(m + n)$。
到了這里,關(guān)于LeetCode 雙周賽 101,DP/中心位貪心/裴蜀定理/Dijkstra/最小環(huán)的文章就介紹完了。如果您還想了解更多內(nèi)容,請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!