数据结构：字符串与哈希表

字符串和哈希表的一些知识点

Python3 字符串基础代码

字符串

upper and lower

ord()：char转ASCII

chr()：ASCII 转 char

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
def lower2upper(_char):
    """convert lower character to upper character
    :param _char: char
    :return: char
    """
    try:
        if ord('a') <= ord(_char) <= ord('z') : 
            char_ASCII = ord(_char) - 32
            upper_char = chr(char_ASCII)
            return upper_char
        else:
            raise ValueError("_char must between \'a\' and \'z\'.")
    except Exception as e:
        print(e)

def upper2lower(_char):
    """convert upper character to lower character
    :param _char: char
    :return: char
    """
    try:
        if ord('A') <= ord(_char) < ord('Z'):
            char_ASCII = ord(_char) + 32
            lower_char = chr(char_ASCII)
            return lower_char
        else:
            raise ValueError("_char must between \'A\' and \'Z\'.")
    except Exception as e:
        print(e)


if __name__ == "__main__":
    upper = lower2upper('a')
    if upper:  print(upper)
    lower = upper2lower('8')
    if lower:  print(lower)

split

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def split(target, s):
    """ split str according special divider
    :param target: str
    :param s: str
    :return: list
    """
    try:
        if s:
            start = 0
            res = []
            for i in range(len(s)):
                if s[i] == target:
                    res.append(s[start:i])
                    start = i + 1
            res.append(s[start:])
            return res
        else:
            raise ValueError("s is not allowed to be empty!")
    except Exception as e:
        print(e)

join

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def join(link, lists):
    """join items in the list by special linker
    :param link: str
    :param lists: list
    :return: str
    """
    try:
        if len(lists):
            res = ''
            for i in lists:
                res += (i+link)
            if len(link):
                res = res[:-len(link)]
            return res
        else:
            raise ValueError("lists is not allowed to be empty!")
    except Exception as e:
        print(e)

replace

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def replace(target, replce, string):
    """replace character in the str with anoteher charcter
    :param target: str
    :param replace: str
    :param string: str
    :return: str
    """
    try:
        if target and replace and string:
            segments = split(target, string)
            res = join(replce, segments)
            return res
        else:
            raise ValueError("paramter error")
    except Exception as e:
        print(e)

String sorted

手写 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
def stringSorted(_strs: List[str]) -> List[str]:
    """sort str
    :param _strs: List[str]
    :return List[str]:
    """
    # 处理并列  A(65) > Z(90) | a(97) > z(112)
    # 第一原则：字母越小越在前面。
    # 第二原则：字母一样的，短小的越在前面。
    # 把名字处理成整数 Tom -> 84 111 109 || Lucy -> 76 117 99 121 || Tomy -> 84 111 109 121
    if len(_strs) == 0: return []
    _dict = {}
    for name in res:
        tmp_list = []
        for j in name:
            tmp_list.append(ord(j))
        _dict[name] = tmp_list

    res = name
    index = 0  # 从名字的第一位开始比较
    chars = _dict[res]
    del _dict[res]  # 默认的这个可以删除掉 后面的比较中就不会自己和自己比较了
    tmp = [res]

    for name in _dict:
        while True:
            if _dict[name][index] < chars[index]:  # 找到一个更大的
                res = name
                tmp.append(name)
                chars = _dict[name]
                break  # 结束 while 循环
            elif _dict[name][index] == chars[index]:  # 当前位一样 去下一位比较
                if (index + 1) > (len(chars) - 1) or (index + 1) > (len(_dict[name]) - 1):  # 长度已经不一样了
                    if len(chars) < len(_dict[name]):  # 字母一样的，短小的越在前面。
                        break  # 结束 while 循环 保持原来的res
                    else:  # 当前的这个人名字更短
                        res = name
                        tmp.append(name)
                        chars = _dict[name]
                        break  # 结束 while 循环
                else:
                    index += 1  # 还没有超出去 index继续增加
            else:  # 当前这个更小
                break # 结束 while 循环 保持原来的res
        index = 0  # 恢复 index 为0
    return tmp[::-1]

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class TestFunc(unittest.TestCase):
    def test_func(self):
        inputs = [
            ["Tom", "Lucy", "Tommy"],  # 功能测试
            ["sfs", "wevvs", "12343"],
            []  # 特判
        ]
        answers = [
            ["Lucy", "Tom", "Tommy"],
            ['12343', 'sfs', 'wevvs'],
            []
        ]
        res = []
        for i in range(len(inputs)):
            try:
                res.append(stringSorted(inputs[i]))
            except Exception:
                res.append("ValueError")
        self.assertEqual(res, answers)

if __name__ == "__main__":
    unittest.main()

