C #: Chuỗi lặp lại

Question

Từ thử thách "Chuỗi lặp lại" của HackerRank:

Lilah có một chuỗi, \$s\$, những chữ cái tiếng Anh viết thường mà cô ấy lặp đi lặp lại vô số lần.

Cho một số nguyên, \$n\$, tìm và in số ký tự a trong \$n\$ chữ cái của chuỗi vô hạn của Lilah.

Ví dụ, nếu chuỗi \$s=abcac\$và \$n=10\$, chuỗi con mà chúng tôi coi là \$abcacabcac\$, đầu tiên \$10\$ký tự của chuỗi vô hạn của cô ấy. Có \$4\$ lần xuất hiện của a trong chuỗi con.

Trường hợp thử nghiệm 1:

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

Trường hợp thử nghiệm 2:

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

Giải pháp của tôi:

        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'));
        }

Kết quả phải là 7 và 1000000000000. Giải pháp này đã vượt qua tất cả các trường hợp thử nghiệm trên HackerRank. Nó dựa trên các giải pháp khác, đặc biệt là giải pháp mà tôi đã bình chọn.

Answer 1

1. Bạn có cần xác nhận đầu vào không?

Nếu vậy, bạn nên kiểm tra tất cả các trường hợp:

• đầu vào có thể là rỗng
• đầu vào có thể là một chuỗi trống
• n có thể là số âm hoặc 0

1. Tên biến

Tên biến rất quan trọng, chúng giúp hiểu mã tốt hơn. Bạn không cần phải làm cho chúng càng nhỏ càng tốt. Đặc biệt khi bạn có IDE như VisualStudio sẽ giúp bạn chọn IDE thích hợp với InteliSense.

• numAs -> aCount
• rem -> phần còn lại
• đại diện -> số lần lặp lại
• sRem -> remainderString

1. Thất bại nhanh chóng

Thông thường tốt hơn là để lại một phương pháp "càng sớm càng tốt". Vì vậy, bạn muốn thực hiện xác thực đầu vào trước khi thực hiện bất kỳ công việc nào và thoát khỏi phương thức nếu nó không xác thực. Tương tự, nếu phần dư của bạn là 0, bạn có thể trả về kết quả ngay lập tức.

1. Phép chia số nguyên

Để tính toán số lần lặp lại, bạn lấy n trừ phần còn lại. Nếu bạn kiểm tra phép chia số nguyên trong C # , bạn không cần phải:

long repetitions = n / input.length;

1. Sử dụng Linq

Theo giải pháp tinstaafl , bạn có thể sử dụng Linq để lưu một biến và một dòng:

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

Vì vậy, tất cả, bạn nhận được:

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'));

Answer 2

Tôi không thấy có nhiều thứ để cải thiện. Tuy nhiên, tôi đã nhận thấy một số điều:

Phím tắt có điều kiện:

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

sẽ là điều đầu tiên trong mã của bạn ngay sau input

Tương tự với:

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

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

Bạn không cần chuỗi đó trừ khi rem> 0, vì vậy hãy đưa nó vào khối điều kiện. Tốt hơn nữa, hãy sử dụng tiện ích mở rộng LINQ Takevà thực hiện mọi thứ trong một câu lệnh:

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

Answer 3

Điểm giống với các câu trả lời khác, tuy nhiên có một giải pháp đơn giản hơn cho điều này, bạn có thể chỉ cần thay thế Abằng chuỗi rỗng và so sánh độ dài của cả hai chuỗi, điều này sẽ cho bạn số A.

Đây là một ví dụ :

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

Answer 4

Tôi không thể thêm nhiều vào những gì đã được viết, ngoài việc nói đến hiệu suất, bạn thường thấy Linq ( long numAs = input.Count(c => c.Equals('a'));) khá chậm so với một vòng lặp forhoặc truyền thống hơn while. Nhưng nếu bạn nhấn mạnh vào Linq, bạn có thể làm như sau:

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

Ở đây được sử dụng quá tải Select()cung cấp chỉ mục cùng với mỗi phần tử để ánh xạ tới một bộ giá trị, từ đó có thể lọc theo 'a'và cuối cùng tổng hợp các lần lặp lại: nếu chỉ mục nhỏ hơn kích thước của lời nhắc thì repetitions + 1nên nếu không thì tổng kết lại chỉ các lần lặp lại cho mỗi lần tìm được 'a'.

---

Một cách tiếp cận truyền thống sử dụng while-loops - về cơ bản sử dụng cùng một cách tiếp cận như trên có thể trông giống như:

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

Với cách tiếp cận này, chuỗi s( data) chỉ được phân tích cú pháp một lần.