python算法口诀_左神算法初级4 python实现

桃扇骨 2022-11-05 13:51 91阅读 0赞

初级4的题目相关代码：

1、转圈打印矩阵

\#转圈打印矩阵(二维数组), 比如a矩阵

\# \[\[ 1 2 3\]

\# \[ 4 5 6\]

\# \[ 7 8 9\]

\# \[10 11 12\]\]

\# 打印后为1 2 3 6 9 12 11 10 7 4 5 8

\#采用宏观调度的思想，从外向内分层打印矩阵，根据每一层的左上角和右下角位置即可按顺序打印出该层

import numpy as np

def spiralorderprint(amatrix):

n = amatrix.shape\[0\]

m = amatrix.shape\[1\]

a = 0

b = 0

c = n-1

d = m-1

while a<=c and b<=d:

print\_circle(amatrix, a, b, c, d)

a = a + 1

b = b + 1

c = c - 1

d = d - 1

def print\_circle(amatrix, a, b, c, d):

\#每一层左上角的坐标为(a, b), 右下角的坐标为(c, d)

if a == c:

for i in range(b, d+1):

print(amatrix\[a, i\], end=' ')

elif b == d:

for i in range(a, c+1):

print(amatrix\[i, b\], end=' ')

else:

for i in range(b, d):

print(amatrix\[a, i\], end=' ')

for i in range(a, c):

print(amatrix\[i, d\], end=' ')

for i in range(d, b, -1):

print(amatrix\[c, i\], end=' ')

for i in range(c, a, -1):

print(amatrix\[i, b\], end=' ')

\# a = np.array(\[\[1,2,3\], \[4,5,6\], \[7,8,9\], \[10,11,12\]\])

\# spiralorderprint(a)

b = np.array(\[\[1,2,3,4\], \[5,6,7,8\], \[9,10,11,12\], \[13,14,15,16\]\])

spiralorderprint(b)

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

2、正方形矩阵顺时针旋转90°

\#正方形矩阵顺时针旋转90°

\# \[\[ 1 2 3\]

\# \[ 4 5 6\]

\# \[ 7 8 9\]\]

\# 旋转后为

\# \[\[ 7 4 1\]

\# \[ 8 5 2\]

\# \[ 9 6 3\]\]

\#采用宏观调度的思想，从外向内分层旋转矩阵

import numpy as np

def rotate(amatrix):

n = amatrix.shape\[0\]

a = 0

b = 0

c = n - 1

d = n - 1

while a

rotateedge(amatrix, a, b, c, d)

a = a + 1

b = b + 1

c = c - 1

d = d - 1

def rotateedge(amatrix, a, b, c, d):

for i in range(0, d-b):

tmp = amatrix\[a, b+i\]

amatrix\[a, b+i\] = amatrix\[c-i, b\]

amatrix\[c - i, b\] = amatrix\[c, d-i\]

amatrix\[c, d - i\] = amatrix\[a+i, d\]

amatrix\[a + i, d\] = tmp

a = np.array(\[\[1,2,3\], \[4,5,6\], \[7,8,9\]\])

rotate(a)

print(a)

\[\[7 4 1\]

\[8 5 2\]

\[9 6 3\]\]

3、反转单向和双向链表:

分别实现反转单向链表和反转双向链表的函数，如果链表长度为N，时间复杂度要求为O(N)，空间复杂度要求为O(1)。

\#定义单链表

class listnode:

def \_\_init\_\_(self, x):

self.data = x \#节点的数据域

self.next = None \#节点的指针域，指向下一个节点

\#链表反转

def reverselist(head):

if head==None or head.next==None:

return head

cur = head

pre = None

while cur:

next\_node = cur.next

cur.next = pre \#反转

pre = cur \#pre右移

cur = next\_node \#cur右移

\#测试用例

\#5->3->2->1->9->null

\#9->1->2->3->5->null

n1 = listnode(5)

n2 = listnode(3)

n3 = listnode(2)

n4 = listnode(1)

n5 = listnode(9)

n1.next = n2

n2.next = n3

n3.next = n4

n4.next = n5

print(n1.data, n1.next.data, n1.next.next.data, n1.next.next.next.data, n1.next.next.next.next.data)

