C #: สตริงซ้ำ
จากการท้าทาย 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 มันขึ้นอยู่กับวิธีแก้ปัญหาอื่น ๆ โดยเฉพาะอย่างยิ่งหนึ่งที่ฉันโหวต
คำตอบ
- คุณต้องการตรวจสอบอินพุตหรือไม่?
ในกรณีนี้คุณควรทดสอบทุกกรณี:
- อินพุตอาจเป็นโมฆะ
- อินพุตอาจเป็นสตริงว่าง
- n อาจเป็นลบหรือ 0
- ชื่อตัวแปร
ชื่อตัวแปรมีความสำคัญช่วยให้เข้าใจโค้ดได้ดีขึ้น คุณไม่จำเป็นต้องทำให้เล็กที่สุด โดยเฉพาะอย่างยิ่งเมื่อคุณมี IDE เช่น VisualStudio ที่จะช่วยคุณเลือก IDE ที่เหมาะสมกับ InteliSense
- numAs -> aCount
- rem -> ส่วนที่เหลือ
- reps -> การทำซ้ำ
- sRem -> ส่วนที่เหลือ
- ล้มเหลวอย่างรวดเร็ว
มักจะดีกว่าที่จะออกจากวิธีการ "โดยเร็วที่สุด" ดังนั้นคุณต้องทำการตรวจสอบอินพุตก่อนที่จะดำเนินการใด ๆ และออกจากเมธอดหากไม่ได้ตรวจสอบ ในทำนองเดียวกันถ้าส่วนที่เหลือของคุณเป็น 0 คุณสามารถส่งคืนผลลัพธ์ได้ทันที
- การหารจำนวนเต็ม
ในการคำนวณการทำซ้ำให้ลบส่วนที่เหลือออกจาก n หากคุณตรวจสอบการหารจำนวนเต็มใน C #คุณไม่จำเป็นต้อง:
long repetitions = n / input.length;
- ใช้ 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'));
ไม่เห็นต้องปรับปรุงอะไรมากมาย อย่างไรก็ตามฉันสังเกตเห็นบางสิ่ง:
เงื่อนไขทางลัด:
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'));
}
จุดเดียวกับคำตอบอื่น ๆ อย่างไรก็ตามมีวิธีแก้ปัญหาที่ง่ายกว่าคุณสามารถแทนที่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;
}
ฉันไม่สามารถเพิ่มสิ่งที่เขียนไปแล้วได้มากนักนอกจากเรื่องประสิทธิภาพแล้วคุณมักจะพบว่า 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
) จะถูกแยกวิเคราะห์เพียงครั้งเดียว