c++ - 为什么这个 C++ 程序不适用于少数测试用例？

Question

在第一行，我们写一个 0。现在在接下来的每一行中，我们查看前一行，并将每次出现的 0 替换为 01，并将每次出现的 1 替换为 10。

给定第 N 行和索引 K，返回第 N 行中的第 K 个索引符号。（K 的值是 1 索引的。）（1 索引）。

示例：输入：N = 1，K = 1 输出：0

输入：N = 2，K = 1 输出：0

输入：N = 2，K = 2 输出：1

输入：N = 4，K = 5 输出：1

解释：第1行：0 第2行：01 第3行：0110 第4行：01101001

问题链接： https ://leetcode.com/explore/learn/card/recursion-i/253/conclusion/1675/

解决方案：

class Solution {
public:
    int kthGrammar(int N, int K) {
        if(N==0||K==0)
            return 0;
        
        string result="0";
        string finals;
        int i,j;
        for(j=0;j<N-1;j++)
        {
            
            for(i=0;i<result.length();i++)
            {
                if(result[i]=='0')
                    finals.append("01");
                else
                    finals.append("10");
            }
            result=finals;
            
        }
        return result[K-1]-'0';
    }
};

标签： c++algorithmrecursiondata-structures

Answer 1

您的finals字符串保留旧内容。似乎您需要在每个循环转弯时清除它。

无论如何，您的方法不适合大输入 - 所以不是（巨大的）字符串生成考虑用一些数学计算所需的符号。