Why data structures?

Data structures are containers that organize and group data together in different ways. When you write code to solve a problem, there will always be data involved—and how you store or structure that data in the computer's memory can have a huge impact on what kinds of things you can do with it and how efficiently you can do those things.

Collections:(集合)

Properties of collections

  • Don't have a particular order (so you can't say "give me the 3rd element in this collection")
  • Don't have to have objects of the same type.

Lists

Properties of lists

  • Have an order (so you can say things like "give me the 3rd item in the list")
  • Have no fixed length (you can add or remove elements)

Array(数组)

An array has some things in common with a list. In both cases: * There is a collection of items * The items have an order to them

When an array is created, it is always given some initial size—that is, the number of elements it should be able to hold (and how large each element is). The computer then finds a block of memory and sets aside the space for the array.

Importantly, the space that gets set aside is one, continuous block. That is, all of the elements of the array are contiguous, meaning that they are all next to one another in memory.d

Another key characteristic of an array is that all of the elements are the same size.

When we represent an array visually, we often draw it as a series of boxes that are all of the same size and all right next to one another:

Because all of the elements are 1) next to one another and 2) the same size, this means that if we know the location of the first element, we can calculate the location of any other element.

For example, if the first element in the array is at memory location 00 and the elements are 24 bytes, then the next element would be at location 00 + 24 = 24. And the one after that would be at 24 + 24 = 48, and so on.

Since we can easily calculate the location of any item in the array, we can assign each item an index and use that index to quickly and directly access the item.

