Skip to content

Commit 1c87e8e

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

File tree

7 files changed

+378
-4
lines changed

7 files changed

+378
-4
lines changed

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

Lines changed: 128 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -76,22 +76,149 @@
7676

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

79+
二分查找，见[整数二分算法模板 2](/basic/searching/BinarySearch/README.md)。
80+
7981
<!-- tabs:start -->
8082

8183
### **Python3**
8284

8385
<!-- 这里可写当前语言的特殊实现逻辑 -->
8486

8587
```python
86-
88+
# """
89+
# This is FontInfo's API interface.
90+
# You should not implement it, or speculate about its implementation
91+
# """
92+
#class FontInfo(object):
93+
# Return the width of char ch when fontSize is used.
94+
# def getWidth(self, fontSize, ch):
95+
# """
96+
# :type fontSize: int
97+
# :type ch: char
98+
# :rtype int
99+
# """
100+
#
101+
# def getHeight(self, fontSize):
102+
# """
103+
# :type fontSize: int
104+
# :rtype int
105+
# """
106+
class Solution:
107+
def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:
108+
def check(text, fontSize, w, h, fontInfo) -> bool:
109+
if fontInfo.getHeight(fontSize) > h:
110+
return False
111+
width = 0
112+
for ch in text:
113+
width += fontInfo.getWidth(fontSize, ch)
114+
if width > w:
115+
return False
116+
return True
117+
118+
left, right = 0, len(fonts) - 1
119+
while left < right:
120+
mid = (left + right + 1) >> 1
121+
fontSize = fonts[mid]
122+
if check(text, fontSize, w, h, fontInfo):
123+
left = mid
124+
else:
125+
right = mid - 1
126+
return fonts[left] if check(text, fonts[left], w, h, fontInfo) else -1
87127
```
88128

89129
### **Java**
90130

91131
<!-- 这里可写当前语言的特殊实现逻辑 -->
92132

93133
```java
134+
/**
135+
* // This is the FontInfo's API interface.
136+
* // You should not implement it, or speculate about its implementation
137+
* interface FontInfo {
138+
* // Return the width of char ch when fontSize is used.
139+
* public int getWidth(int fontSize, char ch) {}
140+
* // Return Height of any char when fontSize is used.
141+
* public int getHeight(int fontSize)
142+
* }
143+
*/
144+
class Solution {
145+
public int maxFont(String text, int w, int h, int[] fonts, FontInfo fontInfo) {
146+
int left = 0, right = fonts.length - 1;
147+
while (left < right) {
148+
int mid = (left + right + 1) >> 1;
149+
int fontSize = fonts[mid];
150+
if (check(text, fontSize, w, h, fontInfo)) {
151+
left = mid;
152+
} else {
153+
right = mid - 1;
154+
}
155+
}
156+
return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
157+
}
158+
159+
private boolean check(String s, int fontSize, int w, int h, FontInfo fontInfo) {
160+
if (fontInfo.getHeight(fontSize) > h) {
161+
return false;
162+
}
163+
int width = 0;
164+
for (int i = 0; i < s.length(); ++i) {
165+
char ch = s.charAt(i);
166+
width += fontInfo.getWidth(fontSize, ch);
167+
if (width > w) {
168+
return false;
169+
}
170+
}
171+
return true;
172+
}
173+
}
174+
```
94175

