Skip to content

Commit bf92031

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1618
No.1618.Maximum Font to Fit a Sentence in a Screen
1 parent 45be9e2 commit bf92031

File tree

6 files changed

+228
-116
lines changed

6 files changed

+228
-116
lines changed

‎solution/1600-1699/1618.Maximum Font to Fit a Sentence in a Screen/README.md

Lines changed: 80 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -75,7 +75,13 @@
7575

7676
<!-- 这里可写通用的实现逻辑 -->
7777

78-
二分查找，见[整数二分算法模板 2](/basic/searching/BinarySearch/README.md)。
78+
**方法一：二分查找**
79+
80+
根据题目描述，字体数组按升序排列。因此，我们可以二分枚举字体大小 `fontSize`，找到最大的并且能够在屏幕上显示文本字体大小即可。
81+
82+
时间复杂度 $O(m\log n)$。其中 $m$, $n$ 为文本 `text` 的长度以及字体大小 `fonts` 个数。
83+
84+
关于二分查找，见[整数二分算法模板 2](/basic/searching/BinarySearch/README.md)。
7985

8086
<!-- tabs:start -->
8187

@@ -106,25 +112,20 @@ class Solution:
106112
def maxFont(
107113
self, text: str, w: int, h: int, fonts: List[int], fontInfo: 'FontInfo'
108114
) -> int:
109-
def check(text, fontSize, w, h, fontInfo) -> bool:
110-
if fontInfo.getHeight(fontSize) > h:
115+
def check(size):
116+
if fontInfo.getHeight(size) > h:
111117
return False
112-
width = 0
113-
for ch in text:
114-
width += fontInfo.getWidth(fontSize, ch)
115-
if width > w:
116-
return False
117-
return True
118+
return sum(fontInfo.getWidth(size, c) for c in text) <= w
118119

