拼多多算法岗笔试python解决方案

AC了前三道题，最后一题通过60%，最后一题的解法只通过了线下测试，没有验证

1、 数字山谷：从每个位置向向两边扩展，找到最大山谷，注意边界即可

xx = raw_input()[1:-1]
if xx == '':
    print 0
else:
    x = map(int,xx.split(','))
    n = len(x)

    if n < 3:
        print 0
    else:
        res = 0
        for i in xrange(1,n-1):
            l = i
            while l > 0 and x[l-1]>x[l]:
                l -= 1
            r = i
            while r < n-1 and x[r+1]>x[r]:
                r += 1
            if l < i and r > i:
                res = max(res,r-l+1)
        print res if res >= 3 else 0

2、 字符串构造：假设总串s长度为n，基串base长度为k，如果s/k * base + base[:s%k]==s，则返回（应该有更好的解法）

s = raw_input()
n = len(s)
for i in xrange(1,n+1):
    base = s[:i]
    if base * (n/i) + base[:n%i] == s:
        print base
        break

3、 到达指定位置：

分情况讨论：到target与到abs(target)的情况是一样的
        1. total = 1+2+...+k，求total刚好大于等于n的k，可知到达target至少要用k步，此时超出d=total-k
        2. 如果d为偶数，则只需将d/2步反向即可，k步即可到达target
        3. 如果d为奇数，则k步不可能到达，因为任何反转都会改变偶数距离，不可能消去d，则再走一步判断d+k+1是否为偶数
        4. 如果为偶数，说明k+1步可到
        5. 如果d+k+1为奇数，且已知d为奇数，说明k+1为偶数，不可能在k+1步走到，再走一步，d+k+1+k+2必为偶数，k+2步可到

def solve(target):
    import math
    n = abs(target)
    k = int(math.ceil(((8*n+1)**0.5-1)/2.))
    total = k*(k+1)/2
    d = total - n
    if d % 2 == 0:
        return k
    elif (d+k+1) % 2 == 0:
        return k + 1
    else:
        return k + 2

n = input()
print solve(n)

4、靓号：统计每个数字出现次数counter，以每个数字为基准，按照与基准差值对counter排序，优先替换差值小的数字；关于字典序的问题，如果替换的数比基准大则从前向后替换，如果替换的数比基准大，则从后向前替换，得到的就是字典序最小的字符串，时间复杂度O(n)

n,k = map(int,raw_input().split())
x = raw_input()

dic = Counter(map(int,x))


res = float('inf')
ans = []
for num,cnt in dic.items():
    need = k - cnt
    if need <= 0:
        print 0
        print x
        break
    else:
        tmp = [[xx,dic[xx]] for xx in dic if xx != num]
        tmp.sort(key=lambda y:abs(num-y[0]))
        w = 0
        cur = {}
        ii = 0
        while need > 0:
            act = min(tmp[ii][1], need) 
            cur[tmp[ii][0]] = act
            need -= act
            w += abs(num-tmp[ii][0]) * act
            ii += 1
        if w <= res:
            x_cp = x
            for g,gn in cur.items():
                if g > num:
                    x_cp = x_cp.replace(str(g),str(num),gn)
                if g < num:
                    x_cp = x_cp[::-1].replace(str(g),str(num),gn)[::-1]

            if w == res:
                ans.append(x_cp)
            else:
                ans = [x_cp]
                res = w

print res
print sorted(ans)[0]