拼多多笔试题解析

57 阅读 0 评论 38 点赞

我是靠谱客的博主着急小蝴蝶，最近开发中收集的这篇文章主要介绍拼多多笔试题解析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

120分钟，共四道编程题。

1.输出一个数组A最长的“山谷”子数组B的长度。山谷是指B[0]>B[1]>...B[i-1]>B[i]<B[i+1]<...<B[B.length-1]。B可以是A的子数组或者等于A。如果子数组长度小于3，则返回0。

思路：对每个数，向左搜索，若比当前数大，则一直搜索。向右搜索，若比当前数大，则一直搜索。

代码如下：

def FindSubNum(nums):
    ans=0
    for i in range(1,len(nums)):
        left,right=i,i
        while left-1>=0 and nums[left-1]>nums[left]:
            left-=1
        while right+1<len(nums) and nums[right+1]>nums[right]:
            right+=1
        ans=max(ans,right-left+1)
    return ans if ans>=3 else 0

x=raw_input()
nums=list(map(int,x[1:-1].split(',')))
print FindSubNum(nums)

2.leetcode 459题。

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

不同的是这里要输出子串，且输出的是最短子串。

代码如下：

def repeatedSubstring(s):
    lens=len(s)
    for i in range(1,len(s)):
        base=s[:i]
        if base*(lens/i)==s:
            return base
    return False

x=raw_input()
print repeatedSubstring(x)

3.从x轴的零坐标出发，走出的第n步，步长为n，即第一步移动的距离为1，第二步移动的距离为2。每次移动可以向左或向右移动。求最少需要走多少步才能到达target位置（target可以为负）。若无论怎么走都达到不了，则输出-1。

牛客网大佬的思路：target为正或负，所需要的步数是一样的。target=abs(target)

1.求sum=1+2+...+k。是sum刚好大于target。diff=sum-target

2.若diff为偶数，则让diff/2反向即可，共需要k步到达target。

3.若diff为奇数，让任何数反向都是减少偶数距离，不会使得diff为0。因此让diff+k+1

4.若diff+k+1为偶数，则根据1可知k+1步可到达target。

5.若diff+k+1为奇数，说明k+1为偶数，则k+2必然为奇数，因此diff+k+1+k+2必为偶数，即可以在k+2步时到达。

代码如下：

def FindTarget(target):
    target=abs(target)
    i=0
    sum=0
    while sum<target:
        i += 1
        sum+=i
    if sum==target:
        return i
    else:
        diff=sum-target
        if diff%2==0:
            return i
        else:
            if (diff+i+1)%2==0:
                return i+1
            else:
                return i+2

x=input()
print FindTarget(x)