[CS61A] Lab 04 List

Lab 04 对list的学习，详细内容请看链接 http://gaotx.com/cs61a/lab/lab04/
我的解答 http://gaotx.com/blogs/2015/05/14/cs61a-lab04/

# Q4
def get_seven_a(x):
    """
    >>> x = [1, 3, [5, 7], 9]
    >>> get_seven_a(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[2][1]

def get_seven_b(x):
    """
    >>> x = [[7]]
    >>> get_seven_b(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[0][0]

def get_seven_c(x):
    """
    >>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
    >>> get_seven_c(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[1][1][1][1][1][1][0]

# Q5
def reverse_recursive(lst):
    """Returns the reverse of the given list.

    >>> reverse_recursive([1, 2, 3, 4])
    [4, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"
    if not lst:
        return []
    return reverse_recursive(lst[1:])+[lst[0]]

# Q6
def merge(lst1, lst2):
    """Merges two sorted lists recursively.

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    "*** YOUR CODE HERE ***"
    if not lst1:
        return lst2
    if not lst2:
        return lst1
    if lst1[0]<lst2[0]:
        return [lst1[0]]+merge(lst1[1:],lst2)
    else:
        return [lst2[0]]+merge(lst1,lst2[1:])

# Q8
from math import sqrt

def is_square(n):
    return float(sqrt(n)) == int(sqrt(n))

def squares(seq):
    """Returns a new list containing elements of the original list that are
    perfect squares.

    >>> seq = [49, 8, 2, 1, 102]
    >>> squares(seq)
    [49, 1]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    "*** YOUR CODE HERE ***"
    return [n for n in seq if is_square(n)]

关于list的这个lab不算太难，不过感觉recursive和iterative理解不透彻，每次都得去复习一下它俩的区别
# Q4
def get_seven_a(x):
    """
    >>> x = [1, 3, [5, 7], 9]
    >>> get_seven_a(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[2][1]

def get_seven_b(x):
    """
    >>> x = [[7]]
    >>> get_seven_b(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[0][0]

def get_seven_c(x):
    """
    >>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
    >>> get_seven_c(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[1][1][1][1][1][1][0]

# Q5
def reverse_recursive(lst):
    """Returns the reverse of the given list.

    >>> reverse_recursive([1, 2, 3, 4])
    [4, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"
    if lst == []:
        return []
    return reverse_recursive(lst[1:]) + [lst[0]]

# Q6
def merge(lst1, lst2):
    """Merges two sorted lists recursively.

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    "*** YOUR CODE HERE ***"
    if lst1 == []:
        return lst2
    elif lst2 == []:
        return lst1
    else:
        if lst1[0] < lst2[0]:
            return [lst1[0]] + merge(lst1[1:], lst2)
        else:
            return [lst2[0]] + merge(lst1, lst2[1:])


# Q8
from math import sqrt

def is_square(n):
    return float(sqrt(n)) == int(sqrt(n))

def squares(seq):
    """Returns a new list containing elements of the original list that are
    perfect squares.

    >>> seq = [49, 8, 2, 1, 102]
    >>> squares(seq)
    [49, 1]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    "*** YOUR CODE HERE ***"
    return [i for i in seq if is_square(i)]

from lab04 import *

# Q9
def reverse_iter(lst):
    """Returns the reverse of the given list.

    >>> reverse_iter([1, 2, 3, 4])
    [4, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"
    length = len(lst)
    i = length - 1
    new_lst = []
    while i >= 0:
        new_lst += [lst[i]]
        i -= 1
    return new_lst

# Q10
def mergesort(seq):
    """Mergesort algorithm.

    >>> mergesort([4, 2, 5, 2, 1])
    [1, 2, 2, 4, 5]
    >>> mergesort([])     # sorting an empty list
    []
    >>> mergesort([1])   # sorting a one-element list
    [1]
    """
    "*** YOUR CODE HERE ***"
    if len(seq) == 0 or len(seq) == 1:
        return seq
    else:
        mid = len(seq) // 2
        return merge(mergesort(seq[:mid]), mergesort(seq[mid:]))

   

# Q11
def coords(fn, seq, lower, upper):
    """
    >>> seq = [-4, -2, 0, 1, 3]
    >>> fn = lambda x: x**2
    >>> coords(fn, seq, 1, 9)
    [[-2, 4], [1, 1], [3, 9]]
    """
    "*** YOUR CODE HERE ***"
    return [[ele, fn(ele)] for ele in seq if fn(ele) in range(lower, upper+1)]

# Q12
def deck(suits, numbers):
    """Creates a deck of cards (a list of 2-element lists) with the given
    suits and numbers. Each element in the returned list should be of the form
    [suit, number].

    >>> deck(['S', 'C'], [1, 2, 3])
    [['S', 1], ['S', 2], ['S', 3], ['C', 1], ['C', 2], ['C', 3]]
    >>> deck(['S', 'C'], [3, 2, 1])
    [['S', 3], ['S', 2], ['S', 1], ['C', 3], ['C', 2], ['C', 1]]
    >>> deck([], [3, 2, 1])
    []
    >>> deck(['S', 'C'], [])
    []
    """
    "*** YOUR CODE HERE ***"
    return [[suit, number] for suit in suits for number in numbers]

# Q13
def add_matrices(x, y):
    """
    >>> matrix1 = [[1, 3],
    ...            [2, 0]]
    >>> matrix2 = [[-3, 0],
    ...            [1, 2]]
    >>> add_matrices(matrix1, matrix2)
    [[-2, 3], [3, 2]]
    """
    "*** YOUR CODE HERE ***"
    return [[x[i][j] + y[i][j] for j in range(len(x[i]))] for i in range(len(x))]

关于list的lab，挺简单的，没碰到啥障碍。就是看了Q5的答案之后发现自己智商欠费。代码如下：
# Q4
def get_seven_a(x):
    """
    >>> x = [1, 3, [5, 7], 9]
    >>> get_seven_a(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return x[1][0]

def get_seven_b(x):
    """
    >>> x = [[7]]
    >>> get_seven_b(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return [0][0]

def get_seven_c(x):
    """
    >>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
    >>> get_seven_c(x)
    7
    """
    "*** YOUR CODE HERE ***"
    return [1][1][1][1][1][1][0]

# Q5
def reverse_recursive(lst):
    """Returns the reverse of the given list.

    >>> reverse_recursive([1, 2, 3, 4])
    [4, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"
    if len(lst) == 1:
        return [lst[0]]
    else:
        l = len(lst)
        return [lst[l-1]] + reverse_recursive(lst[:l-1])
        
# Q6
def merge(lst1, lst2):
    """Merges two sorted lists recursively.

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    "*** YOUR CODE HERE ***"
    lst = []
    for item in lst1:
        lst = lst + [item]
    for item in lst2:
        lst = lst + [item]
    lst.sort()
    print lst
   
# Q8
from math import sqrt

def is_square(n):
    return float(sqrt(n)) == int(sqrt(n))

def squares(seq):
    """Returns a new list containing elements of the original list that are
    perfect squares.

    >>> seq = [49, 8, 2, 1, 102]
    >>> squares(seq)
    [49, 1]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    "*** YOUR CODE HERE ***"
    return [item for item in seq if is_square(item)]

这次lab感觉难度不高阿。。

然后是代码：

1. # Q4
   
2. def get_seven_a(x):
   
3.     """
   
4.     >>> x = [1, 3, [5, 7], 9]
   
5.     >>> get_seven_a(x)
   
6.     7
   
7.     """
   
8.     "*** YOUR CODE HERE ***"
   
9.     return x[2][1]
   
10. 
    
11. 
    
12. def get_seven_b(x):
    
13.     """
    
14.     >>> x = [[7]]
    
15.     >>> get_seven_b(x)
    
16.     7
    
17.     """
    
18.     "*** YOUR CODE HERE ***"
    
19.     return x[0][0]
    
20. 
    
21. 
    
22. def get_seven_c(x):
    
23.     """
    
24.     >>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
    
25.     >>> get_seven_c(x)
    
26.     7
    
27.     """
    
28.     "*** YOUR CODE HERE ***"
    
29.     return x[1][1][1][1][1][1][0]
    
30. 
    
31. 
    
32. # Q5
    
33. def reverse_recursive(lst):
    
34.     """Returns the reverse of the given list.
    
35. 
    
36.     >>> reverse_recursive([1, 2, 3, 4])
    
37.     [4, 3, 2, 1]
    
38.     """
    
39.     "*** YOUR CODE HERE ***"
    
40.     if len(lst) < 1:
    
41.         return []
    
42.     return lst[-1:] + reverse_recursive(lst[:-1])
    
43. 
    
44. 
    
45. # Q6
    
46. def merge(lst1, lst2):
    
47.     """Merges two sorted lists recursively.
    
48. 
    
49.     >>> merge([1, 3, 5], [2, 4, 6])
    
50.     [1, 2, 3, 4, 5, 6]
    
51.     >>> merge([], [2, 4, 6])
    
52.     [2, 4, 6]
    
53.     >>> merge([1, 2, 3], [])
    
54.     [1, 2, 3]
    
55.     >>> merge([5, 7], [2, 4, 6])
    
56.     [2, 4, 5, 6, 7]
    
57.     """
    
58.     "*** YOUR CODE HERE ***"
    
59.     ret_list = []
    
60.     i = 0
    
61.     j = 0
    
62.     while i < len(lst1) and j < len(lst2):
    
63.         if lst1[i] < lst2[j]:
    
64.             ret_list.append(lst1[i])
    
65.             i += 1
    
66.         else:
    
67.             ret_list.append(lst2[j])
    
68.             j += 1
    
69.     while i < len(lst1):
    
70.         ret_list.append(lst1[i])
    
71.         i += 1
    
72.     while j < len(lst2):
    
73.         ret_list.append(lst2[j])
    
74.         j += 1
    
75.     return ret_list
    
76. 
    
77. 
    
78. # Q8
    
79. from math import sqrt
    
80. 
    
81. def is_square(n):
    
82.     """
    
83.     >>> is_square(49)
    
84.     True
    
85.     """
    
86.     return float(sqrt(n)) == int(sqrt(n))
    
87. 
    
88. def squares(seq):
    
89.     """Returns a new list containing elements of the original list that are
    
90.     perfect squares.
    
91. 
    
92.     >>> seq = [49, 8, 2, 1, 102]
    
93.     >>> squares(seq)
    
94.     [49, 1]
    
95.     >>> seq = [500, 30]
    
96.     >>> squares(seq)
    
97.     []
    
98.     """
    
99.     "*** YOUR CODE HERE ***"
    
100.     return [n for n in seq if is_square(n)]
     

复制代码

1. from lab04 import *
   
2. 
   
3. # Q9
   
4. def reverse_iter(lst):
   
5.     """Returns the reverse of the given list.
   
6. 
   
7.     >>> reverse_iter([1, 2, 3, 4])
   
8.     [4, 3, 2, 1]
   
9.     """
   
10.     "*** YOUR CODE HERE ***"
    
11.     ret_lst = []
    
12.     for i in range(len(lst)):
    
13.         ret_lst.append(lst[-1])
    
14.         lst = lst[:-1]
    
15.     return ret_lst
    
16. 
    
17. 
    
18. # Q10
    
19. def mergesort(seq):
    
20.     """Mergesort algorithm.
    
21. 
    
22.     >>> mergesort([4, 2, 5, 2, 1])
    
23.     [1, 2, 2, 4, 5]
    
24.     >>> mergesort([])     # sorting an empty list
    
25.     []
    
26.     >>> mergesort([1])   # sorting a one-element list
    
27.     [1]
    
28.     """
    
29.     "*** YOUR CODE HERE ***"
    
30.     if len(seq) == 0 or len(seq) == 1:
    
31.         return seq
    
32.     else:
    
33.         mid = len(seq) // 2
    
34.         return merge(mergesort(seq[:mid]), mergesort(seq[mid:]))
    
35. 
    
36. 
    
37. # Q11
    
38. def coords(fn, seq, lower, upper):
    
39.     """
    
40.     >>> seq = [-4, -2, 0, 1, 3]
    
41.     >>> fn = lambda x: x**2
    
42.     >>> coords(fn, seq, 1, 9)
    
43.     [[-2, 4], [1, 1], [3, 9]]
    
44.     """
    
45.     "*** YOUR CODE HERE ***"
    
46.     return [[x, fn(x)] for x in seq if fn(x) >= lower and fn(x) <= upper]
    
47. 
    
48. 
    
49. # Q12
    
50. def deck(suits, numbers):
    
51.     """Creates a deck of cards (a list of 2-element lists) with the given
    
52.     suits and numbers. Each element in the returned list should be of the form
    
53.     [suit, number].
    
54. 
    
55.     >>> deck(['S', 'C'], [1, 2, 3])
    
56.     [['S', 1], ['S', 2], ['S', 3], ['C', 1], ['C', 2], ['C', 3]]
    
57.     >>> deck(['S', 'C'], [3, 2, 1])
    
58.     [['S', 3], ['S', 2], ['S', 1], ['C', 3], ['C', 2], ['C', 1]]
    
59.     >>> deck([], [3, 2, 1])
    
60.     []
    
61.     >>> deck(['S', 'C'], [])
    
62.     []
    
63.     """
    
64.     "*** YOUR CODE HERE ***"
    
65.     return [[x, y] for x in suits for y in numbers]
    
66. 
    
67. 
    
68. # Q13
    
69. def add_matrices(x, y):
    
70.     """
    
71.     >>> matrix1 = [[1, 3],
    
72.     ...            [2, 0]]
    
73.     >>> matrix2 = [[-3, 0],
    
74.     ...            [1, 2]]
    
75.     >>> add_matrices(matrix1, matrix2)
    
76.     [[-2, 3], [3, 2]]
    
77.     """
    
78.     "*** YOUR CODE HERE ***"
    
79.     return [[x[i][j] + y[i][j] for j in range(len(x[0]))] for i in range(len(x))]
    

复制代码

没明白为啥这次作业的变量是protected的 求解求解 非常感谢

# Q4
def get_seven_a(x):
    """
    >>> x = [1, 3, [5, 7], 9]
    >>> get_seven_a(x)
    7
    """
    "*** YOUR CODE HERE ***"
    for i in x:
        if type(i) == list:
            return get_seven_a(i)
        elif i == 7:
            return i


def get_seven_b(x):
    """
    >>> x = [[7]]
    >>> get_seven_b(x)
    7
    """
    "*** YOUR CODE HERE ***"
    for i in x:
        if type(i) == list:
            return get_seven_a(i)
        elif i == 7:
            return i

def get_seven_c(x):
    """
    >>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
    >>> get_seven_c(x)
    7
    """
    for i in x:
        if type(i) == list:
            return get_seven_a(i)
        elif i == 7:
            return i

# Q5
def reverse_recursive(lst):
    """Returns the reverse of the given list.

    >>> reverse_recursive([1, 2, 3, 4])
    [4, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"
    if not lst:
        return []
    return [lst[-1]] + reverse_recursive(lst[0:-1])

# Q6
def merge(lst1, lst2):
    """Merges two sorted lists recursively.

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    """
    "*** YOUR CODE HERE ***"
    if not lst1 or not lst2:
        return lst1 + lst2
    elif lst1[0] < lst2[0]:
        return [lst1[0]] + merge(lst1[1:], lst2)
    else:
        return [lst2[0]] + merge(lst1, lst2[1:])

# Q8
from math import sqrt

def is_square(n):
    return float(sqrt(n)) == int(sqrt(n))

def squares(seq):
    """Returns a new list containing elements of the original list that are
    perfect squares.

    >>> seq = [49, 8, 2, 1, 102]
    >>> squares(seq)
    [49, 1]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    "*** YOUR CODE HERE ***"
    perfect_squares = [x for x in seq if is_square(x)]
    return perfect_squares

from lab04 import *

# Q9
def reverse_iter(lst):
    """Returns the reverse of the given list.

    >>> reverse_iter([1, 2, 3, 4])
    [4, 3, 2, 1]
    """
    "*** YOUR CODE HERE ***"
    reverse = []
    i = 0
    while i < len(lst):
        reverse = [lst[i]] + reverse
        i = i + 1
    return reverse

# Q10
def mergesort(seq):
    """Mergesort algorithm.

    >>> mergesort([4, 2, 5, 2, 1])
    [1, 2, 2, 4, 5]
    >>> mergesort([])     # sorting an empty list
    []
    >>> mergesort([1])   # sorting a one-element list
    [1]
    """
    "*** YOUR CODE HERE ***"
    if len(seq) < 2:
        return seq
    mid = len(seq) // 2
    return merge(mergesort(seq[:mid]), mergesort(seq[mid:]))
def merge(lst1, lst2):
    if not lst1 or not lst2:
        return lst1 + lst2
    elif lst1[0] < lst2[0]:
        return [lst1[0]] + merge(lst1[1:], lst2)
    else:
        return [lst2[0]] + merge(lst1, lst2[1:])

# Q11
def coords(fn, seq, lower, upper):
    """
    >>> seq = [-4, -2, 0, 1, 3]
    >>> fn = lambda x: x**2
    >>> coords(fn, seq, 1, 9)
    [[-2, 4], [1, 1], [3, 9]]
    """
    "*** YOUR CODE HERE ***"
    return [[x, fn(x)] for x in seq if lower <= fn(x) <= upper]

# Q12
def deck(suits, numbers):
    """Creates a deck of cards (a list of 2-element lists) with the given
    suits and numbers. Each element in the returned list should be of the form
    [suit, number].

    >>> deck(['S', 'C'], [1, 2, 3])
    [['S', 1], ['S', 2], ['S', 3], ['C', 1], ['C', 2], ['C', 3]]
    >>> deck(['S', 'C'], [3, 2, 1])
    [['S', 3], ['S', 2], ['S', 1], ['C', 3], ['C', 2], ['C', 1]]
    >>> deck([], [3, 2, 1])
    []
    >>> deck(['S', 'C'], [])
    []
    """
    "*** YOUR CODE HERE ***"
    return [[x, y] for x in suits
                   for y in numbers]

# Q13
def add_matrices(x, y):
    """
    >>> matrix1 = [[1, 3],
    ...            [2, 0]]
    >>> matrix2 = [[-3, 0],
    ...            [1, 2]]
    >>> add_matrices(matrix1, matrix2)
    [[-2, 3], [3, 2]]
    """
    "*** YOUR CODE HERE ***"
    return [[x[i][j] + y[i][j] for j in range(len(x[0]))] for i in range(len(x))]