Найти массив ключей (шаблон) в заданном массиве

Я работаю над этой проблемой уже 2 часа, и мой разум перестал работать. И я никуда не денусь. Может кто-нибудь помочь?

Вопрос в том, соответствует ли точный шаблон из массива ключей другому массиву. Например:

Key = {3, 8, 6}
Target = {3, 6, 8, 8, 6, 3, 8, 6, 2, 4}

ответом здесь будут индексы, по которым они найдены, а именно:

{5, 6, 7}

вы новичок в Java и хотите знать, как это сделать в Java?

Gimhani 10.09.2018 08:41

Пожалуйста, покажите нам, что вы сделали на данный момент. Что именно не работает?

deHaar 10.09.2018 08:41

Вы просто ищете первое появление? Может быть несколько случаев?

reto 10.09.2018 08:44

Спасибо за ответ, на самом деле я буду искать несколько вхождений. И у меня действительно есть опыт работы с Java, я могу решить проблему leetcode easy - medium, но каким-то образом я застрял на этом и не понимаю, где.

He Chuan 10.09.2018 09:04

По крайней мере, вставьте свой код то, что вы пробовали

ap.singh 10.09.2018 09:17

Просто к вашему сведению; С точки зрения программирования 2 часа - это не большой срок.

achAmháin 10.09.2018 11:05
Основы программирования на Java
Основы программирования на Java
Java - это высокоуровневый объектно-ориентированный язык программирования, основанный на классах.
Концепции JavaScript, которые вы должны знать как JS программист!
Концепции JavaScript, которые вы должны знать как JS программист!
JavaScript (Js) - это язык программирования, объединяющий HTML и CSS с одной из основных технологий Всемирной паутины. Более 97% веб-сайтов используют...
4
6
95
6
Перейти к ответу Данный вопрос помечен как решенный

Ответы 6

Ответ принят как подходящий

Этот код решает проблему:

        int[] key = new int[]{3, 8, 6};
        int[] target = new int[]{3, 6, 8, 8, 6, 3, 8, 6, 2, 4};
        for (int i = 0; i < target.length; i++) {
            int j = 0;
            for (j = 0; j < key.length && (i + j) < target.length; j++) {
                if (target[i + j] != key[j]) {
                    break;
                }
            }
            if (j == key.length && j != 0) {
                System.out.print("{");
                for (j = 0; j < key.length; j++) {
                    System.out.print(i + j);
                    if (j != key.length - 1) {
                        System.out.print(", ");
                    }
                }
                System.out.println("}");
            }

        }

Мы хотим найти массив в родительском массиве и распечатать соответствующие индексы.

Rahim Dastar 10.09.2018 08:57

Да, я тоже прочитал вопрос. Под «немного дополнительной информацией» я подразумеваю, пожалуйста, не размещайте просто код, а сообщайте OP, что делает код, то есть как, код решает проблему.

deHaar 10.09.2018 08:59

Большое тебе спасибо. @RahimDastar. Это мне очень помогло, наконец-то обошли квартал.

He Chuan 10.09.2018 10:26

Попробуй это,

public static void main(String args[]) {
    int[] a = { 1, 5, 7, 3, 6, 10, 9, 8, 3, 6, 7, 10, 9, 8 };
    int[] key = { 3, 6, 10 };
    List<Integer> pos = new ArrayList<Integer>();
    for (int i = 0; i <= a.length - key.length; i++) {
        pos = getPosition(i, a, key);
        if (pos != null)
            System.err.println(pos);
    }
}

private static List<Integer> getPosition(int i, int[] a, int[] key) {
    int count = 0;
    List<Integer> p = new ArrayList<Integer>();
    for (int j = 0; i < a.length && j < key.length; i++, j++) {
        if (a[i] == key[j]) {
            count++;
            p.add(i);
        }
    }
    return count == key.length ? p : null;
}

Что произойдет, если у нас будет число больше 9?

Rahim Dastar 10.09.2018 09:25
    HashMap<Integer, Integer> maps = new HashMap<>();
    IntStream.range(0, target.length).forEach(i -> {
        maps.put(target[i], i);
    });
    Arrays.stream(src).forEach(i -> {
        System.out.println(maps.get(i));
    });

Сначала вычислите показатель, ему нравится группа по, но выбирайте только последнее. наконец, мы можем легко получить индекс из этого Хеш.

Не могли бы вы объяснить, что делают i-> {}? это синтаксис функционального языка? Я видел их только в Javascript. Я использую HashMap с индексами в качестве значений, спасибо

