Q: http://poj.org/problem?id=1635
給定2個tree, 判斷這兩個tree是否為isomorphism
也就是說是否為同樣的架構(不用看值,直接看"架構"就好)
解題的方法很特殊,是用hash的方式去計算單一一個tree的id
如果算出來的id相同,則代表2棵樹的架構一樣,是為isomorphism
先根據input利用vector來建立tree
之後利用遞迴的方法計算root的hash值
如果遇到葉節點就直接回傳一個自己設好的質數(這裡設成191)
hash function為HASH(node) = (HASH(child)^2的總和) mod 34943
可能是因為我沒有建表把每個node的hash值記錄下來吧
速度有點慢,不過還是過了=w=
一開始跑起來結果還怪怪的
之後才發現原來我沒有吸收換行
導致input錯誤,連帶造成答案怪怪的
要細心一點啊@@
文章標籤
全站熱搜
留言列表
生活點滴 (3)