String to Int32

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
def string2int32(_str: str) -> int:
    """convert str to int
    :param _str: str
    :return int:
    """
    # 输入类型检查
    if not isinstance(_str, str): raise ValueError
    # 长度特判
    if len(_str) == 0:  raise ValueError
    flag = True  # 默认为正数
    ord_0 = ord('0')
    ord_9 = ord('9')

    # 输入数据检测
    if _str[0] == '-':
        _str = _str[1:]
        flag = False
    for _char in _str:
        tmp = ord(_char)
        if tmp < ord_0  or tmp > ord_9:
            raise ValueError

    # string to int
    res = 0
    count = 0
    is_valid = True
    for item in _str[::-1]:
        is_valid = True
        # 做溢出判断  -2147483648 < int32 < 2147483647
        # 负数溢出判定 or 正数溢出判定
        tmp = (ord(item) - ord_0) * (10**count)
        if (not flag and res < 147483648 and tmp <= 2000000000) or (flag and res < 147483647 and tmp <= 2000000000):
            pass  # 满足条件，不做处理。
        else:
            is_valid = False

        if is_valid:
            res += tmp
            count += 1
        else:
            raise ValueError

    return res if flag else (0-res)

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import unittest

class TestFunc(unittest.TestCase):
    def test_func(self):
        inputs = [
            "520", "666", "-120", "1", "-3",            # 功能测试
            "2147483646", "-2147483647", "-2147483650",  # 边界测试 -2147483648 < int32 < 2147483647
            "0", "asdf"                                # 特殊样例
        ]
        answers = [520, 666, -120, 1, -3, 2147483646, -2147483647, "ValueError", 0, "ValueError"]
        res = []
        for i in range(len(inputs)):
            try:
                res.append(string2int(inputs[i]))
            except Exception:
                res.append("ValueError")
        self.assertEqual(res, answers)

if __name__ == "__main__":
    unittest.main()

Int32 to String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def int2string(_int: int) -> str:
    # 输入类型检查
    if not isinstance(_int, int): raise ValueError
    # 输入0特判
    if _int == 0:  return "0"
    # 正负数检查
    flag = True
    if _int < 0:
        _int = 0 - _int
        flag = False
    res = ""
    hash_map = {0: "0", 1:   "1", 2: "2", 3: "3", 4: "4", 5: "5", 6: "6", 7: "7", 8: "8", 9: "9"}
    while _int:
        res = hash_map[_int % 10] + res
        _int //= 10
    return res if flag else "-" + res

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class TestFunc(unittest.TestCase):
    def test_func(self):
        inputs = [520, 666, -120, 1, -3, 2147483646, -2147483647,  0, "123"]
        answers = [
            "520", "666", "-120", "1", "-3",  # 功能测试
            "2147483646", "-2147483647",      # 边界测试 -2147483648 < int32 < 2147483647
            "0", "ValueError"                 # 特殊样例
        ]
        res = []
        for i in range(len(inputs)):
            try:
                res.append(int2string(inputs[i]))
            except Exception:
                res.append("ValueError")
        self.assertEqual(res, answers)

if __name__ == "__main__":
    unittest.main()

哈希表

Take List As Hash Map

以 list 作为 hash map，适用于 key 为字符的情况，这时可以用一个长度为 256 的 list 作为 hash map，list 的第 i 个元素代表 chr(i) 这个字符作为 key 所对应的 value。具体应用可以参考剑指offer 面试题50. 第一个只出现一次的字符（易）。

List to Hash map

输入带重复的list转化成hash map

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def func(self, inputs):
        res = {}
        for input in inputs:
            if key in res:
                res[key].append(input)
            else:
                res[key] = [input]
        return res

    def hashMapFunc(self, key):
        # 构建value-key关系
        return _dict[key]

其他基础代码实现

10进制转2、8、16进制

系统实现

1
2
3
4
5
6
>>> bin(160)
'0b10100000'
>>> oct(160)
'0o240'
>>> hex(160)
'0xa0'

手动实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def scale_Convert(number, base):
    prefix = {2: "0b", 8: "0o", 16: "0x"}
    hash_map = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f']
    b = []
    while True:
        s = number // base
        y = number % base
        b = b + [y]
        if s == 0:
           break
        number = s
    b.reverse()
    b = [str(hash_map[i]) for i in b]
    return prefix[base] + "".join(b)

输出

1
2
3
4
5
6
7
8
9
>>> res = scale_Convert(160, 2)
>>> res
'0b10100000'
>>> res = scale_Convert(160, 8)
>>> res
'0o240'
>>> res = scale_Convert(160, 16)
>>> res
'0xa0'

其他

2进制 8进制 10进制 16进制
2进制 - bin(int(n,8)) bin(int(n,10)) bin(int(n,16))
8进制 oct(int(n,2)) - oct(int(n,10)) oct(int(n,16))
10进制 int(n,2) int(n,8) - int(n,16)
16进制 hex(int(n,2)) hex(int(n,8)) hex(int(n,10)) -

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 2进制转8进制，先将2进制转成10进制，再将其10进制形式转换成8进制
>>> a = int('0b10100000', 2)
>>> a
160
>>> oct(a)
'0o240'
# 一次性完成
>>> oct(int('0b10100000', 2))
'0o240'

