p*****2
发帖数: 21240 | 1
白芷帮我看看这段code好吗？指点我一下。
def find(sentence, word):
n=len(sentence)
m=len(word)
dp=[[0 for x in xrange(m+1)] for x in xrange(n+1)]
for i in xrange(n+1):
dp[i][m]=0
for j in xrange(m):
dp[n][j]=n+1
for i in xrange(n-1,-1,-1):
for j in xrange(m-1,-1,-1):
if sentence[i]==word[j]:
dp[i][j]=1+dp[i+1][j+1]
else:
dp[i][j]=1+dp[i+1][j]
ans="none"
min=n+1
for i in xrange(n):
... 阅读全帖 |
|
A*****o
发帖数: 284 | 2 Bless LZ.
写了个onsite第二轮的python解法, 感觉这题不简单啊...
used = [0 for _ in xrange(10)]
def check(s):
global used
for k in xrange(10):
if used[k] > 1:
return False
return True
def min_unused():
for i in xrange(10):
if not used[i]:
return i
return -1
def add1(l):
global used
n = len(l)
k = c = t = pos = -1
for i in xrange(n-1, -1, -1):
c = l[i]
t = (c+1) % 10
if not used[t]:
pos = i
k =... 阅读全帖 |
|
d*******l
发帖数: 338 | 3 这学期试着在学习python，用python也写了一个。力求简练，效率应该不怎么高。
def getpath(now, visited, steps):
if now == visited[h(now)]:
print steps;
return ;
prev = visited[h(now)];
p = [i for i in xrange(0, len(now)) if now[i] != prev[i]][0];
getpath(prev, visited, steps + 1);
print prev[p], now[p];
def h(node):
return ''.join([str(n) for n in node]);
def solve(N, K, init, target):
q = [init];
visited = {h(init):init};
while q != []:
now = q.pop(0);
if no... 阅读全帖 |
|
d*******l
发帖数: 338 | 4 来自主题: JobHunting版 - 求助一算法 这种数字和的问题卷积确实非常好使，鉴于k不一定是10的整次方，具体做起来还要麻
烦一些。下面是一个python的实现：
def conv(a, b):
r = [];
n = len(a);
m = len(b);
a += [0] * m;
b += [0] * n;
for i in xrange(n+m):
t = 0;
for j in xrange(i+1):
t += a[j]*b[i-j];
r.append(t);
return r;
def sum(n):
ret = 0
while(n > 0):
ret += n % 10;
n /= 10;
return ret;
def addV(a, b):
l = min(len(a), len(b));
for i in xrange(l):
a[i] += b[i];
def solve(k... 阅读全帖 |
|
|
Z*****Z
发帖数: 723 | 6 我只是把我知道的可能的不同的写法在这里改一下，改过了不一定好，只是提供另外一
种思路。其实我现在还远没有达到thinking in python那步
from itertools import product
dp=[[0] * (m+1) for _ in xrange(n+1)]
dp[n] = [n+1] * (m+1)
for i,j in product(xrange(n-1,-1,-1), xrange(m-1,-1,-1)):
li = [dp[i][0] for i in xrange(n)]
minLen = min(li)
if minLen < n+1:
i = li.index(minLen)
ans=sentence[i:i+minLen] |
|
d*s
发帖数: 699 | 7 import mpi4py as MPI
size = MPI.COMM_WORLD.size; rank = MPI.COMM_WORLD.rank
datalist = [0 for ii in xrange(size)]
datalist[rank] = data;
stat = MPI.status()
non-block情况：
for id in xrange(size):
if id==rank: continue
MPI.Isend(data, dest=id)
ii=0
while ii
if MPI.Iprobe(source=MPI.ANY_SOURCE, status=stat):
tmp = MPI.Irecv(source=stat.source)
datalist[stat.source] = tmp
ii+=1
block情况麻烦一些，只想出按顺序发送接收的笨办法:
for id in xrange(rank-1):
datalist[id] = MPI.Recv(tag=id)
for id in ... 阅读全帖 |
|
b****j
发帖数: 78 | 8 算法的python实现是这样的，很容易转化成C/C++:
def get_kth_permutation(k, n):
p = []
for i in xrange(n):
p.append(k % (i + 1))
k //= i + 1
for i in xrange(n):
for j in xrange(i + 1, n):
if p[j] <= p[i]:
p[i] += 1
return list(reversed(p)) |
|
d*******l
发帖数: 338 | 9 第一个：
def solve(N):
a = [];
for i in xrange(N):
if i * i * i < N:
a.append(i);
l = len(a);
h = {};
ans = [];
for i in xrange(l):
for j in xrange(i+1, l):
s = i*i*i + j*j*j;
if s >= N:
continue;
if not h.has_key(s):
h[s] = 1;
else:
h[s] += 1;
if h[s] > 1:
ans.append(s);
return ans; |
|
d*******l
发帖数: 338 | 10 第一个：
def solve(N):
a = [];
for i in xrange(N):
if i * i * i < N:
a.append(i);
l = len(a);
h = {};
ans = [];
for i in xrange(l):
for j in xrange(i+1, l):
s = i*i*i + j*j*j;
if s >= N:
continue;
if not h.has_key(s):
h[s] = 1;
else:
h[s] += 1;
if h[s] > 1:
ans.append(s);
return ans; |
|
p*****2
发帖数: 21240 | 11 第一题
f=[1]*10
for i in xrange(1,10):
f[i]=i*f[i-1]
def perf(n,k):
k-=1
ans=[]
v=[False]*n
for i in xrange(n-1,-1,-1):
d=k/f[i]+1
for c in xrange(n):
if not v[c]:
d-=1
if d==0:
break
ans.append(c+1)
v[c]=True
k%=f[i]
return ans |
|
p*****2
发帖数: 21240 | 12
def count(n):
dp=[[0]*(n+1) for i in xrange(n+1)]
dp[0][0]=1
for i in xrange(1,n+1):
for j in xrange(n+1):
dp[i][j]=dp[i-1][j]
if j>=i:
dp[i][j]+=dp[i][j-i]
return dp[n][n] |
|
b*****o
发帖数: 715 | 13 那还是贴code吧，我算出来是140240。 code很没有效率，要算半分钟～
//////////////////////////////////
import fractions
import time
N = 3
M = 3
def notCollinear(i, j):
a, b = map(lambda x: (x / N, x % N), (i,j))
if abs(fractions.gcd(a[0] - b[0], a[1] - b[1])) > 1:
return False
return True
def adjoin(S):
return reduce(lambda x, y: x + y, S)
def nextRound(pw):
return adjoin(map(lambda x: [x + [i] for i in xrange(N * M)
if not i in x and notCollinear(i,x[-1])], pw))
def findAll():
pw = [[[i] for i in xrang... 阅读全帖 |
|
d*k
发帖数: 207 | 14 我贡献个方法
idea: 若原数组为A，所求数组为B.对于每个i，令
L[i] = A[0] * A[1] * ... * A[i-1],
R[i] = A[i+1] * A[i+2] * ... * A[n-1]，则B[i] = L[i] * R[i]。
用python Online coding一个哈
def solve(A):
n = len(A)
if n == 0:
return []
L = [0] * n
R = [0] * n
B = [0] * n
L[0] = 1
for i in xrange(1, n):
L[i] = L[i-1] * A[i-1]
R[n-1] = 1
for i in xrange(n-2, -1, -1):
R[i] = R[i+1] * A[i+1]
for i in xrange(1, n):
B[i] = L[i] * R[i]
return B
时间复杂度O(n)，空间复杂度O(n... 阅读全帖 |
|
p*****2
发帖数: 21240 | 15 第二题
def next(s):
ch=s[0]
c=1
ans=""
for i in xrange(1,len(s)):
if(s[i]==ch):
c+=1
else:
ans+=str(c)+ch
ch=s[i]
c=1
ans+=str(c)+ch
return ans
def get(n):
s="1"
for i in xrange(1,n):
s=next(s)
return s |
|
p*****2
发帖数: 21240 | 16 第一题
def Max(l):
dp=[1]*len(l)
for i in xrange(1,len(l)):
if l[i]==l[i-1]+1:
dp[i]=dp[i-1]+1
return max(dp)
l=[3, 4, 4, 4, 2, 2, 3, 4]
print Max(l)
O(1) space的
def Max(l):
m=1
c=1
for i in xrange(1,len(l)):
if l[i]==l[i-1]+1:
c+=1
m=max(m,c)
else:
c=1
return m |
|
p*****2
发帖数: 21240 | 17 第一题
def Max(l):
dp=[1]*len(l)
for i in xrange(1,len(l)):
if l[i]==l[i-1]+1:
dp[i]=dp[i-1]+1
return max(dp)
l=[3, 4, 4, 4, 2, 2, 3, 4]
print Max(l)
O(1) space的
def Max(l):
m=1
c=1
for i in xrange(1,len(l)):
if l[i]==l[i-1]+1:
c+=1
m=max(m,c)
else:
c=1
return m |
|
a*****n
发帖数: 682 | 18 只用过很短时间的python，面试的那家发来一些题目，其中一道是关于python的，能帮
忙解答一下吗？谢谢
There's a problem with the following Python 2.x code, please fix it.
print reduce(lambda x, y: x+y, filter(lambda x: x%2, map(lambda x: x*x,
xrange(10**6)))) = sum(x*x for x in xrange(1, 10**6, 2))
After the fix, what would be printed? Explain the result. |
|
d******e
发帖数: 164 | 19 Q2 Revised:
class Graph:
def __init__(self):
self.out_edges = {}
self.in_degrees = {}
def add_vertex(self, v):
if v not in self.out_edges:
self.out_edges[v] = []
self.in_degrees[v] = 0
def add_edge(self, v_out, v_in):
if v_in not in self.out_edges[v_out]:
self.out_edges[v_out].append(v_in)
self.in_degrees[v_in] += 1
def process_words(cur_word, next_word, graph):
for i in xrange(min(len(cur_word), len(... 阅读全帖 |
|
g***9
发帖数: 159 | 20 第二题公共前缀并不是leetcode原题吧...
请教大牛 rolling hash 的解法 .. ?
自己写了一个Trie的python版本:
import sys
CHAR_COUNT = 26
class Entry(object):
def __init__(self, count=0, next=None):
self.cnt = count
self.nxt = next
#def
#class
class TrieNode(object):
def __init__(self):
self.entrylist = []
for i in xrange(CHAR_COUNT):
self.entrylist.append(Entry())
#for
#def
#class
root = TrieNode()
def InsertTrieNodes(root, curstr):
n = len(curstr)
prefix = []
curnode = root
valid = Tru... 阅读全帖 |
|
d******e
发帖数: 164 | 21 贴个Python的：
def longest_common_substring(S, T):
m = (0, 0) # (length, end)
dp = [0] * (len(T) + 1)
for i in xrange(0, len(S)):
for j in xrange(len(T) - 1, 0, -1):
if S[i] == T[j]:
dp[j+1] = dp[j] + 1
tup = (dp[j+1], j+1)
m = max(m, tup)
else:
dp[j+1] = 0
return T[m[1]-m[0]:m[1]] |
|
d******e
发帖数: 164 | 22 贴个第二题：
def palindrome(s):
dp = range(-1, len(s))
for i in xrange(1, len(s)+1):
for j in xrange(i):
if is_palindrome(s[j:i]):
dp[i] = min(dp[i], dp[j]+1)
return dp[-1] |
|
b*********s
发帖数: 115 | 23
You are right. deque is much better. Below is the implementation using deque
def solve2(s, k):
from collections import deque
d = deque(maxlen=k + 1)
n = len(s)
if n <= k:
return ''
for i in xrange(k + 1):
while d and ord(d[-1][1]) > ord(s[i]):
if s[i] == '0':
break
d.pop()
d.append((i, s[i]))
res = []
for i in xrange(k + 1, n):
res.append(d.popleft()[1])
while d and d[0][0] < i - k:
... 阅读全帖 |
|
A*****o
发帖数: 284 | 24 Bless !
第一题第二问写了个用集合的方法O(nlogk), 不知道LZ是怎么做的?
def has_dup_k(arr, k):
if not arr or k <= 0:
return False
n = len(arr)
s = set([])
for i in xrange(0, k):
x = arr[i]
if x in s:
return True
s.add(x)
#for
for i in xrange(k, n):
x = arr[i]
if x in s:
return True
s.remove(arr[i-k])
s.add(x)
return False
def test():
arr = [1, 2, 3, 1, 3, 2, 9, 0, 1]
k = 2
print has_dup_k(arr, k)... 阅读全帖 |
|
p***e
发帖数: 111 | 25 代码很难看，晚上有时间再修改。 同样单向bfs需要1200ms左右ac。
class Solution:
def ladderLength(self, start, end, dict):
dict.add(end)
current, distance, visited = [start], 1, {start:0}
bcurrent, bdistance, bvisited = [end], 1, {end:0}
while current and bcurrent:
pre, bpre,next, bnext = [], [], [], []
for word in current:
for i in xrange(len(word)):
left, right = word[:i], word[i + 1:]
for j in ... 阅读全帖 |
|
l***s
发帖数: 15 | 26 my accepted codes. seems different algorithm than the one found online
class Solution:
# @return a string
def longestPalindrome(self, s):
le = len(s)
if not s:
return ''
table=[] #record longest so far and longest ending at i
table.append(((0,0), 1))
for i in xrange(1,le):
curind=table[-1][0]
lastsofar=curind[1]-curind[0]+1
lastending=table[-1][1]
for j in xrange(i-lastending-1, i+1):... 阅读全帖 |
|
c**z
发帖数: 669 | 27 10. If you know Python, please answer the following:
There's a problem with the
following Python 2.x code, please fix it.
print reduce(lambda x, y: x+y, filter(lambda x: x%2, map(lambda x: x*x,
xrange
(10**6)))) = sum(x*x for x in xrange(1, 10**6, 2))
After the fix, what would be printed? Explain the result. |
|
y****2
发帖数: 1017 | 28 print reduce(lambda x, y: x+y, filter(lambda x: x%2, map(lambda x: x*x,
xrange(10**6)))) == sum(x*x for x in xrange(1, 10**6, 2))
=号改成==
结果是True
等式两边都是是1~ 10**6 的奇数求和 |
|
r*****t
发帖数: 2051 | 29 N是一个很大的正整数——可能到10^15次方，
简单起见，不考虑溢出，或者假设用python
A 是一个array，里面存着一些正整数，up to 1000个
从1 - N这N个数，有多少个数，不能被A中的任何一个数整除的？
举个例子：
N = 10
A = [2,4,5]
那么返回4 (1,3,7,9满足条件)
我写的如下，但是面试官不满意，因为N很大的时候内存会溢出
def left(N = 10, A = [2,4,5]):
ones = [1 for i in xrange(N+1)]
ones[0] = 0
for inte in A:
if inte == 1:
return 0
for i in xrange(1,N/inte+1):
ones[i*inte] = 0
return sum(ones) |
|
c*****m
发帖数: 271 | 30 楼主好牛逼，到这程序offer应该有了吧！祝福
之前也看过相似的面经题，当时没想出来解法。看了你的解法，才知道核心思想应该是
greedy吧？
greedy选择下一次排的word的条件是：
1.word余下出现次数最多
2.word满足的位置满足要求，即前面n位置没有相同的word。
因为有heap，你这个解法的复杂度是O(nlogn)。
我想到的和楼上有一位提到的相似，应该是O(n)的：
1. filter: 如果某个word出现大于ceil(N/n)次，那么就不能排，返回异常；否则就可
以排
2. 将N分成ceil(N/n)个sections,从出现次数最大的word开始，比如('a', 3次)，每个
section中放一个word，比如'a'放在１，２，３个section中；如果section满了，就放
到后面的section中去
3. 将所有的section连接起来，得到结果。
写了段python的，求拍
def rearrange(self, word_list, n):
#count
word_counter = collection... 阅读全帖 |
|
c*****m
发帖数: 271 | 31 感觉是wildcard matching的扩展，a+b+c-转换成*aa*bb*cccc，然后dp的过程中记录次
数，写的python代码如下，测试用例过了：
def match(s, p):
#invalid input
if len(p) % 2 != 0:
return -1
#reconstruct p
temp = ''
i = 0
while i < len(p):
#add '*' first
temp += '*'
#add char pattern
if p[i+1] == '+':
temp += p[i] * 2
else:
#p[i+1] == '-'
temp += p[i] * 4
#iterate to next char
i += 2
p = temp
print p
#... 阅读全帖 |
|
s*********b
发帖数: 815 | 32 这是隐性的DP问题啊。products[i] = products_below[i] * products_above[i]。所
以关键是怎么搭建products_below[i]和products_above[i]。这俩都有线性递归的关系
：prouducts_below[i] = products_below[i-1]*ints[i-1], 而products_above[i] =
products_above[i+1] * ints[i+1]。线性递归最安逸了。您老练临时存储都不用。直
接算了记下来就行：
def product(ints):
products = [0]*len(ints)
# products_below[i]
p = 1
for i in xrange(len(ints)):
products[i] = p
p *= ints[i]
# products_above[i]
p = 1
for i in xrange(len(ints)-1, -1, -1):
products... 阅读全帖 |
|
a**i
发帖数: 508 | 33 我想用chartobject在一个EXCEL chart上画多个线. 每次call下面的FUNC.
Function addSeries(objCHart, yRange, xRange, curveName)
With objChart.Chart
With .SeriesCollection.NewSeries
.Values = yRange
.XValues = xRange
.Name = curveName
End With
End With
end function
问题是:
第一条线OK, 后面划出的线上的点的位置是前面线的叠加. 而用MOUSE悬停在点上显示
的数值又是正确的.
例如:line1(x=1)=1, line2(x=1)=0.5
line2(x=1)点的位置就在1.5,但显示0.5 |
|
S*A
发帖数: 7142 | 34 你说的对，numpy slice 的确是使用 view. 我也试过了，对于我的应用
不行。我的问题是数据量很大，就算用 mmap 也要非常有技巧。
问题是 numpy 的 slice object 比 python array.array
费很多内存。我估计 numpy slice 在 200 byte 左右。这样 slice 数目
多上去以后总的内存还是没有省。
import numpy
fp = numpy.memmap("big-file-over-1G-byte", dtype='uint32')
x = [ fp[i] for i in xrange(0, len(fp), 50)]
# load all the thing in memory. Python should take 1.x G here
x = [ fp[i:i+1] for i in xrange(0, len(fp), 50)]
# Python take over 2G here.
不知道你要问什么 bypassing.
我会写 Python 的 C module. 代码看上去很多，但是其实很多是重复... 阅读全帖 |
|
b***y
发帖数: 2799 | 35 ☆─────────────────────────────────────☆
goodbug (好虫) 于 (Fri Jul 11 11:44:11 2008) 提到:
It's interesting to see Python people's philosophy.
For the same problem, Python wrote it this way (wormcc gave
a 2 liners but this one is cleaner for comparison purpose)
f = [open('f'+str(i)+'.bin', 'w') for i in xrange(1,6)]
x = open('abc.bin').read()
for i in xrange(len(x)): f[i%5].write(x[i])
And Java will do it this way:
DataInputStream input = null;
DataOutputStream[] output = new Dat |
|
w****i
发帖数: 964 | 36 def parse(s):
d2 = [1, 1] + [s[i]*2-s[i-1]-s[i+1] for i in xrange(1, len(s)-1)] + [1,
1]
outstr = ''
for i in xrange(len(s)):
if d2[i+1] == 0: continue
if d2[i] != 0 and d2[i+2] != 0: outstr += ', %d' % s[i]
if d2[i] == 0:
outstr += ', %d-%d' % (s[start],s[i])
if s[i] - s[i-1] > 1: outstr += '-%d' % (s[i]-s[i-1])
d2[i+2] = 1
if d2[i+2] == 0: start = i
return outstr[2:] |
|
w****i
发帖数: 964 | 37 def parse(s):
d2 = [1, 1] + [s[i]*2-s[i-1]-s[i+1] for i in xrange(1, len(s)-1)] + [1,
1]
outstr = ''
for i in xrange(len(s)):
if d2[i+1] == 0: continue
if d2[i] != 0 and d2[i+2] != 0: outstr += ', %d' % s[i]
if d2[i] == 0:
outstr += ', %d-%d' % (s[start],s[i])
if s[i] - s[i-1] > 1: outstr += '-%d' % (s[i]-s[i-1])
d2[i+2] = 1
if d2[i+2] == 0: start = i
return outstr[2:] |
|
w****i
发帖数: 964 | 38 def parse(s):
d2 = [1, 1] + [s[i]*2-s[i-1]-s[i+1] for i in xrange(1, len(s)-1)] + [1,
1]
outstr = ''
for i in xrange(len(s)):
if d2[i+1] == 0: continue
if d2[i] != 0 and d2[i+2] != 0: outstr += ', %d' % s[i]
if d2[i] == 0:
outstr += ', %d-%d' % (s[start],s[i])
if s[i] - s[i-1] > 1: outstr += '-%d' % (s[i]-s[i-1])
d2[i+2] = 1
if d2[i+2] == 0: start = i
return outstr[2:] |
|
n******7
发帖数: 12463 | 39 随便写了几行python
跟你的结果一样
===
def leapyr(n):
if n % 400 == 0:
return True
if n % 100 == 0:
return False
if n % 4 == 0:
return True
else:
return False
days = [31,28,31,30,31,30,31,31,30,31,30,31]
start_year = 1970
end_year = 2099
weekday = 3 # 12/31/1969 Wed
weekend = 5 # Fri
for year in xrange(start_year,end_year):
for month in xrange(1,13):
n_days = days[month-1]
if leapyr(year) and month == 2:
n_days = 29
weekda... 阅读全帖 |
|
n******7
发帖数: 12463 | 40 随便写了几行python
跟你的结果一样
===
def leapyr(n):
if n % 400 == 0:
return True
if n % 100 == 0:
return False
if n % 4 == 0:
return True
else:
return False
days = [31,28,31,30,31,30,31,31,30,31,30,31]
start_year = 1970
end_year = 2099
weekday = 3 # 12/31/1969 Wed
weekend = 5 # Fri
for year in xrange(start_year,end_year):
for month in xrange(1,13):
n_days = days[month-1]
if leapyr(year) and month == 2:
n_days = 29
weekda... 阅读全帖 |
|
a**i
发帖数: 508 | 41 【 以下文字转载自 BuildingWeb 讨论区 】
发信人: alli (Emma), 信区: BuildingWeb
标 题: [求助] 用VBScript 在EXCEL画图的问题
发信站: BBS 未名空间站 (Thu Oct 27 14:22:16 2011, 美东)
我想用chartobject在一个EXCEL chart上画多个线. 每次call下面的FUNC.
Function addSeries(objCHart, yRange, xRange, curveName)
With objChart.Chart
With .SeriesCollection.NewSeries
.Values = yRange
.XValues = xRange
.Name = curveName
End With
End With
end function
问题是:
第一条线OK, 后面划出的线上的点的位置是前面线的叠加. 而用MOUSE悬停在点上显示
的数值又是正确的.
例如:line1(x=1)=1, line2(x=1)=0.5
line2(x=1)点的位置就在1.5,但显示0.... 阅读全帖 |
|
b******t
发帖数: 965 | 42 menu.png论坛
space.png home.png
bth_left.png 三藩市地区 只看楼主
Re: 税改出来了 (转载)
三藩市地区 6/828
theme_pic
wwzz
2017-11-02 19:48 楼主
都少交了？
【 以下文字转载自 JobHunting 讨论区 】
发信人: sfxer (Silence), 信区: JobHunting
标 题: Re: 税改出来了
发信站: BBS 未名空间站 (Thu Nov 2 19:03:37 2017, 美东)
brackets,
落入更高的tax brackets就一定多交税？bracket少了你收入里按地税率交税的比例也
多了
不会报税也可以去网上google一下，看看是人家算错了还是你自己理解错了
回复
theme_pic
bikelost
2017-11-02 20:33 2楼
calculations assuming no mortgage deduction in the range where AMT exemption
is phased out
I don't know the exac... 阅读全帖 |
|
d****i
发帖数: 4354 | 43 It is not hard :
def T(n):
if n == 0: return 1
if n == 1: return 1
sub_nodes_total = n - 1
combination_count = 0
for i in xrange(0, n): # i iterated from 0 to (n - 1)
left_node_count = i
right_node_count = sub_nodes_total - i
left_combination_count = T(i) # combination count of left sub tree
right_combination_count = T(right_node_count) # combination count of right sub tree
combination_count += left_combination_count * right_combination |
|
r*******n
发帖数: 3020 | 44 # Input: list, the most left index, the most right index
# Output: print all permutations.
def permutation(a, l, r):
if l >= j:
print a
return
for k in xrange(l,r+1):
#swap the first and the Kth
a[l], a[k] = a[k], a[l]
permutation(a,l+1,r)
a[l], a[k] = a[k], a[l]
How to use:
For example: permutation([1,2,3,4], 0, 3) |
|
d*******l
发帖数: 338 | 45 def F(s, ch1, ch2, n):
p1 = -1;
p2 = -1;
for i in xrange(len(s)):
if s[i] == ch1:
if p2 >= 0 and i - p2 <= n:
return True;
p1 = i;
if s[i] == ch2:
if p1 >= 0 and i - p1 <= n:
return True;
p2 = i;
return False; |
|
d********w
发帖数: 363 | 46 infix expression to prefix expression.
eg:
3 * x + ( 9 + y ) / 4 ->
(+ (* 3 x) (/ (+ 9 y) 4))
参考了网上的一个递归写法，总体挺简洁的，这个复杂度是多少, 有没有O(N)的解法么？
＃reduce 用来标注是否能计算数值
def parse(s, reduce):
for operator in ["+-", "*/"]:
depth = 0
for p in xrange(len(s) - 1, -1, -1):
if s[p] == ')': depth += 1
if s[p] == '(': depth -= 1
if not depth and s[p] in operator:
left = parse(s[:p], reduce)
right = parse(s[p+1:], reduce)
... 阅读全帖 |
|
r****t
发帖数: 10904 | 47 in Python, for C(N,k) 这个是标准写法，至少 loop 到 min (k, N-k) 才对。
val = 1L
for j in xrange(min(k, N-k)):
val = (val * (N-j)) // (j+1) # j+1 because I started from 0
同时，对大组合数都应该用 gamma func 算才对。 |
|
n*s
发帖数: 752 | 48 4. string transpose
import sys
def transpose(input,i):
mystr = list(input)
mystr[i],mystr[i+1] = mystr[i+1],mystr[i]
return ''.join(mystr)
def str_transpose():
print 'input two strings, separated by blank:'
a, b = sys.stdin.readline().split()
size = len(a)
if size != len(b) or sorted(a) != sorted(b):
return 'no way!'
next = [b]
parent = {b:None}
idx = size -1
notFound = True
while notFound:
newstr = []
for x in next:
... 阅读全帖 |
|
n*s
发帖数: 752 | 49 4. string transpose
import sys
def transpose(input,i):
mystr = list(input)
mystr[i],mystr[i+1] = mystr[i+1],mystr[i]
return ''.join(mystr)
def str_transpose():
print 'input two strings, separated by blank:'
a, b = sys.stdin.readline().split()
size = len(a)
if size != len(b) or sorted(a) != sorted(b):
return 'no way!'
next = [b]
parent = {b:None}
idx = size -1
notFound = True
while notFound:
newstr = []
for x in next:
... 阅读全帖 |
|
d********w
发帖数: 363 | 50 apple面试经历：最后被一个变态中国人给灭了，问了我一个半小时，太过分了。干脆把面
经公布出来，希望大家能有机会。
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expression tree设计，grep 电话号码
第二次onsite都是hadoop相关，join的mapreduce实现，分布式wc 列出文件行数， 见
了3个... 阅读全帖 |
|
