Last active
August 16, 2017 17:31
-
-
Save YabZhang/3db8d341426569255fd979c079e9e041 to your computer and use it in GitHub Desktop.
quiz
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/env python3 | |
| # Problem No.1 | |
| def get_pairs_helper(alist, total): | |
| """获取列表中和为total的一组元素""" | |
| if not (alist and isinstance(alist, (list, tuple))): | |
| return | |
| alist.sort() | |
| prev, next_ = 0, len(alist) - 1 | |
| result = [] | |
| while next_ > prev: | |
| if alist[prev] + alist[next_] < total: | |
| prev += 1 | |
| elif alist[prev] + alist[next_] > total: | |
| next_ -= 1 | |
| else: | |
| result.append((alist[prev], alist[next_])) | |
| prev += 1 | |
| next_ -= 1 | |
| return result | |
| def resolve_1(alist, total=16): | |
| pairs = get_paair_helper(alist, total) | |
| if not pairs: | |
| return alist | |
| else: | |
| for item in pairs: | |
| alist.remove(item[0]) | |
| alist.remove(item[1]) | |
| return alist | |
| # Problem 2 | |
| class Node: | |
| """单链表节点""" | |
| def __init__(self, val, next_=None): | |
| self._data = val | |
| self._next = next_ | |
| def get_val(self): | |
| return self._data | |
| def set_val(self, val): | |
| self._data = val | |
| def get_next(self): | |
| return self._next | |
| def set_next(self, node): | |
| self._next = node | |
| class SingleLinkedList: | |
| """单链表类""" | |
| def __init__(self): | |
| self._head = None | |
| def size(self): | |
| count = 0 | |
| if not self._head: | |
| return count | |
| n = self._head | |
| while True: | |
| if n: | |
| count += 1 | |
| else: | |
| break | |
| n = n.get_next() | |
| return count | |
| def __len__(self): | |
| return self.size() | |
| def is_empty(self): | |
| return self._head is None | |
| def set_head(self, node): | |
| self._head = node | |
| def get_head(self): | |
| return self._head | |
| def is_head(self, node): | |
| return self._head is node | |
| def resolve_2(alist): | |
| """把一个列表转换为一个链表""" | |
| sll = SingleLinkedList() | |
| if not alist: | |
| return sll | |
| for item in alist or []: | |
| prev = sll.get_head() | |
| new_node = Node(item, prev) | |
| sll.set_head(now_node) | |
| return sll | |
| # Problem 3 | |
| def seq_gen_helper(alist, blist, reverse): | |
| # make duplicate list | |
| alist = sorted(alist, reverse=reverse) | |
| blist = sorted(blist, reverse=reverse) | |
| # custom cmp operation | |
| op = { | |
| False: lambda m, n: m <= n, | |
| True: lambda m, n: m >= n | |
| } | |
| # gen sorted seq | |
| a_p, b_p = 0, 0 | |
| prev, cur = None, None | |
| while a_p < len(alist) or b_p < len(blist): | |
| if alist[a_p] and op[reverse](alist[a_p], alist[b_p]): | |
| cur = alist[a_p] | |
| a_p += 1 | |
| else: | |
| cur = blist[b_p] | |
| b_p += 1 | |
| # check and filter out duplicate item | |
| if cur is not None and prev is not None: | |
| if cur == prev: | |
| continue | |
| else: | |
| prev = cur | |
| yield cur | |
| def resolve_3(alist, blist, reverse=False): | |
| """利用两个列表创建一个有序无重复的链表""" | |
| # create merged single linked list | |
| new_sll = SingleLinkedList() | |
| for val in seq_gen_helper(alist, blist, reverse=not reverse): | |
| prev = new_sll.get_head() | |
| node = Node(val, prev) | |
| new_sll.set_head(node) | |
| return new_sll |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment