我当时正在尝试解决旧的Google Kick Start问题，即机器人路径解码。
https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d83d
如果上面的链接不起作用，我已经粘贴了问题提示的精简版，它是该问题底部的解决方案。
对于第一个测试集，机器人可以执行的移动总数为10 ^ 4。第二个测试集（我看不到）没有任何限制。
该解决方案对第二个测试集说：“现在移动的数量在原始程序的长度上可能是指数的。因此，不可能在给定的时间内一一执行移动。“
我的解决方案在第二个测试集上超时。但是我希望我的解决方案是O（n），因为我只是遍历输入字符串并在遇到子路径时推入并弹出堆栈。我觉得我正在做的事情与提供的解决方案相似，使用堆栈代替了递归。关于为什么我的解决方案比他们的解决方案要慢的困惑（我将其粘贴在下面）
这是我的代码
#include <iostream> // includes cin to read from stdin and cout to write to stdout
#include<string>
#include<stack>
using namespace std; // since cin and cout are both in namespace std, this saves some text
int main() {
int t; //the number of test cases
cin >> t;
for (int i = 1; i <= t; ++i) {
string path;
cin >> path;
long width=0;
long height=0;
long n=0;
stack<int> pos; //everytime a '(' is detected, the current
//width and height are pushed onto the stack
//along with the number that precedes the '('
string num="";
for(int j=0;j<path.size();j++){
switch(path[j]){
case 'N':
--height;
break;
case 'S':
++height;
break;
case 'W':
--width;
break;
case 'E':
++w;
break;
case '(':
n=stoi(num);
num = "";
pos.push(height);
pos.push(width);
pos.push(n);
height=0;
width=0;
break;
case ')':
n = pos.top();
pos.pop();
width = (width*n) + pos.top();
pos.pop();
//cout << pos.top() << endl;
h = (height*n) + pos.top();
pos.pop();
break;
default:
num+=path[j];
}
}
width += 1;
height += 1;
int edgeOfPlane=1000000000;
while(width > edgeOfPlane){
width -= edgeOfPlane;
}
while(width <= 0){
width+=edgeOfPlane;
}
while(height <= 0){
height+=edgeOfPlane;
}
while (height > edgeOfPlane){
h -= edgeOfPlane;
}
cout << "Case #" << i << ": " << width << " " << height << endl;
}
return 0;
}
问题和解决方案可以在这里找到
https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d83d
如果有人能解释为什么我的解决方案超时，以及为什么他们的2号测试集递归解决方案有效，我将非常感激！
如果Google链接断开，这里是问题提示的简短摘要。新行星上的漫游者，可以认为是由109列（从西到东从1开始编号）的正方形网格组成和109行（从北到南从1开始编号）。令（w，h）表示第w列和第h行的平方。流动站从正方形（1，1）开始。
流动站移动了代表四个基本方向运动的字符串。机械手按以下顺序执行字符串的每个字符：
还有一个特殊的指令X（Y），其中X是2到9之间的一个数字，且Y是一个非空子程序。这表示机器人应将子程序Y总共重复X次。例如：2（NWE）等效于NWENWE。3（S2（E））等同于SEESEESEE。EEEE4（N）2（SS）等效于EEEENNNNSSSS。
如果流动站移动到网格边缘，则将在开始时返回（圆行星）。
Google的解决方案：
为了简化程序的解析，让我们将ClosingBracket（i）定义为与索引i处的右括号相对应的右括号的索引。我们可以使用线性时间中的堆栈为每个左括号找到ClosingBracket（i），这类似于检查字符串是否为正确的括号序列。
为了便于说明，假定行和列的编号从0（含）到109（不含）。假设机器人处于位置（a，b），现在我们在程序中遇到指令X（Y）。让我们说子程序Y将流动站的当前位置更改为dx，dy（由于火星的圆环形状，我们可以假定0≤dx <109和0≤dy <109）。然后，随着子程序Y重复X次，遵循指令X（Y）之后的流动站位置将是（（a + X * dx）mod 109，（b + X * dy）mod 109）。因此，我们只需要找到每个子程序的流动站相对位移即可。
对于在索引L和R之间的子程序，可以如下使用Evaluate（L，R）递归计算机器人的相对位移。考虑我们当前处于正方形（a，b），最初是正方形（0，0）。从左索引L到右索引R迭代子程序，并考虑两种情况：
如果第i个符号位于{'N'，'S'，'E'，'W'}中，请相应地更改机器人的当前位置。如果第i个符号是数字D，则调用Evaluate（i + 2，ClosingBracket（i + 1）-1）来递归下一个子程序的流动站相对位移（dx，dy），将当前位置更改为（（a + D * dx）mod 109，（b + D * dy）mod 109）和将当前位置i移至ClosingBracket（i + 1）+1。
我们只访问程序中的每个字符一次。该解决方案的时间复杂度为O（N），其中N为程序的长度。