腾讯魔方

12. 两个数组差一个元素

难度感：easy

题目

数组 A 和 B 都无序且元素不重复，A 比 B 多一个元素。要求尽量低复杂度、原地、不溢出，找出多出的元素。

题解

• 如果用求和，可能溢出。
• 异或满足 x ^ x = 0、x ^ 0 = x，相同元素会抵消。
• 把两个数组所有元素全部异或，剩下的就是多出的元素。

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

C# 答案

public class Solution
{
    public int FindExtra(int[] a, int[] b)
    {
        int ans = 0;
        foreach (int x in a) ans ^= x;
        foreach (int x in b) ans ^= x;
        return ans;
    }
}

C++ 答案

#include <vector>
using namespace std;

class Solution {
public:
    int findExtra(const vector<int>& a, const vector<int>& b) {
        int ans = 0;
        for (int x : a) ans ^= x;
        for (int x : b) ans ^= x;
        return ans;
    }
};

---

13. 数字串相邻和为 10 消除

难度感：medium

题目

给定由字符 0 到 9 组成的字符串。若相邻两个数字之和为 10，则这两个字符可以消除；消除后新的相邻字符继续判断。求最终字符串长度。

题解

• 这种“相邻消除后继续合并”的题优先想到栈。
• 遍历当前字符时，看它能否和栈顶一起消除。
• 能消除就弹栈，不能消除就入栈；最后栈大小就是剩余长度。

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

C# 答案

using System.Collections.Generic;

public class Solution
{
    public int FinalLength(string s)
    {
        Stack<int> stack = new Stack<int>();
        foreach (char ch in s)
        {
            int x = ch - '0';
            if (stack.Count > 0 && stack.Peek() + x == 10)
            {
                stack.Pop(); // 当前字符与栈顶一起消除
            }
            else
            {
                stack.Push(x);
            }
        }
        return stack.Count;
    }
}

C++ 答案

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

class Solution {
public:
    int finalLength(const string& s) {
        vector<int> st;
        for (char ch : s) {
            int x = ch - '0';
            if (!st.empty() && st.back() + x == 10) {
                st.pop_back(); // 当前字符与栈顶一起消除
            } else {
                st.push_back(x);
            }
        }
        return (int)st.size();
    }
};

---

14. 最大子数组和

难度感：easy-medium

题目

给定整数数组，找到一个连续子数组，使其元素和最大，返回最大和。

题解

• 令 cur 表示以当前位置结尾的最大子数组和。
• 如果前面的和为负，继续接上只会拖累当前数字，所以从当前数字重新开始。
• 转移：cur = max(nums[i], cur + nums[i])。

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

C# 答案

using System;

public class Solution
{
    public int MaxSubArray(int[] nums)
    {
        int cur = nums[0];
        int best = nums[0];

        for (int i = 1; i < nums.Length; i++)
        {
            cur = Math.Max(nums[i], cur + nums[i]);
            best = Math.Max(best, cur);
        }

        return best;
    }
}

C++ 答案

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

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur = nums[0];
        int best = nums[0];

        for (int i = 1; i < (int)nums.size(); ++i) {
            cur = max(nums[i], cur + nums[i]);
            best = max(best, cur);
        }
        return best;
    }
};

---

15. K 个一组翻转链表

难度感：hard

题目

给定链表，每 k 个节点一组进行翻转；不足 k 个的尾部节点保持原顺序。

题解

• 用虚拟头节点降低头部翻转的边界复杂度。
• 每次先向后走 k 步确认这一组足够长。
• 对 [groupPrev.Next, groupNext) 这一段做局部反转，再接回原链表。

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

C# 答案

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public ListNode ReverseKGroup(ListNode head, int k)
    {
        ListNode dummy = new ListNode(0, head);
        ListNode groupPrev = dummy;

        while (true)
        {
            ListNode kth = GetKth(groupPrev, k);
            if (kth == null) break;

            ListNode groupNext = kth.next;
            ListNode prev = groupNext;
            ListNode cur = groupPrev.next;

            while (cur != groupNext)
            {
                ListNode next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
            }

            ListNode oldHead = groupPrev.next;
            groupPrev.next = kth;
            groupPrev = oldHead;
        }

        return dummy.next;
    }

    private ListNode GetKth(ListNode start, int k)
    {
        while (start != null && k > 0)
        {
            start = start.next;
            k--;
        }
        return start;
    }
}

C++ 答案

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x = 0, ListNode* n = nullptr) : val(x), next(n) {}
};

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0, head);
        ListNode* groupPrev = &dummy;

        while (true) {
            ListNode* kth = getKth(groupPrev, k);
            if (!kth) break;

            ListNode* groupNext = kth->next;
            ListNode* prev = groupNext;
            ListNode* cur = groupPrev->next;

            while (cur != groupNext) {
                ListNode* nxt = cur->next;
                cur->next = prev;
                prev = cur;
                cur = nxt;
            }

            ListNode* oldHead = groupPrev->next;
            groupPrev->next = kth;
            groupPrev = oldHead;
        }

        return dummy.next;
    }

