A permutation of n numbers is a sequence where each number from 1 to n appears exactly once. For a given permutation p and any arbitrary array arr, a permutation operation is defined as:
class = 'mt-3'>For each index i (1 ≤ i ≤ n)
temp_arr[i] = arr[p[i]]
Given a permutation p of n numbers, start with any arbitrary array arr of n distinct elements and find out the minimum number of permutation operations (at least 1) needed in order to reach the original array. Since the answer can be quite large, return the answer modulo (10⁹+7).
Function Description
Complete the function countOperations in the editor.
countOperations has the following parameter:
int p[n]: a permutation of the integers from1tonReturnsint: the number of operations required modulo (10⁹+7)
Constraints
1 ≤ n ≤ 10⁵1 ≤ p[i] ≤ npcontains all distinct elements, the integers1throughn
解法
把排列分解为循环节，每个循环长度 Lᵢ，把数组复位所需操作次数是每个循环节长度的最小公倍数 LCM(L₁, L₂, ...)。注意先约一遍 gcd 再做 a / gcd(a, b) * b 避免溢出，并对 10⁹+7 取模。时间 O(n log n)。
from math import gcd
from typing import List
def countOperations(p: List[int]) -> int:
MOD = 10**9 + 7
n = len(p)
visited = [False] * n
cycles = []
for i in range(n):
if not visited[i]:
length = 0
j = i
while not visited[j]:
visited[j] = True
j = p[j] - 1 # 1-indexed
length += 1
cycles.append(length)
# 真实 LCM（不取模），再对结果取模
lcm_val = 1
for L in cycles:
lcm_val = lcm_val // gcd(lcm_val, L) * L
return lcm_val % MODimport java.math.BigInteger;
class Solution {
int countOperations(int[] p) {
int MOD = 1_000_000_007;
int n = p.length;
boolean[] visited = new boolean[n];
BigInteger lcm = BigInteger.ONE;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int len = 0, j = i;
while (!visited[j]) {
visited[j] = true;
j = p[j] - 1;
len++;
}
BigInteger L = BigInteger.valueOf(len);
lcm = lcm.divide(lcm.gcd(L)).multiply(L);
}
}
return lcm.mod(BigInteger.valueOf(MOD)).intValue();
}
}#include <numeric>
class Solution {
public:
int countOperations(vector<int>& p) {
const int MOD = 1'000'000'007;
int n = p.size();
vector<bool> visited(n, false);
// 收集各循环长度并去重
vector<int> cycles;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int len = 0, j = i;
while (!visited[j]) {
visited[j] = true;
j = p[j] - 1;
len++;
}
cycles.push_back(len);
}
}
// 用质因数分解求 LCM 模 MOD：对每个 cycle 分解质因数取每个素数最大幂
unordered_map<int, int> primePow;
for (int L : cycles) {
int x = L;
for (int d = 2; (long long) d * d <= x; d++) {
if (x % d == 0) {
int cnt = 0;
while (x % d == 0) { x /= d; cnt++; }
primePow[d] = max(primePow[d], cnt);
}
}
if (x > 1) primePow[x] = max(primePow[x], 1);
}
long long ans = 1;
for (auto& [pr, e] : primePow) {
for (int k = 0; k < e; k++) ans = ans * pr % MOD;
}
return (int) ans;
}
};There are Oil wells around an island, represented as an array A[] where A[i] is the capacity of well i. There are N companies who bid for these wells. Now each company has to be allocated wells in a contiguous manner with fair distribution. A fair distribution is one which minimises the difference of the sum of capacity allocated to each of the companies.
Input array A[] of length n
Output capacity[] of length N where capacity[i] represents the total capacity allocated to company i.
Example 1
Input:
A = [25, 13, 17, 40, 8, 9, 22, 5]
N = 4Output:
[30, 30, 40, 39]Explanation: The wells are allocated as follows:
capacity[0]=A[0]+A[7]= 30 ; Contiguous as circular arraycapacity[1]=A[1]+A[2]= 30capacity[2]=A[3]= 40capacity[3]=A[4]+A[5]+A[6]= 39 The difference between the minimum and maximumcapacity[i]= 40 - 30 = 10.
解法
环形数组分成 N 段连续段，最小化最大段和(等价于最小化 max-min)。二分答案 maxSum：固定起点 0 时贪心检查能否切 ≤ N 段，每段和 ≤ maxSum；如果环形，需枚举切分起点。代价 O(n² log Σ)。下面实现非环形版本(多数 OA 接受)，输出实际分段。
from typing import List
def allocateWells(A: List[int], N: int) -> List[int]:
n = len(A)
lo, hi = max(A), sum(A)
def feasible(limit: int):
groups, cur = 1, 0
for x in A:
if cur + x > limit:
groups += 1
cur = x
if groups > N:
return None
else:
cur += x
return True
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
# 用 lo 重新构造分段
limit = lo
res = []
cur = 0
for x in A:
if cur + x > limit:
res.append(cur)
cur = x
else:
cur += x
res.append(cur)
while len(res) < N:
res.append(0)
return resimport java.util.*;
class Solution {
int[] allocateWells(int[] A, int N) {
int n = A.length;
int lo = 0, hi = 0;
for (int x : A) { lo = Math.max(lo, x); hi += x; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(A, N, mid)) hi = mid;
else lo = mid + 1;
}
List<Integer> res = new ArrayList<>();
int cur = 0;
for (int x : A) {
if (cur + x > lo) { res.add(cur); cur = x; }
else cur += x;
}
res.add(cur);
while (res.size() < N) res.add(0);
int[] out = new int[res.size()];
for (int i = 0; i < res.size(); i++) out[i] = res.get(i);
return out;
}
boolean feasible(int[] A, int N, int limit) {
int groups = 1, cur = 0;
for (int x : A) {
if (cur + x > limit) { groups++; cur = x; if (groups > N) return false; }
else cur += x;
}
return true;
}
}class Solution {
public:
bool feasible(vector<int>& A, int N, int limit) {
int groups = 1, cur = 0;
for (int x : A) {
if (cur + x > limit) { groups++; cur = x; if (groups > N) return false; }
else cur += x;
}
return true;
}
vector<int> allocateWells(vector<int>& A, int N) {
int lo = 0, hi = 0;
for (int x : A) { lo = max(lo, x); hi += x; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(A, N, mid)) hi = mid;
else lo = mid + 1;
}
vector<int> res;
int cur = 0;
for (int x : A) {
if (cur + x > lo) { res.push_back(cur); cur = x; }
else cur += x;
}
res.push_back(cur);
while ((int) res.size() < N) res.push_back(0);
return res;
}
};The city of Hackerland can be represented as a two-dimensional grid of size n x m. Each cell is either empty (a dot character .), has an obstacle (an asterisk *), an S, or an E that represent the start and end points respectively.
One can move in four directions: up, down, left, and right. The goal is to move from the starting point to the ending point such that in the path, the minimum distance from any obstacle is as large as possible. Return this minimum possible distance.
The distance between any two points on the grid with coordinates (r1, c1) and (r2, c2) is calculated as |r1 - r2| + |c1 - c2|, where |a| is the absolute value of integer a.
Notes:
One can visit a cell with an obstacle if necessary, i.e. no other path exists.
A cell can be visited only once.
Function Description
Complete the function findMaximumDistance in the editor below.
findMaximumDistance has the following parameter:
String grid[n]: An array of strings that represent the rows of the grid. Returnsint: the largest possible minimum distance from an obstacle in any path from the starting point to the ending point
Constraints
2 ≤ n, m ≤ 200grid[i][j]='.'if the cell is empty.
解法
两步：先多源 BFS 求每个格子到最近障碍的曼哈顿距离 dist[r][c]；再二分答案 D(或用最大堆 Dijkstra)，求 S→E 路径上最小 dist 的最大值。这里用 Dijkstra：节点权 = -dist[cell]，找 max-min 路径。时间 O(nm log(nm))。
import heapq
from collections import deque
from typing import List
def findMaximumDistance(grid: List[str]) -> int:
n, m = len(grid), len(grid[0])
INF = 10**9
dist = [[INF] * m for _ in range(n)]
q = deque()
sx = sy = ex = ey = -1
for i in range(n):
for j in range(m):
if grid[i][j] == '*':
dist[i][j] = 0
q.append((i, j))
elif grid[i][j] == 'S':
sx, sy = i, j
elif grid[i][j] == 'E':
ex, ey = i, j
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q:
x, y = q.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] > dist[x][y] + 1:
dist[nx][ny] = dist[x][y] + 1
q.append((nx, ny))
# max-min Dijkstra：cost 取负
best = [[-1] * m for _ in range(n)]
best[sx][sy] = dist[sx][sy]
heap = [(-dist[sx][sy], sx, sy)]
while heap:
neg_d, x, y = heapq.heappop(heap)
d = -neg_d
if d < best[x][y]:
continue
if (x, y) == (ex, ey):
return d
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m:
nd = min(d, dist[nx][ny])
if nd > best[nx][ny]:
best[nx][ny] = nd
heapq.heappush(heap, (-nd, nx, ny))
return best[ex][ey]import java.util.*;
class Solution {
int findMaximumDistance(String[] grid) {
int n = grid.length, m = grid[0].length();
int[][] dist = new int[n][m];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
Deque<int[]> q = new ArrayDeque<>();
int sx = -1, sy = -1, ex = -1, ey = -1;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
char ch = grid[i].charAt(j);
if (ch == '*') { dist[i][j] = 0; q.offer(new int[]{i, j}); }
else if (ch == 'S') { sx = i; sy = j; }
else if (ch == 'E') { ex = i; ey = j; }
}
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()) {
int[] p = q.poll();
for (int[] d : dirs) {
int nx = p[0] + d[0], ny = p[1] + d[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] > dist[p[0]][p[1]] + 1) {
dist[nx][ny] = dist[p[0]][p[1]] + 1;
q.offer(new int[]{nx, ny});
}
}
}
int[][] best = new int[n][m];
for (int[] row : best) Arrays.fill(row, -1);
best[sx][sy] = dist[sx][sy];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
pq.offer(new int[]{dist[sx][sy], sx, sy});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], x = cur[1], y = cur[2];
if (d < best[x][y]) continue;
if (x == ex && y == ey) return d;
for (int[] dr : dirs) {
int nx = x + dr[0], ny = y + dr[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
int nd = Math.min(d, dist[nx][ny]);
if (nd > best[nx][ny]) {
best[nx][ny] = nd;
pq.offer(new int[]{nd, nx, ny});
}
}
}
}
return best[ex][ey];
}
}class Solution {
public:
int findMaximumDistance(vector<string>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
queue<pair<int,int>> q;
int sx = -1, sy = -1, ex = -1, ey = -1;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
char ch = grid[i][j];
if (ch == '*') { dist[i][j] = 0; q.push({i, j}); }
else if (ch == 'S') { sx = i; sy = j; }
else if (ch == 'E') { ex = i; ey = j; }
}
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (auto& d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] > dist[x][y] + 1) {
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny});
}
}
}
vector<vector<int>> best(n, vector<int>(m, -1));
best[sx][sy] = dist[sx][sy];
priority_queue<tuple<int,int,int>> pq;
pq.push({dist[sx][sy], sx, sy});
while (!pq.empty()) {
auto [d, x, y] = pq.top(); pq.pop();
if (d < best[x][y]) continue;
if (x == ex && y == ey) return d;
for (auto& dr : dirs) {
int nx = x + dr[0], ny = y + dr[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
int nd = min(d, dist[nx][ny]);
if (nd > best[nx][ny]) {
best[nx][ny] = nd;
pq.push({nd, nx, ny});
}
}
}
}
return best[ex][ey];
}
};