SENI #032

SENI 032

Ini adalah pasal 32

SENI adalah kegiatan yang diprakarsai oleh 由左耳朵耗子--陈皓: Kerjakan setidaknya satu pertanyaan algoritma leetcode setiap minggu, baca dan komentari setidaknya satu artikel teknis berbahasa Inggris, pelajari setidaknya satu keterampilan teknis, dan bagikan artikel yang berisi opini dan pemikiran. (Artinya, Algoritma, Review, Tip, dan Share disebut sebagai SENI).

Sejak April, karena urusan pribadiku menyita seluruh waktu luangku, kesenian terhenti selama hampir 5 bulan. Saya mulai mengambilnya minggu ini. Pertanyaan algoritma sebelumnya semuanya diimplementasikan dalam bahasa C. Dari artikel ini, mereka diimplementasikan dalam bahasa cepat.

Algoritma

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

Diberikan array bilangan bulat, kembalikan indeks dua angka sedemikian rupa sehingga jumlahnya sama dengan target tertentu. Anda dapat berasumsi bahwa hanya akan ada satu solusi untuk setiap masukan dan Anda tidak dapat menggunakan elemen yang sama dua kali.

Solusi

Untuk soal penjumlahan dua bilangan ini, solusi yang terpikirkan oleh semua orang adalah dengan menggunakan perulangan dua tingkat. Jadi apakah ada solusi yang lebih baik? Soal ini dapat diubah menjadi jumlah yang diketahui dari dua bilangan dan sebuah bilangan, dan mencari bilangan lain; menemukan angka dalam array memerlukan perbandingan satu-ke-satu, yang relatif tidak efisien. Apakah ada cara yang baik? Ada struktur data dalam bahasa berorientasi objek - kamus, yang dapat memenuhi kebutuhan kita. Pertama-tama Anda dapat mengonversi array menjadi kamus, menggunakan nilai sebagai kuncinya, dan subskrip array adalah nilai. Karena dapat diasumsikan bahwa setiap input hanya memiliki satu solusi, tidak masalah jika ada nilai duplikat dalam array. Implementasi spesifiknya adalah sebagai berikut

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. Prediksi Pemenangnya

Kesulitan: Sedang

Diberikan serangkaian skor yang merupakan bilangan bulat non-negatif. Pemain 1 memilih salah satu nomor dari kedua ujung array diikuti oleh pemain 2 dan kemudian pemain 1 dan seterusnya. Setiap kali pemain memilih nomor, nomor tersebut tidak akan tersedia untuk pemain berikutnya. Ini berlanjut sampai semua skor telah dipilih. Pemain dengan skor maksimum menang.

Berdasarkan serangkaian skor, prediksi apakah pemain 1 adalah pemenangnya. Anda dapat berasumsi setiap pemain bermain untuk memaksimalkan skornya.

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

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

Catatan:

1. 1 <= panjang array <= 20.
2. Skor apa pun dalam larik yang diberikan adalah bilangan bulat non-negatif dan tidak akan melebihi 10.000.000.
3. Jika skor kedua pemain sama, maka pemain 1 tetap menjadi pemenangnya.

Solusi

Solusi: pemrograman dinamis

Bahasa: cepat

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];
    }
}

Ulasan

Artikel ini membahas tentang pola desain pembangun melalui kode

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

Kiat

Saat kita melakukan debug, terkadang kita perlu break point untuk metode sistem, seperti break point untuk metode setFrame di UIView, tetapi kita tidak memiliki file .m untuk metode sistem. Dalam hal ini, kita dapat menggunakan metode berikut untuk memecahkan poin.

Di sini $arg1 mewakili objek pengirim pesan, $arg2 mewakili metode, $arg3 mewakili parameter pertama, dan $arg4 mewakili parameter kedua.

$arg1==0x7ff965544230; pada gambar di atas berarti alamat objek pengirim pesan harus 0x7ff965544230; untuk memicu breakpoint

Bagikan

Saya baru-baru ini pergi ke Thailand. Thailand adalah negara Budha. Yang mengejutkan saya, aki mobil dan motor mereka tidak dikunci. Saat membayar, kasir tidak akan mengidentifikasi keaslian uangnya, meski pecahan 1.000. Saya mendengar bahwa tidak ada pemalsuan dan pencurian di Thailand. Jika suatu negara tidak mengalami pemalsuan dan pencurian, negara tersebut dapat menghemat banyak sumber daya. Tanpa pencurian, akan ada berbagai hal anti maling, seperti kunci, yang dapat menghemat banyak sumber daya. Tanpa pemalsuan, akan ada berbagai hal untuk mengidentifikasi pemalsuan. Energi dan sumber daya yang dihabiskan untuk melakukan pemalsuan dan mengidentifikasi pemalsuan dapat digunakan dengan cara yang bermanfaat. Kalau dipikir-pikir, banyak sumber daya manusia yang justru terbuang percuma. Jika tidak ada perang, kita tidak perlu menambah tentara atau mengembangkan berbagai senjata. Sebaliknya, kita dapat menginvestasikan uang dan orang-orang yang digunakan untuk membentuk tentara dan mengembangkan senjata guna memperbaiki lingkungan hidup umat manusia.