数据结构与算法-数组相关

发表于 | 分类于
| 字数统计: 2.1k 字

本篇介绍数组相关的基础题目。

题目一

用数组结构实现大小固定的队列和栈。（难度相当于一面的第一题）

实现栈

  • index指向的是 新来的数要添加的位置。
  • size 指的是固定的长度。

代码：

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
# 用数组结构实现大小固定的队列和栈。（难度相当于一面的第一题）
class ArrayStack(object):
    '''
    固定数组实现栈
    '''

    def __init__(self, initsize):
        # initsize 为空间的大小
        if initsize < 0:
            raise Exception('The init size is less than 0')
        self.arr = [None] * initsize
        self.index = 0  # 当前的指向
        self.size = initsize

    def push(self, val):
        if self.index == self.size:
            # 满了
            raise Exception('The stack is full')
        self.arr[self.index] = val
        self.index += 1

    def pop(self):
        if self.index == 0:
            # 空了
            raise Exception('The stack is empty')
        self.index -= 1
        return self.arr[self.index]

    @property
    def top(self):
        # 查看栈顶
        if self.index == 0:
            # 空了
            raise Exception('The stack is empty')
        return self.arr[self.index - 1]


s1 = ArrayStack(1)
s1.push(1)
print(s1.top)
# s1.push(1)

实现队列

循环利用这个数组

  • start 变量指的是 拿取数据的位置。
  • end 变量指的是 新来的数要添加的位置。
  • size 指的已有元素的个数。

三个变量之间的关系：

  • start与end没有关系。
  • start与size有关：如果size不等于0，总把start位置处的数据取出来。
  • end与size有关：如果size没超最大值，总把新来的数据放到end。

引入size的好处：

  • start与end没有关系，所以不容易判断，何时追上了（满），何时为空，实现start 与 end 的解码。
  • 有了size，加一个数，拿走一个数仅有size控制，简单很多。

实现：

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
# 用数组结构实现大小固定的队列和栈。（难度相当于一面的第一题）
class ArrayQueue(object):
    '''
    固定数组实现队列
    '''

    def __init__(self,initsize):
        if initsize < 0:
            raise Exception('The init size is less than 0')
        self.arr = [None] * initsize
        self.size = 0
        self.start = 0
        self.end = 0

    def push(self,val):
        if self.size ==len(self.arr):
            # 满了
            raise Exception('The queue is full')
        self.size += 1
        self.arr[self.end] = val
        self.end = 0 if self.end == len(self.arr) - 1 else self.end + 1

    def poll(self):
        if self.size == 0:
            # 队列为空
            raise Exception('The queue is empty')
        self.size -= 1
        ret = self.arr[self.start]
        # 到达列表末尾就重新回到列表开头
        self.start = 0 if self.start == len(self.arr) - 1 else self.start + 1
        return ret

    @property
    def top(self):
        if self.size == 0:
            return
        return self.arr[self.start]



a = ArrayQueue(3)
a.push(1)
a.push(2)
a.push(3)
print(a.poll())
print(a.poll())
print(a.poll())
a.push(2)
a.push(3)
a.push(34)
print(a.poll())
print(a.poll())
print(a.poll())

题目二

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。（年年都考）

要求：

  1. pop、push、getMin操作的时间复杂度都是O(1)。
  2. 设计的栈类型可以使用现成的栈结构。

思路：

  • 使用两个栈，data栈保存数据，min栈栈顶保存最小值，如果压入的数据比栈顶数据大，则将栈顶数据复制并压入；如果压入的数据比栈顶数据小，就把该数压入。
  • 在弹出数据的时候同步弹出就行。

理解：

  • data栈顶保存的是最新添加进入的数字，min栈的栈顶保存的是最新的这个数字与底下的数据进行比较后选出的较小值。这样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
class ArrayStack(object):
    def __init__(self):
        self.data = []
        self.mins = []

    def push(self, val):
        self.data.append(val)

        if len(self.mins) == 0 :
            self.mins.append(val)
        else:
            if self.mins[-1] <= val:
                self.mins.append(self.mins[-1])
            else:
                self.mins.append(val)


    def pop(self):
        if len(self.data) == 0:
            return
        self.mins.pop()
        return self.data.pop()

    def get_min(self):
        if len(self.mins) == 0:
            return
        # mins栈顶元素，为最小值
        return self.mins[-1]

a = ArrayStack()
a.push(5)
a.push(2)
a.push(3)
print(a.get_min())  # 2
print(a.pop())  	# 3
print(a.get_min())	# 2

题目三

场景：图的深度优先遍历，通常使用栈来实现的，如果面试官让你使用队列呢？

  • 实际上就是先用队列实现了栈，然后用这个栈来实现图的深度优先遍历。

队列实现栈

  • 准备两个队列，一个队列中放入值
  • pop时，先将 n-1 个值移动到另一个队列中，然后poll出最后这个值就可以。
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
from queue import Queue


class TwoQueueStack(object):
    '''两个队列实现一个栈'''

    def __init__(self):
        self.data = Queue()
        self.help = Queue()

    def push(self, val):
        self.data.put(val)

    def pop(self):
        if self.data.empty():
            raise Exception('Stack is empty')
        while self.data.qsize() > 1:
            self.help.put(self.data.get())
        res = self.data.get()
        self.data, self.help = self.help, self.data
        return res

    @property
    def top(self):
        if self.data.empty():
            raise Exception('Stack is empty')
        while self.data.qsize() > 1:
            self.help.put(self.data.get())
        res = self.data.get()
        self.help.put(res)
        self.data, self.help = self.help, self.data
        return res

