Unity游戏开发者联盟

Appearance

快手游戏 ​

32. 输出目标串对应于源串的索引 ​

难度感：easy-medium

题目 ​

给定源串 source 和目标串 target，判断 target 是否是 source 的子序列；如果是，输出目标串每个字符在源串中匹配到的下标，否则返回空数组。

题解 ​

  • 用双指针从左到右匹配。
  • 源串指针每次前进；当字符相同，记录当前下标并移动目标串指针。
  • 目标串匹配完则成功。

复杂度：O(n) 时间，O(m) 空间，m 是目标串长度。

题目图示

C# 答案 ​

csharp
using System.Collections.Generic;

public class Solution
{
    public List<int> MatchIndices(string source, string target)
    {
        List<int> ans = new List<int>();
        int j = 0;

        for (int i = 0; i < source.Length && j < target.Length; i++)
        {
            if (source[i] == target[j])
            {
                ans.Add(i);
                j++;
            }
        }

        return j == target.Length ? ans : new List<int>();
    }
}

C++ 答案 ​

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

class Solution {
public:
    vector<int> matchIndices(const string& source, const string& target) {
        vector<int> ans;
        int j = 0;
        for (int i = 0; i < (int)source.size() && j < (int)target.size(); ++i) {
            if (source[i] == target[j]) {
                ans.push_back(i);
                j++;
            }
        }
        if (j != (int)target.size()) return {};
        return ans;
    }
};

33. KMP 的 next 数组和字符串匹配 ​

难度感：medium

题目 ​

实现 KMP，返回模式串 pattern 在文本串 text 中第一次出现的位置；不存在返回 -1。

题解 ​

  • next[i] 表示 pattern[0..i] 的最长相等真前后缀长度。
  • 匹配失败时，模式串不用回到开头，而是跳到 next[j-1]。
  • 文本指针永不回退，所以整体线性。

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

题目图示

C# 答案 ​

csharp
public class Solution
{
    public int StrStr(string text, string pattern)
    {
        if (pattern.Length == 0) return 0;
        int[] next = BuildNext(pattern);
        int j = 0;

        for (int i = 0; i < text.Length; i++)
        {
            while (j > 0 && text[i] != pattern[j]) j = next[j - 1];
            if (text[i] == pattern[j]) j++;
            if (j == pattern.Length) return i - pattern.Length + 1;
        }

        return -1;
    }

    private int[] BuildNext(string p)
    {
        int[] next = new int[p.Length];
        int j = 0;
        for (int i = 1; i < p.Length; i++)
        {
            while (j > 0 && p[i] != p[j]) j = next[j - 1];
            if (p[i] == p[j]) j++;
            next[i] = j;
        }
        return next;
    }
}

C++ 答案 ​

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

class Solution {
public:
    int strStr(const string& text, const string& pattern) {
        if (pattern.empty()) return 0;
        vector<int> nxt = buildNext(pattern);
        int j = 0;

        for (int i = 0; i < (int)text.size(); ++i) {
            while (j > 0 && text[i] != pattern[j]) j = nxt[j - 1];
            if (text[i] == pattern[j]) j++;
            if (j == (int)pattern.size()) return i - pattern.size() + 1;
        }
        return -1;
    }

private:
    vector<int> buildNext(const string& p) {
        vector<int> nxt(p.size());
        int j = 0;
        for (int i = 1; i < (int)p.size(); ++i) {
            while (j > 0 && p[i] != p[j]) j = nxt[j - 1];
            if (p[i] == p[j]) j++;
            nxt[i] = j;
        }
        return nxt;
    }
};

34. 屏蔽字匹配：AC 自动机 ​

难度感：medium-hard

题目 ​

给定一批屏蔽词和一段文本，判断文本中是否出现任意屏蔽词。

题解 ​

  • 多个模式串同时匹配，逐个 KMP 会浪费。
  • Trie 负责共享前缀，fail 指针负责失配跳转。
  • AC 自动机扫描文本时，每个字符只推动一次状态转移。

