java - 陷入Java面试中，需要一些提示

coder 2023-05-18 原文

这是我坚持的面试问题:

Given a string consisting of a, b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?

我尝试的解决方案:

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        try {
            BufferedReader in = new BufferedReader(new InputStreamReader(
                    System.in));

            System.out.println(solve(in.readLine()));

            in.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static int solve(String testCase) {
        LinkedList<String> temp = new LinkedList<String>(deconstruct(testCase));

        for (int i = 0; i < (temp.size() - 1); i++) {
            if (!temp.get(i).equals(temp.get(i + 1))) {
                temp.add(i, getThirdChar(temp.remove(), temp.remove()));
                i = -1;
            }
        }

        return reconstruct(temp).length();
    }

    private static List<String> deconstruct(String testCase) {
        List<String> temp = new LinkedList<String>();

        for (int i = 0; i < testCase.length(); i++) {
            temp.add(testCase.charAt(i) + "");
        }

        return temp;
    }

    private static String reconstruct(List<String> temp) {
        String testCase = "";

        for (int i = 0; i < temp.size(); i++) {
            testCase += temp.get(i);
        }

        return testCase;
    }

    private static String getThirdChar(String firstChar, String secondChar) {
        return "abc".replaceAll("[" + firstChar + secondChar + "]+", "");
    }
}

该代码似乎可以在测试输入“cab”(打印“2”)，“bcab”(打印“1”)和“ccccc”(打印“5”)上正常工作。但是我一直被告知我的代码是错误的。谁能帮助我找出错误所在？

最佳答案

正如人们已经指出的那样，错误是您的算法以预定义的顺序进行替换。您的算法将进行转换:
abcc --> ccc代替abcc --> aac --> ab --> c
如果要使用生成精简字符串的技术，则需要:

以所有可以想象的顺序(而不是仅一个预定义的迭代顺序)在一个级别上执行替换

找到一种聪明的方法来决定哪种替换将产生最后一个最短的字符串

如果您只需要缩小后的字符串的长度，则可以简单得多
不需要生成减少的字符串的实现。这是@Matteo答案的扩展版本，具有更多详细信息和有效的(非常简单的)算法。

简单属性

我假设以下三个属性对于给定规则下的abc-strings是正确的。

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

不可能:2 < answer < string.length是真实的

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

属性(property)1

属性一是微不足道的。

属性2(示例说明)

假设:我们有一个长度为5的精简串，以后再也不能精简。
AAAAA
由于此字符串是归约运算的结果，因此前一个字符串必须包含一个B和一个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代替C。A和B的计数将减少一，使计数为奇数，而C的计数将增加一，使该计数为奇数也一样

与此类似，如果两个计数为偶数且一个为奇数，则两个计数将为奇数，而一个运算后甚至为一个，反之亦然。

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

从属性得出结论

考虑两个不可约的字符串:
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.length

Else if (all counts are even) or (all counts are odd), then return 2

Else, then return 1

关于java - 陷入Java面试中，需要一些提示，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8033553/

陷入 java code br String

有关java - 陷入Java面试中，需要一些提示的更多相关文章

ruby - 我需要将 Bundler 本身添加到 Gemfile 中吗？ - 2
当我使用Bundler时，是否需要在我的Gemfile中将其列为依赖项？毕竟，我的代码中有些地方需要它。例如，当我进行Bundler设置时:require"bundler/setup" 最佳答案没有。您可以尝试，但首先您必须用鞋带将自己抬离地面。关于ruby-我需要将Bundler本身添加到Gemfile中吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/4758609/
ruby - rspec 需要 .rspec 文件中的 spec_helper - 2
我注意到像bundler这样的项目在每个specfile中执行requirespec_helper我还注意到rspec使用选项--require，它允许您在引导rspec时要求一个文件。您还可以将其添加到.rspec文件中，因此只要您运行不带参数的rspec就会添加它。使用上述方法有什么缺点可以解释为什么像bundler这样的项目选择在每个规范文件中都需要spec_helper吗？最佳答案我不在Bundler上工作，所以我不能直接谈论他们的做法。并非所有项目都checkin.rspec文件。原因是这个文件，通常按照当前的惯例，只
ruby - 如何在 Lion 上安装 Xcode 4.6，需要用 RVM 升级 ruby - 2
我实际上是在尝试使用RVM在我的OSX10.7.5上更新ruby，并在输入以下命令后:rvminstallruby我得到了以下回复:Searchingforbinaryrubies,thismighttakesometime.Checkingrequirementsforosx.Installingrequirementsforosx.Updatingsystem.......Errorrunning'requirements_osx_brew_update_systemruby-2.0.0-p247',pleaseread/Users/username/.rvm/log/138121
java - 等价于 Java 中的 Ruby Hash - 2
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/
java - 从 JRuby 调用 Java 类的问题 - 2
我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www
ruby-on-rails - 如何生成传递一些自定义参数的 `link_to` URL？ - 2
我正在使用RubyonRails3.0.9，我想生成一个传递一些自定义参数的link_toURL。也就是说，有一个articles_path(www.my_web_site_name.com/articles)我想生成如下内容:link_to'Samplelinktitle',...#HereIshouldimplementthecode#=>'http://www.my_web_site_name.com/articles?param1=value1¶m2=value2&...我如何编写link_to语句“alàRubyonRailsWay”以实现该目的？如果我想通过传递一些
java - 我的模型类或其他类中应该有逻辑吗 - 2
我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我
ruby - 为什么在 ruby 中创建 Rational 不需要新方法 - 2
这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Rubysyntaxquestion:Rational(a,b)andRational.new!(a,b)我正在阅读ruby镐书，我对创建有理数的语法感到困惑。Rational(3,4)*Rational(1,2)产生=>3/8为什么Rational不需要new方法(我还注意到例如我可以在没有new方法的情况下创建字符串)？
java - 什么相当于 ruby 的 rack 或 python 的 Java wsgi？ - 2
什么是ruby的rack或python的Java的wsgi？还有一个路由库。最佳答案来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht
Observability：从零开始创建 Java 微服务并监控它（二） - 2
这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

java - 陷入Java面试中，需要一些提示

有关java - 陷入Java面试中，需要一些提示的更多相关文章

随机推荐