Categoría: Algorithms

Categorías
Algorithms

Convertir BST en una lista ordenada doblemente enlazada (Java)

Deje que el hijo izquierdo de cada nodo sea el siguiente nodo más pequeño y el hijo derecho de cada nodo sea el siguiente nodo más grande.

Node prev = null;
Node head = null;
 
public Node treeToDoublyList(Node root) {
    if (root == null) {
        return null;
    }
 
    helper(root);
 
    head.left = prev;
    prev.right = head;
 
    return head;
}
 
private void helper(Node p) {
    if (p == null) {
        return;
    }
 
    helper(p.left);
 
    //handle current
    if (prev == null) {
        head = p;
    } else {
        prev.right = p;
        p.left = prev;
    }
 
    prev = p;
 
    helper(p.right);
}

Artículos Relacionados:

  1. LeetCode – Lista enlazada de Palindrome (Java)
  2. LeetCode – Lista vinculada inversa II (Java)
  3. Lista enlazada doble inversa
  4. LeetCode – Eliminar elementos de listas vinculadas (Java)

Categorías
Algorithms

LeetCode – Comparación de cadenas de retroceso (Java)

Dadas dos cadenas S y T, devuelva si son iguales cuando ambas se escriben en editores de texto vacíos. # significa un carácter de retroceso.

Ejemplo 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Ejemplo 2:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Solución Java

Este problema requiere tiempo O (N) y espacio O (1).

public boolean backspaceCompare(String S, String T) {
    int i = S.length()-1;
    int j = T.length()-1;
 
    while(i>=0 || j>=0){
        int c1=0;
        while(i>=0 && (c1>0 || S.charAt(i)=='#')){
            if(S.charAt(i)=='#'){
                c1++;
            }else{
                c1--;
            }
 
            i--;
        }
 
        int c2=0;
        while(j>=0 && (c2>0 || T.charAt(j)=='#')){
            if(T.charAt(j)=='#'){
                c2++;
            }else{
                c2--;
            }
 
            j--;
        }
 
        if(i>=0 && j>=0){
            if(S.charAt(i)!=T.charAt(j)){
                return false;
            }else{
                i--;
                j--;
            }
        }else{
            if(i>=0 || j>=0){
                return false;
            }
        }
    }
 
    return i<0 && j<0;
}

Artículos Relacionados:

  1. LeetCode – Comparar números de versión (Java)
  2. LeetCode – Eliminar dígitos K (Java)
  3. LeetCode – Partición a subconjuntos de suma igual K (Java)
  4. LeetCode – Palabras expresivas (Java)

Categorías
Algorithms

Evaluar expresiones matemáticas con más, menos y paréntesis (java)

Dada una cadena de expresión matemática, como 1- (2 + 3), evalúe el valor. La expresión contiene solo dígitos, +, – y paréntesis.

Solución Java

import java.util.ArrayList;
import java.util.Stack;
 
public class ExpressionEvaluator {
    static class Node {
        Boolean isPositive;
        Integer value;
        ArrayList<Node> list;
 
        public Node(boolean isPositive, Integer value) {
            this.isPositive = isPositive;
            this.value = value;
            this.list = new ArrayList<>();
        }
 
        public int evaluate() {
            int sum = 0;
            for (Node t : list) {
                if (t.isPositive) {
                    sum = sum + t.value;
                } else {
                    sum = sum - t.value;
                }
            }
            return sum;
        }
    }
 
