米哈游

1. 队列操作中维护当前不同种类数

难度感：easy

题目

给定若干操作：1 c 表示把种类为 c 的元素入队，2 表示队头出队，3 表示询问当前队列中有多少种不同元素。每次操作 3 输出答案。

题解

• 队列保存入队顺序，哈希表保存每种元素当前出现次数。
• 入队时，如果该种类原次数为 0，不同种类数加 1。
• 出队时，取出队头元素并减少计数；如果计数变成 0，不同种类数减 1。

复杂度：O(q) 时间，O(q) 空间。

C# 答案

using System;
using System.Collections.Generic;

public class MainClass
{
    public static void Main()
    {
        int q = int.Parse(Console.ReadLine());
        Queue<char> queue = new Queue<char>();
        Dictionary<char, int> count = new Dictionary<char, int>();
        int kinds = 0; // 当前队列中不同种类数量

        for (int i = 0; i < q; i++)
        {
            string[] parts = Console.ReadLine().Split();
            if (parts[0] == "1")
            {
                char c = parts[1][0];
                queue.Enqueue(c);
                if (!count.ContainsKey(c) || count[c] == 0) kinds++;
                count[c] = count.ContainsKey(c) ? count[c] + 1 : 1;
            }
            else if (parts[0] == "2")
            {
                char c = queue.Dequeue();
                count[c]--;
                if (count[c] == 0) kinds--;
            }
            else
            {
                Console.WriteLine(kinds);
            }
        }
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    queue<char> que;
    unordered_map<char, int> cnt;
    int kinds = 0; // 当前队列中不同种类数量

    while (q--) {
        char op;
        cin >> op;
        if (op == '1') {
            char c;
            cin >> c;
            que.push(c);
            if (cnt[c] == 0) kinds++;
            cnt[c]++;
        } else if (op == '2') {
            char c = que.front();
            que.pop();
            cnt[c]--;
            if (cnt[c] == 0) kinds--;
        } else {
            cout << kinds << '\n';
        }
    }
    return 0;
}

2. 跳石头得分

难度感：easy-medium

题目

有 n 段石头距离和最大跳跃距离 m，随后给出每种跳跃距离最多可使用次数。从 0 号石头开始按顺序跳到下一个石头；若距离超过 m 或对应距离次数耗尽，则停止。每成功跳一次得 30 分，输出最终得分。

题解

• 题目要求按顺序跳，不需要搜索最优路径。
• 用数组记录每种距离剩余可用次数。
• 从左到右模拟，遇到跳不了的情况立即结束。

复杂度：O(n + m) 时间，O(m) 空间。

C# 答案

using System;

public class MainClass
{
    public static void Main()
    {
        string[] first = Console.ReadLine().Split();
        int n = int.Parse(first[0]);
        int maxStep = int.Parse(first[1]);

        int[] dist = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int[] limit = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        int score = 0;
        for (int i = 0; i < n; i++)
        {
            int d = dist[i];
            if (d > maxStep || limit[d - 1] == 0) break;

            limit[d - 1]--; // 使用一次距离 d 的跳跃
            score += 30;
        }

        Console.WriteLine(score);
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, maxStep;
    cin >> n >> maxStep;
    vector<int> dist(n);
    for (int i = 0; i < n; ++i) cin >> dist[i];

    vector<int> limit(maxStep + 1);
    for (int d = 1; d <= maxStep; ++d) cin >> limit[d];

    int score = 0;
    for (int d : dist) {
        if (d > maxStep || limit[d] == 0) break;
        limit[d]--;      // 使用一次距离 d 的跳跃
        score += 30;
    }

    cout << score << '\n';
    return 0;
}

---

3. 树中统计 abb 模式路径

难度感：medium

题目

给一棵 n 个节点的无向树，每个节点有一个小写字母。统计长度为 2 的有序路径 (x, y, z)，要求 x 与 y 相邻，y 与 z 相邻，x != z，并且 label[x] != label[y]、label[y] == label[z]。

题解

• 把中间点 y 固定住，路径只由它的两个不同邻居组成。
• 统计 same：邻居中字母等于 label[y] 的数量；diff：邻居中字母不等于 label[y] 的数量。
• 以 y 为中点的合法有序路径数量就是 same * diff。

复杂度：O(n) 时间，O(n) 空间。

C# 答案

using System;
using System.Collections.Generic;

public class MainClass
{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        string labels = Console.ReadLine().Trim();
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();

