栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

陷入Java面试中,需要一些提示

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

陷入Java面试中,需要一些提示

正如人们已经指出的那样,错误是您的算法以预定义的顺序进行替换。您的算法将进行转换:

abcc --> ccc
代替
abcc --> aac --> ab --> c

如果要使用生成精简字符串的技术,则需要:

  • 以所有可以想象的顺序(而不是仅一个预定义的迭代顺序)在一个级别上执行替换
  • 找到一种明智的方法来确定哪种替换将最终产生最短的字符串

如果您只需要缩略字符串的长度,那么可以使用一种更简单的实现,它不需要生成缩略字符串。这是@Matteo答案的扩展版本,具有更多详细信息和有效的(非常简单的)算法。

简单属性

我假设在给定的规则集下,关于abc字符串,以下三个属性是正确的。

  1. 如果无法进一步缩小字符串,则该字符串中的所有字符必须为同一字符。

  2. 不可能:

    2 < answer < string.length
    是真的

  3. 在执行归约运算时,如果运算前每个字母的计数为偶数,则运算后每个字母的计数将为奇数。相反,如果在操作之前每个字母的计数为奇数,则在操作之后的计数将为偶数。

物业1

属性一是微不足道的。

属性2(示例说明)

假设:我们有一个长度为5的精简串,以后再也不能精简。

AAAAA

由于此字符串是归约运算的结果,因此前一个字符串必须包含one

B
和one
C
。以下是可能的“父字符串”的一些示例:

BCAAAA
AABCAA
AAACBA

对于所有可能的父字符串,我们可以很容易地看到C:s和B:s中的至少一个可以与A:s而不是彼此组合。这将导致长度为5的字符串,该字符串将进一步减少。因此,我们已经说明了我们拥有不可约的长度为5的字符串的唯一原因是,我们在执行归约运算时没有正确选择要合并的字符。

这种推理适用于所有长度为k的简化字符串

2 < k < string.length

属性3(示例说明)

例如

[numA, numB, numC] = [even, even,even]
,如果有一个折减运算,我们用AB用AB代替AB。A和B的计数将减少1,使计数为奇数,而C的计数将增加1,使计数为奇数。好。

与此类似,如果两个计数为偶数且一个为奇数,则两个计数将为奇数,而在操作后甚至为一个,反之亦然。

换句话说,如果所有三个计数都具有相同的“均匀度”,那么任何减法运算都不能改变它。并且,如果计数的“均匀性”存在差异,则任何减法运算都无法更改该数值。

从属性得出结论

考虑两个不可约的字符串:

A
AA

对于

A
通知,
[numA, numB, numC] = [odd, even, even]
对于
AA
通知,
[numA, numB, numC]= [even, even, even]

现在忘记这两个字符串,并假设我们得到了长度为n的输入字符串。

如果字符串中的所有字符都相等,则答案显然是string.length。

另外,我们从属性2知道可以将字符串缩小到小于3的长度。我们还知道对执行缩小操作的均匀性的影响。如果输入的字符串包含所有字母或所有字母的奇计甚至数,也不可能将其降低到一个字母串,因为它是不可能均匀性结构改变,从

[even,even, even]
[odd, even, even]
通过执行还原操作。

因此,一个更简单的算法如下:

算法

Count the number of occurences of each letter in the input string [numA, numB, numC]If two of these counts are 0, then return string.lengthElse if (all counts are even) or (all counts are odd), then return 2Else, then return 1


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/610345.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号