草庐IT

java - 对序列进行分组是具有给定总和的子序列，并具有字典序优先级

coder 2024-03-29 原文

我正在寻找一种方法来搜索给定序列中的子序列，该子序列总和为给定数字( sum ，此处为 4 )并具有字典序优先级。

以下面的例子为例:

1,2,2,4,1,1

不同的子序列可以相加为4 .例如 1,2,1 , 2,2 2,1,1 .如果存在多个这样的序列，则应返回相应索引数组的按字典顺序排列的第一个:因此，如果可以找到具有第一个元素的此类序列，则必须返回该序列，如果没有，则瞄准第二个和所以一个(迭代(采用下一个)和递归(在选择第一个之后，下一个但第一个也应该最接近序列的头部)。

所以对于这个例子，我们选择 1,2,1 .现在 2,4,1离开了。如果我们重复这个问题，我们将无法与 2 匹配。 :2,4大于 4和 2,1小于 4 .因此我们选择 4 .最后我们必须选择2和 1 .

这个概念的一个实际应用是过山车的队列。您需要 4 人乘坐，但有些人与他们的 friend 成群结队，并希望所有人一起乘坐同一趟车。

在这个例子中 1排在最前面的是一个人，2是一群2他身后的 friend 。现在我们总共需要4这趟旅程的人，我们已经有了 3 ，所以我们切线( 2 和 4 )并选择第一个单例，这样我们总共有 4 个人。

最佳答案

如果我正确理解了问题，那么您基本上要做的是将数字分组，使总和为 4并且您优先在队列中添加号码。

您可以使用动态编程方法来做到这一点。我在这里使用 int[]和一个 int总而言之，但该问题可以推广到大多数数据结构。

首先，您必须定义一个比较器来比较 的列表。指数 例如一个字典:

public class LexComp<T extends Comparable<T>> implements Comparator<List<T>> {

    @Override
    public int compare (List<T> la, List<T> lb) {
        Iterator<T> ita = la.iterator();
        Iterator<T> itb = lb.iterator();
        while(ita.hasNext() && itb.hasNext()) {
            T ea = ita.next();
            T eb = itb.next();
            int cr = ea.compareTo(eb);
            if(cr != 0x00) {
                return cr;
            }
        }
        if(itb.hasNext()) {
            return 1;
        } else if(ita.hasNext()) {
            return -1;
        }
        return 0;
    }

}

接下来您可以使用以下方法:
public ArrayList<Integer> groupSum (int[] values, int sum) {
    ArrayList[] memory = new ArrayList[sum+1];
    memory[0] = new ArrayList<Integer>();
    LexComp<Integer> lc = new LexComp<Integer>();
    int index = 0;
    for(int val : values) {
        for(int i = sum-val; i >= 0 ; i--) {
            if(memory[i] != null) {
                ArrayList<Integer> tmp = (ArrayList<Integer>) memory[i].clone();
                tmp.add(index);
                if(memory[i+val] == null || lc.compare(tmp,(ArrayList<Integer>) memory[i+val]) < 0) {
                    memory[i+val] = tmp;
                }
            }
        }
        index++;
    }
    return memory[sum];
}

此方法返回 ArrayList<Integer>的 指数 其对应元素的总和为 sum和 null如果不能创建这样的组。它将根据LexComp 优先考虑某些组比较器。

对于您给定的输入:
groupSum(new int[] {1,2,2,4,1,1},4);
groupSum(new int[] {1,2,3,2,2,2},4);
groupSum(new int[] {1,2,2,3},4);
groupSum(new int[] {1,2,2,3,1},4);

结果是:
[0, 1, 4]
[0, 2]
[0, 3]
[0, 1, 4]

所以你应该选择第一个、第二个和第五个元素，它们确实总和为 4 .然后，您必须自己从阵列中删除这些项目并重新运行该过程。如果不能构造这样的总和，或者没有足够的元素来求和 4 - 如前所述 - 算法将返回 null .在这种情况下，您必须发明一种回退机制。也许返回组与sum 的差别最小。 .

背景

这是一种动态规划方法。您生成一个 memory其中存储 - 对于每个总和 - 迄今为止找到的最佳解决方案。最初我们没有看到任何值，所以所有项目都包含 null除了 memory[0]它包含一个空的数组列表(因为零元素的总和是 0 )。所以内存看起来像:
Mem
4 -> null
3 -> null
2 -> null
1 -> null
0 -> []

现在算法迭代这些值。我们在示例案例中遇到的第一个值是 1 .现在我们寻找已经定义好的列表，唯一的就是 memory[0]我们可以将该列表升级为列表 [0] (数组存储索引)其总和结果为 1 .从那时起，该列表的值为 null没有其他选择，因此我们将此列表添加到 memory[1] :
Mem
4 -> null
3 -> null
2 -> null
1 -> [0]
0 -> []

下一项是 2 : 我们可以升级两个列表 [] -> [1]和 [0] -> [1]这些将导致带有总和的列表 2和 3分别，所以我们将它们存储在内存的这些索引中:
Mem
4 -> null
3 -> [0,1]
2 -> [1]
1 -> [0]
0 -> []

下一项再次是 2 .现在我们可以升级 4列表:[] -> [2] , [0] -> [0,2] , [1] -> [1,2]和 [0,1] -> [0,1,2] .第一个问题是[0,1,2]的总和是 5高于 sum .这并不有趣，所以我们放弃了那个。然而，问题是，有些地方已经包含了列表:
Mem
4 -> null
3 -> [0,1] <> [0,2]
2 -> [1] <> [2]
1 -> [0]
0 -> []

对于冲突的列表，我们需要寻找解决方案。在那种情况下比较器 - 在这种情况下是 LexComp解决错误。由于我们按字典顺序执行此操作，[0,1]来自 [0,2] 的胜利和 [1]来自 [2] .解析后，列表如下所示:
Mem
4 -> [3]
3 -> [0,1]
2 -> [1]
1 -> [0]
0 -> []

下一个元素是 4 .我们可以升级的唯一列表使得总和仍然小于或等于 sum是 [] -> [3]
Mem
4 -> [3]
3 -> [0,1]
2 -> [1]
1 -> [0]
0 -> []

下一个元素是 1 .我们可以升级除一个列表之外的所有列表 4 -> [3] (否则总和将大于 4 )。但这又导致了很多冲突:
Mem
4 -> [3] <> [0,1,4]
3 -> [0,1] <> [1,4]
2 -> [1] <> [0,4]
1 -> [0] <> [4]
0 -> []

现在，如果我们运行按字典序排列的比较器，它有时会接受新列表，有时会接受旧列表。解析后，内存如下:
Mem
4 -> [0,1,4]
3 -> [0,1]
2 -> [0,4]
1 -> [0]
0 -> []

现在，我们当前生成总和为 4 的组的最佳解决方案已从 [3] 更改为至 [0,1,4] .最后一个元素 1不会对游戏有太大改变:
Mem
4 -> [0,1,4] <> [0,1,5]
3 -> [0,1] <> [0,4,5]
2 -> [0,4] <> [0,5]
1 -> [0] <> [5]
0 -> []

决议后的内容如下:
Mem
4 -> [0,1,4]
3 -> [0,1]
2 -> [0,4]
1 -> [0]
0 -> []

现在我们已经考虑了所有元素和生成 4 的最佳解决方案。是 memory[4]或 [0,1,4] .

不同的顺序

这种方法可以概括为提供不同的 Comparator在 List<T> (这里是 LexComp<T> )将优先考虑另一个索引数组。比较器应始终至少满足传递性约束:如果 x 小于 y 且 y 小于 z:x 必须小于 z。此外，索引列表将始终增加。 [4,1,0] 的索引数组因此是不可能的。

关于java - 对序列进行分组是具有给定总和的子序列，并具有字典序优先级，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30429427/

给定javacodegtbrsumsequence

有关java - 对序列进行分组是具有给定总和的子序列，并具有字典序优先级的更多相关文章

  1. ruby-on-rails - 按天对 Mongoid 对象进行分组 - 2

    在控制台中反复尝试之后，我想到了这种方法，可以按发生日期对类似activerecord的(Mongoid)对象进行分组。我不确定这是完成此任务的最佳方法，但它确实有效。有没有人有更好的建议，或者这是一个很好的方法？#eventsisanarrayofactiverecord-likeobjectsthatincludeatimeattributeevents.map{|event|#converteventsarrayintoanarrayofhasheswiththedayofthemonthandtheevent{:number=>event.time.day,:event=>ev

  2. ruby - 具有身份验证的私有(private) Ruby Gem 服务器 - 2

    我想安装一个带有一些身份验证的私有(private)Rubygem服务器。我希望能够使用公共(public)Ubuntu服务器托管内部gem。我读到了http://docs.rubygems.org/read/chapter/18.但是那个没有身份验证-如我所见。然后我读到了https://github.com/cwninja/geminabox.但是当我使用基本身份验证(他们在他们的Wiki中有)时，它会提示从我的服务器获取源。所以。如何制作带有身份验证的私有(private)Rubygem服务器？这是不可能的吗？谢谢。编辑:Geminabox问题。我尝试“捆绑”以安装新的gem..

  3. 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/

  4. 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

  5. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  6. ruby-on-rails - Rails 3.1 中具有相同形式的多个模型？ - 2

    我正在使用Rails3.1并在一个论坛上工作。我有一个名为Topic的模型，每个模型都有许多Post。当用户创建新主题时，他们也应该创建第一个Post。但是，我不确定如何以相同的形式执行此操作。这是我的代码:classTopic:destroyaccepts_nested_attributes_for:postsvalidates_presence_of:titleendclassPost...但这似乎不起作用。有什么想法吗？谢谢! 最佳答案 @Pablo的回答似乎有你需要的一切。但更具体地说...首先改变你View中的这一行对此#

  7. 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)我

  8. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  9. Observability：从零开始创建 Java 微服务并监控它 （二） - 2

    这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

  10. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

随机推荐