Skip to content

Commit 007e5a1

Browse files
yiakwyyiakwy
committed
New Problem Solution "Sentence Screen Fitting"
1 parent ad9d290 commit 007e5a1

4 files changed

Lines changed: 202 additions & 0 deletions

File tree

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ LeetCode
99
| # | Title | Solution | Difficulty |
1010
|---| ----- | -------- | ---------- |
1111
|477|[Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/) | [C++](./algorithms/cpp/totalHammingDistance/totalHammingDistance.cpp)|Medium|
12+
|418|[SentenceScreenFitting](https://leetcode.com/problems/sentence-screen-fitting/) | [C++](./algorithms/cpp/sentenceScreenFitting/OJ#418.cpp)|Easy|
1213
|415|[Add Strings](https://leetcode.com/problems/add-strings/) | [C++](./algorithms/cpp/addStrings/AddStrings.cpp)|Easy|
1314
|414|[Third Maximum Number](https://leetcode.com/problems/third-maximum-number/) | [C++](./algorithms/cpp/thirdMaximumNumber/ThirdMaximumNumber.cpp)|Easy|
1415
|413|[Arithmetic Slices](https://leetcode.com/problems/arithmetic-slices/) | [C++](./algorithms/cpp/arithmeticSlices/ArithmeticSlices.cpp)|Medium|

‎algorithms/cpp/sentenceScreenFitting/OJ#418.cpp‎

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
//
2+
// OJ#418.cpp
3+
// LeeteCodeOJ#418
4+
//
5+
// Created by Wang Yi on 25/10/16.
6+
// Copyright (c) 2016 Wang Yi. All rights reserved.
7+
//
8+
9+
#include "OJ#418.h"
10+
#include <string.h>
11+
#include <iomanip>
12+
#include <iostream>
13+
#define FOR(START, END) for((START)=0;(START)<(END);(START)+=1) {
14+
#define END ;}
15+
#define N 100
16+
17+
// first brute force solution
18+
int SentenceScreenFitting(char stc[][M], int row, int col, size_t l)
19+
{
20+
int i, j, t, s, k=0, ret=0;
21+
int len[N] = {0};
22+
FOR(i, l) len[i] = (int)strlen(stc[i]) END
23+
24+
FOR(i, row)
25+
j = col;
26+
t = k;
27+
while (j - len[k] >= 0) {
28+
j -= len[k] + 1;
29+
if (k+1 > l-1){
30+
FOR(s, k-t) std::cout << stc[t+s] << ' ' END;
31+
std::cout << stc[t+s];
32+
if (j - len[0] >= 0)
33+
std::cout << ' ';
34+
k = 0;
35+
t = 0;
36+
ret++;
37+
} else{
38+
k++;
39+
}
40+
}
41+
FOR(s, k-t-1) std::cout << stc[t+s] << ' ' END;
42+
if (k-t > 0)
43+
std::cout << stc[t+s];
44+
45+
std::cout << std::setfill ('-') << std::setw(j == col ? col:j+1) << "" << std::endl;
46+
END
47+
48+
return ret;
49+
}
50+
51+
/*
52+
int Solution::wordsTyping(vector<string>& sentence, int rows, int cols)
53+
{
54+
int i, j, t, s, k=0, ret=0, l=(int)sentence.size();
55+
int len[N] = {0};
56+
FOR(i, l) len[i] = (int)sentence[i].size() END
57+
58+
FOR(i, rows)
59+
j = cols;
60+
t = k;
61+
while (j - len[k] >= 0) {
62+
j -= len[k] + 1;
63+
if (k+1 > l-1){
64+
// FOR(s, k-t) std::cout << sentence[t+s] << ' ' END;
65+
// std::cout << sentence[t+s];
66+
// if (j - len[0] >= 0)
67+
// std::cout << ' ';
68+
k = 0;
69+
t = 0;
70+
ret++;
71+
} else{
72+
k++;
73+
}
74+
}
75+
// FOR(s, k-t-1) std::cout << sentence[t+s] << ' ' END;
76+
// if (k-t > 0)
77+
// std::cout << sentence[t+s];
78+
//
79+
// std::cout << std::setfill ('-') << std::setw(j == cols ? cols:j+1) << "" << std::endl;
80+
END
81+
82+
return ret;
83+
}
84+
*/
85+
86+
// second boosting
87+
int Solution::wordsTyping(vector<string>& sentence, int rows, int cols)
88+
{
89+
int i, j, k=0, ret=0, l=(int)sentence.size();
90+
// int t, s;
91+
int jump = 0;
92+
int len[N] = {0};
93+
FOR(i, l) len[i] = (int)sentence[i].size();jump += len[i] END
94+
jump += l;
95+
96+
FOR(i, rows)
97+
j = cols;
98+
// t = k;
99+
100+
if (k == 0){
101+
ret += j / jump;
102+
j = j % jump;
103+
}
104+
105+
while (j - len[k] >= 0) {
106+
j -= len[k] + 1;
107+
if (k+1 > l-1){
108+
// FOR(s, k-t) std::cout << sentence[t+s] << ' ' END;
109+
// std::cout << sentence[t+s];
110+
// if (j - len[0] >= 0)
111+
// std::cout << ' ';
112+
k = 0;
113+
// t = 0;
114+
ret += j / jump + 1;
115+
j = j % jump;
116+
} else {
117+
k++;
118+
}
119+
}
120+
// FOR(s, k-t-1) std::cout << sentence[t+s] << ' ' END;
121+
// if (k-t > 0)
122+
// std::cout << sentence[t+s];
123+
//
124+
// std::cout << std::setfill ('-') << std::setw(j == cols ? cols:j+1) << "" << std::endl;
125+
END
126+
127+
return ret;
128+
}

‎algorithms/cpp/sentenceScreenFitting/OJ#418.h‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
//
2+
// OJ#418.h
3+
// LeeteCodeOJ#418
4+
//
5+
// Created by Wang Yi on 25/10/16.
6+
// Copyright (c) 2016 Wang Yi. All rights reserved.
7+
//
8+
9+
#ifndef __LeeteCodeOJ_418__OJ_418__
10+
#define __LeeteCodeOJ_418__OJ_418__
11+
12+
#define M 10
13+
14+
#include <stdio.h>
15+
#include <string>
16+
#include <vector>
17+
18+
using std::vector;
19+
using std::string;
20+
21+
int SentenceScreenFitting(char stc[][M], int row, int col, size_t l);
22+
23+
class Solution {
24+
public:
25+
int wordsTyping(vector<string>& sentence, int rows, int cols);
26+
};
27+
28+
#endif /* defined(__LeeteCodeOJ_418__OJ_418__) */

‎algorithms/cpp/sentenceScreenFitting/main.cpp‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
//
2+
// main.cpp
3+
// LeeteCodeOJ#418
4+
//
5+
// Created by Wang Yi on 25/10/16.
6+
// Copyright (c) 2016 Wang Yi. All rights reserved.
7+
//
8+
9+
#include <iostream>
10+
#include <string>
11+
#include <string.h>
12+
#include <sstream>
13+
#include <vector>
14+
#include "OJ#418.h"
15+
#define N 100
16+
#define M 10
17+
18+
using std::vector;
19+
20+
int main(int argc, const char * argv[]) {
21+
int rows, cols, ret;
22+
// int i=0;
23+
// char stc[N][M];
24+
vector<string> sentence;
25+
std::string word;
26+
std::string line;
27+
std::stringstream numbers, split;
28+
29+
std::getline(std::cin, line);
30+
numbers << line;
31+
numbers >> rows >> cols;
32+
std::getline(std::cin, line);
33+
split << line;
34+
35+
while (split >> word){
36+
sentence.push_back(word);
37+
// strcpy(stc[i++], word.c_str());
38+
}
39+
40+
Solution solution;
41+
ret = solution.wordsTyping(sentence, rows, cols);
42+
// ret = SentenceScreenFitting(stc, rows, cols, i);
43+
std::cout << ret << std::endl;
44+
return 0;
45+
}

0 commit comments

Comments
 (0)