复杂度：建机 O(总词长 * 字符集)，匹配 O(文本长度)。

题目图示

C# 答案 ​

csharp
using System.Collections.Generic;

public class ACAutomaton
{
    class Node
    {
        public int[] Next = new int[26];
        public int Fail;
        public bool End;
        public Node()
        {
            for (int i = 0; i < 26; i++) Next[i] = -1;
        }
    }

    private List<Node> nodes = new List<Node>();

    public ACAutomaton()
    {
        nodes.Add(new Node());
    }

    public void Insert(string word)
    {
        int cur = 0;
        foreach (char ch in word)
        {
            int c = ch - 'a';
            if (nodes[cur].Next[c] == -1)
            {
                nodes[cur].Next[c] = nodes.Count;
                nodes.Add(new Node());
            }
            cur = nodes[cur].Next[c];
        }
        nodes[cur].End = true;
    }

    public void Build()
    {
        Queue<int> q = new Queue<int>();
        for (int c = 0; c < 26; c++)
        {
            int v = nodes[0].Next[c];
            if (v == -1) nodes[0].Next[c] = 0;
            else q.Enqueue(v);
        }

        while (q.Count > 0)
        {
            int u = q.Dequeue();
            nodes[u].End |= nodes[nodes[u].Fail].End;
            for (int c = 0; c < 26; c++)
            {
                int v = nodes[u].Next[c];
                if (v == -1) nodes[u].Next[c] = nodes[nodes[u].Fail].Next[c];
                else
                {
                    nodes[v].Fail = nodes[nodes[u].Fail].Next[c];
                    q.Enqueue(v);
                }
            }
        }
    }

    public bool ContainsBadWord(string text)
    {
        int cur = 0;
        foreach (char ch in text)
        {
            if (ch < 'a' || ch > 'z') { cur = 0; continue; }
            cur = nodes[cur].Next[ch - 'a'];
            if (nodes[cur].End) return true;
        }
        return false;
    }
}

C++ 答案 ​

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

class ACAutomaton {
    struct Node {
        int next[26];
        int fail = 0;
        bool end = false;
        Node() { memset(next, -1, sizeof(next)); }
    };

    vector<Node> tr;

public:
    ACAutomaton() { tr.push_back(Node()); }

    void insert(const string& word) {
        int cur = 0;
        for (char ch : word) {
            int c = ch - 'a';
            if (tr[cur].next[c] == -1) {
                tr[cur].next[c] = tr.size();
                tr.push_back(Node());
            }
            cur = tr[cur].next[c];
        }
        tr[cur].end = true;
    }

    void build() {
        queue<int> q;
        for (int c = 0; c < 26; ++c) {
            int v = tr[0].next[c];
            if (v == -1) tr[0].next[c] = 0;
            else q.push(v);
        }

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            tr[u].end = tr[u].end || tr[tr[u].fail].end;
            for (int c = 0; c < 26; ++c) {
                int v = tr[u].next[c];
                if (v == -1) tr[u].next[c] = tr[tr[u].fail].next[c];
                else {
                    tr[v].fail = tr[tr[u].fail].next[c];
                    q.push(v);
                }
            }
        }
    }

    bool containsBadWord(const string& text) {
        int cur = 0;
        for (char ch : text) {
            if (ch < 'a' || ch > 'z') { cur = 0; continue; }
            cur = tr[cur].next[ch - 'a'];
            if (tr[cur].end) return true;
        }
        return false;
    }
};

35. 战力排行榜与按战力匹配玩家 ​

难度感：medium-hard

题目 ​

设计一个结构，支持添加玩家 (id, power)，删除玩家，查询与给定战力 power 最接近的玩家。

题解 ​

  • 需要按战力有序，哈希表只适合按 id 查找。
  • 用有序集合保存 (power, id)，用哈希表保存 id -> power。
  • 查询时找第一个 >= power 的元素，再比较它和前驱谁更近。

