Skip to content

Latest commit

 

History

History
230 lines (186 loc) · 6.96 KB

README.md

File metadata and controls

230 lines (186 loc) · 6.96 KB

1618. 找出适应屏幕的最大字号

English Version

题目描述

给定一个字符串 text。并能够在 宽为 w 高为 h 的屏幕上显示该文本。

字体数组中包含按升序排列的可用字号，您可以从该数组中选择任何字体大小。

您可以使用FontInfo接口来获取任何可用字体大小的任何字符的宽度和高度。

FontInfo接口定义如下：

interface FontInfo {
  // 返回 fontSize 大小的字符 ch 在屏幕上的宽度。
  // 每调用该函数复杂度为 O(1)
  public int getWidth(int fontSize, char ch);

  // 返回 fontSize 大小的任意字符在屏幕上的高度。
  // 每调用该函数复杂度为 O(1)
  public int getHeight(int fontSize);
}

一串字符的文本宽度应该是每一个字符在对应字号(fontSize)下返回的宽度getHeight(fontSize)的总和。

请注意：文本最多只能排放一排

如果使用相同的参数调用 getHeight 或 getWidth ，则可以保证 FontInfo 将返回相同的值。

同时，对于任何字体大小的 fontSize 和任何字符 ch ：

  • getHeight(fontSize) <= getHeight(fontSize+1)
  • getWidth(fontSize, ch) <= getWidth(fontSize+1, ch)

返回可用于在屏幕上显示文本的最大字体大小。如果文本不能以任何字体大小显示，则返回-1。

示例 1:

输入: text = "helloworld", w = 80, h = 20, fonts = [6,8,10,12,14,16,18,24,36]
输出: 6

Example 2:

输入: text = "leetcode", w = 1000, h = 50, fonts = [1,2,4]
输出: 4

Example 3:

输入: text = "easyquestion", w = 100, h = 100, fonts = [10,15,20,25]
输出: -1

 

注意:

  • 1 <= text.length <= 50000
  • text 只包含小写字母
  • 1 <= w <= 107
  • 1 <= h <= 104
  • 1 <= fonts.length <= 105
  • 1 <= fonts[i] <= 105
  • fonts 已经按升序排序，且不包含重复项。

解法

二分查找，见整数二分算法模板 2。

Python3

# """
# 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
#        """
class Solution:
    def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:
        def check(text, fontSize, w, h, fontInfo) -> bool:
            if fontInfo.getHeight(fontSize) > h:
                return False
            width = 0
            for ch in text:
                width += fontInfo.getWidth(fontSize, ch)
                if width > w:
                    return False
            return True

        left, right = 0, len(fonts) - 1
        while left < right:
            mid = (left + right + 1) >> 1
            fontSize = fonts[mid]
            if check(text, fontSize, w, h, fontInfo):
                left = mid
            else:
                right = mid - 1
        return fonts[left] if check(text, fonts[left], w, h, fontInfo) else -1

Java

/**
 * // This is the FontInfo's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface FontInfo {
 *     // Return the width of char ch when fontSize is used.
 *     public int getWidth(int fontSize, char ch) {}
 *     // Return Height of any char when fontSize is used.
 *     public int getHeight(int fontSize)
 * }
 */
class Solution {
    public int maxFont(String text, int w, int h, int[] fonts, FontInfo fontInfo) {
        int left = 0, right = fonts.length - 1;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            int fontSize = fonts[mid];
            if (check(text, fontSize, w, h, fontInfo)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
    }

    private boolean check(String s, int fontSize, int w, int h, FontInfo fontInfo) {
        if (fontInfo.getHeight(fontSize) > h) {
            return false;
        }
        int width = 0;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            width += fontInfo.getWidth(fontSize, ch);
            if (width > w) {
                return false;
            }
        }
        return true;
    }
}

C++

/**
 * // This is the FontInfo's API interface.
 * // You should not implement it, or speculate about its implementation
 * class FontInfo {
 *   public:
 *     // Return the width of char ch when fontSize is used.
 *     int getWidth(int fontSize, char ch);
 *     
 *     // Return Height of any char when fontSize is used.
 *     int getHeight(int fontSize)
 * };
 */
class Solution {
public:
    int maxFont(string text, int w, int h, vector<int>& fonts, FontInfo fontInfo) {
        int left = 0, right = fonts.size() - 1;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            int fontSize = fonts[mid];
            if (check(text, fontSize, w, h, fontInfo)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
    }

private:
    bool check(string s, int fontSize, int w, int h, FontInfo fontInfo) {
        if (fontInfo.getHeight(fontSize) > h) {
            return false;
        }
        int width = 0;
        for (auto ch : s) {
            width += fontInfo.getWidth(fontSize, ch);
            if (width > w) {
                return false;
            }
        }
        return true;
    }
};

...