8、 point
8.1 两数之和等于指定值
class Solution:
def twoSum(self , numbers , target ):
# write code here
n = len(numbers)
if n<2:
return []
L = sorted(numbers)
i = 0
j = n-1
while i<j:
if L[i]+L[j]==target:
a = numbers.index(L[i])
numbers.pop(a)
b = numbers.index(L[j])
if b>=a:
b += 1
if a>b:
a,b = b,a
return a+1,b+1
elif L[i]+L[j]>target:
j -= 1
elif L[i]+L[j]<target:
i += 1
return []
8.2 数组中相加和为0的三元组
class Solution:
def threeSum(self , num ):
# write code here
n = len(num)
num = sorted(num)
print('num=',num)
res = []
for i in range(n-2):
if num[i]>0:
break
j = i+1
k = n-1
while j<k:
if num[i]+num[j]+num[k]==0:
t = [num[i],num[j],num[k]]
if t not in res:
res.append(t)
j += 1
k -= 1
elif num[i]+num[j]+num[k]<0:
j += 1
elif num[i]+num[j]+num[k]>0:
k -= 1
print('res=',res)
return
8.3 数组中未出现的最小正整数
先排序，负值略过，重复略过，按1至N对比，如没有则返回
class Solution:
def minNumberdisappered(self , arr ):
# write code here
L = sorted(arr)
L.append(L[-1]+1)
#print(L)
k = 1
for i in range(len(L)-1):
#print('i=',i,'k=',k)
if L[i]<0:
continue
if L[i]==L[i+1]:
continue
if L[i] != k:
break
else:
k += 1
#print('k=',k)
return k
9、 other (array / string / sort)
9.1 字符串的排列
对于已有的每一种排列的每个位置k，插入第i个新数字ss[i]，得到一组新排列
class Solution:
def Permutation(self, ss):
# write code here
n = len(ss)
if n<=0:
return
if n==1:
return ss
ss = list(ss) # 输入转成list（list才有insert方法）
out = []
out.append([ss[0]]) # i-1时已有的排列（二维数组）
for i in range(1,n):
tmp = []
for string in out: # 对于已有的每一种排列
for k in range(len(string)+1): # 当前排列的每个位置k
s = string.copy() # 复制当前排列
s.insert(k,ss[i]) # 在复制排列的第k个位置，插入第i个数ss[i]
tmp.append(s) # 得到一组新排列加入临时二维数组
out = tmp # 更新i-1时已有的排列
for i in range(len(out)):
out[i] = ''.join(out[i]) # 数组合成一个对象用于set()去重，再排序
out = sorted(set(out)) # set的元素只能是单个变量，不能是数组等多变量对象
#print(out)
return out
9.2 找出连续最长的数字串
原字符串前后加##，数字改1，其它改0，利用规则找01突变点，存储最长数字串
L = input()
L = '#'+L+'#'
#print('L=',L)
S=''
for s in L:
if s.isdigit():
S += '1'
else:
S += '0'
#print('S=',S)
i_start = 0
i_len = 0
Out = []
for i in range(1,len(S)):
if S[i]=='1' and S[i-1]=='0':
i_start = i
#print('i_start=',i_start)
elif S[i]=='0' and S[i-1]=='1':
i_end = i
#print('i_end=',i_end)
if i_end-i_start==i_len:
Out.append(L[i_start:i_end])
elif i_end-i_start>i_len:
i_len = i_end-i_start
Out = []
Out.append(L[i_start:i_end])
#print(i_len)
print(''.join(Out)+','+str(i_len))
9.3 学英语
1、关键是1~3位数的表达，首先考虑1~19，20、30、……90建立字典
2、然后将1~3位填充成3位，再分别考虑每一位是否为0的情况
3、and的位置：百位数个数基数词形式加“hundred”，表示几百，在几十几与百位间加上and
例如：2,648 two thousand six hundred and forty eight
D = {'1':'one','2':'two','3':'three','4':'four','5':'five','6':'six','7':'seven','8':'eight','9':'nine','10':'ten',
'11':'eleven','12':'twelve','13':'thirteen','14':'fourteen','15':'fifteen','16':'sixteen','17':'seventeen','18':'eighteen','19':'nineteen','20':'twenty',
'30':'thirty','40':'forty','50':'fifty','60':'sixty','70':'seventy','80':'eighty','90':'ninety'}
def fun(L):
n = len(L)
#print('LL=',L)
#print('nn=',n)
out = ''
if n==1:
out += D[L]
elif n==2:
if int(L)>=10 and int(L)<=20: # 10-20特例
out += D[L]
else :
if L[0] != '0' and L[1] == '0':
out += D[L]
elif L[0] != '0' and L[1] != '0':
t = L[0]+'0'
out += D[t]+' '+ D[L[1]]
else:
if L[0] == '0' and L[1] == '0' and L[2] == '0':
pass
elif L[0] != '0' and L[1] == '0' and L[2] == '0': # 佰
out += D[L[0]]+' hundred'
elif L[0] == '0' and L[1] != '0' and L[2] == '0': # 十
#out += 'and ' + D[L[1:3]]
out += D[L[1:3]]
elif L[0] == '0' and L[1] == '0' and L[2] != '0': # 个
#out += 'and ' + D[L[2]]
out += D[L[2]]
elif L[0] != '0' and L[1] != '0' and L[2] == '0': # 佰十
out += D[L[0]]+' hundred and '+ D[L[1:3]]
elif L[0] != '0' and L[1] == '0' and L[2] != '0': # 佰个
out += D[L[0]]+' hundred and '+ D[L[2]]
elif L[0] == '0' and L[1] != '0' and L[2] != '0': # 十个
if int(L[1:])>10 and int(L[1:])<20: # 10-20特例
#out += 'and ' + D[L[1:]]
out += D[L[1:]]
else:
t = L[1]+'0'
#out += 'and ' + D[t]+' '+D[L[2]]
out += D[t]+' '+D[L[2]]
elif L[0] != '0' and L[1] != '0' and L[2] != '0': # 百十个
if int(L[1:])>10 and int(L[1:])<20: # 10-20特例
out += D[L[0]] + ' hundred and ' + D[L[1:]]
else :
t = L[1]+'0'
out += D[L[0]] + ' hundred and ' + D[t]+' '+D[L[2]]
return out
9.4 人民币转换
D = {'0':'零','1':'壹','2':'贰','3':'叁','4':'肆','5':'伍','6':'陆','7':'柒','8':'捌','9':'玖'}
def f4(L):
L = L.zfill(4)
#--------------------------------------------------
# 个十百千位分别给单位
T = ['仟','佰','拾','']
out = ''
for i in range(4):
if L[i] != '0':
out += D[L[i]]+T[i]
else:
out += '零'
#--------------------------------------------------
# 最多3个0变为1个0
out = out.replace('零零','零')
out = out.replace('零零','零')
out = out.replace('壹拾','拾')
#--------------------------------------------------
# 结尾1个零删除
if out[-1]=='零':
out = out[0:-1]
return out
9.5 合法IP & Mask
# 识别有效的IP地址和掩码并进行分类统计
def value(S):
return int(S[0])*256**3 + int(S[1])*256**2 + int(S[2])*256 + int(S[3])
def bin64(S):
b = ''
for i in S:
b += bin(int(i))[2:].zfill(8)
return b
def isIp(ip):
if len(ip) != 4:
return False
for i in ip:
if not i.isnumeric() or int(i)<0 or int(i)>255:
return False
return True
def isMask(mask):
if len(mask) != 4:
return False
for i in mask:
if not i.isnumeric() or int(i)<0 or int(i)>255:
return False
t = list(map(int,list(bin64(mask))))
a = []
for i in range(len(t)-1):
a.append(t[i]-t[i+1])
if a.count(1) == 1 and a.count(0) == 30:
return True
else:
return False
9.6 螺旋矩阵
先做4个子函数fun1-4，再做一个主调fun，运行一次剥离一圈数据，直到矩阵为空
def fun1(matrix):
if matrix:
return matrix.pop(0),matrix
else:
return [],[]
def fun2(matrix):
if matrix:
t = []
mat = []
for row in matrix:
if row:
a = row.pop()
t.append(a)
mat.append(row)
return t,mat
else:
return [],[]
def fun3(matrix):
if matrix:
return matrix.pop()[::-1],matrix
else:
return [],[]
def fun4(matrix):
if matrix:
t = []
mat = []
for row in matrix[::-1]:
if row:
a = row.pop(0)
t.append(a)
mat.append(row)
return t,mat[::-1]
else:
return [],[]
def fun(matrix):
if matrix:
out1,matrix = fun1(matrix)
out2,matrix = fun2(matrix)
out3,matrix = fun3(matrix)
out4,matrix = fun4(matrix)
return out1+out2+out3+out4,matrix
else:
return [],[]
9.7 容器盛水问题
1、从左向右，从右向左各扫一遍，记住当前最大值，
2、如果当前值小于最大值，则计算水容量，如果当前值大于最大值，则更新最大值
3、对应位置左右扫描取小，即是实际容量，
4、第二次扫描时同时计算容量，少一次遍历
class Solution:
def maxWater(self , arr ):
# write code here
L = arr
n = len(arr)
if n<3:
return 0
i_max = arr[0]
w1 = []
for i in range(1,n-1):
if L[i]>i_max:
i_max = L[i]
w1.append(0)
else:
w1.append(i_max-L[i])
i_max = arr[-1]
w2 = []
res = 0
for i in range(n-2,0,-1):
if L[i]>i_max:
i_max = L[i]
else:
res += min(w1[i-1],i_max-L[i])
#print(w1)
#print(w2)
return res
9.8 称砝码
砝码一个个地增加，原集合中每一个重量 + 新砝码重量 = 新增重量集合
n = int(input())
weight = list(map(int,input().strip().split()))
num = list(map(int,input().strip().split()))
set_old = {0}
for i in range(n):
for j in range(num[i]): # 按砝码个数依次取
w = weight[i] # 新取砝码的重量
#print(w)
set_new = set()
for s in set_old:
set_new.add(s+w) # 原集合中每一个重量 + 新砝码重量 = 新增重量集合
set_old = set_old | set_new # 新增重量集合与原集合的并集，构成下一次的原集合
print(len(set_old))
京公网安备 11010502036488号