1

我有一个不同短语的数组列表，例如“蛋白质”、“蛋白激酶”、“功能性”、“功能性蛋白质”、“sox5”、“il-6”，现在，如果我输入一个句子，“功能性蛋白激酶和 il-6 和 sox5”，它必须提供输出为“{功能蛋白}激酶和 {il-6} 和 {sox5}”。句子中的每个单词都必须与短语进行比较。

我所做的代码返回了不同字符串的开始和结束索引，这些索引与不同短语的数组列表进行了比较。我只需要过滤掉最大且没有任何冲突的索引。例如输入：

[0, 7][8, 22][8, 15] [36, 43] [23, 43] [20, 30]

所需输出：

[0, 7] [8, 22] [23, 43]

案例：

  • 在 [8, 22] 和 [8, 15] 之间，[8, 22] 最大，因为 22-8 = 14 > 15-8 = 7，所以必须选择 [8,22]。
  • 在 [36, 43], [23, 43] 和 [20, 30] 之间，36 位于 [23, 43] 范围内，30 也位于 [23, 43] 范围内，这是碰撞，但在这些碰撞中，[ 23, 43] 最大，必须选择。

我应该怎么做才能获得所需的输出？（比较标准）

我已经做好了，

ArrayList<ArrayList<Integer>> ListOfList = new ArrayList<ArrayList<Integer>>();
for(int a = 0; a<ListOfList.size();a++)
        {
            if(a == ListOfList.size()-1) break;
            for(int b = a+1; b<ListOfList.size();b++)
            {
                if((ListOfList.get(a).get(0) == ListOfList.get(b).get(0)) && (ListOfList.get(a).get(1) < ListOfList.get(b).get(1)))     
                {
                    startOffset = ListOfList.get(b).get(0);
                    endOffset =  ListOfList.get(b).get(1);
                }
                else
                {
                    startOffset = ListOfList.get(a).get(0);
                    endOffset =  ListOfList.get(a).get(1);
                }
            } 
        }
4

2 回答 2

2

据我了解，您的解决方案是将所有具有相交索引的对分组，然后在每组中找到具有最大长度的对。这是一些样板代码。如果您需要更多说明，请告诉我：

静态类对 { public int start, end;

    Pair(int start, int end) {
        this.start = start;
        this.end = end;
    }

    public int weight() {
        return end - start;
    }

    public boolean contains(int point) {
        return start <= point && point <= end;
    }

    public String toString() {
        return String.format("[%d, %d]", start, end);
    }
}

static class Group {
    public List<Pair> pairs = new ArrayList<Pair>();
    public Pair maxWeight;

    Group(Pair start) {
        add(start);
    }

    Group(List<Pair> pairs) {
        for (Pair pair : pairs) {
            add(pair);
        }
    }

    public boolean contains(Pair pair) {
        for (Pair my : pairs) {
            if (my.contains(pair.start) || my.contains(pair.end))
                return true;
        }
        return false;
    }

    public void add(Pair pair) {
        pairs.add(pair);
        if (maxWeight == null || maxWeight.weight() < pair.weight())
            maxWeight = pair;
    }
}

public static void main(String[] args) {
    List<Pair> pairs = new ArrayList<Pair>();
    pairs.add(new Pair(0, 7));
    pairs.add(new Pair(8, 15));
    pairs.add(new Pair(8, 22));
    pairs.add(new Pair(36, 43));
    pairs.add(new Pair(23, 43));
    pairs.add(new Pair(20, 30));
    List<Group> groups = new ArrayList<Group>();

    for (Pair pair : pairs) {
        List<Group> intersects = new ArrayList<Group>();
        for (Group group : groups) {
            if (group.contains(pair)) {
                intersects.add(group);
            }
        }

        if (intersects.isEmpty()) {
            groups.add(new Group(pair));
        } else {
            List<Pair> intervals = new ArrayList<Pair>();
            intervals.add(pair);
            for (Group intersect : intersects) {
                intervals.addAll(intersect.pairs);
            }

            groups.removeAll(intersects);
            groups.add(new Group(intervals));
        }
    }

    for (Group group : groups) {
        System.out.println(group.maxWeight);
    }
}
于 2012-11-16T05:20:48.687 回答
0

如果我可以为这个问题提出不同的方法，因为如果我是你，你正在使用单词，我不会使用索引而是使用实际单词。

测试第一个单词并查看它是否在短语列表中，如果它没有从测试队列中删除它，是否将下一个单词添加到测试中并再次测试它继续以这种方式继续直到找不到匹配项，一旦这个过程完成后，您就有了第一个词组匹配。

用你的例子

“功能蛋白激酶和il-6和sox5”是测试队列，结果为空。

第一个测试将是“功能性”，它将返回 true，这意味着我们需要添加下一个单词并再次测试

第二个测试是“功能性蛋白质”，它会返回真，所以我们需要添加这个词

第三个测试是“功能性蛋白激酶”，它会返回假，现在我们将前一个测试标记为成功并将其从队列中移到结果中，所以我们有

结果中的“{functional protein}”和队列中的“kinase and il-6 and sox5”

下一个测试将是“激酶”，它是假的，所以我们将“激酶”从队列中移到结果中，现在我们有了

结果中的“{功能蛋白}激酶”和队列中的“and il-6 and sox5”

保持这种状态，直到队列为空。

我意识到这不是您问题的直接答案，但也许以不同的方式看待这个问题会对您有所帮助。

于 2012-11-16T05:18:34.130 回答