判断井字棋胜负

通过模拟游戏过程，记录每一步落子情况，检查是否存在横、竖或对角线方向的三连。

class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        char board[3][3] = {{' ', ' ', ' '}, {' ', ' ', ' '}, {' ', ' ', ' '}};
        
        // 填充棋盘
        for (int i = 0; i < moves.size(); ++i) {
            int x = moves[i][0], y = moves[i][1];
            board[x][y] = (i % 2 == 0) ? 'X' : 'O';
        }

        // 检查是否有获胜者
        auto checkWin = [&](char ch) {
            // 行
            for (int i = 0; i < 3; ++i) {
                if (board[i][0] == ch && board[i][1] == ch && board[i][2] == ch)
                    return true;
            }
            // 列
            for (int j = 0; j < 3; ++j) {
                if (board[0][j] == ch && board[1][j] == ch && board[2][j] == ch)
                    return true;
            }
            // 主对角线
            if (board[0][0] == ch && board[1][1] == ch && board[2][2] == ch)
                return true;
            // 反对角线
            if (board[0][2] == ch && board[1][1] == ch && board[2][0] == ch)
                return true;
            return false;
        };

        if (checkWin('X')) return "A";
        if (checkWin('O')) return "B";

        // 是否还有空位
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == ' ') return "Pending";
            }
        }

        return "Draw";
    }
};

最优汉堡制作方案

利用二分查找确定小皇堡数量，基于总原料数约束验证可行性。

class Solution {
public:
    vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        vector<int> result;
        int left = 0, right = cheeseSlices, mid, best = -1;

        while (left <= right) {
            mid = (left + right) / 2;
            int totalTomato = mid * 2 + (cheeseSlices - mid) * 4;

            if (totalTomato <= tomatoSlices) {
                best = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        if (best != -1 && best * 2 + (cheeseSlices - best) * 4 == tomatoSlices) {
            result.push_back(cheeseSlices - best);
            result.push_back(best);
        }

        return result;
    }
};

统计全1正方形子矩阵数量

使用二维前缀和快速计算任意子矩形中1的数量，枚举所有可能的正方形并判断是否全为1。

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int prefix[n+1][m+1] = {0};

        // 构建前缀和数组
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                prefix[i+1][j+1] = prefix[i][j+1] + prefix[i+1][j] - prefix[i][j] + matrix[i][j];
            }
        }

        int count = 0;
        // 枚举所有可能的正方形
        for (int len = 1; len <= min(n, m); ++len) {
            for (int i = 0; i + len <= n; ++i) {
                for (int j = 0; j + len <= m; ++j) {
                    int totalOnes = prefix[i+len][j+len] - prefix[i][j+len] - prefix[i+len][j] + prefix[i][j];
                    if (totalOnes == len * len) {
                        ++count;
                    }
                }
            }
        }

        return count;
    }
};

分割回文串最少修改次数

预处理每个子串变为回文所需的最小修改次数，再用动态规划求解将字符串分成k个回文串的最小代价。

class Solution {
public:
    int palindromePartition(string s, int k) {
        int n = s.length();
        const int INF = 0x3f3f3f3f;

        // dp[i][j]: 前 i 个字符分成 j 个回文串的最小修改次数
        int dp[n+1][k+1];
        memset(dp, INF, sizeof(dp));
        for (int j = 0; j <= k; ++j) dp[0][j] = 0;

        // change[i][j]: 子串 s[i:j] 变成回文所需修改次数
        int change[n][n];
        memset(change, 0, sizeof(change));

        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                int cost = 0;
                for (int l = i, r = j; l < r; ++l, --r) {
                    cost += (s[l] != s[r]);
                }
                change[i][j] = cost;
            }
        }

        // 动态规划
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= min(i, k); ++j) {
                for (int prev = 1; prev <= i; ++prev) {
                    dp[i][j] = min(dp[i][j], dp[prev-1][j-1] + change[prev-1][i-1]);
                }
            }
        }

        return dp[n][k];
    }
};