โจทย์
หมุนลิสต์ไปทางขวาตามจำนวน steps ตำแหน่ง: โดยนำสมาชิกตัวสุดท้ายมาไว้ข้างหน้า ทำซ้ำทั้งหมด steps ครั้ง
ให้เขียนฟังก์ชัน rotate_right(numbers, steps)
อินพุต
numbers: ลิสต์ของจำนวนเต็ม steps: จำนวนตำแหน่งที่ต้องหมุน
เอาต์พุต
คืนค่าลิสต์ที่ถูกหมุนแล้ว
เงื่อนไข
0 ≤ ความยาว ≤ 100,000; 0 ≤ steps ≤ 10⁹
ตัวอย่าง
อินพุต:
numbers = [1, 2, 3, 4, 5]
steps = 2
ผลลัพธ์ที่คาดหวัง:
expected = [4, 5, 1, 2, 3]
อินพุต:
std::vector<long long> numbers = {1, 2, 3, 4, 5};
long long steps = 2;
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {4, 5, 1, 2, 3};
อินพุต:
long[] numbers = new long[] {1, 2, 3, 4, 5};
long steps = 2;
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {4, 5, 1, 2, 3};
คำอธิบาย
หมุนขวา 2 ครั้ง: [5, 1, 2, 3, 4], จากนั้น [4, 5, 1, 2, 3]
อินพุต:
numbers = [1, 2, 3]
steps = 3
ผลลัพธ์ที่คาดหวัง:
expected = [1, 2, 3]
อินพุต:
std::vector<long long> numbers = {1, 2, 3};
long long steps = 3;
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {1, 2, 3};
อินพุต:
long[] numbers = new long[] {1, 2, 3};
long steps = 3;
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {1, 2, 3};
คำอธิบาย
หมุนจำนวนเท่ากับความยาวลิสต์จะได้ลิสต์เดิม: [1, 2, 3]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
การหมุนเท่ากับความยาวรายการจะไม่เปลี่ยนอะไร ดังนั้นสนใจแค่เศษ
คำใบ้ 2
คิดเหมือนแยกรายการใกล้ท้ายแล้วเอาส่วนท้ายไปไว้ด้านหน้า
คำใบ้ 3
จัดการ step ที่ใหญ่มากด้วยการลดก่อนนำไปจัดเรียง
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน