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 from 1 to n Returns int: the number of operations required modulo 10⁹ + 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 % MOD

class 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 nodes
• int friends_from[friends_edges]: the first part of node pairs
• int friends_to[friends_edges]: the other part of node pairs
• int friends_weight[friends_edges]: the interests of node pairs Returns int: maximal integer product of all node pairs sharing the most interests.

Constraints

A yet-to-be-unearthed secret