Unity游戏开发者联盟

Appearance

网易互娱 ​

23. 链表判环 ​

难度感：easy-medium

题目 ​

给定单链表头节点，判断链表中是否存在环。

题解 ​

  • 快慢指针是最经典做法。
  • 慢指针每次走一步，快指针每次走两步。
  • 如果有环，快指针一定会在环内追上慢指针；如果无环，快指针会先到空。

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

题目图示

C# 答案 ​

csharp
public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public class Solution
{
    public bool HasCycle(ListNode head)
    {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }

        return false;
    }
}

C++ 答案 ​

cpp
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }

        return false;
    }
};

24. 找数组的三等分点 ​

难度感：medium

题目 ​

给定整数数组，判断能否切成三个非空连续部分，使三部分元素和相等；若可以，返回两个切分点下标，否则返回 [-1, -1]。

题解 ​

  • 总和必须能被 3 整除。
  • 从左到右找第一次前缀和为 sum/3 的位置作为第一刀。
  • 继续向右找前缀和为 2*sum/3 的位置作为第二刀，并保证右侧非空。

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

题目图示

C# 答案 ​

csharp
public class Solution
{
    public int[] ThreeSplit(int[] nums)
    {
        long sum = 0;
        foreach (int x in nums) sum += x;
        if (sum % 3 != 0) return new[] { -1, -1 };

        long one = sum / 3;
        long two = one * 2;
        long prefix = 0;
        int first = -1;

        for (int i = 0; i < nums.Length - 1; i++)
        {
            prefix += nums[i];
            if (first == -1 && prefix == one)
            {
                first = i;
            }
            else if (first != -1 && prefix == two)
            {
                return new[] { first, i };
            }
        }

        return new[] { -1, -1 };
    }
}

C++ 答案 ​

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

class Solution {
public:
    vector<int> threeSplit(vector<int>& nums) {
        long long sum = accumulate(nums.begin(), nums.end(), 0LL);
        if (sum % 3 != 0) return {-1, -1};

        long long one = sum / 3, two = one * 2;
        long long prefix = 0;
        int first = -1;

        for (int i = 0; i < (int)nums.size() - 1; ++i) {
            prefix += nums[i];
            if (first == -1 && prefix == one) {
                first = i;
            } else if (first != -1 && prefix == two) {
                return {first, i};
            }
        }
        return {-1, -1};
    }
};

25. 多个图形放入正方形的最小边长 ​

难度感：hard

说明：原样本没有完整题面，这里给的是同类考察点的可练版本：二分答案 + 几何可行性检查。

题目 ​

复原练习题：给定若干矩形的宽高，可以旋转 90 度。使用“按行摆放”的规则，判断是否能放入边长为 x 的正方形；求最小可行 x。

题解 ​

  • 原回忆只给出大意，这里抽象成常见的二分答案 + 可行性检查。
  • 如果边长 x 可行，那么更大的边长一定可行，满足单调性。
  • 可行性检查时按行贪心摆放：当前行放不下就换行。

复杂度：O(n log S) 时间，O(1) 额外空间，S 为答案范围。

题目图示

C# 答案 ​

csharp
using System;

public class Solution
{
    public int MinSquareSide(int[][] rects)
    {
        int left = 0, right = 0;
        foreach (var r in rects)
        {
            left = Math.Max(left, Math.Min(r[0], r[1]));
            right += Math.Max(r[0], r[1]);
        }

        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (CanPlace(rects, mid)) right = mid;
            else left = mid + 1;
        }

        return left;
    }

    private bool CanPlace(int[][] rects, int side)
    {
        int usedH = 0, rowW = 0, rowH = 0;

        foreach (var r in rects)
        {
            int w = r[0], h = r[1];
            if (w > side && h > side) return false;
            if (w > side || (h <= side && h < w))
            {
                int t = w; w = h; h = t; // 尽量让宽能放进当前边长
            }

            if (rowW + w > side)
            {
                usedH += rowH;
                rowW = 0;
                rowH = 0;
            }

            rowW += w;
            rowH = Math.Max(rowH, h);
            if (usedH + rowH > side) return false;
        }
        return true;
    }
}

C++ 答案 ​

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

