本文已收录到 AndroidFamily，技术和职场问题，请重视公众号 [彭旭锐] 加入知识星球提问。

  • 往期回忆：LeetCode 单周赛第 348 场 数位 DP 模版学会了吗？

双周赛 106 概览

T1. 判断一个数是否诱人（Easy）

  • 标签：计数

T2. 找到最长的半重复子字符串（Medium）

  • 标签：同向双指针

T3. 移动机器人（Medium）

  • 标签：脑筋急转弯、排序

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

  • 标签：散列表、贪心

LeetCode 双周赛 106（2023/06/10）两道思维题

T1. 判断一个数是否诱人（Easy）

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

题解一（计数）

  • 核算拼接后的数字，并查看数字 1 到 9 的数量是否为 1，能够用字符串比较来模拟计数；
  • 调查数字规律，合法 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("")
    }
}

复杂度剖析：

  • 时刻复杂度：O(UlgU) U 是单个数字的最大长度
  • 空间复杂度：O(U)

题解二（打表）

标题范围中只要 4 个诱人数。

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

复杂度剖析：

  • 时刻复杂度：O(1)
  • 空间复杂度：O(1)

T2. 找到最长的半重复子字符串（Medium）

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

题解（同向双指针）

保护滑动窗口，假如右指针与前一个方位相同，阐明添加一个相邻重复对。

当相邻重复对 repeatCnt 大于 1 时，此时需求缩短左指针，假如左指针与右边后一个方位相同，阐明减少一个相邻重复对（由于 repeatCnt 大于 1 时左指针不可能超过窗口，所以不需求查看左指针移动越界）。

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) {
            // 移动右指针
            if (j > 0 && s[j] == s[j - 1]) repeatCnt ++
            while (repeatCnt > 1) {
                // 移动左指针
                if (s[i] == s[i + 1]) repeatCnt --
                i++
            }
            // 记录成果
            ret = Math.max(ret, j - i + 1)
        }
        return ret
    }
}

复杂度剖析：

  • 时刻复杂度：O(n)
  • 空间复杂度：O(1)

T3. 移动机器人（Medium）

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

题解（模拟 + 排序）

注意到当发生磕碰而改动机器人方向时，咱们能够对调机器人身份，此时等价于没有发生磕碰且机器人按照正常方向行进，因此咱们能够直接忽视磕碰规矩，核算机器人的最终方位并核算两两间隔。

为了核算两两间隔，咱们先对一切点排序。由于两个机器人的间隔公式是 x – y，那么对于每个机器人 nums[i]，在间隔公式中它将作为 i 次 x 做加法，以及作为 (n -1 – i) 次 y 做解法，能够枚举每个机器人对间隔公式的贡献度而算出整体的两两间隔和。

class Solution {
    fun sumDistance(nums: IntArray, s: String, d: Int): Int {
        val n = nums.size
        val MOD = 1000000007
        // 移动（忽视磕碰）
        for (i in nums.indices) {
            nums[i] += if (s[i] == 'R') d else -d
        }
        // 排序
        nums.sort()
        // 核算两两间隔
        var ret = 0L
        for (i in nums.indices) {
            ret = (ret + (2L * i - n + 1) * nums[i]) % MOD
        }
        return ret.toInt()
    }
}

复杂度剖析：

  • 时刻复杂度：O(nlgn) 瓶颈在排序
  • 空间复杂度：O(lgn)

相似标题：

  • 1503.一切蚂蚁掉下来前的最终一刻

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

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

题解（散列 + 贪心）

容易想到，咱们需求选择出 1 相对稀少的那些行（但不一定是最稀少的行），而且重复选择完全相同的行不会对成果发生价值，所以咱们先对行去重。

由于标题最多只要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
                // 是否互补
                if (x and y == 0) return listOf(indexs[x], indexs[y]).sorted()
            }
        }
        return Collections.emptyList()
    }
}

复杂度剖析：

  • 时刻复杂度：O(n + U^2) U = 32
  • 空间复杂度：O(U)

往期回忆

  • LeetCode 单周赛第 348 场 数位 DP 模版学会了吗？
  • LeetCode 单周赛第 347 场 二维空间上的 LIS 最长递增子序列问题
  • LeetCode 双周赛第 104 场 流水的动态规划，铁打的结构化思考
  • LeetCode 双周赛第 103 场 区间求和的树状数组经典应用

LeetCode 双周赛 106（2023/06/10）两道思维题