Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
构造一个针对单 1 #382
 2 #Runtime: 167 ms (Beats 33.87%)
 3 #Memory: 17.9 MB (Beats 11.29%)
 4 
 5 # Definition for singly-linked list.
 6 # class ListNode(object):
 7 #     def __init__(self, val=0, next=None):
 8 #         self.val = val
 9 #         self.next = next
10 class Solution(object):
11 
12     def __init__(self, head):
13         """
14         :type head: Optional[ListNode]
15         """
16         self.head = head
17         
18 
19     def getRandom(self):
20         """
21         :rtype: int
22         """
23         ans = self.head
24         p = self.head
25         cnt = 0
26         while p:
27             cnt += 1
28             if random.randint(1, cnt) == 1:
29                 ans = p.val
30             p = p.next
31         return ans
32 
33 # Your Solution object will be instantiated and called as such:
34 # obj = Solution(head)
35 # param_1 = obj.getRandom()链表的函数,使之每次调用可以随机输出其中一个值
参考了discussion的Reservoir sampling思路->https://leetcode.com/problems/linked-list-random-node/solutions/3278159/easy-solutions-in-java-python-and-c-look-at-once/



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理