LeetCode 1618. 找出適應屏幕的最大字號(二分查找)

Michael阿明 2021-08-15 22:28:29 阅读数:514

本文一共[544]字,预计阅读时长:1分钟~
leetcode 找出 屏幕 最大 大字

文章目錄

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阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753164u.html