编程基础-1-数组、链表

发表于 | 分类于 | 评论数： | 阅读次数：

数组

实现一个支持动态扩容的数组

参考：python实现动态数组

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
# coding:utf-8                                                                                                       
                                                                                                                     
class Array:                                                                                                         
    def __init__(self, capacity):                                                                                    
        self.capacity = capacity                                                                                     
        self.size = 0  # 元素数目                                                                                        
        self.data = [None] * self.capacity                                                                           
                                                                                                                     
    def resize(self, new_capacity):                                                                                  
        # 新建容量为new_capacity的数组，将原数组元素逐个移动到新数组中                                                                       
        new_arr = Array(new_capacity)                                                                                
        for i in range(self.size):                                                                                   
            new_arr.append_element(self.data[i])                                                                     
        self.capacity = new_capacity                                                                                 
        self.data = new_arr.data                                                                                     
        print("Resize!!!Now Array is", self.data)                                                                    
                                                                                                                     
    def add_element(self, index, e):                                                                                 
        if index < 0 or index > self.size:                                                                           
            print("index out of range")                                                                              
            return -1                                                                                                
        if self.size == self.capacity:  # 如果满了则扩容2倍                                                                  
            self.resize(2 * self.capacity)                                                                           
        for i in range(self.size - 1, index - 1, -1):  # 从后往前，将元素逐个往后移动一位，空位给新元素e                                    
            self.data[i + 1] = self.data[i]                                                                          
        self.data[index] = e                                                                                         
        self.size += 1                                                                                               
        print("Add element!!!Now Array is", self.data)                                                               
                                                                                                                     
    def append_element(self, e):                                                                                     
        self.add_element(self.size, e)  # 直接调用add_element，减少判断                                                                  
                                                                                                                     
                                                                                                                     
a = Array(3)                                                                                                         
a.add_element(1, 1)                                                                                                  
a.add_element(0, 5)                                                                                                  
a.append_element(6)                                                                                                  
a.append_element(1)                                                                                                  
a.append_element(4)                                                                                                  
                                                                                                                     
"""                                                                                                                  
index out of range                                                                                                   
Add element!!!Now Array is [5, None, None]                                                                           
Add element!!!Now Array is [5, 6, None]                                                                              
Add element!!!Now Array is [5, 6, 1]                                                                                 
Add element!!!Now Array is [5, None, None, None, None, None]                                                         
Add element!!!Now Array is [5, 6, None, None, None, None]                                                            
Add element!!!Now Array is [5, 6, 1, None, None, None]                                                               
Resize!!!Now Array is [5, 6, 1, None, None, None]                                                                    
Add element!!!Now Array is [5, 6, 1, 4, None, None]                                                                  
"""

实现一个大小固定的有序数组，支持动态增删改操作

需要注意数组始终有序，在下方代码中默认升序

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
# coding:utf-8

class SortList:
    def __init__(self, n):
        self.slist = []
        self.max_size = n  # 固定长度为n
        self.now_size = 0  # 记录当前长度方便后续操作

    def add_element(self, e):
        if self.now_size >= self.max_size:
            print("self.now_size >= self.max_size")
            return -1
        i = 0
        while (i < self.now_size):
            if self.slist[i] < e:
                i += 1
            else:
                break
        self.slist.append(e)
        self.now_size += 1
        print(self.slist)

    def remove_element(self, e):
        if self.now_size == 0:
            print("self.now_size == 0")
            return -1
        # self.slist.remove(e) 直接使用remove可以实现功能。下方使用二分法找到对应元素索引再根据索引删除

        ret = -1  # 待删除元素下标，不存在返回-1
        start = 0
        end = self.now_size
        while start < end:
            mid = (start + end) // 2
            if self.slist[mid] < e:
                start = mid + 1
            elif self.slist[mid] > e:
                end = mid - 1
            else:
                ret = mid
                break
        if ret == -1:
            print("element {} not found in slist".format(e))
            return -1
        del self.slist[ret]  # 或self.slist.pop(ret); 或使用切片删除
        # self.slist.pop(ret)
        self.now_size -= 1
        print(self.slist)

    def replace_element(self, old, new):
        self.remove_element(old)
        self.add_element(new)
        print(self.slist)


sl = SortList(3)
sl.add_element(1)
sl.remove_element(7)
sl.remove_element(1)
sl.add_element(2)
sl.add_element(3)
sl.add_element(4)
sl.replace_element(3, 5)
sl.add_element(1)
sl.remove_element(4)

