3

我有两个Arraylist，我想检查一个是否是另一个的子集（排序在比较中并不重要）。问题是：让我们说Ar1={e,e,r}和Ar2={e,r,b,d}。在我的代码中，它说Ar1是一个子集。但我想让它说假，因为Ar2只有一个 e。怎么做？

public static void dostuff(String word1,String word2){
    List<String> list1 = new ArrayList<String>();
    List<String> list2 = new ArrayList<String>();

    for (String character : word1.split("")) {
        list1.add(character);
    }
    for (String character : word2.split("")) {
        list2.add(character);
    }

    boolean sub = list1.containsAll(list2) || list2.containsAll(list1);

    System.out.println(sub);
}
4

7 回答 7

3

我想这可能是你想要的。请注意，如果元素被删除，则list2.remove(elem)返回，否则返回。truefalse

public static boolean dostuff(String word1,String word2){
    List<String> list1 = new ArrayList<>();
    List<String> list2 = new ArrayList<>();
    List<String> list3;

    for (String character : word1.split("")) {
        list1.add(character);
    }

    for (String character : word2.split("")) {
        list2.add(character);
    }

    list3 = new ArrayList<>(list2);

    boolean isSubset = true;

    for (final String elem : list1) {
        if (!list2.remove(elem)) {
            isSubset = false;
            break;
        }
    }

    if (isSubset) {
        return true;
    }

    for (final String elem : list3) {
        if (!list1.remove(elem)) {
            return false;
        }
    }

    return true;
}
于 2015-08-02T13:19:26.967 回答
0

您可以使用几个地图来存储每个字母的频率：

public static void dostuff(String word1, String word2) {
    Map<String, Long> freq1 = Arrays.stream(word1.split("")).collect(
        Collectors.groupingBy(Function.identity(), Collectors.counting()));

    Map<String, Long> freq2 = Arrays.stream(word2.split("")).collect(
        Collectors.groupingBy(Function.identity(), Collectors.counting()));

    System.out.println(contains(freq1, freq2) || contains(freq2, freq1));
}

方法contains如下：

private static boolean contains(Map<String, Long> freq1, Map<String, Long> freq2) {
    return freq1.entrySet().stream().allMatch(
        e1 -> e1.getValue().equals(freq2.get(e1.getKey())));
}

测试：

dostuff("eer", "erbd"); // {r=1, e=2}, {b=1, r=1, d=1, e=1}, false

dostuff("erbed", "eer"); // {b=1, r=1, d=1, e=2}, {r=1, e=2}, true

这个想法是使用 java 8 流来创建频率图，然后流式传输两个图的条目集以比较所有元素及其频率。如果所有条目都匹配，则意味着第二个列表包含第一个列表中具有相同频率的所有元素，而不管顺序如何。

如果结果是false第一个列表，则根据问题要求也以相反的方式执行检查。

于 2015-08-02T16:00:56.260 回答
0

这是一个有效的解决方案

检查演示 

 public static void main (String[] args) throws java.lang.Exception
 {
    dostuff("eer","erbd");
 }

 public static void dostuff(String word1, String word2) {
        List<String> list1 = new ArrayList<String>();

   for (String character : word1.split("")) {
            list1.add(character);
        }

        boolean sub = true;
        for (String character : word2.split("")) {
            if (list1.remove(character)) {
               if (list1.isEmpty()) {
                    break;
                }
            } else {
                sub = false;
                break;
            }
        }
        System.out.println(sub);
    }
于 2015-08-02T13:15:41.773 回答
0

另请注意，数学和 Java 集是唯一的，因此请小心使用术语“子集”。

您可以使用频率图来测试一个列表是否“具有另一个列表中的每个元素，并且出现次数相同或更少”。即一旦你有了你的列表，你可以将它转换成一个Map<T, Integer>来存储每个列表元素的计数。使用映射可以避免改变原始列表（如果通过在遇到它们时从主列表中删除元素进行测试，您会这样做）：

public static <T> boolean isSublist(List<T> masterList, List<T> subList) {
    Map<T, Integer> masterMap = new HashMap<T, Integer>();
    for (T t : masterList) masterMap.put(t, 1 + masterMap.getOrDefault(t, 0));

    Map<T, Integer> testMap = new HashMap<T, Integer>();
    for (T t : subList) testMap.put(t, 1 + testMap.getOrDefault(t, 0));

    for(Map.Entry<T, Integer> entry : testMap.entrySet()) {
        if (masterMap.getOrDefault(entry.getKey(), 0) < entry.getValue()) return false;
    }

    return true;
}

