LeetCode

约 4148 字大约 14 分钟

C++算法数据结构

2026-02-13

每日一题

799. 香槟塔 - 力扣（LeetCode）

香槟塔点击展开题目

思路：递推

假设f[i][j]有pour的酒，不考虑溢出。

f[i][j] > 1 表示有溢出溢出的量× = (f[j][j] - 1) / 2;
否则没有溢出递推计算所有的f[i]], 答案为f[query_row][query_glass]和1取min

C++

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<vector<double>> f(query_row + 1, vector<double>(query_row + 1));
        f[0][0] = poured;
        for(int i = 0; i < query_row; i ++)
        {
            for(int j = 0; j <= i; j ++)
            {
                if(f[i][j] > 1)
                {
                    double x = (f[i][j] - 1) / 2;
                    f[i + 1][j] += x, f[i + 1][j + 1] += x;
                }
            }
        }
        return min(1.0, f[query_row][query_glass]);
    }
};

从根到叶的二进制数之和

点击展开题目

思路遍历，维护从根节点到当前节点的二进制和深度优先遍历dfs，当前结点到根的二进制值就是父结点乘以2加上当前结点的值。如果遍历到叶子结点，那么就更新答案

时间复杂度: $O(N)$

空间复杂度:

O(H)

C++

  /**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
  class Solution {
  public:
      int sumRootToLeaf(TreeNode* root) {
          return dfs(root, 0);
      }

      int dfs(TreeNode* root, int x)
      {
          if(!root) return 0;
          x = x * 2 + root->val;
          if(!root->left && !root->right) return x;
          return dfs(root->left, x) + dfs(root->right, x);
      }
  };

1582.二进制矩阵中的特殊位置

点击展开题目

思路：开两个数组分别记录行和列中有几个1，判断每个位置行和列是否只有当前一个1。

C++

  class Solution {
  public:
      int numSpecial(vector<vector<int>>& mat) {
          int n = mat.size(), m = mat[0].size();
          vector<int> row(n), col(m);
          for(int i = 0; i < n; i ++)
              for(int j = 0; j < m; j ++)
              {
                  row[i] += mat[i][j];
                  col[j] += mat[i][j];
              }

          int res = 0;
          for(int i = 0; i < n; i ++)
              for(int j = 0; j < m; j ++)
                  if(mat[i][j] == 1 && row[i] == 1 && col[j] == 1)
                      res ++;
          return res;
      }
  };

1758. 生成交替二进制字符串的最少操作数

点击展开题目

C++

  class Solution {
  public:
      int minOperations(string s) {
          int cnt = 0;
          for(int i = 0; i < s.size(); i ++)
          {
              if(s[i] != ('0' + i % 2))
              {
                  cnt ++;
              }
          }
          return min(cnt, (int)s.size() - cnt);
      }
  };

1888. 使二进制字符串字符交替的最少反转次数

点击展开题目

思路：要求操作二最少，操作一无限制，操作一所有可能均为 S+S中字串

$s = 111000, s+s = 111000111000$

111000_____
_110001____
__100011___
___000111__
____001110_
_____011100

要求所有字串交替，可能情况如下

0101...对于每个字符串的下标位置i需要满足int(s[i]) % 2 == i % 2
1010...对于每个字符串的下标位置i需要满足int(s[i]) % 2 != i % 2

把满足 int(t[i])=imod2 的 t[i] 视作 . 字符，把满足 int(t[i]) !=i mod 2 的 t[i] 视作 X 字符，我们可以得到X.XX.XX.XX.

当子串左端点下标是偶数时：
- 子串中的 X 的个数就是改成 0101⋯ 的类型 2 操作次数。
- 子串中的 . 的个数就是改成 1010⋯ 的类型 2 操作次数。
当子串左端点下标是奇数时：
- 子串中的 . 的个数就是改成 0101⋯ 的类型 2 操作次数。
- 子串中的 X 的个数就是改成 1010⋯ 的类型 2 操作次数。

我们可以统计子串中的 X 的个数 cnt，那么 n−cnt 就是子串中的 . 的个数。

对于每个子串，既可以改成 0101⋯，又可以改成 1010⋯，取最小值，用 min(cnt,n−cnt) 更新答案的最小值。

题解参考：灵茶山艾府

C++

class Solution {
public:
    int minFlips(string s) {
        int n = s.size(), ans = n, cnt =  0;
        for(int i = 0; i < n * 2 - 1; i ++)
        {
            if(s[i % n] % 2 != i % 2)
                cnt ++;
            int left = i - n + 1;// 算窗口左边界
            if(left < 0)// 窗口不够长，不算
                continue;
            ans = min({ans, cnt, n - cnt});// 算当前窗口最小修改次数
            if(s[left] % 2 != left % 2)// 删掉滑出窗口的左字符
                cnt --;
        }
        return ans;
    }
};

动态规划

完全平方数

C++神秘数学定理

class Solution {
public:
    bool check(int n)
    {
        int r = sqrt(n);
        return r * r == n;
    }

    int numSquares(int n) {
        if(check(n)) return 1;

        for(int a = 1; a <= n / a; a ++)
            if(check(n - a * a))
                return 2;

        while(n % 4 == 0) n /= 4;
        if(n % 8 != 7) return 3;

        return 4;
    }
};

C++完全背包思想

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, n);
        f[0] = 0;
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= i / j; j ++)
            {
                f[i] = min(f[i], f[i - j * j] + 1);
            }
        }
        return f[n];
    }
};

零钱兑换

C++

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int INF = INT_MAX;
        vector<int> f(amount + 1, INF);
        f[0] = 0;

        for(int i = 1; i <= amount; i ++)
            for(int j = 0; j < coins.size(); j ++)
                if(coins[j] <= i && f[i - coins[j]] != INF)
                    f[i] = min(f[i], f[i - coins[j]] + 1);

        return f[amount] == INF ? -1 : f[amount];
    }
};

周赛490

计算比赛分数差

点击展开题目

思路：模拟，定义两个变量first、second表示第一个人和第二个人的得分，定义一个bool型flag表示是否第一个为主动玩家。如果 nums[i] 是奇数或者每第 6 场比赛，交换角色则flag =! flag，最后返回first-second

c++

class Solution {
public:
    int scoreDifference(vector<int>& nums) {
        int first = 0, second = 0;
        bool flag = true;
        for(int i = 0; i < nums.size(); i ++)
        {
            if(nums[i] % 2) flag = !flag;
            if((i + 1) % 6 == 0) flag = !flag;
            if(flag) first += nums[i];
            else second += nums[i];
        }
        return first - second;
    }
};

阶数数字排列

点击展开题目

C++

class Solution {
public:
    int fact(int n)//计算阶乘
    {
        if(n <= 1) return 1;
        return n * fact(n - 1);
    }
    bool isDigitorialPermutation(int n) {
        //1.预处理0-9的阶乘
        int f[10] = {0};
        for(int i = 0; i < 10; i ++)
        {
            f[i] = fact(i);
        }
        //2.计算n各位阶乘之和记为sum，计算每n中个数字出现的次数
        int cnt[10] = {};
        int t = n;
        int sum = 0;
        while(t)
        {
            cnt[t % 10] ++;
            sum += f[t % 10];
            t /= 10;
        }
        //3 计算sum中每个数字出现频率
        t = sum;
        while(t)
        {
            cnt[t % 10] --;
            t /= 10;
        }
        //4.判断sum中每个数字出现频率和n是否相同，相同则存在
        for(int i = 0; i < 10; i ++)
            if(cnt[i] != 0)
                return false;
        return true;
    }
};

重新排列后的最大按位异或值

点击展开题目

C++

class Solution {
public:
    string maximumXor(string s, string t) {
        int c0 = 0, c1 = 0;
        int n = s.size();
        string res;
        for(int i = 0; i < t.size(); i ++)
        {
            if(t[i] == '0') c0 ++;
            else c1 ++;
        }

        for(int i = 0; i < n; i ++)
        {
            if(s[i] == '1')
            {
                if(c0 > 0)
                {
                    res += '1';
                    c0 --;
                }
                else
                {
                    res += '0';
                    c1 --;
                }
            }
            else
            {
                if(c1 > 0)
                {
                    res += '1';
                    c1 --;
                }
                else
                {
                    res += '0';
                    c0 --;
                }
            }
        }
        return res;
    }
};