3、算法

int sum(int n) {
    int sum = 0; // O(1)
    for (int i = 1; i <= n; i++) { // O(1)
        sum += i;
    }
    return sum;
}

int[] createArray(int n) {
    int[] arr = new int[n]; // O(n)
    for (int i = 0; i < n; i++) {
        arr[i] = i;
    }
    return arr;
}

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

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

void merge(vector<int>& nums, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; ++i) {
        L[i] = nums[left + i];
    }
    for (int i = 0; i < n2; ++i) {
        R[i] = nums[mid + i + 1];
    }
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            nums[k++] = L[i++];
        } else {
            nums[k++] = R[j++];
        }
    }
    while (i < n1) {
        nums[k++] = L[i++];
    }
    while (j < n2) {
        nums[k++] = R[j++];
    }
}

void mergeSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

int main() {
    vector<int> nums{5, 2, 4, 7, 1, 3, 2, 6};
    mergeSort(nums, 0, nums.size() - 1);
    for (auto num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

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

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left;
    for (int j = left; j < right; ++j) {
        if (nums[j] <= pivot) {
            swap(nums[i++], nums[j]);
        }
    }
    swap(nums[i], nums[right]);
    return i;
}

void quickSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(nums, left, right);
        quickSort(nums, left, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, right);
    }
}

int main() {
    vector<int> nums{5, 2, 4, 7, 1, 3, 2, 6};
    quickSort(nums, 0, nums.size() - 1);
    for (auto num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 寻找中位数的中位数
int findMedian(vector<int>& nums, int l, int r) {
    sort(nums.begin() + l, nums.begin() + r + 1);
    return nums[(l + r) / 2];
}

// 将中位数放到左边第一个位置
int partition(vector<int>& nums, int l, int r, int pivot) {
    int i = l, j = r;
    while (i <= j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i <= j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }
    return i - 1;
}

int select(vector<int>& nums, int l, int r, int k) {
    if (l == r) return nums[l];
    int pivot = findMedian(nums, l, r);
    int index = partition(nums, l, r, pivot);
    int count = index - l + 1;
    if (k == count) {
        return nums[index];
    } else if (k < count) {
        return select(nums, l, index - 1, k);
    } else {
        return select(nums, index + 1, r, k - count);
    }
}

int main() {
    vector<int> nums = {5, 1, 3, 2, 4};
    int k = 3;
    int result = select(nums, 0, nums.size() - 1, k);
    cout << "The " << k << "th smallest element is: " << result << endl;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

long long merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    long long count = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
            count += mid - i + 1;
        }
    }
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    for (int p = 0; p < temp.size(); ++p) {
        nums[left + p] = temp[p];
    }
    return count;
}

long long mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) {
        return 0;
    }
    int mid = left + (right - left) / 2;
    long long count = 0;
    count += mergeSort(nums, left, mid);
    count += mergeSort(nums, mid + 1, right);
    count += merge(nums, left, mid, right);
    return count;
}

long long countInversions(vector<int>& nums) {
    return mergeSort(nums, 0, nums.size() - 1);
}

int main() {
    vector<int> nums = {7, 5, 6, 4};
    cout << "The number of inversions is: " << countInversions(nums) << endl;
    return 0;
}

#include <vector>
using namespace std;

// 合并两个已排序的部分
void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> left(arr.begin() + l, arr.begin() + m + 1);
    vector<int> right(arr.begin() + m + 1, arr.begin() + r + 1);

    int i = 0, j = 0, k = l;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    // 复制剩余元素
    while (i < left.size()) arr[k++] = left[i++];
    while (j < right.size()) arr[k++] = right[j++];
}

// 归并排序函数
void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // 找到中点
        mergeSort(arr, l, m);    // 排序左半部分
        mergeSort(arr, m + 1, r); // 排序右半部分
        merge(arr, l, m, r);     // 合并两部分
    }
}

#include <vector>
using namespace std;

// 分区函数
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = (low - 1);  // i是小于基准的元素的索引

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++;    // 增加小于基准的元素的索引
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // pi是分区索引，arr[pi]现在处于正确位置
        int pi = partition(arr, low, high);

        // 分别对分区前后的子数组进行排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

#include <vector>
using namespace std;

void heapify(vector<int>& arr, int n, int i) {
    int largest = i; // 初始化最大元素为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点大于当前最大元素
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大元素不是根节点
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // 递归地调整受影响的子树
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]); // 将当前根节点移至数组末尾

        // 调整剩余堆
        heapify(arr, i, 0);
    }
}

#include <iostream>
using namespace std;

const int MAXN = 1 << 20;
int n, m, a[MAXN], b[MAXN];

// 对于一个二元竞赛，找出其胜者的编号
int get_winner(int x, int y) {
    return a[x] < a[y] ? x : y;
}

