最新文章

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

using namespace std;

// 方法一：暴力递归
class Solution1 {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;

        int minCoins = INT_MAX;

        for (int coin : coins) {
            // 尝试使用当前硬币
            int res = coinChange(coins, amount - coin);
            if (res >= 0) {
                minCoins = min(minCoins, res + 1);
            }
        }

        return minCoins == INT_MAX ? -1 : minCoins;
    }
};

// 方法二：记忆化递归
class Solution2 {
public:
    int coinChange(vector<int>& coins, int amount) {
        // memo[i] 表示组成金额 i 所需的最少硬币数
        vector<int> memo(amount + 1, -2); // -2 表示未计算
        return dfs(coins, amount, memo);
    }

private:
    int dfs(vector<int>& coins, int amount, vector<int>& memo) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;

        // 如果已经计算过，直接返回结果
        if (memo[amount] != -2) return memo[amount];

        int minCoins = INT_MAX;

        for (int coin : coins) {
            int res = dfs(coins, amount - coin, memo);
            if (res >= 0) {
                minCoins = min(minCoins, res + 1);
            }
        }

        // 记录计算结果
        memo[amount] = (minCoins == INT_MAX) ? -1 : minCoins;
        return memo[amount];
    }
};

// 方法三：动态规划
class Solution3 {
public:
    int coinChange(vector<int>& coins, int amount) {
        // dp[i] 表示组成金额 i 所需的最少硬币数
        vector<int> dp(amount + 1, amount + 1);

        // 初始化：组成金额 0 需要 0 个硬币
        dp[0] = 0;

        // 计算每个金额的最小硬币数
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // 如果 dp[amount] 仍然是初始值，说明无法组成该金额
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

// 方法四：动态规划优化
class Solution4 {
public:
    int coinChange(vector<int>& coins, int amount) {
        // dp[i] 表示组成金额 i 所需的最少硬币数
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        // 优化：先对硬币排序，可以减少部分比较
        sort(coins.begin(), coins.end());

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin > i) break; // 硬币面额大于当前金额，无需继续
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
};

// 方法五：广度优先搜索
class Solution5 {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) return 0;

        queue<int> q;
        vector<bool> visited(amount + 1, false);

        q.push(0);
        visited[0] = true;

        int level = 0;

        while (!q.empty()) {
            int size = q.size();
            level++;

            for (int i = 0; i < size; i++) {
                int current = q.front();
                q.pop();

                for (int coin : coins) {
                    int next = current + coin;

                    if (next == amount) {
                        return level;
                    }

                    if (next < amount && !visited[next]) {
                        visited[next] = true;
                        q.push(next);
                    }
                }
            }
        }

        return -1;
    }
};

// 方法六：贪心 + DFS（不一定总是最优，但效率高）
class Solution6 {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 按面额从大到小排序
        sort(coins.rbegin(), coins.rend());

        int ans = INT_MAX;
        dfs(coins, amount, 0, 0, ans);
        return ans == INT_MAX ? -1 : ans;
    }

private:
    void dfs(vector<int>& coins, int amount, int index, int count, int& ans) {
        if (amount == 0) {
            ans = min(ans, count);
            return;
        }

        if (index == coins.size()) return;

        // 剪枝：如果当前硬币数量已经超过已知最优解，提前返回
        if (count >= ans) return;

        // 尝试使用尽可能多的当前面额硬币
        for (int k = amount / coins[index]; k >= 0 && count + k < ans; k--) {
            dfs(coins, amount - k * coins[index], index + 1, count + k, ans);
        }
    }
};