private:
    ListNode* getKth(ListNode* start, int k) {
        while (start && k > 0) {
            start = start->next;
            k--;
        }
        return start;
    }
};

---

16. 链表排序

难度感：medium

题目

给定单链表头节点，将链表按升序排序，要求尽量做到 O(n log n)。

题解

• 链表不适合随机访问，所以归并排序比快速排序更自然。
• 用快慢指针找到中点，把链表断成两半。
• 递归排序左右两半，然后合并两个有序链表。

复杂度：O(n log n) 时间，递归栈 O(log n)。

C# 答案

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public ListNode SortList(ListNode head)
    {
        if (head == null || head.next == null) return head;

        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode right = slow.next;
        slow.next = null; // 断开左右两半

        return Merge(SortList(head), SortList(right));
    }

    private ListNode Merge(ListNode a, ListNode b)
    {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;

        while (a != null && b != null)
        {
            if (a.val <= b.val)
            {
                cur.next = a;
                a = a.next;
            }
            else
            {
                cur.next = b;
                b = b.next;
            }
            cur = cur.next;
        }

        cur.next = a ?? b;
        return dummy.next;
    }
}

C++ 答案

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

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* right = slow->next;
        slow->next = nullptr; // 断开左右两半

        return merge(sortList(head), sortList(right));
    }

private:
    ListNode* merge(ListNode* a, ListNode* b) {
        ListNode dummy;
        ListNode* cur = &dummy;

        while (a && b) {
            if (a->val <= b->val) {
                cur->next = a;
                a = a->next;
            } else {
                cur->next = b;
                b = b->next;
            }
            cur = cur->next;
        }

        cur->next = a ? a : b;
        return dummy.next;
    }
};

---

17. 最大区间和

难度感：easy-medium

题目

给定整数数组，求连续区间的最大和。这个题和最大子数组和是同一个核心模型。

题解

• 把“区间必须连续”转成“以当前位置结尾的最优值”。
• 如果之前的累计和小于 0，就丢弃之前的区间。
• 每走到一个位置都更新全局最大值。

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

SVG 解析图

C# 答案

using System;

public class Solution
{
    public int MaxIntervalSum(int[] nums)
    {
        int current = 0;
        int best = int.MinValue;

        foreach (int x in nums)
        {
            current = Math.Max(x, current + x);
            best = Math.Max(best, current);
        }

        return best;
    }
}

C++ 答案

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

class Solution {
public:
    int maxIntervalSum(vector<int>& nums) {
        int current = 0;
        int best = INT_MIN;

        for (int x : nums) {
            current = max(x, current + x);
            best = max(best, current);
        }

        return best;
    }
};

---

18. 删除最大的 N 个数

难度感：medium

题目

给定数组 nums 和整数 n，删除其中最大的 n 个数，返回剩余元素。若有重复值，按值删除对应数量即可。

题解

• 如果只关心删除哪些值，可以用小顶堆维护最大的 n 个数。
• 先找出要删除的数及其出现次数，再二次扫描保留其余元素。
• 也可以排序后删除，但堆在 n 远小于数组长度时更合适。

复杂度：O(m log n) 时间，O(n) 空间，m 为数组长度。

C# 答案

using System;
using System.Collections.Generic;

public class Solution
{
    public List<int> RemoveLargestN(int[] nums, int n)
    {
        // C# 旧环境没有 PriorityQueue，这里用 SortedDictionary 模拟小顶堆计数。
        SortedDictionary<int, int> heap = new SortedDictionary<int, int>();
        int size = 0;

        foreach (int x in nums)
        {
            Add(heap, x);
            size++;
            if (size > n)
            {
                int min = FirstKey(heap);
                RemoveOne(heap, min);
                size--;
            }
        }

        Dictionary<int, int> remove = new Dictionary<int, int>();
        foreach (var kv in heap)
        {
            remove[kv.Key] = kv.Value;
        }

        List<int> ans = new List<int>();
        foreach (int x in nums)
        {
            if (remove.ContainsKey(x) && remove[x] > 0)
            {
                remove[x]--;
            }
            else
            {
                ans.Add(x);
            }
        }
        return ans;
    }

    private void Add(SortedDictionary<int, int> map, int x)
    {
        map[x] = map.ContainsKey(x) ? map[x] + 1 : 1;
    }

