Siri Bercakap dengan Anda #1

**imej muka depan mencerminkan mood semasa siaran

Ingin bermula dengan pemikiran, bahawa untuk sementara waktu, saya mempunyai tabiat untuk menuliskan cabaran dan potensi penyelesaiannya yang pernah saya hadapi setiap hari, sama ada ia sebahagian daripada pekerjaan atau aktiviti masa lapang saya.

Bermula dari siaran ini, saya telah memutuskan untuk memperkenalkan siri "Bercakap dengan Anda", di mana saya akan menyiarkannya di sini (sekurang-kurangnya buat masa ini, paling banyak sekali dalam beberapa hari) untuk melihatnya kepada umum.

Di satu pihak sekarang saya akan melihat sekilas di sini dari semasa ke semasa dan bukannya nota berstruktur baik saya untuk merombak beberapa maklumat dan DevCommunity akan mengendalikan storan, navigasi dalam tertib menaik dan semua perkara lain, pada satu lagi saya percaya perkara itu Saya menulis di sini mungkin mendapati penonton bukan bagi pihak saya sahaja. Kencangkan, mari kita mulakan.

Kira Kejadian

Agak kerap bekerja dengan DS anda perlu mengira jumlah kejadian nilai dan kata penutup untuk menanyakannya dengan cara yang cekap, sebaik-baiknya Masa O(1).

Jelas sekali, anda mungkin terfikir untuk mencipta HashTable dan kemudian melintasi DS, mengisi HashTable. Itu benar dan mungkin kelihatan seperti:

iterable = [...]
hashtable = {}
for value in iterable:
    hashtable[value] = hashtable.get(value, 0) + 1

Hari ini saya menghadapi pendekatan alternatif yang akan berfungsi dengan sempurna pada senarai digit mengelakkan penggunaan HashTable (kadang-kadang ia mungkin satu keperluan).

Idea di sebalik adalah pertama sekali untuk mendapatkan nilai maksimum daripada senarai dan mencipta senarai baharu panjang nilai maksimum, yang akan digunakan sebagai pemetaan indeks.

list_ = [1, 1, 2, 3]
max_ = max(list_)
indices = [0] * max_   # [0, 0, 0, 0]

Sekarang, mari kita merentasi senarai asal dan memetakan kejadian setiap nilai dalam senarai indeks.

1. iteration
[1, 1, 2, 3] # list
 |

[0, 1, 0, 0] # indices

2. iteration
[1, 1, 2, 3] # list
    |

[0, 2, 0, 0] # indices

3. iteration
[1, 1, 2, 3] # list
       |

[0, 2, 1, 0] # indices

4. iteration
[1, 1, 2, 3] # list
          |

[0, 2, 1, 1] # indices

Apa yang baru berlaku. Pada asasnya, kami mengambil nilai daripada senarai asal dan menggunakannya sebagai indeks dalam senarai indeks kami (dan nilai tambahan pada indeks).

Sekarang jika kami ingin mewakili hasil kami menggunakan senarai pemetaan, kami mungkin berkata, terdapat 0 sifar-s kerana pada indeks 0 kita mempunyai nilai 0, pada indeks 1 kita mempunyai nilai 2, bermakna terdapat 2 satu -s, pada indeks 2 kita mempunyai nilai 1, bermakna terdapat 1 dua-s, dsb.

Elemen Cermin dalam Matriks

Walaupun memegang 2 darjah BSc dan MSc, apabila saya mengetahui helah matematik baru, saya masih mendapat perasaan yang menarik, aka "gosh, that's so simple and works".

Baiklah, kembali kepada topik, anggap anda mempunyai matriks N*N dan anda perlu menterbalikkan baris dan lajur dengan cara untuk mendapatkan jumlah maksimum semua elemen (baris demi baris).

matrix 4*4

1 2 3 9
0 9 8 2
5 1 7 4
8 2 6 7  

Dari pandangan pertama, mungkin anda tidak tahu dari mana hendak bermula. Tetapi inilah helah dengan elemen cermin.

matrix 4*4

A B B A
C D D C
C D D C 
A B B A

Perkara utama di sini ialah, A dalam matriks mungkin ditukar hanya oleh A-s yang lain. Mari kita gambarkan kita berada di sudut kiri atas A (iaitu 1) dan kami ingin tahu sama ada terdapat A lain (hanya bercermin A) iaitu parut. Dan sesungguhnya, kami mempunyai sedemikian di sudut kanan atas (9).

Mengikut logik dan mengingat semula masalah asal (jumlah maksimum membalikkan baris dan lajur) kami mungkin membuat kesimpulan bahawa pada hakikatnya kami tidak perlu melakukan sebarang operasi terbalik, sebaliknya hanya cari nilai maksimum antara yang dicerminkan. Dan itu sahaja.

timbunan. Tukar ganti antara kerumitan Masa dan Angkasa.

Anggapkan anda mempunyai tugas untuk melaksanakan pembalut tindanan dengan hanya 3 fungsi: (1) pop (2) push (3) get_min. Anda mungkin menggunakan antara muka tindanan untuk (1) pop dan (2) push, namun masih perlu melaksanakan (3) get_min. Annnd get_min() sepatutnya berfungsi untuk Masa O(1).

Nah, apabila saya mula-mula menangani masalah itu, saya benar-benar terlupa tentang pertukaran, yang mengatakan: "Apabila anda mengoptimumkan prestasi Masa, anda mungkin menjadi lebih teruk dengan Space dan sebaliknya". Mengapa ini penting, kerana saya mula memikirkan DS yang dioptimumkan yang membawa saya ke HashTables, tetapi saya benar-benar terlepas senarai naif, yang boleh berfungsi untuk O(1) (lunas) juga.

Jadi saya sampai ke tahap semasa saya mencipta HashTable di mana saya mungkin menyimpan setiap keadaan kelas pembalut ... akan berhenti di sini kerana "lebih mudah ialah pilihan yang lebih baik" (kadangkala). Mari lihat pelaksanaan dengan senarai tambahan untuk menyimpan nilai min bagi setiap keadaan tindanan.

class Wrapper:
   def __init__(self, stack):
      self.stack = stack
      self.min = []

   # Time O(1)
   def pop(self):
      self.stack.pop()
      self.min.pop()

   # Time O(1)
   def push(self, value):
      self.stack.push(value=value)
      min_ = self.min[-1]
      if value < min_:
          min_ = value
      self.min.append(min_)

   # Time O(1)
   def get_min(self):
      return self.min[-1]

Semudah itu.

Membuat kesimpulan

• teruskan pengekodan dan pembangunan
• ingat tentang pertukaran dan jangan terlalu rumit (apabila anda tidak diminta)

Atas ialah kandungan terperinci Siri Bercakap dengan Anda #1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!