getOrDefault仅从 Java 8 开始可用，但您可以轻松编写自己的方法来处理相同的操作。

于 2015-08-02T13:15:58.073 回答
0

@Johdoe。以下逻辑可能会对您有所帮助。您可以根据需要进行优化。

ArrayList<String> list1 = new ArrayList<String>();
ArrayList<String> list2 = new ArrayList<String>();
list1.add("e");
list1.add("a");
list1.add("r");

list2.add("e");
list2.add("r");
list2.add("b");
list2.add("d");
list2.add("a");
System.out.println("list2 " + list2);
System.out.println("list1 " + list1);

Set<Integer> tempList = new HashSet<Integer>();

System.out.println("  containsAll " + list2.containsAll(list1));
for (int i = 0; i < list2.size(); i++) {
    for (int j = 0; j < list1.size(); j++) {
        if (list2.get(i).equals(list1.get(j))) {
            tempList.add(i);
        }
    }
}
System.out.println(" tempList  " + tempList);
System.out.println("list 1 is subset of list 2  "
        + (tempList.size() == list1.size()));
于 2015-08-02T13:30:22.823 回答
0

既然我明白内容的顺序无关紧要，您只想知道一个字符串的所有字符是否存在于另一个字符串中（频率相同），反之亦然。

试试这个函数，它将检查所有内容，而无需调用该方法两次，也无需使用流：

public static boolean subsetExists(String s1, String s2) {
    String temp = s2.replaceAll(String.format("[^%s]", s1), "");
    char[] arr1 = s1.toCharArray();
    char[] arr2 = temp.toCharArray();
    Arrays.sort(arr1);
    Arrays.sort(arr2);

    boolean isSubset = new String(arr2).contains(new String(arr1));
    if (!isSubset) {
        temp = s1.replaceAll(String.format("[^%s]", s2), "");
        arr1 = temp.toCharArray();
        arr2 = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);

        isSubset = new String(arr1).contains(new String(arr2));
    }
    return isSubset;
}

你不必费心把你String的s变成Lists。正在发生的事情是我们正在检查是否所有的字母都s1存在，s2反之亦然。

我们删除了不在s1from中的字符s2并将其存储在临时String. 将临时String和s1转换为char[]s。然后我们对两个数组进行排序并将它们转换回Strings。然后我们可以检查NEW SORTEDString contains()是否临时NEW SORTED s1。如果这个结果是假的，那么我们从s2to应用相同的逻辑检查s1。

用法：

public static void main(String[] args) throws Exception {
    String s1 = "eer";
    String s2 = "bderz";
    String s3 = "bderzzeee";

    System.out.println(subsetExists(s1, s2));
    System.out.println(subsetExists(s1, s3));
}

public static boolean subsetExists(String s1, String s2) {
    String temp = s2.replaceAll(String.format("[^%s]", s1), "");
    char[] arr1 = s1.toCharArray();
    char[] arr2 = temp.toCharArray();
    Arrays.sort(arr1);
    Arrays.sort(arr2);

    boolean isSubset = new String(arr2).contains(new String(arr1));
    if (!isSubset) {
        temp = s1.replaceAll(String.format("[^%s]", s2), "");
        arr1 = temp.toCharArray();
        arr2 = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);

        isSubset = new String(arr1).contains(new String(arr2));
    }
    return isSubset;
}

结果：

false
true
于 2015-08-02T13:40:38.893 回答
0

我自己找到了解决方案，请检查这是正确的，但我相信它是正确的。

public static void dostuff(String word1, String word2) {
    boolean sub = false;

    ArrayList<String> list1 = new ArrayList<String>();
    ArrayList<String> list2 = new ArrayList<String>();
    ArrayList<String> list3 = new ArrayList<String>();
    for (int i = 0; i < word1.length(); i++) {
        list1.add(word1.split("")[i]);
    }
    for (int i = 0; i < word2.length(); i++) {
        list2.add(word2.split("")[i]);
    }

    if (list1.size() >= list2.size()) {
        for (String i : list2) {
            if (list1.contains(i)) {
                list1.remove(i);
                list3.add(i);
            }
        }
        if (list2.containsAll(list3) && list2.size() == list3.size()) {
            sub = true;
        }
    } else if (list2.size() > list1.size()) {
        for (String i : list1) {
            if (list2.contains(i)) {
                list2.remove(i);
                list3.add(i);
            }
            if (list1.containsAll(list3) && list1.size() == list3.size()) {
                sub = true;
            }
        }
    }
    System.out.println(sub);
}
于 2015-08-02T15:53:40.937 回答