// 计算比赛的比较轮数
int get_log(int n) {
    int logn = 0;
    while ((1 << logn) < n) {
        logn++;
    }
    return logn;
}

// 进行一轮比赛，将胜者放到下一轮
void play_round(int cur, int nxt) {
    for (int i = 0; i < n; i += 2) {
        int winner = get_winner(a[i], a[i + 1]);
        b[i >> 1] = winner;
    }
    if (n & 1) {
        b[n >> 1] = a[n - 1];
    }
    swap(a, b);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int logn = get_log(n);
    m = 1 << logn;
    for (int i = n; i < m; i++) {
        a[i] = MAXN;  // 将序列补齐成2的幂次方
    }

    for (int i = 0; i < logn; i++) {
        play_round(i, i + 1);
    }

    cout << a[0] << endl;  // 输出最小值

    return 0;
}

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

void bucketSort(float arr[], int n) {
    vector<float> buckets[n];

    // 1. 将元素分配到桶中
    for (int i = 0; i < n; i++) {
        int bi = n * arr[i]; // 索引
        buckets[bi].push_back(arr[i]);
    }

    // 2. 对每个桶进行排序
    for (int i = 0; i < n; i++) {
        sort(buckets[i].begin(), buckets[i].end());
    }

    // 3. 合并桶
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    float arr[] = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};
    int n = sizeof(arr) / sizeof(arr[0]);
    bucketSort(arr, n);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

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

// 一个用于基数排序的计数排序函数
void countingSort(std::vector<int>& arr, int exp) {
    std::vector<int> output(arr.size());
    std::vector<int> count(10, 0);

    // 计算每个位的出现次数
    for (int i = 0; i < arr.size(); i++)
        count[(arr[i] / exp) % 10]++;

    // 更改count[i]，使得count[i]包含了这一位上小于等于i的数字的个数
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // 构建输出数组
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 将排序好的数据复制到原数组
    for (int i = 0; i < arr.size(); i++)
        arr[i] = output[i];
}

// 基数排序函数
void radixSort(std::vector<int>& arr) {
    int m = *max_element(arr.begin(), arr.end());

    // 对每一位进行计数排序
    for (int exp = 1; m / exp > 0; exp *= 10)
        countingSort(arr, exp);
}

int main() {
    std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    for (int i = 0; i < arr.size(); i++)
        std::cout << arr[i] << " ";
    return 0;
}

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

// 构建部分匹配表
vector<int> buildPartialMatchTable(string pattern) {
    vector<int> lps(pattern.length());
    int len = 0; // 长度为0的前缀
    lps[0] = 0; // lps[0]总是0

    // lps数组的构建
    int i = 1;
    while (i < pattern.length()) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// KMP字符串匹配算法
void KMPSearch(string text, string pattern) {
    vector<int> lps = buildPartialMatchTable(pattern);

    int i = 0; // 文本字符串的索引
    int j = 0; // 模式字符串的索引
    while (i < text.length()) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }

        if (j == pattern.length()) {
            cout << "Found pattern at index " << i - j << endl;
            j = lps[j - 1];
        } else if (i < text.length() && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i = i + 1;
            }
        }
    }
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    KMPSearch(text, pattern);
    return 0;
}

int head[MAXN], ver[MAXM], nxt[MAXM], cnt = 1;
bool vis[MAXN];
int ans = 0;

void add(int x, int y) {
    ver[++cnt] = y;
    nxt[cnt] = head[x];
    head[x] = cnt;
}

void dfs(int u, int num) {
    if (num == 5) {  // 剪枝条件，num为当前深度
        ans++;
        return;
    }
    vis[u] = true;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = ver[i];
        if (!vis[v]) {
            dfs(v, num + 1);
        }
    }
    vis[u] = false;
}

int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; i++) {
        dfs(i, 1);
    }
    cout << ans / 10 << endl;
    return 0;
}

#include <iostream>
#include <queue>
#include <unordered_set>

using namespace std;