补充:Python list is essentially implemented like an array (specifically, it behaves like a dynamic array, if you're curious). In particular, the elements of a Python list are contiguous in memory, and they can be accessed using an index.In addition to the underlying array(除了数组), a Python list also includes some additional behavior(python的list有自己的方法). For example, you can use things like pop and append methods on a Python list to add or remove items. Using those methods, you can essentially utilize a Python list like a stack.

String

  • 在python中字符串是代表Unicode字符的字节数组。

反转字符串

string_reverser函数以一个字符串作为输入，返回反转后的字符串。 例如：输入water，返回retaw。 

1
2
3
4
5
6
7
def string_reverser(our_string):
    reverse_string = ''
    i = len(our_string) - 1
    while i >= 0:
        reverse_string += our_string[i]
        i -= 1
    return reverse_string
测试用例： 
1
2
3
4
5
# Test Cases
print(string_reverser('love'))
print ("Pass" if ('retaw' == string_reverser('water')) else "Fail")
print ("Pass" if ('!noitalupinam gnirts gnicitcarP' == string_reverser('Practicing string manipulation!')) else "Fail")
print ("Pass" if ('3432 :si edoc esuoh ehT' == string_reverser('The house code is: 2343')) else "Fail")
#### 重组字符串(Anagrams)

Anagrams是一个字符串中的字符重组后的字符串。anagram_checker函数用来判断两个字符串是否为Anagrams。

示例： * "rat" is an anagram of "art" * "alert" is an anagram of "alter" * "Slot machines" is an anagram of "Cash lost in me"

假设输入的两个字符串： * 没有标点符号 * 没有数字 * 没有特殊字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def anagram_checker(str1, str2):
    str1 = str1.lower()
    str2 = str2.lower()
    
    str2 = list(str2)
    
    for char in str1:
        if char == ' ':
            continue
        if char in str2:
            str2.remove(char)
    if len(str2) > 0:
        for char in str2:
            if char != ' ':
                return False
    return True

测试用例： 

1
2
3
4
5
6
# Test Cases
print ("Pass" if not (anagram_checker('water','waiter')) else "Fail")
print ("Pass" if anagram_checker('Dormitory','Dirty room') else "Fail")
print ("Pass" if anagram_checker('Slot machines', 'Cash lost in me') else "Fail")
print ("Pass" if not (anagram_checker('A gentleman','Elegant men')) else "Fail")
print ("Pass" if anagram_checker('Time and tide wait for no man','Notified madman into water') else "Fail")
#### 反转句子中的字符串(词)

word_flipper函数将给定句子中的每个词进行反转，但词的顺序不改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def string_reverser(our_string):
    reverse_string = ''
    i = len(our_string) - 1
    while i >= 0:
        reverse_string += our_string[i]
        i -= 1
    return reverse_string
def word_flipper(our_string):
    reverse_string = ''
    word = ''
    for i in range(len(our_string)):
        if i == len(our_string)-1:
            word += our_string[i]
            reverse_string += string_reverser(word)
        if our_string[i] == ' ':
            reverse_string += string_reverser(word)
            reverse_string += ' '
            word = ''
        else:
            word += our_string[i]
    return reverse_string

测试用例： 

1
2
3
print ("Pass" if ('retaw' == word_flipper('water')) else "Fail")
print ("Pass" if ('sihT si na elpmaxe' == word_flipper('This is an example')) else "Fail")
print ("Pass" if ('sihT si eno llams pets rof ...' == word_flipper('This is one small step for ...')) else "Fail")
#### 汉明距离

在信息论中，汉明距离是指两个相同长度的字符串中对应字符不同的位置数。 

1
2
3
4
5
6
7
8
def hamming_distance(str1, str2):
    if len(str1) != len(str2):
        return None
    distance = 0
    for i in range(len(str1)):
        if str1[i] != str2[i]:
            distance += 1
    return distance
测试用例： 
1
2
3
4
5
print ("Pass" if (10 == hamming_distance('ACTTGACCGGG','GATCCGGTACA')) else "Fail")
print ("Pass" if  (1 == hamming_distance('shove','stove')) else "Fail")
print ("Pass" if  (None == hamming_distance('Slot machines', 'Cash lost in me')) else "Fail")
print ("Pass" if  (9 == hamming_distance('A gentleman','Elegant men')) else "Fail")
print ("Pass" if  (2 == hamming_distance('0101010100011101','0101010100010001')) else "Fail")
## 链表(Linked List)

链表的每个结点是通过指针连起来的，链表中每个结点除了存储自身的数据外还要存储下一结点的地址。 > 单向的链表只记录一个后面结点的地址(next，双向链表记录前一个和后一个结点的地址(pre、next)

python实现并遍历链表

  • 定义链表中结点

创建拥有值(value)和指针(next)的结点(Node): 

1
2
3
4
class Node(object):
	def __init__(self, value):
		self.value = value
		self.next = None
生成值为2的头节点以及第二个节点(值为1)： 
1
2
head = Node(2)
head.next = Node(1)
* 迭代生成链表： 
1
2
3
4
5
6
7
8
9
10
11
def create_linked_list(input_list):
    head = None
    node = None
    for i in range(len(input_list)):
        if i == 0:
            head = Node(input_list[0])
            node = head
        else:
            node.next = Node(input_list[i])
            node = node.next
    return head
* 遍历链表 
1
2
3
4
5
6
7
8
def traverse_list(node):
    if node != None:
        print(node.value)
    else:
        return None
    while node.next != None:
        node = node.next
        print(node.value)
### python实现不同的链表类型

链表的类型有单链表、双向链表以及循环链表。

单链表(singly linked lists)

单链表中每个节点仅指向其后一个节点。

  • 定义节点类： 
    1
    2
    3
    4
    class Node(object):
    	def __init__(self, value):
    		self.value = value
    		self.next = None
    单链表示例： 
    1
    2
    head = Node(1)
    head.next = Node(2)
  • 用类实现单链表： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Node:
        def __init__(self, value):
            self.value = value
            self.next = None
    class LinkedList(object):
        def __init__(self):
            self.head = None
        
        def append(self, value):
            if self.head is None:
                self.head = Node(value)
                return
            node = self.head
            while node.next != None:
                node = node.next
            node.next = Node(value)
    实现具有如下方法的类：
  • 向链表尾部增加节点以及在头部前面增加节点
  • 搜索链表中是否存在某个值并返回该节点
  • 移除(remove)一个节点
  • 弹出(pop)，返回第一个节点的值并将该节点删除
  • 在某位置插入节点
  • 返回链表长度的方法 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    class Node(object):
        def __init__(self, value):
            self.value = value
            self.next = None
    class LinkedList(object):
        def __init__(self):
            self.head = None

        def append(self, value):
            node = self.head
            if node is None:
                self.head = Node(value)
                return
            while node.next != None:
                node = node.next
            node.next = Node(value)
            return
        def prepend(self, value):
            if self.head is None:
                self.head = Node(value)
                return
            node = self.head
            self.head = Node(value)
            self.head.next = node
            return
        def search(self, value):
            if self.head is None:
                return None
            node = self.head
            while node.value != value:
                node = node.next
                if node is None:
                    return None
            return node
        def remove(self, value):
            if self.head is None:
                return
            if self.head.value == value:
                node = self.head.next
                self.head.next = None
                self.head = node
                return
            pre = self.head
            node = self.head.next
            while node.value != value:
                pre = node
                node = node.next
                if node is None:
                    return
            pre.next = node.next
            node.next = None
            return
        def pop(self):
            if self.head is None:
                return None
            node = self.head
            self.head = node.next
            node.next = None
            return node.value  
        def insert(self, value, pos):
            if pos == 0:
                node = self.head
                self.head = Node(value)
                self.head.next = node
                return
            pre = self.head
            node = self.head.next
            index = 1
            while pos != index:
                if node is None:
                    pre.next = Node(value)
                    return
                pre = node
                node = node.next
            pre.next = Node(value)
            pre.next.next = node
            return
        def size(self):
            if self.head is None:
                return 0
            node = self.head
            size = 1
            while node.next != None:
                size += 1
                node = node.next
            return size
        def to_list(self):
            out = []
            node = self.head
            while node:
                out.append(node.value)
                node = node.next
            return out
    测试用例： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    ## Test your implementation here

    # Test prepend
    linked_list = LinkedList()
    linked_list.prepend(1)
    assert linked_list.to_list() == [1], f"list contents: {linked_list.to_list()}"
    linked_list.append(3)
    linked_list.prepend(2)
    assert linked_list.to_list() == [2, 1, 3], f"list contents: {linked_list.to_list()}"
        
    # Test append
    linked_list = LinkedList()
    linked_list.append(1)
    assert linked_list.to_list() == [1], f"list contents: {linked_list.to_list()}"
    linked_list.append(3)
    assert linked_list.to_list() == [1, 3], f"list contents: {linked_list.to_list()}"

    # Test search
    linked_list.prepend(2)
    linked_list.prepend(1)
    linked_list.append(4)
    linked_list.append(3)
    assert linked_list.search(1).value == 1, f"list contents: {linked_list.to_list()}"
    assert linked_list.search(4).value == 4, f"list contents: {linked_list.to_list()}"

    # Test remove
    linked_list.remove(1)
    assert linked_list.to_list() == [2, 1, 3, 4, 3], f"list contents: {linked_list.to_list()}"
    linked_list.remove(3)
    assert linked_list.to_list() == [2, 1, 4, 3], f"list contents: {linked_list.to_list()}"
    linked_list.remove(3)
    assert linked_list.to_list() == [2, 1, 4], f"list contents: {linked_list.to_list()}"

    # Test pop
    value = linked_list.pop()
    assert value == 2, f"list contents: {linked_list.to_list()}"
    assert linked_list.head.value == 1, f"list contents: {linked_list.to_list()}"

    # Test insert 
    linked_list.insert(5, 0)
    assert linked_list.to_list() == [5, 1, 4], f"list contents: {linked_list.to_list()}"
    linked_list.insert(2, 1)
    assert linked_list.to_list() == [5, 2, 1, 4], f"list contents: {linked_list.to_list()}"
    linked_list.insert(3, 6)
    assert linked_list.to_list() == [5, 2, 1, 4, 3], f"list contents: {linked_list.to_list()}"

    # Test size
    assert linked_list.size() == 5, f"list contents: {linked_list.to_list()}"
  • 反转单链表

给定一个单链表，返回一个它反转后的单链表 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# Helper Code

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, value):
        if self.head is None:
            self.head = Node(value)
            return
        
        node = self.head
        while node.next:
            node = node.next

        node.next = Node(value)
        
    def __iter__(self):
        node = self.head
        while node:
            yield node.value
            node = node.next
            
    def __repr__(self):
        return str([v for v in self])

# 反转单链表函数
def reverse(linkedlist):
    if linkedlist.head is None:
        return None
    value_list = list()
    for value in linkedlist:
        value_list.append(value)
    i = len(value_list) - 1
    reverse_linkedlist = LinkedList()
    reverse_linkedlist.head = Node(value_list[i])
    node = reverse_linkedlist.head
    i -= 1
    while i >= 0:
        node.next = Node(value_list[i])
        node = node.next
        i -= 1
    return reverse_linkedlist
测试用例： 
1
2
3
4
5
6
7
llist = LinkedList()
for value in [4,2,5,1,-3,0]:
    llist.append(value)

flipped = reverse(llist)
is_correct = list(flipped) == list([0,-3,1,5,2,4]) and list(llist) == list(reverse(flipped))
print("Pass" if is_correct else "Fail")
* 展平嵌套链表 嵌套链表是节点为排序好的单链表的链表。 展平嵌套链表就是将所有节点(子链表)合为一个排序好的单链表。

  1. 节点和单链表类的定义 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Node:
        def __init__(self, value):
            self.value = value
            self.next = None

        def __repr__(self):
            return str(self.value)


    class LinkedList:
        def __init__(self, head):
            self.head = head

        def append(self, value):
            if self.head is None:
                self.head = Node(value)
                return
            node = self.head
            while node.next is not None:
                node = node.next
            node.next = Node(value)
  2. 实现展平函数

hint:如果提前写一个merge函数用于合并两个单链表会让代码看起来更简介 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
def merge(list1, list2):
    node1 = list1.head
    node2 = list2.head
    list_sorted = None
    node_sorted = None
    while node1 != None and node2 != None:
        value = None
        if node1.value <= node2.value:
            value = node1.value
            if node1.next != None:
                node1 = node1.next
            else:
                node_sorted.next = Node(value)
                node_sorted = node_sorted.next
                node_sorted.next = node2
                return list_sorted
        else:
            value = node2.value
            if node2.next != None:
                node2 = node2.next
            else:
                node_sorted.next = Node(value)
                node_sorted = node_sorted.next
                node_sorted.next = node1
                return list_sorted
        if list_sorted is None:
            list_sorted = LinkedList(Node(value))
            node_sorted = list_sorted.head
        else:
            node_sorted.next = Node(value)
            node_sorted = node_sorted.next
    return list_sorted
class NestedLinkedList(LinkedList):
    def __init__(self, head):
        self.head = head
    def append(self, linkedlist):
        node = self.head
        while node.next != None:
            node = node.next
        node.next = Node(linkedlist)
        return
    def flatten(self):
        node = self.head
        list1 = node.value
        while node.next != None:
            list2 = node.next.value
            list1 = merge(list1, list2)
            node = node.next
        return list1
3. 测试用例 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
linked_list = LinkedList(Node(1))
linked_list.append(3)
linked_list.append(5)

second_linked_list = LinkedList(Node(2))
second_linked_list.append(4)

nested_linked_list = NestedLinkedList(Node(linked_list))
nested_linked_list.append(second_linked_list)

solution = nested_linked_list.flatten()
node = solution.head
value_list = []
while node != None:
    print(node.value)
    node = node.next
输出1 2 3 4 5

双向链表(doubly linked list)

双向链表中除了头节点和尾节点，节点不仅指向下一个节点还指向上一个节点。

定义节点类： 

1
2
3
4
5
class DoubleNode(object):
	def __init__(self, value):
		self.value = value
		self.previous = None
		self.next = None
定义双向链表类： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class DoublyLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, value):
        if self.head is None:
            self.head = DoubleNode(value)
            self.tail = self.head
            return
        node = DoubleNode(value) 
        self.tail.next = node
        node.previous = self.tail
        self.tail = node
        return
