网易雷火

27. 单链表添加和删除

难度感：easy

题目

实现一个简单单链表，支持在头部添加元素，并删除第一个值等于 value 的节点。

题解

• 头部删除是链表题最容易出边界的地方。
• 使用虚拟头节点可以统一删除头节点和中间节点。
• 遍历时检查 cur.Next，找到目标后改指针跳过它。

复杂度：添加头节点 O(1)，删除 O(n)，空间 O(1)。

C# 答案

public class Node
{
    public int Val;
    public Node Next;
    public Node(int val) { Val = val; }
}

public class MyList
{
    public Node Head;

    public void AddFirst(int val)
    {
        Node node = new Node(val);
        node.Next = Head;
        Head = node;
    }

    public void DeleteFirst(int val)
    {
        Node dummy = new Node(0);
        dummy.Next = Head;
        Node cur = dummy;

        while (cur.Next != null)
        {
            if (cur.Next.Val == val)
            {
                cur.Next = cur.Next.Next;
                break;
            }
            cur = cur.Next;
        }

        Head = dummy.Next;
    }
}

C++ 答案

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

class MyList {
public:
    Node* head = nullptr;

    void addFirst(int val) {
        Node* node = new Node(val);
        node->next = head;
        head = node;
    }

    void deleteFirst(int val) {
        Node dummy(0);
        dummy.next = head;
        Node* cur = &dummy;

        while (cur->next) {
            if (cur->next->val == val) {
                Node* removed = cur->next;
                cur->next = removed->next;
                delete removed;
                break;
            }
            cur = cur->next;
        }

        head = dummy.next;
    }
};

---

28. 有序数组去重

难度感：easy

题目

给定升序数组，原地删除重复元素，使每个元素只出现一次，返回去重后的长度。

题解

• 有序数组的重复元素必然相邻。
• 用慢指针 slow 指向已去重区域最后一个位置。
• 快指针遇到新值时，把它写到 slow+1。

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

C# 答案

public class Solution
{
    public int RemoveDuplicates(int[] nums)
    {
        if (nums.Length == 0) return 0;

        int slow = 0;
        for (int fast = 1; fast < nums.Length; fast++)
        {
            if (nums[fast] != nums[slow])
            {
                slow++;
                nums[slow] = nums[fast];
            }
        }

        return slow + 1;
    }
}

C++ 答案

#include <vector>
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;

        int slow = 0;
        for (int fast = 1; fast < (int)nums.size(); ++fast) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;
    }
};

---

29. TopK：堆版与快选版

难度感：medium

题目

给定数组和整数 k，返回最大的 k 个元素。要求能讲出小顶堆版和快速选择版。

题解

• 小顶堆版更稳：维护大小为 k 的小顶堆，时间 O(n log k)。
• 快选版平均更快：把第 n-k 小元素放到正确位置，右侧就是 TopK。
• 技术交流中要主动说清楚两者复杂度和稳定性差异。

复杂度：堆版 O(n log k)；快选平均 O(n)。

C# 答案

using System;
using System.Collections.Generic;

public class Solution
{
    // 这里给堆版，现场最稳。
    public List<int> TopK(int[] nums, int k)
    {
        SortedDictionary<int, int> heap = new SortedDictionary<int, int>();
        int size = 0;

        foreach (int x in nums)
        {
            heap[x] = heap.ContainsKey(x) ? heap[x] + 1 : 1;
            size++;
            if (size > k)
            {
                int min = FirstKey(heap);
                if (--heap[min] == 0) heap.Remove(min);
                size--;
            }
        }

        List<int> ans = new List<int>();
        foreach (var kv in heap)
            for (int i = 0; i < kv.Value; i++)
                ans.Add(kv.Key);
        return ans;
    }

    private int FirstKey(SortedDictionary<int, int> map)
    {
        foreach (var kv in map) return kv.Key;
        return -1;
    }
}

C++ 答案

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

class Solution {
public:
    vector<int> topK(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
        for (int x : nums) {
            pq.push(x);
            if ((int)pq.size() > k) pq.pop();
        }

        vector<int> ans;
        while (!pq.empty()) {
            ans.push_back(pq.top());
            pq.pop();
        }
        return ans;
    }
};

---

30. 大指数 a^n 的个位数

难度感：medium

题目

给定非负整数 a 和可能非常大的十进制字符串 n，求 a^n 的个位数。

题解

• 个位数只与 a 的个位有关。
• 任意数字幂的个位变化周期最多为 4。
• 把大指数 n 对周期取模即可；注意余数为 0 时取周期最后一项。

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

C# 答案

using System.Collections.Generic;

public class Solution
{
    public int LastDigit(int a, string n)
    {
        if (n == "0") return 1;

        int baseDigit = a % 10;
        List<int> cycle = new List<int>();
        int cur = baseDigit;

        while (!cycle.Contains(cur))
        {
            cycle.Add(cur);
            cur = (cur * baseDigit) % 10;
        }

        int mod = 0;
        foreach (char ch in n)
        {
            mod = (mod * 10 + (ch - '0')) % cycle.Count;
        }

        int index = mod == 0 ? cycle.Count - 1 : mod - 1;
        return cycle[index];
    }
}

C++ 答案

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

class Solution {
public:
    int lastDigit(int a, const string& n) {
        if (n == "0") return 1;

        int base = a % 10;
        vector<int> cycle;
        int cur = base;
        while (find(cycle.begin(), cycle.end(), cur) == cycle.end()) {
            cycle.push_back(cur);
            cur = cur * base % 10;
        }

        int mod = 0;
        for (char ch : n) {
            mod = (mod * 10 + ch - '0') % cycle.size();
        }

        int idx = (mod == 0) ? (int)cycle.size() - 1 : mod - 1;
        return cycle[idx];
    }
};

---

31. 快速幂

难度感：medium

题目

实现 pow(a, n)，支持大指数；可带模数 mod，返回 a^n % mod。

题解

• 把指数按二进制拆分。
• 当前位为 1 时，把当前底数乘进答案。
• 每轮底数平方，指数右移一位。

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

C# 答案

public class Solution
{
    public long FastPow(long a, long n, long mod)
    {
        long ans = 1 % mod;
        a %= mod;

        while (n > 0)
        {
            if ((n & 1) == 1)
            {
                ans = ans * a % mod;
            }
            a = a * a % mod;
            n >>= 1;
        }

        return ans;
    }
}

C++ 答案

class Solution {
public:
    long long fastPow(long long a, long long n, long long mod) {
        long long ans = 1 % mod;
        a %= mod;

        while (n > 0) {
            if (n & 1) ans = ans * a % mod;
            a = a * a % mod;
            n >>= 1;
        }

        return ans;
    }
};