Catalog
【 First positive number missing 】
【 Linked list 】（ Single list ）
Realization , And add, delete, modify and query operations ：
# Reference resources :https://www.cnblogs.com/kumata/p/9098137.html
import ctypes
class DynamicArray:
def __init__(self):# Special methods
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 ''
The test program ：
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)))Test result output ：
('size was: ', '0')
10 20 30
0 5 10 15 20 30
0 5 10 15 30
('size is: ', '5')
Given two arrays of ordered integers nums1 and nums2, take nums2 Merge into nums1 in , bring num1 Make an ordered array .
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:# Start at the end
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 -= 1Given an array of unsorted integers , Find the smallest positive integer that does not appear .
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_numRealization , And add, delete, and check 、 reverse 、 Output and other operations .
Node class ：
# Order one first node Class
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_nextlist ：
# Realization Linked List How to operate it
class LinkedList():
def __init__(self): # Initialize the linked list as an empty list
self._head = Node()
self._tail = None
self._length = 0
# Check if it is empty
def isEmpty(self):
return self._length == 0
#add Add elements to the front of the linked list :O(1)
def add(self,value):
self._head.setValue(value)
new_node = Node(value,self._head)
self._head = Node(next=new_node)
self._length += 1
#append Add elements at the end of the list :O(n)
def append(self,value):
new_node = Node(value,None)
if self._tail == None:
self._tail = new_node
self._head.setNext(new_node)
else:
self._tail.setNext(new_node)
self._tail = new_node
self._length += 1
#search Search whether the element is in the linked list
def search(self,value):
current = self._head.getNext()
found_value = False
while current != None:
if current.getValue() == value:
found_value = True
break
else:
current = current.getNext()
return found_value
#index The position of the index element in the linked list
def index(self,value):
current = self._head.getNext()
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 Delete an element in the linked list
def remove(self,value):
current = self._head
found =False
# if current.getValue() == value:
# self._head = current.getNext()
# 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 Insert element in linked list
def insert(self,pos,value):
if pos>self._length:
raise Exception("out index")
else:
current = self._head
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
# List inversion
def reverse(self):
if self._length == 1:
return
pre = self._head.getNext()
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()
self._head = Node(next=pre)
# Output
def _print(self):
if self._length == 0:
return
current = self._head.getNext()
# print current.getValue()
while current != None:
print '->',current.getValue(),
current = current.getNext()
print ''
The test program ：
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()Test result output ：
-> 10 -> 20 -> 30
-> 5 -> 10 -> 15 -> 20 -> 30
-> 5 -> 10 -> 15 -> 30 Given a linked list , Judge whether there are links in the list .
# Double pointer
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head==None or head.next==None:
return False
slow = head
fast = head.next
while slow != fast:
if fast==None or fast.next==None:
return False
slow = slow.next
fast = fast.next.next
return TrueMerge two ordered lists into a new ordered list and return . The new linked list is made up of all the nodes of the given two linked lists .
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
head = ListNode(0)
now = head
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
return head.next
if l2:
now.next = l2
return head.next