He Chuan 10.09.2018 10:25
char[]  key = {3, 8, 6};
    char[]  target = {3, 6, 8, 8, 6, 3, 8, 6, 2, 4};
    String keyStr = new String( key );
    String targetStr = new String( target );
    int start = targetStr.indexOf( keyStr );
    int[] resultArr = new int[key.length];
    int x = 0;
    for(int i = start; i< start + key.length; i++)
    {
        resultArr[ x] = i;
        x++;
    }
    System.out.println( Arrays.toString( resultArr ));

если вы хотите сопоставить несколько раз, используйте:

 char[] key = {3, 8, 6};
    char[] target = {3, 6, 8, 8, 6, 3, 8, 6, 2, 4, 3, 8, 6};
    String keyStr = new String( key );
    String targetStr = new String( target );

    Pattern pattern = Pattern.compile( keyStr );
    Matcher matcher = pattern.matcher( targetStr );
    // Check all occurrences
    while( matcher.find() )
    {
        System.out.print( "Start index: " + matcher.start() );
        System.out.print( " End index: " + matcher.end() );

        int start = matcher.start();
        int[] resultArr = new int[key.length];
        int x = 0;
        for( int i = start; i < start + key.length; i++ )
        {
            resultArr[x] = i;
            x++;
        }
        System.out.println( Arrays.toString( resultArr ) );
    }

Это интересный способ, быстрее или медленнее, чем при использовании HashMap?

He Chuan 10.09.2018 10:39

этот шаблон и сопоставление на самом деле очень интересны, никогда раньше не видели. Если бы я хотел поймать все вхождения, могу ли я просто выполнить targetStr? IndexOf (KeyStr, start + 1) и продолжать цикл до достижения target.length - key.length? Потому что каждый раз он сообщает первый индекс вхождения, и я мог бы просто key.length-1 к начальному индексу, чтобы выяснить следующее.

He Chuan 10.09.2018 10:52

Вы должны пройти через все элементы в «целевом» массиве, а также сохранить некоторый индекс, который будет следовать за текущим шаблоном совпадения из «ключевого» массива, давайте назовем этот индекс «keyIndex». Каждый раз, когда элемент из «целевого» массива равен элементу в позиции «keyIndex» из «ключевого» массива, вы увеличиваете keyIndex (текущий шаблон соответствия больше) и добавляете к некоторой структуре данных (я выбираю список ) индекс из "целевого" массива, в котором элементы равны. Если элементы не равны, вы должны сбросить «keyIdnex» (длина текущего шаблона совпадения равна нулю) и очистить список.

Я считаю, что это должно быть вам полезно:

        public static List<Integer> findPattern(int[] key , int[] target){
           List<Integer> result = new ArrayList<Integer>(); //This list hold the indexes of the patter

           int keyIndex = 0; //The index to follow after the "key" array
           for(int i = 0 ; i < target.length; i++){
               if(target[i] == key[keyIndex]){ //This "key" element is equal to the element from the "target"
                    result.add(i); //Add the index in which the elements are equal.
                    keyIndex++; //The currently match pattern is larger, increment "keyIndex"
                    if(result.size() == key.length) //The all pattern is checked and match, return the list which store the indexes
                        return result;
               }else{ //The pattern is not match anymore, reset all the data
                    keyIndex = 0;
                    i--;
                    result.clear();
              }
           }
           return null; //The pattern from "key" not found in "target" ,return null
        }

Спасибо за подробное объяснение, но я обнаружил проблему с кодом, он вернет null, если ключ равен {2,8,6}, а цель - {2,2,8,6}

He Chuan 10.09.2018 11:14

Спасибо за ваш комментарий. Я забыл уменьшить «i» в блоке else, чтобы снова начать сравнение с предыдущим элементом в «target». Решение отредактировано.

Michael_Sabbah 10.09.2018 12:06

Вы можете создать подмассивы вашего целевого массива с длиной вашего ключевого массива и сравнить каждый подмассив с ключом:

import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class OBJ {
    public static void main(String[] args){
        int[] key    = {3, 8, 6};
        int[] target = {3, 6, 8, 8, 6, 3, 8, 6, 2, 4};
        for(int i = 0; i < target.length - key.length; i++){
            int[] temp = Arrays.copyOfRange(target, i, i+key.length);
            if(Arrays.equals(key,temp)){
                String indices =  IntStream.range(i, i+key.length).mapToObj(e->String.valueOf(e)).collect(Collectors.joining(","));
                System.out.println(indices);
            }
        }
    }
}

Другие вопросы по теме