// 测试函数
void testCoinChange() {
    vector<int> coins1 = {1, 2, 5};
    int amount1 = 11;

    vector<int> coins2 = {2};
    int amount2 = 3;

    vector<int> coins3 = {1, 3, 4};
    int amount3 = 6;

    // 测试不同方法
    Solution1 s1;
    Solution2 s2;
    Solution3 s3;
    Solution4 s4;
    Solution5 s5;
    Solution6 s6;

    cout << "测试用例1: coins = [1, 2, 5], amount = 11" << endl;
    cout << "暴力递归: " << s1.coinChange(coins1, amount1) << endl;
    cout << "记忆化递归: " << s2.coinChange(coins1, amount1) << endl;
    cout << "动态规划: " << s3.coinChange(coins1, amount1) << endl;
    cout << "动态规划优化: " << s4.coinChange(coins1, amount1) << endl;
    cout << "广度优先搜索: " << s5.coinChange(coins1, amount1) << endl;
    cout << "贪心+DFS: " << s6.coinChange(coins1, amount1) << endl;
    cout << endl;

    cout << "测试用例2: coins = [2], amount = 3" << endl;
    cout << "暴力递归: " << s1.coinChange(coins2, amount2) << endl;
    cout << "记忆化递归: " << s2.coinChange(coins2, amount2) << endl;
    cout << "动态规划: " << s3.coinChange(coins2, amount2) << endl;
    cout << "动态规划优化: " << s4.coinChange(coins2, amount2) << endl;
    cout << "广度优先搜索: " << s5.coinChange(coins2, amount2) << endl;
    cout << "贪心+DFS: " << s6.coinChange(coins2, amount2) << endl;
    cout << endl;

    cout << "测试用例3: coins = [1, 3, 4], amount = 6" << endl;
    cout << "暴力递归: " << s1.coinChange(coins3, amount3) << endl;
    cout << "记忆化递归: " << s2.coinChange(coins3, amount3) << endl;
    cout << "动态规划: " << s3.coinChange(coins3, amount3) << endl;
    cout << "动态规划优化: " << s4.coinChange(coins3, amount3) << endl;
    cout << "广度优先搜索: " << s5.coinChange(coins3, amount3) << endl;
    cout << "贪心+DFS: " << s6.coinChange(coins3, amount3) << endl;
}

int main() {
    testCoinChange();
    return 0;
}

#include <iostream>
using namespace std;

void swapWithXOR(int &a, int &b) {
    a = a ^ b;  // Step 1: a = a ^ b
    b = a ^ b;  // Step 2: b = (a ^ b) ^ b = a
    a = a ^ b;  // Step 3: a = (a ^ b) ^ a = b
}

int main() {
    int x = 5, y = 10;
    cout << "Before: x = " << x << ", y = " << y << endl;
    swapWithXOR(x, y);
    cout << "After: x = " << x << ", y = " << y << endl;
    return 0;
}

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

int findUnique(const vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;  // 所有出现两次的数字会互相抵消
    }
    return result;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 4, 3, 2, 1};
    cout << "Unique number: " << findUnique(arr) << endl;  // 输出: 5
    return 0;
}

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

string xorEncryptDecrypt(const string& text, char key) {
    string result = text;
    for (size_t i = 0; i < text.length(); i++) {
        result[i] = text[i] ^ key;  // 加密
        // 对结果再次异或相同的key即可解密
    }
    return result;
}

int main() {
    string message = "Hello, World!";
    char key = 'K';

    string encrypted = xorEncryptDecrypt(message, key);
    cout << "Encrypted (hex): ";
    for (char c : encrypted) {
        printf("%02X ", (unsigned char)c);
    }
    cout << endl;

    string decrypted = xorEncryptDecrypt(encrypted, key);
    cout << "Decrypted: " << decrypted << endl;

    return 0;
}

#include <iostream>
using namespace std;

bool haveOppositeSign(int a, int b) {
    // 利用最高位（符号位）的异或判断
    return (a ^ b) < 0;
}

int main() {
    int x = 10, y = -5, z = 20;

    cout << x << " and " << y << " have opposite sign: " 
         << (haveOppositeSign(x, y) ? "true" : "false") << endl;

    cout << x << " and " << z << " have opposite sign: " 
         << (haveOppositeSign(x, z) ? "true" : "false") << endl;

    return 0;
}

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

char calculateChecksum(const vector<char>& data) {
    char checksum = 0;
    for (char byte : data) {
        checksum ^= byte;  // 异或校验
    }
    return checksum;
}

bool verifyChecksum(const vector<char>& data, char expectedChecksum) {
    char calculated = 0;
    for (char byte : data) {
        calculated ^= byte;
    }
    return calculated == expectedChecksum;
}

int main() {
    vector<char> data = {'A', 'B', 'C', 'D', 'E'};

    char checksum = calculateChecksum(data);
    cout << "Checksum: " << (int)checksum << endl;

    // 模拟传输（假设数据正确）
    cout << "Verification: " 
         << (verifyChecksum(data, checksum) ? "Pass" : "Fail") << endl;

    // 模拟数据错误
    vector<char> corruptedData = {'A', 'F', 'C', 'D', 'E'};  // B变成了F
    cout << "Verification with corrupted data: "
         << (verifyChecksum(corruptedData, checksum) ? "Pass" : "Fail") << endl;

    return 0;
}

// 6. 切换特定位（toggle bit）
unsigned int toggleBit(unsigned int num, int position) {
    return num ^ (1 << position);  // 切换指定位（0变1，1变0）
}

// 7. 判断奇偶性
bool isOdd(int num) {
    return (num ^ 1) != (num + 1);  // 等价于 num & 1
}

