Личный технический блог:www.zhenganwen.top

Классический алгоритм

Алгоритм Манахера

оригинальный вопрос

Алгоритм Манахера происходит от названия «Нахождение длины самой длинной палиндромной подстроки в строке». НапримерabcdcbСамая длинная подстрока палиндромаbcdcb, длина которого равна 5.

Мы можем пройти каждый символ в строке. Когда символ пройден, сравните, совпадает ли соседний символ слева с соседним символом справа. Если они одинаковы, продолжайте сравнивать правый справа и слева налево.Та же ли левая сторона, если она такая же, продолжай сравнивать..., мы пока будем называть этот процесс внешним «расширением». Когда «расширение» не перемещается, подстрока, состоящая из всех пройденных символов, является самой длинной подстрокой палиндрома с центром на текущем пройденном символе.

Мы можем получить длину самой длинной подстроки палиндрома каждый раз при обходе и использовать глобальную переменную для сохранения наибольшей.После обхода мы можем получить решение этой задачи. Но проанализируйте временную сложность этого метода: когда дело доходит до первого символа, он может расширяться только на один; когда дело доходит до второго символа, он может расширяться максимум на два; ...; до середины строковый символ, расширять не более(n-1)/2+1поэтому временная сложность1+2+……+(n-1)/2+1которыйO(N^2). Но алгоритм Манахера может сделатьO(N).

В алгоритме Манахера определены следующие понятия:

• Палиндромный радиус: максимальное количество символов, на которое символ в строке может расширяться наружу, называется палиндромным радиусом символа. НапримерabcdcbКитайские символыd, может расширитьc, и еще одинb, а затем расширить до правой границы строки, а затем считать сам символ, символdРадиус палиндрома равен 3.
• Массив палиндромного радиусаpArr: Длина совпадает с длиной строки, сохраняя радиус палиндрома каждого символа в строке. НапримерcharArr="abcdcb",вcharArr[0]='a'Ни один из них не может быть расширен, но у него есть своиpArr[0]=1;а такжеcharArr[3]='d'Расширение до 2, включая собственноеpArr[3]=3.
• крайний правый палиндром правая границаR: Нижний индекс самого правого символа, расширенный операцией «расширить» в процессе обхода. НапримерcharArr=“abcdcb”, при переходе кa, может только расширятьсяaсам по себе не может расширяться наружу, поэтомуR=0Когда траверсbможно только расширитьbсам, так обновиR=1; но при переходе кd, расширяет два символа наружу доcharArr[5]=b,такRОбновление до 5.
• Центр палиндрома, соответствующий правой границе самого правого палиндромаC:Cа такжеRсоответствуют и обновляются одновременно. Напримерabcdcbпройти кdчас,R=5,Cто естьcharArr[3]='d'индекс3.

Разберитесь с проблемой, что длина подстроки палиндрома четна: возьмите приведенное вышеabcdcbНапример, гдеbcdcbпринадлежит палиндрому, но что, если длина палиндрома четна? картинаcabbac, по определенной выше логике "расширения" радиус палиндрома каждого символа равен 0, а на самом делеcabbacДлина самой длинной подстроки палиндрома равна 6. Поскольку логика «расширения» выше заключается в том, чтобы по умолчанию обрабатывать подстроку палиндрома как строку нечетной длины, нам нужно обработать строку перед использованием алгоритма Манахера.Вот небольшой трюк, который заключается в обработке строки Специальный символ добавляется между началом и концом и каждым символом, так что входная строка может быть равномерно преобразована в строку нечетной длины. НапримерabbaПосле обработки в#a#b#b#a, то естьcharArr[4]='#'Радиус палиндрома равен 4, то есть максимальная длина палиндромной подстроки исходной строки равна 4. Соответствующий код выглядит следующим образом:

public static char[] manacherString(String str){
  char[] source = str.toCharArray();
  char chs[] = new char[str.length() * 2 + 1];
  for (int i = 0; i < chs.length; i++) {
    chs[i] = i % 2 == 0 ? '#' : source[i / 2];
  }
  return chs;
}

Затем проанализируйте, как алгоритм BFPRT использует вычисления в процессе обхода.pArr,R,Cдля ускорения решения палиндрома радиусов последующих символов.

Во-первых, случай 1 состоит в том, что пройденный символьный индексcurсуществуетRсправа от (изначально другойR=-1), максимальный радиус палиндрома персонажа в данном случаеpArr[cur]Решение не может быть ускорено, и может быть решено только путем расширения наружу шаг за шагом.

Случай 2 состоит в том, что пройденный символьный индексcurсуществуетRналево, когдаpArr[cur]Процесс решения может быть ускорен за счет использования ранее пройденной информации о радиусе палиндрома символов. делать отдельноcur,RоCточка симметрииcur'а такжеL:

• если изcur'Левая граница расширяющегося наружу наибольшего диапазона не превышаетL,ТакpArr[cur]=pArr[cur'].

  

  Доказательство следующее:

  

  Так как он был пройден раньшеcur'Символ на позиции, поэтому у нас есть запись о количестве шагов, которые можно развернуть на этой позиции (pArr[cur']), то естьcur'+pArr[cur']персонаж вy'не равноcur'-pArr[cur']персонаж вx'из. согласно сRа такжеCопределение, весьLприбытьRАссортимент символов примерноCсимметричный, то естьcurНаибольшая подстрока палиндрома, которую можно расширить иcur'Максимальные палиндромные подстроки, которые могут быть расширены, одинаковы, поэтому их можно получить напрямую.pArr[cur]=pArr[cur'].

• если изcur'Левая граница наибольшего расширяющегося экстента превышаетL,ТакpArr[cur]=R-cur+1.

  

  Доказательство следующее:

  

  Rодин символ вправоx,xоcurсимметричные персонажиy,x,yоCсимметричные персонажиx',y'. согласно сC,Rопределение имеетx!=x';из-заx',y'вcur'находится внутри палиндромной подстроки с центром вcur'симметричный, поэтому естьx'=y', можно запускатьx!=y';опять такиy,y'оCсимметричный иL,Rвнутри так и естьy=y'. Таким образом, естьx!=y,следовательноcurРадиус палиндромаR-cur+1.

• кcur'Левая граница наибольшего диапазона, расширяющегося наружу от центра, точноL,ТакpArr[cur] >= （R-cur+1）

  

  В этой ситуации,cur'Диапазон, который можно расширить,cur'-L, что соответствуетcurДиапазон, который можно расширить,R-cur. ноcurВозможность дальнейшего расширения зависит отxа такжеyравны. И предпосылки, которые мы можем получить, это толькоx!=x',y=y',x'!=y', нельзя вывестиx,yотношения, только знаюcurРадиус палиндрома минимума равенR-cur+1(включая самого себя), вам нужно продолжать попытки масштабирования, чтобы решитьpArr[cur].

В итоге,pArr[cur]Есть четыре случая для расчета: сильное расширение, равноеpArr[cur'],равныйR-cur+1,отR-cur+1Продолжайте расширяться наружу. Решение исходной проблемы с использованием этого алгоритма заключается в переборе каждого символа в строке, пытаясь масштабировать до максимума и обновляя каждый символ.R(только увеличивать, но не уменьшать), каждый разRВеличина увеличения — это количество символов, которое можно увеличить на этот раз, иRРешение задачи можно определить при достижении конца строки, поэтому временная сложность равна сумме количества проверок для каждой операции расширения, т. е.RДиапазон изменений (-1~2N, так как обработка строк добавляетN+1индивидуальный#символов), т.е.O(1+2N)=O(N).

Общий код выглядит следующим образом:

public static int maxPalindromeLength(String str) {
  char charArr[] = manacherString(str);
  int pArr[] = new int[charArr.length];
  int R = -1, C = -1;
  int max = Integer.MIN_VALUE;
  for (int i = 0; i < charArr.length; i++) {
    pArr[i] = i > R ? 1 : Math.min(pArr[C * 2 - i], R - i);
    while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
      if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
        pArr[i]++;
      } else {
        break;
      }
    }
    if (R < i + pArr[i]) {
      R = i + pArr[i]-1;
      C = i;
    }
    max = Math.max(max, pArr[i]);
  }
  return max-1;
}

public static void main(String[] args) {
  System.out.println(maxPalindromeLength("zxabcdcbayq"));
}

Приведенный выше код объединяет обработку ветвей четырех случаев в7~14Ряд. из которых7Строка предназначена для определения информации об ускорении: если текущий символ обхода находится вRСправа сначала посчитайте себя с помощьюpArr[i]=1, проверьте позже, можно ли его расширить, а затем напрямуюpArr[i]++может; в противном случае текущий персонажpArr[i]либоpArr[i'](iоCсимметричный нижний индексi'Формула вывода2*C-i), или любойR-i+1, либо>=R-i+1, можно сначалаpArr[i]Значение установлено наименьшее из трех случаев, а затем проверьте позже, можно ли его расширить, а затем напрямуюpArr[i]++Вот и все.

наконец получилmaxэто обработанная строка (length=2N+1), радиус самой длинной палиндромной подстроки,max-1Точно равна длине самой длинной подстроки палиндрома в исходной строке.

сложные вопросы

Вам предлагается добавить в строку как можно меньше символов, чтобы она стала палиндромом.

идея: когдаRДостигнув конца строки в первый раз, выполнитеRоCточка симметрииL,будетLРезультатом является обратный порядок предыдущей строки.

Алгоритм BFPRT