176+
### **C++**
177+
178+
```cpp
179+
/**
180+
* // This is the FontInfo's API interface.
181+
* // You should not implement it, or speculate about its implementation
182+
* class FontInfo {
183+
* public:
184+
* // Return the width of char ch when fontSize is used.
185+
* int getWidth(int fontSize, char ch);
186+
*
187+
* // Return Height of any char when fontSize is used.
188+
* int getHeight(int fontSize)
189+
* };
190+
*/
191+
class Solution {
192+
public:
193+
int maxFont(string text, int w, int h, vector<int>& fonts, FontInfo fontInfo) {
194+
int left = 0, right = fonts.size() - 1;
195+
while (left < right) {
196+
int mid = left + right + 1 >> 1;
197+
int fontSize = fonts[mid];
198+
if (check(text, fontSize, w, h, fontInfo)) {
199+
left = mid;
200+
} else {
201+
right = mid - 1;
202+
}
203+
}
204+
return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
205+
}
206+
207+
private:
208+
bool check(string s, int fontSize, int w, int h, FontInfo fontInfo) {
209+
if (fontInfo.getHeight(fontSize) > h) {
210+
return false;
211+
}
212+
int width = 0;
213+
for (auto ch : s) {
214+
width += fontInfo.getWidth(fontSize, ch);
215+
if (width > w) {
216+
return false;
217+
}
218+
}
219+
return true;
220+
}
221+
};
95222
```
96223
97224
### **...**

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

