LeetCode 1618. 找出适应屏幕的最大字号（二分查找）

Michael阿明

发布于 2021-09-06 11:36:32

3670

发布于 2021-09-06 11:36:32

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

给定一个字符串 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 <= 10^7
1 <= h <= 10^4
1 <= fonts.length <= 10^5
1 <= fonts[i] <= 10^5
fonts 已经按升序排序，且不包含重复项。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-font-to-fit-a-sentence-in-a-screen 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

根据题目的条件，有序，可以使用二分查找，先找出满足高度的最大字符
再找出宽度也满足的最大字体

/**
 * // 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 {
    vector<long long> ct;
public:
    int maxFont(string text, int w, int h, vector<int>& fonts, FontInfo fontInfo) {
        int n = fonts.size(), m = text.size();
        int l = 0, r = n-1, mid, rm = -1, ans = -1;
        ct.resize(26);
        for(auto c : text)
            ct[c-'a']++;
        while(l <= r)
        {
            mid = (l+r)>>1;
            if(fontInfo.getHeight(fonts[mid]) > h)
                r = mid-1;
            else
            {
                rm = mid;
                l = mid+1;
            }
        }
        if(rm == -1) return -1;//高度容不下
        l = 0, r = rm;
        while(l <= r)
        {
            mid = (l+r)>>1;
            if(!ok_width(fontInfo,fonts[mid],w))
                r = mid-1;
            else
            {
                ans = mid;
                l = mid+1;
            }
        }
        return ans==-1 ? -1 : fonts[ans];
    }
    bool ok_width(FontInfo& fontInfo, int fsize, int w)
    {
        long long tot = 0;
        for(int i = 0; i < 26; ++i)
        {
            tot += fontInfo.getWidth(fsize, 'a'+i)*ct[i];
            if(tot > w)
                return false;
        }
        return true;
    }
};

52 ms 14.1 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/08/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https