Hackerrank Dicts 解题记录

Hash Tables: Ransom Note

一道简易的题目，由于碰到了我经常用到的库 Counter，所以在此还是记录一下


from collections import Counter

def checkMagazine(magazine, note):
    magazineList =  Counter(magazine)
    magazineDict = {v:magazineList[v] for v in magazineList}
    noteList = Counter(note)
    noteDict = {v:noteList[v] for v in noteList}
    for v in noteDict:
        if v not in magazineDict or magazineDict[v] < noteDict[v]:
            print("No")
            return
    print("Yes")
    return

对比一下其他人使用相同的库的代码，感觉别人写的实在是太骚了呀，深深感觉到自己的掌握还远远不够
`python def checkMagazine(magazine, note): if not (Counter(note) - Counter(magazine)): # or Counter(note) - Counter(magazine) == {} print("Yes") else: print("No")`

Sherlock and Anagrams

一道中等难度的题目,最初采用将字符串都拆解成他们的不同字串的方法，结果超时了，想想也是，如果是100个字母长度的字符串，那么结果就是2¹⁰⁰,不超时才怪。

from collections import Counter

def checkAnag(a,b):
    if Counter(a) == Counter(b):
        return True
    
def sherlockAndAnagrams(s):
    count = 0
    s1 = "".join(reversed(s))
    sub1 =[s1[i:i+x+1] for i in range(len(s1)) for x in range(len(s1)-i)]
    if s1 in sub1:
        sub1.remove(s1)
    for i in range(len(sub1)):
        for j in range(i+1,len(sub1)):
            if checkAnag(sub1[i],sub1[j]):
                count += 1
    return count

与其对其中的每一个字母进行计数，还不如将所有的字母都按顺序排列一遍，然后再比较最后的两个序列是否相同，此思路的实现代码如下
`python def sherlockAndAnagrams(s): count=0 dict={} n=len(s) for i in range(n): for j in range(n-i): sub=''.join(sorted(s[j:j+i+1])) try: dict[sub]+=1 except: dict[sub]=1 for i in dict: count+=dict[i]*(dict[i]-1)//2 return count`

Count Triplets

对三个数进行r倍组合，1为特殊情况，我直接用了组合计算，不过代码出现了超时，再研究研究哪里出了问题

from collections import Counter
from itertools import combinations
# Complete the countTriplets function below.
def combinationResult(num):
    i = 0
    for combination in combinations(range(num),3):
        i += 1
    return i 
def countTriplets(arr, r):
    sum = 0
    square = r**2
    countNum = Counter(arr)
    if r == 1:
        for v in countNum:
            if(countNum[v]>2):
                sum += combinationResult(countNum[v])
        return sum
    sortSet = list(sorted(set(arr)))
    firstLimit = sortSet[len(sortSet)-1]/square
    for x in sortSet:
        if x > firstLimit:
            break
        if x*r in sortSet and x*square in sortSet:
            sum += countNum[x]*countNum[x*r]*countNum[x*square]
    
    return sum

关于组合数的计算，参见python计算组合数的两种实现方法
经过对两种方法(直接进行组合与笛卡尔乘积)的比对，得出直接利用combinations来计算更加迅速一些,以下为比较代码：

import math
import itertools
import time
from itertools import combinations

unique = [1, 2, 3, 4, 5, 56, 78, 23]
time1 = time.time()
for j in range(1000000):
    i = 0
    for combination in combinations(unique, 2):
        i += 1

time2 = time.time()

for j in range(1000000):
    d = 0
    uniques = [unique, unique]
    for combination in itertools.product(*uniques):
        d += 1
time3 = time.time()
print("time 2-1 = "+str(time2-time1), "time 3-1 = "+str(time3-time2))
#time 2-1 = 3.7130393981933594 time 3-1 = 7.952743053436279

为了将这道题解决，我看了一下出题者的解释，在出题者的hint中提到本题是能够达到O(n)的复杂度的，反观一下自己，虽然自己并没有写什么循环，不过的话在循环里的if语句中用到了两个in，基本算是O(n³)的复杂度了。
按照作者的意思，作者进行个对arr的遍历，建立两个字典，假设三元组为(A，B，C)，两个字典分别是指对于B来说A已经存在了，以及对于C来说（A，B）的组合已经准备好了。
每个字典里面放的并不是实值，而是对于未来三元组的一个可能性的预测，在遍历每个A的同时让B与C的线性空间不断减小，是一个非常有意思的解决思路。以下是它的python代码。

def countTriplets(arr, r):
    r2 = Counter()
    r3 = Counter()
    count = 0
    
    for v in arr:
        if v in r3:
            count += r3[v]
        
        if v in r2:
            r3[v*r] += r2[v]
        
        r2[v*r] += 1

    return count

Yanjian Zhang's blog