- android - RelativeLayout 背景可绘制重叠内容
- android - 如何链接 cpufeatures lib 以获取 native android 库?
- java - OnItemClickListener 不起作用,但 OnLongItemClickListener 在自定义 ListView 中起作用
- java - Android 文件转字符串
给定一个字符串,找出最少需要多少个字符才能使这个单词成为回文。示例:
ABBA : 0 (already a palindrome)ABB: 1FAE: 2FOO: 1
最佳答案
仅限算法,因为这可能是家庭作业 [向 Raymond 道歉,这是一个面试问题而不是家庭作业,正如他的编辑/评论所表明的那样。但是,算法和添加的伪代码对于该目的仍然有效,我在最后添加了一些 C 代码]。
您需要找到字符串末尾最长的回文。可以通过简单地从字符串的开头运行一个指针和从结尾运行一个指针来创建一种查看字符串是否为回文的算法,检查它们所指的字符是否相同,直到它们在中间相遇。像这样的东西:
function isPalindrome(s):
i1 = 0
i2 = s.length() - 1
while i2 > i1:
if s.char_at(i1) not equal to s.char_at(i2):
return false
increment i1
decrement i2
return true
尝试使用完整的字符串。如果这不起作用,将第一个字符保存在堆栈中,然后查看其余字符是否形成回文。如果这不起作用,请同时保存第二个字符并从第三个字符开始再次检查。
最终你会得到一系列保存的字符和剩下的字符串,这是一个回文。
最好的情况是原始字符串是一个回文,在这种情况下堆栈将为空。最坏的情况是剩下一个字符(一个字符的字符串自动成为回文),而所有其他字符都在堆栈中。
您需要添加到原始字符串末尾的字符数是堆栈上的字符数。
要真正制作回文,将字符一个一个地从堆栈中弹出,并将它们放在回文字符串的开头和结尾。
例子:
String Palindrome Stack Notes
------ ---------- ----- -----
ABBA Y - no characters needed.
String Palindrome Stack Notes
------ ---------- ----- -----
ABB N -
BB Y A one character needed.
ABBA Y - start popping, finished.
String Palindrome Stack Notes
------ ---------- ----- -----
FAE N -
AE N F
E Y AF two characters needed.
AEA Y F start popping.
FAEAF Y - finished.
String Palindrome Stack Notes
------ ---------- ----- -----
FOO N -
OO Y F one character needed.
FOOF Y - start popping, finished.
String Palindrome Stack Notes
------ ---------- ----- -----
HAVANNA N -
AVANNA N H
VANNA N AH
ANNA Y VAH three characters needed.
VANNAV Y AH start popping.
AVANNAVA Y H
HAVANNAVAH Y - finished.
String Palindrome Stack Notes
------ ---------- -------- -----
deoxyribo N -
eoxyribo N d
oxyribo N ed
: : :
bo N iryxoed
o Y biryxoed eight chars needed.
bob Y iryxoed start popping.
ibobi Y ryxoed
: : :
oxyribobiryxo Y ed
eoxyribobiryxoe Y d
deoxyribobiryxoed Y - finished.
将此方法转换为“代码”:
function evalString(s):
stack = ""
while not isPalindrome(s):
stack = s.char_at(0) + stack
s = s.substring(1)
print "Need " + s.length() + " character(s) to make palindrome."
while stack not equal to "":
s = stack.char_at(0) + s + stack.char_at(0)
stack = stack.substring(1)
print "Palindrome is " + s + "."
对于那些对伪代码不太感兴趣的人,这里有一个用 C 编写的测试程序可以解决问题。
#include <stdio.h>
#include <string.h>
static char *chkMem (char *chkStr) {
if (chkStr == NULL) {
fprintf (stderr, "Out of memory.\n");
exit (1);
}
return chkStr;
}
static char *makeStr (char *oldStr) {
char *newStr = chkMem (malloc (strlen (oldStr) + 1));
return strcpy (newStr, oldStr);
}
static char *stripFirst (char *oldStr) {
char *newStr = chkMem (malloc (strlen (oldStr)));
strcpy (newStr, &(oldStr[1]));
free (oldStr);
return newStr;
}
static char *addFront (char *oldStr, char addChr) {
char *newStr = chkMem (malloc (strlen (oldStr) + 2));
sprintf (newStr, "%c%s", addChr, oldStr);
free (oldStr);
return newStr;
}
static char *addBoth (char *oldStr, char addChr) {
char *newStr = chkMem (malloc (strlen (oldStr) + 3));
sprintf (newStr, "%c%s%c", addChr, oldStr, addChr);
free (oldStr);
return newStr;
}
static int isPalindrome (char *chkStr) {
int i1 = 0;
int i2 = strlen (chkStr) - 1;
while (i2 > i1)
if (chkStr[i1++] != chkStr[i2--])
return 0;
return 1;
}
static void evalString (char *chkStr) {
char * stack = makeStr ("");
char * word = makeStr (chkStr);
while (!isPalindrome (word)) {
printf ("%s: no, ", word);
stack = addFront (stack, *word);
word = stripFirst (word);
printf ("stack <- %s, word <- %s\n", stack, word);
}
printf ("%s: yes, need %d character(s)\n", word, strlen (stack));
printf ("----------------------------------------\n");
printf ("Adjusting to make palindrome:\n");
while (strlen (stack) > 0) {
printf (" %s, stack <- %s\n", word, stack);
word = addBoth (word, *stack);
stack = stripFirst (stack);
}
printf (" %s\n", word);
printf ("========================================\n");
free (word);
free (stack);
}
int main (int argc, char *argv[]) {
int i;
for (i = 1; i < argc; i++) evalString (argv[i]);
return 0;
}
运行这个:
mkpalin abb abba fae foo deoxyribo
给出输出:
abb: no, stack <- a, word <- bb
bb: yes, need 1 character(s)
----------------------------------------
Adjusting to make palindrome:
bb, stack <- a
abba
========================================
abba: yes, need 0 character(s)
----------------------------------------
Adjusting to make palindrome:
abba
========================================
fae: no, stack <- f, word <- ae
ae: no, stack <- af, word <- e
e: yes, need 2 character(s)
----------------------------------------
Adjusting to make palindrome:
e, stack <- af
aea, stack <- f
faeaf
========================================
foo: no, stack <- f, word <- oo
oo: yes, need 1 character(s)
----------------------------------------
Adjusting to make palindrome:
oo, stack <- f
foof
========================================
deoxyribo: no, stack <- d, word <- eoxyribo
eoxyribo: no, stack <- ed, word <- oxyribo
oxyribo: no, stack <- oed, word <- xyribo
xyribo: no, stack <- xoed, word <- yribo
yribo: no, stack <- yxoed, word <- ribo
ribo: no, stack <- ryxoed, word <- ibo
ibo: no, stack <- iryxoed, word <- bo
bo: no, stack <- biryxoed, word <- o
o: yes, need 8 character(s)
----------------------------------------
Adjusting to make palindrome:
o, stack <- biryxoed
bob, stack <- iryxoed
ibobi, stack <- ryxoed
ribobir, stack <- yxoed
yribobiry, stack <- xoed
xyribobiryx, stack <- oed
oxyribobiryxo, stack <- ed
eoxyribobiryxoe, stack <- d
deoxyribobiryxoed
========================================
关于c# - 我如何找出最少数量的字符来创建回文?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/903176/
找出/计算符号的宽度 panel.add(textfield,BorderLayout.SOUTH); system.out.println(textfield.getWidth()); System
嘿,所以我正在制作一个因式分解程序,我想知道是否有人可以给我任何想法,让我知道如何找到一个有效的方法来找到两个数字乘以指定数字的倍数,以及添加到指定数字。 例如我可能有 (a)(b) = 6 a +
我以以下方式将 GWT 方法导出到 native javascript: public class FaceBookGalleryEntryPoint implements EntryPoint {
通常,当您在 Web 上找到 Silverlight 代码示例时,它可能只包含一段代码,而不是使其工作所需的完整代码集。当我试图确定在 xaml 文件顶部使用什么命名空间和/或程序集声明时,这让我感到
我对 Dojo 工具包有点陌生。有些问题我想得到启发(我用谷歌搜索,但没有得到任何合适且令人满意的答案) 我已经在运行的应用程序(由另一个软件开发人员开发)中有一个 dojo.js(也许是下载的未压缩
这个问题在这里已经有了答案: 关闭 11 年前。 Possible Duplicate: How to detect which row [ tr ] is clicked? 我有一个这样的表:
我目前正在尝试找出特定应用程序使用的数据保护类别。 我的第一个方法是使用未加密的 iTunes 备份来确定所使用的保护类别。我用过this提取备份。但现在我要陷入困境了。 此外,我不太确定 iTune
我有一个 NSRangeException 错误,该错误并不总是发生(尤其是在调试时)。它是随机出现的,我无法弄清楚它来自哪里。我有很多数组操作,因此很难以这种方式消除它。 我的问题是我是否可以从调试
我有一个控制台程序,它链接到 Mac 上的 Foundation 框架。如何找到可执行文件所在的文件夹? 最佳答案 即使该工具不在 bundle 中,您仍然可以使用一些 NSBundle 方法。例如:
简单的问题是:如何找出 Cocoa 应用程序中可执行文件的位置。 请记住,在许多类 Unix 操作系统中,人们使用 PATH 环境来为其可执行文件分配首选位置,特别是当他们的系统中有同一应用程序的多个
如何找出 TGridPanel 内控件的位置(行和列索引)?我想对按钮数量使用常见的 OnClick 事件,并且需要知道按钮的 X、Y 位置。 我使用的是 Delphi 2007。 最佳答案 不幸的是
我试图找到一种方法来确定 .NET 应用程序中任意文件夹中的总磁盘空间和可用磁盘空间。文件夹中的“总磁盘空间”和“可用磁盘空间”是指如果您对其执行“dir”命令,该文件夹将报告的总磁盘空间和可用磁盘空
我希望能够通过 shell 脚本判断任何 POSIX 系统上是否存在命令。 在 Linux 上,我可以执行以下操作: if which ; then ...snip... fi 但是,Solar
如何找到不同 Haskell 函数的复杂性(以 big-O 表示)? 例如, subsequences 的复杂度是多少? ? 最佳答案 您只能通过查看代码来计算函数的确切复杂度。但是,您可以使用 cr
我试图找出我的对象占用了多少内存来查看有多少对象最终出现在 Large Object Heap 上。 (超过 85,000 字节)。 是否像为每个对象添加 4(表示 int)、添加 8(表示 long
一旦我在 Vim 中加载任何文件,它就会尝试检测该文件,并在可能的情况下用颜色突出显示它。 我想知道一个 Vim 命令,它会告诉我 Vim 认为哪个 ftplugin 或文件类型插件/文件类型会突出显
是否有可能找出 querySelector 的哪一部分与 DOM 中的特定元素匹配? 假设您有以下查询: 'h1,h2,h3,h4.custom-bg,div' 如果您使用 document.quer
我遇到一个问题,用户设置的区域设置(德语)与安装的语言 Windows(英语)不同。有没有办法发现安装的 Windows 语言与用户设置的区域设置?我应该注意的问题是我正在创建共享,并且根据区域设置设
我正在写入应用程序中的文件。我想找到该文件以检查该文件是否已正确写入(以便我可以通过 Web View 访问该文件)。这是我用来编写文件的代码: try { FileOutputStream
我有一个从 JSON 文件填充的 HashMap。键值对中的值可以是两种不同的类型 - 字符串或其他键值对。 例如: HashMap hashMap = new Map(); JSON 文件看起来有点
我是一名优秀的程序员,十分优秀!