编程基础-4-散列表、字符串

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

散列表（哈希表）

实现一个基于链表法解决冲突问题的散列表

参考：https://www.cnblogs.com/linxiyue/p/3795396.html

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
class _ListNode(object):
    def __init__(self,key):
        self.key=key
        self.next=None
class HashMap(object):
    def __init__(self,tableSize):
        self._table=[None]*tableSize
        self._n=0  #number of nodes in the map
    def __len__(self):
        return self._n
    def _hash(self,key):
        return abs(hash(key))%len(self._table)
    def __getitem__(self,key):
        j=self._hash(key)
        node=self._table[j]
        while node is not None and node.key!=key :
            node=node.next
        if node is None:
            raise KeyError,'KeyError'+repr(key)
        return node       
    def insert(self,key):
        try:
            self[key]
        except KeyError:
            j=self._hash(key)
            node=self._table[j]
            self._table[j]=_ListNode(key)
            self._table[j].next=node
            self._n+=1
    def __delitem__(self,key):
        j=self._hash(key)
        node=self._table[j]
        if node is not None:
            if node.key==key:
                self._table[j]=node.next
                self._-=1
            else:
                while node.next!=None:
                    pre=node
                    node=node.next
                    if node.key==key:
                        pre.next=node.next
                        self._n-=1
                        break

实现一个 LRU 缓存淘汰算法

LRU全称是Least Recently Used，即最近最久未使用的意思。

LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

使用dict和list实现

比较自然的想法：使用dict存<key,value>，使用list记录访问顺序，索引[0,…,capacity-1]，越小表示访问时间越近，每次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
# coding: utf-8

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.lru_cache = {}
        self.sort_list = []  # 访问顺序

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.lru_cache:
            value = self.lru_cache[key]
            self.sort_list.remove(key)
            self.sort_list.insert(0, key)
        else:
            value = -1
        print("get", key, ": ", self.lru_cache, self.sort_list)
        return value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.lru_cache:
            self.lru_cache[key] = value
            self.sort_list.remove(key)
            self.sort_list.insert(0, key)
        else:
            if len(self.sort_list) == self.capacity:
                last_key = self.sort_list.pop()
                self.lru_cache.pop(last_key)
            self.sort_list.insert(0, key)
            self.lru_cache[key] = value

        print("put <", key, ":", value, ">: ", self.lru_cache, self.sort_list)


# Your LRUCache object will be instantiated and called as such:
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print("get value is: ",cache.get(1))
cache.put(3, 3)
cache.put(4, 4)
print("get value is: ",cache.get(1))
print("get value is: ",cache.get(3))
print("get value is: ",cache.get(5))

"""
put < 1 : 1 >:  {1: 1} [1]
put < 2 : 2 >:  {1: 1, 2: 2} [2, 1]
get 1 :  {1: 1, 2: 2} [1, 2]
get value is:  1
put < 3 : 3 >:  {1: 1, 3: 3} [3, 1]
put < 4 : 4 >:  {3: 3, 4: 4} [4, 3]
get 1 :  {3: 3, 4: 4} [4, 3]
get value is:  -1
get 3 :  {3: 3, 4: 4} [3, 4]
get value is:  3
get 5 :  {3: 3, 4: 4} [3, 4]
get value is:  -1
"""

对应的 LeetCode 练习题

哈希表

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

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                                                       
"""

字符串

实现一个字符集，只包含 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)