Вопрос: Дан массив целых чисел, вернуть в нем k-е наименьшее число.

Эту проблему можно решить с помощью голландского флага.partitionИ идея случайной быстрой сортировки: случайным образом выбрать число, и разделить массив на<,=,>три части, то=Нетрудно узнать наименьшее число части числа в массиве, а затем для<(если K-е наименьшее число находится в<часть) или>(если K-е наименьшее число находится в>часть) рекурсивно процесс до тех пор, пока количество частей=Номер детали — это точно K-е наименьшее число во всем массиве. При таком подходе нетрудно получить математическое ожидание временной сложности, посколькуO(NlogN)(На основе 2). Но в конце концов это математическое ожидание, и производительность в реальной инженерии может быть необъективной, а временная сложность алгоритма BFPRT может бытьO(NlogN).

Алгоритм BFPRT сначала делит массив на группы по 5 элементов.N/5Небольшая часть (последние менее 5 элементов сами по себе образуют часть), затем отсортируйте внутреннюю часть этих маленьких частей, а затем возьмите медиану каждой маленькой части, а затем отсортируйте, чтобы получить медиану:

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

O(NlogN)доказательство того, почему каждый раундpartitionПосле того, как случайный выбор в BFPRT изменен на логику выбора, определенную BFPRT, временная сложность этой задачи полностью становитсяO(NlogN)какие? Разберем шаги этого алгоритма:

Алгоритм BFPRT, получает массив и значение K, возвращает число в массиве

1. Массив делится наN/5Мелкие детали, для сортировки требуется 5 номеров каждой деталиO(1), все части должны быть выровненыO(N/5)=O(N)
2. Возьмите медиану каждой дроби, всегоN/5число, рекурсивно вызовите алгоритм BFPRT, чтобы получить количество этих чисел(N/5)/2Небольшие числа (т.е. медиана этих чисел), обозначаемые какpivot
3. кpivotДля сравнения разделите весь массив на<pivot , =pivot , >pivotтри области
4. Определить, в какой области находится K-е наименьшее число, если оно находится в=область возвращается напрямуюpivot, если в<или>область, затем рекурсивно вызвать алгоритм BFPRT с номером этой области
5. base case: Когда алгоритм BFPRT вызывается рекурсивно, обнаруживается, что в этой области есть только одно число, тогда это число и есть число, которое мы ищем.

Пример кода:

public static int getMinKthNum(int[] arr, int K) {
  if (arr == null || K > arr.length) {
    return Integer.MIN_VALUE;
  }
  int[] copyArr = Arrays.copyOf(arr, arr.length);
  return bfprt(copyArr, 0, arr.length - 1, K - 1);
}

public static int bfprt(int[] arr, int begin, int end, int i) {
  if (begin == end) {
    return arr[begin];
  }
  int pivot = medianOfMedians(arr, begin, end);
  int[] pivotRange = partition(arr, begin, end, pivot);
  if (i >= pivotRange[0] && i <= pivotRange[1]) {
    return arr[i];
  } else if (i < pivotRange[0]) {
    return bfprt(arr, begin, pivotRange[0] - 1, i);
  } else {
    return bfprt(arr, pivotRange[1] + 1, end, i);
  }
}

public static int medianOfMedians(int[] arr, int begin, int end) {
  int num = end - begin + 1;
  int offset = num % 5 == 0 ? 0 : 1;
  int[] medians = new int[num / 5 + offset];
  for (int i = 0; i < medians.length; i++) {
    int beginI = begin + i * 5;
    int endI = beginI + 4;
    medians[i] = getMedian(arr, beginI, Math.min(endI, end));
  }
  return bfprt(medians, 0, medians.length - 1, medians.length / 2);
}

public static int getMedian(int[] arr, int begin, int end) {
  insertionSort(arr, begin, end);
  int sum = end + begin;
  int mid = (sum / 2) + (sum % 2);
  return arr[mid];
}

public static void insertionSort(int[] arr, int begin, int end) {
  if (begin >= end) {
    return;
  }
  for (int i = begin + 1; i <= end; i++) {
    for (int j = i; j > begin; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1);
      } else {
        break;
      }
    }
  }
}

public static int[] partition(int[] arr, int begin, int end, int pivot) {
  int L = begin - 1;
  int R = end + 1;
  int cur = begin;
  while (cur != R) {
    if (arr[cur] > pivot) {
      swap(arr, cur, --R);
    } else if (arr[cur] < pivot) {
      swap(arr, cur++, ++L);
    } else {
      cur++;
    }
  }
  return new int[]{L + 1, R - 1};
}

public static void swap(int[] arr, int i, int j) {
  int tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

public static void main(String[] args) {
  int[] arr = {6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9};
  System.out.println(getMinKthNum(arr,13));
}

Временная сложностьO(NlogN)(база 2) доказательство, анализbfprtэтапы выполнения (при условииbfprtВременная сложностьT(N)):

1. Сначала соберите 5 групп по 5 и отсортируйте их внутри, отсортируйте 5 чисел какO(1), все группы отсортированы какO(N/5)=O(N)
2. Нарисуйте медиану из каждой группы на шаге 1, чтобы сформировать медианную группу с общим количествомN/5номер, рекурсивный вызовbfprtспроси об этомN/5номер(N/5)/2Малое число (т.е. медиана) равноT(N/5), обозначаемый какpivot
3. для шага 2pivotДля сравнения, массив разделен на меньше, равно и больше трех областей, потому чтоpivotявляется медианой в медианной группе, поэтому медианная группа имеетN/5/2=N/10соотношение чиселpivotмаленький, этоN/10Числа являются соответственно медианой определенной группы на шаге 1, и можно сделать вывод, что существует по крайней мере3N/10соотношение чиселpivotнебольшой, то есть не более7N/10соотношение чиселpivotбольшой. То есть больше площади (или меньше) максимума содержит7N/10число, по крайней мере3N/10номер, то еслиiКогда большие числа не находятся в равной области, либо рекурсияbfprtНезависимо от того, нужно ли иметь дело с областью меньше или больше, размер подпроцесса в наихудшем случае не превышает7N/10,СейчасT(7N/10)

В итоге,bfprtизT(N)Есть формула вывода:T(N/5)+T(7N/10)+O(N). согласно сОсновыФормула Мастера, представленная в, может быть полученаbfprtВременная сложностьO(NlogN)(На основе 2).

Двоичное дерево Морриса Траверса

Рекурсивная и нерекурсивная версии обхода бинарного дерева в прямом, прямом и обратном порядке упоминаются в [Прямой алгоритм BAT (базовый)], но временная сложность этих шести алгоритмов обхода требуетO(H)(вHДополнительная пространственная сложность высоты дерева), потому что процесс обхода бинарного дерева может только просматривать дочерний узел и не может возвращаться к родительскому узлу, поэтому эти алгоритмы используют стек для сохранения родительского узла для возврата (суть рекурсии что система помогает нам прессовать стек), а стек должен вмещать не менееHэлементы (например, возврат к родительскому узлу при переходе к конечному узлу, убедитесь, что все его родительские узлы находятся в стеке). Временная сложность обхода Морриса по-прежнемуO(N)Дополнительная пространственная сложность в случаеO(1).

Правила обхода

Во-первых, прежде чем вводить обход Морриса, давайте забудем правила, определяемые предварительным порядком, порядком и пост-порядком.Например, в предварительном обходе после получения дерева сначала проходите головной узел, затем левое поддерево и, наконец, правое поддерево, причем обход поддерева остается таким во время обхода.

Забыв эти правила обхода, давайте посмотрим на критерии, определяемые обходом Морриса:

1. определить указатель обходаcur, указатель сначала указывает на головной узел
2. судитьcurЛевое поддерево ?
   • еслиcurЛевый дочерний элемент пустой, что указываетcurЛевое поддерево не существует, тоcurдвигаться вправо кcur.right
   • еслиcurЛевый дочерний элемент не равен нулю, что указывает наcurЛевое поддерево существует, найдите самый правый узел левого поддерева, обозначенный какmostRight
     • если,mostRightправый дочерний элемент пуст, тогда пусть он указывает наcur(mostRight.right=cur), и сдвиг влевоcur(cur=cur.left)
     • еслиmostRightПравый потомок не пуст, тогда пустьcurсдвиг вправо (cur=cur.right), и воляmostRightправильный ребенок
3. После шага 2, еслиcurне пусто, то продолжайтеcurПереходим к шагу 2, иначе обход заканчивается.

На следующем рисунке показан пример, демонстрирующий весь процесс обхода Морриса:

предварительный заказ, неупорядоченная последовательность

После завершения обходаcurПосле небольшой обработки введенной последовательности узлов легко получить предпорядковую и неупорядоченную последовательность бинарного дерева:

Образец кода:

public static class Node {
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data;
    }
}

public static void preOrderByMorris(Node root) {
    if (root == null) {
        return;
    }
    Node cur = root;
    while (cur != null) {
        if (cur.left == null) {
            System.out.print(cur.data+" ");
            cur = cur.right;
        } else {
            Node mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                System.out.print(cur.data+" ");
                mostRight.right = cur;
                cur = cur.left;
            } else {
                cur = cur.right;
                mostRight.right = null;
            }
        }
    }
    System.out.println();
}

public static void mediumOrderByMorris(Node root) {
    if (root == null) {
        return;
    }
    Node cur = root;
    while (cur != null) {
        if (cur.left == null) {
            System.out.print(cur.data+" ");
            cur = cur.right;
        } else {
            Node mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            } else {
                System.out.print(cur.data+" ");
                cur = cur.right;
                mostRight.right = null;
            }
        }
    }
    System.out.println();
}

