Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit249bf6b

Browse files
add 418
1 parentb2e057f commit249bf6b

File tree

3 files changed

+146
-0
lines changed

3 files changed

+146
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -160,6 +160,7 @@ Your ideas/fixes/algorithms are more than welcome!
160160
|421|[Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_421.java)| O(n) | O(1) | Medium | Bit Manipulation, Trie
161161
|420|[Strong Password Checker](https://leetcode.com/problems/strong-password-checker/)|[Solution](../master/src/main/java/com/fishercoder/solutions/StrongPasswordChecker.java)| ?| ?| Hard|
162162
|419|[Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_419.java) | O(m*n) |O(1) | Medium| DFS
163+
|418|[Sentence Screen Fitting](https://leetcode.com/problems/sentence-screen-fitting/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_418.java)| O(n)|O(1)| Medium|
163164
|417|[Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/)|[Solution](../master/src/main/java/com/fishercoder/solutions/PacificAtlanticWaterFlow.java) | O(m*n*Max(m,n)) |O(m*n) | Medium| DFS
164165
|416|[Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_416.java)| O(m*n)|O(m*n) | Medium | DP
165166
|415|[Add Strings](https://leetcode.com/problems/add-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_415.java)| O(n)|O(1)| Easy|
Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
packagecom.fishercoder.solutions;
2+
3+
/**
4+
* 418. Sentence Screen Fitting
5+
*
6+
* Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.
7+
8+
Note:
9+
10+
A word cannot be split into two lines.
11+
The order of words in the sentence must remain unchanged.
12+
Two consecutive words in a line must be separated by a single space.
13+
Total words in the sentence won't exceed 100.
14+
Length of each word is greater than 0 and won't exceed 10.
15+
1 ≤ rows, cols ≤ 20,000.
16+
17+
Example 1:
18+
19+
Input:
20+
rows = 2, cols = 8, sentence = ["hello", "world"]
21+
22+
Output:
23+
1
24+
25+
Explanation:
26+
hello---
27+
world---
28+
29+
The character '-' signifies an empty space on the screen.
30+
31+
Example 2:
32+
33+
Input:
34+
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]
35+
36+
Output:
37+
2
38+
39+
Explanation:
40+
a-bcd-
41+
e-a---
42+
bcd-e-
43+
44+
The character '-' signifies an empty space on the screen.
45+
46+
Example 3:
47+
48+
Input:
49+
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]
50+
51+
Output:
52+
1
53+
54+
Explanation:
55+
I-had
56+
apple
57+
pie-I
58+
had--
59+
60+
The character '-' signifies an empty space on the screen.
61+
62+
*/
63+
publicclass_418 {
64+
65+
/**credit: https://discuss.leetcode.com/topic/62455/21ms-18-lines-java-solution
66+
*
67+
1. String s = String.join(" ", sentence) + " " ;. This line gives us a formatted sentence to be put to our screen.
68+
2. start is the counter for how many valid characters from s have been put to our screen.
69+
3. if (s.charAt(start % l) == ' ') is the situation that we don't need an extra space for current row. The current row could be successfully fitted. So that we need to increase our counter by using start++.
70+
4. The else is the situation, which the next word can't fit to current row. So that we need to remove extra characters from next word.
71+
5. start / s.length() is (# of valid characters) / our formatted sentence.
72+
*/
73+
publicintwordsTyping(String[]sentence,introws,intcols) {
74+
Strings =String.join(" ",sentence) +" ";
75+
intstart =0,l =s.length();
76+
for (inti =0;i <rows;i++) {
77+
start +=cols;
78+
if (s.charAt(start %l) ==' ') {
79+
start++;
80+
}else {
81+
while (start >0 &&s.charAt((start-1) %l) !=' ') {
82+
start--;
83+
}
84+
}
85+
}
86+
returnstart /s.length();
87+
}
88+
89+
}
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._418;
4+
importorg.junit.BeforeClass;
5+
importorg.junit.Test;
6+
7+
importstaticorg.junit.Assert.assertEquals;
8+
9+
/**
10+
* Created by stevesun on 6/11/17.
11+
*/
12+
publicclass_418Test {
13+
privatestatic_418test;
14+
privatestaticString[]sentence;
15+
16+
@BeforeClass
17+
publicstaticvoidsetup(){
18+
test =new_418();
19+
}
20+
21+
@Test
22+
publicvoidtest1(){
23+
sentence =newString[]{"hello","world"};
24+
assertEquals(1,test.wordsTyping(sentence,2,8));
25+
}
26+
27+
@Test
28+
publicvoidtest2(){
29+
sentence =newString[]{"a","bcd","e"};
30+
assertEquals(2,test.wordsTyping(sentence,3,6));
31+
}
32+
33+
@Test
34+
publicvoidtest3(){
35+
sentence =newString[]{"I","had","apple","pie"};
36+
assertEquals(1,test.wordsTyping(sentence,4,5));
37+
}
38+
39+
@Test
40+
publicvoidtest4(){
41+
sentence =newString[]{"f","p","a"};
42+
assertEquals(10,test.wordsTyping(sentence,8,7));
43+
}
44+
45+
@Test
46+
publicvoidtest5(){
47+
sentence =newString[]{"hello","leetcode"};
48+
assertEquals(1,test.wordsTyping(sentence,1,20));
49+
}
50+
51+
@Test
52+
publicvoidtest6(){
53+
sentence =newString[]{"h"};
54+
assertEquals(4,test.wordsTyping(sentence,2,3));
55+
}
56+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp