|
发表于 2017-9-11 17:20:06
|
显示全部楼层
本帖最后由 gunjang 于 2017-9-13 17:01 编辑
我能说答案是68888888(选项3)吗。。。555无法投票
该问题分成两个部分,找出数字x的位置和把序列分成连续的x,x+1,x+2...
第一个很简单,因为1-9共9个数字长度为1,10-99共90个数字长度为2。。。很有规律
第二个如果是普通的连续序列,或者只是长度为1的序列,还好判断,但是考虑到99100序列中截取的部分如9100就很难,故采用通配符?*代表1个和多个字符进行匹配。。。(正则表达式水平不够,大神应该可以直接用regex进行模式判断吧),容易出错,还缺少测试代码。。
凑合吧
- #http://bbs.fishc.com/thread-96256-1-1.html
- import math
- def get10nindex(n):
- r = 0
- for i in range(1, n+1):
- r += (10**i - 10**(i-1)) * i
- return r
- def getXindex(x):
- n = int(math.log10(x))
- return get10nindex(n) + (x-10**n-1+1)*(n+1)
- #Wildcard: question mark(?): one character
- #star(*) any number of characters
- def match(source, startindex, x):
- #return True or False and startindex
- x = str(x)
- for i in range(len(x)):
- if source[startindex+i] == '?':
- continue
- if source[startindex+i] == '*':
- return True, len(source)
- if source[startindex+i] != x[i]:
- return False, 0
- return True, startindex+len(x)
- #9932 ==> 3199,3200 => 3199,3
- def trymatch(newseq, sublen, qmcnt):
- #9932 => ..9932* => ..99 , 32* => ??00, 32* #99+1=100[1:3]
- a = '?'*qmcnt+str(int(newseq[qmcnt:sublen])+1)[qmcnt-sublen:]#[:sublen-qmcnt]
- b = newseq[sublen:]
- #exp: a,b=99,100,have difficent length
- print('trymath', a,'vs',b)
- r = ''
- for i in range(sublen):
- if a[i] == b[i]:
- r += a[i]
- else:
- if a[i]=='?':
- r += b[i]
- elif b[i] == '*':
- return True, r+a[i:]
- else:
- return False, ''
- return True, r
- def getMinXinSequence(sequence):
- sequence = str(sequence)
- x = int(sequence)
- offset = 0
- if len(sequence) == 1:
- return x, offset
- if len(sequence) == 2:
- #56 78 => 5 7
- if int(sequence[1]) == int(sequence[0])+1:
- return int(sequence[0]), 0
- #53 =>3|53|6 or 53|54
- t = (x%10)*10 + x//10
- if x < t:
- return x, 0
- else:
- return t, 1
- #length >= 3
- #wildchar
- #. match one char/digit
- #* match any chars/digits
- for sublen in range(1, len(sequence)+1):
- for qmcnt in range(sublen):
- newseq = '?'*qmcnt + sequence + '*'
- if qmcnt == 0:
- if sublen == len(sequence): #n=sequence
- continue
- n = int(sequence[:sublen])
- index = sublen
- while True:
- n += 1
- matched, index = match(newseq, index, n)
- if not matched:
- break
- else:
- if index >= len(sequence):
- return int(sequence[:sublen]), 0 # matched
- else:
- if len(sequence) + qmcnt > 2*sublen:
- n = int(sequence[sublen-qmcnt:sublen-qmcnt+sublen])
- #check prev number
- matched, index = match(newseq, 0, n-1)
- if not matched:
- continue
- index = sublen-qmcnt+sublen
- t = n
- while True:
- t += 1
- matched, index = match(sequence, index, t)
- if not matched:
- break
- else:
- if index >= len(sequence):
- return n-1, qmcnt # matched
- else:
- #too complex ,such as 23|4523|46 =>2345, 2346
- #1|2312|4 or 12|312|4 => 123,124 qmcnt=1,2, sublen=3
- # 129,130(2913)
- matched, secondnum = trymatch(newseq, sublen, qmcnt)
- if matched:
- n = int(secondnum)-1
- if x < n:
- return x, 0
- else:
- return n, qmcnt
- return x, offset
- def findposition(n):
- minx, offset = getMinXinSequence(n)
- return getXindex(minx)+offset
- # print(5, getMinXinSequence('5'))
- # print(12345, getMinXinSequence('12345'))
- # print(122123124, getMinXinSequence('122123124'))
- # print(122123124126, getMinXinSequence('122123124126'))
- # print(54, getMinXinSequence('54')) #45 , 1
- # print(56, getMinXinSequence('56')) #5,incorrect
- # t1 = '122123124' #==> 122
- # print(t1[2:], getMinXinSequence(t1[2:])) #==> 122,2
- # print(312, getMinXinSequence('312')) #==> 123,124 => 123,2
- #print(9932, getMinXinSequence('9932')) #==> 3199,3200 => 3199,3 or 2|993,2|994
- #print(9931, getMinXinSequence('9931')) #==> 3199,3200 => 3199,3 or 1|993,1|994
- #print(45, getXindex(45)) #79
- #print(123456798, getXindex(123456798)) #1000000071
- #print(123459876, getXindex(123459876)) #1000027773
- #print(findposition(789)) #6
- #print(findposition(454)) #79
- #print(getXindex(10000000)-1) #
- print(findposition(9100)) #9100=>99,100=>99,1=>189
复制代码 |
评分
-
查看全部评分
|