C #: สตริงซ้ำ

Aug 20 2020

จากการท้าทาย HackerRank "สตริงซ้ำ":

Lilah มีสายอักขระ\$s\$ของตัวอักษรภาษาอังกฤษตัวพิมพ์เล็กที่เธอพูดซ้ำหลายครั้ง

รับจำนวนเต็ม\$n\$ค้นหาและพิมพ์จำนวนตัวอักษร a ในตัวแรก\$n\$ ตัวอักษรของสายอักขระที่ไม่มีที่สิ้นสุดของ Lilah

ตัวอย่างเช่นถ้าสตริง\$s=abcac\$และ\$n=10\$สตริงย่อยที่เราพิจารณาคือ\$abcacabcac\$ครั้งแรก\$10\$อักขระของสตริงที่ไม่มีที่สิ้นสุดของเธอ มี\$4\$ การเกิดขึ้นของ a ในสตริงย่อย

กรณีทดสอบ 1:

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

กรณีทดสอบ 2:

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

ทางออกของฉัน:

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

ผลลัพธ์ควรเป็น 7 และ 1000000000000 โซลูชันนี้ผ่านกรณีทดสอบทั้งหมดบน HackerRank มันขึ้นอยู่กับวิธีแก้ปัญหาอื่น ๆ โดยเฉพาะอย่างยิ่งหนึ่งที่ฉันโหวต

คำตอบ

4 MartinVerjans Aug 20 2020 at 21:46
  1. คุณต้องการตรวจสอบอินพุตหรือไม่?

ในกรณีนี้คุณควรทดสอบทุกกรณี:

  • อินพุตอาจเป็นโมฆะ
  • อินพุตอาจเป็นสตริงว่าง
  • n อาจเป็นลบหรือ 0
  1. ชื่อตัวแปร

ชื่อตัวแปรมีความสำคัญช่วยให้เข้าใจโค้ดได้ดีขึ้น คุณไม่จำเป็นต้องทำให้เล็กที่สุด โดยเฉพาะอย่างยิ่งเมื่อคุณมี IDE เช่น VisualStudio ที่จะช่วยคุณเลือก IDE ที่เหมาะสมกับ InteliSense

  • numAs -> aCount
  • rem -> ส่วนที่เหลือ
  • reps -> การทำซ้ำ
  • sRem -> ส่วนที่เหลือ
  1. ล้มเหลวอย่างรวดเร็ว

มักจะดีกว่าที่จะออกจากวิธีการ "โดยเร็วที่สุด" ดังนั้นคุณต้องทำการตรวจสอบอินพุตก่อนที่จะดำเนินการใด ๆ และออกจากเมธอดหากไม่ได้ตรวจสอบ ในทำนองเดียวกันถ้าส่วนที่เหลือของคุณเป็น 0 คุณสามารถส่งคืนผลลัพธ์ได้ทันที

  1. การหารจำนวนเต็ม

ในการคำนวณการทำซ้ำให้ลบส่วนที่เหลือออกจาก n หากคุณตรวจสอบการหารจำนวนเต็มใน C #คุณไม่จำเป็นต้อง:

long repetitions = n / input.length;
  1. ใช้ Linq

ตามโซลูชัน tinstaaflคุณสามารถใช้ Linq เพื่อบันทึกตัวแปรและบรรทัด:

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

สรุปแล้วคุณจะได้รับ:

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

ไม่เห็นต้องปรับปรุงอะไรมากมาย อย่างไรก็ตามฉันสังเกตเห็นบางสิ่ง:

เงื่อนไขทางลัด:

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

ควรเป็นสิ่งแรกในโค้ดของคุณทันที input

ในทำนองเดียวกันกับ:

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

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

คุณไม่จำเป็นต้องใช้สตริงนั้นเว้นแต่จะrem> 0 ดังนั้นให้รวมไว้ในบล็อกเงื่อนไข ยิ่งไปกว่านั้นให้ใช้ส่วนขยาย LINQ Takeและทำทุกอย่างในคำสั่งเดียว:

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

จุดเดียวกับคำตอบอื่น ๆ อย่างไรก็ตามมีวิธีแก้ปัญหาที่ง่ายกว่าคุณสามารถแทนที่Aด้วยสตริงว่างและเปรียบเทียบความยาวของสตริงทั้งสองซึ่งจะให้จำนวน A

นี่คือตัวอย่าง:

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

ฉันไม่สามารถเพิ่มสิ่งที่เขียนไปแล้วได้มากนักนอกจากเรื่องประสิทธิภาพแล้วคุณมักจะพบว่า Linq ( long numAs = input.Count(c => c.Equals('a'));) ค่อนข้างช้าเมื่อเทียบกับแบบดั้งเดิมforหรือwhileวนซ้ำมากกว่า แต่ถ้าคุณยืนยัน Linq คุณสามารถทำสิ่งต่อไปนี้:

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

นี่คือการใช้โอเวอร์โหลดSelect()ที่ให้ดัชนีพร้อมกับแต่ละองค์ประกอบเพื่อแมปกับทูเพิลค่าซึ่งเป็นไปได้ที่จะกรอง'a'และสรุปการทำซ้ำในที่สุด: หากดัชนีน้อยกว่าขนาดของการเตือนความจำrepetitions + 1ควรเป็น 'a'สรุปเป็นอย่างอื่นเท่านั้นซ้ำสำหรับแต่ละพบ


วิธีการแบบดั้งเดิมโดยใช้while-loops - โดยพื้นฐานแล้วการใช้แนวทางเดียวกันกับข้างต้นอาจมีลักษณะดังนี้:

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

ด้วยวิธีนี้สตริงs( data) จะถูกแยกวิเคราะห์เพียงครั้งเดียว