0

我正在练习 Koeing 加速 C++，并想验证我的答案。由于网上没有可用的解决方案，我想在这里发布并请专家对我的解决方案的看法。我不确定人们是否会喜欢我把它贴在这里。如果没有，请告诉我，我以后不会这样做。还要提一下，这不是家庭作业，纯粹是我希望将我的 C++ 技能提升到一个新的水平。

问题：编写一个程序来查找字典中的所有回文。接下来，找到最长的回文。

到目前为止我所做的-> 我已经定义了测试回文的函数，还将所有单词存储在一个列表中。我在下面发布了我的代码。

我被困在哪里： 我需要建议，我选择使用列表数据结构而不是向量是否好？其次，我被困在如何显示最长的单词。我可以显示最长的长度但不能显示最长的单词。

我在下面的尝试

    bool palindromeTest( const std::string& input )
{
   typedef std::string::size_type strSize;
    strSize i = 0;
    strSize j = input.size() - 1  ;
    while( i < input.size() )
    {
        if ( input[i] != input[j])
        {
            return false;
        }
        i++;
        j--;
    }

    return true;
}



int main()
{

    // stores all words in a list or vector
    std::list< string> listDict;
    std::string readWord;
    std::ifstream readFile( "/Users/apple/palidndrome-ch5-10/dict.txt" );
    if( ! readFile )
    {
        std::cout <<" failed to open file" << std::endl;
        return 0;
    }
    while( readFile >> readWord )
    {
        listDict.push_back( readWord );
    }

     std::string::size_type maxLen = 0 ;
     std::string longestWord = " "; // to store longest palindrome


     // print all the palindrome words and also which is longest palindrome.

    for( std::list<std::string>::const_iterator it = listDict.begin(); it != listDict.end(); ++it )
    {

        if( palindromeTest( *it )  )
        {
            std::cout <<" the word -> " << *it << " is palindrome" << std::endl;
            // find max len of palindrome;
            maxLen = max( maxLen, it->size() );
            longestWord = *it ;// need to change code here ?? no idea how

        }

    }

    std::cout <<" the maximum len is = " << maxLen << std::endl;
    std::cout << " the word with maximum length is  " << longestWord ; // something is wrong here


    return 0;
}
4

2 回答 2

1

向量和列表在这里同样有效，尽管向量更有效。

您可以通过更改找到最长的单词

maxLen = max( maxLen, it->size() );
            longestWord = *it ;// need to change code here ?? no idea how

到

if (it->size() >= longestWord.size()) {longestWord = *it;}

（您实际上不需要跟踪 maxlen，因为您可以调用longestWord.size()。）

于 2012-07-15T03:19:50.577 回答
1

首先是回文测试。您正在检查字符串中的每个字符两次，这是不需要的。虽然在这种特殊情况下这无关紧要，因为它只是将该特定操作的时间加倍，但对于一些类似的操作，它会改变语义（考虑reverse-- 在概念上与回文测试非常相似）。为了改进检查，您可以使用循环计数器 from 0toinput.size()/2或使用两个指针/迭代器并运行直到它们在中间相遇。另请注意，迭代到input.size()/2将留下一个从未测试过奇数大小字符串的字符，但这很好。

当需要顺序容器时，您应该始终默认为std::vector<>，而不是std::list<>. 要手动查找最大值，您应该将调用更改max为进行测试，以检查此元素是否大于前一个最大值，然后更新 max 的值和字符串的位置（或字符串本身）。在这种特殊情况下，如果重复次数很高，您也可以考虑不使用顺序容器，而是使用关联容器 ( std::set<std::string>) 来避免重复。但最好不要将单词完全存储在内存中。

您应该学习使用迭代器，以及标准库中的迭代器标头。例如，阅读循环可以转换为：

std::vector<std::string> words;
std::copy( std::istream_iterator<std::string>( readFile ),
           std::istream_iterator<std::string>(),
           std::back_inserter( words );

回文检查可以调用std::equal算法：

bool isPalindrome( std::string const & str ) {
   return std::equal( str.begin(), str.begin()+str.size()/2,
                      str.rbegin() );
}

通过提供适当的函子，也可以使用算法来找到最长的回文：

std::vector::const_iterator max = std::max_element( words.begin(), words.end(), []( std::string const & lhs, std::string const & rhs ) { return lhs.size () < rhs.size(); });

（使用 C++11 中的 lambda，在 C++03 中，您需要创建一个执行相同比较的函子，这需要更多样板代码，但不应该更复杂）

正如 Antimony 指出的那样，如果您只需要这个结果，则不需要将所有单词都保存在内存中，在这种情况下，您可以只测试读取的每个单词，并且仅当它是最长的回文时才存储它直到现在。这不是很容易用标准算法实现的，而且只滚动你自己的循环会更简单。

虽然出于学习目的，您可能想要遵循这本书（针对 C++03），但 C++11 中的一个简单解决方案可能是：

std::string longestPalindrome( std::istream& stream ) {
   std::string longest;
   std::for_each( std::istream_iterator<std::string>(stream),
                  std::istream_iterator<std::string>(),
                  [&longest]( std::string const & word ) {
                      // if is longest palindrome so far
                      if (std::equal( word.begin(),
                                      word.begin()+word.size()/2,
                                      word.rbegin() 
                          && word.size() > longest.size())) 
                      {
                         longest = word;
                      }
                  });
   return longest;
}
int main() {
   std::ifstream readFile( "/Users/apple/palidndrome-ch5-10/dict.txt" );
   if ( !readFile ) {
      std::cerr << "failed to open file\n";      // [*]
      exit(1);
   }
   std::string longest = longestPalindrome( readFile );
   std::cout << "The longest palindrome is: '" << longest << "'\n";
}

[*]：注意，除非你真的需要它，否则最好只输出 "\n" 而不是std::endl. 两者之间的区别在于，它std::endl还会刷新流（强制写入），这会无缘无故地影响性能。至于什么时候需要flush，基本上是需要保证现在输出的时候，比如查询用户的时候：

std::cout << "Enter a number: " << std::flush; // Ensure that the user gets the message
                                               // before we lock waiting for an answer:
std::cin >> number;

即使在这种情况下，转储“\n”也比转储“\n”更清楚（如果您需要换行符）而std::flush不是std::endl（不太清楚刷新是故意的，因为有太多代码std::endl无休止地使用......

于 2012-07-15T04:22:17.333 回答