public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    preOrderByMorris(root);
    mediumOrderByMorris(root);

}

Здесь стоит отметить:обход Морриса придет к узлу, левый дочерний элемент которого не является пустым дважды, в то время как другие узлы проходят только один раз. Следовательно, при использовании обхода Морриса для печати последовательности предварительного порядка, если у приходящего узла нет левого дочернего элемента, он может быть напечатан напрямую (этот тип узла будет проходить через него только один раз), в противном случае, если самый правый узел левого поддерева узел приходит Правый дочерний элемент узла не печатается до тех пор, пока он не станет пустым (это первый раз, когда он приходит к узлу), поэтому он игнорируетсяcurУзел, который появляется во второй раз в переданной последовательности узлов; при использовании Морриса для обхода и печати последовательности по порядку, если у приходящего узла нет левого дочернего элемента, то распечатайте его напрямую (этот тип узла будет проходить только один раз). , левый, средний, правый , без левого, вывести сразу), иначе, если крайний правый узел левого поддерева пришедшего к нему узла не пуст, он будет напечатан (это второй раз, чтобы прийти к узел), так что игнорируетсяcurПервое вхождение повторяющегося узла в последовательности переданных узлов.

пост-последовательность

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

Но на самом деле в процессе обхода Морриса, если каждый раз встречать узел, проходящий через второй раз, печатается узел на правой границе левого поддерева узла снизу вверх, и, наконец, все дерево Печатается правая граница числа снизу вверх, и, наконец, это последовательность этого числа в обратном порядке:

Среди них не что иное, как выполнение операции печати во время второго узла, пройденного в обходе Морриса. Чтобы напечатать правую границу дерева снизу вверх, узлы на правой границе можно рассматривать какrightУказатель представляет собой связанный список указателей-преемников, переверните егоreverseЗатем распечатайте и, наконец, восстановите исходную структуру. Пример кода выглядит следующим образом (где подверженное ошибкам место18линия и19строки кода нельзя поменять местами):

public static void posOrderByMorris(Node root) {
    if (root == null) {
        return;
    }
    Node cur = root;
    while (cur != null) {
        if (cur.left == null) {
            cur = cur.right;
        } else {
            Node mostRight = cur.left;
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
            } else {
                mostRight.right = null;
                printRightEdge(cur.left);
                cur = cur.right;
            }
        }
    }
    printRightEdge(root);
}

private static void printRightEdge(Node root) {
    if (root == null) {
        return;
    }
    //reverse the right edge
    Node cur = root;
    Node pre = null;
    while (cur != null) {
        Node next = cur.right;
        cur.right = pre;
        pre = cur;
        cur = next;
    }
    //print 
    cur = pre;
    while (cur != null) {
        System.out.print(cur.data + " ");
        cur = cur.right;
    }
    //recover
    cur = pre;
    pre = null;
    while (cur != null) {
        Node next = cur.right;
        cur.right = pre;
        pre = cur;
        cur = next;
    }
}

public static void main(String[] args) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    posOrderByMorris(root);
}

анализ временной сложности

Поскольку при обходе Морриса только узел, левый дочерний элемент которого не пуст, пройдет дважды, а другие узлы пройдут только один раз, то есть количество обходов меньше, чем2N, поэтому временная сложность использования обхода Морриса для получения последовательностей в прямом и прямом порядке, естественно, одинакова.O(1); но также учитывается временная сложность генерации последовательности пост-заказаprintRightEdgeВременная сложность , но вы обнаружите, что в течение всего процесса обхода всеprintRightEdgeЭто сводится к простому обходу и печатиNузлы:

Таким образом, временная сложность по-прежнемуO(N).

Порядок, в котором Моррис обходит узлы, не является предварительным, порядковым и обратным, но определяет, какой узел следует обходить следующим, в соответствии с собственным набором критериев.

Уникальная особенность обхода Морриса заключается в том, что он полностью использует недопустимую ссылку конечного узла (ссылка указывает на пустую, но ссылочная переменная все еще занимает память), тем самым реализуяO(1)временная сложность.

Суммируйте самую длинную длину подмассива цели

Пример: массив[7,3,2,1,1,7,-6,-1,7]в и для7Самый длинный подмассив длины равен 4. (подмассив: массив любого количества последовательных чисел в массиве)

Основная предпосылка: если мы найдем подмассив, сумма которого равна цели, среди всех подмассивов, оканчивающихся на каждое число в массиве, то ответ должен быть в нем.

Правило: для массивов[i,……,k,k+1,……,j], если искомая цель равна 800 и мы знаем изiдобавить кjНарастающим итогом является 2000, то отiНачать накапливать в обратном порядке, если накоплено доkКогда общая сумма достигает 1200, тоk+1~jЭто самый длинный подмассив с совокупной суммой 800 во всем массиве.

Шаги: с[7,3,2,1,1,7,-6,-3,7],aim=7Например,

• Первое место(0,-1)положить вHashMap, накопленная сумма, представляющая 0, появляется до того, как она была пройдена.->(0,-1)
• Затем каждый раз, когда число проходится, накопленная сумма, образованная позицией, сохраняется вHashMap,Напримерarr[0]=7, накопленная сумма, сформированная в позиции 0, является накопленной суммой, сформированной в предыдущей позиции0плюс на этой позиции7, так будет(7,0)положить вHashMapСередина указывает на то, что накопленная сумма, сформированная в первый раз на позиции 0, равна7, затем вычтите накопленную сумму в этом местеaim,Сейчас7-7=0, найти позицию, в которой накопленная сумма впервые равна 0, т.е.-1, поэтому самый длинный подмассив с суммой целей в подмассивах, оканчивающихся на нижний индекс 0, равен0~0,Сейчас7Один элемент, помните максимальную длинуmaxLength=1.->(7,0)
• Потомarr[1]=3, накопленная сумма, сформированная на позиции 1, равна7+3=10,HashMapНет вkeyза10записи, так что ставьте(10,1)Указывает, что самая ранняя накопленная сумма, сформированная в позиции 1, равна 10, а затем накопленная сумма в этой позиции вычитается.aimкоторый10-7=3,прибытьHashMapнайти любойkeyза3(есть ли какая-либо позиция, которая образует самую раннюю накопленную сумму 3), и обнаружили, что нет, поэтому в подмассиве, оканчивающемся индексом 1, нет накопленной суммы.aimиз.->(10,1)
• Потомarr[2]=2, накопленная сумма, образованная на позиции 2, равна10+2=12,HashMapНет вkeyза12записи, так что ставьте(12,2),sum-aim=12-7=5,прибытьHashMapнайти любойkeyза5, обнаружил, что записи нет, значит, в подмассиве, оканчивающемся индексом 2, нет накопительной суммыaimиз.->(12,2)
• приходитьarr[3]=1, положить в(13,3),sum-aim=5, подмассив, заканчивающийся нижним индексом 3, не имеет кумулятивной суммы для прицеливания.->(13,3)
• приходитьarr[4]=1, положить в(14,4),sum-aim=7,ОбнаружитьHashMapимеютkey=7запись о(7,0), то есть кумулятивная сумма в позиции 0 может достигать 7, поэтому1~4представляет собой кумулятивную сумму в подмассиве, оканчивающемся индексом 4, как7самый длинный подмассив , обновитьmaxLength=4.->(14,4)
• приходитьarr[5]=7, положить в(21,5),sum-aim=14,HashMapимеют(14,4),следовательно5~5является самым длинным подмассивом этого раунда, ноmaxLength=4>1, поэтому не обновляется.->(21,5)
• приходитьarr[6]=-6, положить в15,6, нет совпадающих подмассивов.->(15,6)
• приходитьarr[7]=-1, совокупная сумма15+(-1)=14,ноHashMapимеютkey=14записи, так что не ставьте(14,7)(HashMapСохраняется в позиции, в которой впервые появляется накопленная сумма, а накопленная сумма 14 появляется не раньше, чем в нижнем индексе 4).sum-aim=7,HashMapимеют(7,0), поэтому самый длинный подмассив в этом раунде равен1~7, так что обновитеmaxLength=7.
• приходитьarr[8]=7, кумулятивная сумма равна 21, и есть запись с ключом 21, поэтому (21, 7) не ставится.sum-aim=14, самый длинный подмассив в этом раунде5~8, длина 4, без обновленияmaxLength.

Образец кода:

public static int maxLength(int[] arr,int aim) {
    //key->accumulate sum   value->index
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    hashMap.put(0, -1);
    int curSum = 0;
    int maxLength = 0;
    for (int i = 0; i < arr.length; i++) {
        curSum += arr[i];
        if (!hashMap.containsKey(curSum)) {
            hashMap.put(curSum, i);
        }
        int gap = curSum - aim;
        if (hashMap.containsKey(gap)) {
            int index = hashMap.get(gap);
            maxLength = Math.max(maxLength, i - index);
        }
    }
    return maxLength;
}

public static void main(String[] args) {
    int arr[] = {7, 3, 2, 1, 1, 7, -6, -1, 7};
    int aim = 7;
    System.out.println(maxLength(arr, aim));//7
}

расширять

Найдите длину самого длинного подмассива с одинаковыми нечетными и четными числами

Установите для нечетного числа значение 1, а для четного числа значение -1, которое преобразуется в самую длинную длину подмассива, которая в сумме равна 0.