int main() {
    unsigned int value = 0b1010;  // 二进制 1010 (十进制10)
    cout << "Original: " << value << endl;

    // 切换第1位（从0开始计数）
    value = toggleBit(value, 1);
    cout << "After toggle bit 1: " << value << endl;  // 变成 1000 (8)

    return 0;
}

   struct Node {
       int data;
       Node* next;
   };

   class Stack {
   private:
       Node* top;
   public:
       Stack() : top(nullptr) {}

       void push(int value) {
           Node* newNode = new Node{value, top};
           top = newNode;
       }

       int pop() {
           if (top == nullptr) throw std::out_of_range("Stack is empty");
           int value = top->data;
           Node* temp = top;
           top = top->next;
           delete temp;
           return value;
       }

       bool isEmpty() {
           return top == nullptr;
       }
   };

   class Queue {
   private:
       int* arr;
       int front, rear, capacity;
   public:
       Queue(int size) : capacity(size), front(0), rear(0) {
           arr = new int[size];
       }

       void enqueue(int value) {
           if ((rear + 1) % capacity == front) throw std::overflow_error("Queue is full");
           arr[rear] = value;
           rear = (rear + 1) % capacity;
       }

       int dequeue() {
           if (front == rear) throw std::underflow_error("Queue is empty");
           int value = arr[front];
           front = (front + 1) % capacity;
           return value;
       }

       bool isEmpty() {
           return front == rear;
       }
   };

#include <iostream>
#include <stdexcept>

class ArrayList {
private:
    int* arr;           // 动态数组存储数据
    int capacity;       // 数组的容量
    int size;           // 当前存储的元素个数

public:
    // 构造函数
    ArrayList(int cap = 10) : capacity(cap), size(0) {
        arr = new int[capacity];  // 动态分配内存
    }

    // 析构函数
    ~ArrayList() {
        delete[] arr;  // 释放内存
    }

    // 添加元素到数组末尾
    void add(int value) {
        if (size >= capacity) {
            resize();  // 扩展数组容量
        }
        arr[size++] = value;
    }

    // 根据索引访问元素
    int get(int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of bounds");
        }
        return arr[index];
    }

    // 删除指定索引位置的元素
    void remove(int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of bounds");
        }
        for (int i = index; i < size - 1; ++i) {
            arr[i] = arr[i + 1];  // 向前移动元素
        }
        --size;
    }

    // 扩展数组容量
    void resize() {
        capacity *= 2;  // 容量翻倍
        int* newArr = new int[capacity];
        for (int i = 0; i < size; ++i) {
            newArr[i] = arr[i];
        }
        delete[] arr;  // 释放旧的数组
        arr = newArr;  // 更新为新的数组
    }

    // 打印所有元素
    void print() {
        for (int i = 0; i < size; ++i) {
            std::cout << arr[i] << " ";
        }
        std::cout << std::endl;
    }

    // 获取数组的当前大小
    int getSize() {
        return size;
    }

    // 获取数组的容量
    int getCapacity() {
        return capacity;
    }
};

int main() {
    ArrayList list;

    list.add(10);
    list.add(20);
    list.add(30);
    list.add(40);

    std::cout << "ArrayList after adding elements: ";
    list.print();

    std::cout << "Element at index 2: " << list.get(2) << std::endl;

    list.remove(2);

    std::cout << "ArrayList after removing element at index 2: ";
    list.print();

    std::cout << "Size: " << list.getSize() << ", Capacity: " << list.getCapacity() << std::endl;

    return 0;
}

#include <iostream>
#include <stdexcept>

class LinkedList {
private:
    struct Node {
        int data;
        Node* next;
    };

    Node* head;  // 链表头
    int size;    // 当前存储的元素个数

public:
    // 构造函数
    LinkedList() : head(nullptr), size(0) {}

    // 析构函数
    ~LinkedList() {
        while (head != nullptr) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // 添加元素到链表尾部
    void add(int value) {
        Node* newNode = new Node{value, nullptr};
        if (head == nullptr) {
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next != nullptr) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
        ++size;
    }

    // 根据索引访问元素
    int get(int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of bounds");
        }
        Node* temp = head;
        for (int i = 0; i < index; ++i) {
            temp = temp->next;
        }
        return temp->data;
    }

    // 删除指定索引位置的元素
    void remove(int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of bounds");
        }
        Node* temp = head;
        if (index == 0) {
            head = head->next;
        } else {
            for (int i = 0; i < index - 1; ++i) {
                temp = temp->next;
            }
            Node* toDelete = temp->next;
            temp->next = temp->next->next;
            delete toDelete;
        }
        --size;
    }

    // 打印所有元素
    void print() {
        Node* temp = head;
        while (temp != nullptr) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

    // 获取链表的当前大小
    int getSize() {
        return size;
    }
};

