You are moderating a newspaper page, and you have to align the text on the page properly. The text is provided to you in the following format:
paragraphsis an array of paragraphs, where each paragraph is represented as an array of words.alignsis an array representing the alignment of each paragraph fromparagraphs— each element is either"LEFT"or"RIGHT".widthrepresents the maximum number of characters each line of the output can include.
For each paragraph, include all the words paragraphs[i][j], in order, separated by spaces:
- Include as many words as possible per page line (the length of the line must be less than or equal to
width), and put the next word on a new line if it would exceed this limit. - In the case of excess whitespace, words from
paragraphs[i]should be aligned according toaligns[i]. Ifaligns[i] = "LEFT", the line should have no leading spaces. - Include a border of
'*'characters around all the edges of the result.
解法
每个段落贪心装行：能装就继续，否则换行；按对齐填充后用 * 边框包裹。复杂度 O(total characters)。
def solution(paragraphs, aligns, width):
lines = []
for words, align in zip(paragraphs, aligns):
cur = []
cur_len = 0
for w in words:
extra = 1 if cur else 0
if cur_len + extra + len(w) <= width:
cur.append(w); cur_len += extra + len(w)
else:
lines.append((cur, align))
cur = [w]; cur_len = len(w)
if cur: lines.append((cur, align))
out = []
border = '*' * (width + 2)
out.append(border)
for words, align in lines:
line = ' '.join(words)
pad = width - len(line)
if align == "LEFT":
line = line + ' ' * pad
else:
line = ' ' * pad + line
out.append('*' + line + '*')
out.append(border)
return outclass Solution {
public List<String> newspaperLayout(String[][] paras, String[] aligns, int W) {
List<Object[]> lines = new ArrayList<>();
for (int p = 0; p < paras.length; p++) {
List<String> cur = new ArrayList<>(); int len = 0;
for (String w : paras[p]) {
int add = (cur.isEmpty() ? 0 : 1) + w.length();
if (len + add <= W) { cur.add(w); len += add; }
else { lines.add(new Object[]{cur, aligns[p]}); cur = new ArrayList<>(); cur.add(w); len = w.length(); }
}
if (!cur.isEmpty()) lines.add(new Object[]{cur, aligns[p]});
}
List<String> out = new ArrayList<>();
String border = "*".repeat(W + 2);
out.add(border);
for (Object[] ln : lines) {
String s = String.join(" ", (List<String>) ln[0]);
int pad = W - s.length();
s = ln[1].equals("LEFT") ? s + " ".repeat(pad) : " ".repeat(pad) + s;
out.add("*" + s + "*");
}
out.add(border);
return out;
}
}vector<string> newspaperLayout(vector<vector<string>>& paras, vector<string>& aligns, int W) {
vector<pair<vector<string>, string>> lines;
for (int p = 0; p < (int)paras.size(); ++p) {
vector<string> cur; int len = 0;
for (auto& w : paras[p]) {
int add = (cur.empty() ? 0 : 1) + (int)w.size();
if (len + add <= W) { cur.push_back(w); len += add; }
else { lines.push_back({cur, aligns[p]}); cur = {w}; len = w.size(); }
}
if (!cur.empty()) lines.push_back({cur, aligns[p]});
}
vector<string> out;
string border(W + 2, '*');
out.push_back(border);
for (auto& [ws, al] : lines) {
string s;
for (int i = 0; i < (int)ws.size(); ++i) { if (i) s += ' '; s += ws[i]; }
int pad = W - s.size();
s = (al == "LEFT") ? s + string(pad, ' ') : string(pad, ' ') + s;
out.push_back("*" + s + "*");
}
out.push_back(border);
return out;
}On the planet Octavia, astronomers track time using 8 distinct lunar phases instead of weekdays: NewMoon, Crescent, Quarter, Gibbous, Full, Waning, Eclipse, and Twilight. These phases repeat cyclically.
The Octavian year is divided into 12 seasons (January to December with Earth-month lengths), and each date has a corresponding lunar phase. Given a specific date (a season and day number) and the lunar phase with which the year began, determine the lunar phase for that date.
Notes:
- The number of days in each season in a non-leap year, in order: January: 31, February: 28, March: 31, April: 30, May: 31, June: 30, July: 31, August: 31, September: 30, October: 31, November: 30, December: 31.
- The lunar phases in the Octavian calendar are, in order:
NewMoon, Crescent, Quarter, Gibbous, Full, Waning, Eclipse, Twilight.
解法
自 1 月 1 日起的总天数 = season 前所有整月天数 + dayCount - 1。相位下标 = (start + total) mod 8。复杂度 O(1)。
def solution(season, dayCount, initialPhase):
phases = ["NewMoon", "Crescent", "Quarter", "Gibbous", "Full", "Waning", "Eclipse", "Twilight"]
days = {"January":31, "February":28, "March":31, "April":30, "May":31, "June":30,
"July":31, "August":31, "September":30, "October":31, "November":30, "December":31}
months_in_order = ["January","February","March","April","May","June","July","August","September","October","November","December"]
total = 0
for m in months_in_order:
if m == season: break
total += days[m]
total += dayCount - 1
start = phases.index(initialPhase)
return phases[(start + total) % 8]class Solution {
public String lunarPhase(String season, int dayCount, String initialPhase) {
String[] phases = {"NewMoon","Crescent","Quarter","Gibbous","Full","Waning","Eclipse","Twilight"};
String[] months = {"January","February","March","April","May","June","July","August","September","October","November","December"};
int[] days = {31,28,31,30,31,30,31,31,30,31,30,31};
int total = 0;
for (int i = 0; i < months.length; i++) { if (months[i].equals(season)) break; total += days[i]; }
total += dayCount - 1;
int start = 0; for (int i = 0; i < 8; i++) if (phases[i].equals(initialPhase)) { start = i; break; }
return phases[(start + total) % 8];
}
}string lunarPhase(string season, int dayCount, string initialPhase) {
vector<string> phases = {"NewMoon","Crescent","Quarter","Gibbous","Full","Waning","Eclipse","Twilight"};
vector<pair<string,int>> months = {{"January",31},{"February",28},{"March",31},{"April",30},{"May",31},{"June",30},
{"July",31},{"August",31},{"September",30},{"October",31},{"November",30},{"December",31}};
int total = 0;
for (auto& [m, d] : months) { if (m == season) break; total += d; }
total += dayCount - 1;
int start = find(phases.begin(), phases.end(), initialPhase) - phases.begin();
return phases[(start + total) % 8];
}Apply a sequence of commands to a matrix: swapRows r1 r2, swapColumns c1 c2, reverseRow r, reverseColumn c, rotate90Clockwise. Return the resulting matrix.
解法
直接模拟：除旋转外每个操作 O(R + C)，旋转 O(R · C)。最坏总复杂度 O(K · R · C)。旋转通过转置后反转每行实现。
def robot_matrix(mat, cmds):
M = [row[:] for row in mat]
for cmd in cmds:
parts = cmd.split()
op = parts[0]
if op == 'swapRows':
r1, r2 = int(parts[1]), int(parts[2]); M[r1], M[r2] = M[r2], M[r1]
elif op == 'swapColumns':
c1, c2 = int(parts[1]), int(parts[2])
for row in M: row[c1], row[c2] = row[c2], row[c1]
elif op == 'reverseRow':
r = int(parts[1]); M[r].reverse()
elif op == 'reverseColumn':
c = int(parts[1])
col = [M[i][c] for i in range(len(M))][::-1]
for i in range(len(M)): M[i][c] = col[i]
else:
nr, nc = len(M), len(M[0])
M = [[M[nr - 1 - i][j] for i in range(nr)] for j in range(nc)]
return Mclass Solution {
public int[][] robotMatrix(int[][] mat, String[] cmds) {
int[][] M = mat;
for (String cmd : cmds) {
String[] parts = cmd.split(" ");
switch (parts[0]) {
case "swapRows": { int r1 = Integer.parseInt(parts[1]), r2 = Integer.parseInt(parts[2]); int[] t = M[r1]; M[r1] = M[r2]; M[r2] = t; break; }
case "swapColumns": { int c1 = Integer.parseInt(parts[1]), c2 = Integer.parseInt(parts[2]); for (int[] row : M) { int t = row[c1]; row[c1] = row[c2]; row[c2] = t; } break; }
case "reverseRow": { int r = Integer.parseInt(parts[1]); for (int i = 0, j = M[r].length - 1; i < j; i++, j--) { int t = M[r][i]; M[r][i] = M[r][j]; M[r][j] = t; } break; }
case "reverseColumn": { int c = Integer.parseInt(parts[1]); for (int i = 0, j = M.length - 1; i < j; i++, j--) { int t = M[i][c]; M[i][c] = M[j][c]; M[j][c] = t; } break; }
case "rotate90Clockwise": {
int nr = M.length, nc = M[0].length;
int[][] nw = new int[nc][nr];
for (int j = 0; j < nc; j++) for (int i = 0; i < nr; i++) nw[j][i] = M[nr - 1 - i][j];
M = nw; break;
}
}
}
return M;
}
}vector<vector<int>> robotMatrix(vector<vector<int>>& mat, vector<string>& cmds) {
auto M = mat;
for (auto& cmd : cmds) {
stringstream ss(cmd); string op; ss >> op;
if (op == "swapRows") { int r1, r2; ss >> r1 >> r2; swap(M[r1], M[r2]); }
else if (op == "swapColumns") { int c1, c2; ss >> c1 >> c2; for (auto& row : M) swap(row[c1], row[c2]); }
else if (op == "reverseRow") { int r; ss >> r; reverse(M[r].begin(), M[r].end()); }
else if (op == "reverseColumn") { int c; ss >> c; int n = M.size(); for (int i = 0; i < n / 2; ++i) swap(M[i][c], M[n-1-i][c]); }
else {
int nr = M.size(), nc = M[0].size();
vector<vector<int>> nw(nc, vector<int>(nr));
for (int j = 0; j < nc; ++j) for (int i = 0; i < nr; ++i) nw[j][i] = M[nr-1-i][j];
M = nw;
}
}
return M;
}