Definition: A sublist of linked list s is a linked list of some of the elements of s in order. For example, <3 6 2 5 1 7> has sublists <3 2 1> and <6 2 7> but not <5 6 7>.
Definition: A linear sublist of a linked list of numbers s is a sublist in which the difference between adjacent numbers is always the same. For example <2 4 6 8> is a linear sublist of <1 2 3 4 6 9 1 8 5> because the difference between each pair of adjacent elements is 2.
Implement linear which takes a linked list of numbers s (either a Link instance or Link.empty). It returns the longest linear sublist of s. If two linear sublists are tied for the longest, return either one.
class Link:
"""A linked list is either a Link object or Link.empty
>>> s = Link(3, Link(4, Link(5)))
>>> s.rest
Link(4, Link(5))
>>> s.rest.rest.rest is Link.empty
True
>>> s.rest.first * 2
8
>>> print(s)
<3 4 5>
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest:
rest_repr = ', ' + repr(self.rest)
else:
rest_repr = ''
return 'Link(' + repr(self.first) + rest_repr + ')'
def __str__(self):
string = '<'
while self.rest is not Link.empty:
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + '>'
def linear(s):
#Fing longest with d from first
def complete(first, rest):
if rest is Link.empty:
return Link(first)
elif rest.first - first == d:
return Link(first, complete(rest.first, rest.rest))
else:
return complete(first, rest.rest)
if s is Link.empty:
return s
longest = Link(s.first)
while s is not Link.empty:
t = s.rest
while t is not Link.empty:
d = t.first - s.first
candidate = Link(s.first, complete(t.first, t.rest))
if length(candidate) > length(longest):
longest = candidate
t = t.rest
s = s.rest
return longest
def length(s):
if s is Link.empty:
return 0
return 1 + length(s.rest)
标签：Q2,return,self,Discussion12,rest,CS61A,Link,empty,first From： https://www.cnblogs.com/s1mple/p/18617218