When given a number N, for each integer i in the range from 1 to N inclusive, print one value per line as follows:
- If
iis a multiple of both 3 and 5, printFizzBuzz. - If
iis a multiple of 3 but not 5, printFizz. - If
iis a multiple of 5 but not 3, printBuzz. - Otherwise, print the value of
i.
Constraints
0 < N ≤ 2 × 10⁶.
解法
线性扫描，用 by3 / by5 两个布尔标记。输出用 StringBuilder 或预分配字符串缓冲，避免大 N 下的二次拼接。复杂度 O(N)。
import sys
def fizz_buzz(n: int) -> str:
out = []
for i in range(1, n + 1):
by3, by5 = i % 3 == 0, i % 5 == 0
if by3 and by5: out.append("FizzBuzz")
elif by3: out.append("Fizz")
elif by5: out.append("Buzz")
else: out.append(str(i))
return '\n'.join(out)
if __name__ == "__main__":
n = int(sys.stdin.readline())
sys.stdout.write(fizz_buzz(n))import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) {
boolean by3 = i % 3 == 0, by5 = i % 5 == 0;
if (by3 && by5) sb.append("FizzBuzz");
else if (by3) sb.append("Fizz");
else if (by5) sb.append("Buzz");
else sb.append(i);
sb.append('\n');
}
System.out.print(sb);
}
}#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int n; cin >> n;
string out;
out.reserve(n * 4);
for (int i = 1; i <= n; i++) {
bool by3 = i % 3 == 0, by5 = i % 5 == 0;
if (by3 && by5) out += "FizzBuzz";
else if (by3) out += "Fizz";
else if (by5) out += "Buzz";
else out += to_string(i);
out += '\n';
}
cout << out;
}There is a set of N jars containing chocolates. Some of them may be empty. Determine the maximum number of chocolates Andrew can pick from the jars given that he cannot pick from jars next to each other.
Input: first line N, second line N space-separated integers (chocolates per jar).
Output: max chocolates pickable.
Constraints
1 ≤ N ≤ 1000.
解法
经典打家劫舍 DP：dp[i] = max(dp[i-1], dp[i-2] + jars[i])。滚动两个变量即可。时间 O(N)，空间 O(1)。
def tallest_chocolate(jars: list[int]) -> int:
prev2 = prev1 = 0
for x in jars:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int prev2 = 0, prev1 = 0;
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int cur = Math.max(prev1, prev2 + x);
prev2 = prev1;
prev1 = cur;
}
System.out.println(prev1);
}
}#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
int prev2 = 0, prev1 = 0;
for (int i = 0; i < n; i++) {
int x; cin >> x;
int cur = max(prev1, prev2 + x);
prev2 = prev1;
prev1 = cur;
}
cout << prev1;
}Find the element which is largest in its row and smallest in its column in a matrix. If no such element exists, print -1.
Input: N M then N rows of M non-negative integers.
Constraints
1 ≤ N, M ≤ 1000.
2 2
1 2
3 4
→ 2解法
预处理 rowMax[i](第 i 行最大值所在列)和 colMin[j](第 j 列最小值所在行)。(i, j) 是鞍点当且仅当 j == rowMax[i] 且 i == colMin[j]。复杂度 O(N · M)。
def saddle_point(a: list[list[int]]) -> int:
n, m = len(a), len(a[0])
row_max_col = [max(range(m), key=lambda j: a[i][j]) for i in range(n)]
col_min_row = [min(range(n), key=lambda i: a[i][j]) for j in range(m)]
for i in range(n):
j = row_max_col[i]
if col_min_row[j] == i:
return a[i][j]
return -1import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[][] a = new int[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) a[i][j] = sc.nextInt();
int[] rowMaxCol = new int[n], colMinRow = new int[m];
for (int i = 0; i < n; i++) {
int idx = 0;
for (int j = 1; j < m; j++) if (a[i][j] > a[i][idx]) idx = j;
rowMaxCol[i] = idx;
}
for (int j = 0; j < m; j++) {
int idx = 0;
for (int i = 1; i < n; i++) if (a[i][j] < a[idx][j]) idx = i;
colMinRow[j] = idx;
}
for (int i = 0; i < n; i++) {
int j = rowMaxCol[i];
if (colMinRow[j] == i) { System.out.println(a[i][j]); return; }
}
System.out.println(-1);
}
}#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m; cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> a[i][j];
vector<int> rowMaxCol(n), colMinRow(m);
for (int i = 0; i < n; i++) {
int idx = 0;
for (int j = 1; j < m; j++) if (a[i][j] > a[i][idx]) idx = j;
rowMaxCol[i] = idx;
}
for (int j = 0; j < m; j++) {
int idx = 0;
for (int i = 1; i < n; i++) if (a[i][j] < a[idx][j]) idx = i;
colMinRow[j] = idx;
}
for (int i = 0; i < n; i++) {
int j = rowMaxCol[i];
if (colMinRow[j] == i) { cout << a[i][j]; return 0; }
}
cout << -1;
}