国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

LeetCode 雙周賽 101,DP/中心位貪心/裴蜀定理/Dijkstra/最小環(huán)

這篇具有很好參考價(jià)值的文章主要介紹了LeetCode 雙周賽 101,DP/中心位貪心/裴蜀定理/Dijkstra/最小環(huán)。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方,請大家不吝賜教,您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

本文已收錄到 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)。

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)!

本文來自互聯(lián)網(wǎng)用戶投稿,該文觀點(diǎn)僅代表作者本人,不代表本站立場。本站僅提供信息存儲(chǔ)空間服務(wù),不擁有所有權(quán),不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載,請注明出處: 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符,請點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋,一經(jīng)查實(shí),立即刪除!

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

  • [LeetCode周賽復(fù)盤] 第 102 場雙周賽20230415

    [LeetCode周賽復(fù)盤] 第 102 場雙周賽20230415

    T4卡了半小時(shí),真的不應(yīng)該。 T1 模擬。 T2 前綴和模擬。 T3 分層遍歷。 T4 floyd/dij(我覺得dij不是正解)。 鏈接: 6333. 查詢網(wǎng)格圖中每一列的寬度 1. 題目描述 2. 思路分析 按題意模擬即可。 3. 代碼實(shí)現(xiàn) 鏈接: 6334. 一個(gè)數(shù)組所有前綴的分?jǐn)?shù) 1. 題目描述 2. 思路分析 不要被題目的一堆

    2023年04月16日
    瀏覽(25)
  • 第 107 場LeetCode雙周賽

    第 107 場LeetCode雙周賽

    A 最大字符串配對數(shù)目 顯然各字符串對 間匹配的先后順序不影響最大匹配數(shù)目, 可以從后往前遍歷數(shù)組, 判斷前面是否有和當(dāng)前末尾構(gòu)成匹配的. B 構(gòu)造最長的新字符串 記憶化搜索: 定義狀態(tài) p a a , b b , a b , l a s t p_{aa,bb,ab,last} p aa , bb , ab , l a s t ? 為剩余三種字符串分別為aa、

    2024年02月11日
    瀏覽(22)
  • leetcode第124場雙周賽

    給你一個(gè)整數(shù)數(shù)組? nums ?,如果? nums ? 至少 ?包含? 2 ?個(gè)元素,你可以執(zhí)行以下操作: 選擇? nums ?中的前兩個(gè)元素并將它們刪除。 一次操作的? 分?jǐn)?shù) ?是被刪除元素的和。 在確保 ?所有操作分?jǐn)?shù)相同 ?的前提下,請你求出? 最多 ?能進(jìn)行多少次操作。 請你返回按照上述

    2024年02月19日
    瀏覽(17)
  • leetcode 122雙周賽 解題思路+代碼

    本人水平有限,只做出3道,最后1道放棄。 給你一個(gè)長度為 n 的整數(shù)數(shù)組 nums 。 一個(gè)數(shù)組的 代價(jià) 是它的 第一個(gè) 元素。比方說,[1,2,3] 的代價(jià)是 1 ,[3,4,1] 的代價(jià)是 3 。 你需要將 nums 分成 3 個(gè) 連續(xù)且沒有交集 的子數(shù)組。 請你返回這些子數(shù)組的 最小 代價(jià) 總和 。 示例 1: 輸

    2024年02月20日
    瀏覽(21)
  • 第 122 場 LeetCode 雙周賽題解

    第 122 場 LeetCode 雙周賽題解

    A 將數(shù)組分成最小總代價(jià)的子數(shù)組 I 枚舉:枚舉后兩個(gè)子數(shù)組的起始下標(biāo) B 判斷一個(gè)數(shù)組是否可以變?yōu)橛行?模擬:模擬冒泡排序的過程,若相鄰元素大小關(guān)系需要交換位置,但其二進(jìn)制下數(shù)位為 1 的數(shù)目不同,則返回false,若完成排序返回true C 通過操作使數(shù)組長度最小 腦筋急

    2024年01月22日
    瀏覽(24)
  • LeetCode 雙周賽 106(2023/06/10)兩道思維題

    本文已收錄到 AndroidFamily,技術(shù)和職場問題,請關(guān)注公眾號(hào) [彭旭銳] 加入知識(shí)星球提問。 往期回顧:LeetCode 單周賽第 348 場 · 數(shù)位 DP 模版學(xué)會(huì)了嗎? T1. 判斷一個(gè)數(shù)是否迷人(Easy) 標(biāo)簽:計(jì)數(shù) T2. 找到最長的半重復(fù)子字符串(Medium) 標(biāo)簽:同向雙指針 T3. 移動(dòng)機(jī)器人(Medi

    2024年02月08日
    瀏覽(24)
  • LeetCode 雙周賽 103(2023/04/29)區(qū)間求和的樹狀數(shù)組經(jīng)典應(yīng)用

    本文已收錄到 AndroidFamily,技術(shù)和職場問題,請關(guān)注公眾號(hào) [彭旭銳] 提問。 大家好,我是小彭。 這場周賽是 LeetCode 雙周賽第 103 場,難得在五一假期第一天打周賽的人數(shù)也沒有少太多。這場比賽前 3 題比較簡單,我們把篇幅留給最后一題。 往期周賽回顧:LeetCode 單周賽第

    2024年02月02日
    瀏覽(23)
  • LeetCode 雙周賽 104(2023/05/13)流水的動(dòng)態(tài)規(guī)劃,鐵打的結(jié)構(gòu)化思考

    本文已收錄到 AndroidFamily,技術(shù)和職場問題,請關(guān)注公眾號(hào) [彭旭銳] 提問。 往期回顧:LeetCode 單周賽第 344 場 · 手寫遞歸函數(shù)的通用套路 T1. 老人的數(shù)目(Easy) 標(biāo)簽:模擬、計(jì)數(shù) T2. 矩陣中的和(Medium) 標(biāo)簽:模擬、排序 T3. 最大或值(Medium) 標(biāo)簽:動(dòng)態(tài)規(guī)劃、前后綴分解

    2024年02月04日
    瀏覽(52)
  • Leetcode 第 108 場雙周賽 Problem C 將字符串分割為最少的美麗子字符串(動(dòng)態(tài)規(guī)劃)

    Leetcode 第 108 場雙周賽 Problem C 將字符串分割為最少的美麗子字符串(動(dòng)態(tài)規(guī)劃) 題目 給你一個(gè)二進(jìn)制字符串 s ,你需要將字符串分割成一個(gè)或者多個(gè) 子字符串 ,使每個(gè)子字符串都是 美麗 的。 如果一個(gè)字符串滿足以下條件,我們稱它是 美麗 的: 它不包含前導(dǎo) 0 。 它是

    2024年02月15日
    瀏覽(23)
  • 裴蜀定理

    目錄 裴蜀定理 OJ實(shí)戰(zhàn) 力扣?1250. 檢查「好數(shù)組」 力扣?2543. 判斷一個(gè)點(diǎn)是否可以到達(dá) 裴蜀定理:若a,b是整數(shù),且gcd(a,b)=d,那么對于任意的整數(shù)x,y,ax+by都一定是d的倍數(shù),特別地,一定存在整數(shù)x,y,使ax+by=d成立。 給你一個(gè)正整數(shù)數(shù)組? nums ,你需要從中任選一些子集,然后將

    2024年02月14日
    瀏覽(16)

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包,優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包