本文共 1207 字，大约阅读时间需要 4 分钟。

小扣在秋日市集发现了一款速算机器人。店家对机器人说出两个数字（记作 x 和 y ），请小扣说出计算指令：

• "A" 运算：使 x = 2 * x + y ；
• "B" 运算：使 y = 2 * y + x 。

在本次游戏中，店家说出的数字为 x = 1 和 y = 0 ，小扣说出的计算指令记作仅由大写字母 A 、B 组成的字符串 s ，字符串中字符的顺序表示计算顺序，请返回最终 x 与 y 的和为多少。

示例 1：

输入：s = "AB"输出：4解释：经过一次 A 运算后，x = 2, y = 0。再经过一次 B 运算，x = 2, y = 2。最终 x 与 y 之和为 4。

提示：

• 0 <= s.length <= 10
• s 由 'A' 和 'B' 组成

题意：不用说明了。

思路1：简单模拟即可。代码如下：

class Solution {
   public:    int calculate(string s) {
           int x = 1, y = 0;        for (const char &c : s) {
               if (c == 'A') x = 2 * x + y;             else y = 2 * y + x;        }        return x + y;    }};

效率如下：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗：5.7 MB, 在所有 C++ 提交中击败了99.24% 的用户

思路2：如果这个字符串很大的话，$O(n)$ 的算法就无法使用，有没有更快的方法？要求的结果是 $x+y$ ，每出现一个 'A' ，就会有 $x+y=(2x+y)+y=2x+2y$ ，每出现一个 'B' ，就会有 $x+y=x+(2y+x)=2x+2y$ 。所以可以知道，每出现一个 'A'/'B' ，都会使得 $x+y$ 的整体值翻倍。于是 $O(1)$ 的代码如下：

class Solution {
   public:    int calculate(string s) {
           return 1 << s.size();    }};

提交后的结果：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗：5.9 MB, 在所有 C++ 提交中击败了25.99% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108738283 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！