【数据结构与算法】之数组系列-20240115

---

一、599. 两个列表的最小索引总和

简单
假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。

示例 1:
输入:
list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]，
list2 = [“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]
输出: [“Shogun”]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:
输入:
list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]，
list2 = [“KFC”, “Shogun”, “Burger King”]
输出: [“Shogun”]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
list2 = [“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]

思路：
1、获取两个list的相同元素交集
2、对元素交集构建索引和与元素列表的映射（可能答案不止一个）
3、排序返回索引和最小的元素列表

def func599(list1,list2):
    res=defaultdict(list)
    for char in set(list1) & set(list2):
        res[list1.index(char)+list2.index(char)].append(char)   #defaultdict(<class 'list'>, {3: ['KFC'], 1: ['Shogun'], 4: ['Burger King']})
    return min(res.items())

list1= ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["KFC", "Shogun", "Burger King"]
print(func599(list1,list2))

特别注意：
d={1:‘a’,3:‘g’,5:‘u’}
print(d.items()) dict_items([(1, ‘a’), (3, ‘g’), (5, ‘u’)])
print(max(d.items())) (5, ‘u’)
print(min(d.items())) (1, ‘a’)

二、724. 寻找数组的中心下标

简单
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。
示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

def func724(nums):
    sum_left=0
    sum_right=sum(nums)
    for i in range(len(nums)):
        sum_right=sum_right-nums[i]
        if sum_left == sum_right:
            return i
        sum_left+=nums[i]
    return -1
nums=[6,1,6]
res=func724(nums)
print(res)

三、面试题 16.11. 跳水板

简单
你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
返回的长度需要从小到大排列。

示例 1
输入：
shorter = 1
longer = 2
k = 3
输出： [3,4,5,6]
解释：
可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。以此类推，得到最终结果。

思路：动态规划
最开始全是短木板（k*shorter），然后每次都把上一次的一个短木板变为长木板。

class Solution:
    def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
        if not k:
            return []
        if shorter == longer:
            return [shorter * k]
        result = []
        for i in range(k+1):
            result.append(shorter * (k-i) + longer * i)
        return result

ss=Solution()
shorter = 1
longer = 2
k = 3
print(ss.divingBoard(shorter,longer,k))

四、35. 搜索插入位置

简单
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

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


nums = [1, 3, 5, 6]
target = 5
print(func4(nums, target))

---