quick Select，取第k大的数。O(N)
def quickSelect(List,l,r,k):
if(l==r): return List[k-1]
rand=random.randint(l,r-1)
comp=List[rand]
i=l
j=r
while(True):
while(List[i]<=comp):
i+=1
while(List[j]>=comp):
j-=1
if(i>=j):
break
temp=List[i]
List[i]=List[j]
List[j]=temp
if(i==k):
return List[k-1]
if(i>k):
return quickSelect(List,l,j,k)
else:
return quickSelect(List,j+1,r,k)
isomorphic Strings
扫两遍
def isomorphic(str1,str2):
if(len(str1)!=len(str2)):
return False
a=[0]*300
b=[0]*300
for i in range(len(str1)):
if(a[ord(str1[i])]!=0 and a[ord(str1[i])]!=ord(str2[i])): return False
else:
a[ord(str1[i])]=ord(str2[i])
for j in range(len(str1)):
if(b[ord(str2[j])]!=0 and b[ord(str2[j])]!=ord(str1[j])): return False
else:
b[ord(str2[j])]=ord(str1[j])
for k in range(0,300):
if(a[k]!=0 and b[a[k]]!=k):
return False
if(b[k]!=0 and a[b[k]]!=k):
return False
return True
给定一组Array 表示每个起始位置和线段长度 {,,,,} return 不重复的线段最多的条数
算起止。递归数列
def countMax(List):
num=len(List)
if num==0: return 0
if num==1: return 1
for i in range(num):
(a,b)=List[i]
List[i]=(a,a+b)
List.sort(key=lambda List:List[1])
print(List)
f=[0]*num
f[0]=1
for i in range(1,num):
(x1,y1)=List[i]
temp=0
for j in range(i-1,-1,-1):
(x0,y0)=List[j]
if(y0<=x1):
temp=f[j]+1
break
f[i]=max(f[i-1],temp)
return f[num-1]
Write a function that takes two arguments, a list of words and an integer n,# and returns the nth most common word in the list.
用python的dictionary
def nthMostCommon(List,n):
dictL={}
for i in range(len(List)):
if(not List[i] in dictL):
dictL[List[i]]=1
else:
dictL[List[i]]+=1
#print(dictL)
sortDict=sorted(dictL.items(),key=lambda d:d[1],reverse=True)
#print(sortDict)
(a,b)=sortDict[n-1]
return a
long common prefix
扫两遍
def longestCommonPrefix(self, strs):
# write your code here
minLength=10000000
minWord=""
for i in range(len(strs)):
length=len(strs[i])
if length
minWord=strs[i]
if minWord=='': return ""
for i in range(len(strs)):
for j in range(len(minWord)):
if(minWord[j]!=strs[i][j]):
minWord=minWord[:j]
if minWord=="": return ""
break
return minWord
判断字符是否同构
两个方法
def anagram(self, s, t):
#d1=dict()
#for c in s:
# d1[c]=d1.get(c,0)+1
#d2=dict()
#for d in t:
# d2[d]=d2.get(d,0)+1
#return (d1==d2)
# write your code here
a=sorted(s)
b=sorted(t)
return (a==b)
你有一个人的密码，但是密码是全小写的， 真正的密码里有些字母是大写的，找到那个正确的密码。他给你一个能查string是不是正确密码的函数。 eg: Given a password string "password" and a function isCorrectPassword(), output the correct password => "PAssWord" Follow Up 是如果给你一个random string " aaaaaapasswordaaaabbbbcc", 其中有个substring是你的密码，找到那个密码。 密码依旧是全小写的， 要用之前写的function找到带大写字母的密码。
def findPassword(s):
length=len(s)
num=2**length
for i in range(num):
temp=i
temps=s
for j in range(length):
if(temp%2==1):
temps=temps[0:j]+temps[j].upper()+temps[j+1:]
temp=temp//2
print(temps)
#findPassword("password")
#bruce
def findSubstring(s):
length=len(s)
for i in range(length):
for j in range(i,length+1):
print(s[i:j])
findSubstring("aaaaaapasswordaaaabbbbcc")
#include
using namespace std;
#define inf (100)
int n,s,t,ret,tot,SR[102],SC[102],c[205][205],d[205],q[205],pre[205];
inline bool Extended_path()
{
memset(d,0,sizeof(d));
q[1]=s;
d[s]=1;
ret=t;
for (int head=0,tail=1;head++
for (int v=1;v<=t;v++)
if (c[u][v] && !d[v]) {
d[v]=d[u]+1;
q[++tail]=v;
}
if (d[t]) return true;
}
return false;
}
inline void Push_flow()
{
int flow=inf;
for (int v=t;v!=s;v=pre[v])
flow=min(flow,c[pre[v]][v]);
tot-=2*flow;
for (int v=t;v!=s;v=pre[v]) {
c[pre[v]][v]-=flow;
c[v][pre[v]]+=flow;
if (!c[pre[v]][v]) ret=pre[v];
ret=t;
}
}
inline void Dinic(int u)
{
if (u!=t) {
for (int v=1;v<=t;v++)
if (c[u][v] && d[u]+1==d[v]) {
pre[v]=u;
Dinic(v);
if (d[u]>d[ret]) return;
ret=t;
}
d[u]=0;
} else Push_flow();
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&SR[i]);
for (int i=1;i<=n;i++)
scanf("%d",&SC[i]);
s=2*n+1;t=2*n+2;
for (int i=1;i<=n;i++) {
c[s][i]=SR[i];
c[n+i][t]=SC[i];
tot+=SR[i]+SC[i];
for (int j=1;j<=n;j++)
c[i][n+j]=inf;
}
for (;Extended_path();Dinic(s));
if (!tot) {
printf("YES\n");
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) {
printf("%d",c[n+j][i]);
if (j
}
} else printf("NO\n");
return 0;
}
网络流dinic。。。虽然感觉大抵不会考到但是。。。
先这么多吧。。。感觉python真是好东西。。。处理string简直舒爽>。<
以及真的最近短时间完全彻底的系统学一门语言感觉。。。c++快不会写了＝ ＝
啊我曾经最爱的c++要变成python了嘤嘤嘤
下周开始学python写OOP不知道作业会成啥样。
明天再开始写周六要交的作业吧。。。睡觉去了
PS最近学O(N)计算方法＋各种sort算法2节课了。。。
这是第几次学这些东西了（不x
还好我不是0基础要不估计要疯（x
下周找时间去找老师聊聊好了＝ ＝啊希望能拿到yelp秋季实习嘤嘤嘤