Lines changed: 126 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -128,13 +128,138 @@ interface FontInfo {
128128
### **Python3**
129129

130130
```python
131-
131+
# """
132+
# This is FontInfo's API interface.
133+
# You should not implement it, or speculate about its implementation
134+
# """
135+
#class FontInfo(object):
136+
# Return the width of char ch when fontSize is used.
137+
# def getWidth(self, fontSize, ch):
138+
# """
139+
# :type fontSize: int
140+
# :type ch: char
141+
# :rtype int
142+
# """
143+
#
144+
# def getHeight(self, fontSize):
145+
# """
146+
# :type fontSize: int
147+
# :rtype int
148+
# """
149+
class Solution:
150+
def maxFont(self, text: str, w: int, h: int, fonts: List[int], fontInfo : 'FontInfo') -> int:
151+
def check(text, fontSize, w, h, fontInfo) -> bool:
152+
if fontInfo.getHeight(fontSize) > h:
153+
return False
154+
width = 0
155+
for ch in text:
156+
width += fontInfo.getWidth(fontSize, ch)
157+
if width > w:
158+
return False
159+
return True
160+
161+
left, right = 0, len(fonts) - 1
162+
while left < right:
163+
mid = (left + right + 1) >> 1
164+
fontSize = fonts[mid]
165+
if check(text, fontSize, w, h, fontInfo):
166+
left = mid
167+
else:
168+
right = mid - 1
169+
return fonts[left] if check(text, fonts[left], w, h, fontInfo) else -1
132170
```
133171

134172
### **Java**
135173

136174
```java
175+
/**
176+
* // This is the FontInfo's API interface.
177+
* // You should not implement it, or speculate about its implementation
178+
* interface FontInfo {
179+
* // Return the width of char ch when fontSize is used.
180+
* public int getWidth(int fontSize, char ch) {}
181+
* // Return Height of any char when fontSize is used.
182+
* public int getHeight(int fontSize)
183+
* }
184+
*/
185+
class Solution {
186+
public int maxFont(String text, int w, int h, int[] fonts, FontInfo fontInfo) {
187+
int left = 0, right = fonts.length - 1;
188+
while (left < right) {
189+
int mid = (left + right + 1) >> 1;
190+
int fontSize = fonts[mid];
191+
if (check(text, fontSize, w, h, fontInfo)) {
192+
left = mid;
193+
} else {
194+
right = mid - 1;
195+
}
196+
}
197+
return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
198+
}
199+
200+
private boolean check(String s, int fontSize, int w, int h, FontInfo fontInfo) {
201+
if (fontInfo.getHeight(fontSize) > h) {
202+
return false;
203+
}
204+
int width = 0;
205+
for (int i = 0; i < s.length(); ++i) {
206+
char ch = s.charAt(i);
207+
width += fontInfo.getWidth(fontSize, ch);
208+
if (width > w) {
209+
return false;
210+
}
211+
}
212+
return true;
213+
}
214+
}
215+
```
137216

217+
### **C++**
218+
219+
```cpp
220+
/**
221+
* // This is the FontInfo's API interface.
222+
* // You should not implement it, or speculate about its implementation
223+
* class FontInfo {
224+
* public:
225+
* // Return the width of char ch when fontSize is used.
226+
* int getWidth(int fontSize, char ch);
227+
*
228+
* // Return Height of any char when fontSize is used.
229+
* int getHeight(int fontSize)
230+
* };
231+
*/
232+
class Solution {
233+
public:
234+
int maxFont(string text, int w, int h, vector<int>& fonts, FontInfo fontInfo) {
235+
int left = 0, right = fonts.size() - 1;
236+
while (left < right) {
237+
int mid = left + right + 1 >> 1;
238+
int fontSize = fonts[mid];
239+
if (check(text, fontSize, w, h, fontInfo)) {
240+
left = mid;
241+
} else {
242+
right = mid - 1;
243+
}
244+
}
245+
return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
246+
}
247+
248+
private:
249+
bool check(string s, int fontSize, int w, int h, FontInfo fontInfo) {
250+
if (fontInfo.getHeight(fontSize) > h) {
251+
return false;
252+
}
253+
int width = 0;
254+
for (auto ch : s) {
255+
width += fontInfo.getWidth(fontSize, ch);
256+
if (width > w) {
257+
return false;
258+
}
259+
}
260+
return true;
261+
}
262+
};
138263
```
139264
140265
### **...**

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

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/**
2+
* // This is the FontInfo's API interface.
3+
* // You should not implement it, or speculate about its implementation
4+
* class FontInfo {
5+
* public:
6+
* // Return the width of char ch when fontSize is used.
7+
* int getWidth(int fontSize, char ch);
8+
*
9+
* // Return Height of any char when fontSize is used.
10+
* int getHeight(int fontSize)
11+
* };
12+
*/
13+
class Solution {
14+
public:
15+
int maxFont(string text, int w, int h, vector<int>& fonts, FontInfo fontInfo) {
16+
int left = 0, right = fonts.size() - 1;
17+
while (left < right) {
18+
int mid = left + right + 1 >> 1;
19+
int fontSize = fonts[mid];
20+
if (check(text, fontSize, w, h, fontInfo)) {
21+
left = mid;
22+
} else {
23+
right = mid - 1;
24+
}
25+
}
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;
42+
}
43+
};

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/**
2+
* // This is the FontInfo's API interface.
3+
* // You should not implement it, or speculate about its implementation
4+
* interface FontInfo {
5+
* // Return the width of char ch when fontSize is used.
6+
* public int getWidth(int fontSize, char ch) {}
7+
* // Return Height of any char when fontSize is used.
8+
* public int getHeight(int fontSize)
9+
* }
10+
*/
11+
class Solution {
12+
public int maxFont(String text, int w, int h, int[] fonts, FontInfo fontInfo) {
13+
int left = 0, right = fonts.length - 1;
14+
while (left < right) {
15+
int mid = (left + right + 1) >> 1;
16+
int fontSize = fonts[mid];
17+
if (check(text, fontSize, w, h, fontInfo)) {
18+
left = mid;
19+
} else {
20+
right = mid - 1;
21+
}
22+
}
23+
return check(text, fonts[left], w, h, fontInfo) ? fonts[left] : -1;
24+
}
25+
26+
private boolean check(String s, int fontSize, int w, int h, FontInfo fontInfo) {
27+
if (fontInfo.getHeight(fontSize) > h) {
28+
return false;
29+
}
30+
int width = 0;
31+
for (int i = 0; i < s.length(); ++i) {
32+
char ch = s.charAt(i);
33+
width += fontInfo.getWidth(fontSize, ch);
34+
if (width > w) {
35+
return false;
36+
}
37+
}
38+
return true;
39+
}
40+
}

0 commit comments

Comments
 (0)