C #: String Berulang

Aug 20 2020

Dari tantangan "String Berulang" HackerRank:

Lilah memiliki tali, \$s\$, dari huruf kecil bahasa Inggris yang dia ulangi berkali-kali tanpa batas.

Diberikan bilangan bulat, \$n\$, cari dan cetak jumlah huruf a pertama \$n\$ huruf dari string tak terbatas Lilah.

Misalnya, jika string \$s=abcac\$dan \$n=10\$, sub string yang kami anggap adalah \$abcacabcac\$, yang pertama \$10\$karakter dari string tak terbatasnya. Ada \$4\$ kemunculan a di sub-string.

Kasus uji 1:

        string input = "aba";
        long n = 10;

Kasus uji 2:

        string input = "a";
        long n = 1000000000000;

Solusi Saya:

        string input = "aba";
        long n = 10;
        long numAs = input.Count(c => c.Equals('a'));

        if (input.Length == 0)
        {
            return 0;
        }

        long rem = n % input.Length;
        long reps = (n - rem) / input.Length;
        long count = reps * numAs;

        string sRem = input.Substring(0, (int)rem);

        if (rem != 0)
        {
            count += sRem.Count(c => c.Equals('a'));
        }

Hasilnya harus 7 dan 1000000000000. Solusi ini lulus semua kasus uji di HackerRank. Ini didasarkan pada solusi lain, terutama yang saya pilih.

Jawaban

4 MartinVerjans Aug 20 2020 at 21:46
  1. Apakah Anda perlu memvalidasi input?

Jika demikian, Anda harus menguji semua kasus:

  • masukan bisa jadi nol
  • masukan bisa berupa string kosong
  • n bisa menjadi negatif atau 0
  1. Nama variabel

Nama variabel itu penting, karena membantu memahami kode dengan lebih baik. Anda tidak harus membuatnya sekecil mungkin. Terutama ketika Anda memiliki IDE seperti VisualStudio yang akan membantu Anda memilih yang tepat dengan InteliSense.

  • numAs -> aCount
  • rem -> sisa
  • repetisi -> pengulangan
  • sRem -> sisaString
  1. Gagal dengan cepat

Biasanya lebih baik meninggalkan metode "secepat mungkin". Jadi, Anda ingin melakukan validasi input sebelum melakukan pekerjaan apa pun dan keluar dari metode jika tidak divalidasi. Dengan cara yang sama, jika sisa Anda 0, Anda dapat langsung mengembalikan hasil.

  1. Divisi bilangan bulat

Untuk menghitung pengulangan Anda, kurangi sisanya dari n. Jika Anda memeriksa pembagian integer di C # , Anda tidak perlu:

long repetitions = n / input.length;
  1. Gunakan Linq

Sesuai solusi tinstaafl , Anda dapat menggunakan LINQ untuk menyimpan variabel dan baris:

count += remainderString.Take((int)remainder).Count(c => c.Equals('a'));

Jadi, secara keseluruhan, Anda mendapatkan:

long aCount = input.Count(c => c.Equals('a'));

if (input == null || input.Length == 0 || n <= 0)
{
    return 0;
}

long repetitions = n / input.Length;
long remainder = n % input.Length;
long count = repetitions * aCount;

if (remainder == 0)
{
    return count;
}

return count + remainderString.Take((int)remainder).Count(c => c.Equals('a'));
2 tinstaafl Aug 20 2020 at 05:06

Saya tidak melihat banyak hal untuk ditingkatkan. Namun, saya memperhatikan beberapa hal:

Pintasan bersyarat:

if (input.Length == 0)
{
    return 0;
}

harus menjadi hal pertama dalam kode Anda setelahnya input

Demikian pula dengan:

string sRem = input.Substring(0, (int)rem);

if (rem != 0)
{
    count += sRem.Count(c => c.Equals('a'));
}

Anda tidak membutuhkan string itu kecuali rem> 0, jadi sertakan itu dalam blok bersyarat. Bahkan lebih baik lagi, gunakan ekstensi LINQ, Takedan lakukan semuanya dalam satu pernyataan:

if (rem != 0)
{
    count += sRem.Take((int)rem).Count(c => c.Equals('a'));
}
2 iSR5 Aug 21 2020 at 07:25

Poin yang sama dengan jawaban lain, namun ada solusi yang lebih sederhana untuk ini, Anda cukup mengganti Adengan string kosong, dan membandingkan panjang kedua string, yang akan memberi Anda jumlah A.

Berikut ini contohnya:

public static long RepeatedString(string s, long n)
{
    if (string.IsNullOrWhiteSpace(s) || n <= 0) { return 0; }
    
    // Local function that would return the number of A's 
    long CountA(string input) => input.Length - input.Replace("a", "").Length;
    
    var aCount = CountA(s);
    
    var reminder = n % s.Length; 
    
    var repetition = (n - reminder) / s.Length;
    
    var count = repetition * aCount;

    var reminderStr = s.Substring(0, (int)reminder);
    
    var result = count + CountA(reminderStr);
    
    return result;
}
1 Noname Aug 22 2020 at 01:50

Saya tidak dapat menambahkan banyak hal pada apa yang telah ditulis, selain dalam hal kinerja, Anda akan sering menemukan Linq ( long numAs = input.Count(c => c.Equals('a'));) agak lambat dibandingkan dengan yang lebih tradisional foratau whileloop. Tetapi jika Anda bersikeras pada Linq, Anda dapat melanjutkan semuanya seperti:

long CountChars(string data, long length, char c = 'a')
{
  if (string.IsNullOrEmpty(data) || length <= 0) return 0;

  long repetitions = length / data.Length;
  long remSize = length % data.Length;

  return data
    .Select((ch, i) => (ch, i))
    .Where(chi => chi.ch == c)
    .Sum(chi => chi.i < remSize ? repetitions + 1 : repetitions);
}

Di sini digunakan overload Select()yang menyediakan indeks bersama dengan setiap elemen untuk dipetakan ke tupel nilai, dari mana dimungkinkan untuk memfilter 'a'dan akhirnya merangkum pengulangan: jika indeks lebih kecil dari ukuran pengingat maka repetitions + 1harus dijumlahkan sebaliknya hanya pengulangan untuk setiap ditemukan 'a'.


Pendekatan tradisional menggunakan while-loops - pada dasarnya menggunakan pendekatan yang sama seperti di atas bisa terlihat seperti:

long CountChars(string data, long length, char c = 'a')
{
  if (string.IsNullOrEmpty(data) || length <= 0) return 0;

  long count = 0;
  long repetitions = length / data.Length + 1; // + 1 for the possible extra 'a' in the reminder
  long remSize = length % data.Length;

  int i = 0;

  while (i < remSize)
  {
    if (data[i++] == c)
      count += repetitions;
  }

  repetitions--;
  while (i < data.Length)
  {
    if (data[i++] == c)
      count += repetitions;
  }

  return count;
}

Dengan pendekatan ini string s( data) hanya diurai satu kali.