第一题：字符串距离

题目：

给出两个相同长度的由字符 a 和 b 构成的字符串，定义它们的距离为对应位置不同的字符的数量。如串”aab”与串”aba”的距离为 2；串”ba”与串”aa”的距离为 1；串”baa”和串”baa”的距离为 0。下面给出两个字符串 S 与 T，其中 S 的长度不小于 T 的长度。我们用|S|代表 S 的长度，|T|代表 T 的长度，那么在 S 中一共有|S|-|T|+1 个与T长度相同的子串，现在你需要计算 T 串与这些|S|-|T|+1 个子串的距离的和。

输入描述：

第一行包含一个字符串 S。第二行包含一个字符串 T。S 和 T 均由字符 a 和 b 组成，1 ≤ |T| ≤ |S| ≤105 。

输出描述：

输出对应的答案。

样例：

in:

aab

aba

out:

2

in:

aaabb

bab

out:

5

#-*- coding:utf-8 -*-

'''

    思路:字符串T在S下每次移动一次，进行比较

'''

class Lenth:

    def __init__(self,S,T):

        self.s=S

        self.t=T

    '''

        len_s:字符串S长度

        len_t:字符串T长度

        num:存储最后结果

    '''

    def Fun(self):

        len_s=len(self.s)

        len_t=len(self.t)

        num=0

        for i in range(len_s-len_t+1):#字符串移动次数

            for k in range(0, len_t):#同等字符串比较

                if self.s[i:len_t + i]==self.t:

                    break

                if self.s[k+i] != self.t[k]:

                    num+=1

        return num

S=raw_input()

T=raw_input()

print Lenth(S,T).Fun()

第二题：数字字符

题目：

在十进制表示中，任意一个正整数都可以用字符‘0’-‘9’表示出来。但是当‘0’-‘9’这些字符每种字符的数量有限时，可能有些正整数就无法表示出来了。比如你有两个‘1’，一个‘2’ ，那么你能表示出 11，12，121 等等，但是无法表示出 10，122，200 等数。
　
现在你手上拥有一些字符，它们都是‘0’-‘9’的字符。你可以选出其中一些字符然后将它们组合成一个数字，那么你所无法组成的最小的正整数是多少？

输入描述：

第一行包含一个由字符’0’-‘9’组成的字符串，表示你可以使用的字符。1 ≤ 字符串长度 ≤ 1000

输出描述：

输出你所无法组成的最小正整数。

样例：

in:

55

out:

1

in:

123456789

out:

10

#-*- coding:utf-8 -*-

'''

    本题思路，将0和123456789分开考虑，本题结果只可能为：10~10....、1~11....、2~22......

'''

class Min_num:

    '''

        input_list:输入的字符串

        i:记录1~9在字符串中的一起出现的次数

    '''

    def __init__(self,input_list):

        self.input_list=input_list

        self.i=0

    def min(self):

        '''

        j:用于记录0出现在字符串的次数，

        while循环计算0出现的次数，同时提出字符串中的0

        '''

        j=0

        while True:

            if 0 in self.input_list:

                self.input_list.remove(0)

                j+=1

            else:

                break

        i_first=self.get_list()

        if j>=0 and self.i==0:#当输入的字符串中有0，但是1~9并不都存在

            return i_first

        elif j>=0 and self.i>j:#当存在1~9的字符串的次数多余0的次数

            return ''+(j+1)*''

        elif j>=0 and self.i!=0:#当存在0的次数多余1~9的字符串的次数

            return str(i_first)*(self.i+1)

    '''

    get_list:用于计算1~9在输入字符串中同时出现的次数，

    返回第一次不出现在字符串中的数，同时记录1~9出现的

    次数

    '''

    def get_list(self):

        l=[1,2,3,4,5,6,7,8,9]

        for i in l:

            if i in self.input_list:

                self.input_list.remove(i)

            else:

                return i

        self.i+=1

        return self.get_list()#递归循环

while True:

    s=raw_input()

    input_list=[]

    for i in s:

        input_list.append(int(i))

    print Min_num(input_list).min()

巴特西

2018春招-美团后台开发方向编程题 (python实现)

第一题：字符串距离

题目：

输入描述：

输出描述：

样例：

第二题：数字字符

题目：

输入描述：

输出描述：

样例：

最新文章

热门文章