复杂度：添加/删除/查询均为 O(log n)。

题目图示

C# 答案 ​

csharp
using System;
using System.Collections.Generic;

public class MatchMaker
{
    private SortedSet<Tuple<int, int>> set = new SortedSet<Tuple<int, int>>();
    private Dictionary<int, int> powerById = new Dictionary<int, int>();

    public void Add(int id, int power)
    {
        if (powerById.ContainsKey(id)) Remove(id);
        powerById[id] = power;
        set.Add(Tuple.Create(power, id));
    }

    public void Remove(int id)
    {
        if (!powerById.ContainsKey(id)) return;
        int power = powerById[id];
        powerById.Remove(id);
        set.Remove(Tuple.Create(power, id));
    }

    public int FindClosest(int power)
    {
        int bestId = -1;
        int bestDiff = int.MaxValue;

        // C# SortedSet 没有直接 lower_bound，这里遍历写法便于理解；
        // 工程里可用第三方有序表或自己封装红黑树/跳表。
        foreach (var item in set)
        {
            int diff = Math.Abs(item.Item1 - power);
            if (diff < bestDiff)
            {
                bestDiff = diff;
                bestId = item.Item2;
            }
            if (item.Item1 >= power) break;
        }
        return bestId;
    }
}

C++ 答案 ​

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

class MatchMaker {
    set<pair<int,int>> byPower;          // (power, id)
    unordered_map<int,int> powerById;    // id -> power

public:
    void add(int id, int power) {
        remove(id);
        powerById[id] = power;
        byPower.insert({power, id});
    }

    void remove(int id) {
        if (!powerById.count(id)) return;
        int power = powerById[id];
        powerById.erase(id);
        byPower.erase({power, id});
    }

    int findClosest(int power) {
        if (byPower.empty()) return -1;
        auto it = byPower.lower_bound({power, -1});

        int bestId = -1;
        int bestDiff = INT_MAX;
        auto relax = [&](set<pair<int,int>>::iterator p) {
            int diff = abs(p->first - power);
            if (diff < bestDiff) {
                bestDiff = diff;
                bestId = p->second;
            }
        };

        if (it != byPower.end()) relax(it);
        if (it != byPower.begin()) relax(prev(it));
        return bestId;
    }
};

36. 手写优先级队列：二叉堆 ​

难度感：medium

题目 ​

实现一个最小优先级队列，支持 Push、Pop、Peek。

题解 ​

  • 二叉堆用数组表示完全二叉树。
  • 父节点下标 (i-1)/2，左右孩子 2i+1、2i+2。
  • 插入时上浮，删除堆顶时把末尾放到堆顶再下沉。

复杂度：插入/删除 O(log n)，查看堆顶 O(1)。

题目图示

C# 答案 ​

csharp
using System.Collections.Generic;

public class MinHeap
{
    private List<int> heap = new List<int>();

    public void Push(int x)
    {
        heap.Add(x);
        SiftUp(heap.Count - 1);
    }

    public int Peek()
    {
        return heap[0];
    }

    public int Pop()
    {
        int ans = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);
        if (heap.Count > 0) SiftDown(0);
        return ans;
    }

    private void SiftUp(int i)
    {
        while (i > 0)
        {
            int p = (i - 1) / 2;
            if (heap[p] <= heap[i]) break;
            Swap(p, i);
            i = p;
        }
    }

    private void SiftDown(int i)
    {
        while (true)
        {
            int left = i * 2 + 1, right = i * 2 + 2, smallest = i;
            if (left < heap.Count && heap[left] < heap[smallest]) smallest = left;
            if (right < heap.Count && heap[right] < heap[smallest]) smallest = right;
            if (smallest == i) break;
            Swap(i, smallest);
            i = smallest;
        }
    }

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

C++ 答案 ​

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

