请问在leetcode上如何重载某个类的比较函数？

比如merge k sorted lists这道题，用priority queue(heap)的解法， 因为比较的是两个listnode类的val, 需要重载listnode的__lt__函数， 我看leetcode上别人是重新定义一个更大的类（比如下面的这个priorityqueuenode)， 然后用listnode初始化这个类， 想问下有没有方法可以在leetcode的格式下直接重载listnode的__lt__, 这样避免了重新定义一个新类。。。谢谢！

https://leetcode.com/problems/merge-k-sorted-lists/

别人的重载方法：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class priorityQueueNode:  #define a new class
    def __init__(self,key,val):
        self.key = key
        self.val = val
    def __lt__(self,other):  #reload the new class __lt__
        return self.key < other.key

class Solution:
    # merge every two lists

    # priority queue
# time Onlog(len(lists))
# space Olen(lists) + n
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:

        dummy = ListNode(0)
        node = dummy
        n = len(lists)
        minHeap = []
        for l in lists:
            if l:
                heapq.heappush(minHeap,priorityQueueNode(l.val,l))
        #print(minHeap)
        while minHeap:
            top = heapq.heappop(minHeap).val
            node.next = top
            node = node.next
            if top.next:
                heapq.heappush(minHeap,priorityQueueNode(top.next.val,top.next))
        return dummy.next

这应该是重写不是重载。应该可以创建一个子类继承之后重写吧。 你创建一个子类，继承listnode， 然后再重写这个子类的__lt__. 构造函数直接继承。。或者是用lambda？ 但是我忘记heappop和heappush能不能用lambda了。。

ps: 重写关系从oop的角度来讲， 父类的方法只能被子类重写。。。不创建子类重写父类的方法在oop语言里面，应该是不存在的（correct me if im wrong), 因为这本身违背了oop的原则

1. class priorityQueueNode(ListNode):  #define a new class
   
2.     def __lt__(self,other):  #reload the new class __lt__
   
3.         return self.key < other.key

复制代码

在两周以前我都是自己重写一个类做wrap，但是最近被朋友提醒用tuple一包就行了不需要写别的类，你只需要heappush(h,(node.val,node)) 这样就会按val排序了，而且我一般还会加一个记数i进tuple，因为tuple是按顺序来比较的，为了防止node的lt gt没有实现（我不知道有没有），放一个计数变成（node.val,i,node）这样就算val相同，比较到i肯定也会不同，就不会比较node了

这里写两种方法，都是LeetCode上可以提交通过的

第一种方法就是你想要的“重写”（overwrite）ListNode 原有的 __lt__，就在class Solution前面加一行代码就可以：

1. 
   
2. # 将ListNode的__lt__函数替换为自定义的一个lambda function
   
3. ListNode.__lt__ = lambda self, other: self.val < other.val
   
4. 
   
5. class Solution:
   
6.     # merge every two lists
   
7. 
   
8.     # priority queue
   
9.     # time Onlog(len(lists))
   
10.     # space Olen(lists) + n
    
11.     def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    
12.         dummy = ListNode(0)
    
13.         node = dummy
    
14.         n = len(lists)
    
15.         minHeap = []
    
16.         for l in lists:
    
17.             if l:
    
18.                 heapq.heappush(minHeap, l)
    
19.         while minHeap:
    
20.             top = heapq.heappop(minHeap)
    
21.             node.next = top
    
22.             node = node.next
    
23.             if top.next:
    
24.                 heapq.heappush(minHeap, top.next)
    
25.         return dummy.next
    

复制代码

这个方法体现了Python的动态语言特性，也就是一个class的可执行代码本身也是一个object，是在运行时可以修改的数据（first-class citizen）。这是很灵活但也是危险的特性（class的行为可以在其定义区域之外做任意改动），实际工程项目里面应该是会禁止或者非常小心做这样的事情的。


第二种是自定义一个通用的PriorityQueue，使用lambda function注入compare函数。稍微要多写一点代码，但都是封装在PriorityQueue内部所以代码结构反而会更清晰。这个如果在面试的时候写出来应该是比较加分的，因为展示了抽象能力：