# 8进制转16进制，先将8进制转成10进制，再将其10进制形式转换成16进制
>>> a = int('0o240', 8)
>>> a
160
>>> hex(a)
'0xa0'
# 一次性完成
>>> hex(int('0o240', 8))
'0xa0'

举一反三

在微软产品Excel中，用A表示第1列，B表示第2列……Z表示第26列，AA表示第27列，AB表示第28列……以此类推。请写出一个函数，输入用字母表示的列号编码，输出它是第几列。 这是一道很新颖的关于进制的题目，其本质是把十进制数字用A～Z表示成二十六进制。如果想到这一点，那么解决这个问题就不难了。

1
2
3
4
5
6
7
8
9
10
11
12
13
def computeCols(col):
    hash_map = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5, "F": 6, "G": 7, "H": 8, "I": 9, "J": 10, "K": 11, "L": 12, "M": 13, "N": 14, "O": 15, "P": 16, "Q": 17, "R": 18, "S": 19, "T": 20, "U": 21, "V": 22, "W": 23, "X": 24, "Y": 25, "Z": 26}
    
    count = 0
    res = 0
    for char in col[::-1]:
        tmp = (26 ** count) * hash_map[char]
        res += tmp
        count += 1
    return res

if __name__ == "__main__":
    print(computeCols("AD"))

关键思想总结

相关题目总结

LeetCode 36. 有效的数独（中）

直觉

所谓合格的数独，本质就是一个判定是否存在重复的问题。这就可以通过创建 rows、column、boxes三种哈希表保存每个数字的出现情况，进而实现对重复是否存在的判定了。

  • 遍历数独。
  • 检查看到每个单元格值是否已经在当前的行 / 列 / 子数独中出现过：
    • 如果出现重复，返回 false。
    • 如果没有，则保留此值以进行进一步跟踪。
  • 返回 true。

关键代码

1
2
3
4
5
6
7
8
9
10
11
rows = [{} for i in range(9)]
columns = [{} for i in range(9)]
boxes = [{} for i in range(9)]

box_index = (i // 3 ) * 3 + j // 3  # 获取当前格子所在的 3x3 宫
rows[i][num] = rows[i].get(num, 0) + 1  # 行出现次数加一
columns[j][num] = columns[j].get(num, 0) + 1  # 列出现次数加一
boxes[box_index][num] = boxes[box_index].get(num, 0) + 1  # 3x3 宫内出现次数加一
# 如果在行、列、3x3 小格子内，任何一种情况下出现次数超过1，就不是有效数独，返回False
if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
    return False

注意使用 dict.get() 命令来避免判定

1
2
3
4
5
6
7
8
# 不用get就要判定
if num in rows[i]:
	rows[i][num] += 1
else:
	rows[i][num] = 0

# 用了get一行代码
rows[i][num] = rows[i].get(num, 0) + 1

题解

LeetCode 36. 有效的数独（中）

LeetCode 146. LRU缓存机制（中）

直觉

哈希表保存key-value，链表保存使用时间前后关系。新插入或者刚刚访问过的key，放到双向链表最前面，如果新插入时cache容量不够，就删除双向链表最后面的那个节点（最近最久未使用）。

关键代码

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
# 定义双链表节点
class DLinkedNode():
    """bidirectional linked list
    """
    def __init__(self):
        self.key = 0
        self.val = 0
        self.prev = None
        self.next = None

# 定义LRU Cache类，有添加节点、删除节点、移动到链表开头、移动到链表结尾、删除链表尾结点、初始化、get函数 
class LRUCache():

    def __init__(self, capacity):
        self.cache = {}  # hash map负责保存DLinkedNode，双向链表负责保存使用时间。
        self.size = 0  # 保存当前已经存储的缓存数量
        self.capacity = capacity  # 保存该LRUCache能够保存的最多缓存数量
        self.head, self.tail = DLinkedNode(), DLinkedNode()  # head和tail起哑节点的作用
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        """get node which with the certain key
        """
        node = self.cache.get(key, None)
        if not node:
            return -1
        self.moveToHead(node)  # 只要访问过 就放到最前面
        return node.val

    def put(self, key, value):
        """put value into the node which with the certain key
        """
        node = self.cache.get(key)
        
        if not node:  # 新节点放到最前面
            newNode = DLinkedNode()
            newNode.key = key
            newNode.val = value
            self.cache[key] = newNode
            self.addNode(newNode)
            self.size += 1

            if self.size > self.capacity:
                tail = self.popTailNode()
                del self.cache[tail.key]
                self.size -= 1
        else:  # 之前已经存在的节点
            node.val = value
            self.moveToHead(node)

题解

LeetCode 146. LRU缓存机制（中）

算法与数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！