c++ - 调试嵌套 for 循环的正常方法是什么？

Question

我正在为 Leetcode 问题 38 编写代码。数数并说。它没有通过案例，所以我添加了一些cout进行调试。请告诉我是否有调试嵌套 for 循环的正常方法，我应该在哪里添加cout表达式。我不想知道如何修改代码以通过案例。
这是我的代码：

class Solution {
public:
    string countAndSay(int n) {
        string cur("1");
        while (--n) {
            string tmp = cur;
            string next;
            for (int i = 0; i < tmp.size();) {
                cout << "i:" << i << endl;
                int count = 1;
                for (int j = i + 1; j < tmp.size(); j++) {
                    if (tmp[j] != tmp[0]) {
                        break;
                    }
                    count++;
                }
                cout << "count:" << count << endl;
                next += std::to_string(count) + tmp[0];
                cout << "cur:" << cur << endl;
                i += count;
            }
            cur = next;
            cout << n << cur << endl;
        }
        
        return cur;
        
    }
};

标签： c++debuggingnested-loopscout

Answer 1

您将不得不为此使用调试器，并逐步通过您的算法来查找错误。很难调试别人的算法。

这将通过：

#include <string>

struct Solution {
    static const std::string countAndSay(int n) {
        if (not n) {
            return "";
        }

        std::string res = "1";

        while (--n) {
            std::string curr = "";

            for (int index = 0; index < res.size(); index++) {
                int count = 1;

                while ((index + 1 < res.size()) and (res[index] == res[index + 1])) {
                    count++;
                    index++;
                }

                curr += std::to_string(count) + res[index];
            }

            res = curr;
        }

        return res;
    }
};

Java 解决方案

class Solution {
    public String countAndSay(int n) {
        if (n == 1)
            return "1";
        String prev = countAndSay(n - 1);
        StringBuilder str = new StringBuilder();
        int i = 0;
        while (i < prev.length()) {
            char curr = prev.charAt(i);
            int j = 0;
            while (i + j < prev.length() && prev.charAt(i + j) == curr)
                j++;
            str.append(j);
            str.append(curr);
            i += j;
        }
        return str.toString();
    }
}

这是 LeetCode 使用正则表达式的解决方案之一：

import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
  public String countAndSay(int n) {
    String currSeq = "1";

    // Pattern to match the repetitive digits
    String regexPattern = "(.)\\1*";
    Pattern pattern = Pattern.compile(regexPattern);

    for (int i = 1; i < n; ++i) {
      Matcher m = pattern.matcher(currSeq);
      StringBuffer nextSeq = new StringBuffer();

      // each group contains identical and adjacent digits
      while (m.find()) {
        nextSeq.append(m.group().length() + String.valueOf(m.group().charAt(0)));
      }
      // prepare for the next iteration
      currSeq = nextSeq.toString();
    }

    return currSeq;
  }
}

这是另一个使用滑动窗口的 LeetCode 解决方案：

class Solution {
  public String countAndSay(int n) {

    LinkedList<Integer> prevSeq = new LinkedList<Integer>();
    prevSeq.add(1);
    // Using -1 as the delimiter
    prevSeq.add(-1);

    List<Integer> finalSeq = this.nextSequence(n, prevSeq);
    StringBuffer seqStr = new StringBuffer();
    for (Integer digit : finalSeq) {
      seqStr.append(String.valueOf(digit));
    }
    return seqStr.toString();
  }

  protected LinkedList<Integer> nextSequence(int n, LinkedList<Integer> prevSeq) {
    if (n <= 1) {
      // remove the delimiter before return
      prevSeq.pollLast();
      return prevSeq;
    }

    LinkedList<Integer> nextSeq = new LinkedList<Integer>();
    Integer prevDigit = null;
    Integer digitCnt = 0;
    for (Integer digit : prevSeq) {
      if (prevDigit == null) {
        prevDigit = digit;
        digitCnt += 1;
      } else if (digit == prevDigit) {
        // in the middle of the sub-sequence
        digitCnt += 1;
      } else {
        // end of a sub-sequence
        nextSeq.add(digitCnt);
        nextSeq.add(prevDigit);
        // reset for the next sub-sequence
        prevDigit = digit;
        digitCnt = 1;
      }
    }

    // add the delimiter for the next recursion
    nextSeq.add(-1);
    return this.nextSequence(n - 1, nextSeq);
  }
}

---

参考

• 有关其他详细信息，您可以查看讨论板。有很多公认的解决方案，其中包含多种语言和解释、高效算法以及渐近时间/空间复杂度分析^1、2。