测试工程师面试题-Python编程题

Q:无序列表，如何去重

ids=[1,2,3,4,3,2,5] 
new_ids=list(set(ids)) 
print(new_ids)

Q:字符串转为数字，比如 str="1234"，变成 int 1234，并测试这个程序。

def stoi(sr):
    current = 0
    for i in sr:
        sum = ord(i) - ord('0')
        current = current * 10 + sum
    return current

assert type(stoi('1234')) == int
assert stoi('1234') == 1234

Q:99乘法表

for i in range(1, 10):
    for j in range(1, i+1):
        print('{}x{}={}\t'.format(j, i, i*j), end='')
    print()

Q:实现阶乘函数

def factorial(num):
    if num <=1:
        return 1
    else:
        return num*factorial(num-1)

Q:leetcode-468. 验证IP地址

IPv4的格式:(1~255).(0~255).(0~255).(0~255)

def legal_ip_2(one_str):
    try:
        IPy.IP(one_str)
        return True
    except Exception as e:
        return False

def validate_IP4(ip):
    nums = ip.split('.')
    for x in nums:
        if len(x) == 0 or len(x) > 3:
            return "Neither"
        if x[0] == '0' and len(x) != 1 or not x.isdigit() or int(x) > 255:
            return "Neither"
    return "IPv4"
def validate_IP6(ip):
    nums = ip.split(':')
    hexdigits = '0123456789abcdefABCDEF'
    for x in nums:
        if len(x) == 0 or len(x) > 4 or not all(c in hexdigits for c in x):
            return "Neither"
    return "IPv6"
def valid(ip):
    if ip.count('.')==3:
        return validate_IP4(ip)
    if ip.count(':')==7:
        return validate_IP6(ip)
    else:
        return False

Q:算出 100-1000 的质数

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数.

data = []
for i in range(100, 1000):
    for j in range(2, i):
        if i % j == 0:
            break
    else:
        data.append(i)

Q:字符串反转，如果字符串有多个空格也需要处理

ss = 'SJD EJJF EJEF'
ss = re.sub(r'\s', '', ss)
print(ss[::-1])

ss = 'SJD EJJF EJEF'
ss = re.sub(r'\s', '', ss)
a = ''.join(reversed(ss))
print(a)

def rev(str):
    l = list(str)
    newstr = ""
    while len(l) > 0:
        newstr += l.pop()
    return newstr

Q: 找出第一个非重复字符在字符串中的位置

举例：‘Google’返回l,4

def first_char(string):
    dict1 = {}
    for i in string:
        # 累计字符的出现次数
        if i in dict1:
            dict1[i] += 1
        # 只出现一次，key对应的value就记1次
        else:
            dict1[i] = 1
    for i in range(len(string)):
        if dict1[string[i]] == 1:
            return string[i], i

Q:实现斐波那契数列(⽣成器方式)

def fib(n):
    if n <= 1:
        return n
    return fib(n-1)+fib(n-2)
for i in range(1, 20):
    print(fib(i), end=',')

Q:leetcode-165. 比较版本号

Python比较两个版本号 v1 和 v2；如果 v1 > 2 返回 1,如果 v1 < v2 返回 -1， 除此之外返回 0。

思路：
根据点分割两个字符串将分割的结果存储到数组中。
遍历较长数组并逐个比较块。如果其中一个数组结束了，实际上可以根据需要添加尽可能多的零，以继续与较长的数组进行比较。
如果两个版本号不同，则返回 1 或 -1。
版本号相同，返回 0。

def compare_version(v1, v2):
    nums1 = v1.split('.')
    nums2 = v2.split('.')
    n1, n2 = len(nums1), len(nums2)
    for i in range(max(n1, n2)):
        i1 = int(nums1[i])if i < n1 else 0
        i2 = int(nums2[i])if i < n2 else 0
        if i1 != i2:
            return 1 if i1 > i2 else -1
    return 0

Q:对列表中的 IP 排序

import socket

iplist = ['192.168.1.33','10.5.1.3','10.5.2.4','202.98.96.68','133.120.1.1','192.168.1.22']
print(sorted(iplist, key=socket.inet_aton))

socket.inet_aton(ip_string)  // 依赖于inet_aton的C实现
转换IPV4地址字符串（192.168.10.8）成为32位打包的二进制格式（长度为4个字节的二进制字符串），它不支持IPV6。inet_pton()支持IPV4/IPV6地址格式。

Q:字符串中找出连续最长的数字串。

import re
print(max(re.findall(r"\d*", input()), key=len))

Q:leetcode-409. 最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

