本文已收錄到 AndroidFamily，技術(shù)和職場(chǎng)問(wèn)題，請(qǐng)關(guān)注公眾號(hào) [彭旭銳] 提問(wèn)。

• 往期回顧：LeetCode 單周賽第 346 場(chǎng) · 僅 68 人 AK 的最短路問(wèn)題

周賽 347 概覽

T1.?移除字符串中的尾隨零（Easy）

• 標(biāo)簽：模擬、字符串

T2. 對(duì)角線上不同值的數(shù)量差（Easy）

• 標(biāo)簽：前后綴分解

T3. 使所有字符相等的最小成本（Medium）

• 標(biāo)簽：模擬、貪心

T4. 矩陣中嚴(yán)格遞增的單元格數(shù)（Hard）

• 標(biāo)簽：排序、動(dòng)態(tài)規(guī)劃

T1.?移除字符串中的尾隨零（Easy）

https://leetcode.cn/problems/remove-trailing-zeros-from-a-string/

題解（模擬）

基于 StringBuilder：

class Solution {
    fun removeTrailingZeros(num : String): String {
        if (num.length == 1) return num
        val builder = StringBuilder(num)
        while (builder.last() == '0') {
            builder.deleteCharAt(builder.lastIndex)
        }
        return builder.toString()
    }
}

基于正則表達(dá)式匹配：

class Solution {
    fun removeTrailingZeros(num : String): String {
        return num.replace(Regex("0*$"), "")
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$
• 空間復(fù)雜度：$O(1)$ 不考慮結(jié)果字符串

T2. 對(duì)角線上不同值的數(shù)量差（Easy）

https://leetcode.cn/problems/difference-of-number-of-distinct-values-on-diagonals/

題解（前后綴分解）

第一次掃描增加正權(quán)，第二次掃描增加負(fù)權(quán)：

class Solution {
    fun differenceOfDistinctValues(grid: Array<IntArray>): Array<IntArray> {
        // 兩次掃描
        val n = grid.size
        val m = grid[0].size
        val ret = Array(n) { IntArray(m) }
        
        for (row in 0 until n) {
            var i = row
            var j = 0
            val set = HashSet<Int>()
            while (i < n && j < m) {
                ret[i][j] += set.size
                set.add(grid[i][j])
                i++
                j++
            }
        }
        
        for (col in 1 until m) {
            var i = 0
            var j = col
            val set = HashSet<Int>()
            while (i < n && j < m) {
                ret[i][j] = set.size
                set.add(grid[i][j])
                i++
                j++
            }
        }

        for (row in 0 until n) {
            var i = row
            var j = m - 1
            val set = HashSet<Int>()
            while (i >= 0 && j >= 0) {
                ret[i][j] = Math.abs(ret[i][j] - set.size)
                set.add(grid[i][j])
                i--
                j--
            }
        }
        
        for (col in 0 until m - 1) {
            var i = n - 1
            var j = col
            val set = HashSet<Int>()
            while (i >= 0 && j >= 0) {
                ret[i][j] = Math.abs(ret[i][j] - set.size)
                set.add(grid[i][j])
                i--
                j--
            }
        }
        return ret
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(nm)$
• 空間復(fù)雜度：$O(nm)$

T3. 使所有字符相等的最小成本（Medium）

https://leetcode.cn/problems/minimum-cost-to-make-all-characters-equal/

題解一（模擬）

從中間開(kāi)始翻轉(zhuǎn)，將不符合目標(biāo)的字符向兩端推，選擇反轉(zhuǎn)到 ‘1’ 和 ‘0’ 兩個(gè)方案的最優(yōu)解：

class Solution {
    
    private fun op(s:String, target:Char) :Long {
        val n = s.length
        var ret = 0L
        var flag = true
        for (i in n / 2 - 1 downTo 0) {
            if ((flag && s[i] != target) || (!flag && s[i] == target)) {
                ret += i + 1
                flag = !flag
            }
        }
        flag = true
        for (i in n / 2 until n) {
            if ((flag && s[i] != target) || (!flag && s[i] == target)) {
                ret += n - i
                flag = !flag
            }
        }
        return ret
    }
    
    fun minimumCost(s: String): Long {
        return Math.min(op(s,'0'), op(s,'1'))
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$
• 空間復(fù)雜度：$O(1)$

題解二（找規(guī)律）

當(dāng)相鄰字符串不相等時(shí)，必然需要反轉(zhuǎn)。如果接近左邊往左邊翻轉(zhuǎn)的成本更低，同時(shí)，如果接近右邊，往右邊翻轉(zhuǎn)的成本更低。

class Solution {
    fun minimumCost(s: String): Long {
        val n = s.length
        var ret = 0L
        for (i in 1 until n) {
            if (s[i - 1] != s[i]) {
                ret += Math.min(i, n - i)
            }
        }
        return ret
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$
• 空間復(fù)雜度：$O(1)$

T4. 矩陣中嚴(yán)格遞增的單元格數(shù)（Hard）

https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/

• 錯(cuò)誤思路：

從最大值開(kāi)始逆向推導(dǎo)，但是最優(yōu)路徑不一定會(huì)經(jīng)過(guò)最大值。

• 正確思路：

只有小的數(shù)字才能到大的數(shù)字，因此我們先將所有數(shù)字進(jìn)行排序，對(duì)于每個(gè)數(shù)字儲(chǔ)存其對(duì)應(yīng)的所有位置。此時(shí)，每個(gè)位置的 LIS 最長(zhǎng)序列長(zhǎng)度只跟其排序前面的數(shù)字中位于同行和同列的數(shù)字有關(guān)，即前面數(shù)字且處于同行同列的最長(zhǎng)路徑 + 1。

class Solution {
    fun maxIncreasingCells(mat: Array<IntArray>): Int {
        val n = mat.size
        val m = mat[0].size
        var ret = 0
        // 排序
        val map = TreeMap<Int, MutableList<IntArray>>()
        for (i in 0 until n) {
            for (j in 0 until m) {
                map.getOrPut(mat[i][j]) { LinkedList<IntArray>() }.add(intArrayOf(i, j))
            }
        }
        val rowMax = IntArray(n)
        val colMax = IntArray(m)
        // 枚舉
        for ((x, indexs) in map) {
            val mx = IntArray(indexs.size)
            // LIS
            for (i in indexs.indices) {
                mx[i] = Math.max(rowMax[indexs[i][0]], colMax[indexs[i][1]]) + 1
                ret = Math.max(ret, mx[i])
            }
            for (i in indexs.indices) {
                rowMax[indexs[i][0]] = Math.max(rowMax[indexs[i][0]], mx[i])
                colMax[indexs[i][1]] = Math.max(colMax[indexs[i][1]], mx[i])
            }
        }
        return ret
    }
}

復(fù)雜度分析：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-462167.html

• 時(shí)間復(fù)雜度：$O(nm·lg(nm))$ 瓶頸在排序
• 空間復(fù)雜度：$O(nm)$

往期回顧

• LeetCode 單周賽第 346 場(chǎng) · 僅 68 人 AK 的最短路問(wèn)題
• LeetCode 單周賽第 345 場(chǎng) · 體驗(yàn)一題多解的算法之美
• LeetCode 雙周賽第 104 場(chǎng) · 流水的動(dòng)態(tài)規(guī)劃，鐵打的結(jié)構(gòu)化思考
• LeetCode 雙周賽第 103 場(chǎng) · 區(qū)間求和的樹狀數(shù)組經(jīng)典應(yīng)用

到了這里，關(guān)于LeetCode 周賽 347（2023/05/28）二維空間上的 LIS 最長(zhǎng)遞增子序列問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！