reverselist(n1)

print(n5.data, n5.next.data, n5.next.next.data, n5.next.next.next.data, n5.next.next.next.next.data)

5 3 2 1 9

9 1 2 3 5

\#定义双向链表

class listnode:

def \_\_init\_\_(self, x):

self.data = x \#节点的数据域

self.prev = None \#节点的指针域，指向上一个节点

self.next = None \#节点的指针域，指向下一个节点

\#链表反转

def reverselist(head):

if head==None:

return head

if head.next==None and head.prev==None:

return head

cur = head

while cur:

next\_node = cur.next

cur.next = cur.prev

cur.prev = next\_node

cur = next\_node

\#测试用例

n1 = listnode(5)

n2 = listnode(3)

n3 = listnode(2)

n4 = listnode(1)

n5 = listnode(9)

n1.prev = None

n1.next = n2

n2.prev = n1

n2.next = n3

n3.prev = n2

n3.next = n4

n4.prev = n3

n4.next = n5

n5.prev = n4

n5.next = None

print(n1.data, n1.next.data, n1.next.next.data, n1.next.next.next.data, n1.next.next.next.next.data)

reverselist(n1)

print(n5.data, n5.next.data, n5.next.next.data, n5.next.next.next.data, n5.next.next.next.next.data)

5 3 2 1 9

9 1 2 3 5

4、“之”字形打印矩阵

\#之字形打印矩阵,也是宏观调度问题，需要找到对角线的两端并依次打印

\# \[\[ 1 2 3\]

\# \[ 4 5 6\]

\# \[ 7 8 9\]

\# \[10 11 12\]\]

\#打印后为1 2 4 7 5 3 6 8 10 11 9 12

import numpy as np

def print\_z\_matrix(amatrix):

n = amatrix.shape\[0\]

m = amatrix.shape\[1\]

ar = 0

ac = 0

br = 0

bc = 0

fromup = False \#打印方向是从上往下为True,从下往上为False

while ar!=n-1:

print\_level(amatrix, ar, ac, br, bc, fromup)

if ac

ac=ac+1

else:

ar=ar+1

if br

br=br+1

else:

bc=bc+1

fromup = not(fromup)

print(amatrix\[ar, ac\])

def print\_level(amatrix, ar, ac, br, bc, fromup):

if fromup==True:

while ac>=bc:

print(amatrix\[ar, ac\], end=' ')

ar=ar+1

ac=ac-1

else:

while bc<=ac:

print(amatrix\[br, bc\], end=' ')

br=br-1

bc=bc+1

a = np.array(\[\[1,2,3\], \[4,5,6\], \[7,8,9\], \[10,11,12\]\])

print\_z\_matrix(a)

1 2 4 7 5 3 6 8 10 11 9 12

5、在行列都排好序的矩阵中找数

\#在行和列都排好序的矩阵中找数，存在则返回true，不存在则返回false

import numpy as np

def findnum(amatrix, num):

n = amatrix.shape\[0\]

m = amatrix.shape\[1\]

ar=0

ac=m-1

while ar<=n-1 and ac>=0:

if amatrix\[ar, ac\]>num:

ac = ac-1

elif amatrix\[ar, ac\]

ar = ar+1

else:

return True

return False

b = np.array(\[\[1,2,3,4\], \[5,6,7,8\], \[9,10,11,12\], \[13,14,15,16\]\])

num = 20

print(findnum(b, num))

num = 5

print(findnum(b, num))

False

True

6、打印两个有序链表的公共部分

\#给定两个有序链表的头指针head1和head2, 打印两个链表的公共部分(定义两个指针，类似外排方式)

\#定义单链表

class listnode:

def \_\_init\_\_(self, x):

self.data = x \#节点的数据域

self.next = None \#节点的指针域，指向下一个节点

def printtwolist(head1, head2):

cur1 = head1

cur2 = head2

while cur1!=None and cur2!=None:

if cur1.data < cur2.data:

nex = cur1.next

cur1 = nex

elif cur1.data == cur2.data:

print(cur1.data, end=' ')

nex = cur2.next

cur2 = nex

else:

nex = cur2.next

cur2 = nex

head1 = listnode(1)

head1.next=listnode(5)

head1.next.next = listnode(7)

