技術文章 » LeetCode 周賽 347（2023/05/28）二維空間上的 LIS 最長遞增子序列問題

LeetCode 周賽 347（2023/05/28）二維空間上的 LIS 最長遞增子序列問題

2023-05-28 18:01:08

本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 提問。

周賽 347 概覽

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

  • 標籤：模擬、字串

T2. 對角線上不同值的數量差（Easy）

  • 標籤：前字尾分解

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

  • 標籤：模擬、貪心

T4. 矩陣中嚴格遞增的單元格數（Hard）

  • 標籤：排序、動態規劃

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()
    }
}

基於正規表示式匹配：

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

複雜度分析：

  • 時間複雜度：$O(n)$
  • 空間複雜度：$O(1)$ 不考慮結果字串

T2. 對角線上不同值的數量差（Easy）

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

題解（前字尾分解）

第一次掃描增加正權，第二次掃描增加負權：

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
    }
}

複雜度分析：

  • 時間複雜度：$O(nm)$
  • 空間複雜度：$O(nm)$

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

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

題解一（模擬）

從中間開始翻轉，將不符合目標的字元向兩端推，選擇反轉到 ‘1’ 和 ‘0’ 兩個方案的最優解：

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'))
    }
}

複雜度分析：

  • 時間複雜度：$O(n)$
  • 空間複雜度：$O(1)$

題解二（找規律）

當相鄰字串不相等時，必然需要反轉。如果接近左邊往左邊翻轉的成本更低，同時，如果接近右邊，往右邊翻轉的成本更低。

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
    }
}

複雜度分析：

  • 時間複雜度：$O(n)$
  • 空間複雜度：$O(1)$

T4. 矩陣中嚴格遞增的單元格數（Hard）

https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/
  • 錯誤思路：

從最大值開始逆向推導，但是最優路徑不一定會經過最大值。

  • 正確思路：

只有小的數位才能到大的數位，因此我們先將所有數位進行排序，對於每個數位儲存其對應的所有位置。此時，每個位置的 LIS 最長序列長度只跟其排序前面的數位中位於同行和同列的數位有關，即前面數位且處於同行同列的最長路徑 + 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
    }
}

複雜度分析：

  • 時間複雜度：$O(nm·lg(nm))$ 瓶頸在排序
  • 空間複雜度：$O(nm)$

往期回顧