Here I record the answers to all my PYTHON problems. I used PY2. Updates are slow. I mean, it’s stupid, you know, for example, range could be xrange
1. Remove duplicates from the sorted array
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] == nums[i+1]:
del nums[i+1]
else:
break
return len(nums)
Copy the codeThe best time to buy and sell stocks II
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
zong = 0
for i in range(len(prices)-1):
if prices[i+1]>prices[i]:
zong+= (prices[i+1]-prices[i])
return zong
Copy the codeGiven an array, move the elements of the array k positions to the right, where k is non-negative.
class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
k = k%len(nums)
nums[:] = nums[-k:]+nums[:-k]
Copy the codeGiven an array of integers, determine whether there are duplicate elements. The function returns true if any value appears in the array at least twice. Return false if each element in the array is different.
class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(set(nums)) == len(nums):
return False
else:
return True
Copy the codeGiven an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
for i in range(len(nums)):
if len(nums) == 1:
return nums[0]
if nums[0] == nums[1]:
del nums[0]
del nums[0]
else:
return nums[0]
Copy the codeGiven a non-empty array of non-negative integers, incrementing the number by one returns a new array.
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
num = 1
for i in range(len(digits)):
num+=int(digits[i])*(10**(len(digits)-i-1))
return [int(i) for i in list(str(num))]
Copy the codeGiven an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
j=0
for i in xrange(len(nums)):
if nums[j] == 0:
nums.append(nums.pop(j))
else:
j+=1
Copy the codeGiven an array of integers and a target value, find two numbers that neutralize the target value in the array.
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in xrange(len(nums)):
for j in xrange(i+1,len(nums)):
if nums[i]+nums[j] == target:
return [i,j]
Copy the codeDetermine if a 9×9 sudoku is valid. You only need to verify that the numbers you have entered are valid according to the following rules.
class Solution(object): def isValidSudoku(self, board): """ :type board: List[List[str]] :rtype: bool """ for i in xrange(9): hang = board[i] lie = [] for j in range(9): lie.append(board[j][i]) for m in hang: if hang.count(m)>1 and m! ='.': return False for n in lie: if lie.count(n)>1 and n! ='.': return False for j in xrange(9): if i%3==0 and j%3==0: small = [] for p in range(i,i+3): for q in range(j,j+3): if board[p][q] ! = '.': small.append(board[p][q]) if len(small) ! = len(list(set(small))): print i,j,p,q return False return TrueCopy the codeGiven an n by n two-dimensional matrix representing an image.
Rotate the image 90 degrees clockwise.
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n/2):
for j in range(i,n-i-1):
tmp = matrix[i][j]
print tmp
matrix[i][j]=matrix[n-j-1][i]
matrix[j][n-i-1],tmp = tmp,matrix[j][n-i-1]
matrix[n-i-1][n-j-1],tmp = tmp,matrix[n-i-1][n-j-1]
matrix[n-j-1][i]=tmp
Copy the codeWrite a function that reverses the input string.
class Solution(object):
def reverseString(self, s):
"""
:type s: str
:rtype: str
"""
return str(s)[::-1]
Copy the codeReverse the integer
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
if str(x)[0] == '-':
num = int('-'+str(x)[1:][::-1])
else :
num = int(str(x)[::-1])
if num>2**31-1 or num<-2**31:
return 0
else:
return num
Copy the codeGiven a string, find its first non-repeating character and return its index. If none exists, -1 is returned.
class Solution(object):
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
for i in range(len(s)):
if s[i] not in s[i+1:] and s[i] not in s[:i]:
return i
return -1
Copy the codeValid letter heterotopic word
class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ if len(s) ! = len(t): return False while s: tmp = s[0] s=s.replace(tmp,'') t=t.replace(tmp,'') if len(s)! =len(t): return False return TrueCopy the codeGiven a string, verify that it is a palindrome string, considering only alphanumeric characters, regardless of letter case.
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
s = filter(str.isalnum, str(s)).lower()
if s == s[::-1]:
return True
else:
return False
Copy the codeAn integer sequence is a sequence of integers in which integers are counted in order to get the next number. The first five are as follows:
class Solution(object): def countAndSay(self, n): """ :type n: int :rtype: str """ old = '1' for i in range(n-1): num = 1 value = '' next = '' while 1: try: if old[0]==old[1]: num += 1 value = old[0] else: if value! ='': next+= str(num)+str(value) else: next+= str(num)+str(old[0]) num = 1 value = '' old=old[1:] except IndexError,e: next += str(num)+str(old[0]) old = next break return oldCopy the codeWrite a function to find the longest public prefix in an array of strings.
Returns the empty string “” if no common prefix exists.
class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ rstr = '' if strs == []: return rstr old = strs[0] for i in range(len(old)): For j in range(len(STRS)): try: if old[I] == STRS [j] : pass else: return RSTR except: return rstr else: rstr += old[i] return rstrCopy the codeWrite a function that removes a given (non-trailing) node from a linked list, and you will be given only the nodes that need to be removed.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
Copy the codeGiven a linked list, delete the NTH last node of the list and return the first node of the list.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
dummy = ListNode(-1)
dummy.next = head
p = dummy
c = head
c2 = head
num = 0
while c2 is not None:
num+=1
c2=c2.next
for i in range(num-n+1):
if c.next is not None:
p=p.next
c=c.next
else:
p.next = None
return dummy.next
p.val = c.val
p.next=c.next
return dummy.next
Copy the codeReverse a linked list
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
p = head
q = None
while p:
c = p.next
p.next = q
q = p
p = c
return q
Copy the codeMerges two ordered lists into a new ordered list and returns. A new list is formed by concatenating all the nodes of a given two lists.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1==None and l2==None:
return None
if l1==None:
return l2
if l2==None:
return l1
if l1.val<l2.val:
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
if l2.val<l1.val:
l2.next = self.mergeTwoLists(l1,l2.next)
return l2
elif l1.val==l2.val:
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
Copy the codeDetermine if a linked list is palindromic.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
list1 = []
list2 = []
if head == None:
return True
while head:
list1.append(head.val)
list2.append(head.val)
head = head.next
list1.reverse()
if list1 == list2:
return True
else:
return False
Copy the codeGiven a linked list, determine whether there are rings in the list.
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head == None:
return False
try:
p1 =head
p2 = head.next
except:
return False
while p1:
if p1 == p2:
return True
else:
try:
p1 =p1.next
p2 = p2.next
p2 = p2 .next
except:
return False
return False
Copy the codeThe maximum depth of a binary tree
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
else:
return 1+max(self.maxDepth(root.left),self.maxDepth(root.right))
Copy the code