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 ans

class 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 = 8

Output:

6

Explanation: :)

解法

二分速度 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 lo

class 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 standing
• int 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) Constraints
• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 100
• 1 ≤ k ≤ 100
• Each cell of the grid contains values either 0 or 1.

Example 1

Input:

maze = [[0, 0], [1, 0]]
k = 2

Output:

2

Explanation: 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 = 5

Output:

2

Explanation: 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];
    }
};

Your daughter, Alex, has just come home with a bag full of candy after a long night of trick-or-treating. Before going to sleep, Alex places the candy in numPiles piles with the i-th pile containing candyPiles[i] number of candies. After arranging the candies into piles, Alex announces she is going to sleep for numHours hours. Your plan is to eat all the candy before Alex wakes up in numHours. You can eat c candies per hour, but in each hour you will only eat candy from a single pile. If a pile contains fewer than c candies, you will only eat the number of candies in that pile and you will wait until the next hour to eat more candy. Having a little bit of self-restraint your goal is to calculate the smallest number of candies c you need to eat per hour in order to finish all the candy before Alex wakes up again. Function Description Complete the function minimumEatingSpeed in the editor. minimumEatingSpeed has the following parameters:

• int[] candyPiles: an array of integers representing the number of candies in each pile
• int numHours: the number of hours Alex will be asleep for Returns int: the smallest number of candies c that you need to eat per hour in order to finish all the candies before Alex wakes up

Given a GET request query string, parse the key-value pairs into a normalized representation. The input may start with ?. Parameters are separated by &. A parameter can have one of these forms:

• key=value: stores the parsed value for key.
• !key: stores the boolean value true for key. Keys may repeat. If a key appears more than once, preserve all of its values in insertion order. Values can be integers, booleans, quoted strings, or list literals. For this function, return a stable string serialization of the parsed map:
• Return one entry per distinct key.
• Keep keys in the order they first appear.
• Represent a single value as key=value.
• Represent multiple values as key=value1|value2|....
• Remove surrounding double quotes from quoted string values.

Constraints

• 0 ≤ query.length ≤ 10⁵
• Keys are non-empty and contain letters, digits, underscores, or hyphens.
• Values do not contain unescaped &.

Example 1

Input:

query = "?key1=1&key1=\"abc\"&key2=value1&!isBooleanField"

Output:

["key1=1|abc","key2=value1","isBooleanField=true"]

Explanation: key1 appears twice, so both values are preserved. The boolean shorthand !isBooleanField stores true.

Example 2

Input:

query = "page=2&active=false&tags=[red,blue]&page=3"

Output:

["page=2|3","active=false","tags=red|blue"]

Explanation: The parser keeps the first-seen key order: page, active, then tags.

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. You are given n sentences and a fixed table content width width. Print each sentence as one row in a bordered table. Input The first line contains two integers n and width. The next n lines each contain one sentence. Sentences may contain spaces, and each sentence length is guaranteed to be at most width. Output For each sentence, output a border line, then the sentence row, then continue with the next border line. A border line is +, followed by width + 2 dash characters, followed by +. A sentence row starts with | , then the sentence, then enough trailing spaces to fill exactly width content characters, then |. If n = 0, return no output lines. Example Input: 3 55, followed by Hello world, How are you today, and Bye. The sample output is shown in the visible example. Function Description Complete solvePrintSentencesAsTable. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

• 0 ≤ n ≤ 10⁵
• 1 ≤ width ≤ 10⁴
• Each sentence contains printable ASCII characters and spaces.
• Each sentence length is at most width.

The input is a list of strings, each describing the action of an army. For example: 'A Munich Hold' means Army A is stationed in Munich and does not move. 'B Warsaw Support A' means Army B, located in Warsaw, provides support to Army A, increasing its strength. In this case, Army A's strength becomes 2. 'C Bohemia Move Munich' means Army C, located in Bohemia, is attacking Munich. In this scenario, Army C has a strength of 1, and Army A has a strength of 2 (due to support from Army B). As a result, Army C loses, and Army A successfully defends Munich. If multiple armies in the same location have equal strength, they all lose. If an army is providing support but gets attacked itself (meaning another army moves into its location), its support becomes invalid. The function needs to return a list of strings, each describing the final state of every army. For example, in the above scenario, the output would be: ['A Munich', 'B Warsaw', 'C [dead]'].

Example 1

Input:

actions = ["A Munich Hold", "B Warsaw Support A", "C Bohemia Move Munich"]

Output:

["A Munich", "B Warsaw", "C [dead]"]

Explanation: In this scenario, Army C has a strength of 1, and Army A has a strength of 2 (due to support from Army B). As a result, Army C loses, and Army A successfully defends Munich. The final state of each army is as follows:

• Army A remains in Munich.
• Army B remains in Warsaw.
• Army C is defeated and is marked as [dead].

Given a float array price

Example 1

Input:

prices = [1.2, 4.3, 5.8, 6.4]
target = 18

Output:

[1, 4, 6, 7]

Explanation: :)