        for (int i = 0; i < n - 1; i++)
        {
            int[] e = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int a = e[0] - 1, b = e[1] - 1;
            graph[a].Add(b);
            graph[b].Add(a);
        }

        long ans = 0;
        for (int y = 0; y < n; y++)
        {
            long same = 0, diff = 0;
            foreach (int nb in graph[y])
            {
                if (labels[nb] == labels[y]) same++;
                else diff++;
            }
            ans += same * diff; // x 选异字母邻居，z 选同字母邻居
        }

        Console.WriteLine(ans);
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    long long ans = 0;
    for (int y = 0; y < n; ++y) {
        long long same = 0, diff = 0;
        for (int nb : g[y]) {
            if (s[nb] == s[y]) same++;
            else diff++;
        }
        ans += same * diff; // 有序路径：异字母邻居 -> y -> 同字母邻居
    }
    cout << ans << '\n';
    return 0;
}

---

4. 英语复述计分

难度感：easy

题目

有 t 次测试。每次测试给出老师说的 n 个单词和学生复述的 n 个单词。同位置单词相同得 1 分，否则扣 1 分；若过程中分数低于 0，本次测试失败。统计通过次数。

题解

• 逐场测试模拟分数变化。
• 一旦分数低于 0，可以提前结束当前测试。
• 没有跌破 0 的场次计入答案。

复杂度：O(总单词数) 时间，O(n) 空间。

C# 答案

using System;

public class MainClass
{
    public static void Main()
    {
        int t = int.Parse(Console.ReadLine());
        int pass = 0;

        for (int round = 0; round < t; round++)
        {
            int n = int.Parse(Console.ReadLine());
            string[] a = Console.ReadLine().Split();
            string[] b = Console.ReadLine().Split();

            int score = 0;
            bool ok = true;
            for (int i = 0; i < n; i++)
            {
                score += a[i] == b[i] ? 1 : -1;
                if (score < 0)
                {
                    ok = false;
                    break;
                }
            }

            if (ok) pass++;
        }

        Console.WriteLine(pass);
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    int pass = 0;
    while (t--) {
        int n;
        cin >> n;
        vector<string> a(n), b(n);
        for (string &x : a) cin >> x;
        for (string &x : b) cin >> x;

        int score = 0;
        bool ok = true;
        for (int i = 0; i < n; ++i) {
            score += (a[i] == b[i]) ? 1 : -1;
            if (score < 0) {
                ok = false;
                break;
            }
        }
        if (ok) pass++;
    }
    cout << pass << '\n';
    return 0;
}

---

5. 怪物攻击与 AOE 触发

难度感：medium

题目

有 n 个怪物，血量为 hp[i]。单次普通攻击只能对一个怪物造成 1 点伤害。每个怪物第一次血量降到初始血量一半及以下时，会触发一次 AOE，对所有怪物造成 1 点伤害。求击杀所有怪物的最少普通攻击次数。

题解

• AOE 触发次数越多越好，因为一次触发会给所有怪物减血。
• 血量特别高的怪物必须主动打到触发线，先处理高血量怪物可以保证它们也贡献 AOE。
• 其余怪物按血量从小到大处理，避免低血量怪被其他 AOE 直接打死而浪费触发机会。

复杂度：排序 O(n log n)，额外空间 O(1) 到 O(n)。

C# 答案

using System;

public class MainClass
{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int[] hp = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        Array.Sort(hp);

        long attacks = 0;
        int triggered = 0;     // 已经触发过的 AOE 次数
        int right = n - 1;

