吉比特

41. 数组实现堆排序

难度感：medium

题目

使用数组原地实现堆排序，将数组按升序排列。

题解

• 升序排序一般先建大顶堆。
• 堆顶是当前最大值，把它交换到数组末尾。
• 缩小堆范围后对堆顶下沉，重复直到有序。

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

C# 答案

public class Solution
{
    public void HeapSort(int[] a)
    {
        int n = a.Length;

        for (int i = n / 2 - 1; i >= 0; i--)
            Heapify(a, n, i);

        for (int end = n - 1; end > 0; end--)
        {
            Swap(a, 0, end);      // 最大值放到末尾
            Heapify(a, end, 0);   // 只维护 [0, end)
        }
    }

    private void Heapify(int[] a, int size, int i)
    {
        while (true)
        {
            int left = i * 2 + 1, right = i * 2 + 2, largest = i;
            if (left < size && a[left] > a[largest]) largest = left;
            if (right < size && a[right] > a[largest]) largest = right;
            if (largest == i) break;
            Swap(a, i, largest);
            i = largest;
        }
    }

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

C++ 答案

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    void heapSort(vector<int>& a) {
        int n = a.size();

        for (int i = n / 2 - 1; i >= 0; --i)
            heapify(a, n, i);

        for (int end = n - 1; end > 0; --end) {
            swap(a[0], a[end]);    // 最大值放到末尾
            heapify(a, end, 0);    // 只维护 [0, end)
        }
    }

private:
    void heapify(vector<int>& a, int size, int i) {
        while (true) {
            int left = i * 2 + 1, right = i * 2 + 2, largest = i;
            if (left < size && a[left] > a[largest]) largest = left;
            if (right < size && a[right] > a[largest]) largest = right;
            if (largest == i) break;
            swap(a[i], a[largest]);
            i = largest;
        }
    }
};

---

42. 字符串模拟位运算：二进制加法

难度感：medium

题目

给定两个二进制字符串 a 和 b，返回它们的二进制和字符串。

题解

• 从低位到高位模拟竖式加法。
• 每一位相加时带上进位 carry。
• 当前位结果是 sum % 2，新进位是 sum / 2。

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

C# 答案

using System.Text;

public class Solution
{
    public string AddBinary(string a, string b)
    {
        int i = a.Length - 1, j = b.Length - 1, carry = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0 || carry > 0)
        {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';
            sb.Append((char)('0' + (sum % 2)));
            carry = sum / 2;
        }

        char[] arr = sb.ToString().ToCharArray();
        System.Array.Reverse(arr);
        return new string(arr);
    }
}

C++ 答案

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

class Solution {
public:
    string addBinary(string a, string b) {
        int i = a.size() - 1, j = b.size() - 1, carry = 0;
        string ans;

        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';
            ans.push_back(char('0' + (sum % 2)));
            carry = sum / 2;
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};