    public static int evaluate(String s) {
        Stack<Node> stack = new Stack<>();
        stack.push(new Node(true, 0));
 
        Boolean isPositive = true;
        StringBuilder sb = null;
 
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Node top = stack.peek();
 
            if (c >= '0' && c <= '9') {
                if (sb == null) {
                    sb = new StringBuilder();
                }
                sb.append(c);
                if (i == s.length() - 1
                        || s.charAt(i + 1) < '0' || s.charAt(i + 1) > '9') {
                    top.list.add(new Node(
                            isPositive == null ? true : isPositive,
                            Integer.valueOf(sb.toString())));
                    isPositive = null;
                    sb = null;
                }
            } else if (c == '(') {
                Node t = new Node(isPositive, null);
                isPositive = null;
                top.list.add(t);
                stack.push(t);
            } else if (c == ')') {
                int val = stack.pop().evaluate();
                top = stack.peek();
                top.list.get(top.list.size() - 1).value = val;
            } else if (c == '-' || c == '+') {
                if (c == '-') {
                    isPositive = false;
                } else {
                    isPositive = true;
                }
            }
        }
 
        return stack.peek().evaluate();
    }
 
 
    public static void main(String[] args) {
        System.out.println(evaluate("(1-20)+3")); //-16
        System.out.println(evaluate("1-(20+1-(2+3))")); //-15
    }
}

Artículos Relacionados:

  1. LeetCode – Evaluar la notación polaca inversa
  2. LeetCode – Paréntesis válidos (Java)
  3. LeetCode – Paréntesis válidos más largos (Java)
  4. LeetCode – Cadena de decodificación (Java)

Categorías
Algorithms

LeetCode – Permutación en cadena (Java)

Dadas dos cadenas s1 y s2, escriba una función que devuelva verdadero si s2 contiene la permutación de s1. En otras palabras, una de las permutaciones de la primera cadena es la subcadena de la segunda cadena.

Por ejemplo:

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Solución Java

public boolean checkInclusion(String s1, String s2) {
    HashMap<Character, Integer> dict = new HashMap<>();
    for (int i = 0; i < s1.length(); i++) {
        int feq = dict.getOrDefault(s1.charAt(i), 0);
        dict.put(s1.charAt(i), feq + 1);
    }
 
    HashMap<Character, Integer> temp = new HashMap<>();
    int i = 0;
    for (int j = 0; j < s2.length(); j++) {
        if (!dict.containsKey(s2.charAt(j))) {
            i = j + 1;
            temp.clear(); //clear counter
            continue;
        }
 
        int count = temp.getOrDefault(s2.charAt(j), 0);
        if (count == 0 || count < dict.get(s2.charAt(j))) {
            temp.put(s2.charAt(j), count + 1);
 
            if (j - i + 1 == s1.length()) {
                return true;
            }
        } else {
            while (i < j) {
                if (s2.charAt(i) == s2.charAt(j)) {
                    i++;
                    break;
                }
 
                temp.put(s2.charAt(i), temp.get(s2.charAt(i)) - 1);
                i++;
            }
        }
    }
 
    return false;
}

Artículos Relacionados:

  1. LeetCode – Subcadena de ventana mínima (Java)
  2. LeetCode – Reorganizar cadena k distancia aparte (Java)
  3. LeetCode – Siguiente permutación (Java)
  4. LeetCode – Total de subsecuencias distintas (Java)

Categorías
Algorithms

LeetCode – Costo mínimo para contratar trabajadores K (Java)

Hay N trabajadores. El i-ésimo trabajador tiene una cualidad[i] y un salario mínimo de expectativa de salario[i].

Ahora queremos contratar exactamente K trabajadores para formar un grupo remunerado. Al contratar un grupo de trabajadores K, debemos pagarles de acuerdo con las siguientes reglas:
A cada trabajador del grupo remunerado se le debe pagar en la proporción de su calidad en comparación con otros trabajadores del grupo remunerado.
A cada trabajador del grupo remunerado se le debe pagar al menos su salario mínimo esperado.
Devuelva la menor cantidad de dinero necesaria para formar un grupo pagado que satisfaga las condiciones anteriores.

Ejemplo:

Input: quality = [10,20,5], wage = [70,50,30], K = 2
Output: 105.00000
Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.

Solución Java

