【数据结构与算法】之字符串系列-20240124

---

一、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)。

思路：
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')

二、657. 机器人能否返回原点

简单
在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。
如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。
注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

示例 1:
输入: moves = “UD”
输出: true
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。

示例 2:
输入: moves = “LL”
输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。

class Solution:
    def func657(self, moves):
        L = -1
        R = 1
        U = 1
        D = -1
        res = 0
        for item in moves:
            if item == 'L':
                res -= 1
            elif item == 'R':
                res += 1
            elif item == 'U':
                res += 1
            else:
                res -= 1
        if res == 0:
            return True
        return False


ss = Solution()
moves = "UD"
print(ss.func657(moves))

三、680. 验证回文串 II

简单
给你一个字符串 s，最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：
输入：s = “aba”
输出：true

示例 2：
输入：s = “abca”
输出：true
解释：你可以删除字符 ‘c’ 。

示例 3：
输入：s = “abc”
输出：false

class Solution680:
    def func1(self, s):
        left = 0
        right = len(s) - 1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            elif s[left] != s[right]:
                return s[left:right] == s[left:right][::-1] or s[left + 1:right + 1] == s[left + 1:right + 1]
        return True


s = Solution680()
strs = "abc"
print(s.func1(strs))

四、796. 旋转字符串

简单

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。
s 的 旋转操作 就是将 s 最左边的字符移动到最右边。
例如, 若 s = ‘abcde’，在旋转一次之后结果就是’bcdea’ 。

示例 1:
输入: s = “abcde”, goal = “cdeab”
输出: true
示例 2:
输入: s = “abcde”, goal = “abced”
输出: false

思路：如果字符串A经过多次旋转之后得到字符串B，那么字符串A拼接后再去掉首尾各一位后一定包含字符串B

def func796(s, goal):
    return goal in (s + s)[1:-1]

s = "abcde"
goal = "abced"
print(func796(s, goal))

五、771. 宝石与石头

简单
给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。
示例 1：
输入：jewels = “aA”, stones = “aAAbbbb”
输出：3

示例 2：
输入：jewels = “z”, stones = “ZZ”
输出：0

def func771(jewels, stones):
    return sum([stones.count(i) for i in jewels])

jewels = "z"
stones = "ZZ"
print(func771(jewels, stones))

---