        // 血量 >= 2n 的怪，即使吃满其他 AOE，也需要主动处理。
        while (right >= 0 && hp[right] >= 2 * n)
        {
            attacks += hp[right] - n;
            triggered++;
            right--;
        }

        for (int i = 0; i <= right; i++)
        {
            int original = hp[i];
            int cur = original - triggered; // 已经吃过前面 AOE 后的当前血量

            if (cur > original / 2)
            {
                attacks += cur - original / 2; // 打到触发线
                cur = original / 2;
            }

            int futureAoe = n - triggered;     // 后续还能吃到的 AOE 数
            if (cur > futureAoe) attacks += cur - futureAoe;
            triggered++;
        }

        Console.WriteLine(attacks);
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> hp(n);
    for (int &x : hp) cin >> x;
    sort(hp.begin(), hp.end());

    long long attacks = 0;
    int triggered = 0; // 已经触发过的 AOE 次数
    int right = n - 1;

    // 血量特别高的怪必须主动打，先让它们触发 AOE。
    while (right >= 0 && hp[right] >= 2 * n) {
        attacks += hp[right] - n;
        triggered++;
        right--;
    }

    for (int i = 0; i <= right; ++i) {
        int original = hp[i];
        int cur = original - triggered;

        if (cur > original / 2) {
            attacks += cur - original / 2; // 打到一半触发线
            cur = original / 2;
        }

        int futureAoe = n - triggered;
        if (cur > futureAoe) attacks += cur - futureAoe;
        triggered++;
    }

    cout << attacks << '\n';
    return 0;
}

---

6. 裁剪嫁接树的最小丑陋值

难度感：medium-hard

题目

一棵以 1 为根的树，每个节点有权值 w[i]，整棵树的丑陋值为 sum(depth[i] * w[i])。允许裁剪一次某个子树并把它嫁接到根节点下，求最小丑陋值。

题解

• 一次 DFS 计算每个节点深度、子树权值和、子树当前贡献。
• 把节点 u 的子树嫁接到根下后，子树内所有节点深度都会减少 depth[u] - 2。
• 因此总丑陋值可减少 (depth[u] - 2) * subtreeSum[u]，枚举 u 取最大减少量。

复杂度：O(n) 时间，O(n) 空间。

C# 答案

using System;
using System.Collections.Generic;

public class MainClass
{
    static List<int>[] g;
    static long[] w, sub;
    static int[] depth;
    static long total = 0;

    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        w = new long[n + 1];
        string[] ws = Console.ReadLine().Split();
        for (int i = 1; i <= n; i++) w[i] = long.Parse(ws[i - 1]);

        g = new List<int>[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new List<int>();
        for (int i = 0; i < n - 1; i++)
        {
            int[] e = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            g[e[0]].Add(e[1]);
            g[e[1]].Add(e[0]);
        }

        sub = new long[n + 1];
        depth = new int[n + 1];
        Dfs(1, 0, 1);

        long bestReduce = 0;
        for (int u = 2; u <= n; u++)
        {
            long reduce = Math.Max(0, depth[u] - 2) * sub[u];
            if (reduce > bestReduce) bestReduce = reduce;
        }

        Console.WriteLine(total - bestReduce);
    }