#### 循环链表(circular linked list) 循环链表是指链表中某个节点的next指针指向了其前面的节点。

判断是否为循环链表的方法 检测单链表中是否存在环：利用两个指针(runner)，一个跑的快，一个跑的慢。runner们一起从头节点出发，慢的runner一次移动1步，快的runner一次移动2步，如果存在两个runner相遇的情况，那么链表中存在环。

  1. 类的定义 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Node:
        def __init__(self, value):
            self.value = value
            self.next = None
            
    class LinkedList:
        def __init__(self, init_list=None):
            self.head = None
            if init_list:
                for value in init_list:
                    self.append(value)
            
        def append(self, value):
            if self.head is None:
                self.head = Node(value)
                return
            
            # Move to the tail (the last node)
            node = self.head
            while node.next:
                node = node.next
            
            node.next = Node(value)
            return
  2. 创建含有环的单链表 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    list_with_loop = LinkedList([2, -1, 3, 0, 5])

    # Creating a loop where the last node points back to the second node
    loop_start = list_with_loop.head.next

    node = list_with_loop.head
    while node.next: 
        node = node.next   
    node.next = loop_start
  3. 判断链表中是否有环的函数 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def iscircular(linked_list):
        if linked_list.head is None:
            return False
        slow_runner = linked_list.head
        fast_runner = linked_list.head
        while fast_runner is not None:
            if fast_runner.next is None:
                return False
            else:
                if fast_runner.next.next is None:
                    return False
                else:
                    fast_runner = fast_runner.next.next
                    slow_runner = slow_runner.next
            if fast_runner == slow_runner:
                return True
        return False
  4. 测试用例 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    # Test Cases

    small_loop = LinkedList([0])
    small_loop.head.next = small_loop.head
    print ("Pass" if iscircular(list_with_loop) else "Fail")
    print ("Pass" if not iscircular(LinkedList([-4, 7, 2, 5, -1])) else "Fail")
    print ("Pass" if not iscircular(LinkedList([1])) else "Fail")
    print ("Pass" if iscircular(small_loop) else "Fail")
    print ("Pass" if not iscircular(LinkedList([])) else "Fail")