class MinHeap {
    vector<int> heap;

public:
    void push(int x) {
        heap.push_back(x);
        siftUp(heap.size() - 1);
    }

    int peek() {
        return heap[0];
    }

    int pop() {
        int ans = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) siftDown(0);
        return ans;
    }

private:
    void siftUp(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[p] <= heap[i]) break;
            swap(heap[p], heap[i]);
            i = p;
        }
    }

    void siftDown(int i) {
        while (true) {
            int left = i * 2 + 1, right = i * 2 + 2, smallest = i;
            if (left < (int)heap.size() && heap[left] < heap[smallest]) smallest = left;
            if (right < (int)heap.size() && heap[right] < heap[smallest]) smallest = right;
            if (smallest == i) break;
            swap(heap[i], heap[smallest]);
            i = smallest;
        }
    }
};

37. 跳表 SkipList ​

难度感：medium-hard

题目 ​

实现一个简化跳表，支持 Search 和 Add。跳表常用于有序集合、排行榜、范围查询。

题解 ​

  • 跳表是多层有序链表，高层负责快速跳跃，底层保存完整数据。
  • 查找时从最高层开始，能向右就向右，不能向右就下降。
  • 插入时随机生成层高，并在每一层更新前驱指针。

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

题目图示

C# 答案 ​

csharp
using System;

public class Skiplist
{
    class Node
    {
        public int Val;
        public Node[] Next;
        public Node(int val, int level)
        {
            Val = val;
            Next = new Node[level];
        }
    }

    private const int MaxLevel = 16;
    private Node head = new Node(-1, MaxLevel);
    private Random rand = new Random();

    public bool Search(int target)
    {
        Node cur = head;
        for (int level = MaxLevel - 1; level >= 0; level--)
        {
            while (cur.Next[level] != null && cur.Next[level].Val < target)
                cur = cur.Next[level];
        }
        cur = cur.Next[0];
        return cur != null && cur.Val == target;
    }

    public void Add(int num)
    {
        Node[] update = new Node[MaxLevel];
        Node cur = head;
        for (int level = MaxLevel - 1; level >= 0; level--)
        {
            while (cur.Next[level] != null && cur.Next[level].Val < num)
                cur = cur.Next[level];
            update[level] = cur;
        }

        int lv = RandomLevel();
        Node node = new Node(num, lv);
        for (int i = 0; i < lv; i++)
        {
            node.Next[i] = update[i].Next[i];
            update[i].Next[i] = node;
        }
    }

    private int RandomLevel()
    {
        int lv = 1;
        while (lv < MaxLevel && rand.Next(2) == 0) lv++;
        return lv;
    }
}

C++ 答案 ​

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

class Skiplist {
    struct Node {
        int val;
        vector<Node*> next;
        Node(int v, int level) : val(v), next(level, nullptr) {}
    };

    static const int MAX_LEVEL = 16;
    Node* head;

public:
    Skiplist() {
        head = new Node(-1, MAX_LEVEL);
    }

    bool search(int target) {
        Node* cur = head;
        for (int level = MAX_LEVEL - 1; level >= 0; --level) {
            while (cur->next[level] && cur->next[level]->val < target)
                cur = cur->next[level];
        }
        cur = cur->next[0];
        return cur && cur->val == target;
    }

    void add(int num) {
        vector<Node*> update(MAX_LEVEL);
        Node* cur = head;
        for (int level = MAX_LEVEL - 1; level >= 0; --level) {
            while (cur->next[level] && cur->next[level]->val < num)
                cur = cur->next[level];
            update[level] = cur;
        }

        int lv = randomLevel();
        Node* node = new Node(num, lv);
        for (int i = 0; i < lv; ++i) {
            node->next[i] = update[i]->next[i];
            update[i]->next[i] = node;
        }
    }

private:
    int randomLevel() {
        int lv = 1;
        while (lv < MAX_LEVEL && (rand() & 1) == 0) lv++;
        return lv;
    }
};

