【数据结构与算法】之排序系列-20240202

这里写目录标题

一、389. 找不同

简单
给定两个字符串 s 和 t ，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。

示例 1：
输入：s = “abcd”, t = “abcde”
输出：“e”
解释：‘e’ 是那个被添加的字母。

示例 2：
输入：s = “”, t = “y”
输出：“y”

异或小知识
1.如果两个相同的数字进行异或运算，结果为 0。
2.如果一个数字与 0 进行异或运算，结果仍为该数字本身。
3.这个方法不受顺序限制，因为异或运算具有交换律和结合律。换句话说，异或运算的结果不会受到操作数的顺序影响。
又因为int与str不能直接进行异或运算，所以要将s中取出的字符串用函数ord()转化成相应的ASCII码。最后输出时再用chr()转化成字符即可。
在这个问题中，我们首先对字符串 s 中的所有字符进行异或运算，得到一个结果。
然后，对字符串 t 中的所有字符也进行异或运算，将结果与之前的结果再次进行异或运算。
由于相同的字符进行异或运算的结果为 0，所以对于在 s 中出现过的字符，它们会相互抵消掉，最终的结果为 0。
而对于在 t 中被添加的字符，它们与之前的结果进行异或运算后，结果不为 0，这样就找到了被添加的字符。

classSolution389:deffunc(self, s, t):
        result =0for char in s:
            result = result ^ord(char)for char in t:
            result = result ^ord(char)returnchr(result)

res = Solution389()

s ="abcd"
t ="abcde"print(res.func(s, t))

二、414. 第三大的数

简单
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例 1：
输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例 2：
输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例 3：
输入：[2, 2, 3, 1]
输出：1

解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

classSolution414:deffunc(self, nums):
        nums.sort()
        nums1 =list(set(nums))iflen(nums1)<3:return nums1[-1]else:return nums1[-3]

s = Solution414()
nums =[2,2,1]print(s.func(nums))

三、455. 分发饼干

简单
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

classSolution455:deffunc(self, g, s):
        g.sort()
        s.sort()
        gid =0
        sid =0
        count =0while gid <len(g)and sid <len(s):# 孩子不能超过饼干的个数，饼干不能超过孩子的个数if s[sid]>= g[gid]:
                count +=1
                gid +=1
                sid +=1else:
                sid +=1return count

r = Solution455()
g =[1,4]
s =[1,2,3]print(r.func(g, s))

四、506. 相对名次

简单
给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。

运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：

名次第 1 的运动员获金牌 “Gold Medal” 。
名次第 2 的运动员获银牌 “Silver Medal” 。
名次第 3 的运动员获铜牌 “Bronze Medal” 。
从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 “x”）。
使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。

示例 1：
输入：score = [5,4,3,2,1]
输出：[“Gold Medal”,“Silver Medal”,“Bronze Medal”,“4”,“5”]
解释：名次为 [1st, 2nd, 3rd, 4th, 5th] 。

示例 2：
输入：score = [10,3,8,9,4]
输出：[“Gold Medal”,“5”,“Bronze Medal”,“Silver Medal”,“4”]
解释：名次为 [1st, 5th, 3rd, 2nd, 4th] 。

classSolution:deffindRelateRank(self, nums):
        pairs =[]for i inrange(len(nums)):
            pairs.append([nums[i], i])# [[10,0],[3,1],[8,2],[9,3],[4,4]]
        pairs1 =sorted(pairs, key=lambda x: x[0], reverse=True)# [[10,0],[9,3],[8,2],[4,4],[3,1]]for i inrange(len(nums)):if i ==0:
                nums[pairs1[i][1]]="G"if i ==1:
                nums[pairs1[i][1]]='S'if i ==2:
                nums[pairs1[i][1]]="Bronze Medal"if i >2:
                nums[pairs1[i][1]]=str(i +1)return nums

s = Solution()
nums =[10,3,8,9,4]print(s.findRelateRank(nums))

五、561. 数组拆分

简单
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。

示例 1：
输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：

1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 所以最大总和为 4

示例 2：
输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

思路：
我们先研究一个整数队(a,b)，假设里面较小的是a，那么无论b多大，累加到答案中的就只是a
因此，我们构造(a,b)时，使这两个元素之差尽可能地小，才能尽可能地“不浪费”较大的b
那么方法就出来了，直接对原始数组排个序，相邻元素两两成对即可。

classS:deffunc(self, nums):
        nums.sort()print(nums)
        res =0for i inrange(0,len(nums),2):
            res += nums[i]return res

res = S()
nums =[1,4,3,2]print(res.func(nums))

六、594. 最长和谐子序列

简单
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：
输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]

示例 2：
输入：nums = [1,2,3,4]
输出：2

示例 3：
输入：nums = [1,1,1,1]
输出：0

思路：首先将数组排序，得到递增数组
然后进行遍历一次数组，利用双指针实现类似滑动窗口的功能

classS594:deffunc(self, nums):
        nums.sort()# [1,2,2,2,3,3,5,7]
        res =0
        i =0
        tmp =0for j inrange(1,len(nums)):if nums[j]- nums[i]>1:
                i +=1elif nums[j]- nums[i]==1:
                tmp +=1
                res =max(res, tmp +1)return res

s = S594()
nums =[1,1,1,1]print(s.func(nums))