head1.next.next.next = listnode(9)

head2 = listnode(2)

head2.next = listnode(3)

head2.next.next = listnode(5)

head2.next.next.next = listnode(7)

printtwolist(head1, head2)

5 7

7、判断一个链表是否为回文结构

\#给定一个链表的头节点head,判断该链表是否是回文结构(逆序后和原始一样;存在一个对称轴，左右两边对称)

\#定义单链表

class listnode:

def \_\_init\_\_(self, x):

self.data = x \#节点的数据域

self.next = None \#节点的指针域，指向下一个节点

def ispalindrome(head):

if head==None or head.next == None:

return True

cur = head

stack=\[\]

while cur!=None:

stack.append(cur)

cur = cur.next

cur = head

while cur!=None:

if cur.data == stack.pop().data:

cur = cur.next

else:

return False

return True

head1 = listnode(1)

head1.next = listnode(5)

head1.next.next = listnode(5)

head1.next.next.next = listnode(1)

print(ispalindrome(head1))

8、将单向链表按某值划分成左边小、中间相等、右边大的形式

\#将单向链表按某值划分成左边小、中间相等、右边大的形式

\#定义单链表

class listnode:

def \_\_init\_\_(self, x):

self.data = x \#节点的数据域

self.next = None \#节点的指针域，指向下一个节点

\#普通版(荷兰国旗问题，把链表中的每个节点依次放入数组中)

def partitionlist1(head, pivot):

if head==None or head.next ==None:

return head

help\_list = \[\]

cur = head

while cur!=None:

help\_list.append(cur)

cur = cur.next

less = -1

curr = 0

more = len(help\_list)

while curr

if help\_list\[curr\].data < pivot:

tmp = help\_list\[less +1\]

help\_list\[less + 1\] = help\_list\[curr\]

help\_list\[curr\] = tmp

less = less + 1

curr = curr + 1

elif help\_list\[curr\].data > pivot:

tmp = help\_list\[more-1\]

help\_list\[more-1\] = help\_list\[curr\]

help\_list\[curr\] = tmp

more = more - 1

else:

curr = curr + 1

new\_head = help\_list\[0\]

p = new\_head

for i in range(1, len(help\_list)):

p.next = help\_list\[i\]

p = p.next

p.next = None

return new\_head

\# \#进阶版(保证顺序相同), 将less、equal、more三个链表重新串起来

def partitionlist2(head, pivot):

if head==None or head.next ==None:

return head

less\_start = less\_end = None

equal\_start = equal\_end = None

more\_start = more\_end = None

cur = head

while cur!=None:

if cur.data < pivot:

if less\_start ==None:

less\_start = less\_end = cur

cur = cur.next

else:

less\_end.next = cur

less\_end = cur

cur = cur.next

elif cur.data == pivot:

if equal\_start ==None:

equal\_start = equal\_end = cur

cur = cur.next

else:

equal\_end.next = cur

equal\_end = cur

cur = cur.next

else:

if more\_start == None:

more\_start = more\_end = cur

cur = cur.next

else:

more\_end.next = cur

more\_end = cur

cur = cur.next

\#7种情况

if less\_start!=None and equal\_start!=None and more\_start!=None:

new\_head = less\_start

less\_end.next = equal\_start

equal\_end.next = more\_start

more\_end.next = None

elif less\_start!=None and equal\_start!=None and more\_start==None:

new\_head = less\_start

less\_end.next = equal\_start

equal\_end.next = None

elif less\_start!=None and equal\_start==None and more\_start==None:

new\_head = less\_start

less\_end.next = None

elif less\_start != None and equal\_start == None and more\_start != None:

new\_head = less\_start

less\_end.next = more\_start

more\_end.next = None

elif less\_start==None and equal\_start!=None and more\_start!=None:

new\_head = equal\_start

equal\_end.next = more\_start

more\_end.next = None

elif less\_start==None and equal\_start!=None and more\_start==None:

new\_head = equal\_start

equal\_end.next = None

elif less\_start==None and equal\_start==None and more\_start!=None:

new\_head = more\_start

more\_end.next = None

return new\_head

9、复制含有随机指针节点的链表

\#复制含有随机指针节点的链表

class randomlistnode:

def \_\_init\_\_(self, x):

self.data = x \#节点的数据域

self.next = None \#节点的指针域，指向下一个节点

self.rand = None

def copylist(head):

if head == None:

return head

\#将复制的节点插入原节点后面

cur = head

while cur!=None:

next\_node = cur.next

copynode = randomlistnode(cur.data)

cur.next = copynode

copynode.next = next\_node

cur = next\_node

\#设置好每一个复制节点的rand指针

cur = head

while cur!=None:

next\_node = cur.next.next

copynode = cur.next

if cur.rand==None:

copynode.rand = None

else:

copynode.rand =cur.rand.next

cur = next\_node

\#分离原节点与复制节点

cur = head

new\_head = head.next

p = new\_head

while p.next!=None:

next\_node = cur.next.next

p.next = next\_node.next

p = p.next

cur.next = next\_node

cur = next\_node

cur.next = None

return new\_head

l1=randomlistnode(1)

l2=randomlistnode(5)

l3=randomlistnode(9)

l1.next=l2

l2.next=l3

l1.rand=None

l2.rand=l1

l3.rand=l2

print(l2.rand.data, l3.rand.data)

new\_head = copylist(l1)

10、两个单链表相交的一系列问题

\#两个单链表相交的一系列问题：首先判断这两个单链表是否有环；如果都无环，则为无环单链表相交问题;一个有环一个无环直接返回None；

\#两个均有环，则根据第一个入环节点loop1和loop2的值分情况计算

\#定义单链表

class listnode:

def \_\_init\_\_(self, x):

self.data = x \#节点的数据域

self.next = None \#节点的指针域，指向下一个节点

def intersect(head1, head2):

loop1 = getloopnode(head1)

loop2 = getloopnode(head2)

if loop1 == None and loop2 == None:

noloop(head1, head2)

elif loop1!=None and loop2!=None:

bothloop(head1, loop1, head2, loo2)

else:

return None

def getloopnode(head):

if head == None or head.next==None or head.next.next ==None:

return None

fast = head.next.next

slow = head.next

while fast != slow:

if fast.next==None or fast.next.next==None:

return None

fast = fast.next.next

slow = slow.next

fast = head

while fast!=slow:

fast = fast.next

slow = slow.next

return fast

def noloop(head1, head2):

cur = head1

i = 1

while cur.next!=None:

cur = cur.next

i = i + 1

end1 = cur

len1 = i

cur = head2

i = 1

while cur.next != None:

cur = cur.next

i = i + 1

end2 = cur

len2 = i

if end1!=end2:

return None

cur1 = head1

cur2 = head2

if len1 > len2:

for i in range(len1-len2):

cur1 = cur1.next

elif len2 > len1:

for i in range(len2-len1):

cur2 = cur2.next

while cur1!=cur2:

cur1=cur1.next

cur2=cur2.next

return cur1

def bothloop(head1, loop1, head2, loop2):

if loop1 == loop2:

cur = head1

i = 1

while cur!= loop1:

cur = cur.next

i = i + 1

end1 = cur

len1 = i

cur = head2

i = 1

while cur!= loop2:

cur = cur.next

i = i + 1

end2 = cur

len2 = i

if end1 != end2:

return None

cur1 = head1

cur2 = head2

if len1 > len2:

for i in range(len1 - len2):

cur1 = cur1.next

elif len2 > len1:

for i in range(len2 - len1):

cur2 = cur2.next

while cur1 != cur2:

cur1 = cur1.next

cur2 = cur2.next

return cur1

else:

cur = loop1.next

while cur!=loop1:

if cur == loop2:

return loop1

cur = cur.next

return None

python算法口诀_左神算法初级4 python实现

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 python算法口诀_左神算法初级4 python实现

相关左神算法进阶班3_4网易题——烽火传递

相关左神算法：加强堆的实现（Java）

相关 python-初级

相关 Leetcode初级算法打家劫舍（动态规划）（Python实现）

相关【搞定左神算法初级班】第7节：暴力递归、动态规划

相关【搞定左神算法初级班】第4节：二叉树及相关常见面试题

相关【搞定左神算法初级班】第6节：前缀树、贪心算法

相关左神算法进阶班1_4Manacher算法