38. A* 算法原理：返回路径 ​

难度感：medium

题目 ​

给定网格地图，使用 A* 从起点找到终点，并返回路径坐标列表。不可达返回空列表。

题解 ​

  • 和第 20 题的最短距离不同，这里要保存父节点用于还原路径。
  • 每次松弛邻居时记录 parent[nr,nc] = 当前格子。
  • 终点出队后，从终点沿 parent 回溯到起点，再反转。

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

题目图示

C# 答案 ​

csharp
using System;
using System.Collections.Generic;

public class Solution
{
    public List<int[]> FindPath(int[][] grid, int sr, int sc, int tr, int tc)
    {
        int m = grid.Length, n = grid[0].Length;
        int[,] dist = new int[m, n];
        int[,] pr = new int[m, n], pc = new int[m, n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                dist[i, j] = int.MaxValue;
                pr[i, j] = pc[i, j] = -1;
            }

        SortedSet<(int f, int g, int r, int c)> pq = new SortedSet<(int, int, int, int)>();
        dist[sr, sc] = 0;
        pq.Add((H(sr, sc, tr, tc), 0, sr, sc));
        int[][] dirs = { new[] {1,0}, new[] {-1,0}, new[] {0,1}, new[] {0,-1} };

        while (pq.Count > 0)
        {
            var cur = First(pq); pq.Remove(cur);
            if (cur.g != dist[cur.r, cur.c]) continue;
            if (cur.r == tr && cur.c == tc) break;

            foreach (int[] d in dirs)
            {
                int nr = cur.r + d[0], nc = cur.c + d[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] == 1) continue;
                int ng = cur.g + 1;
                if (ng < dist[nr, nc])
                {
                    dist[nr, nc] = ng;
                    pr[nr, nc] = cur.r; pc[nr, nc] = cur.c;
                    pq.Add((ng + H(nr, nc, tr, tc), ng, nr, nc));
                }
            }
        }

        if (dist[tr, tc] == int.MaxValue) return new List<int[]>();
        List<int[]> path = new List<int[]>();
        for (int r = tr, c = tc; r != -1;)
        {
            path.Add(new[] { r, c });
            int nr = pr[r, c], nc = pc[r, c];
            r = nr; c = nc;
        }
        path.Reverse();
        return path;
    }

    private int H(int r, int c, int tr, int tc) { return Math.Abs(r - tr) + Math.Abs(c - tc); }
    private (int f, int g, int r, int c) First(SortedSet<(int f, int g, int r, int c)> s) { foreach (var x in s) return x; return (0, 0, 0, 0); }
}

C++ 答案 ​

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

class Solution {
public:
    vector<pair<int,int>> findPath(vector<vector<int>>& grid, int sr, int sc, int tr, int tc) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        vector<vector<pair<int,int>>> parent(m, vector<pair<int,int>>(n, {-1, -1}));
        using Node = tuple<int,int,int,int>; // f,g,r,c
        priority_queue<Node, vector<Node>, greater<Node>> pq;
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

        dist[sr][sc] = 0;
        pq.push({h(sr, sc, tr, tc), 0, sr, sc});

        while (!pq.empty()) {
            auto [f, g, r, c] = pq.top();
            pq.pop();
            if (g != dist[r][c]) continue;
            if (r == tr && c == tc) break;

            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc]) continue;
                int ng = g + 1;
                if (ng < dist[nr][nc]) {
                    dist[nr][nc] = ng;
                    parent[nr][nc] = {r, c};
                    pq.push({ng + h(nr, nc, tr, tc), ng, nr, nc});
                }
            }
        }

        if (dist[tr][tc] == INT_MAX) return {};
        vector<pair<int,int>> path;
        for (pair<int,int> p = {tr, tc}; p.first != -1; p = parent[p.first][p.second])
            path.push_back(p);
        reverse(path.begin(), path.end());
        return path;
    }