Найдите самый длинный подмассив с одинаковым количеством единиц и двоек (массив содержит только 0, 1 и 2 элемента)

Установка 2 в -1 преобразует его в длину самого длинного подмассива, который в сумме равен 0

Передовой

В схеме деления массива произвольно, сколько после деления подмассивов имеет сумму XOR не более 0

Пример: дать вам массив[1,2,3,0,2,3,1,0], вы должны разделить как[1,2,3],[0],[2,3,1],[0], ответ 4.

главная предпосылка: Если мы узнаем максимальное количество подмассивов, у которых сумма XOR равна 0 во всех подмассивах, заканчивающихся каждым числом в массиве после произвольного деления, то ответ должен быть в нем.

закон: операция XOR соответствует коммутативным и ассоциативным законам.0^N=N,N^N=0.

Анализ возможностей: для массива[i，……，j，m，……，n,k], предполагая, что несколько подмассивов формируются после оптимального разделения в соответствии со смыслом вопроса, k как последний элемент всего массива также должен быть последним элементом последнего подмассива. Последний подмассив будет иметь только два случая: сумма XOR не равна 0, сумма XOR равна 0.

• Если первое, то даже если элемент k будет удален из последнего подмассива, сумма XOR не будет равна 0, иначе оптимальное деление разделит последний подмассив на два подмассива, где k — отдельный подмассив. Например, последний подмассивindexOf(m)~indexOf(k), чья сумма XOR не равна 0, тоdp[indexOf(k)]=dp[indexOf(k)-1], представляющий массив0~indexOf(k)решение и его подмассивы0~(indexOf(k)-1)Решение такое же.->case 1
• Если это последнее, то не может быть меньшего k-терминированного подмассива с суммой XOR, равной 0, в последнем подмассиве. Например, последний подмассивindexOf(m)~indexOf(k), его сумма XOR равна 0, тоdp[indexOf(k)]=dp[indexOf(m)-1]+1, представляющий массив0~indexOf(k)решение = подмассив0~(indexOf(m)-1)+1 за решение.->case 2

Образец кода:

public static int maxSubArrs(int[] arr) {
    if (arr == null) {
        return 0;
    }
    HashMap<Integer, Integer> map = new HashMap();
    map.put(0, -1);
    int curXorSum = 0;
    int res = 0;
    int[] dp = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        curXorSum ^= arr[i];
        //case 1，之前没有出现过这个异或和，那么该位置上的dp等于前一个位置的dp
        if (!map.containsKey(curXorSum)) {
            dp[i] = i > 0 ? dp[i - 1] : 0;
        } else {
            //case 2，之前出现过这个异或和，那么之前这个异或和出现的位置到当前位置形成的子数组异或和为0
            int index = map.get(curXorSum);
            dp[i] = index > 0 ? dp[index] + 1 : 1;
        }
        //把最近出现的异或和都记录下来，因为要划分出最多的异或和为0的子数组
        map.put(curXorSum, i);
    }
    //最后一个位置的dp就是整个问题的解
    return dp[dp.length -1];
}

public static void main(String[] args) {
    int arr[] = {1, 2, 3, 0, 2, 3, 1, 0,4,1,3,2};
    System.out.println(maxSubArrs(arr));
}

Очень рутинная проблема сбора информации о бинарном дереве

Найдите максимальное количество узлов в бинарном дереве для поиска бинарного поддерева

Максимальное двоичное поддерево поиска относится к поддереву двоичного дерева, которое является двоичным деревом поиска и имеет наибольшее количество узлов.

Такие вопросы обычно имеютглавная предпосылка:Если предположить, что для поддерева с любым узлом в дереве в качестве головного узла мы можем найти максимальное количество узлов в бинарном поддереве поиска, то ответ должен быть в нем.

Для поддерева с любым узлом в качестве головного узла решение максимального бинарного поддерева поиска разбивается на три случая (перечислить возможности):

• Максимальное бинарное поддерево поиска всего дерева находится в левом поддереве. Это требует, чтобы бинарное поддерево максимального поиска существовало в его левом поддереве, а его правое поддерево не существовало.
• Максимальное бинарное поддерево поиска всего дерева находится в правом поддереве. Для этого требуется, чтобы в его правом поддереве существовало бинарное поддерево максимального поиска, а в левом поддереве - нет.
• Максимальное бинарное поддерево поиска всего бинарного дерева — это оно само. Для этого требуется, чтобы его левое поддерево было двоичным поддеревом поиска, а максимальный узел левого поддерева был меньше головного узла, а его правое поддерево было двоичным поддеревом поиска, а минимальное значение правого поддерева было меньше головного узла. Узел большой.

Чтобы различать эти три случая, нам необходимо собрать информацию:

• Существует ли максимальное бинарное дерево поиска в поддереве
• головной узел поддерева
• максимальный узел поддерева
• Минимальный узел поддерева

Итак, мы можем начать нашу процедуру роста:

1. Инкапсулируйте информацию, которую нужно собрать из поддерева, вReturnData, который представляет информацию, которая должна быть возвращена вышестоящему после обработки этого поддерева.
2. Предположим, я использую подпроцесс для сбора информации о поддереве, а затем обрабатываю всю информацию, которую текущее дерево должно предоставить вышестоящему в соответствии с информацией о поддереве и ситуации, указанной при анализе проблемы. , и вернуть его вышестоящему (Интеграция информации).
3. Конечноbase case, подпроцесс останавливается, когда поддерево становится пустым.

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

public static class Node{
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data;
    }
}

public static class ReturnData {
    int size;
    Node head;
    int max;
    int min;
    public ReturnData(int size, Node head, int max, int min) {
        this.size = size;
        this.head = head;
        this.max = max;
        this.min = min;
    }
}