// 双向BFS+剪枝求解最短路径
int biBFS(string beginWord, string endWord, unordered_set<string>& wordList) {
    if (beginWord == endWord) return 1; // 特判
    unordered_set<string> visited1, visited2, *visitedPtr1, *visitedPtr2; // 两个方向的visited集合
    visited1.insert(beginWord);
    visited2.insert(endWord);
    int step = 1;
    while (!visited1.empty() && !visited2.empty()) {
        if (visited1.size() > visited2.size()) { // 优化：始终选择访问节点数量较少的那一方，减少搜索的深度
            visitedPtr1 = &visited2;
            visitedPtr2 = &visited1;
            swap(beginWord, endWord);
        } else {
            visitedPtr1 = &visited1;
            visitedPtr2 = &visited2;
        }
        unordered_set<string> tmpSet; // 记录新访问的节点
        for (auto it = visitedPtr1->begin(); it != visitedPtr1->end(); it++) {
            string currWord = *it;
            for (int i = 0; i < currWord.size(); i++) { // 逐个修改当前单词的每一个字符
                char tmp = currWord[i];
                for (char c = 'a'; c <= 'z'; c++) { // 对每一个字符，枚举26个字母
                    currWord[i] = c;
                    if (visitedPtr2->count(currWord)) return step + 1; // 如果另一个方向的visited集合已包含该单词，即找到了公共节点，返回答案
                    if (wordList.count(currWord) && !visitedPtr1->count(currWord)) { // 如果wordList中包含该单词且还未被visited访问，加入tmpSet
                        tmpSet.insert(currWord);
                        visitedPtr1->insert(currWord);
                    }
                }
                currWord[i] = tmp; // 恢复当前单词的第i个字符
            }
        }
        visitedPtr1->swap(tmpSet); // 优化：用swap交换visited集合和tmpSet，避免拷贝visited集合
        step++; // 更新步数
    }
    return 0; // 未找到路径
}

int main() {
    string beginWord = "hit";
    string endWord = "cog";
    unordered_set<string> wordList = {"hot", "dot", "dog", "lot", "log"};
    cout << biBFS(beginWord, endWord, wordList) << endl; // 输出最短路径长度
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 10010;

struct Point {
    int x, y;
    int f, g, h;  // f = g + h，g表示从起点到当前点的实际代价，h表示从当前点到终点的估计代价
};

struct HeapNode {
    int d;
    int x, y;

    bool operator< (const HeapNode& t) const {
        return d > t.d;  // 小根堆，距离越小优先级越高
    }
};

int n, m;
char g[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool st[N][N];
Point q[N * N];
priority_queue<HeapNode> heap;  // A*算法中的堆优化，存储所有待扩展的点

int manhattan(int x, int y, Point& t) {  // 曼哈顿距离
    return abs(x - t.x) + abs(y - t.y);
}

int a_star(Point start, Point end) {
    start.f = 0;
    start.g = 0;
    start.h = manhattan(start.x, start.y, end);

    heap.push({start.f, start.x, start.y});

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int x = t.x, y = t.y;

        if (st[x][y]) continue;
        st[x][y] = true;

        if (x == end.x && y == end.y) return t.d;  // 找到终点

        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];

            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (g[a][b] == '#') continue;

            Point next = {a, b};
            next.g = start.g + 1;
            next.h = manhattan(a, b, end);
            next.f = next.g + next.h;

            heap.push({next.f, a, b});
        }
    }

    return -1;  // 无法到达终点
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];

    Point start = {0, 0}, end = {0, 0};
    cin >> start.x >> start.y >> end.x >> end.y;

    int distance = a_star(start, end);

    cout << distance << endl;

    return 0;
}

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

const int N = 3;  // N为八数码的边长

struct Board {
    int b[N][N];   // 存放八数码的矩阵
    int space;     // 存放0的位置
    int score;     // 估价函数的值
    int step;      // 当前的步数

    // 计算估价函数的值
    void calc_score() {
        int h = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (b[i][j] == 0) continue;
                int x = (b[i][j] - 1) / N;
                int y = (b[i][j] - 1) % N;
                h += abs(i - x) + abs(j - y);
            }
        }
        score = h + step;
    }

    bool operator < (const Board& o) const {
        return score > o.score;   // 优先队列的比较函数
    }
};

const int dx[] = {-1, 0, 1, 0};  // 用于计算空格的邻居位置
const int dy[] = {0, 1, 0, -1};

Board start, goal;
unordered_map<string, int> vis;   // 存放已经访问过的状态
priority_queue<Board> q;          // 优先队列

// 判断当前状态是否合法
bool is_valid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

// 计算当前状态的哈希值
string get_hash(const Board& b) {
    string res;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            res += char(b.b[i][j] + '0');
        }
    }
    return res;
}

// A*算法
void A_star() {
    start.step = 0;
    start.calc_score();
    q.push(start);
    vis[get_hash(start)] = 1;

    while (!q.empty()) {
        Board u = q.top(); q.pop();
        if (u.score > vis[get_hash(u)]) continue;

        if (get_hash(u) == get_hash(goal)) {
            cout << u.step << endl;
            return;
        }

        int sx = u.space / N, sy = u.space % N;
        for (int i = 0; i < 4; i++) {
            int nx = sx + dx[i], ny = sy + dy[i];
            if (!is_valid(nx, ny)) continue;

            Board v = u;
            v.b[sx][sy] = v.b[nx][ny];
            v.b[nx][ny] = 0;
            v.space = nx * N + ny;
            v.step++;
            v.calc_score();

            if (vis[get_hash(v)] && v.score >= vis[get_hash(v)]) continue;
            q.push(v);
            vis[get_hash(v)] = v.score;
        }
    }
}