狗家油管上门面经

请问楼主，第三题找共同祖先的题，一个人有两个parent，两个parent可以有多个children吧？

楼主请问第四题用KMP应该咋做呢？

第三题应该是union find，union find 找祖先的时间复杂是O（1）

第四题
印度小哥那题感觉不难吧，时间O（N)能解决
要做的就是建立原字母和后来字母的位置映射
比如
单词：ABC -> CBA
位置：123 -> 321
单词：ABCDEF -> DAEFBC
位置：123456 -> 415623

建立完映射之后，只要找映射之后的数组内有几个递增数组就可以了
比如321 内 三个递增数组  分别是 3 2 1
比如415623内有 三个递增数组 分别是  4 15 623

hlckl123456 发表于 2018-9-8 13:54
第三题应该是union find，union find 找祖先的时间复杂是O（1）

第四题

union find为什么是O(1)呢？我感觉至少得把所有元素都过一遍吧？

sxhexe 发表于 2018-9-16 06:56
union find为什么是O(1)呢？我感觉至少得把所有元素都过一遍吧？

不用啊，你那样就重复查询了。
因为有self.find 里面那一步 for n in path:
时间复杂度 average 是 1
def connect(self, a, b):
        self.father[self.find(a)] = self.find(b)

    """
    @param: a: An integer
    @param: b: An integer
    @return: A boolean
    """
    def query(self, a, b):
        return self.find(a) == self.find(b)
   
    def find(self, node):
        path = []
        while self.father[node] != node:
            path.append(node)
            node = self.father[node]
            
        for n in path:
            self.father[n] = node
            
        return node

sxhexe 发表于 2018-9-16 06:56
union find为什么是O(1)呢？我感觉至少得把所有元素都过一遍吧？

union find所以子，都是和父距离1的
你和trie搞混了吧？

mark 油管面经

已经连续答对5天的题，签到5天了，还是差点儿分。。。