public static ReturnData process(Node root) {
    if (root == null) {
        return new ReturnData(0, null, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    ReturnData leftInfo = process(root.left);
    ReturnData rightInfo = process(root.right);
    
    //case 1
    int leftSize = leftInfo.size;
    //case 2
    int rightSize = rightInfo.size;
    int selfSize = 0;
    if (leftInfo.head == root.left && rightInfo.head == root.right
        && leftInfo.max < root.data && rightInfo.min > root.data) {
        //case 3
        selfSize = leftInfo.size + rightInfo.size + 1;
    }
    int maxSize = Math.max(Math.max(leftSize, rightSize), selfSize);
    Node maxHead = leftSize > rightSize ? leftInfo.head : 
    				selfSize > rightSize ? root : rightInfo.head;
    
    return new ReturnData(maxSize, maxHead, 
                          Math.max(Math.max(leftInfo.max, rightInfo.max), root.data), 
                          Math.min(Math.min(leftInfo.min, rightInfo.min), root.data));
}

public static void main(String[] args) {
    Node root = new Node(0);
    root.left = new Node(5);
    root.right = new Node(1);
    root.left.left = new Node(3);
    root.left.left.left = new Node(2);
    root.left.left.right = new Node(4);
    System.out.println(process(root).size);//4
}

Найдите самое длинное расстояние в бинарном дереве

Если в бинарном дереве, начиная с узла А, Сяомин может подняться к своему родительскому узлу и спуститься к своему дочернему узлу, то Сяомин должен пройти от узла А к узлу В как минимум через количество узлов (включая А и В) называется расстоянием от А до В. Среди расстояний, образованных любыми двумя узлами, наибольшее называется максимальным расстоянием дерева.

Очень рутинный:

Основная посылка: если для поддерева с любым узлом дерева в качестве головного узла, если мы можем найти максимальное расстояние всех этих поддеревьев, то ответ находится в нем.

Для любого поддерева дерева решение максимального расстояния разбивается на следующие три случая:

• Максимальное расстояние этого дерева равно максимальному расстоянию левого поддерева.
• Максимальное расстояние этого дерева равно максимальному расстоянию правого поддерева.
• Максимальное расстояние дерева — от самого глубокого узла левого поддерева через головной узел дерева до самого глубокого узла правого поддерева.

Информация для сбора из поддерева:

• Максимальное расстояние поддерева
• глубина поддерева

Образец кода:

public static class Node{
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data;
    }
}

public static class ReturnData{
    int maxDistance;
    int height;
    public ReturnData(int maxDistance, int height) {
        this.maxDistance = maxDistance;
        this.height = height;
    }
}

public static ReturnData process(Node root){
    if (root == null) {
        return new ReturnData(0, 0);
    }
    ReturnData leftInfo = process(root.left);
    ReturnData rightInfo = process(root.right);

    //case 1
    int leftMaxDistance = leftInfo.maxDistance;
    //case 2
    int rightMaxDistance = rightInfo.maxDistance;
    //case 3
    int includeHeadDistance = leftInfo.height + 1 + rightInfo.height;

    int max = Math.max(Math.max(leftMaxDistance, rightMaxDistance), includeHeadDistance);
    return new ReturnData(max, Math.max(leftInfo.height, rightInfo.height) + 1);
}

public static void main(String[] args) {
    Node root = new Node(0);
    root.left = new Node(5);
    root.right = new Node(1);
    root.right.right = new Node(6);
    root.left.left = new Node(3);
    root.left.left.left = new Node(2);
    root.left.left.right = new Node(4);
    System.out.println(process(root).maxDistance);
}

Очень рутинно: перечислить возможности -> интегрировать информацию, которая должна быть возвращена этим процессом, из информации, собранной подпроцессом -> вернуть

Максимальная активность в танце

Взаимоотношения между начальством и подчиненными компании - это многоразветвленное дерево Эта компания хочет провести вечеринку Вы как организатор уже разобрались в психологии каждого:сотрудник Если начальник присутствует, сотрудник точно не придет. У каждого сотрудника есть значение активности (чем выше значение, тем активнее партия),Вы можете отправить приглашение сотруднику, чтобы решить, кто придет, как сделать атмосферу танца максимально активной? Возвращает наибольшее активное значение.

Пример:

Если вы пригласите прийти А, то его прямой подчиненный BCD точно не придет.Вы можете пригласить любого из EFGHJKL.Если вы пригласите их всех, то максимальная активность танцевальной вечеринки составитA(2)+E(9)+F(11)+G(2)+H(4)+J(7)+K(13)+L(5); но если вы решите не приглашать A прийти, то вы можете пригласить любого из его прямых подчиненных BCD.Например, если вы пригласите B, но не CD, то прямой подчиненный B E точно не вернется, но вы можете выберите прямого подчиненного CD.

главная предпосылка: Если вы знаете влияние каждого работника, пришедшего или не пришедшего на танец, на значение танцевальной активности, то максимальное значение активности танцевальной вечеринки узнать несложно. Например, пригласить ли А приехать зависит от: Прийти или не пригласить Б выбрать того, кто получит наибольшую выгоду от значения активности стороны в двух случаях + Прийти или не приехать С. В этих двух случаях выбрать один что увеличивает самую активную ценность танца, точно так же для любого работника, пригласить его или нет использовать это решение.

перечислить возможности: приходить или не приходить.

Информация, собираемая подпроцессом: Возвращает большее значение значения прироста активного значения дочернего сотрудника для выпускного вечера и значения усиления для неявившегося на выпускной вечер.

Образец кода:

public static class Node{
    int happy;
    List<Node> subs;
    public Node(int happy) {
        this.happy = happy;
        this.subs = new ArrayList<>();
    }
}

public static class ReturnData {
    int maxHappy;
    public ReturnData(int maxHappy) {
        this.maxHappy = maxHappy;
    }
}

public static ReturnData process(Node root) {
    if (root.subs.size() == 0) {
        return new ReturnData(root.happy);
    }
    //case 1:go
    int go_Happy = root.happy;
    //case 2:don't go
    int unGo_Happy = 0;
    for (Node sub : root.subs) {
        unGo_Happy += process(sub).maxHappy;
    }
    return new ReturnData(Math.max(go_Happy, unGo_Happy));
}

public static int maxPartyHappy(Node root) {
    if (root == null) {
        return 0;
    }
    return process(root).maxHappy;
}

public static void main(String[] args) {
    Node A = new Node(2);
    Node B = new Node(8);
    Node C = new Node(5);
    Node D = new Node(24);
    B.subs.add(new Node(9));
    C.subs.addAll(Arrays.asList(new Node(11),new Node(2),new Node(4),new Node(7)));
    D.subs.addAll(Arrays.asList(new Node(13), new Node(5)));
    A.subs.addAll(Arrays.asList(B, C, D));
    System.out.println(maxPartyHappy(A));//57
}

Оценить математическое выражение

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

Пример:str="48*((70-65)-43)+8*1", возвращает -1816.str="3+1*4", возвращает 7.str="3+(1*4)", возвращает 7.

проиллюстрировать:

1. Можно считать, что заданная строка должна быть корректной формулой, то есть нет необходимости проверять правильность формулы на стр.
2. Если это отрицательное число, оно должно быть заключено в круглые скобки, например"4*(-3)". Но если отрицательное число стоит в начале формулы или в начале скобочной части, то скобок быть не может, например"-3*4"和"(-3*4)"все законны.
3. Не беспокойтесь о переполнении во время расчета

Анализ оптимального решения: сложность этой задачи заключается в том, как поступать со скобками в выражениях, что можно сделать с помощью стека. Но если вы полагаетесь только на один стек, объем кода будет сложным. Если мы выделим вычисление подвыражения, содержащего левую и правую скобки в формуле, как процесс (обозначается какprocess), то процесс можно использовать повторно.Если рассматривать все подвыражения, содержащие левые и правые скобки во всем выражении, как число, то исходная задача преобразуется в вычисление выражений без скобок.

с выражением3+2*5-(7+2)*3Например, проанализируйте шаги решения проблемы:

Образец кода:

public static int getValue(String exp){
    return process(exp.toCharArray(), 0)[0];
}

/**
     * @param exp   expression
     * @param index the start index of expression
     * @return int[], include two elements:the result and the endIndex
     */
public static int[] process(char[] exp, int index) {

    LinkedList que = new LinkedList();
    //下一个要往队尾放的数
    int num = 0;
    //黑盒process返回的结果
    int sub[];

    while (index < exp.length && exp[index] != ')') {

        if (exp[index] >= '0' && exp[index] <= '9') {
            num = num * 10 + exp[index] - '0';
            index++;
        } else if (exp[index] != '(') {
            // +、-、*、/
            addNum(num, que);
            num = 0;
            que.addLast(String.valueOf(exp[index]));
            index++;
        } else {
            // '('
            sub = process(exp, index + 1);
            num = sub[0];
            index = sub[1] + 1;
        }
    }

    addNum(num, que);

    return new int[]{getSum(que), index};
}

private static int getSum(LinkedList<String> que) {
    int res = 0;
    boolean add = true;
    while (!que.isEmpty()) {
        int num = Integer.valueOf(que.pollFirst());
        res += add ? num : -num;
        if (!que.isEmpty()) {
            add = que.pollFirst().equals("+") ? true : false;
        }
    }
    return res;
}

private static void addNum(int num, LinkedList<String> que) {
    if (!que.isEmpty()) {
        String element = que.pollLast();
        if (element.equals("+") || element.equals("-")) {
            que.addLast(element);
        } else{
            // * or /
            Integer preNum = Integer.valueOf(que.pollLast());
            num = element.equals("*") ? (preNum * num) : (preNum / num);
        }
    }
    que.addLast(String.valueOf(num));
}

public static void main(String[] args) {
    String exp = "48*((70-65)-43)+8*1";
    System.out.println(getValue(exp));
    System.out.println(-48*38+8);
}

XOR и самый большой подмассив

Учитывая массив, позвольте вам найти наибольшую сумму XOR всех подмассивов.

насильственное решение

Переберите каждое число в массиве и найдите сумму XOR всех подмассивов, заканчивающихся этим числом.

public static class NumTrie{
    TrieNode root;

    public NumTrie() {
        root = new TrieNode();
    }

    class TrieNode{
        TrieNode[] nexts;
        public TrieNode(){
            nexts = new TrieNode[2];
        }
    }

    public void addNum(int num) {
        TrieNode cur = root;
        for (int i = 31; i >= 0; i--) {
            int path = (num >> i) & 1;
            if (cur.nexts[path] == null) {
                cur.nexts[path] = new TrieNode();
            }
            cur = cur.nexts[path];
        }
    }

    /**
         * find the max value of xor(0,k-1)^xor(0,i)-> the max value of xor(k,i)
         * @param num -> xor(0,i)
         * @return
         */
    public int maxXor(int num) {
        TrieNode cur = root;
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            int path = (num >> i) & 1;
            //如果是符号位，那么尽量和它相同（这样异或出来就是正数），如果是数值位那么尽量和它相反
            int bestPath = i == 31 ? path : (path ^ 1);
            //如果贪心路径不存在，就只能走另一条路
            bestPath = cur.nexts[bestPath] != null ? bestPath : (bestPath ^ 1);
            //记录该位上异或的结果
            res |= (bestPath ^ path) << i;

            cur = cur.nexts[bestPath];
        }
        return res;
    }
}

public static int maxXorSubArray(int arr[]) {
    int maxXorSum = Integer.MIN_VALUE;
    NumTrie numTrie = new NumTrie();
    //没有数时异或和为0，这个也要加到前缀数中，否则第一次到前缀树找bestPath会报空指针
    numTrie.addNum(0);
    int xorZeroToI = 0;
    for (int i = 0; i < arr.length; i++) {
        xorZeroToI ^= arr[i];
        maxXorSum = Math.max(maxXorSum, numTrie.maxXor(xorZeroToI));
        numTrie.addNum(xorZeroToI);
    }
    return maxXorSum;
}


public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 1, 2, -7};
    System.out.println(maxXorSubArray(arr));
}

Временная сложностьO(N^3)

Оптимизация решения грубой силы

Обратите внимание на насильственное решение{1, 2, 3, 4, 1, 2, 0}Например, когда я вычисляю с помощью4Когда XOR суммирует все подмассивы в конце, я сначала вычисляю подмассивы{4}, затем вычислить{3,4}, затем вычислить{2,3,4}То есть каждый раз выполняется XOR от начала до конца, и результат предыдущего вычисления не ускоряет процесс последующего вычисления. Так я думал, когда я вычисляю{3,4}когда3^4Временно сохранить результат{2,3,4}Повторно используйте его при расчете и снова сохраните2^3^4результат, в следующем{1,2,3,4}Расчет можно использовать повторно. Таким образом, решение грубой силы оптимизировано следующим образом:

public static int solution2(int[] arr) {
    int res = 0;
    int temp=0;
    for (int i = 0; i < arr.length; i++) {
        //以i结尾的最大异或和
        int maxXorSum = 0;
        for (int j = i; j >= 0; j--) {
            temp ^= arr[j];
            maxXorSum = Math.max(maxXorSum, temp);
        }
        //整体的最大异或和
        res = Math.max(res, maxXorSum);
    }
    return res;
}

