ARTES #032

ARTES 032

Este é o artigo 32

ARTS é uma atividade iniciada por 由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS).

Desde Abril, porque os meus assuntos pessoais ocuparam todo o meu tempo livre, as artes foram suspensas durante quase 5 meses. Comecei a pegar essa semana. As questões anteriores do algoritmo foram todas implementadas em linguagem C. A partir deste artigo, eles são implementados em linguagem rápida.

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 uma matriz de números inteiros, retorne os índices de dois números de forma que sua soma seja igual a um alvo específico. Você pode assumir que haverá apenas uma solução para cada entrada e que não poderá usar o mesmo elemento duas vezes.

Solução

Para este problema da soma de dois números, a solução que todos podem imaginar é usar um loop de dois níveis. Então, existe uma solução melhor? Este problema pode ser transformado em uma soma conhecida de dois números e um número, e encontrar outro número; encontrar um número em uma matriz requer comparação um a um, o que é relativamente ineficiente. Existe uma boa maneira? Existe uma estrutura de dados em linguagens orientadas a objetos - um dicionário, que pode atender às nossas necessidades. Você pode primeiro converter o array em um dicionário, usar valor como chave e o subscrito do array é valor. Como pode-se supor que cada entrada terá apenas uma solução, não importa se existem valores duplicados no array. A implementação específica é a seguinte

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. Preveja o vencedor

Dificuldade: Média

Dada uma matriz de pontuações que são números inteiros não negativos. O jogador 1 escolhe um dos números de qualquer extremidade da matriz, seguido pelo jogador 2 e depois pelo jogador 1 e assim por diante. Cada vez que um jogador escolhe um número, esse número não estará disponível para o próximo jogador. Isso continua até que todas as pontuações tenham sido escolhidas. O jogador com a pontuação máxima vence.

Dada uma série de pontuações, preveja se o jogador 1 é o vencedor. Você pode assumir que cada jogador joga para maximizar sua pontuação.

Exemplo 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.

Exemplo 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 <= comprimento da matriz <= 20.
2. Quaisquer pontuações na matriz fornecida são números inteiros não negativos e não excederão 10.000.000.
3. Se as pontuações de ambos os jogadores forem iguais, o jogador 1 ainda é o vencedor.

Solução

Solução: programação 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];
    }
}

Revisão

Este artigo fala sobre o padrão de design do construtor por meio de código

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

Dicas

Quando estamos depurando, às vezes precisamos quebrar pontos para métodos do sistema, como pontos de interrupção para o método setFrame do UIView, mas não temos arquivos .m para métodos do sistema. Neste caso, podemos usar o seguinte método para quebrar pontos.

Aqui $arg1 representa o objeto que envia a mensagem, $arg2 representa o método, $arg3 representa o primeiro parâmetro e $arg4 representa o segundo parâmetro.

$arg1==0x7ff965544230; na figura acima significa que o endereço do objeto que envia a mensagem deve ser 0x7ff965544230; para acionar o ponto de interrupção

Compartilhar

Recentemente fui para a Tailândia. A Tailândia é um país budista. O que me surpreendeu é que seus carros e motos a bateria não estão trancados. Ao pagar, o caixa não identificará a autenticidade do dinheiro, mesmo que seja de 1.000 valores. Ouvi dizer que não há falsificação e roubo na Tailândia. Se um país não tiver falsificação e roubo, poderá economizar muitos recursos. Sem roubo, haverá vários dispositivos antifurto, como fechaduras, que podem economizar muitos recursos. Sem falsificação, haverá várias coisas para identificar a falsificação. A energia e os recursos gastos na falsificação e na identificação da falsificação podem ser usados ​​de maneiras úteis. Se você pensar desta forma, muitos recursos humanos são realmente desperdiçados. Se não houvesse guerra, não teríamos que formar um exército ou desenvolver diversas armas. Em vez disso, podemos investir o dinheiro e as pessoas utilizadas para formar o exército e desenvolver armas para melhorar o ambiente de vida da humanidade.