Bilangan Cara Memisahkan Tatasusunan

2270. Bilangan Cara Memisahkan Tatasusunan

Kesukaran: Sederhana

Topik: Tatasusunan, Jumlah Awalan

Anda diberi 0-diindeks nombor tatasusunan integer dengan panjang n.

nombor mengandungi pecahan yang sah pada indeks i jika yang berikut adalah benar:

• Jumlah unsur i 1 pertama ialah lebih besar daripada atau sama dengan hasil tambah n - i - 1 unsur terakhir.
• Terdapat sekurang-kurangnya satu elemen di sebelah kanan i. Iaitu, 0 <= i < n - 1.

Kembalikan bilangan pecahan yang sah dalam nombor.

Contoh 1:

• Input: nombor = [10,4,-8,7]
• Output: 2
• Penjelasan: Terdapat tiga cara untuk membahagikan nombor kepada dua bahagian yang tidak kosong:
  • Pisah nombor pada indeks 0. Kemudian, bahagian pertama ialah [10], dan hasil tambahnya ialah 10. Bahagian kedua ialah [4,-8,7], dan hasil tambahnya ialah 3. Oleh kerana 10 >= 3 , i = 0 ialah pemisahan yang sah.
  • Pisah nombor pada indeks 1. Kemudian, bahagian pertama ialah [10,4], dan hasil tambahnya ialah 14. Bahagian kedua ialah [-8,7], dan hasil tambahnya ialah -1. Oleh kerana 14 >= -1, i = 1 ialah pembahagian yang sah.
  • Pisah nombor pada indeks 2. Kemudian, bahagian pertama ialah [10,4,-8], dan hasil tambahnya ialah 6. Bahagian kedua ialah [7], dan hasil tambahnya ialah 7. Sejak 6 < 7, i = 2 bukan pemisahan yang sah.
  • Oleh itu, bilangan pecahan yang sah dalam nombor ialah 2.

Contoh 2:

• Input: nombor = [2,3,1,0]
• Output: 2
• Penjelasan: Terdapat dua pemisahan yang sah dalam nombor:
  • Pisah nombor pada indeks 1. Kemudian, bahagian pertama ialah [2,3], dan hasil tambahnya ialah 5. Bahagian kedua ialah [1,0], dan hasil tambahnya ialah 1. Oleh kerana 5 >= 1, i = 1 ialah pembahagian yang sah.
  • Pisah nombor pada indeks 2. Kemudian, bahagian pertama ialah [2,3,1], dan hasil tambahnya ialah 6. Bahagian kedua ialah [0], dan hasil tambahnya ialah 0. Oleh kerana 6 >= 0, i = 2 ialah pembahagian yang sah.

  Kekangan:

  • 2 <= nums.length <= 10⁵
  • -10⁵ <= nums[i] <= 10⁵

  Petunjuk:

  1. Untuk mana-mana indeks i, bagaimanakah kita boleh mencari jumlah unsur pertama (i 1) daripada hasil tambah unsur i pertama?
  2. Jika jumlah keseluruhan tatasusunan diketahui, bagaimanakah kita boleh menyemak sama ada jumlah unsur pertama (i 1) lebih besar daripada atau sama dengan unsur yang tinggal?

  Penyelesaian:

  Kita boleh mendekatinya menggunakan langkah berikut:

  Pendekatan:

  1. Jumlah Awalan: Mula-mula, kita mengira jumlah terkumpul tatasusunan dari sebelah kiri, yang membantu dalam menyemak jumlah unsur i 1 yang pertama.
  2. Jumlah Jumlah: Kira jumlah keseluruhan tatasusunan, yang berguna untuk menyemak sama ada jumlah unsur yang tinggal adalah kurang daripada atau sama dengan jumlah unsur i 1 yang pertama.
  3. Lelaran ke atas tatasusunan: Untuk setiap indeks i yang sah (di mana 0 <= i < n-1), kami menyemak sama ada jumlah unsur i 1 pertama adalah lebih besar daripada atau sama dengan jumlah elemen n-i-1 yang terakhir.
  4. Kecekapan: Daripada mengira semula jumlah berulang kali, gunakan jumlah awalan dan jumlah keseluruhan untuk perbandingan yang cekap.

  Mari laksanakan penyelesaian ini dalam PHP: 2270. Bilangan Cara Memisahkan Tatasusunan
  

  
  
  
  
  
  
    
    
    Penjelasan:
  
  
  
  
  $totalSum: Pembolehubah ini menyimpan jumlah semua elemen dalam tatasusunan nums.
  
  $prefixSum: Pembolehubah ini menjejaki jumlah terkumpul unsur dari sebelah kiri (sehingga indeks i).
  
  $remainingSum: Ini ialah jumlah elemen yang tinggal dari indeks i 1 hingga penghujung tatasusunan. Ia dikira dengan menolak $prefixSum daripada $totalSum.
  
  Semakan Pisahan Sah: Untuk setiap indeks i, kami menyemak sama ada jumlah awalan lebih besar daripada atau sama dengan jumlah baki.
  
  
  
    
    
    Kerumitan Masa:
  
  
  
  
  O(n): Kami mengulangi tatasusunan sekali untuk mengira jumlah dan sekali lagi untuk menyemak pembahagian yang sah. Oleh itu, kerumitan masa adalah linear berkenaan dengan panjang tatasusunan.
  
  
  
    
    
    Kerumitan Ruang:
  
  
  
  
  O(1): Kami hanya menggunakan beberapa pembolehubah tambahan ($totalSum, $prefixSum, $remainingSum), jadi kerumitan ruang adalah malar.
  
  
  Pautan Kenalan
  
  Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!
  
  Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:
  
  
  LinkedIn
  GitHub
  
  
  
            
  
              
    
  
              
          

Atas ialah kandungan terperinci Bilangan Cara Memisahkan Tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!