亲宝软件园·资讯

展开

Leetcode题解 - 部分中等难度算法题解(56、957、825、781、1324、816)

但是我拒绝 人气:0
957. N 天后的牢房


思路:
模拟变换,当N天结合后返回 => 当N非常大的时候,超时 => 一般N很大的时候,这种题目必然存在循环,所以记录找过的状态,一旦出现已经访问过的状态可立即跳出循环。

class Solution:
    def prisonAfterNDays(self, cells, N: int):
        vis = []
        while 1:
            if not N:
                return cells
            if cells in vis:
                ind = vis.index(cells)
                break
            tcell = cells.copy()
            for i in range(len(cells)):
                if i == 0 or i == len(cells)-1:
                    tcell[i] = 0
                    continue
                if cells[i-1] == cells[i+1]:
                    tcell[i] = 1
                else:
                    tcell[i] = 0
            vis.append(cells)
            cells = tcell
            N -= 1
        vis = vis[ind:]
        return vis[N % len(vis)]

825. 适龄的朋友


思路:
最直观的就是两层循环暴力,意料之中的超时了。那么就改以人为单位交友,变为以组(年龄相同的为一组)为单位交友。

还需要注意的一点就是15岁以下的没朋友,不符合第一个条件!

from collections import Counter
class Solution:
    def numFriendRequests(self, ages) -> int:
        ages, res = sorted(Counter(ages).items(), key=lambda x: x[0]), 0
        for i in range(len(ages)):
            if ages[i][0] < 15:
                continue
            res += (ages[i][1] - 1) * ages[i][1]
            for j in range(i):
                if ages[j][0] <= (ages[i][0] * 0.5 + 7):
                    continue
                else:
                    res += ages[i][1] * ages[j][1]
        return res

781. 森林中的兔子



思路:
颜色相同的兔子如果说自己有i个伙伴,那么所有伙伴都出现,该颜色对应的数字最多出现 i+1次 => 通过频率来判断,那些是同样颜色的。

"""
判断某数字出现的频次,数字0特殊处理一下
数字i出现的频次小于等于i+1时,说明大家都是一个色。
大于i+1的时候,就说明还有别的颜色,看是i+1的几倍就 i+1 * ?
"""
import math
from collections import Counter
class Solution:
    def numRabbits(self, answers) -> int:
        ans, res = Counter(answers), 0
        for num, times in ans.items():
            if not num:
                res += times
            else:
                if times <= num + 1:
                    res += num + 1
                else:
                    t = math.ceil(times / (num + 1))
                    res += t * (num + 1)
        return res

1324. 竖直打印单词


思路:
补上空格,矩阵转置输出,末尾的空格需要去掉。

class Solution:
    def printVertically(self, s: str):
        s = s.split(" ")
        l = len(sorted(s, key=lambda x:-len(x))[0])
        for i in range(len(s)):
            s[i] = s[i] + (l - len(s[i])) * " "
        res = []
        for i in zip(*s):
            i = ("".join(list(i))).rstrip()
            res.append(i)
        return res

816. 模糊坐标


思路:
分割数组找到整数、小数部分。比较麻烦在于加上小数点后时候合理:

  1. 不是‘0’也不是'0.'但以0开头的不合理
  2. 以‘0’结尾的不合理
"""
先分割字符串,得到整数部分和小数部分,再分别为两部分加上小数点,同时判断加上小数点后是否为合理数字
"""
class Solution:
    def ambiguousCoordinates(self, S: str):
        def produce(string):
            res = []
            # 本身就是一个完整的数字
            if len(str(int(string))) == len(string):
                res = [string]
            # 如果全是零直接返回
            if set(string) == {'0'}:
                return res
            # 在不同的位置添加小数点
            for i in range(1,len(string)):
                t = string[:i]+"."+string[i:]
                # 不是'0'也不是'0.'开头的,以'0'开头的都要删掉
                if len(string[:i]) >= 2 and string[:i].startswith("0"):
                    continue
                # '0'结尾的也删掉
                if string[i:].endswith('0'):
                    continue
                res.append(t)
            return res
        S, res, r = S[1:-1], [], []
        # 分割字符串获取整数、小数部分
        for i in range(1, len(S)):
            res.append((S[:i], S[i:]))
        for x, y in res:
            px = produce(x)
            py = produce(y)
            for i in px:
                for j in py:
                    r.append("("+i+", "+j+")")
        return r

56. 合并区间


思路:
按照合并的要求来就vans了。先排序,保证遍历的时候后面的要么是头比前面大,要么是尾巴更长。记录当前拼接的头尾,如果遇到了头比当前拼接的尾巴还大,这两个区间不可能合并的,重新开始一次拼接,否则更新尾巴。

class Solution:
    def merge(self, intervals):
        res = []
        # 先排序
        intervals = sorted(intervals)
        # 记录拼接的首尾大小
        s, e = intervals[0][0], intervals[0][1]
        for x, y in intervals[1:]:
            # 你的头大于我的尾部,不可能拼接的。重新开始一次拼接
            if x > e:
                res.append([s, e])
                s, e = x, y
                continue
            # 可以拼接到一起,更新尾巴
            if y > e:
                e = y
        if [s, e] not in res:
            res.append([s, e])
        return res

加载全部内容

相关教程
猜你喜欢
用户评论