jilinxie1988@gmail.com
BAN USERFrom the description and the test cases given, the number may not be of same length all the time:
"9979981000" -> 999 ,, 1000 is of different length.
This is an instant idea, but not a fast one:
def solve(s):
l = len(s)
for i in xrange(1,l):
h = 0
t = i
miss = -1
while t<l:
next = str(int(s[h:t]) + 1)
if next == s[t:len(next)+t]:
h = t
t = h+len(next)
continue
next = str(int(s[h:t]) + 2)
if next == s[t:len(next)+t]:
if miss != -1:
miss = -1
break
miss = int(next)-1
h = t
t = h+len(next)
continue
break
if miss != -1:
break
return miss
if __name__ == '__main__':
test = ['1234568', '9979981000','624625627']
print test
for i in test:
print solve(i)
I did a parsing of the string.
def process(s):
info = []
pos = 0
word = ''
num = ''
for i in s:
if i.isdigit():
info.append(pos)
info.append(word)
num += i
elif i.isalpha():
if num != '':
pos += int(num)*len(word)
num = ''
word = ''
word += i
return info
def get(index, info):
if index < 0:
raise
pos = 0
for i in xrange(0, len(info), 2):
if info[i] > index:
pos = info[i-2]
break
return info[pos+1][(index-pos)%len(info[pos+1])]
if __name__ == '__main__':
s = "a2bc3d4"
print get(7, process(s))
Good explanation
- jilinxie1988@gmail.com January 16, 2015A binary tree can be converted into an array based on its property that: n's root is n*2 and n*2+1.
So, the problem becomes searching for substring.
Then,, the problem becomes quite simple.
This is a non-recursive version:
Based on this function
f(n)(k) means
for a string of length n in which any adjacent character are combinable,
the solution number of splitting it so that there k substring with a pair of character while others of one character.
Then.
f(n)(0) = 1
f(n)(1) = n-1
f(n)(k) = f(n-2)(k-1) + f(n-3)(k-1) + ... + f(2k-2)(k-1)
f(n)(n/2) = 1 if n is oven else f[l-2][l/2-1]
This is a simple implementation:
#The string can be divided into 'super substring'
# 11111121, is a kind of super substring
# any adjacent unit in super substring is combinable.
#calculate all possible combination of super_substring
data_dict = {1:[1]}
# l is length of super substring
def solv_super_substring(l):
if l <= 1:
return
data_dict[l] = [0] * (l/2+1)
data_dict[l][0] = 1
data_dict[l][1] = l-1
for i in xrange(2, l/2):
for j in xrange((i-1)*2, l-1):
data_dict[l][i] += data_dict[j][i-1]
if l % 2 == 1:
data_dict[l][l/2] = 1+data_dict[l-2][l/2-1]
else:
data_dict[l][l/2] = 1
def extract_super_substring(s):
ssstr = []
tmp = ''
lofs = len(s)
for c in xrange(lofs):
if s[c] in '12':
tmp += s[c]
continue
elif s[c] in '3456' and len(tmp) > 0:
tmp += s[c]
ssstr.append(tmp)
tmp = ''
return ssstr
#test
if __name__ == '__main__':
s = '123121241291'
sstr = extract_super_substring(s)
print s
print sstr
lofss = map(lambda x: len(x), sstr)
ml = max(lofss)
for i in xrange(ml+1):
solv_super_substring(i)
print data_dict
res = []
for l in lofss:
res.append(sum(data_dict[l]))
print res
r = 1
for i in res:
r *= i
print r
I get an idea:
first , fill the new array like this:
arr[i] = sum(a[0,i-1])
This can be done in O(n) in a for loop
Then, reversely do the operation, and add result to the previous arr.
I'll try program this out,, but have to say,, always easier to think than do it for me..
Simple code:
from random import randint
a = []
for i in xrange(randint(5,10), randint(50,60)):
a.append(randint(1,100))
res = [0] * len(a)
sm = a[0]
for i in xrange(1, len(res)):
res[i] = sm
sm += a[i]
sm = a[len(a)-1]
for i in xrange(len(res)-2, -1, -1):
res[i] += sm
sm += a[i]
print sum(a)
print a
print res
Repwilliamland1990, Associate at Advent
Gifted in donating shaving cream worldwide. Crossed the country getting my feet wet with the elderly in Salisbury, MD. Have ...
for digit d, the number of it occurrences in all number of length l is:
f(l) = f(l-1)*10 + 10**(l-1)
f(1) = 1
0 is special, we need do minus of case like:
0,01,02,03…
so for 0,
we minus:
sum(10**i) #i in [0,1,2,3 ,l-1]
So, now, we know occurrence number of d for books of:
10**i-1(i>1)
pages
Based on this,, we can further decide the occurrence number of d for any given number is a
nearly constant time, as shown by nonzero_cal and zero_cal.
calculation of zero can be a little tricky though.
This solution can deal with thick books fast,,, well, yeah,, there's no so thick books existing ever~
- jilinxie1988@gmail.com January 23, 2015