Imagine a gravity-based puzzle game where an irregular figure made of * cells must fall to the bottom of board. Cells are '-' (empty), '#' (obstacle), or '*' (figure). Find the minimum number of '#' obstacles to remove so the figure can touch the bottom row with at least one of its cells. The figure is one connected piece.
- 1 ≤
board.length≤ 100 - 1 ≤
board[0].length≤ 100 board[i][j]∈{'-', '#', '*'}- Execution time limit: 3 seconds
- Memory limit: 1 GB
board = [['*', '*', '*'],
['#', '*', '#'],
['*', '-', '-'],
['-', '-', '-'],
['-', '#', '-']]
solution(board) = 2解法
每一列上图形会下落直到最底部的 * 触地。该列的代价 = 该最底 * 严格下方的 # 数。整个图形能下落的距离受最受限列约束，答案 = 所有列代价的最小值。复杂度 O(rows × cols)。
def solution(board: list[list[str]]) -> int:
rows, cols = len(board), len(board[0])
ans = float('inf')
for c in range(cols):
# 找到该列最底下的 '*' 行号
bottom_star = -1
for r in range(rows):
if board[r][c] == '*':
bottom_star = r
if bottom_star == -1:
continue # 这一列没有图形格子，跳过
# 数从 bottom_star + 1 到 rows - 1 之间 '#' 的个数
obstacles = 0
for r in range(bottom_star + 1, rows):
if board[r][c] == '#':
obstacles += 1
ans = min(ans, obstacles)
return ans if ans != float('inf') else 0class Solution {
int solution(char[][] board) {
int rows = board.length, cols = board[0].length;
int ans = Integer.MAX_VALUE;
for (int c = 0; c < cols; c++) {
// 找到该列最底下的 '*' 行号
int bottomStar = -1;
for (int r = 0; r < rows; r++) {
if (board[r][c] == '*') bottomStar = r;
}
if (bottomStar == -1) continue;
// 数从 bottomStar + 1 到 rows - 1 之间 '#' 的个数
int obstacles = 0;
for (int r = bottomStar + 1; r < rows; r++) {
if (board[r][c] == '#') obstacles++;
}
ans = Math.min(ans, obstacles);
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}class Solution {
public:
int solution(vector<vector<char>>& board) {
int rows = board.size(), cols = board[0].size();
int ans = INT_MAX;
for (int c = 0; c < cols; c++) {
// 找到该列最底下的 '*' 行号
int bottomStar = -1;
for (int r = 0; r < rows; r++) {
if (board[r][c] == '*') bottomStar = r;
}
if (bottomStar == -1) continue;
// 数从 bottomStar + 1 到 rows - 1 之间 '#' 的个数
int obstacles = 0;
for (int r = bottomStar + 1; r < rows; r++) {
if (board[r][c] == '#') obstacles++;
}
ans = min(ans, obstacles);
}
return ans == INT_MAX ? 0 : ans;
}
};Given readings, count how many entries are an integer power of k (i.e. k⁰, k¹, k², ...).
- 1 ≤
readings.length≤ 10⁵ - 1 ≤
readings[i]≤ 10⁹ - 2 ≤
k≤ 10⁹ - Memory limit: 1 GB
solution([1, 2, 3, 8, 16, 10, 120], 2) = 5solution([10000, 100, 1000000, 101, 1010, 1010000], 10) = 3解法
把所有 ≤ max(readings) 的 k 的幂存入哈希集合，每次读数 O(1) 查表。复杂度 O(n + log_k(maxVal))。
def solution(readings: list[int], k: int) -> int:
# 预生成所有 ≤ 1e9 的 k 的幂
max_val = max(readings)
powers = set()
p = 1 # k⁰
while p <= max_val:
powers.add(p)
# 防止 p * k 溢出（Python 没有 int 溢出，但仍要避免无意义的大数）
if p > max_val // k and p * k > max_val:
break
p *= k
return sum(1 for x in readings if x in powers)import java.util.HashSet;
import java.util.Set;
class Solution {
int solution(int[] readings, int k) {
// 预生成所有 ≤ 1e9 的 k 的幂
int maxVal = 0;
for (int x : readings) maxVal = Math.max(maxVal, x);
Set<Long> powers = new HashSet<>();
long p = 1L; // k⁰；用 long 防溢出
while (p <= maxVal) {
powers.add(p);
if (p > Long.MAX_VALUE / k) break;
p *= k;
}
int count = 0;
for (int x : readings) {
if (powers.contains((long) x)) count++;
}
return count;
}
}#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int solution(vector<int>& readings, int k) {
// 预生成所有 ≤ maxVal 的 k 的幂
int maxVal = *max_element(readings.begin(), readings.end());
unordered_set<long long> powers;
long long p = 1; // k⁰；用 long long 防溢出
while (p <= maxVal) {
powers.insert(p);
if (p > LLONG_MAX / k) break;
p *= k;
}
int count = 0;
for (int x : readings) {
if (powers.count((long long) x)) count++;
}
return count;
}
};Given numbers and a pattern of {-1, 0, 1} (less / equal / greater than previous), count how many length-(m+1) subarrays of numbers match the pattern, where each consecutive pair's sign relation matches pattern[j].
- 2 ≤
numbers.length≤ 10⁴ - 1 ≤
pattern.length<numbers.length - −10⁹ ≤
numbers[i]≤ 10⁹ pattern[i]∈{-1, 0, 1}- Execution time limit: 4 seconds
- Memory limit: 1 GB
numbers = [1, 4, 4, 1, 3, 5, 5, 3]
pattern = [1, 0, -1]
solution(numbers, pattern) = 2| start | subarray | signs | match |
|---|---|---|---|
| 0 | [1, 4, 4, 1] | +, =, - → 1, 0, -1 | yes |
| 1 | [4, 4, 1, 3] | =, -, + → 0, -1, 1 | no |
| 2 | [4, 1, 3, 5] | -, +, + → -1, 1, 1 | no |
| 3 | [1, 3, 5, 5] | +, +, = → 1, 1, 0 | no |
| 4 | [3, 5, 5, 3] | +, =, - → 1, 0, -1 | yes |
解法
枚举长度为 m+1 的窗口起点 i。对 j ∈ [0, m) 比较 numbers[i+j+1] 与 numbers[i+j]，检查符号是否匹配 pattern[j]。复杂度 O((n - m) · m)。
def solution(numbers: list[int], pattern: list[int]) -> int:
n, m = len(numbers), len(pattern)
count = 0
# 枚举每个长度 m+1 的子数组起点
for i in range(n - m):
ok = True
for j in range(m):
diff = numbers[i + j + 1] - numbers[i + j]
# diff 的正负号必须与 pattern[j] 一致
if pattern[j] == 1 and diff <= 0:
ok = False
break
if pattern[j] == 0 and diff != 0:
ok = False
break
if pattern[j] == -1 and diff >= 0:
ok = False
break
if ok:
count += 1
return countclass Solution {
int solution(int[] numbers, int[] pattern) {
int n = numbers.length, m = pattern.length;
int count = 0;
// 枚举每个长度 m+1 的子数组起点
for (int i = 0; i <= n - m - 1; i++) {
boolean ok = true;
for (int j = 0; j < m; j++) {
int diff = numbers[i + j + 1] - numbers[i + j];
// diff 的正负号必须与 pattern[j] 一致
if (pattern[j] == 1 && diff <= 0) { ok = false; break; }
if (pattern[j] == 0 && diff != 0) { ok = false; break; }
if (pattern[j] == -1 && diff >= 0) { ok = false; break; }
}
if (ok) count++;
}
return count;
}
}class Solution {
public:
int solution(vector<int>& numbers, vector<int>& pattern) {
int n = numbers.size(), m = pattern.size();
int count = 0;
// 枚举每个长度 m+1 的子数组起点
for (int i = 0; i + m < n; i++) {
bool ok = true;
for (int j = 0; j < m; j++) {
long long diff = (long long) numbers[i + j + 1] - numbers[i + j];
// diff 的正负号必须与 pattern[j] 一致
if (pattern[j] == 1 && diff <= 0) { ok = false; break; }
if (pattern[j] == 0 && diff != 0) { ok = false; break; }
if (pattern[j] == -1 && diff >= 0) { ok = false; break; }
}
if (ok) count++;
}
return count;
}
};