面试练习题汇总
  • 说明
  • C/C++ 问答题汇总
  • 编程题汇总
    • 腾讯 2017 暑期实习生编程题
      • 构造回文
      • 算法基础-字符移位
      • 有趣的数字
    • 剑指 Offer 编程题练习
      • 二维数组中的查找
      • 从尾到头打印链表
      • 旋转数组的最小数字
      • 替换空格
      • 用两个栈实现队列
      • 重建二叉树
    • 网易 2017 校招笔试编程题
      • 二进制权重
      • 平方串
      • 数位和
  • 安全测试开发相关面试
    • 安全测试类面试参考
    • 业务安全类面试参考
    • 测试开发类面试参考
  • 深信服sangfor相关
    • 深信服acm相关
    • 测试类面试参考
    • 智安全杯
      • 智安全杯-2018比赛
      • 智安全杯-2019初赛
      • 智安全杯-2019复赛
  • 软件测试题汇总
  • 计算机知识题汇总
    • 前 75 题
    • 75 题以后
  • Python 语言特性
    • 1 Python的函数参数传递
    • 2 @staticmethod和@classmethod
    • 3 类变量和实例变量
    • 4 Python中单下划线和双下划线
    • 5 args and *kwargs
    • 6 面向切面编程AOP和装饰器
    • 7 单例模式
    • 8 Python 函数式编程
    • 9 Python 里的拷贝
  • stackoverflow-about-Python
    • Python中关键字yield有什么作用?
    • [Python中的元类(metaclass)是什么?](stackoverflow-about-Python/Python中的元类(metaclass)是什么.md)
    • Python中如何在一个函数中加入多个装饰器?
    • 如何判断一个文件是否存在?
    • 如何调用外部命令?
    • 枚举类型的使用?
    • 在Windows下安装pip?
    • 字典合并问题
    • 在Android上运行Python
    • 根据字典值进行排序
    • 在函数里使用全局变量
    • 变化的默认参数
    • 装饰器classmethod和staticmethod的区别
    • 检查列表为空的最好办法
    • 怎么用引用来改变一个变量
    • 检查文件夹是否存在的操作
    • name=main的作用
    • super与init方法
    • str与repr的区别
    • 循环中获取索引
    • 类里的静态变量
    • 怎么在终端里输出颜色?
    • 为什么用pip比用easy_install的好?
    • join的问题
    • 把列表分割成同样大小的块
    • 为什么代码在一个函数里运行的更快
    • 如何快速合并列表中的列表?
    • 如何知道一个对象有一个特定的属性?
    • 如何通过函数名的字符串来调用这个函数?
    • 单下划线和双下划线的含义?
  • Python 面试编程题
    • 1 台阶问题 斐波那契
    • 2 变态台阶问题
    • 3 矩形覆盖
    • 4 杨氏矩阵查找
    • 5 去除列表中的重复元素
    • 6 链表成对调换
    • 7 创建字典的方法
    • 8 合并两个有序列表
    • 9 二分查找
    • 10 快排
    • 11 找零问题
    • 12 二叉树相关
    • 13 单链表逆置
Powered by GitBook
On this page
  • 题目描述
  • 说明
  • 最终提交

Was this helpful?

  1. 编程题汇总
  2. 腾讯 2017 暑期实习生编程题

有趣的数字

题目描述

小Q今天在上厕所时想到了这个问题:有n个数,两两组成二元组,差的绝对值最小的有多少对呢?差的绝对值最大的呢?

输入描述:

输入包含多组测试数据。

对于每组测试数据:

N - 本组测试数据有n个数

a1,a2...an - 需要计算的数据

保证:

1<=N<=100000,0<=ai<=INT_MAX.

输出描述:

对于每组数据,输出两个数,第一个数表示差的绝对值最小的对数,第二个数表示差的绝对值最大的对数。

输入例子:

6

45 12 45 32 5 6

输出例子:

1 2

说明

自己在网上找了 Python 的正确答案, 然后写单元测试不断测试自己的答案, 详见对应文件夹下的 unittest_solve

最终提交

虽然写得很丑...漂亮版本的参考单元测试里面的 right_answer 吧

from collections import OrderedDict

__author__ = '__L1n__w@tch'


def solve(n, data):
    """
    求解出差的绝对值最小的对数以及差的绝对值最大的对数
    :param n: 待输入数据的个数, such as 6
    :param data: 待输入的数据, such as [45, 12, 45, 32, 5, 6]
    :return: 差的绝对值最小的对数, 差的绝对值最大的对数, 比如 (1, 2)
    """
    data = sorted(list(map(int, data.split())))

    # 读取时创建字典, 判断是否有重复数字
    od = OrderedDict()
    has_same_number = False
    min_abs_sub_pairs, max_abs_sub_pairs = 0, 0

    if n == 1:
        return "{} {}".format(0, 0)

    for each_number in data:
        value = od.get(each_number, 0)
        if value > 0:
            has_same_number = True
        od[each_number] = value + 1

    # if 分支, 有重复数字则遍历求取, 每个有重复数字能提供 n * (n - 1) / 2 对
    if has_same_number:
        for each_number in od:
            min_abs_sub_pairs += od[each_number] * (od[each_number] - 1) // 2
    else:  # 无重复数字则依次遍历求取
        temp_od = od.copy()  # 拷贝一份以便后面处理
        pre_items = temp_od.popitem(last=False)  # 获取最小项
        min_abs_sub = -1  # 初始化

        # 遍历每一项
        for next_items in temp_od.items():
            if min_abs_sub == -1 or abs(pre_items[0] - next_items[0]) < min_abs_sub:
                min_abs_sub = abs(pre_items[0] - next_items[0])
                min_abs_sub_pairs = pre_items[1] * next_items[1]
            elif min_abs_sub == abs(pre_items[0] - next_items[0]):
                min_abs_sub_pairs += pre_items[1] * next_items[1]
            pre_items = next_items

    # 计算绝对值最大的对数, 最高和最低个数乘积即可
    max_abs_sub_pairs = od.popitem(last=True)[1] * od.popitem(last=False)[1]

    return "{} {}".format(min_abs_sub_pairs, max_abs_sub_pairs)

if __name__ == "__main__":
    while True:
        try:
            length = int(input())
            data = raw_input()
            print solve(length, data)
        except EOFError:
            break
Previous算法基础-字符移位Next剑指 Offer 编程题练习

Last updated 5 years ago

Was this helpful?