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

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. 模糊坐标

思路：

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

不是‘0’也不是'0.'但以0开头的不合理
以‘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

巴特西