ARTES #032

##ARTES 032

este es el articulo 32

ARTES es una actividad iniciada por 由左耳朵耗子--陈皓: Haga al menos una pregunta sobre el algoritmo leetcode cada semana, lea y comente al menos un artículo técnico en inglés, aprenda al menos una habilidad técnica y comparta un artículo con opiniones y pensamientos. (Es decir, Algoritmo, Revisión, Consejo y Compartir se denominan ARTS).

Desde abril, debido a que mis asuntos personales han ocupado todo mi tiempo libre, las artes han estado suspendidas durante casi 5 meses. Empecé a recogerlo esta semana. Todas las preguntas del algoritmo anterior se implementaron en lenguaje C. A partir de este artículo, se implementan en lenguaje rápido.

Algoritmo

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Dada una matriz de números enteros, devuelve los índices de dos números de modo que su suma sea igual a un objetivo específico. Puedes asumir que solo habrá una solución para cada entrada y que no puedes usar el mismo elemento dos veces.

Solución

Para este problema de la suma de dos números, la solución que todos pueden pensar es utilizar un bucle de dos niveles. Entonces, ¿existe una solución mejor? Este problema se puede transformar en una suma conocida de dos números y un número, y encontrar otro número; encontrar un número en una matriz requiere una comparación uno a uno, lo cual es relativamente ineficiente. ¿Existe una buena manera? Existe una estructura de datos en los lenguajes orientados a objetos: un diccionario, que puede satisfacer nuestras necesidades. Primero puede convertir la matriz en un diccionario, usar el valor como clave y el subíndice de la matriz es el valor. Como se puede suponer que cada entrada tendrá solo una solución, no importa si hay valores duplicados en la matriz. La implementación específica es la siguiente.

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var numbersDictionary: [Int: Int] = [:]
        
        for index in 0...(nums.count - 1){
            let number = nums[index]
            numbersDictionary[number] = index
        }
        
        
        for index in 0...(nums.count - 1) {
            let number = nums[index]
            let remainder = target - number
            
            let indexOfTarget = numbersDictionary[remainder]
            if let indexOfTarget = indexOfTarget {
                if(indexOfTarget != index){
                    return [indexOfTarget, index]
                }
                
            }
            
        }
        return []
    }
}

​ ​

486. Predecir el ganador

Dificultad: Media

Dada una serie de puntuaciones que son números enteros no negativos. El jugador 1 elige uno de los números de cada extremo de la matriz, seguido por el jugador 2 y luego el jugador 1, y así sucesivamente. Cada vez que un jugador elige un número, ese número no estará disponible para el siguiente jugador. Esto continúa hasta que se hayan elegido todas las puntuaciones. El jugador con la puntuación máxima gana.

Dada una serie de puntuaciones, predice si el jugador 1 es el ganador. Puedes asumir que cada jugador juega para maximizar su puntuación.

Ejemplo 1:

Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2\. If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5\. If player 2 chooses 5, then player 1 will be left with 1 (or 2). So, final score of player 1 is 1 + 2 = 3, and player 2 is 5\. Hence, player 1 will never be the winner and you need to return False.

Ejemplo 2:

Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1\. Then player 2 have to choose between 5 and 7\. No matter which number player 2 choose, player 1 can choose 233.Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Nota:

1. 1 <= longitud de la matriz <= 20.
2. Cualquier puntuación en la matriz dada es un número entero no negativo y no excederá 10.000.000.
3. Si las puntuaciones de ambos jugadores son iguales, entonces el jugador 1 sigue siendo el ganador.

Solución

Solución: programación dinámica

Idioma: Rápido

class Solution {
//    var  dp1  = ()
    var  dp = [[Int]]()
    
    func PredictTheWinner(_ nums: [Int]) -> Bool{
        if (nums.count%2==0){
             return true;
        }
        
        dp = [[Int]](repeating: [Int](repeating: 0, count: nums.count), count: nums.count)
        return recur(nums,0,nums.count-1)>=0;
    }
    
    func recur(_ nums: [Int], _ start:Int, _ end:Int) -> Int{
        if (start == end){
            return nums[start];
        }
        if dp[start][end] != 0 {
            return dp[start][end];
        }
        let left:Int = nums[start] - recur(nums, start+1, end);
        let right:Int = nums[end] - recur(nums, start, end-1);
        dp[start][end] = max(left, right);//ma.max(left, right);
        
        return dp[start][end];
    }
}

Revisión

Este artículo habla sobre el patrón de diseño del constructor a través del código.

https://dandan2009.github.io/2019/10/17/design-patterns-by-tutorials-the-power-of-OOP-part-1/

Consejos

Cuando estamos depurando, a veces necesitamos puntos de interrupción para los métodos del sistema, como puntos de interrupción para el método setFrame de UIView, pero no tenemos archivos .m para los métodos del sistema. En este caso, podemos utilizar el siguiente método para romper puntos.

Aquí $arg1 representa el objeto que envía el mensaje, $arg2 representa el método, $arg3 representa el primer parámetro y $arg4 representa el segundo parámetro.

$arg1==0x7ff965544230; en la figura anterior significa que la dirección del objeto que envía el mensaje debe ser 0x7ff965544230; para activar el punto de interrupción

Compartir

Hace poco fui a Tailandia. Tailandia es un país budista. Lo que me sorprendió es que sus coches y motos a batería no están cerrados con llave. Al pagar, el cajero no identificará la autenticidad del dinero, aunque sea de 1.000 denominaciones. Escuché que en Tailandia no hay falsificaciones ni robos. Si un país no sufre falsificaciones ni robos, puede ahorrar muchos recursos. Sin robo, habrá varios elementos antirrobo, como cerraduras, que pueden ahorrar muchos recursos. Sin falsificación, habrá varias cosas para identificar la falsificación. La energía y los recursos invertidos en la falsificación y en su identificación pueden utilizarse de manera útil. Si lo piensas de esta manera, en realidad se desperdician muchos recursos humanos. Si no hay guerra, no tendríamos que formar un ejército ni desarrollar diversas armas. En lugar de ello, podemos invertir el dinero y el personal utilizados para formar el ejército y desarrollar armas para mejorar el entorno de vida de la humanidad.