整数转十六进制表示

实现一个算法，将给定整数转换为十六进制字符串形式。对于负数，采用补码表示；结果中除零本身外不应出现前导零，且所有字母均为小写。禁止使用内置的直接转换函数。

输入范围： −2³¹ ≤ num ≤ 2³¹ − 1

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

string intToHex(int val) {
    if (val == 0) return "0";
    unsigned int x = val;  // 利用无符号数自动处理补码
    string res;
    while (x > 0) {
        int digit = x & 0xF;
        if (digit < 10) res = char('0' + digit) + res;
        else res = char('a' + digit - 10) + res;
        x >>= 4;
    }
    return res;
}

网格中的岛屿计数

给定一个由字符 '1'（陆地）和 '0'（水）构成的二维网格，统计其中岛屿的个数。岛屿由相邻的陆地水平或垂直连接而成，网格四周视为水域。

#include <vector>
using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void eraseIsland(vector<vector<char>>& board, int r, int c) {
    if (r < 0 || r >= board.size() || c < 0 || c >= board[0].size()) return;
    if (board[r][c] != '1') return;
    board[r][c] = '0';
    for (int k = 0; k < 4; k++) {
        eraseIsland(board, r + dx[k], c + dy[k]);
    }
}

int countIslands(vector<vector<char>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    int rows = grid.size(), cols = grid[0].size();
    int total = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '1') {
                total++;
                eraseIsland(grid, i, j);
            }
        }
    }
    return total;
}

最长连续递增子数组

在整数数组中找出连续递增子数组的最大长度。遍历过程中维护当前递增长度，遇到非递增时重置计数。

int maxAscendingLen(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return n;
    int best = 1, cur = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i] > arr[i-1]) {
            cur++;
            best = max(best, cur);
        } else {
            cur = 1;
        }
    }
    return best;
}

构造回文串的最少插入次数

求将字符串变为回文串所需的最少字符插入次数。等价于原串长度减去其最长回文子序列长度。

int minInsertions(string s) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = n-1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i+1; j < n; j++) {
            if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
            else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
        }
    }
    return n - dp[0][n-1];
}

双值最大公约数

计算两个非负整数的最大公约数，采用欧几里得算法的迭代实现。

long long computeGCD(long long a, long long b) {
    while (b != 0) {
        long long tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

过河问题

多人过河类问题通常涉及动态规划或贪心策略。设每人过河耗时已知，每次最多两人乘船，求最短时间方案。

int riverCross(vector<int>& cost) {
    sort(cost.begin(), cost.end());
    int n = cost.size();
    if (n == 0) return 0;
    if (n == 1) return cost[0];
    if (n == 2) return cost[1];
    // 方案：最快者往返接送 vs 最快两人先过
    int res = 0;
    while (n > 3) {
        // 两种策略取较小
        int planA = cost[0] + 2*cost[1] + cost[n-1];
        int planB = 2*cost[0] + cost[n-1] + cost[n-2];
        res += min(planA, planB);
        n -= 2;
    }
    if (n == 3) res += cost[0] + cost[1] + cost[2];
    else if (n == 2) res += cost[1];
    else res += cost[0];
    return res;
}

火车票预订系统

模拟列车座位分配，处理区间查询与预订请求。可用线段树或差分数组维护各区间剩余票数。

struct TicketSystem {
    vector<int> diff;
    int stations;
    
    TicketSystem(int n) : stations(n), diff(n+1, 0) {}
    
    void book(int from, int to, int cnt) {
        diff[from] += cnt;
        diff[to+1] -= cnt;
    }
    
    bool check(int from, int to, int need) {
        int cur = 0;
        for (int i = 0; i <= to; i++) {
            cur += diff[i];
            if (i >= from && cur < need) return false;
        }
        return true;
    }
};

双栈模拟队列

使用两个栈实现队列的先进先出特性。一个栈负责入队，另一个负责出队，必要时转移元素。

template <typename T>
class QueueViaStacks {
    stack<T> inStack, outStack;
    
    void shift() {
        if (!outStack.empty()) return;
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }
    
public:
    void enqueue(T val) { inStack.push(val); }
    
    T dequeue() {
        shift();
        T val = outStack.top();
        outStack.pop();
        return val;
    }
    
    T peek() { shift(); return outStack.top(); }
    
    bool empty() { return inStack.empty() && outStack.empty(); }
};

方阵顺时针旋转

将 n×n 矩阵顺时针旋转90度，要求原地操作。采用分层处理，逐圈交换四个对应位置。

void rotateMatrix(vector<vector<int>>& mtx) {
    int n = mtx.size();
    for (int layer = 0; layer < n/2; layer++) {
        int first = layer, last = n - 1 - layer;
        for (int i = first; i < last; i++) {
            int offset = i - first;
            int top = mtx[first][i];
            mtx[first][i] = mtx[last-offset][first];
            mtx[last-offset][first] = mtx[last][last-offset];
            mtx[last][last-offset] = mtx[i][last];
            mtx[i][last] = top;
        }
    }
}

背包问题之小偷选择

给定物品重量与价值，在容量限制下求最大价值。经典01背包的动态规划解法。

int knapsack(vector<int>& wt, vector<int>& val, int cap) {
    int n = wt.size();
    vector<int> dp(cap + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = cap; w >= wt[i]; w--) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[cap];
}

任务调度优化

给定任务及其冷却时间，求完成所有任务的最短时间。贪心策略：优先安排出现次数最多的任务，利用最大堆或计数排序。

int leastInterval(vector<char>& tasks, int coolDown) {
    vector<int> freq(26, 0);
    for (char c : tasks) freq[c - 'A']++;
    sort(freq.begin(), freq.end());
    int maxFreq = freq[25];
    int idle = (maxFreq - 1) * coolDown;
    for (int i = 24; i >= 0 && freq[i] > 0; i--) {
        idle -= min(freq[i], maxFreq - 1);
    }
    return tasks.size() + max(idle, 0);
}