LeetCode中，python一行代码能干啥？

luanhz

发布于 2020-04-07 15:22:36

7970

发布于 2020-04-07 15:22:36

文章被收录于专栏：小数志

导读

都说python语言简洁、集成高效，一行代码往往能实现很多复杂的操作，比如两变量交换、心形输出、打印乘法口诀等等。但这些总归还是不太实用。那么我们换做在LeetCode中，看看用python一行代码都能解决什么问题。

注：以下题目均来自LeetCode。

Lee‍tCod‍e789# 逃脱阻碍者

‍‍

你在进行一个简化版的吃豆人游戏。你从 (0, 0) 点开始出发，你的目的地是 (target[0], target[1]) 。地图上有一些阻碍者，第 i 个阻碍者从 (ghosts[i][0], ghosts[i][1]) 出发。每一回合，你和阻碍者们*可以*同时向东，西，南，北四个方向移动，每次可以移动到距离原位置1个单位的新位置。如果你可以在任何阻碍者抓住你之前到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者同时到达了一个位置（包括目的地）都不算是逃脱成功。当且仅当你有可能成功逃脱时，输出 True。来源：力扣（LeetCode）789#逃脱阻碍者

题目理解不难，实际上就是判断游戏者是否比所有阻碍者都更接近目的地，当然是在曼哈顿距离下的接近。所以程序实现的核心即是判断一个值比多个值都更小。想到all函数的用法。

class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        return all([abs(target[0])+abs(target[1]) < abs(ghost[0]-target[0])+abs(ghost[1]-target[1]) for ghost in ghosts])

关键点：

曼哈顿距离求解
列表推导式求解多个判断结果
all函数对多个逻辑结果判断

LeetCode1347# 制造字母异位词

给你两个长度相等的字符串 s 和 t。每一个步骤中，你可以选择将 t 中的任一字符替换为另一个字符。返回使 t 成为 s 的字母异位词的最小步骤数。字母异位词指字母相同，但排列不同的字符串。示例 1：输出：s = "bab", t = "aba" 输出：1 提示：用 'b' 替换 t 中的第一个 'a'，t = "bba" 是 s 的一个字母异位词。来源：力扣（LeetCode）1347#制造字母异位词的最小步骤数

构造字母异位词，实际上就相当于以字符串s为基础，判断t中有几个和其不重叠的字符个数，考虑用python自带库collections中的计数器Counter实现。

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        return sum((collections.Counter(s) - collections.Counter(t)).values())

关键点：

Counter计数器可以实现字符计数功能
Counter类减法中，以前者为基数，且仅保留正数部分（即前面没有的而后面独有的，减法不保留）
sum求和计数器之差

LeetCode48# 旋转图像

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。示例 1: 给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], 原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ] 来源：力扣（LeetCode）48#旋转图像

图像的旋转相当于是对矩阵先转置再左右翻转，而实现python中转置则必然是用ZIP函数，左右翻转即是对列表逆序。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix[:] = [lyst[::-1] for lyst in zip(*matrix)]

关键点：

zip函数对嵌套列表实现"转置"
列表逆序操作
嵌套列表的inplace需要用matrix[:]

LeetCode面试题50# 只出现1次字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。示例: s = "abaccdeff" 返回 "b" s = "" 返回 " " 来源：力扣（LeetCode）面试题50. 第一个只出现一次的字符

涉及到出现次数，想到用Counter；要求找出第一个出现，而Counter刚好保留出场顺序，再加上必要的条件特判即可。

class Solution:
    def firstUniqChar(self, s: str) -> str:
        return ([k for k, v in collections.Counter(s).items() if v==1]+[' '])[0]

关键点：

Counter实现计数，并保留字符先后顺序
列表推导式筛选仅出现1次字符
加一个空格字符列表避免结果为空
输出第一个结果

LeetCode面试题58# 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。示例 1：输入: s = "abcdefg", k = 2 输出: "cdefgab" 来源：力扣（LeetCode）面试题58 - II. 左旋转字符串

提到旋转，可以想到用collections模块中deque的rotate接口（参考Python内置容器），但那个是inplace操作。直接对原字符串拼接，再从旋转后目标位置截取相应长度。

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return (s+s)[n:n+len(s)]

关键点：

字符串拼接实现扩展
左旋n个相当于起始索引右移到n

LeetCode914# 卡牌分组

给定一副牌，每张牌上都写着一个整数。此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：每组都有 X 张牌。组内所有的牌上都写着相同的整数。仅当你可选的 X >= 2 时返回 true。示例 1：输入：[1,2,3,4,4,3,2,1] 输出：true 解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4] 来源：力扣（LeetCode）914. 卡牌分组

本题还是比较难想的，需要数学知识作为支撑。因为要求相同的数字分为一组而且还要统计不同计数间能否存在共同的分组大小，用counter；目标是求可能分组大小越大越好，实际上是要找最大公约数；有N个数字的计数那么就是N个计数的最大公约数。

class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        import functools
        return functools.reduce(math.gcd, collections.Counter(deck).values()) > 1

关键点：