TVP

# 想去看机会？这10道最高频的手撕代码题都会了吗？

5.4K0

#### 1，快速排序

``````def quick_sort(arr,start=0,end=None):
if end is None:
end = len(arr)-1
if end<=start:
return(arr)
i,j = start,end
ref = arr[start]
while j>i:
if arr[j]>= ref:
j = j - 1
else:
# 此处使用一行语句交换3个元素的值
arr[i],arr[j],arr[i+1] = arr[j],arr[i+1],arr[i]
i = i + 1
quick_sort(arr,start=start,end = i-1)
quick_sort(arr,start=i+1,end = end)
return(arr)

print(quick_sort([1,1,3,3,2,2,6,6,6,5,5,7]))
``````

``[1, 1, 2, 2, 2, 3, 5, 5, 6, 6, 6, 7]``

#### 2，二分查找

``````def binary_search(arr,target):
start,end = 0,len(arr)-1
while True:
if end - start <=1:
if target == arr[start]:
return(start)
elif target == arr[end]:
return(end)
else:
return(-1)

mid = (start + end)//2
if arr[mid]>=target:
end = mid
else:
start = mid

print(binary_search([1,4,7,8,9,12],9))
print(binary_search([1,4,7,8,9,12],3))
``````

``````4
-1``````

#### 3，爬楼梯

``````def climb_stairs(n):
if n==1:
return 1
if n==2:
return 2
a,b = 1,2
i = 3
while i<=n:
a,b = b,a+b
i +=1
return b

print(climb_stairs(10))
``````

``89``

#### 4，两数之和

``````def sum_of_two(arr,target):
dic = {}
for i,x in enumerate(arr):
j = dic.get(target-x,-1)
if j != -1:
return((j,i))
else:
dic[x] = i
return([])

arr = [2,7,4,9]
target = 6
print(sum_of_two(arr,target))
``````

``(0, 2)``

#### 5，最大回撤

``````def max_drawdown(arr):
assert len(arr)>2, "len(arr) should > 2!"
x,y = arr[0:2]
xmax = x
maxdiff = x-y

for i in range(2,len(arr)):
if arr[i-1] > xmax:
xmax = arr[i-1]
if xmax - arr[i] > maxdiff:
maxdiff = xmax - arr[i]
x,y = xmax,arr[i]

print("x=",x,",y=",y)
return(maxdiff)

print(max_drawdown([3,7,2,6,4,1,9,8,5]))
``````

``````x= 7 ,y= 1
6``````

#### 6，合并两个有序数组

``````def merge_sorted_array(a,b):
c = []
i,j = 0,0
while True:
if i==len(a):
c.extend(b[j:])
return(c)
elif j==len(b):
c.extend(a[i:])
return(c)
else:
if a[i]<b[j]:
c.append(a[i])
i=i+1
else:
c.append(b[j])
j=j+1

print(merge_sorted_array([1,2,6,8],[2,4,7,10]))
``````

``[1, 2, 2, 4, 6, 7, 8, 10]``

#### 7，最大连续子数组和

``````def max_sub_array(arr):
n = len(arr)
maxi,maxall = arr[0],arr[0]
for i in range(1,n):
maxi = max(arr[i],maxi + arr[i])
maxall = max(maxall,maxi)
return(maxall)

print(max_sub_array([1,5,-10,2,5,-3,2,6,-3,1]))
``````

``12``

#### 8，最长不重复子串

``````def longest_substr(s):
dic = {}
start,maxlen,substr = 0,0,""

for i,x in enumerate(s):
if x in dic:
start = max(dic[x]+1,start)
dic[x] = i
else:
dic[x] = i

if i-start+1>maxlen:
maxlen = i-start+1
substr = s[start:i+1]
return(substr)

print(longest_substr("abcbefgf"))
print(longest_substr("abcdef"))
print(longest_substr("abbcddefh"))
``````

``````cbefg
abcdef
defh``````

#### 9，全排列

``````import numpy as np
def permutations(arr):
if len(arr)<=1:
return([arr])
t = [arr[0:1]]
i = 1
while i<=len(arr)-1:
a = arr[i]
t = [xs[0:j]+[a]+xs[j:] for xs in t for j in range(i+1)]
t = np.unique(t,axis=0).tolist()
i = i+1
return(t)
print(permutations([1,1,3]))
``````

``[[1, 1, 3], [1, 3, 1], [3, 1, 1]]``

#### 10，三数之和

``````def sum_of_three(arr,target):
assert len(arr)>=3,"len(arr) should >=3!"
arr.sort()
ans = set()
for k,c in enumerate(arr):
i,j = k+1,len(arr)-1
while i<j:
if arr[i]+arr[j]+c <target:
i = i+1
elif arr[i]+arr[j]+c > target:
j = j-1
else:
ans.update({(arr[k],arr[i],arr[j])})
i = i+1
j = j-1
return(list(ans))

print(sum_of_three([-3,-1,-2,1,2,3],0))
``````

``[(-2, -1, 3), (-3, 1, 2)]``

0 条评论

LV.

• 1，快速排序
• 2，二分查找
• 3，爬楼梯
• 4，两数之和
• 5，最大回撤
• 6，合并两个有序数组
• 7，最大连续子数组和
• 8，最长不重复子串
• 9，全排列
• 10，三数之和