Python作业答疑_6.22~6.25

一、Python 一班

1. 基数分割列表

1.1 问题描述

给定一无序数列，把数列的第一个数字当成基数，让数列中基数小的数字排在数列前面，比基数大的数字排在数列的后面。

1.2 问题示例

如数列：num=[4,1,8,3,9,2,10,7]。基数为 4，排序后 num=[1,3,2,4,8,9,10,7]。

1.3 问题提示

可以使用左右指针方案。

1.4 编码实现

num = [4, 1, 8, 3, 9, 2, 10, 7]
# 基数
base_num = num[0]
# 左指针
left = 0
# 右指针
right = len(num) - 1
while left < right:
    while num[right] > base_num and right > left:
        right -= 1
    while num[left] < base_num and right > left:
        left += 1
    # 交换
    num[left], num[right] = num[right], num[left]
print(num)

2. 回旋镖的数量

2.1 问题描述

在平面中给定n个点，每一对点都是不同的，回旋镖是点的元组（i，j，k），其中，点i和点j之间的距离与点i和点k之间的距离相同（i，j，k的顺序不同，为不同元组）。找到回旋镖的数量。n最多为500，并且点的坐标都在[-10 000，10 000]范围内。

2.2 问题示例

输入[[0，0]，[1，0]，[2，0]]，输出2，两个回旋镖是[[1，0]，[0，0]，[2，0]]和[[1，0]，[2，0]，[0，0]]。

2.3 问题提示

关键是求解出两个点之间的距离。

2.4 编码实现

def getDistance(a,b):
    dx = a[0] - b[0]
    dy = a[1] - b[1]
    return dx * dx + dy * dy

def number0fBoomerangs(points):
    # 参数points:整数列表#返回整数
    if points == None:
        return 0
    ans = 0
    for i in range(len(points)):
        disCount = {}
        for j in range(len(points)):
            if i == j:
                continue
            distance = getDistance(points[i],points[j])
            count = disCount.get(distance,0)
            disCount[distance] = count + 1
        for distance in disCount:
            ans += disCount[distance] * (disCount[distance] - 1)
    return ans

n = [[0,0],[1,0],[2, 0]]
print("输入:",n)
print("输出:",number0fBoomerangs(n))

3. 合并排序数组

3.1 问题描述

合并两个排序的整数数组A和B，变成一个新的排序数组。

3.2 问题示例

输入[1，2，3]及元素个数3，输入[4，5]及元素个数2，输出[1，2，3，4，5]，经过合并新的数组为[1，2，3，4，5]。输入[1，2，5]及元素个数3，输入[3，4]及元素个数2，输出[1，2，3，4，5]，经过合并新的数组为[1，2，3，4，5]。

3.3 编码实现

a = [1, 4, 6]
b = [3, 5]
c = []
i = 0
j = 0
while i < len(a) and j < len(b):
    if a[i] < b[j]:
        c.append(a[i])
        i += 1
    else:
        c.append(b[j])
        j += 1
while i < len(a):
    c.append(a[i])
    i += 1
while j < len(b):
    c.append(b[j])
    j += 1
print(c)

二、Python 二班

1. 构造矩形

1.1 问题描述

给定一个矩形大小，设计其长（L）宽（W），使其满足如下要求：

• 矩形区域大小需要和给定目标相等；
• 宽度W不大于长度L，即L≥W；
• 长和宽的差异尽可能小；
• 返回设计好的长度L和宽度W。

1.2 问题示例

输入为4，输出为[2，2]，目标面积为4，所有可能的组合有[1，4]，[2，2]，[4，1]，[2，2]是最优的，L=2，W=2。

1.3 问题提示

给定区域面积不超过10 000 000，而且是正整数，页面宽度和长度必须是正整数。

1.4 编码实现

方案一：两头向中思路，求差值最小的一对长和宽

area = int(input("矩形大小："))
wi = 1
le = area
c = le-wi
for i in range(1, area + 1):
    le = area // i
    if le - i < c and le >= i and le * i == area:
        wi = i
        c = le - i
print(int(area / wi), wi)

方案二：中间开始，试探查找 。

import math
area = int(input("矩形大小："))
w = int(math.sqrt(area))
while area % w != 0:
    w -= 1
print(area // w, w)

2. 两个排序数组合的第k小元素

2.1 问题描述

给定两个排好序的数组A，B，定义集合sum=a+b，其中a来自数组A，b来自数组B，求sum中第k小的元素。

2.2 问题示例

给出A=[1，7，11]，B=[2，4，6]，sum=[3，5，7，9，11，13，13，15，17]，当k=3，返回7；当k=4，返回9；当k=8，返回15。

2.3 问题提示

最简单的方案，2 个列表中的数字相乘组成新的列表，再排序。

2.4 编码实现

k = int(input("位置"))
A = [1, 7, 11]
B = [2, 4, 6]
s = []
for i in range(len(A)):
    for j in range(len(B)):
        s.append(A[i] + B[j])
s.sort()
print(s[k - 1])

三、Python 三班

1. 首字母大写

1.1 问题描述

输入一个英文句子，将每个单词的首字母改成大写

1.2 问题示例

输入s="i want to go home"，输出"I Want To Go Home"。输入s="we want to go to school"，输出"We Want To Go To School"。

1.3 问题提示

可以使用 split分割字符串，取出首字母后转换成大写(可以使用字符串的 upper()方法把字母转成大写)。

1.4 编码实现

s = "i want to go home"
lst = s.split(" ")
print(lst)
for i in range(len(lst)):
    lst[i] = lst[i][0].upper()+lst[i][1:]
print(" ".join(lst))

2. 七进制

2.1 问题描述

给定一个整数，返回其七进制的字符串表示。

2.2 问题示例

输入num=100，输出202。输入num=7，输出10。

2.3 问题提示

求解七进制方法：把数字不停除以 7。再把余数重新连接起来。

如求解 100 的 七进制：

• 100 除以 7 ，余数为 2，商为 14.

• 14 再除以 7，余数为 0,商为 2。

• 2 再除了 7 ，余数为 2，商为 0。

  从后向前，把余数连接起来：202。

2.4 编码实现

num=7
res=""
while num>0:
    res+=str(num % 7)
    num=num // 7
print(res[::-1])

3. 查找数组中没有出现的所有数字

3.1 问题描述

给定一个整数数组，其中1≤a[i]≤n（n为数组的大小），一些元素出现两次，其他元素出现一次。找到[1，n]中所有未出现在此数组中的元素。

3.2 问题示例

输入[4，3，2，7，8，2，3，1]，输出[5，6]。

3.3 问题提示

逐一查找！

3.4 编码实现

num = [4, 3, 2, 7, 8, 2, 3, 1]
for i in range(1,len(num)+1):
    if i not in num:
        print(i)