    static void Dfs(int u, int parent, int dep)
    {
        depth[u] = dep;
        sub[u] = w[u];
        total += w[u] * dep;

        foreach (int v in g[u])
        {
            if (v == parent) continue;
            Dfs(v, u, dep + 1);
            sub[u] += sub[v];
        }
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g;
vector<long long> w, sub;
vector<int> depth;
long long total = 0;

void dfs(int u, int parent, int dep) {
    depth[u] = dep;
    sub[u] = w[u];
    total += w[u] * dep;

    for (int v : g[u]) {
        if (v == parent) continue;
        dfs(v, u, dep + 1);
        sub[u] += sub[v];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    g.assign(n + 1, {});
    w.assign(n + 1, 0);
    sub.assign(n + 1, 0);
    depth.assign(n + 1, 0);

    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0, 1);

    long long bestReduce = 0;
    for (int u = 2; u <= n; ++u) {
        long long reduce = max(0, depth[u] - 2) * sub[u];
        bestReduce = max(bestReduce, reduce);
    }

    cout << total - bestReduce << '\n';
    return 0;
}

---

7. 青蛙跳台阶

难度感：easy

题目

一只青蛙一次可以跳 1 级或 2 级台阶，问跳到第 n 级共有多少种跳法。

题解

• 最后一步可能从 n-1 跳 1 级，也可能从 n-2 跳 2 级。
• 所以 dp[n] = dp[n-1] + dp[n-2]。
• 只需要保存前两个状态即可。

复杂度：O(n) 时间，O(1) 空间。

C# 答案

public class Solution
{
    public int NumWays(int n)
    {
        if (n <= 1) return 1;

        int prev2 = 1; // dp[0]
        int prev1 = 1; // dp[1]
        for (int i = 2; i <= n; i++)
        {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

C++ 答案

class Solution {
public:
    int numWays(int n) {
        if (n <= 1) return 1;

        int prev2 = 1; // dp[0]
        int prev1 = 1; // dp[1]
        for (int i = 2; i <= n; ++i) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

---

8. 两个队列实现栈

难度感：medium

题目

用两个队列实现一个后进先出的栈，支持 Push、Pop、Top、Empty。

题解

• 队列是先进先出，栈是后进先出。
• 每次入栈后，把旧队列元素依次搬到新元素后面，使主队列队头永远是栈顶。
• 这样 Pop 和 Top 都可以 O(1)。

复杂度：Push O(n)，Pop/Top O(1)，空间 O(n)。

C# 答案

using System.Collections.Generic;

public class MyStack
{
    private Queue<int> q = new Queue<int>();

    public void Push(int x)
    {
        Queue<int> temp = new Queue<int>();
        temp.Enqueue(x); // 新元素应成为栈顶

        while (q.Count > 0)
        {
            temp.Enqueue(q.Dequeue());
        }

        q = temp;
    }

    public int Pop()
    {
        return q.Dequeue();
    }

    public int Top()
    {
        return q.Peek();
    }

    public bool Empty()
    {
        return q.Count == 0;
    }
}

C++ 答案

#include <queue>
using namespace std;

class MyStack {
    queue<int> q;

public:
    void push(int x) {
        queue<int> temp;
        temp.push(x); // 新元素应成为栈顶

        while (!q.empty()) {
            temp.push(q.front());
            q.pop();
        }

        q.swap(temp);
    }

    int pop() {
        int x = q.front();
        q.pop();
        return x;
    }

    int top() {
        return q.front();
    }

    bool empty() {
        return q.empty();
    }
};

---

9. 找到所有数组中消失的数字

难度感：medium

题目

给定长度为 n 的数组 nums，其中元素范围是 1..n。有些数字出现两次，有些数字没有出现。要求 O(n) 时间、O(1) 额外空间找出所有没出现的数字。

题解

• 利用数字范围 1..n，把值映射到下标 value - 1。
• 遍历数组时，把出现过的数字对应位置标成负数。
• 最后仍为正数的位置 i，说明数字 i + 1 没出现。

复杂度：O(n) 时间，除了答案外 O(1) 空间。

C# 答案

using System;
using System.Collections.Generic;

public class Solution
{
    public IList<int> FindDisappearedNumbers(int[] nums)
    {
        for (int i = 0; i < nums.Length; i++)
        {
            int index = Math.Abs(nums[i]) - 1;
            if (nums[index] > 0)
            {
                nums[index] = -nums[index]; // 标记这个数字出现过
            }
        }

        List<int> ans = new List<int>();
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] > 0) ans.Add(i + 1);
        }
        return ans;
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (int x : nums) {
            int idx = abs(x) - 1;
            if (nums[idx] > 0) nums[idx] = -nums[idx]; // 标记出现过
        }

        vector<int> ans;
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (nums[i] > 0) ans.push_back(i + 1);
        }
        return ans;
    }
};

---

10. 无序数组找中位数 / 第 k 小

难度感：medium

题目

给定无序数组，要求找到第 k 小的数；当 k=(n+1)/2 时就是中位数。

题解

• 排序可以做，但时间复杂度是 O(n log n)。
• 更好的方法是快速选择：每次 partition 后，只递归包含第 k 个元素的一侧。
• 平均 O(n)，最坏 O(n^2)，可以随机选 pivot 降低风险。

复杂度：平均 O(n) 时间，O(1) 额外空间。

C# 答案

using System;

public class Solution
{
    private Random rand = new Random();

    public int KthSmallest(int[] nums, int k)
    {
        int target = k - 1; // 第 k 小对应 0-based 下标 k-1
        int left = 0, right = nums.Length - 1;

        while (left <= right)
        {
            int pivotIndex = Partition(nums, left, right);
            if (pivotIndex == target) return nums[pivotIndex];
            if (pivotIndex < target) left = pivotIndex + 1;
            else right = pivotIndex - 1;
        }
        return -1;
    }

    private int Partition(int[] a, int left, int right)
    {
        int p = rand.Next(left, right + 1);
        Swap(a, p, right);
        int pivot = a[right];
        int store = left;

        for (int i = left; i < right; i++)
        {
            if (a[i] < pivot)
            {
                Swap(a, store, i);
                store++;
            }
        }

        Swap(a, store, right);
        return store;
    }

    private void Swap(int[] a, int i, int j)
    {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int kthSmallest(vector<int>& nums, int k) {
        int target = k - 1; // 第 k 小对应 0-based 下标
        int left = 0, right = (int)nums.size() - 1;

        while (left <= right) {
            int idx = partition(nums, left, right);
            if (idx == target) return nums[idx];
            if (idx < target) left = idx + 1;
            else right = idx - 1;
        }
        return -1;
    }

private:
    int partition(vector<int>& a, int left, int right) {
        int p = left + rand() % (right - left + 1);
        swap(a[p], a[right]);
        int pivot = a[right];
        int store = left;

        for (int i = left; i < right; ++i) {
            if (a[i] < pivot) {
                swap(a[store], a[i]);
                store++;
            }
        }

        swap(a[store], a[right]);
        return store;
    }
};

---

11. 手写循环队列

难度感：easy-medium

题目

实现固定容量循环队列，支持 EnQueue、DeQueue、Front、IsEmpty、IsFull。

题解

• 用数组存储元素，head 指向队头，tail 指向下一个可写位置。
• 维护 size 可以最简单地区分空和满。
• 下标移动用 (index + 1) % capacity 实现循环。

复杂度：所有操作 O(1)，空间 O(k)。

C# 答案

public class MyCircularQueue
{
    private int[] data;
    private int head = 0;
    private int tail = 0;
    private int size = 0;

    public MyCircularQueue(int k)
    {
        data = new int[k];
    }

    public bool EnQueue(int value)
    {
        if (IsFull()) return false;
        data[tail] = value;
        tail = (tail + 1) % data.Length;
        size++;
        return true;
    }

    public bool DeQueue()
    {
        if (IsEmpty()) return false;
        head = (head + 1) % data.Length;
        size--;
        return true;
    }

    public int Front()
    {
        return IsEmpty() ? -1 : data[head];
    }

    public bool IsEmpty() { return size == 0; }
    public bool IsFull() { return size == data.Length; }
}

C++ 答案

#include <vector>
using namespace std;

class MyCircularQueue {
    vector<int> data;
    int head = 0, tail = 0, sz = 0;

public:
    MyCircularQueue(int k) : data(k) {}

    bool enQueue(int value) {
        if (isFull()) return false;
        data[tail] = value;
        tail = (tail + 1) % data.size();
        sz++;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % data.size();
        sz--;
        return true;
    }

    int Front() {
        return isEmpty() ? -1 : data[head];
    }

    bool isEmpty() { return sz == 0; }
    bool isFull() { return sz == (int)data.size(); }
};