pta7-2查找书籍

以下是一个解决pta7-2查找书籍问题的Python程序：

n = int(input())  # 输入书籍数量
books = []  # 存储书籍信息的列表

# 循环读取书籍信息
for i in range(n):
    book_info = input().split()  # 输入格式为“价格 书名”，使用split()函数将其拆分为列表
    book_info[0] = float(book_info[0])  # 将价格转换为浮点数
    books.append(book_info)  # 将书籍信息添加到列表中

# 使用max()和min()函数找到价格最高和最低的书籍
max_book = max(books, key=lambda x: x[0])  # 根据价格进行比较
min_book = min(books, key=lambda x: x[0])

# 输出结果
print("{:.2f}, {}".format(max_book[0], max_book[1]))
print("{:.2f}, {}".format(min_book[0], min_book[1]))

相关问题

PTA6-2 查找二叉排序树

题目描述：

给定一棵二叉排序树和一个值，求该值在树中出现的次数。

输入格式：

第一行包含整数 n，表示树中节点个数。

接下来 n 行，每行包含一个整数，表示当前节点的值。

最后一行包含一个整数x，表示需要统计出现次数的值。

输出格式：

共一行，包含一个整数，表示该值在树中出现的次数。

输入样例：

5
2
1
2
3
4
2

输出样例：

2

算法1：

递归遍历，统计值出现的次数。

时间复杂度

平均时间复杂度为O(logn)，最坏时间复杂度为O(n)。

参考文献

Python 代码

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):

    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: bool
        """
        if not root:
            return 0

        if val == root.val:
            return 1 + self.searchBST(root.left, val) + self.searchBST(root.right, val)
        elif val < root.val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

算法2：

迭代遍历，统计值出现的次数。

时间复杂度

平均时间复杂度为O(logn)，最坏时间复杂度为O(n)。

参考文献

Python 代码

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):

    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: bool
        """
        if not root:
            return 0

        count = 0
        stack = [root]

        while stack:
            node = stack.pop()
            if node.val == val:
                count += 1
            if node.left and node.val >= val:
                stack.append(node.left)
            if node.right and node.val <= val:
                stack.append(node.right)

        return count

pta7-12二分查找

二分查找是一种高效的查找算法，它的前提是待查找的序列必须是有序的。具体实现过程如下：

1.定义一个函数，传入待查找的序列和待查找的元素。

2.定义左右两个指针，分别指向序列的第一个元素和最后一个元素。

3.当左指针小于等于右指针时，执行以下操作：

a.计算中间位置的索引，即(left+right)//2。

b.如果中间位置的元素等于待查找的元素，返回中间位置的索引。

c.如果中间位置的元素大于待查找的元素，将右指针移动到中间位置的左边一个位置。

d.如果中间位置的元素小于待查找的元素，将左指针移动到中间位置的右边一个位置。

4.如果左指针大于右指针，说明待查找的元素不存在于序列中，返回-1。

下面是一个示例代码：

def binary_search(arr, x):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            right = mid - 1
        else:
            left = mid + 1
    return -1