public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 1, 2, 0};
    System.out.println(solution2(arr));//7
}

Тогда временная сложность снижается доO(N^2)

Оптимальным решением

Однако использование префиксной древовидной структуры может обеспечить временную сложностьO(N).

Идея решения проблемы:iРешение максимальной суммы XOR всех подмассивов в конце ограниченоO(1).

Навыки решения проблем:

1. для подмассивов0~i(i является допустимым индексом) и0~iиндекс междуk(k больше или равно 0, меньше или равно i),k~iисключающее ИЛИ иxor(k,i),0~iисключающее ИЛИ иxor(0,i),0~k-1XOR и междуxor(0,k-1)Между этими тремя существует следующая связь:xor(k,i)=xor(0,i) ^ xor(o,k-1)(A^B=C -> B=C^A), так что спрашивайтеxor(k,i)Максимальное значение может быть преобразовано вxor(0,i) ^ xor(o,k-1)максимальное значение (Эта идея важна, следующие шаги основаны на этом).

2. Пройдите массив, поместите 32-битное двоичное число суммы XOR подмассива, начиная с первого элемента и заканчивая текущим проходимым элементом, в древовидную структуру префикса (каждый бит является символом, а символ либо 0 или 1). После завершения обхода все0~iСумма XOR хранится в дереве префиксов. Например: траверс{1, 2, 3, 4, 1, 2, 0}Результирующее дерево префиксов выглядит следующим образом:

   

3. Предположим, что в процессе обхода массива для построения префиксного дерева, проходя к4А вот и номер, будет0 100Поместите его в него, потому что он был пройден раньше1,2,3,такxor(0,0),xor(0,1),xor(0,2)Также в дереве префиксов. Если запрос в это времяxor(k,3)Максимальное значение (k находится между нижними индексами 0 и 3 включительно), которое можно преобразовать, чтобы найтиxor(0,3) ^ xor(0,k-1), и мы знаем, чтоxor(0,3)=0 100,такxor(0,k-1)решение становится ключевым.

   xor(0,k-1)Решение: курсор в это времяcurОт корневого узла префиксного дерева к конечному узлу,curДвоичные биты, которые проходят по пути, соединяются вместе какxor(0,k-1), требуя, чтобы каждый раз, когда вы выбираете, какой бит пройти, сделать его как можно ближе кxor(0,3)Результат XOR больше:

   

   Этот процесс решенияжадный(Если это знаковый бит, сделайте результат XOR равным 0, насколько это возможно, а если это числовой бит, сделайте результат XOR максимально равным 1), только дерево префиксов содержитxor(0,0)、xor(0,1)、xor(0,2)、xor(0,3),а такжеxor(0,k-1)Вы можете только брать значения из него.Процесс шаг за шагом от корневого узла к листовому узлу является жадным, какой путь соответствуетxorсделатьxor ^ xor(0,3)максимум.

   Образец кода:

   public static class NumTrie{
       TrieNode root;
   
       public NumTrie() {
           root = new TrieNode();
       }
   
       class TrieNode{
           TrieNode[] nexts;
           public TrieNode(){
               nexts = new TrieNode[2];
           }
       }
   
       public void addNum(int num) {
           TrieNode cur = root;
           for (int i = 31; i >= 0; i--) {
               int path = (num >> i) & 1;
               if (cur.nexts[path] == null) {
                   cur.nexts[path] = new TrieNode();
               }
               cur = cur.nexts[path];
           }
       }
   
       /**
            * find the max value of xor(0,k-1)^xor(0,i)-> the max value of xor(k,i)
            * @param num -> xor(0,i)
            * @return 
            */
       public int maxXor(int num) {
           TrieNode cur = root;
           int res = 0;
           for (int i = 31; i >= 0; i--) {
               int path = (num >> i) & 1;
               //如果是符号位，那么尽量和它相同（这样异或出来就是正数），如果是数值位那么尽量和它相反
               int bestPath = i == 31 ? path : (path ^ 1);
               //如果贪心路径不存在，就只能走另一条路
               bestPath = cur.nexts[bestPath] != null ? bestPath : (bestPath ^ 1);
               //记录该位上异或的结果
               res |= (bestPath ^ path) << i;
   
               cur = cur.nexts[bestPath];
           }
           return res;
       }
   }
   
   public static int maxXorSubArray(int arr[]) {
       int maxXorSum = 0;
       NumTrie numTrie = new NumTrie();
       //一个数自己异或自己异或和为0，这个也要加到前缀数中，否则第一次到前缀树找bestPath会报空指针
       numTrie.addNum(0);
       int xorZeroToI = 0;
       for (int i = 0; i < arr.length; i++) {
           xorZeroToI ^= arr[i];
           maxXorSum = Math.max(maxXorSum, numTrie.maxXor(xorZeroToI));
           numTrie.addNum(xorZeroToI);
       }
       return maxXorSum;
   }
   
   
   public static void main(String[] args) {
       int[] arr = {1, 2, 3, 4, 1, 2, -7};
       System.out.println(maxXorSubArray(arr));//7
   }
   

Суммируйте самый длинный подмассив целей (все больше 0)

В базовой главе те же вопросы, за исключением того, что значение элемента массива здесь положительное, а в базовой главе оно может быть положительным, отрицательным или 0.

Практика в основах заключается в использовании хеш-таблицы для записи подмассива и самой ранней позиции вхождения. И этот вопрос может иметь дополнительную пространственную сложность из-за особенностей данных (все положительные числа).O(1), временная сложностьO(N)завершено в течение.

Используйте окно, используйте L для представления левого края окна, R для представления правого края окна и sum для представления суммы элементов в окне (изначально 0). Сначала и L, и R останавливаются в положении -1, а затем каждый раз нужно продлевать L на один шаг вправо или R на один шаг вправо, в зависимости от ситуации:

• еслиsum<aim, то R расширяется вправо
• еслиsum=aim, затем запишите количество элементов в окне, L расширяется вправо
• еслиsum>aim, то L расширяется вправо

пока R не расширится доarr.lengthЕсли он пересекает границу, то сумма элементов в окне должна быть меньше цели, и весь процесс может закончиться. ответ на всеsum=aimМаксимальное количество элементов в окне в данном случае.

Образец кода:

/**
     * 数组元素均为正数，求和为aim的最长子数组的长度
     * @param arr
     * @return
     */
public static int aimMaxSubArray(int arr[],int aim) {
    int L=-1;
    int R= -1;
    int sum = 0;
    int len=0;
    while (R != arr.length) {
        if (sum < aim) {
            R++;
            if (R < arr.length) {
                sum += arr[R];
            } else {
                break;
            }
        } else if (sum == aim) {
            len = Math.max(len, R - L);
            sum -= arr[++L];
        } else {
            sum -= arr[++L];
        }
    }
    return len;
}

public static void main(String[] args) {
    int arr[] = {1, 2, 3, 5, 1, 1, 1, 1, 1, 1, 9};
    System.out.println(aimMaxSubArray(arr,6));
}

Подумайте: почему процесс получил правильный ответ? Другими словами, почему окно не пропускает самую длинную подматрицу прицеливания, когда окно сдвигается вправо? Мы можем это доказать:

Предполагая, что область эллипса является самым длинным подмассивом, сумма которого равна цели, если L подходит к левой границе области L2 области эллипса, то есть два случая для положения R: внутри области эллипса, такой как R1, и вне области эллипса регион, такой как R2. Если первое, из-за окнаL2~R1определенно меньше, чемaim(все элементы — положительные числа), поэтому в процессе движения R от R1 к правой границе области эллипса L всегда находится на L2, и, очевидно, правильный ответ не будет упущен; окноL2~R2изsumзначительно больше, чемaim, так что эта ситуация невозможна. И L находится слева от L2, например, L1, R еще менее вероятно пересечет эллиптическую область до R2, потому что окно всегда сохраняетсяsum<=aimиз.

Сумма самого длинного подмассива меньше или равна цели (положительный, отрицательный и 0)

Если вы используете перебор грубой силы для перечисления подмассивов, начиная с каждого элемента, то ответ должен быть там (O(N^3)). Но вот временная сложностьO(N)решение.

Сначала пройдите массив от конца к началу, чтобы сгенерировать два вспомогательных массива.min_sumа такжеmin_sum_indexв качестве вспомогательной информации при решении.min_sumУказывает наименьшую сумму всех подмассивов, начинающихся с элемента,min_sum_indexТогда он соответствует конечному индексу подмассива минимальной суммы.

Пример: для[100,200,7,-6].

1. Сначала пройдите 3 позиции-6,к-6Подмассив в начале имеет только[-6],следовательноmin_sum[3] = -6, min_sum_index[3] = 3([-6]хвостовой элемент-6Индекс в исходном массиве3).
2. Затем перейдите в положение 27,к7Минимальный подмассив суммы в начале равен[7,-6],следовательноmin_sum[2] = 7-6 = 1, min_sum_index[2]=3. ([7,-6]хвостовой элемент-6Индекс в исходном массиве3).
3. Затем перейдите в положение 1200,имеютmin_sum[1] = 200, min_sum_index[1] = 1.
4. Затем перейдите в положение 0100,имеютmin_sum[0] = 100, min_sum_index[0] = 0.

Затем после обхода массива и создания двух вспомогательных массивов можно приступить к формальному процессу решения:

При использовании окна L представляет левый край окна, R представляет правый край окна,sumПредставляет сумму элементов в окне.