Primero, clasifique a los trabajadores por su relación salario / calidad en orden ascendente. El valor de la relación más pequeño significa mejor calidad y bajos salarios. Luego, pruebe primero la mejor proporción y use el montón para rastrear la calidad más grande. Dada una proporción, la calidad más grande se elimina de la cola porque requiere más salario.

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        ArrayList<Worker> list = new ArrayList<>();
        for(int i=0; i<wage.length; i++){
            list.add(new Worker(quality[i], wage[i]));
        }
        Comparator<Worker> comp = Comparator.comparing((Worker w) -> w.ratio);
        Collections.sort(list, comp);
 
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int sum = 0;
        double result = Integer.MAX_VALUE;
 
        for(int i=0; i<list.size(); i++){
            Worker w = list.get(i);
            sum += w.quality;
            q.offer(-w.quality);
 
            if(q.size()>K){
                int extra = q.poll();
                sum += extra;
            }
 
            if(q.size() == K){
                result = Math.min(result, sum * w.ratio);        
            }
        }
 
        return result;
    }
}
 
class Worker{
    int quality;
    int wage;
    double ratio;
 
    public Worker(int q, int w){
        this.quality = q;
        this.wage = w;
        this.ratio = (double)w/q;
    }
}

Artículos Relacionados:

  1. LeetCode – Árboles de altura mínima (Java)
  2. LeetCode – Rectángulo de área mínima (Java)
  3. LeetCode – Cadenas cambiadas de grupo (Java)
  4. LeetCode – Subsecuencia de ventana mínima (Java)

Categorías
Algorithms

LeetCode – Coincidencia de cadenas repetidas (Java)

Dadas dos cadenas A y B, encuentre el número mínimo de veces que A debe repetirse de manera que B sea una subcadena de la misma. Si no hay tal solución, devuelve -1.

Por ejemplo, con A = «abcd» y B = «cdabcdab».

Retorna 3, porque al repetir A tres veces (“abcdabcdabcd”), B es una subcadena de la misma; y B no es una subcadena de A repetida dos veces («abcdabcd»).

Nota:
La longitud de A y B estará entre 1 y 10000.

Solución Java

La complejidad temporal de la solución óptima es O (n) donde n es la longitud de la cuerda más larga de A y B.

public int repeatedStringMatch(String A, String B) {
    int i = 0;
    int j = 0;
 
    int result = 0;
    int k = 0;
 
    while (j < B.length()) {
        if (A.charAt(i) == B.charAt(j)) {
            i++;
            j++;
 
            if (i == A.length()) {
                i = 0;
                result++;
            }
        } else {
            k++;
            if (k == A.length()) {
                return -1;
            }
            i = k;
            j = 0;
            result = 0;
        }
    }
 
    if (i > 0) {
        result++;
    }
 
    return result;
}

Artículos Relacionados:

  1. LeetCode – Secuencias de ADN repetidas (Java)
  2. LeetCode – Permutación en cadena (Java)
  3. LeetCode – Cadena a entero (atoi) (Java)
  4. LeetCode – Eliminar paréntesis no válidos (Java)

Categorías
Algorithms

LeetCode – Ajuste de pantalla de frases (Java)

Dada una pantalla de filas x columnas y una oración representada por una lista de palabras no vacías, averigüe cuántas veces se puede colocar la oración dada en la pantalla.

Nota:
Una palabra no se puede dividir en dos líneas.
El orden de las palabras en la oración no debe modificarse.
Dos palabras consecutivas en una línea deben estar separadas por un solo espacio.

Solución Java

public int wordsTyping(String[] sentence, int rows, int cols) {
    int i = 0;
    int cnt = 0;
 
    int k = 0;  //kth word
    int colLen = cols;
 
    while (i < rows) {
        String sen = sentence[k++];
        if (sen.length() > cols) {
            return 0;
        }
 
        if (colLen >= sen.length()) {
            colLen = colLen - sen.length() - 1;
        } else {
            i++;
            colLen = cols;
            colLen = colLen - sen.length() - 1;
        }
 
        if (i >= rows) {
            return cnt;
        }
 
        if (k == sentence.length) {
            cnt++;
            k = 0;
        }
    }
 
    return cnt;
}

