## 数组和列表（Python）

Python CSDN 数组 列表

【动态数组】

【合并两个有序数组】

【缺失的第一个正数】

【链表】（单列表）

【环形列表】

【合并两个有序链表】

# 【动态数组】

• ## 编程实现

``````#参考:https://www.cnblogs.com/kumata/p/9098137.html
import ctypes
class DynamicArray:
def __init__(self):#特殊方法
self._n = 0
self._capacity = 10
self._A = self._make_array(self._capacity)
def __len__ (self):
return self._n
def is_empty(self):
return self._n==0
# O(1)
def __getitem__ (self, k):
if k<0 or k>=self._n:
raise Exception("out of index")
return self._A[k]
# O(1)
def append(self, obj):
if self._n == self._capacity:
self._resize(2*self._capacity)
self._A[self._n] = obj
self._n += 1
def _make_array(self, c):
return (c* ctypes.py_object)()
def _resize(self, c):
B = self._make_array(c)
for i in range(self._n):
B[i] = self._A[i]
self._A = B
self._capacity = c
# O(n)
def insert(self, k, value):
if k<0 or k>=self._n:
raise Exception("out index")
if self._n == self._capacity:
self._resize(2*self._capacity)
for i in range(self._n,k,-1):
self._A[i] = self._A[i-1]
self._A[k] = value
self._n +=1
# O(n)
def remove(self, value):
for k in range(self._n):
if self._A[k] == value:
for i in range(k,self._n-1):
self._A[i] = self._A[i+1]
self._A[self._n-1] = None
self._n -= 1
return
def _print(self):
for i in range(self._n):
print self._A[i],' ',
print ''
``````

``````mylist = DynamicArray()
print ('size was: ', str(len(mylist)))
mylist.append(10)
mylist.append(20)
mylist.append(30)
mylist._print()
mylist.insert(0, 0)
mylist.insert(1, 5)
mylist.insert(3, 15)
mylist._print()
mylist.remove(20)
mylist._print()
print ('size is: ', str(len(mylist)))``````

``````('size was: ', '0')
10 20 30
0 5 10 15 20 30
0 5 10 15 30
('size is: ', '5')
``````
• ## 相关类型题：

### 【合并两个有序数组】

``````class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
index = m+n-1
i = m-1
j = n-1
while index>=0:#从末尾开始
if i<0:
nums1[index] = nums2[j]
j -= 1
elif j<0:
nums1[index] = nums1[i]
i -= 1
else:
if nums1[i]>nums2[j]:
nums1[index] = nums1[i]
i -= 1
else:
nums1[index] = nums2[j]
j -= 1
index -= 1``````

### 【缺失的第一个正数】

``````class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
min_num = 1
for i in nums:
if i == min_num:
min_num += 1
elif i>min_num:
return min_num
return min_num``````

# 【链表】（单列表）

• ## 编程实现

``````#先定一个node的类
class Node(): #value + next
def __init__ (self, value = None, next = None):
self._value = value
self._next = next
def getValue(self):
return self._value
def getNext(self):
return self._next
def setValue(self,new_value):
self._value = new_value
def setNext(self,new_next):
self._next = new_next``````

``````#实现Linked List及其各类操作方法
def __init__(self): #初始化链表为空表
self._tail = None
self._length = 0
#检测是否为空
def isEmpty(self):
return self._length == 0
self._length += 1
#append在链表尾部添加元素:O(n)
def append(self,value):
new_node = Node(value,None)
if self._tail == None:
self._tail = new_node
else:
self._tail.setNext(new_node)
self._tail = new_node
self._length += 1
#search检索元素是否在链表中
def search(self,value):
found_value = False
while current != None:
if current.getValue() == value:
found_value = True
break
else:
current = current.getNext()
return found_value
#index索引元素在链表中的位置
def index(self,value):
count =0
found =False
while current !=None:
count +=1
if current.getValue() == value:
found = True
break
current = current.getNext()
if found:
return count
else:
raise Exception("no found")
#remove删除链表中的某项元素
def remove(self,value):
found =False
# if current.getValue() == value:
# self._length -= 1
# return
while current.getNext() !=None:
if current.getNext().getValue() == value:
found = True
current.setNext(current.getNext().getNext())
self._length -= 1
return
current = current.getNext()
if found:
return
else:
raise Exception("no found")
#insert链表中插入元素
def insert(self,pos,value):
if pos>self._length:
raise Exception("out index")
else:
pre = None
for i in range(1,self._length):
pre = current
current = current.getNext()
if pos == i:
new_node = Node(value)
new_node.setNext(current)
pre.setNext(new_node)
self._length += 1
break
#列表反转
def reverse(self):
if self._length == 1:
return
self._tail = Node(value=pre.getValue())
current = pre.getNext()
pre.setNext(None)
while current != None:
next_node = current.getNext()
current.setNext(pre)
pre = current
current = next_node
# next_node = next_node.getNext()
#输出
def _print(self):
if self._length == 0:
return
# print current.getValue()
while current != None:
print '->',current.getValue(),
current = current.getNext()
print ''
``````

``````mylist = LinkedList()
mylist.append(10)
mylist.append(20)
mylist.append(30)
mylist._print()
mylist.insert(1, 5)
mylist.insert(3, 15)
mylist._print()
mylist.remove(20)
mylist._print()``````

``````-> 10 -> 20 -> 30
-> 5 -> 10 -> 15 -> 20 -> 30
-> 5 -> 10 -> 15 -> 30 ``````
• ## 相关类型题：

### 【环形列表】

``````#双指针
class Solution(object):
"""
:rtype: bool
"""
return False
while slow != fast:
if fast==None or fast.next==None:
return False
slow = slow.next
fast = fast.next.next
return True``````

### 【合并两个有序链表】

``````class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1:
return l2
if not l2:
return l1
while l1 and l2:
if l1.val <= l2.val:
now.next = ListNode(l1.val)
l1 = l1.next
now = now.next
else:
now.next = ListNode(l2.val)
l2 = l2.next
now = now.next
if l1:
now.next = l1