Contiguous subarrays are a group of an uninterrupted range of elements from an array as they occur. No elements in the range can be skipped or reordered. Given an array of integers numbers and an integer k, determine the total number of subarrays of numbers that have a product less than or equal to k.
Constraints
1 ≤ n ≤ 5×10⁵, 1 ≤ numbers[i] ≤ 100, 1 ≤ k ≤ 10⁶. Return long int.
Example: numbers = [2, 3, 4], k = 12 → 5 (subarrays [2], [3], [4], [2,3], [3,4]).
解法
滑动窗口：维护当前乘积，prod > k 时收缩左端。每个合法的 r 贡献 r - l + 1 个子数组。复杂度 O(N)。
def count_subarrays(nums, k):
if k < 1:
return 0
ans = 0
prod, l = 1, 0
for r, x in enumerate(nums):
prod *= x
while prod > k:
prod //= nums[l]
l += 1
ans += r - l + 1
return ansclass Solution {
public static long count(int[] nums, int k) {
if (k < 1) return 0;
long ans = 0, prod = 1;
int l = 0;
for (int r = 0; r < nums.length; r++) {
prod *= nums[r];
while (prod > k) prod /= nums[l++];
ans += r - l + 1;
}
return ans;
}
}long long countSubarrays(vector<int>& nums, int k) {
if (k < 1) return 0;
long long ans = 0, prod = 1;
int l = 0;
for (int r = 0; r < (int)nums.size(); r++) {
prod *= nums[r];
while (prod > k) prod /= nums[l++];
ans += r - l + 1;
}
return ans;
}A bakery is having a donut eating challenge! In order to win, you must eat all numBoxes boxes of donuts, with the i-th box having donutBoxes[i] number of donuts. To make things more difficult, the challenge has a time limit of numMinutes minutes.
Your plan is to eat d donuts per minute, but in each minute you will only eat donuts from a single box. If a box contains fewer than d donuts, you will only eat the number of donuts in that box and you will wait until the next minute to eat more donuts.
You know you can win the challenge, but you want to pace yourself. What is the smallest number of donuts d you need to eat per minute in order to eat all the donuts within the time limit?
Input Format
The first line of the input will be an integer, numBoxes, representing the total number of boxes.
The following numBoxes lines of the input will be integers, representing the number of donuts in each box. The i-th line will be donutBoxes[i], the number of donuts in the i-th box.
The last line of the input will be an integer, numMinutes, representing the time limit of the challenge.
Output Format
The output will be an integer, representing the smallest number of donuts (d) that you need to eat per minute in order to complete the challenge within the time limit.
Constraints
- The time limit of the challenge in minutes (
numMinutes) will always be equal to, or grea
Example 1
Input:
donutBoxes = [4, 9, 11, 17]
numMinutes = 8Output:
6Explanation: :)
解法
二分速度 d ∈ [1, max(donutBoxes)]。给定 d，所需分钟 = Σ box / d。找满足 ≤ numMinutes 的最小 d。时间 O(n log max)。
from typing import List
def donut_challenge(donut_boxes: List[int], num_minutes: int) -> int:
lo, hi = 1, max(donut_boxes)
while lo < hi:
mid = (lo + hi) // 2
need = sum((b + mid - 1) // mid for b in donut_boxes)
if need <= num_minutes: hi = mid
else: lo = mid + 1
return loclass Solution {
public int donutChallenge(int[] donutBoxes, int numMinutes) {
int lo = 1, hi = 0;
for (int b : donutBoxes) hi = Math.max(hi, b);
while (lo < hi) {
int mid = (lo + hi) / 2;
long need = 0;
for (int b : donutBoxes) need += (b + mid - 1) / mid;
if (need <= numMinutes) hi = mid; else lo = mid + 1;
}
return lo;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int donutChallenge(vector<int>& donutBoxes, int numMinutes) {
int lo = 1, hi = 0;
for (int b : donutBoxes) hi = max(hi, b);
while (lo < hi) {
int mid = (lo + hi) / 2;
long long need = 0;
for (int b : donutBoxes) need += (b + mid - 1) / mid;
if (need <= numMinutes) hi = mid; else lo = mid + 1;
}
return lo;
}
};There is a maze in HackerPlay where children play for recreation.
The maze is represented as an n * m grid of cells, where each cell is either empty (denoted by 0), or contains an obstacle (denoted by 1). HackerMan is currently standing at cell (0, 0) and wishes to reach the cell (n - 1, m - 1).
For a jump parameter denoted by k, in one move, HackerMan can move to any of the following cells:
(i + x, j) where 1 ≤ x ≤ k provided cell (i + x, j) lies in the maze and there are no cells containing obstacles in the range (i, j) → (i + 1, j) → ... → (i + x, j).
(i - x, j) where 1 ≤ x ≤ k provided cell (i - x, j) lies in the maze and there are no cells containing obstacles in the range (i, j) → (i - 1, j) → ... → (i - x, j).
(i, j + x) where 1 ≤ x ≤ k provided cell (i, j + x) lies in the maze and there are no cells containing obstacles in the range (i, j) → (i, j + 1) → ... → (i, j + x).
(i, j - x) where 1 ≤ x ≤ k provided cell (i, j - x) lies in the maze and there are no cells containing obstacles in the range (i, j) → (i, j - 1) → ... → (i, j - x).
Find the minimum number of moves in which HackerMan can reach the cell (n - 1, m - 1) starting from (0, 0), or -1 if it is impossible to reach that cell.
Function Description
Complete the function getMinimumMoves in the editor below.
getMinimumMoves has the following parameters:
int maze[n][m]: the maze in HackerPlay where HackerMan is standingint k: the maximum distance HackerMan can traverse in one move Returns int: the minimum number of moves in which HackerMan can reach the destination cell(n - 1, m - 1)Constraints1 ≤ n ≤ 1001 ≤ m ≤ 1001 ≤ k ≤ 100- Each cell of the grid contains values either
0or1.
Example 1
Input:
maze = [[0, 0], [1, 0]]
k = 2Output:
2Explanation:
The maze looks like this.
0 0
1 0
The following sequence of moves can be performed: (0, 0) → (0, 1) → (1, 1). Hence, HackerMan can reach the end in 2 moves, which is minimum possible. The answer is 2.
Example 2
Input:
maze = [[0, 0, 0], [1, 0, 0]]
k = 5Output:
2Explanation:
The maze can be represented as:
0 0 0
1 0 0
The following sequence of moves can be performed: (0, 0) → (0, 2) → (1, 2).
解法
BFS：每个状态是 (r, c)，相邻状态是同方向连续走 1..k 步且不撞障碍可达的所有格子。逐方向尝试，遇到障碍就停。第一次到达 (n-1, m-1) 的步数即答案。时间 O(n·m·k)。
from collections import deque
from typing import List
def get_minimum_moves(maze: List[List[int]], k: int) -> int:
n, m = len(maze), len(maze[0])
if maze[0][0] == 1 or maze[n - 1][m - 1] == 1:
return -1
dist = [[-1] * m for _ in range(n)]
dist[0][0] = 0
q = deque([(0, 0)])
while q:
r, c = q.popleft()
if (r, c) == (n - 1, m - 1):
return dist[r][c]
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
for x in range(1, k + 1):
nr, nc = r + dr * x, c + dc * x
if not (0 <= nr < n and 0 <= nc < m) or maze[nr][nc] == 1:
break
if dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
return dist[n - 1][m - 1]import java.util.*;
class Solution {
public int getMinimumMoves(int[][] maze, int k) {
int n = maze.length, m = maze[0].length;
if (maze[0][0] == 1 || maze[n - 1][m - 1] == 1) return -1;
int[][] dist = new int[n][m];
for (int[] row : dist) Arrays.fill(row, -1);
dist[0][0] = 0;
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[]{0, 0});
int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
if (r == n - 1 && c == m - 1) return dist[r][c];
for (int i = 0; i < 4; i++) {
for (int x = 1; x <= k; x++) {
int nr = r + dr[i] * x, nc = c + dc[i] * x;
if (nr < 0 || nr >= n || nc < 0 || nc >= m || maze[nr][nc] == 1) break;
if (dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.add(new int[]{nr, nc});
}
}
}
}
return dist[n - 1][m - 1];
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int getMinimumMoves(vector<vector<int>>& maze, int k) {
int n = maze.size(), m = maze[0].size();
if (maze[0][0] == 1 || maze[n - 1][m - 1] == 1) return -1;
vector<vector<int>> dist(n, vector<int>(m, -1));
dist[0][0] = 0;
queue<pair<int,int>> q; q.push({0, 0});
int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
if (r == n - 1 && c == m - 1) return dist[r][c];
for (int i = 0; i < 4; i++) {
for (int x = 1; x <= k; x++) {
int nr = r + dr[i] * x, nc = c + dc[i] * x;
if (nr < 0 || nr >= n || nc < 0 || nc >= m || maze[nr][nc] == 1) break;
if (dist[nr][nc] == -1) { dist[nr][nc] = dist[r][c] + 1; q.push({nr, nc}); }
}
}
}
return dist[n - 1][m - 1];
}
};