    private void RemoveOne(SortedDictionary<int, int> map, int x)
    {
        if (--map[x] == 0) map.Remove(x);
    }

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

C++ 答案

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

class Solution {
public:
    vector<int> removeLargestN(vector<int>& nums, int n) {
        priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆

        for (int x : nums) {
            pq.push(x);
            if ((int)pq.size() > n) pq.pop();
        }

        unordered_map<int, int> remove;
        while (!pq.empty()) {
            remove[pq.top()]++;
            pq.pop();
        }

        vector<int> ans;
        for (int x : nums) {
            if (remove[x] > 0) {
                remove[x]--;
            } else {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

---

19. 判断两条线段是否相交

难度感：medium

题目

给定二维平面上两条线段 AB 和 CD，判断它们是否相交，包括端点接触和共线重叠。

题解

• 用叉积判断点在线段两侧的位置关系。
• 一般相交：C、D 在 AB 两侧，并且 A、B 在 CD 两侧。
• 共线情况需要额外判断点是否在线段包围盒内。

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

C# 答案

using System;

public struct Point
{
    public long X, Y;
    public Point(long x, long y) { X = x; Y = y; }
}

public class Solution
{
    public bool Intersect(Point a, Point b, Point c, Point d)
    {
        long d1 = Cross(a, b, c);
        long d2 = Cross(a, b, d);
        long d3 = Cross(c, d, a);
        long d4 = Cross(c, d, b);

        if (d1 == 0 && OnSegment(a, b, c)) return true;
        if (d2 == 0 && OnSegment(a, b, d)) return true;
        if (d3 == 0 && OnSegment(c, d, a)) return true;
        if (d4 == 0 && OnSegment(c, d, b)) return true;

        return (d1 > 0) != (d2 > 0) && (d3 > 0) != (d4 > 0);
    }

    private long Cross(Point a, Point b, Point p)
    {
        return (b.X - a.X) * (p.Y - a.Y) - (b.Y - a.Y) * (p.X - a.X);
    }

    private bool OnSegment(Point a, Point b, Point p)
    {
        return Math.Min(a.X, b.X) <= p.X && p.X <= Math.Max(a.X, b.X) &&
               Math.Min(a.Y, b.Y) <= p.Y && p.Y <= Math.Max(a.Y, b.Y);
    }
}

C++ 答案

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

struct Point {
    long long x, y;
};

class Solution {
public:
    bool intersect(Point a, Point b, Point c, Point d) {
        long long d1 = cross(a, b, c);
        long long d2 = cross(a, b, d);
        long long d3 = cross(c, d, a);
        long long d4 = cross(c, d, b);

        if (d1 == 0 && onSegment(a, b, c)) return true;
        if (d2 == 0 && onSegment(a, b, d)) return true;
        if (d3 == 0 && onSegment(c, d, a)) return true;
        if (d4 == 0 && onSegment(c, d, b)) return true;

        return (d1 > 0) != (d2 > 0) && (d3 > 0) != (d4 > 0);
    }

private:
    long long cross(Point a, Point b, Point p) {
        return (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
    }

    bool onSegment(Point a, Point b, Point p) {
        return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
               min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
    }
};

---

20. A* 网格寻路

难度感：medium

题目

给定 0/1 网格，0 可走、1 障碍，从起点到终点四方向移动，使用 A* 求一条最短路径长度；不可达返回 -1。

题解

• A* 本质是带启发函数的 Dijkstra。
• 优先队列按 f = g + h 排序，g 是已走距离，h 是到终点的曼哈顿估计。
• 在单位边权网格中，曼哈顿距离是可采纳启发，不会高估真实距离。

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

C# 答案

using System;
using System.Collections.Generic;

public class Solution
{
    public int AStar(int[][] grid, int sr, int sc, int tr, int tc)
    {
        int m = grid.Length, n = grid[0].Length;
        int[,] dist = new int[m, n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                dist[i, j] = int.MaxValue;

        SortedSet<(int f, int g, int r, int c)> pq = new SortedSet<(int, int, int, int)>();
        dist[sr, sc] = 0;
        pq.Add((Heuristic(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);
            int g = cur.g, r = cur.r, c = cur.c;
            if (r == tr && c == tc) return g;
            if (g != dist[r, c]) continue;

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

    private int Heuristic(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)> set)
    {
        foreach (var x in set) return x;
        return (0, 0, 0, 0);
    }
}

C++ 答案

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

class Solution {
public:
    int aStar(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));
        using Node = tuple<int, int, int, int>; // f, g, r, c
        priority_queue<Node, vector<Node>, greater<Node>> pq;

        dist[sr][sc] = 0;
        pq.push({h(sr, sc, tr, tc), 0, sr, sc});
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

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

            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;
                    pq.push({ng + h(nr, nc, tr, tc), ng, nr, nc});
                }
            }
        }
        return -1;
    }

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