algorithm - verdad - tag del youtuber hipocrita wattpad

¿Cómo determinar si una secuencia es bitónica?

Question

Una secuencia es bitónica si aumenta monótonamente y luego disminuye monótonamente, o si puede desplazarse circularmente para aumentar monótonamente y luego disminuir monótonamente. Por ejemplo las secuencias (1, 4, 6, 8, 3, −2), (9, 2, −4, −10, −5) y (1, 2, 3, 4) son bitónicas, pero (1 , 3, 12, 4, 2, 10) no es bitónico.

¿Cómo se puede determinar si una secuencia dada es bitónica?

Tengo la siguiente opinión. Podemos caminar hasta n / 2 , donde n es la longitud de la matriz, y verificar si

(a[i] < a[i + 1]) and (a[n - i - 1] < a[n-1 - (i + 1)])

¿Es esto correcto?

Answer 1

Aquí hay una implementación eficiente y simple en Java. Atraviesa la matriz solo una vez para determinar si la matriz es bitónica o no. Utiliza una reversal variable que cuenta el número de inversiones de dirección de monotonicidad en la matriz (incluida la envoltura circular).

La trend variable puede tener tres valores:

• 0 , si los valores son los mismos;
• 1 , si la matriz es monótonamente creciente;
• -1 , si la matriz está disminuyendo monótonamente.

public static boolean bitonic(int[] arr) {
int reversal = 0;
int len = arr.length;
int trend = 0; // 0 means any, 1 means increasing, -1 means decreasing
for (int i= 0; i < len ; i++) {
if(arr[i%len] < arr[(i+1)%len]){
if (trend == 0) trend = 1;
else if ( trend == -1) {
reversal ++;
trend = 1;
}
}
else if(arr[i%len] > arr[(i+1)%len]){
if (trend == 0) trend = -1;
else if ( trend == 1) {
reversal ++;
trend = -1;
}
}
if(reversal > 2) return false;
}
return true;
}

Answer 2

Debe haber exactamente dos (o, dependiendo de cómo su definición trate con la degeneración, exactamente 0) las transiciones entre ascenso y descenso. No olvide verificar la transición entre [n] y [0].

Answer 3

Puede buscar el pico, es decir, cuando a [i-1] <a [i] && a [i]> a [i + 1], a [i] es el pico local (cuidando de envolver con módulo) operador).

En una secuencia bitónica, solo puede haber uno de esos picos. Una vez que encontró el pico, entonces puede caminar cuesta abajo hacia la izquierda (envolviéndose según sea necesario, nuevamente usando el módulo) hasta que encuentre una cuesta arriba. Luego regresa a la cima, camina cuesta abajo hacia la derecha, hasta que encuentra otra cuesta arriba. Ahora, si una secuencia es bitónica, entonces habrá cubierto toda la secuencia yendo cuesta abajo en ambos lados.

por cierto, ¿entendí mal la pregunta o su primer ejemplo no es bitónico?

Answer 4

Una secuencia bitónica:

 //
/ /
//

No es una secuencia bitónica

 //
/ / / (higher than start)
//

Obviamente, si la dirección cambia más de dos veces, no podemos tener una secuencia bitónica.
Si la dirección cambia menos de dos veces, debemos tener una secuencia bitónica.

Si hay dos cambios en la dirección, PODEMOS tener una secuencia bitónica. Considere las dos imágenes de ascii arriba. Claramente, una secuencia con dos cambios de dirección coincidirá con uno de los patrones (permitiendo una reflexión). Por lo tanto, establecemos la dirección inicial comparando los elementos primero y último. Ya que estos pueden ser iguales, usamos el primer elemento que no es igual al último elemento.

Aquí hay una implementación en Java:

public static Boolean bitonic(int[] array) {
if (array == null) return false;
if (array.length < 4) return true;
Boolean dir;// false is decreasing, true is increasing
int pos = 0, switches = 0;
while (pos < array.length) {
if (array[pos] != array[array.length - 1])
break;
pos++;
}
if (pos == array.length) return true;
//pos here is the first element that differs from the last
dir = array[pos] > array[array.length - 1];
while (pos < array.length - 1 && switches <= 2) {
if ((array[pos + 1] != array[pos]) &&
((array[pos + 1] <= array[pos]) == dir)) {
dir ^= true;
switches++;
}
pos++;
}
return switches <= 2;
}

Answer 5

• Recorra la matriz hacia delante, envolviéndose cuando llegue al final (código a continuación)
• Cuente el número total de puntos de inflexión que encuentre, si num_inflection_points==2 entonces su matriz es bitónica.
• El tiempo de ejecución de este debe ser O(n) .

-

Aquí hay un ejemplo de trabajo en c ++:

bool is_bitonic(const vector<int>& v) {
bool was_decreasing = v.back() > v.front();
int num_inflections = 0;
for (int i = 0; i < v.size() && num_inflections <= 2; i++) {
bool is_decreasing = v[i] > v[(i+1)%v.size()];
// Check if this element and next one are an inflection.
if (was_decreasing != is_decreasing) {
num_inflections++;
was_decreasing = is_decreasing;
}
}
return 2 == num_inflections;
}

• Notas, dependiendo de su implementación:

Nota 1: Esta es la idea básica para atravesar una matriz circularmente:

for (int i = ip_index; i < array_length; i++) {
int index = (i + 1) % array_length; // wraps around to beginning
// Retrieve the value with
DoSomethingWithValue(array[index];)
}

Nota 2: Podría simplificar el código a una length + 1 bucle circular length + 1 , lo que garantizará que encuentre ambos puntos de inflexión.

Nota 3: O, podría simplificar el código si siempre busca el primer punto de inflexión que va aumentando o disminuyendo (antes de buscar otros puntos de inflexión). De esa manera, su escaneo solo tiene que preocuparse por encontrar exactamente otro punto de inflexión con el giro opuesto.

Nota 4: En cuanto a su ejemplo, no puede usar N/2 , porque el punto de inflexión no necesariamente ocurre en el punto medio de la matriz.