Artículos Relacionados:

  1. LeetCode – Mejor punto de encuentro (Java)
  2. LeetCode – Tic-Tac-Toe (Java)
  3. LeetCode – Producto máximo de longitudes de palabras (Java)
  4. LeetCode – Word Break II (Java)

Categorías
Algorithms

LeetCode – Próxima hora más cercana (Java)

Dado un tiempo representado en el formato «HH: MM», forme el siguiente tiempo más cercano reutilizando los dígitos actuales. No hay límite en la cantidad de veces que se puede reutilizar un dígito.

Puede asumir que la cadena de entrada proporcionada es siempre válida. Por ejemplo, «01:34», «12:09» son todos válidos. «1:34», «12: 9» no son válidos.

Ejemplo 1:

Entrada: «19:34»
Salida: «19:39»
Explicación: La siguiente hora más cercana a elegir entre los dígitos 1, 9, 3, 4 es 19:39, que ocurre 5 minutos más tarde. No son las 19:33, porque esto ocurre 23 horas y 59 minutos después.

Solución Java

public String nextClosestTime(String time) {
    ArrayList<Integer> list = new ArrayList<>();
    ArrayList<Character> charList = new ArrayList<>();
    TreeSet<Integer> set = new TreeSet<>();
 
    //get digit list
    for (int i = 0; i < time.length(); i++) {
        if (time.charAt(i) >= '0' && time.charAt(i) <= '9') {
            charList.add(time.charAt(i));
        }
    }
 
    //get all possible number combinations
    for (int i = 0; i < charList.size(); i++) {
        for (int j = 0; j < charList.size(); j++) {
            set.add(Integer.parseInt(charList.get(i) + "" + charList.get(j)));
        }
    }
 
    //add to list
    list.addAll(set);
 
    String[] arr = time.split(":");
    int hour = Integer.parseInt(arr[0]);
    int min = Integer.parseInt(arr[1]);
 
    int idxMin = search(list, min);
    int idxHour = search(list, hour);
 
    String hh = "";
    String mm = "";
 
    if (idxMin < list.size() - 1 && list.get(idxMin + 1) < 60) {
        hh = hour + "";
        mm = list.get(idxMin + 1) + "";
    } else {
        if (idxHour < list.size() - 1 && list.get(idxHour + 1) < 24) {
            hh = list.get(idxHour + 1) + "";
            mm = list.get(0) + "";
        } else {
            hh = list.get(0) + "";
            mm = list.get(0) + "";
        }
    }
 
    if (hh.length() < 2) {
        hh = "0" + hh;
    }
 
    if (mm.length() < 2) {
        mm = "0" + mm;
    }
 
    return hh + ":" + mm;
}
 
private int search(ArrayList<Integer> list, int target) {
    int i = 0;
    int j = list.size() - 1;
 
    while (i < j) {
        int m = i + (j - i) / 2;
        if (list.get(m) < target) {
            i = m + 1;
        } else {
            j = m;
        }
    }
 
    return j;
}

Artículos Relacionados:

  1. LeetCode – Combinaciones de letras de un número de teléfono (Java)
  2. LeetCode – Plus One (Java)
  3. LeetCode – 3Sum Closest (Java)
  4. LeetCode – Cadena de decodificación (Java)

Categorías
Algorithms

LeetCode – Mi calendario II (Java)

Implemente una clase MyCalendarTwo para almacenar sus eventos. Se puede agregar un nuevo evento si agregar el evento no causa una reserva triple.

Tu clase tendrá un método, book (int start, int end). Formalmente, esto representa una reserva en el intervalo semiabierto[inicio, fin), el rango de números reales x tal que inicio <= x 

