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

• 往期回顧：LeetCode 單周賽第 348 場(chǎng) · 數(shù)位 DP 模版學(xué)會(huì)了嗎？

雙周賽 106 概覽

T1. 判斷一個(gè)數(shù)是否迷人（Easy）

• 標(biāo)簽：計(jì)數(shù)

T2. 找到最長(zhǎng)的半重復(fù)子字符串（Medium）

• 標(biāo)簽：同向雙指針

T3. 移動(dòng)機(jī)器人（Medium）

• 標(biāo)簽：腦筋急轉(zhuǎn)彎、排序

T4. 找到矩陣中的好子集（Hard）

• 標(biāo)簽：散列表、貪心

T1. 判斷一個(gè)數(shù)是否迷人（Easy）

https://leetcode.cn/problems/check-if-the-number-is-fascinating/description/

題解一（計(jì)數(shù)）

• 計(jì)算拼接后的數(shù)字，并檢查數(shù)字 1 到 9 的數(shù)量是否為 1，可以用字符串比較來模擬計(jì)數(shù)；
• 觀察數(shù)字規(guī)律，合法 n 的有效范圍是 [123, 329]。

class Solution {
    fun isFascinating(n: Int): Boolean {
        if (n !in 123..329) return false
        return "123456789" == "$n${2*n}${3*n}".asSequence().sorted().joinToString("")
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(UlgU) U 是單個(gè)數(shù)字的最大長(zhǎng)度
• 空間復(fù)雜度：O(U)

題解二（打表）

題目范圍中只有 4 個(gè)迷人數(shù)。

class Solution {
    fun isFascinating(n: Int): Boolean {
        return n in arrayOf(192, 219, 273, 327)
    }
}

復(fù)雜度分析：

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

T2. 找到最長(zhǎng)的半重復(fù)子字符串（Medium）

https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/

題解（同向雙指針）

維護(hù)滑動(dòng)窗口，如果右指針與前一個(gè)位置相同，說明增加一個(gè)相鄰重復(fù)對(duì)。

當(dāng)相鄰重復(fù)對(duì) repeatCnt 大于 1 時(shí)，此時(shí)需要收縮左指針，如果左指針與右邊后一個(gè)位置相同，說明減少一個(gè)相鄰重復(fù)對(duì)（由于 repeatCnt 大于 1 時(shí)左指針不可能超過窗口，所以不需要檢查左指針移動(dòng)越界）。

class Solution {
    fun longestSemiRepetitiveSubstring(s: String): Int {
        val n = s.length
        var ret = 0
        var i = 0
        var repeatCnt = 0
        for (j in 0 until n) {
            // 移動(dòng)右指針
            if (j > 0 && s[j] == s[j - 1]) repeatCnt ++
            while (repeatCnt > 1) {
                // 移動(dòng)左指針
                if (s[i] == s[i + 1]) repeatCnt --
                i++
            }
            // 記錄結(jié)果
            ret = Math.max(ret, j - i + 1)
        }
        return ret
    }
}

復(fù)雜度分析：

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

T3. 移動(dòng)機(jī)器人（Medium）

https://leetcode.cn/problems/movement-of-robots/

題解（模擬 + 排序）

注意到當(dāng)發(fā)生碰撞而改變機(jī)器人方向時(shí)，我們可以對(duì)調(diào)機(jī)器人身份，此時(shí)等價(jià)于沒有發(fā)生碰撞且機(jī)器人按照正常方向行駛，因此我們可以直接忽視碰撞規(guī)則，計(jì)算機(jī)器人的最終位置并計(jì)算兩兩距離。

為了計(jì)算兩兩距離，我們先對(duì)所有點(diǎn)排序。由于兩個(gè)機(jī)器人的距離公式是 x - y，那么對(duì)于每個(gè)機(jī)器人 nums[i]，在距離公式中它將作為 i 次 x 做加法，以及作為 (n -1 - i) 次 y 做解法，可以枚舉每個(gè)機(jī)器人對(duì)距離公式的貢獻(xiàn)度而算出整體的兩兩距離和。

class Solution {
    fun sumDistance(nums: IntArray, s: String, d: Int): Int {
        val n = nums.size
        val MOD = 1000000007
        // 移動(dòng)（忽視碰撞）
        for (i in nums.indices) {
            nums[i] += if (s[i] == 'R') d else -d
        }
        // 排序
        nums.sort()
        // 計(jì)算兩兩距離
        var ret = 0L
        for (i in nums.indices) {
            ret = (ret + (2L * i - n + 1) * nums[i]) % MOD
        }
        return ret.toInt()
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(nlgn) 瓶頸在排序
• 空間復(fù)雜度：O(lgn)

相似題目：

• 1503.?所有螞蟻掉下來前的最后一刻

T4. 找到矩陣中的好子集（Hard）

https://leetcode.cn/problems/find-a-good-subset-of-the-matrix/

題解（散列 + 貪心）

容易想到，我們需要選擇出 1 相對(duì)稀疏的那些行（但不一定是最稀疏的行），而且重復(fù)選擇完全相同的行不會(huì)對(duì)結(jié)果產(chǎn)生價(jià)值，所以我們先對(duì)行去重。

由于題目最多只有5 列，所有最多只有 2^5=32 種行類型，可以證明題目在 n = 5 的情況下，有效解最多只有 2 行。

class Solution {
    fun goodSubsetofBinaryMatrix(grid: Array<IntArray>): List<Int> {
        val n = grid.size
        val m = grid[0].size
        // 分組
        val U = 32 // 0 - 31
        val indexs = IntArray(U) { -1 }
        for ((i, row) in grid.withIndex()) {
            var mask = 0
            for ((j, e) in row.withIndex()) {
                mask = mask or (e shl j)
            }
            indexs[mask] = i
        }
        // 全 0
        if (-1 != indexs[0]) return listOf(indexs[0])
        // 貪心
        for (x in 1 until U) {
            for (y in 1 until U) {
                // 過濾
                if (-1 == indexs[x] || -1 == indexs[y]) continue
                // 是否互補(bǔ)
                if (x and y == 0) return listOf(indexs[x], indexs[y]).sorted()
            }
        }
        return Collections.emptyList()
    }
}

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

• 時(shí)間復(fù)雜度：O(n + U^2) U = 32
• 空間復(fù)雜度：O(U)

往期回顧

• LeetCode 單周賽第 348 場(chǎng) · 數(shù)位 DP 模版學(xué)會(huì)了嗎？
• LeetCode 單周賽第 347 場(chǎng) · 二維空間上的 LIS 最長(zhǎng)遞增子序列問題
• 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 雙周賽 106（2023/06/10）兩道思維題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！