时间戳

首页 > 解决方案 > 搜索最长的重复字节序列

java - 搜索最长的重复字节序列

问题描述

使用字节我需要找到最长的重复序列。最长的重复序列是 23

23 56 23 8888

由于它从序列 8 开始依次出现在字节列表中两次。我决定在这条路径上采取行动。

  1. 取第一个数字并检查它是否在列表中的其他任何位置，
    如果不是，则取下一个数字

2 356 2 38888

  1. 之后，我检查第一个号码是否一致，如果是，我将它们放在一个列表中，然后我继续检查（例如，如果两个 23 号码之后会重合），如果我不那么我取另一个号码。

23 56 23 8888

我的方法

List<Byte> topList = new ArrayList<>(); // byte list
List<Byte> result = new ArrayList<>(); // result list
for (int i = 0; i < topList.size(); i += count) {
            count = 1;
            for (int j = i + 1; j < topList.size(); j += count) {
                if (topList.get(i).equals(topList.get(j))&& !result.contains(topList.get(j))) {
                    result.add(topList.get(i));
                    result.add(topList.get(j));
                    for (int k = j + 1; k < topList.size(); k++) {
                        if (topList.get(k).equals(topList.get(i + count)) ) {
                            result.add(topList.get(k));
                            System.out.println(result);
                            count++; // step to pass already checked numbers
                        }
                    }
                }
            }
        }

但是我的代码不能正常工作。

2238888

我得到了序列数据。告诉我如何改进它，你不能使用字符串

标签： java

解决方案

我看不到解决方案的任何替代O(n^2)方案，从输入中的每个位置开始，我们生成每个前向序列并检查我们以前是否见过它，保持最长。幸运的是，我们不需要考虑比当前最长序列更短的序列，也不需要考虑更长的序列 then n/2，其中n是输入的大小，因为这些不能重复。此外，我们不考虑破坏重复字符的序列，因为它们将被视为不可分割的。

这是一个简单的实现，它使用 aSet来跟踪以前见过的序列。实际上，您希望使用更紧凑的更复杂的结构并利用元素中的模式，但这足以验证我们正在生成所需的输出。

static List<Byte> longestRepeatingSeq(List<Byte> in)
{
    int n = in.size();
    Set<List<Byte>> seen = new HashSet<>();
    List<Byte> max = Collections.<Byte> emptyList();
    for (int i=0; i<n; i++)
    {
        for (int j =i+max.size()+1; j<=n && j<=i +n/2; j++)
        {
            if (j == n || in.get(j) != in.get(j - 1))
            {
                List<Byte> sub = in.subList(i, j);
                if (seen.contains(sub))
                {
                    if (sub.size() > max.size())
                    {
                        max = sub;
                    }
                } 
                else
                {
                    seen.add(sub);
                }
            }
        }
    }
    return max;
}

测试：

public static void main(String[] args)
{
    String[] tests = 
        {
            "123123",
            "235623",
            "2356238888",
            "88388",
            "883883",
            "23235623238888",
        };

    for(String s : tests)
    {
        List<Byte> in = new ArrayList<>();
        for(String ns : s.split("")) in.add(Byte.parseByte(ns));
        System.out.println(s + " " + longestRepeatingSeq(in));
    }
}

输出：

123123 [1, 2, 3]
235623 [2, 3]
2356238888 [2, 3]
88388 [8, 8]
883883 [8, 8, 3]
23235623238888 [2, 3, 2, 3]

推荐阅读