难度: Medium
Submission
运行时间: 412 ms
内存: 27.8 MB
# """
# This is FontInfo's API interface.
# You should not implement it, or speculate about its implementation
# """
#class FontInfo(object):
# Return the width of char ch when fontSize is used.
# def getWidth(self, fontSize, ch):
# """
# :type fontSize: int
# :type ch: char
# :rtype int
# """
#
# def getHeight(self, fontSize):
# """
# :type fontSize: int
# :rtype int
# """
from collections import Counter
class Solution:
def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:
@lru_cache(None)
def check(x):
f = fonts[x]
if fontInfo.getHeight(f) > h:
return False
width = 0
for ch in cnt:
width += cnt[ch]*fontInfo.getWidth(f, ch)
if width > w:
return False
return True
cnt = Counter(text)
m = len(fonts)
i = 0
j = m - 1
while i < j - 1:
mid = i + (j - i) // 2
if check(mid):
i = mid
else:
j = mid
if check(j):
return fonts[j]
if check(i):
return fonts[i]
return -1
Explain
该题解利用二分查找来解决找出适应屏幕的最大字号问题。首先，使用一个辅助函数 `check(x)` 来判断给定字号是否能使所有文字适应屏幕宽度和高度。如果当前字号的高度超过屏幕高度或者文字总宽度超过屏幕宽度，则该字号不合适。通过使用二分查找，我们可以有效地找到最大合适的字号。检查函数被缓存，以优化重复计算。
时间复杂度: O(n * log m)
空间复杂度: O(u + m)
# 使用 FontInfo 的 API 接口，不实现具体的函数
# class FontInfo(object):
# def getWidth(self, fontSize, ch):
# def getHeight(self, fontSize):
from collections import Counter
from functools import lru_cache
class Solution:
def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:
@lru_cache(None)
def check(x):
f = fonts[x]
if fontInfo.getHeight(f) > h:
return False # 字号高度超过屏幕
width = 0
for ch in cnt:
width += cnt[ch]*fontInfo.getWidth(f, ch)
if width > w:
return False # 文字总宽度超过屏幕宽度
return True
cnt = Counter(text) # 统计每个字符的出现次数
m = len(fonts)
i = 0
j = m - 1
while i < j - 1:
mid = i + (j - i) // 2
if check(mid):
i = mid
else:
j = mid
if check(j):
return fonts[j]
if check(i):
return fonts[i]
return -1 # 如果没有合适的字号，返回 -1
Explore
选择`i + (j - i) // 2`作为计算中点的方式是为了防止`i`和`j`的值非常大时，直接相加导致整数溢出。虽然在Python中整数类型可以自动处理大数，但在其他编程语言如Java或C++中，整数类型有固定的大小限制，直接相加可能会超出该类型的最大值。因此，`i + (j - i) // 2`是一种更安全的方法，适用于多种编程环境。
在本题中，使用`i < j - 1`作为循环条件是为了确保循环退出时，`i`和`j`之间最多只有一个元素，这样可以在循环外部对这两个元素进行额外的检查，以确定哪个字号确实适合。这与常见的`i <= j`条件不同，后者通常会在找到目标或条件不满足时直接结束循环。使用`i < j - 1`能更精确地控制循环的结束条件，特别是在需要最后进一步判断的场景中非常有用。
在二分查找结束后，`i`和`j`的位置可能非常接近但不一定精确指向满足条件的最大字号。因此，需要分别检查`i`和`j`的位置以确定哪个字号实际上可以适应屏幕。这种方法确保了即使在循环条件使得`i`和`j`相邻时，我们也能通过额外检查找到确切的、最大的适应字号。
在Python中，整数类型是动态的，可以自动处理较大的数值而不会发生溢出。这意味着即使字符宽度累计的值很大，Python仍然可以正确处理。在设计算法时，不需要特别考虑整数溢出的问题，除非在使用固定整数大小的编程语言。在那种情况下，可能需要引入额外的逻辑来检测和处理潜在的溢出情况。