class Solution {
public:
    int minSquareSide(vector<vector<int>>& rects) {
        int left = 0, right = 0;
        for (auto& r : rects) {
            left = max(left, min(r[0], r[1]));
            right += max(r[0], r[1]);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canPlace(rects, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

private:
    bool canPlace(vector<vector<int>>& rects, int side) {
        int usedH = 0, rowW = 0, rowH = 0;
        for (auto r : rects) {
            int w = r[0], h = r[1];
            if (w > side && h > side) return false;
            if (w > side || (h <= side && h < w)) swap(w, h);

            if (rowW + w > side) {
                usedH += rowH;
                rowW = 0;
                rowH = 0;
            }

            rowW += w;
            rowH = max(rowH, h);
            if (usedH + rowH > side) return false;
        }
        return true;
    }
};

26. 多个 UI Tag 的点击与重叠检测 ​

难度感：medium-hard

说明：原样本是场景追问，这里给的是客户端常用的空间哈希版本；四叉树/kd-tree 也是同一类优化思路。

题目 ​

复原练习题：屏幕上有若干矩形 UI tag，给定点击点 (x,y)，返回命中的最高层 tag；同时支持查询哪些 tag 与某个 tag 的矩形重叠。

题解 ​

  • 少量 tag 可以直接遍历，数量大时要用空间索引。
  • 这里用统一网格哈希：把矩形登记到覆盖的网格桶里。
  • 点击时只查所在桶；重叠检测时只查目标矩形覆盖的桶，并用精确矩形相交过滤。

复杂度：设单个查询候选数为 c，查询约 O(c)；建表与矩形覆盖格子数有关。

题目图示

C# 答案 ​

csharp
using System;
using System.Collections.Generic;

public class SpatialTags
{
    public struct Rect
    {
        public int Id, X1, Y1, X2, Y2, Z;
        public bool Contains(int x, int y) { return X1 <= x && x <= X2 && Y1 <= y && y <= Y2; }
    }

    private int cell;
    private List<Rect> rects = new List<Rect>();
    private Dictionary<string, List<int>> buckets = new Dictionary<string, List<int>>();

    public SpatialTags(int cellSize) { cell = cellSize; }

    public void Add(Rect r)
    {
        int index = rects.Count;
        rects.Add(r);
        for (int gx = r.X1 / cell; gx <= r.X2 / cell; gx++)
            for (int gy = r.Y1 / cell; gy <= r.Y2 / cell; gy++)
                AddToBucket(gx + "," + gy, index);
    }

    public int HitTest(int x, int y)
    {
        string key = (x / cell) + "," + (y / cell);
        if (!buckets.ContainsKey(key)) return -1;

        int bestId = -1, bestZ = int.MinValue;
        foreach (int idx in buckets[key])
        {
            Rect r = rects[idx];
            if (r.Contains(x, y) && r.Z > bestZ)
            {
                bestZ = r.Z;
                bestId = r.Id;
            }
        }
        return bestId;
    }

    private void AddToBucket(string key, int index)
    {
        if (!buckets.ContainsKey(key)) buckets[key] = new List<int>();
        buckets[key].Add(index);
    }
}

C++ 答案 ​

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

class SpatialTags {
    struct Rect {
        int id, x1, y1, x2, y2, z;
        bool contains(int x, int y) const {
            return x1 <= x && x <= x2 && y1 <= y && y <= y2;
        }
    };

    int cell;
    vector<Rect> rects;
    unordered_map<string, vector<int>> buckets;

public:
    SpatialTags(int cellSize) : cell(cellSize) {}

    void add(int id, int x1, int y1, int x2, int y2, int z) {
        Rect r{id, x1, y1, x2, y2, z};
        int idx = rects.size();
        rects.push_back(r);
        for (int gx = x1 / cell; gx <= x2 / cell; ++gx) {
            for (int gy = y1 / cell; gy <= y2 / cell; ++gy) {
                buckets[key(gx, gy)].push_back(idx);
            }
        }
    }

    int hitTest(int x, int y) {
        string k = key(x / cell, y / cell);
        if (!buckets.count(k)) return -1;

        int bestId = -1, bestZ = INT_MIN;
        for (int idx : buckets[k]) {
            const Rect& r = rects[idx];
            if (r.contains(x, y) && r.z > bestZ) {
                bestZ = r.z;
                bestId = r.id;
            }
        }
        return bestId;
    }

private:
    string key(int gx, int gy) {
        return to_string(gx) + "," + to_string(gy);
    }
};

文章评价

读完这篇，留下你的看法

暂无审核通过的评价。

登录账号后才能评价。

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