• L приходит к каждому элементу массива от начала до конца.Каждый раз, когда L приходит к одному из элементов, он пытается расширить R вправо.Когда R не может быть расширен, размер окнаR-LТо есть длина самого длинного подмассива, начинающегося с этого элемента и меньшего или равного цели.
• L сначала приходит к первому элементу, R тоже сначала останавливается на первом элементе,sum=0.
• Логика расширения R вправо такова: еслиsum + min_sum[L] <= aim, то R расширяется доmin_sum_index[L] + 1местоположение и обновлениеsum.
• Когда R расширяется до точки, где его нельзя расширить, запишитеR-L, L переходит к следующему элементу и обновляетsum.
• Если L идет после элемента,sum > aim, указывающее, что длина самого длинного подмассива, начинающегося с этого элемента и меньшего или равного цели, больше, чем текущий размер окнаR-LЕсли еще меньше, то подмассив, начинающийся с этого элемента, в правильном ответе не учитывается (поскольку максимальное окно, образованное предыдущим элементом, больше максимального окна, образованного текущим элементом, а первое было записано), L переходит непосредственно к переходу к следующему элементу и обновлениюsum.

Образец кода:

public static int lessOrEqualAim(int arr[], int aim) {
    int min_sum[] = new int[arr.length];
    int min_sum_index[] = new int[arr.length];
    min_sum[arr.length-1] = arr[arr.length - 1];
    min_sum_index[arr.length-1] = arr.length - 1;
    for (int i = arr.length - 2; i >= 0; i--) {
        if (min_sum[i + 1] < 0) {
            min_sum[i] = arr[i] + min_sum[i + 1];
            min_sum_index[i] = min_sum_index[i + 1];
        } else {
            min_sum[i] = arr[i];
            min_sum_index[i] = i;
        }
    }

    int R = 0;
    int sum = 0;
    int maxLen = 0;
    for (int L = 0; L < arr.length; L++) {
        while (R < arr.length && sum + min_sum[R] <= aim) {
            sum += min_sum[R];
            R = min_sum_index[R] + 1;
        }
        maxLen = Math.max(maxLen, R - L);
        sum -= R == L ? 0 : arr[L];
        R = Math.max(R, L + 1);
    }
    return maxLen;
}

public static void main(String[] args) {
    int arr[] = {1, 2, 3, 2, -1, -1, 1, 1, -1, -1, 9};
    System.out.println(lessOrEqualAim(arr,3));//8
}

19-27Строка - это сложная часть реализации, первая строка 19 - это L от начала до конца до каждого элемента в массиве, затем20-23изwhileсостоит в том, чтобы попытаться заставить R расширяться до тех пор, пока R не сможет расширяться,24Когда R не расширяется, он может записывать длину самого длинного подмассива, который начинается с элемента в текущей позиции L и меньше или равен прицелу, и, наконец, входит в следующий раз.forПеред циклом L перемещается на один шаг вправо,sumОбновление имеет два случая:

1. 29В ПОРЯДКЕwhileказнен,Rрасширен, так чтоsumПросто вычтите элемент из текущего L напрямую.
2. 29В ПОРЯДКЕwhileвообще не выполнял.Rне расширил шаг иLВ той же позиции, то есть в данный момент в окне нет элементов (только когда R>L, окно содержит элементы от L до R),sum=0, L и R должны прийти к следующему элементу одновременно,sumпо-прежнему 0, поэтомуsumне нужно вычитатьarr[L](Декремент необходим только в том случае, если сдвиг L вправо приводит к тому, что элемент выходит за пределы окна.arr[L]).

В конце концов26Линия также состоит в том, чтобы гарантировать, что если R не может быть расширен все время, когда L смещается вправо, то когда L перемещается вправо к R, а R все еще не может быть расширен, то R должен быть сдвинут вправо на одну позицию в одновременно с Л.

Этот метод может сделатьO(N)Ключевой момент временной сложности: отбросить недопустимые случаи. Например, L обновляется на один шаг вправоsumПотом, если найдутsum > aim, очевидно, что самый длинный подмассив, начинающийся с текущего L и меньший или равный цели, должен быть меньше текущегоR-L, и записанный на предыдущем шагеR-(L-1), подмассивы, начинающиеся с текущего L, которые удовлетворяют условию, можно игнорировать (поскольку они должны быть меньше, чемR-(L-1)), не позволяя R вернуться к текущему L, чтобы снова расширить R.

Таким образом, и L, и R перемещаются только вправо, не возвращаясь назад, поэтому временная сложность состоит в том, чтобы пройти массив один раз.

Проблема Джозефа о круговом односвязном списке

У известного еврейского историка Иосифа Флавия есть следующая история: После того, как римляне заняли Хотапат, 39 евреев спрятались в яме с Иосифом Флавием и его друзьями, 39 евреев решили, что они скорее умрут, чем будут схвачены врагом. было решено, 41 человек выстроились в круг, первый человек начал считать, тот, кто насчитал 3, покончил жизнь самоубийством, а затем следующий человек повторно доложил 1, и тот, кто насчитал 3, покончил жизнь самоубийством. последний человек остался, этот человек свободен выбирать свою судьбу. Это знаменитая проблема Джозефа. Теперь опишите структуру и представьте весь процесс самоубийства, используя однонаправленный круговой связанный список.

войти: заголовок узла кругового односвязного списка и значение m количества отчетов.

вернуть: Последний оставшийся узел и сам этот узел образуют циклический односвязный список, а остальные узлы удаляются.

Передовой: если количество узлов связанного списка равно N, а временная сложность составляет O(N) для выполнения требований исходной задачи, как этого достичь?

Насильственный метод: начинайте считать с головного узла, считайте от 1 до m, удаляйте узел при счете до m, а затем начинайте считать со следующего узла... поэтому удаляйте (n-1) узлов и перед каждым удалением Считайте m чисел, поэтому временная сложность равнаO(NxM)

ВотO(N)Методы.

Сначала введите функцию:

Если вы начнете с головного узла, номер 1, 2, 3, ... для каждого узла по очереди. Например, в круговом связанном списке есть 3 узла, и каждый раз, когда счет достигает 7, вы убиваете:

Номер узла	считать
1	1
2	2
3	3
1	4
2	5
3	6
1	убийство

Затем перед уничтожением номер узла и количество отчетов имеют следующее соответствие (ось x представляет, где число сообщается в данный момент, ось y соответствует количеству узлов, о которых сообщается, а n - количество узлов ):

Предполагая, что после каждого убийства номер перенумеровывается со следующего узла и номер пересчитывается.Например, в круговом связанном списке 9 узлов.Если число достигает 7, убийство будет убито.Тогда старый номер узла до убийства и номер узла после убийства перенумерованы.Новые номера имеют следующую связь:

старый номер	новый номер
1	3
2	4
3	5
4	6
5	7
6	8
7	Убито, перенумерация со следующего узла
8	1
9	2

Если количество узлов в связанном списке равно n, и счетчик достигает m для уничтожения, то соответствующее соотношение между старым и новым номерами узлов выглядит следующим образом (гдеs— номер узла с номером отчета m):

Этот график также может быть представлен базовой функциейy = (x - 1) % n + 1Преобразуем влево на s единиц длины:

которыйy = (x - 1 + s) % n + 1.

Теперь у нас есть следующие две формулы:

1. 结点编号 = (报数 - 1) % n + 1
2. 旧编号 = (新编号 - 1 + s) % n +1,вsномер узла с номером отчета m

Его можно получить из уравнения 1s = (m - 1) % n + 1, мы можем получить

3. 旧编号 = (新编号 - 1 + (m - 1) % n + 1) % n + 1 = (新编号 + m - 1) % n + 1,вmа такжеnОпределяется входными параметрами.

Теперь, когда у нас есть уравнение 3, мы можем найти старый номер узла, учитывая новый номер узла после того, как другой узел был уничтожен. Другими словами, если предположить, что первое убийство совершено сейчасn-1Узел, после убийства только последнего узла (выбранного узла), узел перенумерации должен быть №1, затем первый узелn-1Мы можем найти номер выбранного узла до того, как убитый узел будет уничтожен с помощью уравнения 3, и с помощью этого результата мы также можем получить номер выбранного узла в первомn-2Номер убитого узла до того, как он был убит, ..., нажмите его по очереди, чтобы восстановить номер выбранного узла, когда узел не мертв, чтобы мы могли найти узел из входного связанного списка, непосредственно Point его преемник указывает на себя и возвращается.

Образец кода:

static class Node {
    char data;
    Node next;

    public Node(char data) {
        this.data = data;
    }
}

public static Node aliveNode(Node head, int m) {
    if (head == null) {
        return null;
    }
    int tmp = 1;
    Node cur = head.next;
    while (cur != head) {
        tmp++;
        cur = cur.next;
    }

    //第n-1次杀人前还有两个结点，杀完之后天选结点的新编号为1
    //通过递归调用getAlive推出所有结点存活时，天选结点的编号
    int nodeNumber = getAlive(1, m, 2, tmp);

    cur = head;
    tmp = 1;
    while (tmp != nodeNumber) {
        cur = cur.next;
        tmp++;
    }
    cur.next = cur;
    return cur;
}

/**
     * 旧编号 = (新编号 + m - 1) % n + 1
     *
     * @param newNumber 新编号
     * @param m
     * @param n         旧编号对应的存活的结点个数
     * @param len       结点总个数
     * @return
     */
public static int getAlive(int newNumber, int m, int n, int len) {
    if (n == len) {
        return (newNumber + m - 1) % n + 1;
    }
    //计算出新编号对应的旧编号，将该旧编号作为下一次计算的新编号
    return getAlive((newNumber + m - 1) % n + 1, m, n + 1, len);
}

public static void main(String[] args) {
    Node head = new Node('a');
    head.next = new Node('b');
    head.next.next = new Node('c');
    head.next.next.next = new Node('d');
    head.next.next.next.next = new Node('e');
    head.next.next.next.next.next = head;

    System.out.println(aliveNode(head, 3).data);//d
}

Классическая структура

структура максимального обновления окна

максимальная структура обновления

При помещении данных в эту структуру он будет проверять существующие данные в структуре, начиная с наибольшей метки времени. следующий будет проверяться до тех пор, пока он не будет помещен. Введенные данные меньше, чем проверяемые данные, или данные в структуре были извлечены, а затем данные, которые нужно поместить, помещаются в структуру и помечаются отметкой времени. Таким образом, каждый раз, когда данные извлекаются из структуры, будут возвращены данные с наименьшей меткой времени в структуре, которая также является самой большой среди всех данных, которые до сих пор поступали в структуру.

Эта структура может быть реализована с использованием двусторонней очереди, один конец которой используется только для помещения данных (процесс проверки перед размещением данных может вытолкнуть другие данные), а другой конец используется для получения максимального значения, которое произошло до сих пор.

Пример выглядит следующим образом:

package top.zhenganwen.structure;

import java.util.LinkedList;

public class MaxValueWindow {

  private LinkedList<Integer> queue;
  public MaxValueWindow() {
    this.queue = new LinkedList();
  }

  //更新窗口最大值
  public void add(int i){
    while (!queue.isEmpty() && queue.getLast() <= i) {
      queue.pollLast();
    }
    queue.add(i);
  }

  //获取窗口最大值
  public int getMax() {
    if (!queue.isEmpty()) {
      return queue.peek();
    }
    return Integer.MIN_VALUE;
  }

  //使窗口最大值过期
  public void expireMaxValue() {
    if (!queue.isEmpty()) {
      queue.poll();
    }
  }

  public static void main(String[] args) {
    MaxValueWindow window = new MaxValueWindow();
    window.add(6);
    window.add(4);
    window.add(9);
    window.add(8);
    System.out.println(window.getMax());//9
    window.expireMaxValue();
    System.out.println(window.getMax());//8
  }
}

пример

окно двигаться

дает вам длинуNЦелочисленный массив и размерWокно, длинойN-W+1Массив записывает максимальное значение в пределах окна при перемещении окна слева направо в массиве.

для массивов[1,2,3,4,5,6,7]и размер окна3, когда окно перемещается слева направо:

• [1,2,3],4,5,6,7, когда начальный нижний индекс окна равен 0, номер в рамке равен1,2,3, максимальное значение равно 3
• 1,[2,3,4],5,6,7, максимальное значение равно 4
• 1,2,[3,4,5],6,7, максимальное значение равно 5
• ...

Итак, искомый массив[3,4,5,6,7].

Идея: характеристика представленной выше структуры максимального обновления окна заключается в том, что если число, помещенное перед ним, все еще существует в структуре, то число должно быть больше, чем число, помещенное позже. Процесс перемещения окна в этом вопросе — это процесс вычитания и увеличения числа из окна. брать[1,2,3],4прибыть1,[2,3,4]Анализ этого процесса: первый[1,2,3],4Окно в состоянии должно иметь только одно значение3(Поскольку 1 добавляется первым, 1 появляется перед добавлением 2, а 2 появляется перед добавлением 3);1,[2,3,4]Процесс заключается в том, чтобы сначала уменьшить число до окна1добавить еще один номер4процесс, потому что окно не содержит1Так что просто добавьте номер4(во всплывающем окне3, добавьте номер4).

Пример кода:

public static void add(int arr[], int index, LinkedList<Integer> queue) {
  if (queue == null) {
    return;
  }
  while (!queue.isEmpty() && arr[queue.getLast()] < arr[index]) {
    queue.pollLast();
  }
  queue.add(index);
}

public static void expireIndex(int index, LinkedList<Integer> queue) {
  if (queue == null) {
    return;
  }
  if (!queue.isEmpty() && queue.peek() == index) {
    queue.pollFirst();
  }
}

public static int[] maxValues(int[] arr, int w) {
  int[] res = new int[arr.length - w + 1];
  LinkedList<Integer> queue = new LinkedList();
  for (int i = 0; i < w; i++) {
    add(arr, i, queue);
  }
  for (int i = 0; i < res.length; i++) {
    res[i] = queue.peek();
    if (i + w <= arr.length - 1) {
      expireIndex(i, queue);
      add(arr, i + w, queue);
    }
  }
  for (int i = 0; i < res.length; i++) {
    res[i] = arr[res[i]];
  }
  return res;
}

public static void main(String[] args) {
  int[] arr = {3, 2, 1, 5, 6, 2, 7, 8, 10, 6};
  System.out.println(Arrays.toString(maxValues(arr,3)));//[3, 5, 6, 6, 7, 8, 10, 10]
}

Здесь следует отметить, что для этого вопроса максимальное значение окна обновляется до структурыaddа такжеexpireМетод улучшен (индекс, соответствующий значению, сохраняется в структуре). Например[2,1,2],-1->2,[1,2,-1], что следует перевести как[2,1,2],-1Максимальное значение окна в состоянии это число на 2 нижнем индексе2, становится2,[1,2,-1]Когда это должно быть переведено в число с нижним индексом 0, истекшим из окна, это не должны быть данные2Срок действия подчиненного окна истек (это приведет к ошибочному удалению максимального значения 2 с нижним индексом 2 в окне).

Найдите количество подмассивов, которые соответствуют цели

По заданному массиву целых чисел определить, что разница между максимальным и минимальным значениями во всех его подмассивах не превышаетnum(Если он удовлетворяется, говорят, что массив соответствует стандарту). (Подмассив относится к массиву, состоящему из элементов с любыми последовательными нижними индексами в исходном массиве)

Насильственное решение: пройтись по каждому элементу, затем пройти по всем подмассивам, возглавляемым текущим элементом, а затем пройти по подмассивам, чтобы найти максимальное и минимальное значения, чтобы определить, соответствует ли он стандарту. Очевидно, временная сложность этого методаo(N^3), но если обновить структуру с максимальным значением, то можно добитьсяO(N)уровневое решение.

При использованииLа такжеRдва указателя указывают на два нижних индекса массива, иLсуществуетRСлева. когдаL~RКогда этот подмассив достигает стандарта, можно сделать вывод, чтоLДлина начала не превышаетR-L+1Соблюдены все подмассивы; когдаL~RКогда этот подмассив не соответствует стандарту, независимо отLна сколько позиций расширить влево илиRна сколько позиций расширить вправо,L~RЕще не на высоте.

O(N)Соответствующий алгоритм решения:Lа такжеRвсе начинается с 0,RСначала двигайся вправо,RИспользуйте структуру максимального обновления и структуру минимального обновления, чтобы записывать каждый раз, когда вы сдвигаетесь вправо на одну позицию.L~Rнижний индекс между максимальным и минимальным значениями, когдаRПереместить, если переместиться на одну позицию вправоL~RОстановитесь, если он не соответствует стандарту, а затем используйте текущийLДлина начала не превышаетR-L+1подмассивы , все удовлетворяют критериям, тогдаLПереместиться на одну позицию вправо и одновременно обновить максимальную и минимальную структуры обновления (L-1срок действия нижнего индекса истек), затем двигайтесь вправоRкRЕсли вы переместитесь на одну позицию вправоL~Rне до упора (каждое правое смещениеRтакже обновлять структуру обновления наибольшего и наименьшего значения за раз) ...; до тех пор, покаLпока не будет достигнут конец массива. будет каждый разRпри остановке,R-L+1Количество кумулятивныхO(N)решение, потому чтоLа такжеRдвигаться только вправо, и каждый разRпри остановке сLКоличество квалифицированных подстрок в начале напрямую передается черезR-L+1вычисления, поэтому временная сложность состоит в том, чтобы пройти массив один раз.O(N).

Образец кода:

public static int getComplianceChildArr(int arr[], int num) {
  //最大值、最小值更新结构
  LinkedList<Integer> maxq = new LinkedList();
  LinkedList<Integer> minq = new LinkedList<>();
  int L = 0;
  int R = 0;
  maxq.add(0);
  minq.add(0);
  int res = 0;
  while (L < arr.length) {
    while (R < arr.length - 1) {
      while (!maxq.isEmpty() && arr[maxq.getLast()] <= arr[R + 1]) {
        maxq.pollLast();
      }
      maxq.add(R + 1);
      while (!minq.isEmpty() && arr[minq.getLast()] >= arr[R + 1]) {
        minq.pollLast();
      }
      minq.add(R + 1);
      if (arr[maxq.peekFirst()] - arr[minq.peekFirst()] > num) {
        break;
      }
      R++;
    }
    res += (R - L + 1);
    if (maxq.peekFirst() == L) {
      maxq.pollFirst();
    }
    if (minq.peekFirst() == L) {
      minq.pollFirst();
    }
    L++;
  }
  return res;
}

public static void main(String[] args) {
  int[] arr = {1, 2, 3, 5};
  System.out.println(getComplianceChildArr(arr, 3));//9
}