private:
    int h(int r, int c, int tr, int tc) { return abs(r - tr) + abs(c - tc); }
};

39. 红黑树原理：用有序集合做范围查询 ​

难度感：hard

题目 ​

复原练习题：维护一组整数，支持插入、删除、查询第一个大于等于 x 的数。底层可用红黑树实现。

题解 ​

  • 红黑树是一种近似平衡的二叉搜索树，保证查找/插入/删除 O(log n)。
  • C++ 的 std::set 和 C# 的 SortedSet 都是红黑树风格的有序集合。
  • 技术环节一般更看重你能讲清性质、复杂度和使用场景，不常要求完整手写红黑树。

复杂度：插入/删除/查询 O(log n)。

题目图示

C# 答案 ​

csharp
using System.Collections.Generic;

public class OrderedSetDemo
{
    private SortedSet<int> set = new SortedSet<int>();

    public void Add(int x) { set.Add(x); }
    public void Remove(int x) { set.Remove(x); }

    public int LowerBound(int x)
    {
        // 旧版 C# SortedSet 没有直接 LowerBound；
        // 这里保留接口思想。工程中可用 GetViewBetween 或自写树。
        foreach (int v in set)
        {
            if (v >= x) return v;
        }
        return -1;
    }
}

C++ 答案 ​

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

class OrderedSetDemo {
    set<int> s; // 通常由红黑树实现

public:
    void add(int x) {
        s.insert(x);
    }

    void remove(int x) {
        s.erase(x);
    }

    int lowerBound(int x) {
        auto it = s.lower_bound(x); // 第一个 >= x 的元素
        if (it == s.end()) return -1;
        return *it;
    }
};

40. 哈希冲突：链地址法哈希表 ​

难度感：easy-medium

题目 ​

实现一个简单整数哈希集合，使用链地址法解决哈希冲突，支持 Add、Contains、Remove。

题解 ​

  • 哈希冲突是多个 key 映射到同一个桶。
  • 链地址法让每个桶挂一个链表或动态数组。
  • 查找时先定位桶，再在桶内线性查找。

复杂度：平均 O(1)，最坏 O(n)；空间 O(n + bucket)。

题目图示

C# 答案 ​

csharp
using System.Collections.Generic;

public class MyHashSet
{
    private const int BucketSize = 769;
    private List<int>[] buckets = new List<int>[BucketSize];

    public void Add(int key)
    {
        int idx = Hash(key);
        if (buckets[idx] == null) buckets[idx] = new List<int>();
        if (!buckets[idx].Contains(key)) buckets[idx].Add(key);
    }

    public void Remove(int key)
    {
        int idx = Hash(key);
        if (buckets[idx] != null) buckets[idx].Remove(key);
    }

    public bool Contains(int key)
    {
        int idx = Hash(key);
        return buckets[idx] != null && buckets[idx].Contains(key);
    }

    private int Hash(int key)
    {
        return (key % BucketSize + BucketSize) % BucketSize;
    }
}

C++ 答案 ​

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

class MyHashSet {
    static const int BUCKET = 769;
    vector<vector<int>> buckets;

public:
    MyHashSet() : buckets(BUCKET) {}

    void add(int key) {
        int idx = hash(key);
        if (!contains(key)) buckets[idx].push_back(key);
    }

    void remove(int key) {
        int idx = hash(key);
        auto& b = buckets[idx];
        b.erase(std::remove(b.begin(), b.end(), key), b.end());
    }

    bool contains(int key) {
        int idx = hash(key);
        for (int x : buckets[idx]) {
            if (x == key) return true;
        }
        return false;
    }

private:
    int hash(int key) {
        return (key % BUCKET + BUCKET) % BUCKET;
    }
};

文章评价

读完这篇，留下你的看法

暂无审核通过的评价。

登录账号后才能评价。

本站访客数0总站访问量0本页访问量0