"""
[1]
element 7 not found in slist
[]
[2]
[2, 3]
[2, 3, 4]
[2, 4]
[2, 4, 5]
[2, 4, 5]
self.now_size >= self.max_size
[2, 5]
"""

实现两个有序数组合并为一个有序数组

方法一

return sorted(list1+list2)，先合并再排序

方法二

使用一种比较朴素的方法来合并：遍历2个数组，将较小的数插入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
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
# coding:utf-8

def merge_sort_list(list1, list2):
    n1 = len(list1)
    n2 = len(list2)
    if (n1 == 0):
        return list2
    elif (n2 == 0):
        return list1
    list = []
    print(list)
    p1 = 0
    p2 = 0
    while p1 < n1 and p2 < n2:
        if list1[p1] <= list2[p2]:
            list.append(list1[p1])
            p1 += 1
        else:
            list.append(list2[p2])
            p2 += 1
        print(list)
    if p1 < n1:
        list += list1[p1:]
    else:
        list += list2[p2:]
    return list

# 一些测试用例
list1 = [1, 3, 5, 6, 8]
list2 = [0, 1, 2, 3, 4, 9, 10]
print(merge_sort_list(list1, list2))
print(sorted(list1 + list2))  # 用于对比结果
"""
[]
[0]
[0, 1]
[0, 1, 1]
[0, 1, 1, 2]
[0, 1, 1, 2, 3]
[0, 1, 1, 2, 3, 3]
[0, 1, 1, 2, 3, 3, 4]
[0, 1, 1, 2, 3, 3, 4, 5]
[0, 1, 1, 2, 3, 3, 4, 5, 6]
[0, 1, 1, 2, 3, 3, 4, 5, 6, 8]
[0, 1, 1, 2, 3, 3, 4, 5, 6, 8, 9, 10]
[0, 1, 1, 2, 3, 3, 4, 5, 6, 8, 9, 10]
"""

list1 = [1, 3, 5, 6, 8]
list2 = []
print(merge_sort_list(list1, list2))
print(sorted(list1 + list2))
"""
[1, 3, 5, 6, 8]
[1, 3, 5, 6, 8]
"""

list1 = []
list2 = [0, 1, 2, 3, 4, 9, 10]
print(merge_sort_list(list1, list2))
print(sorted(list1 + list2))
"""
[0, 1, 2, 3, 4, 9, 10]
[0, 1, 2, 3, 4, 9, 10]
"""

list1 = []
list2 = []
print(merge_sort_list(list1, list2))
print(sorted(list1 + list2))
"""
[]
[]
"""

哈希表

学习哈希表思想，并完成leetcode上的两数之和(1)及Happy Number(202)！(要求全部用哈希思想实现！)

哈希表可简单理解为k-v，在python中，哈希表可用dict表示

leetcode-1-两数之和

代码见：leetcode-1-两数之和 中”方法二”，使用dict记录当前元素下标和匹配的值

LeetCode-202-快乐数Happy Number

使用dict记录求过的数

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
class Solution(object):                                    
    def isHappy(self, n):                                  
        """                                                
        :type n: int                                       
        :rtype: bool                                       
        """                                                
        m_dict = {}                                        
        while n != 1:                                      
            # print(n)                                     
            n = sum(int(i) ** 2 for i in str(n))           
            if n in m_dict:                                
                return False                               
            m_dict[n] = 1                                  
        return True                                        
                                                                                                                  
s = Solution()                                             
print(s.isHappy(19))                                       
                                                           
"""                                                        
19                                                         
82                                                         
68                                                         
100                                                        
True                                                       
"""

对应的 LeetCode 练习题

Three Sum（求三数之和）

英文版：https://leetcode.com/problems/3sum/
中文版：https://leetcode-cn.com/problems/3sum/
代码见：leetcode-15-三数之和

Majority Element（求众数）

英文版：https://leetcode.com/problems/majority-element/

中文版：https://leetcode-cn.com/problems/majority-element/

使用dict记录{当前num：出现次数}

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        m_dict = {}                         
        for e in nums:                      
            m_dict[e] = m_dict.get(e, 0) + 1
            if m_dict[e] > len(nums) / 2:  
                return e

或者调用Counter

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        from collections import Counter
        num=dict(Counter(nums))
        for key in num:
            if num[key]>len(nums)/2:
                return key

