สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums ซึ่งมีค่าไม่เป็นลบ เราต้องหาคู่ของดัชนีจำนวนหนึ่งที่มีอยู่ในอาร์เรย์ ถ้าคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนคำตอบ mod 10^9+7 ในที่นี้ ดัชนีคู่หนึ่ง (i, j) ถือว่าดีเมื่อตรงตามเงื่อนไขเหล่านี้ทั้งหมด:1. 0 <=i
หมายเหตุ − ที่นี่ rev() จะกลับเฉพาะส่วนบวกของจำนวนเต็ม ดังนั้นหาก rev(564) อยู่ที่นั่น มันหมายถึง 465 แต่ถ้า rev(540) อยู่ ค่านั้นจะส่งกลับ 45
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[97,2,42,11] ผลลัพธ์จะเป็น 2 เพราะมีสองคู่ (0,2) และ (1,3) สำหรับคู่แรก [97 + rev (42) =97+24 =121 และ 42 + รอบ (97) =42 + 79 =121] และสำหรับอันที่สอง [2 + รอบ(11) =2 + 11 =13 และ 11 + รอบ (2) =13].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ม :=(10^9) +7
-
dic :=แผนที่ว่างซึ่งมีค่าเริ่มต้นเป็น 0
-
สำหรับแต่ละ num เป็น num ทำ
-
rev :=ย้อนกลับของ num
-
เพิ่ม dic[num - rev] ขึ้น 1
-
-
res:=0
-
สำหรับแต่ละ val ในรายการค่าทั้งหมดของ dic ทำ
-
res :=res + ผลหารของ (val*(val-1))/2
-
-
คืนค่า res mod m
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
from collections import defaultdict def solve(nums): m = (10**9)+7 dic = defaultdict(int) for num in nums: rev=int(str(num)[::-1]) dic[num-rev]+=1 res=0 for val in dic.values(): res += (val*(val-1)) // 2 return res % m nums = [97,2,42,11] print(solve(nums))
อินพุต
[97,2,42,11]
ผลลัพธ์
2