[数据结构与算法]【秋招编程题记录】【1】7.16蔚来笔试+7.17Leetcode周赛笔记

1. 选择客栈

丽江河边有n家很有特色的客栈，客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰（总共k种，用整数 0~k-1表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p。
他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。
输入描述:

第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；
接下来的n行，第i+1行两个整数，之间用一个空格隔开，分别表示i号客栈的装饰色调和i号客栈的咖啡店的最低消费。

输出描述:

输出只有一行，一个整数，表示可选的住宿方案的总数。

思路：
题目想要寻找色调相同的两个客栈，中间有一个最低消费低于p的客栈中的咖啡馆（注意咖啡馆不需要为同色调）。
维护last cnt和tot数组，last记录色调c的最后一次出现的索引，cnt统计之前色调color出现的次数，tot统计色调c的第一家客栈的方案
从1到n遍历第二个客栈，记录遍历过程中的最低消费小等于p的最近的客栈（咖啡馆）now，如果now位于色调最后一次出现之后，则之前的同色调都可以作为第一家客栈，更新tot[color]，更新ans cnt last 为下次遍历做准备。

n,k,p = map(int,input().strip().split())
last, cnt, tot = [0 for _ in range(k)],[0 for _ in range(k)], [0 for _ in range(n)]
now = 0
ans = 0
# 固定客栈2，寻找客栈1的方案数
for i in range(n):
    color, price = map(int,input().strip().split())
    # 更新最近的最低消索引
    if price <= p:
        now = i
    # 如果最低消索引大等于之前最后一个色调索引，则之前的同色调客栈都可以作为客栈1的选择方案
    if now >= last[color]:
        tot[color] = cnt[color]
    # 如果小于，仍按照上一个tot进行方案数的计算
    last[color] = i  # 更新last
    ans += tot[color] # 统计方案数
    cnt[color] += 1   # 更新cnt
print(ans)

2. 裁剪数字后查询第 K 小的数字

给你一个下标从 0 开始的字符串数组 nums ，其中每个字符串 长度相等 且只包含数字。
再给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ki, trimi] 。对于每个 queries[i] ，你需要：

• 将 nums 中每个数字 裁剪 到剩下 最右边 trimi 个数位。
• 在裁剪过后的数字中，找到 nums 中第 ki 小数字对应的 下标 。如果两个裁剪后数字一样大，那么下标 更小 的数字视为更小的数字。
• 将 nums 中每个数字恢复到原本字符串。

请你返回一个长度与 queries 相等的数组 answer，其中 answer[i]是第 i 次查询的结果。

提示：

• 裁剪到剩下 x 个数位的意思是不断删除最左边的数位，直到剩下 x 个数位。
• nums 中的字符串可能会有前导 0 。
  思路：
  模拟这个过程，切片排序即可，将索引和切片完的字符串包在一起参与排序，这样能够保证当存在多个相同元素时能够准确找到索引。
  正确解法：

class Solution(object):
    def smallestTrimmedNumbers(self, nums, queries):
        """
        :type nums: List[str]
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        ans = []
        for k, trim in queries:
            # 关键：将索引一起加入排序，从而分开每一个值相同的元素，同时保持相对位置
            nums_idxs = [(num[-trim:], idx) for idx, num in enumerate(nums)]
            nums_idxs = sorted(nums_idxs)
            ans.append(nums_idxs[k-1][1])
        return ans

错误解法：

class Solution(object):
    def smallestTrimmedNumbers(self, nums, queries):
        """
        :type nums: List[str]
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        # 错误样例
        # 当存在多个元素一样的时候，虽然sort能够找到第k个值
        # 但是index只会返回值第一次出现的位置
        # 例如 nums = ["24","24","24","24"]
        # queries = [[1,1],[2,2],[3,3]]
        # 返回[0,0,0] 错误 [0,1,2] 正确
        ans = []
        for k, trim in queries:
            sort_nums = sorted(nums,key=lambda x: int(x[-trim:]))
            ans.append(nums.index(sort_nums[k-1]))
        return ans