int main() {
    LinkedList list;

    list.add(10);
    list.add(20);
    list.add(30);
    list.add(40);

    std::cout << "LinkedList after adding elements: ";
    list.print();

    std::cout << "Element at index 2: " << list.get(2) << std::endl;

    list.remove(2);

    std::cout << "LinkedList after removing element at index 2: ";
    list.print();

    std::cout << "Size: " << list.getSize() << std::endl;

    return 0;
}

#include <iostream>
#include <array>
#include <algorithm>

int main() {
    // 创建一个固定大小的 std::array
    std::array<int, 5> arr = {1, 2, 3, 4, 5};

    // 获取数组大小
    std::cout << "Size of array: " << arr.size() << std::endl;

    // 使用迭代器遍历数组
    std::cout << "Array elements: ";
    for (auto it = arr.begin(); it != arr.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用 at() 进行访问（带边界检查）
    std::cout << "Element at index 2: " << arr.at(2) << std::endl;

    // 获取第一个和最后一个元素
    std::cout << "First element: " << arr.front() << std::endl;
    std::cout << "Last element: " << arr.back() << std::endl;

    // 使用 fill() 填充所有元素
    arr.fill(10);
    std::cout << "Array after fill: ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // 使用 std::sort 对数组排序
    std::sort(arr.begin(), arr.end());
    std::cout << "Sorted array: ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    // 交换两个 std::array
    std::array<int, 5> arr2 = {1, 1, 1, 1, 1};
    arr.swap(arr2);
    std::cout << "Array after swap: ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

Size of array: 5
Array elements: 1 2 3 4 5 
Element at index 2: 3
First element: 1
Last element: 5
Array after fill: 10 10 10 10 10 
Sorted array: 10 10 10 10 10 
Array after swap: 1 1 1 1 1

#include <iostream>
#include <list>
#include <algorithm>

int main() {
    // 创建一个 std::list
    std::list<int> lst = {10, 20, 30, 40, 50};

    // 获取列表大小
    std::cout << "Size of list: " << lst.size() << std::endl;

    // 在列表尾部添加元素
    lst.push_back(60);
    // 在列表头部添加元素
    lst.push_front(5);

    std::cout << "List after pushing elements: ";
    for (int val : lst) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 删除头部元素
    lst.pop_front();
    // 删除尾部元素
    lst.pop_back();

    std::cout << "List after popping elements: ";
    for (int val : lst) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 使用 insert 插入元素到指定位置
    auto it = lst.begin();
    std::advance(it, 2);  // 移动迭代器到索引 2
    lst.insert(it, 25);

    std::cout << "List after insertion: ";
    for (int val : lst) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 使用 remove 删除特定元素
    lst.remove(30);  // 删除所有值为 30 的元素

    std::cout << "List after removing 30: ";
    for (int val : lst) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 对列表进行排序
    lst.sort();
    std::cout << "Sorted list: ";
    for (int val : lst) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // 清空列表
    lst.clear();
    std::cout << "List after clear: " << lst.size() << std::endl;

    return 0;
}

Size of list: 5
List after pushing elements: 5 10 20 30 40 50 60 
List after popping elements: 10 20 30 40 50 
List after insertion: 10 20 25 30 40 50 
List after removing 30: 10 20 25 40 50 
Sorted list: 10 20 25 40 50 
List after clear: 0

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; ++i) {
        int key = arr[i];  // 当前需要插入的元素
        int j = i - 1;

        // 找到合适的位置并将元素移到正确位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;  // 将当前元素插入到合适位置
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    insertionSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];  // 临时数组

    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);  // 对左半部分进行归并排序
        mergeSort(arr, mid + 1, right);  // 对右半部分进行归并排序

        merge(arr, left, mid, right);  // 合并两个已排序的部分
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    mergeSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为枢纽
    int i = low - 1;  // i 是小于 pivot 的元素的分界

    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);  // 交换元素
        }
    }
    swap(arr[i + 1], arr[high]);  // 将 pivot 放到正确的位置
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 获取分区点

        quickSort(arr, low, pi - 1);  // 递归排序左边
        quickSort(arr, pi + 1, high);  // 递归排序右边
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
using namespace std;

void heapify(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(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; --i)
        heapify(arr, n, i);

    // 提取元素从堆中
    for (int i = n - 1; i >= 1; --i) {
        swap(arr[0], arr[i]);  // 交换堆顶与当前最后一个元素
        heapify(arr, i, 0);  // 重新调整堆
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    heapSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}