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
For each index i (1 ≤ i ≤ n) temp_arr[i] = arr[p[i]]
arr = temp_arr
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 modulo10⁹ + 7
Constraints
1 ≤ n ≤ 10⁵1 ≤ p[i] ≤ n- p contains all distint elements, the integers 1 through n
解法
置换分解为若干循环，恢复原数组所需的最少操作数 = 所有循环长度的最小公倍数。DFS 标记每个循环、记录长度，再对所有长度求 LCM，对 10⁹ + 7 取模。复杂度 O(n log MAX)，空间 O(n)。
from math import gcd
from typing import List
def count_operations(p: List[int]) -> int:
MOD = 10**9 + 7
n = len(p)
seen = [False] * n
ans = 1
for i in range(n):
if seen[i]:
continue
j = i
length = 0
while not seen[j]:
seen[j] = True
j = p[j] - 1
length += 1
ans = ans // gcd(ans, length) * length
return ans % MODclass Solution {
int countOperations(int[] p) {
final int MOD = 1_000_000_007;
int n = p.length;
boolean[] seen = new boolean[n];
long ans = 1;
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
int j = i, length = 0;
while (!seen[j]) { seen[j] = true; j = p[j] - 1; length++; }
ans = ans / gcd(ans, length) * length % MOD;
}
return (int) ans;
}
private long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
}class Solution {
public:
int countOperations(vector<int>& p) {
const int MOD = 1'000'000'007;
int n = p.size();
vector<bool> seen(n, false);
long long ans = 1;
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
int j = i, length = 0;
while (!seen[j]) { seen[j] = true; j = p[j] - 1; ++length; }
ans = ans / __gcd(ans, (long long) length) * length % MOD;
}
return (int) ans;
}
};Huffman codes compress text by assigning the characters that occur at the highest frequency the shortest possible codes. In this encoding scheme, no code can be a prefix of another. For example, if the code for a is 01, then the code for b cannot be 011.
Given an array of Huffman code mappings and a Huffman-encoded string, find the decoded string. Each mapping will be a string consisting of a tab-separated ('\t') character and its encoded value: 'c encoded value' where the whitespace is a tab character. The newline character is represented as the character [newline] in the codes list, but should translate to \n when decoded.
Note: While all code mappings in the example are 6 digits long, mappings can be different lengths. The algorithm creates the shortest length mapping for the most frequent character encoded.
Function Description
Complete the function decode in the editor below. The function must return the decoded string.
decode has the following parameter(s):
string codes[n]: an array of character mappings in the form "character\tmapping"
encoded: an encoded string
Constraints
- 1 ≤ n ≤ 100
- 1 ≤ |encoded| ≤ 7000
- All characters of encoded are eithe
Example 1
Input:
codes = ["a 100100", "b 100101", "[newline] 111111"]
encoded = "100100111111100101"Output:
"a
b"Explanation: The output is "a\nb". There is a newline inbetween a and b.
解法
每行按 tab 拆分，建 encoding -> char 字典；[newline] 替换为 \n。然后扫描 encoded 串，维护当前累计 bit 串作为 key，命中字典即输出对应字符并清空。哈夫曼前缀性质保证不会歧义。复杂度 O(|encoded| · maxCodeLen) 最坏，空间 O(n)。
from typing import List
def decode(codes: List[str], encoded: str) -> str:
table = {}
for line in codes:
ch, code = line.split("\t") if "\t" in line else line.split(" ", 1)
if ch == "[newline]":
ch = "\n"
table[code] = ch
out = []
cur = ""
for b in encoded:
cur += b
if cur in table:
out.append(table[cur])
cur = ""
return "".join(out)import java.util.*;
class Solution {
String decode(String[] codes, String encoded) {
Map<String, String> table = new HashMap<>();
for (String line : codes) {
String[] parts = line.contains("\t") ? line.split("\t") : line.split(" ", 2);
String ch = parts[0].equals("[newline]") ? "\n" : parts[0];
table.put(parts[1], ch);
}
StringBuilder out = new StringBuilder();
StringBuilder cur = new StringBuilder();
for (char b : encoded.toCharArray()) {
cur.append(b);
String s = cur.toString();
if (table.containsKey(s)) { out.append(table.get(s)); cur.setLength(0); }
}
return out.toString();
}
}class Solution {
public:
string decode(vector<string>& codes, string encoded) {
unordered_map<string, string> table;
for (auto& line : codes) {
size_t sep = line.find('\t');
if (sep == string::npos) sep = line.find(' ');
string ch = line.substr(0, sep);
string code = line.substr(sep + 1);
if (ch == "[newline]") ch = "\n";
table[code] = ch;
}
string out, cur;
for (char b : encoded) {
cur += b;
auto it = table.find(cur);
if (it != table.end()) { out += it->second; cur.clear(); }
}
return out;
}
};Given a graph of friends who have different interests, determine which groups of friends have the most interests in common. Then use a little math to determine a value to return.
The graph will be represented as a series of nodes numbered consecutively from 1 to friends_nodes. Friendships have evolved based on interests which will be represented as weights in the graph. Any members who share the same interest are said to be connected by that interest. Once the node pairs with the maximum number of shared interests are determined, multiply the friends_nodes of the resulting node pairs and return the maximal product.
Function Description
Complete the function maxShared in the editor.
maxShared has the following parameter(s):
int friends_nodes: number of nodesint friends_from[friends_edges]: the first part of node pairsint friends_to[friends_edges]: the other part of node pairsint friends_weight[friends_edges]: the interests of node pairs Returnsint: maximal integer product of all node pairs sharing the most interests.
Constraints
A yet-to-be-unearthed secret
解法
把图按权重(兴趣)分组，每个兴趣下的节点集合 S，对集合内任意两点(无论是否直接相连)"共享兴趣" 数 += 1。等价于：对每对 (u, v)，他们共享兴趣数 = 二人同时出现在多少个兴趣对应的节点集合中。直接对每个兴趣枚举所有点对累加哈希表 (u,v) -> cnt。最后选出 cnt 最大的所有对，取其 u * v 的最大值。复杂度 O(Σ |S_k|²)，空间 O(n²) 最坏。
from typing import List
from collections import defaultdict
def max_shared(friends_nodes: int, friends_from: List[int], friends_to: List[int],
friends_weight: List[int]) -> int:
by_interest = defaultdict(set)
for u, v, w in zip(friends_from, friends_to, friends_weight):
by_interest[w].add(u)
by_interest[w].add(v)
share = defaultdict(int)
for nodes in by_interest.values():
nodes = sorted(nodes)
for i in range(len(nodes)):
for j in range(i + 1, len(nodes)):
share[(nodes[i], nodes[j])] += 1
if not share:
return 0
max_share = max(share.values())
return max(u * v for (u, v), c in share.items() if c == max_share)import java.util.*;
class Solution {
int maxShared(int friendsNodes, int[] friendsFrom, int[] friendsTo, int[] friendsWeight) {
Map<Integer, Set<Integer>> byInterest = new HashMap<>();
for (int i = 0; i < friendsFrom.length; i++) {
byInterest.computeIfAbsent(friendsWeight[i], k -> new TreeSet<>())
.add(friendsFrom[i]);
byInterest.get(friendsWeight[i]).add(friendsTo[i]);
}
Map<Long, Integer> share = new HashMap<>();
for (Set<Integer> set : byInterest.values()) {
List<Integer> list = new ArrayList<>(set);
for (int i = 0; i < list.size(); i++)
for (int j = i + 1; j < list.size(); j++) {
long key = (long) list.get(i) * 1_000_000L + list.get(j);
share.merge(key, 1, Integer::sum);
}
}
if (share.isEmpty()) return 0;
int maxShare = Collections.max(share.values());
int ans = 0;
for (var e : share.entrySet()) {
if (e.getValue() == maxShare) {
int u = (int) (e.getKey() / 1_000_000L);
int v = (int) (e.getKey() % 1_000_000L);
ans = Math.max(ans, u * v);
}
}
return ans;
}
}class Solution {
public:
int maxShared(int friendsNodes, vector<int>& friendsFrom, vector<int>& friendsTo,
vector<int>& friendsWeight) {
unordered_map<int, set<int>> byInterest;
for (size_t i = 0; i < friendsFrom.size(); ++i) {
byInterest[friendsWeight[i]].insert(friendsFrom[i]);
byInterest[friendsWeight[i]].insert(friendsTo[i]);
}
unordered_map<long long, int> share;
for (auto& [k, set_] : byInterest) {
vector<int> list(set_.begin(), set_.end());
for (size_t i = 0; i < list.size(); ++i)
for (size_t j = i + 1; j < list.size(); ++j) {
long long key = (long long) list[i] * 1000000LL + list[j];
share[key]++;
}
}
if (share.empty()) return 0;
int maxShare = 0;
for (auto& [k, v] : share) maxShare = max(maxShare, v);
int ans = 0;
for (auto& [k, v] : share) {
if (v == maxShare) {
int u = (int)(k / 1000000LL);
int w = (int)(k % 1000000LL);
ans = max(ans, u * w);
}
}
return ans;
}
};