数据结构-2-数组、字符串

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

数组

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

参考：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

字符串

实现一个字符集，只包含 a～z 这 26 个英文字母的 Trie 树

Trie树又叫做前缀树（Prefix Tree）

将每个节点的children都是一个dict，根据dict中的key找下一个节点

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
# coding:utf-8                                          
                                                        
class Node(object):                                     
    def __init__(self):                                 
        self.children = {}                              
        self.is_end = False                             
                                                        
                                                        
class Trie(object):                                     
    def __init__(self):                                 
        self.root = Node()                              
                                                        
    def insert(self, word):                             
        node = self.root                                
        for w in word:                                  
            if w not in node.children:                  
                node.children[w] = Node()               
            node = node.children[w]                     
        node.is_end = True                              
                                                        
    def search(self, word):                             
        node = self.root                                
        for w in word:                                  
            if w not in node.children:                  
                return False                            
            node = node.children[w]                     
        return node.is_end                              
                                                        
                                                        
t = Trie()                                              
t.insert("hi")                                          
t.insert("hello")                                       
print(t.search("a"))  # False                           
print(t.search("hi"))  # True

实现朴素的字符串匹配算法

字符串匹配：字符串”abcde”中是否含有字符串”bd”

朴素算法：暴力解，下面给出了2种方式

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

def find_str(str1, str2):
    n1 = len(str1)
    n2 = len(str2)
    if n2 == 0:
        return 0
    for i in range(n1 - n2):
        for j in range(n2):
            # print(i, j)
            if str1[i + j] != str2[j]:
                break
            else:
                if j == n2 - 1:
                    return i
    return -1

def find_str2(str1, str2):
    p1 = 0
    p2 = 0
    while p1 < len(str1) and p2 < len(str2):
        # print(p1, p2)
        if str1[p1] == str2[p2]:
            p1, p2 = p1 + 1, p2 + 1
        else:
            p1, p2 = p1 - p2 + 1, 0  # 注意p1取值为 p1 - p2 + 1
    if p2 == len(str2):
        return p1 - p2
    return -1


str1 = "abcdefs"
str2 = "bc"
str3 = "ea"
str4 = "jljljkjjjl"
str5 = ""
str8 = "ab"
print(find_str(str1, str2))
print(find_str2(str1, str2))
print(str1.find(str2))  # 1  使用find用于检验结果

print(find_str(str1, str3))
print(find_str2(str1, str3))
print(str1.find(str3))  # -1

print(find_str(str1, str4))
print(find_str2(str1, str4))
print(str1.find(str4))  # -1

print(find_str(str1, str5))
print(find_str2(str1, str5))
print(str1.find(str5))  # 0

print(find_str(str1, str8))
print(find_str2(str1, str8))
print(str1.find(str8))  # 0

str6 = ""
str7 = ""
print(find_str(str6, str7))
print(find_str2(str6, str7))
print(str6.find(str7))  # 0

对应的 LeetCode 练习题

Reverse String （反转字符串）

英文版：https://leetcode.com/problems/reverse-string/
中文版：https://leetcode-cn.com/problems/reverse-string/
代码见：leetcode-344-反转字符串

Reverse Words in a String（翻转字符串里的单词）

英文版：https://leetcode.com/problems/reverse-words-in-a-string/
中文版：https://leetcode-cn.com/problems/reverse-words-in-a-string/
代码如下：

1
2
3
4
5
6
7
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        return " ".join(s.strip().split()[::-1])

String to Integer (atoi)（字符串转换整数 (atoi)）

英文版：https://leetcode.com/problems/string-to-integer-atoi/
中文版：https://leetcode-cn.com/problems/string-to-integer-atoi/
代码见：leetcode-8-字符串转换整数(atoi)