面试题44：数字序列中某一位的数字

题目描述：

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。

详细代码： # -*- coding:utf-8 -*- class Solution: def dightAtIndex(self, index): if index < 0: return -1 digit = 1 while True: nums = self.countOfInteger(digit) if index < digit * nums: return self.Digit(digit, index) index -= nums * digit digit += 1 def countOfInteger(self, digit): if digit == 1: return 10 count = pow(10, digit - 1) return 9 * count def Digit(self, digit, index): if digit == 1: ceginNum = 0 else: beginNum = pow(10, digit - 1) num = beginNum + index // digit indexOfRight = digit - index % digit for i in range(1, indexOfRight): num //= 10 return num % 10

面试题45：把数组排成最小的数

题目描述：

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

详细代码： # -*- coding:utf-8 -*- from functools import cmp_to_key class Solution: def PrintMinNumber(self, numbers): # write code here if len(numbers) <= 0: return "" str_num = [str(i) for i in numbers] res = sorted(str_num, key = cmp_to_key(lambda x, y: int(x + y) - int(y + x))) return ''.join(res)

面试题46：把数字翻译成字符串

题目描述：

给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成“a”，1翻译成“b”，……，11翻译成“1”,……，25翻译成“z”。一个数字可能有多个翻译。例如：12258有5种不同的翻译，分别是“bccfi”、“bwfi”、“bczi”、“mcfi”和“mzi”。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

详细代码： # -*- coding:utf-8 -*- class Solution: def getTranslationCount(self, number): """ :type number: int :rtype: int """ if number < 0: return 0 str_num = str(number) return self.Count(str_num) def Count(self, str_num): length = len(str_num) counts = [0] * length for i in range(length - 1, -1, -1): count = 0 if i < length - 1: count += counts[i + 1] else: count = 1 if i < length - 1: digit1 = int(str_num[i]) digit2 = int(str_num[i + 1]) converted = digit1 * 10 + digit2 if converted >=10 and converted <=25: if i < length - 2: count += counts[i + 2] else: count += 1 counts[i] = count return counts[0]

面试题47：礼物的最大价值

题目描述：

在一个mxn的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0），你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿多少价值的礼物？

详细代码： # -*- coding:utf-8 -*- class Solution: def getMaxValue(self, array, rows, cols): if array == [] or rows < 0 or cols < 0: return 0 MaxValue = [0 for i in range(cols)] for i in range(rows): for j in range(cols): up = 0 left = 0 if i > 0: up = MaxValue[j] if j > 0: left = MaxValue[j - 1] MaxValue[j] = max(up, left) + array[i * cols + j] return MaxValue[cols - 1]

面试题48：最长不含重复字符的子字符串

题目描述：

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长字符串的长度。假设字符串中只包含‘a’-‘z’的字符。例如，在字符串“arabcacfr”中，最长的不含重复字符的子字符串是“acfr”，长度为4。

详细代码： class Solution: def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ start = 0 maxLength = 0 usedChar = {} for i in range(len(s)): if (s[i] in usedChar) and start <= usedChar[s[i]]: start = usedChar[s[i]] + 1 else: maxLength = max(maxLength, i - start + 1) usedChar[s[i]] = i return maxLength