1. class PriorityQueueBucket:
   
2.     def __init__(self, key, value):
   
3.         self.key = key
   
4.         self.value = value
   
5.    
   
6.     def __lt__(self, other):
   
7.         return self.key < other.key
   
8. 
   
9. # 支持自定义comparator的PriorityQueue
   
10. class PriorityQueue:
    
11.     import heapq
    
12.     import functools
    
13.    
    
14.     def __init__(self, cmp = lambda x, y: x > y):
    
15.         self.container = []
    
16.         self.getKey = functools.cmp_to_key(
    
17.             lambda x, y: -1 if cmp(x, y) else 1 if cmp(y, x) else 0)
    
18. 
    
19.     def __len__(self):
    
20.         return len(self.container)
    
21. 
    
22.     def push(self, item):
    
23.         heapq.heappush(self.container, PriorityQueueBucket(self.getKey(item), item))
    
24. 
    
25.     def pop(self):
    
26.         return heapq.heappop(self.container).value
    
27. 
    
28. 
    
29. class Solution:
    
30.     # merge every two lists
    
31. 
    
32.     # priority queue
    
33.     # time Onlog(len(lists))
    
34.     # space Olen(lists) + n
    
35.     def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    
36.         dummy = ListNode(0)
    
37.         node = dummy
    
38.         n = len(lists)
    
39.         minHeap = PriorityQueue(lambda x, y: x.val < y.val)
    
40.         for l in lists:
    
41.             if l:
    
42.                 minHeap.push(l)
    
43.         while minHeap:
    
44.             top = minHeap.pop()
    
45.             node.next = top
    
46.             node = node.next
    
47.             if top.next:
    
48.                 minHeap.push(top.next)
    
49.         return dummy.next
    

复制代码

hjy 发表于 2020-8-14 06:40
这应该是重写不是重载。应该可以创建一个子类继承之后重写吧。 你创建一个子类，继承listnode， 然后再重写 ...

谢谢， 终于能区分重写和重载了。 ：）

Mr.p 发表于 2020-8-14 10:52
在两周以前我都是自己重写一个类做wrap，但是最近被朋友提醒用tuple一包就行了不需要写别的类，你只需要hea ...

这个方法很简洁， one more question, 如果需要比较两个不同类型的值， 比如top k frequent words 这道题， 需要先按照每个词出现的频率排序， 如果两个词出现频率一样就按那个哪个词有“lower alphabetical order”排序。还能用这个tuple 方法吗？ 我试了一下以下的代码， 似乎对有的测试例比如input=["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"] 排序就不对了，不知道大神们有啥idea?谢谢！
ttps://leetcode.com/problems/top-k-frequent-words/，
class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        d=collections.Counter(words)
        h=[]
        res=[]
        for key, val in d.items():
            heappush(h, (val, key))
            if len(h)>k:
                heappop(h)
        
        while h:
            tmp=h.pop()
            res.append(tmp[1])
        return reversed(res)
        

magicsets 发表于 2020-8-15 15:07
这里写两种方法，都是LeetCode上可以提交通过的

第一种方法就是你想要的“重写”（overwrite）ListNode  ...

谢谢， 第2种方法太牛了！

fasionfans 发表于 2020-8-30 00:38
这个方法很简洁， one more question, 如果需要比较两个不同类型的值， 比如top k frequent words 这道题 ...

如果我没理解错哈，你要先按频率排序，再按字母序那就压入一个这样的tuple (频数，原字符串，其他信息) heap在比较大小的时候会按tuple内的各个元素的先后顺序拿来作比较，若第一个元素相同，则比较第二个。
这样你把频数和字符串本身都放进去应该就可以了，这也是为什么我前面的例子里要加一个计数i进tuple，为了防止val相同的时候去比较node，然而node的lt和gt又没有正确的实现这样的情况。

嗯嗯， 你的理解是对的， 我就是这么压入tuple的， 那个key就是原字符串， 然而过不了测视例。 :D