def cront(s):
  count = collections.Counter(s).values()
  x = sum([item//2*2 for item in count if(item//2>0)])
  return x if x==len(s)else x+1

Q:[-1,1,1,-2,3,-5,-6]⽤最少的时间、空间，将负数放在左边、正数放右边。

def sort_li(li):
    i = 0
    j = len(li) - 1
    while i <= j:
        if li[i] < 0:
            i += 1
        elif li[j] > 0:
            j -= 1
        else:
            li[i], li[j] = li[j], li[i]
    return li

Q: lintcode-144. 交错正负数

给出一个含有正整数和负整数的数组，重新排列成一个正负数交错的数组。
解题思路：先将负数放在左边，正数放在右边，然后隔一个数进行交换。（需考虑负数多，正数多和正负数一样多的情况）

def rerange(a):
    if a is None or len(a) == 0:
        return a
    start, end = 0, len(a)-1
    while start < end:
        if a[end] > 0:
            end -= 1
        elif a[start] < 0:
            start += 1
        else:
            a[start], a[end] = a[end], a[start]
    # 计算负数的个数
    if a[start] < 0:
        start += 1
    # 负数更少，两边应是正数
    if start < len(a)-start:
        start, end = 0, len(a)-2
    # 正数更少，两边应是负数
    elif start > len(a)-start:
        start, end = 1, len(a)-1
    # 正数负数相同
    else:
        start, end = 0, len(a)-1

    while start < end:
        if a[start] > 0 or a[end] < 0:
            break
        a[start], a[end] = a[end], a[start]
        start += 2
        end -= 2

    return a

Q:字符串中最小的整数

class Solution(object):
    def FindMaxinStr(self, s):
        if not s:
            return 0
        result = []
        current = 0
        for c in s:
            num = ord(c) - ord('0')
            if 0 <= num <= 9:
                current = current*10+num
                result.append(current)
            else:
                current = 0
        return min(result)

Q: 剑指 Offer 50. 第一个只出现一次的字符

在字符串s中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

def first(s: str):
    dic = {}
    for c in s:
        dic[c] = c not in dic
    for c in s:
        if dic[c]:
            return c
    return ''

Q:输⼊一个字符串然后去掉空格，在统计每个字⺟出现的次数

from collections import Counter
a = a.replace(' ', '')
b = Counter(a)

def str_count(a):
    a = a.replace(' ', '')
    b = {}
    i = 0
    while i < len(a):
        if a[i] in b:
            b[a[i]] += 1
        else:
            b[a[i]] = 1
        i += 1
    return b

Q：leetcode-88.合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

def merge(nums1, m, nums2, n):
    p1 = m - 1
    p2 = n - 1
    p = m + n - 1

    while p1 >= 0 and p2 >= 0:
        if nums1[p1] < nums2[p2]:
            nums1[p] = nums2[p2]
            p2 -= 1
        else:
            nums1[p] = nums1[p1]
            p1 -= 1
        p -= 1
    nums1[:p2 + 1] = nums2[:p2 + 1]

Q::leetcode-10. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

 def numWays(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007

Q:leetcode-704. 二分法查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot = left + (right - left) // 2
            if nums[pivot] == target:
                return pivot
            if target < nums[pivot]:
                right = pivot - 1
            else:
                left = pivot + 1
        return -1

Q:leetcode-20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

def isvalid(self, s):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

Q: 剑指Offer-40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

def getLeastNumbers(arr: List[int], k: int):
    arr.sort()
    return arr[:k]

时间复杂度：O(n log n),其中 nn 是数组 arr 的长度.算法的时间复杂度即排序的时间复杂度。
空间复杂度：O(log n),排序所需额外的空间复杂度为O(logn)

def getLeastNumbers1(arr:List[int], k: int):
    if k == 0:
        return list()
    hp = [-x for x in arr[:k]]
    heapq.heapify(hp)
    for i in range(k,len(arr)):
        if -hp[0]>arr[i]:
            heapq.heappop(hp)
            heapq.heappush(hp, -arr[i])
    ans = [-x for x in hp]
    return ans

时间复杂度：O(nlogk)，其中 nn 是数组 arr 的长度。由于大根堆实时维护前 k小值，所以插入删除都是 O(logk) 的时间复杂度，最坏情况下数组里 nn 个数都会插入，所以一共需要 O(nlogk) 的时间复杂度。
空间复杂度：O(k)，因为大根堆里最多 kk 个数。

Q: leetcode-347. 前 K 个高频元素

class Solution:
    def top(self,nums,k):
        lookup = Counter(nums)
        return [item[0] for item in lookup.most_common(k)]

Q:leetcode-560.和为K的子数组

class Solution:
    def subarraySum(self, nums, k: int):
        # num_times 存储某“前缀和”出现的次数，这里用collections.defaultdict来定义它
        # 如果某前缀不在此字典中，那么它对应的次数为0
        num_times = collections.defaultdict(int)
        num_times[0] = 1  # 先给定一个初始值，代表前缀和为0的出现了一次
        cur_sum = 0  # 记录到当前位置的前缀和
        res = 0
        for i in range(len(nums)):
            cur_sum += nums[i]  # 计算当前前缀和
            if cur_sum - k in num_times:  # 如果前缀和减去目标值k所得到的值在字典中出现，即当前位置前缀和减去之前某一位的前缀和等于目标值
                res += num_times[cur_sum - k]
            # 下面一句实际上对应两种情况，一种是某cur_sum之前出现过（直接在原来出现的次数上+1即可），
            # 另一种是某cur_sum没出现过（理论上应该设为1，但是因为此处用defaultdict存储，如果cur_sum这个key不存在将返回默认的int，也就是0）
            # 返回0加上1和直接将其置为1是一样的效果。所以这里统一用一句话包含上述两种情况
            num_times[cur_sum] += 1
        return res

Q:leetcode-434. 字符串中的单词数

class Solution:
    def countSegments(self, s):
        return len(s.split())

Q:字母统计并排序, 其中单词用空格分隔，统计出现最多的3个单词和它们出现的次数

def func(data):
    # 按空格对字符串进行切割
    data = data.split(' ')
    list_most=collections.Counter(data).most_common(3)
    print(list_most)

Q:快排

def quick_sort(li,start,end):
    if start >= end:
        return
    left = start
    right = end
    mid = li[left]
    while left < right:
        while left < right and li[right] >= mid:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] < mid:
            left += 1
        li[right] = li[left]
    li[left] = mid
    quick_sort(li, start, left-1)
    quick_sort(li, left+1, end)

Q:冒泡排序

def bubble_sort(arr):
    length = len(arr)
    while length > 0:
        for i in range(length-1):
            if arr[i] > arr[i+1]:
                current = arr[i]
                arr[i] = arr[i+1]
                arr[i + 1] = current
        length -= 1