t = TwoQueueStack()
t.push(5)
t.push(4)
t.push(3)
print(t.top) 	# 3
print(t.pop())	# 3
print(t.pop())	# 4

栈实现队列

  • 准备两个栈,push栈，pop栈
  • push栈中存数据，pop栈中取数据
  • 如果要pop数据，需要将push栈中所有数据都放入pop栈；
  • 如果pop数据时，pop栈不为空，则push栈中的数据不能放入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
from queue import LifoQueue
class TwoStackQueue(object):
    def __init__(self):
        self.stack_push = LifoQueue()
        self.stack_pop = LifoQueue()

    def push(self,val):
        self.stack_push.put(val)
        self.dao()

    def poll(self):
        if (self.stack_push.empty() and self.stack_pop.empty()):
            raise Exception('Queue is empty!')
        self.dao()
        return self.stack_pop.get(block=False)

    def dao(self):
        '''将push栈中的数据 到 在pop栈中'''
        if not self.stack_pop.empty():
            return
        while not self.stack_push.empty():
            self.stack_pop.put(self.stack_push.get(block=False))

t = TwoStackQueue()
t.push(1)
t.push(2)
t.push(3)
print(t.poll())
print(t.poll())
print(t.poll())

题目四

猫狗队列

宠物、狗和猫的类如下：

1
2
3
4
5
class Pet(object):
	def __init__(self,types):
		self.types = types
	def get_pet_type(self):
		return self.types

实现一种猫狗队列的结构，要求如下：用户可以调用add方法将cat类或dog类的实例放入队列；用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；用户可以调用isEmpty方法，检查队列中是否有dog类的实例；用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。

题目五

转圈打印矩阵

宏观调度问题

给定一个整型矩阵matrix，请按照转圈的方式打印它。

例如：

1
2
3
4
5
6
7
1 ->	2 -> 	3 ->   	4 
					   ↓
5  	->	6 	->	 7		8 
↑				↓	   ↓
9 		10 	<-	11 	    12 
↑					   ↓
13 	<-	14 	<-	15 	<-	16

打印结果为：1，2，3，4，8，12，16，15，14，13，9，5，6，7，11，10

要求：额外空间复杂度为O(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
def spiral_order_print(m):
    tr, tc = 0, 0
    dr, dc = len(m) - 1, len(m[0]) - 1
    while tr <= dr and tc <= dc:
        print_edge(m, tr, tc, dr, dc)
        # 打印完一圈后，左上角的点向右下角移动，右下角的点向左上角移动。
        tr += 1
        tc += 1
        dr -= 1
        dc -= 1


def print_edge(m, tr, tc, dr, dc):
    '''
    打印矩形上的值
    :param tr: 左上角的行
    :param tc: 左上角的列
    :param dr: 右下角的行
    :param dc: 右下角的列
    '''
    if tr == dr:
        # 只有一行
        for i in range(tc, dc + 1):
            print(m[tr][i])
    elif tc == dc:
        # 只有一列
        for i in range(tr, dr + 1):
            print(m[i][tc])
    else:
        cur_c = tc
        cur_r = tr
        while cur_c != dc:
            print(m[cur_r][cur_c])
            cur_c += 1
        while cur_r != dr:
            print(m[cur_r][cur_c])
            cur_r += 1
        while cur_c != tc:
            print(m[cur_r][cur_c])
            cur_c -= 1
        while cur_r != tr:
            print(m[cur_r][cur_c])
            cur_r -= 1


li = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]
spiral_order_print(li)

题目六

矩阵旋转

宏观调度问题

扩展为一个N*N的正方形，顺时针旋转90度。要求：额外空间复杂度为O(1)

1
2
3
4
5
6
7
1	2	3
4	5	6
7	8	9
↓
7	4	1
8	5	2
9	6	3

思路：

  • 同上面的转圈，只要能把一圈做好，剩下就是一个缩小规模，重复调用的过程。
  • 对于一圈中的所有元素，4个角要交换位置。

代码：

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
def rotate(m):
    tr = tc = 0
    dr = dc = len(m) - 1
    while tr < dr:
        rotate_edge(m, tr, tc, dr, dc)
        tr += 1
        tc += 1
        dr -= 1
        dc -= 1


def rotate_edge(m, tr, tc, dr, dc):
    # 处理一个正方形
    times = dc - tc
    tmp = 0
    for i in range(times):
        tmp = m[tr][tc + i]  # 取出左上角
        m[tr][tc + i] = m[dr - i][tc]  # 覆盖左上角
        m[dr - i][tc] = m[dr][dc - i]  # 覆盖左下角
        m[dr][dc - i] = m[tr + i][dc]  # 覆盖右下角
        m[tr + i][dc] = tmp			  # 覆盖左上角	


li = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
rotate(li)
print(li)

持续更新中！！！

-------------The End-------------

本文标题:数据结构与算法-数组相关

文章作者:Naqin

发布时间:2019年12月26日 - 13:12

最后更新:2020年02月24日 - 22:02

原始链接:https://chennq.top/数据结构/20191226-data-struct-array.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Naqin wechat
欢迎看官加我微信！
坚持原创技术分享，您的支持将鼓励我继续创作！
0%