Example:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true

Solución Java

Esta es una versión más complicada de My Calendar I, en la que solo nos importa si ya se usa un intervalo de tiempo. Para este problema, podemos agregar otra lista para rastrear los intervalos reservados dobles.

class MyCalendarTwo {
    ArrayList<int[]> single = null;
    ArrayList<int[]> overlap = null;
 
    public MyCalendarTwo() {
        single = new ArrayList<>();
        overlap = new ArrayList<>();
    }
 
    public boolean book(int start, int end) {
        for (int[] itv : overlap) {
            if (end > itv[0] && start < itv[1]) {
                return false;
            }
        }
 
        for (int[] itv : single) {
            if (end > itv[0] && start < itv[1]) {
                overlap.add(new int[]{Math.max(itv[0], start), Math.min(itv[1], end)});
            }
        }
 
        single.add(new int[]{start, end});
 
        return true;
    }
}

La complejidad del tiempo es O (N ^ 2) ya que cada operación del libro itera sobre todos los intervalos existentes. La complejidad del espacio es O (N).

Artículos Relacionados:

  1. LeetCode – Área de rectángulo (Java)
  2. LeetCode – Max Chunks para ordenar (Java)
  3. LeetCode – Poder de tres (Java)
  4. LeetCode: subcadena más larga sin caracteres repetidos (Java)

Categorías
Algorithms

LeetCode – K ranuras vacías (Java)

Dado un jardín con N ranuras. En cada ranura hay una flor. Cada una de las N flores florecerá una a una en N días. En cada día, habrá exactamente una flor floreciendo y seguirá floreciendo desde entonces.

Dada una matriz de números del 1 al N. Cada número de la matriz es la ranura donde la flor se abrirá en (i + 1) -ésimo día. Por ejemplo, la matriz [5, 3, 1, 4, 2] significa que el flujo 5 florecerá el día 1, la flor 3 florecerá el día 2, la flor 1 florecerá el día 3, etc.

Dado un número entero k, devuelve el primer día en el que existen dos flores floreciendo y también las flores entre ellas es k y estas flores no están floreciendo.

Solución Java 1

public int kEmptySlots(int[] flowers, int k) {
    int[] days = new int[flowers.length + 1];
    for (int i = 0; i < flowers.length; i++) {
        days[flowers[i]] = i + 1;
    }
 
    int result = Integer.MAX_VALUE;
 
    for (int i = 1; i < days.length - k - 1; i++) {
        int l = days[i];
        int r = days[i + k + 1];
 
        int max = Math.max(l, r);
        int min = Math.min(l, r);
 
 
        boolean flag = true;
        for (int j = 1; j <= k; j++) {
            if (days[i + j] < max) {
                flag = false;
                break;
            }
        }
 
        if (flag && max < result) {
            result = max;
        }
    }
 
    return result == Integer.MAX_VALUE ? -1 : result;
}

La complejidad del tiempo es O (N * k) y la complejidad del espacio es O (N).

Solución Java 2

public int kEmptySlots2(int[] flowers, int k) {
    TreeSet<Integer> set = new TreeSet<>();
 
    for (int i = 0; i < flowers.length; i++) {
        Integer higher = set.higher(flowers[i]);
        Integer lower = set.lower(flowers[i]);
 
        if (lower != null && flowers[i] - k - 1 == lower) {
            return i + 1;
        }
 
        if (higher != null && flowers[i] + k + 1 == higher) {
            return i + 1;
        }
 
        set.add(flowers[i]);
    }
 
    return -1;
}

La complejidad del tiempo es O (N * log (N)) y la complejidad del espacio es O (N).

Artículos Relacionados:

  1. LeetCode: subcadena más larga sin caracteres repetidos (Java)
  2. LeetCode – Entero inverso
  3. LeetCode – Prefijo común más largo (Java)
  4. LeetCode – Longitud de la última palabra (Java)