算法工程师14.1——力扣刷题基本题

1 栈、队列

1.1 栈的实现

class Stack:
    def __init__(self):
        self.items = []

    def isEMpty(self):
        return self.items == []

    def push(self,item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()   # 删除最后一个元素

    def peek(self):
        return self.items[len(self.items)-1] # 产看栈顶元素

    def size(self):
        return len(self.items)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.2 队列的实现

class Queue:
    def __init__(self):
        self.items = []

    def isEMpty(self):
        return self.items == []

    def push(self,item):
        self.items.append(item)

    def pop(self):
        return self.items.pop(0)   # 出队列

    def peek(self):
        return self.items[0] # 产看栈顶元素

    def size(self):
        return len(self.items)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.3 双向队列

class TwoQueue:
    def __init__(self):
        self.items = []

    def isEMpty(self):
        return self.items == []

    def push(self,item):
        self.items.append(item)

    def headpush(self,item):
        self.items.insert(0,item)

    def pop(self):
        return self.items.pop(0)   # 出队列

    def tailpop(self):
        return self.items.pop()

    def peek(self):
        return self.items[0] # 产看栈顶元素

    def size(self):
        return len(self.items)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.4 简单括号匹配

核心思想是遇到左括号就加到列表里，遇到右括号就看遇前面的第一个左括号是否匹配，匹配则移除左括号，不匹配说明括号不匹配

def matches(open,close):
    opens = "([{"
    closes = ")]}"
    return opens.index(open) == closes.index(close)

def parCheck(synbolString):
    balanced = True
    index = 0
    list_stack = []
    while index<len(synbolString) and balanced:
        symbol = synbolString[index]
        if symbol in "([{":
            list_stack.append(symbol)
        elif symbol in ")]}":
            if matches(list_stack[-1],symbol):
                list_stack.pop()
            else:
                balanced = False
        else:
            return None

        #print(index,balanced,symbol)

        index +=1
    if len(list_stack) != 0:
        balanced = False

    return balanced


if __name__ == '__main__':
    str = "{{([][])}()}"
    str = "{{([][])}()"
    str = "{([][])}()"
    print(parCheck(str))
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

1.5 十进制转换

一直除，直到值为0，每次剩下的余数越往后越处于高位，将余数排列好就行，栈的思想
核心思想就是除以进制数，得到余数，余数从后往前排列

def baseCov(decnumeber,base):
    digits = "0123456789ABCDEF"
    value = []
    while decnumeber > 0:
        yushu = decnumeber%base
        print(yushu,digits[yushu])
        value.append(digits[yushu])
        decnumeber = decnumeber//base

    result = ""
    index = len(value)-1
    while index>=0:
        result = result+value[index]
        index -=1
    return result


if __name__ == '__main__':
    num = 1293
    print(baseCov(num,16))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.6 表达式转换（未完成）

1.7 后缀表达式求值

2 链表

数据项和存放位置没有直接联系，依靠前后项的指引而链接
理解链表最重要的是知道浅拷贝，下面的图片案例展示的一清二楚
链表的实现需要
两个类，链表类和节点类，只用一个节点类也可以
各种方法操作时都需注意头节点特殊对待

2.1 单向链表(节点和链表两个class,注意头节点和尾节点)

import os

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

class UnorderedList:
    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def remove(self,item):
        current = self.head
        find = False
        pre  = None
        count = 0
        # 如果链表是空的
        if current == None:
            return False

        # 如果第1个就是
        if current.data == item:
            self.head = self.head.next
            return count

        # 如果没有找到，就继续往下走
        while not find and current!=None:
            if current.data == item:
                find = True
                pre.next = current.next
            else:
                pre = current
                current = current.next
                count +=1

        if find == False:
            return find
        else:
            return count

    def add(self,item):
        temp = Node(item)
        # 先给当前的加上
        temp.next = self.head
        # 再给头节点加上
        self.head = temp

    def size(self):
        num = 0
        current = self.head
        while current!=None:
            current = current.next
            num +=1
        return num

    def search(self,item):
        current = self.head
        find = False
        count = 0
        while not find and current!=None:
            if current.data == item:
                find = True
            else:
                current = current.next
                count +=1
        if find == False:
            return find
        else:
            return count


if __name__ == '__main__':
    lista = UnorderedList()
    lista.add(2)
    lista.add(3)
    lista.add(4)
    lista.add(5)
    current = lista.head
    while current!=None:
        print(current.data)
        current = current.next
    print("个数：",lista.size())
    s = lista.search(33)
    a = lista.remove(2)
    print(s,a)
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

2.2 双向链表的实现

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

class UnorderedList:
    def __init__(self):
        self.head = None

if __name__ == '__main__':
    a = UnorderedList()
1
2
3
4
5
6
7
8
9
10
11
12

3 树

非线性结构典型的递归结构

3.1 树的列表实现

3.2 树的链表实现

一个类

（20）树的三种遍历方式，使用外部函数的方法
（21）树的三种遍历方式，使用类内部函数的方法
（22）二叉堆
（23）二叉查找树
（24）平衡二叉树

4 图

（25）图的实现
（26）词梯问题（最短路径）
（27）骑士周游
（28）广度搜索
（29）深度搜索
（30）最短路径
（31）拓扑排序算法
（32）最小生成树

5 查找排序

（9）顺序查找的while实现
（10）二分查找
（11）二分查找的递归实现

（12）冒泡排序
（13）选择排序
（14）插入排序
（15）希尔排序
（16）归并排序
（17）快速排序

6 递归

6.1

7 动态规划

7.1 动态规划实现博物馆大盗的问题

8 枚举

9 贪心

10 分治

11 最优路径

12 其它

12.1 比较两个单词的组成字符是否一致

12.2 股票问题