119120
left, right = 0, len(fonts) - 1
121+
ans = -1
120122
while left < right:
121123
mid = (left + right + 1) >> 1
122-
fontSize = fonts[mid]
123-
if check(text, fontSize, w, h, fontInfo):
124+
if check(fonts[mid]):
124125
left = mid
125126
else:
126127
right = mid - 1
127-
return fonts[left] if check(text, fonts[left], w, h, fontInfo) else -1
128+
return fonts[left] if check(fonts[left]) else -1
128129
```
129130

130131
### **Java**
@@ -147,8 +148,7 @@ class Solution {
147148
int left = 0, right = fonts.length - 1;
148149
while (left < right) {
149150
int mid = (left + right + 1) >> 1;
150-
int fontSize = fonts[mid];
151-
if (check(text, fontSize, w, h, fontInfo)) {
151+
if (check(text, fonts[mid], w, h, fontInfo)) {
152152
left = mid;
153153
} else {
154154
right = mid - 1;
@@ -157,19 +157,15 @@ class Solution {
157157
return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
158158
}
159159

160-
private boolean check(String s, int fontSize, int w, int h, FontInfo fontInfo) {
161-
if (fontInfo.getHeight(fontSize) > h) {
160+
private boolean check(String text, int size, int w, int h, FontInfo fontInfo) {
161+
if (fontInfo.getHeight(size) > h) {
162162
return false;
163163
}
164164
int width = 0;
165-
for (int i = 0; i < s.length(); ++i) {
166-
char ch = s.charAt(i);
167-
width += fontInfo.getWidth(fontSize, ch);
168-
if (width > w) {
169-
return false;
170-
}
165+
for (char c : text.toCharArray()) {
166+
width += fontInfo.getWidth(size, c);
171167
}
172-
return true;
168+
return width <= w;
173169
}
174170
}
175171
```
@@ -192,33 +188,80 @@ class Solution {
192188
class Solution {
193189
public:
194190
int maxFont(string text, int w, int h, vector<int>& fonts, FontInfo fontInfo) {
191+
auto check = [&](int size) {
192+
if (fontInfo.getHeight(size) > h) return false;
193+
int width = 0;
194+
for (char& c : text) {
195+
width += fontInfo.getWidth(size, c);
196+
}
197+
return width <= w;
198+
};
195199
int left = 0, right = fonts.size() - 1;
196200
while (left < right) {
197-
int mid = left + right + 1 >> 1;
198-
int fontSize = fonts[mid];
199-
if (check(text, fontSize, w, h, fontInfo)) {
201+
int mid = (left + right + 1) >> 1;
202+
if (check(fonts[mid])) {
200203
left = mid;
201204
} else {
202205
right = mid - 1;
203206
}
204207
}
205-
return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
208+
return check(fonts[left]) ? fonts[left] : -1;
206209
}
210+
};
211+
```
207212
208-
private:
209-
bool check(string s, int fontSize, int w, int h, FontInfo fontInfo) {
210-
if (fontInfo.getHeight(fontSize) > h) {
213+
### **JavaScript**
214+
215+
```js
216+
/**
217+
* // This is the FontInfo's API interface.
218+
* // You should not implement it, or speculate about its implementation
219+
* function FontInfo() {
220+
*
221+
* @param {number} fontSize
222+
* @param {char} ch
223+
* @return {number}
224+
* this.getWidth = function(fontSize, ch) {
225+
* ...
226+
* };
227+
*
228+
* @param {number} fontSize
229+
* @return {number}
230+
* this.getHeight = function(fontSize) {
231+
* ...
232+
* };
233+
* };
234+
*/
235+
/**
236+
* @param {string} text
237+
* @param {number} w
238+
* @param {number} h
239+
* @param {number[]} fonts
240+
* @param {FontInfo} fontInfo
241+
* @return {number}
242+
*/
243+
var maxFont = function (text, w, h, fonts, fontInfo) {
244+
const check = function (size) {
245+
if (fontInfo.getHeight(size) > h) {
211246
return false;
212247
}
213-
int width = 0;
214-
for (auto ch : s) {
215-
width += fontInfo.getWidth(fontSize, ch);
216-
if (width > w) {
217-
return false;
218-
}
248+
let width = 0;
249+
for (const c of text) {
250+
width += fontInfo.getWidth(size, c);
251+
}
252+
return width <= w;
253+
};
254+
let left = 0;
255+
let right = fonts.length - 1;
256+
while (left < right) {
257+
const mid = (left + right + 1) >> 1;
258+
if (check(fonts[mid])) {
259+
left = mid;
260+
} else {
261+
right = mid - 1;
219262
}
220-
return true;
221263
}
264+
return check(fonts[left]) ? fonts[left] : -1;
222265
};
223266
```
224267

‎solution/1600-1699/1618.Maximum Font to Fit a Sentence in a Screen/README_EN.md

Lines changed: 74 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -120,25 +120,20 @@ class Solution:
120120
def maxFont(
121121
self, text: str, w: int, h: int, fonts: List[int], fontInfo: 'FontInfo'
122122
) -> int:
123-
def check(text, fontSize, w, h, fontInfo) -> bool:
124-
if fontInfo.getHeight(fontSize) > h:
123+
def check(size):
124+
if fontInfo.getHeight(size) > h:
125125
return False
126-
width = 0
127-
for ch in text:
128-
width += fontInfo.getWidth(fontSize, ch)
129-
if width > w:
130-
return False
131-
return True
126+
return sum(fontInfo.getWidth(size, c) for c in text) <= w
132127

133128
left, right = 0, len(fonts) - 1
129+
ans = -1
134130
while left < right:
135131
mid = (left + right + 1) >> 1
136-
fontSize = fonts[mid]
137-
if check(text, fontSize, w, h, fontInfo):
132+
if check(fonts[mid]):
138133
left = mid
139134
else:
140135
right = mid - 1
141-
return fonts[left] if check(text, fonts[left], w, h, fontInfo) else -1
136+
return fonts[left] if check(fonts[left]) else -1
142137
```
143138

144139
### **Java**
@@ -159,8 +154,7 @@ class Solution {
159154
int left = 0, right = fonts.length - 1;
160155
while (left < right) {
161156
int mid = (left + right + 1) >> 1;
162-
int fontSize = fonts[mid];
163-
if (check(text, fontSize, w, h, fontInfo)) {
157+
if (check(text, fonts[mid], w, h, fontInfo)) {
164158
left = mid;
165159
} else {
166160
right = mid - 1;
@@ -169,19 +163,15 @@ class Solution {
169163
return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
170164
}
171165

172-
private boolean check(String s, int fontSize, int w, int h, FontInfo fontInfo) {
173-
if (fontInfo.getHeight(fontSize) > h) {
166+
private boolean check(String text, int size, int w, int h, FontInfo fontInfo) {
167+
if (fontInfo.getHeight(size) > h) {
174168
return false;
175169
}
176170
int width = 0;
177-
for (int i = 0; i < s.length(); ++i) {
178-
char ch = s.charAt(i);
179-
width += fontInfo.getWidth(fontSize, ch);
180-
if (width > w) {
181-
return false;
182-
}
171+
for (char c : text.toCharArray()) {
172+
width += fontInfo.getWidth(size, c);
183173
}
184-
return true;
174+
return width <= w;
185175
}
186176
}
187177
```
@@ -196,41 +186,88 @@ class Solution {
196186
* public:
197187
* // Return the width of char ch when fontSize is used.
198188
* int getWidth(int fontSize, char ch);
199-
*
189+
*
200190
* // Return Height of any char when fontSize is used.
201191
* int getHeight(int fontSize)
202192
* };
203193
*/
204194
class Solution {
205195
public:
206196
int maxFont(string text, int w, int h, vector<int>& fonts, FontInfo fontInfo) {
197+
auto check = [&](int size) {
198+
if (fontInfo.getHeight(size) > h) return false;
199+
int width = 0;
200+
for (char& c : text) {
201+
width += fontInfo.getWidth(size, c);
202+
}
203+
return width <= w;
204+
};
207205
int left = 0, right = fonts.size() - 1;
208206
while (left < right) {
209-
int mid = left + right + 1 >> 1;
210-
int fontSize = fonts[mid];
211-
if (check(text, fontSize, w, h, fontInfo)) {
207+
int mid = (left + right + 1) >> 1;
208+
if (check(fonts[mid])) {
212209
left = mid;
213210
} else {
214211
right = mid - 1;
215212
}
216213
}
217-
return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
214+
return check(fonts[left]) ? fonts[left] : -1;
218215
}
216+
};
217+
```
218+
219+
### **JavaScript**
219220
220-
private:
221-
bool check(string s, int fontSize, int w, int h, FontInfo fontInfo) {
222-
if (fontInfo.getHeight(fontSize) > h) {
221+
```js
222+
/**
223+
* // This is the FontInfo's API interface.
224+
* // You should not implement it, or speculate about its implementation
225+
* function FontInfo() {
226+
*
227+
* @param {number} fontSize
228+
* @param {char} ch
229+
* @return {number}
230+
* this.getWidth = function(fontSize, ch) {
231+
* ...
232+
* };
233+
*
234+
* @param {number} fontSize
235+
* @return {number}
236+
* this.getHeight = function(fontSize) {
237+
* ...
238+
* };
239+
* };
240+
*/
241+
/**
242+
* @param {string} text
243+
* @param {number} w
244+
* @param {number} h
245+
* @param {number[]} fonts
246+
* @param {FontInfo} fontInfo
247+
* @return {number}
248+
*/
249+
var maxFont = function (text, w, h, fonts, fontInfo) {
250+
const check = function (size) {
251+
if (fontInfo.getHeight(size) > h) {
223252
return false;
224253
}
225-
int width = 0;
226-
for (auto ch : s) {
227-
width += fontInfo.getWidth(fontSize, ch);
228-
if (width > w) {
229-
return false;
230-
}
254+
let width = 0;
255+
for (const c of text) {
256+
width += fontInfo.getWidth(size, c);
257+
}
258+
return width <= w;
259+
};
260+
let left = 0;
261+
let right = fonts.length - 1;
262+
while (left < right) {
263+
const mid = (left + right + 1) >> 1;
264+
if (check(fonts[mid])) {
265+
left = mid;
266+
} else {
267+
right = mid - 1;
231268
}
232-
return true;
233269
}
270+
return check(fonts[left]) ? fonts[left] : -1;
234271
};
235272
```
236273

‎solution/1600-1699/1618.Maximum Font to Fit a Sentence in a Screen/Solution.cpp

Lines changed: 12 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -13,31 +13,23 @@
1313
class Solution {
1414
public:
1515
int maxFont(string text, int w, int h, vector<int>& fonts, FontInfo fontInfo) {
16+
auto check = [&](int size) {
17+
if (fontInfo.getHeight(size) > h) return false;
18+
int width = 0;
19+
for (char& c : text) {
20+
width += fontInfo.getWidth(size, c);
21+
}
22+
return width <= w;
23+
};
1624
int left = 0, right = fonts.size() - 1;
1725
while (left < right) {
18-
int mid = left + right + 1 >> 1;
19-
int fontSize = fonts[mid];
20-
if (check(text, fontSize, w, h, fontInfo)) {
26+
int mid = (left + right + 1) >> 1;
27+
if (check(fonts[mid])) {
2128
left = mid;
2229
} else {
2330
right = mid - 1;
2431
}
2532
}
26-
return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
27-
}
28-
29-
private:
30-
bool check(string s, int fontSize, int w, int h, FontInfo fontInfo) {
31-
if (fontInfo.getHeight(fontSize) > h) {
32-
return false;
33-
}
34-
int width = 0;
35-
for (auto ch : s) {
36-
width += fontInfo.getWidth(fontSize, ch);
37-
if (width > w) {
38-
return false;
39-
}
40-
}
41-
return true;
33+
return check(fonts[left]) ? fonts[left] : -1;
4234
}
43-
};
35+
};

0 commit comments

Comments
 (0)