#include <iostream> // cout
#include <stdio.h> // printf
#include <string>
using namespace std;
bool is_palidrome(string inputString) {
int num_to_parse = inputString.size();
/* immediately return on single letter string as all single letter strings are palindromes -- saves CPU time as programme does not need to enter the loop */
if(num_to_parse == 1) {
return true;
}
for(int i=0; num_to_parse; i++) {
int point_end = num_to_parse - i - 1;
if(inputString[i] == inputString[point_end]) {
continue;
} else if (i == num_to_parse) {
return true;
} else {
return false;
}
}}
int main() {
// Change the value of inputString to test different palindromes
string inputString = "caabaac";
printf("%s", is_palidrome(inputString)?"This is a palindrome.":"Not a palindrome."); // ternary: test condition ? return this if true : return this if false
return 0;
}
我认为目前我正在执行的循环次数大约是我需要执行的循环次数的2倍，因此浪费了CPU时间。同样，可能还有进一步的优化。任何帮助都非常感激，因为我真的想正确理解这些内容并为代码库做贡献，而不是仅仅用别人的高级代码来做所有事情。
#1 楼
for(int i=0; num_to_parse; i++)
小屋
为什么
num_to_parse您的病情如何？那你也有if (i == num_to_parse)吗？真奇怪我将其重写为：for(int i=0; i < num_to_parse; i++) {
int point_end = num_to_parse - i - 1;
if(inputString[i] == inputString[point_end]) {
continue;
} else {
return false;
}
}
return true;
如果您想进一步简化，您可以这样做：
for(int i=0; i <= num_to_parse; i++) {
int point_end = num_to_parse - i - 1;
if(inputString[i] != inputString[point_end]) {
return false;
}
}
return true;
注意不同的情况。还有其他一些简化的改进，但是在另一个答案中提到了。
我在写这篇文章的时候，意识到您的缩进是...很奇怪，可以说最小。请不要在代码中使用
}}之类的东西；虽然在少数情况下可能还可以（正常情况下，您没有缩进的嵌套名称空间），但在此都不适用。using namespace std不好理念。请不要这样做。printf("%s", is_palidrome(inputString)?"This is a palindrome.":"Not a palindrome.");
这只是...很奇怪。我的意思是，首先，您没有结尾的换行符，因此它可能根本不会输出任何内容。例如，在我的C IDE中，它会打印，但在我的Bash控制台上，它肯定看起来很奇怪（
This is a palindrome.q@my-hostname ~>）。甚至忽略了这种矛盾……为什么会这样呢？三元数只会使它变得比必须的复杂。如果您坚持使用C函数（稍后会再介绍），请执行以下操作：
if (is_palindrome(inputString)) {
puts("This is a palindrome.");
} else {
puts("Not a palindrome.");
}
C ++等效项应该相当简单；如果您想对刷新每一行抱有偏执，而不是仅仅确保将其刷新在几个关键位置（这是我对性能至关重要的工作，因为要写到以下内容），请用
puts(...)替换std::cout << ... << "\n";，或者用std::endl代替"\n"。控制台速度很慢，除非您告诉他们，否则大多数C ++标准库都将在合理的范围内避免这样做）现在来谈谈“使用C函数”的事情。你为什么要这么做？您具有C ++的全部功能，但您没有。如果要用C编写，请用C编写-它只会发生变化，就像四行一样。可能更少。不要只使用C ++的一小部分。或者，也可以只写C。
关于速度的最初考虑，您可以在O（n）中完成（据我所知），即绝对下限。不过，您仍然要遍历每个字符，因此它并没有达到它想要的速度—您只需要遍历一半以上即可。
最后，“接近金属”？这只是C，只是少量的C ++，它们都是高级语言。不像Python那样高级，但是高级语言的定义是它从C和C ++的任何一台特定机器中抽象出来。这里没有金属。那可能是机器代码，也可能是汇编。
评论
\ $ \ begingroup \ $
哇，很奇怪，它可以在任何存在错误的编码环境中工作！不可思议，我看到了在不同环境中的不同行为！
\ $ \ endgroup \ $
–Angular4 Kiddie
17年4月22日在14:15
\ $ \ begingroup \ $
...在我忘了Tab移至下一件事而不是缩进之后，我花了我很多时间来完成我的评论，我得到了2个赞成和1个接受。谢谢？ ：D
\ $ \ endgroup \ $
–莫妮卡基金的诉讼
17年4月22日在14:16
\ $ \ begingroup \ $
@RailsKiddie并不是唯一的一个-请参阅我的编辑。至少有我发现，还有另一件事会使它的行为不一致。
\ $ \ endgroup \ $
–莫妮卡基金的诉讼
17年4月22日在14:16
\ $ \ begingroup \ $
我会正确阅读。这真的很有用。显然，如果我知道在发布时代码在所有环境中都无法正常工作，那我就不会在SO中发布，而是在这里，但因为我对反馈感到非常满意，这是一个非常有用的响应。
\ $ \ endgroup \ $
–Angular4 Kiddie
17年4月22日在14:20
\ $ \ begingroup \ $
@CodyGray好，很公平。我在考虑C，因为该程序基本上只是C，而C没有（用户指定的）命名空间。
\ $ \ endgroup \ $
–莫妮卡基金的诉讼
17年4月22日在17:42
#2 楼
第一件事：这不起作用#include <iostream> // cout
#include <stdio.h> // printf
#include <string>
您包括了
<iostream>，但没有使用它来代替printf。如果我们实际上按照C ++的方式使用<iostream>，则不需要<stdio.h>。using namespace std;
对于小的示例和程序，这并不多问题但是在较大的程序中，在文件顶层使用
std名称空间会污染全局名称空间，如果在头文件中使用该名称空间尤其糟糕。 int num_to_parse = inputString.size();
为确保正确性，并在输入字符串过大并超出
auto的最大限制的情况下，此处应使用int而不是int。 if (num_to_parse == 1) {
return true;
}
可以完全删除，并在重写的
for循环中进行处理。 for (int i = 0; num_to_parse; i++) {
int point_end = num_to_parse - i - 1;
if (inputString[i] == inputString[point_end]) {
continue;
} else if (i == num_to_parse) {
return true;
} else {
return false;
}
}
for循环的条件永远不会为零（它可以（一旦建议被应用），这只是一个附加了计数器的无限循环。条件应为i < num_to_parse。那不是for循环的目的。它只会搞乱所有内容（就像您的if语句一样，这没有任何意义）。我将该函数的结尾重写为（编辑：注释的改进）： // (num_to_parse/2) means that i will reach the middle of the string, and no further.
auto middleOfString = num_to_parse / 2;
for (decltype(num_to_parse) i = 0; i < middleOfString; ++i) {
if (inputString[i] != inputString[num_to_parse-i-1]) {
return false;
}
}
return true;
}
更简单，它可以工作:)
int main() {
// Change the value of inputString to test different palindromes
string inputString = "caabaac";
printf("%s", is_palidrome(inputString)?"This is a palindrome.":"Not a palindrome."); // ternary: test condition ? return this if true : return this if false
return 0;
}
printf可以用C ++优良性和具有更易读的if / else语句（在这种情况下）的三元语句替换。应用了所有这些后，最终代码如下所示：
#include <iostream>
#include <string>
bool is_palidrome(std::string inputString) {
auto num_to_parse = inputString.size();
auto middleOfString = num_to_parse / 2;
for (decltype(num_to_parse) i = 0; i < middleOfString; ++i) {
if (inputString[i] != inputString[num_to_parse-i-1]) {
return false;
}
}
return true;
}
int main() {
// Change the value of inputString to test different palindromes
std::string inputString = "caabaac";
if (is_palidrome(inputString)) {
std::cout << "This is a palindrome." << std::endl;
} else {
std::cout << "Not a palindrome." << std::endl;
}
return 0;
}
评论
\ $ \ begingroup \ $
好的第一个答案！我要假装你偷走了我们俩从我身上注意到的所有东西，尽管那可能根本不是真的。 :)
\ $ \ endgroup \ $
–莫妮卡基金的诉讼
17年4月22日在14:35
\ $ \ begingroup \ $
谢谢，谢谢:)事实是，我在提交它之前就开始写这篇文章，所以我们俩都自己做了这些事情：P但是后来ifif语句使我震惊，所以我对其进行了测试并不得不重写因为OP的代码无效。
\ $ \ endgroup \ $
–user136614
17年4月22日在14:37
\ $ \ begingroup \ $
@InternetAussie是的，它只是在我使用的编码环境中起作用的，因此在这里发布了，但是自那以后，我发现它不适用于大多数其他语言。
\ $ \ endgroup \ $
–Angular4 Kiddie
17年4月22日在14:40
\ $ \ begingroup \ $
我很好奇，为什么不使用迭代器而不是索引来重写它呢？ leftChar = inputString.begin（）rightChar = inputString.end（）while（leftchar！= rightChar）{...}
\ $ \ endgroup \ $
–pacmaninbw
17年4月22日在15:19
\ $ \ begingroup \ $
@pacmaninbw几个原因：（1）包括我自己在内的更多人熟悉并适应索引。 （2）使用迭代器没有太多好处。 （3）如果字符串的长度是偶数，则迭代器将“交叉”并遍历整个字符串，而不是一半。 （4）我必须记得在开始之前减少end迭代器，因为它指向结束之后的元素。
\ $ \ endgroup \ $
–user136614
17-4-22在15:33
#3 楼
忽略正确性问题以及其他答案已详细介绍的其他一些问题，而将重点放在简单的程序转换（将程序转换为等效程序）上：值得指出只要有
if (c) {
return true;
} else {
return false;
}
，只需将其替换为
return c;
也不需要
continue;因为除了这些if之外没有其他内容。您可以将if的主体设为空（如果要保留该结构）。这样就可以了（注意：我不建议实际使用带有空if主体的代码，这只是我建议的较大转换的一个步骤）：if (inputString[i] == inputString[point_end]) {
} else {
return i == num_to_parse;
}
从那里，您可以将循环更改为（将条件固定为一点，以确保您的意图是什么）
for (int i=0; i<num_to_parse; i++) {
if (inputString[i] != inputString[point_end]) {
return i == num_to_parse;
}
}
这表明了不必要的计算，现在
return中的条件永远不能是true，因为循环将在i == num_to_parse之前结束。现在，可以将其更改为：for (int i=0; i<num_to_parse; i++) {
if (inputString[i] != inputString[point_end]) {
return false;
}
}
再一次，这不会解决正确性问题，因为除了我改变条件之外，没有任何变换改变了程序的含义（通常是程序转换的目的）。但是，这已在其他答案中得到解决。
现在，由于简化了代码，这也许可以更正确地说明问题。
此外，在一个不相关的主题上：我不确定是否将其描述为“接近金属”。它绝对需要操作系统，并且使用诸如
std::string之类的高级结构。这并不是说它不好，但是我不会将其描述为“接近金属”。评论
\ $ \ begingroup \ $
我唯一不同意的是建议继续选举以支持一个空的身体。继续是很好和明确的，一个空的身体看起来像有人不小心删除了一些东西。我知道这只是进行较大转换的一个步骤，但是最好弄清楚这一点，以防有人弄错了杆的末端并开始将其继续换成空语句。
\ $ \ endgroup \ $
–法老王
17年4月23日在0:37
\ $ \ begingroup \ $
@Pharap好点！我对此添加了注释。
\ $ \ endgroup \ $
–大卫
17年4月23日在0:42
#4 楼
在所有其他因素都相同的情况下，解决问题的最佳方案是使他人最容易理解的解决方案。您提到您除了“基本循环和数学运算”外，不想使用任何东西，但是最容易理解的代码通常不包含原始的显式循环。因此，我建议最好的解决方案是：bool is_palindrome = std::equal(in.begin(), in.end(), in.rbegin());
对迭代器有一个健康的了解对于使用标准库编写简洁的算法至关重要，因此您应该将其归功于自己确保您对它们感到满意。
std::equal比较两个范围的元素，如果每个元素的第一个元素相等，每个元素的第二个元素相等，则返回true，依此类推，直到结束。标准库容器的rbegin()和rend()函数在容器上返回反向迭代器。也就是说，迭代器将容器从最后一个元素遍历到第一个元素，而不是从第一个元素到最后一个元素。因此，基本上，我们要做的是检查字符串的反向视图是否等于字符串本身。当然，这样做的工作量大约是所需的两倍，每个字符读取两次。除非您有非常长的字符串，否则根本不会有问题，但是如果您想将线性时间系数减少一半，则可以这样做，而不会损失太多可读性：
bool is_palindrome = std::equal(in.begin(), in.begin() + (in.size() / 2), in.rbegin());
这里的所有极端情况都是正确的事情，但是无论如何，我还是会继续讨论它们，只是为了欢笑和踢腿。
如果是空字符串
in.begin() == in.end()，并且std::equal返回true的空范围，因此正确地认为它是回文。在优化版本中，in.begin() + 0 == in.begin()使我们得到相同的结果。对于单个字符输入，第一个版本将其与自身进行比较，并且（惊奇！）发现它是相等的。在优化的版本中，
in.size() / 2变为1 / 2，当进行整数除法时，其结果为0，因此我们返回比较空范围，并将其视为回文。在输入的情况下第一个版本的长度为奇数，将中间的字符与其自身进行比较，这是不必要的，但不会改变结果。在优化版本中，
n / 2再次向0截断，因此忽略了中间字符，这没关系。因为我们知道从字符串开头算起的长度始终等于如果从字符串的末尾开始计算长度，则无需担心显式检查大小或使用
std::equal重载，该重载将结束迭代器用于第二个范围。最后，修改后，您可以使该算法真正通用，从而不仅可以在
std::string上运行，而且还可以在std::wstring，char[N]（尽管由于空终止而不能使用字符串文字），std::vector<int>等上运行。template <typename T>
bool is_palindrome(const T& in) {
using std::begin;
using std::end;
using std::rbegin;
auto it1 = begin(in);
auto it2 = it1 + (std::distance(it1, end(in)) / 2);
return std::equal(it1, it2, rbegin(in));
}
#5 楼
当您传入string("")或string()时，您的代码中存在错误。我想指出的另一件事是，您对如何节省进入循环之前检查num_to_parse == 1的时间的评论不太正确。当发现自己在运行continue的循环中编写第二条检查时，应该始终保持警惕。有一种更好的方法。不必检查奇数长度字符串的中间字母，因为它与自身完全相同。因此，您可以检查
i < num_to_parse/2，并且当num_to_parse为1时，程序将立即进入循环。但是，您需要检查字符串大小是否为零，否则将初始化
point_end至-1。这使inputString[point_end]成为危险的错误！这是一个固定版本。
bool is_palindrome2(const std::string& s)
{
if (s.size() > 0) {
const size_t last = s.size()-1;
const size_t sentinel = s.size()/2;
for (size_t i = 0; i < sentinel; ++i )
if (s[i] != s[last-i])
return false;
} // end if
return true;
}
许多程序员不喜欢这样使用无符号索引；最好添加断言
last >= i，以防万一有人弄乱了循环，这绝对是偏执的。。特别是，Google会告诉您使用带符号的类型（例如ptrdiff_t）作为循环索引，而Microsoft则告诉您使用rsize_t，您可以更轻松地捕获下溢错误。由于有一个评论者提出了疑问，为什么不使用迭代器，所以这里是一个使用迭代器的版本。在没有机器语言间接寻址的体系结构上，这可能更接近金属。它也几乎与C程序员为您提供的优化代码相同，并且可以以相同的速度进行编译：
bool is_palindrome1(const std::string& s)
{
if (s.size() > 0) {
std::string::const_iterator left = s.begin();
std::string::const_iterator right = s.end()-1;
while (left < right) {
if (*left != *right)
return false;
++left; // Often written: if (*left++ != *right--)
--right;
} // end while
} // end if
return true;
}
和测试驱动程序：
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using std::cout;
using std::endl;
using std::size_t;
int main()
{
const std::vector<std::string> testcases =
{ "", "a", "aa", "ba", "abccba", "abcdcba", "abdccba" };
for ( const std::string& s : testcases )
if ( is_palindrome2(s) && is_palindrome1(s) )
cout << '\"' << s << "\" is a palindrome." << endl;
else if ( !is_palindrome2(s) && !is_palindrome1(s) )
cout << '\"' << s << "\" is not a palindrome." << endl;
else
cout << "Bug on input \"" << s << "\"." << endl;
return EXIT_SUCCESS;
}
#6 楼
请注意有关“最佳”解决方案的内容，但是这是我在C ++中的解决方法：#include <string>
#include <iostream>
using namespace std;
bool is_palindrome(const string &inputString)
{
for(int i = 0, j = inputString.size() - 1; i < j; i++, j--)
if (inputString[i] != inputString[j]) return false;
return true;
}
int main(int argc, char *argv[])
{
if (argc != 2) cout << "Usage: " << argv[0] << " <string>" << endl;
else cout << "The string '" << argv[1] << "' is "
<< (is_palindrome(argv[1]) ? "" : "not ")
<< "a palindrome." << endl;
return 0;
}
但是由于您提到的是最接近金属的方法，所以我请尝试在C中执行此操作：
#include <stdio.h>
#include <string.h>
int is_palindrome(const char *inputString)
{
int i, j;
if (inputString)
for(i = 0, j = strlen(inputString) - 1; i < j; i++, j--)
if (inputString[i] != inputString[j]) return 0;
return 1;
}
int main(int argc, char *argv[])
{
if (argc != 2) printf("Usage: %s <string>\n", argv[0]);
else printf("The string '%s' is %sa palindrome.\n",
argv[1], (is_palindrome(argv[1]) ? "" : "not "));
return 0;
}
请注意，在两种情况下，
is_palindrome中的循环条件还确保了空字符串有资格作为回文，而不会尝试不正确访问索引为-1的字符。评论
\ $ \ begingroup \ $
C版本需要空指针检查。
\ $ \ endgroup \ $
–法老王
17年4月23日在0:45
\ $ \ begingroup \ $
好点。编辑。
\ $ \ endgroup \ $
–维克多·托特（Viktor Toth）
17年4月23日在1:02
\ $ \ begingroup \ $
这不是正确性问题，但是由于这是一个代码检查站点，所以我必须说，我希望在代码中看到更多的花括号。即使我了解它是如何工作的，但在if之后立即看到for循环，而没有引入任何作用域，总是让我做两次。这也大大增加了维护难度。
\ $ \ endgroup \ $
–科迪·格雷
17-4-23在9:29
\ $ \ begingroup \ $
这是一个好主意，但我谨不同意。几十年来（自1970年代以来我一直在编写代码）我开始鄙视过多的花括号。除了成为不必要的学徒（以我个人公认的个人观点）之外，它们还使代码更难阅读，因为它散布在更多的房地产中，更难以一次看到。是的，当有机会插入更多代码时，我也使用花括号，或者缩进级别太多。但是当我判断可以忽略它们时，我很乐意这么做。
\ $ \ endgroup \ $
–维克多·托特（Viktor Toth）
17-4-23在13:11
\ $ \ begingroup \ $
@isanae FWIW对我来说很有意义。 if（expression）语句；之所以合乎逻辑，是因为它类似于一个简单的句子。确保大括号对垂直对齐是同样合理的。与之相比，K＆R在行尾有大括号而在行首有大括号的系统似乎要倒退得多。
\ $ \ endgroup \ $
–法老王
17年4月25日在10:56
评论
我知道这是一个小程序，但是您仍然应该检查一下。 stackoverflow.com/questions/1452721 / ...这里的金属到底是什么？
当您完成一项任务时，应该在编写代码之前先分析一下手头的东西。回文是一个反映在中间的单词，谁甚至可以考虑检查其中的所有字符？删除for，声明两个索引（两个int），将一个设置为0，将另一个设置为字符串的末尾，然后执行while循环，直到第一个索引大于或等于第二个索引（记住++和-显然是循环内的索引）
您对回文症的确切定义是什么？您的解决方案不会检测到许多传统的英语回文。例如：-女士，我是亚当-我是在那儿看到厄尔巴岛-一个人，一个计划，一条运河，巴拿马！您的解决方案是否考虑英语以外的其他语言？ -日语：かるいきびんなこねこなんびきいるか-中文：上海自来水来自海上-北印度语：नन是否考虑重音折叠？ -西班牙语：Adánno cede con nada。
如果您要说“接近金属”，请确保您的代码是汇编语言，而不是高级语言。