Missing Positive（求缺失的第一个正数）

英文版：https://leetcode.com/problems/first-missing-positive/
中文版：https://leetcode-cn.com/problems/first-missing-positive/
思路：使用桶，大小为len(nums)，负数可以丢弃，大于len(nums)的数也可以丢弃。遍历一遍后nums后，遍历桶，返回第一个空位index
代码如下：

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 Solution(object):                                    
    def firstMissingPositive(self, nums):                  
        """                                                
        :type nums: List[int]                              
        :rtype: int                                        
        """                                                
        n = len(nums) + 1  # 0位置无效，多设置一位，使用index更直观        
        bucket = [0] * n                                   
        for e in nums:                                     
            # print(bucket)                                
            if e > 0 and e < n:  # 求的是第一个缺失的正整数，>n的数可以丢弃   
                bucket[e] = e  # 非0值，设置为e方便debug           
        # print(bucket)                                    
        for i in range(1, n):                              
            if bucket[i] == 0:                             
                return i                                   
        return n                                           
                                                           
                                                           
s = Solution()                                             
print(s.firstMissingPositive([1, 2, 0]))  # 3              
print(s.firstMissingPositive([1, 2]))  # 3                 
print(s.firstMissingPositive([3, 4, -1, 1]))  # 2          
print(s.firstMissingPositive([7, 8, 9, 11, 12]))  # 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
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
# coding: utf-8

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


class LinkedList(object):
    def __init__(self):
        self.head = None

    def __len__(self):
        pre = self.head
        length = 0
        while pre:
            length += 1
            pre = pre.nex
        return length

    def is_empty(self):
        return False if len(self) > 0 else True

    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
        else:
            pre = self.head
            while pre.next:
                pre = pre.next
            pre.next = node

    def insert(self, index, data):
        node = Node(data)
        if abs(index + 1) > len(self):
            return False
        index = index if index >= 0 else len(self) + index + 1
        if index == 0:
            node.next = self.head
            self.head = node
        else:
            pre = self.get(index - 1)
            if pre:
                nex = pre.nex
                pre.nex = node
                node.next = nex
            else:
                return False
        return node

    def delete(self, index):
        f = index if index > 0 else abs(index + 1)
        if len(self) <= f:
            return False
        pre = self.head
        index = index if index >= 0 else len(self) + index
        prep = None
        while index:
            prep = pre
            pre = pre.nex
            index -= 1
        if not prep:
            self.head = pre.nex
        else:
            prep.nex = pre.nex
        return pre.data

实现单链表反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# coding: utf-8

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


class LinkedList(object):
    def __init__(self):
        self.head = None
 
    def __reversed__(self):
        def reverse(pre_node, node):
            if pre_node is self.head:
                pre_node.nex = None
            if node:
                next_node = node.nex
                node.nex = pre_node
                return reverse(node, next_node)
            else:
                self.head = pre_node

        return reverse(self.head, self.head.nex)

实现两个有序的链表合并为一个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
def Merge(self, pHead1, pHead2):
       if pHead1 == None:
           return pHead2
       elif pHead2 == None:
           return pHead1
       pMergedHead = None
       if pHead1.val < pHead2.val:
           pMergedHead = pHead1
           pMergedHead.next = self.Merge(pHead1.next, pHead2)
       else:
           pMergedHead = pHead2
           pMergedHead.next = self.Merge(pHead1, pHead2.next)
       return pMergedHead

实现求链表的中间结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# coding: utf-8

class Node:
    def __init__(self,data,next):
        self.data = data
        self.next = next
n1 = Node('n1',None)
n2 = Node('n2',n1)
n3 = Node('n3',n2)
n4 = Node('n4',n3)
n5 = Node('n5',n4)

p1 = n5
p2 = n5
while p2.next is not None and p2.next.next is not None:
    p1 = p1.next
    p2 = p2.next.next
print(p1.data)

对应的 LeetCode 练习题

Linked List Cycle I（环形链表）

英文版：https://leetcode.com/problems/linked-list-cycle/

中文版：https://leetcode-cn.com/problems/linked-list-cycle/

Merge k Sorted Lists（合并 k 个排序链表）

英文版：https://leetcode.com/problems/merge-k-sorted-lists/

中文版：https://leetcode-cn.com/problems/merge-k-sorted-lists/