day17_原题496/504/506/507/541

1.下一个更大元素I(原题496)

给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
    对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
    对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

示例 2:

输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
    对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
    对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

（1）思路：

题目中已经给出了解题的思路：先拿出nums1中的一个元素 i，然后遍历nums2中的元素查找是否有与 i 相同值的元素，如果有则判断下一个元素 j 是否比相同值的元素值大：是的话就返回 j，否则就返回 -1 ；最后返回 res 的值

（2）代码：

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
    	res = []
    	for i in nums1:
    		for j in nums2[nums2.index(i)+1:]:
    			if j > i:
    				res.append(j)
    				break
    			else:
    				res.append(-1)
    	return res

2. 七进制数（原题504）

给定一个整数，将其转化为7进制，并以字符串形式输出

示例 1:

输入: 100
输出: "202"

示例 2:

输入: -7
输出: "-10"

注意: 输入范围是 [-1e7, 1e7]

（1）思路：

（2）代码：

• 常见的十进制转二进制思路,下问十进制转七进制等问题都是基于下面的代码改写

class Solution:
    def convertToBase2(self, num) :
        array = []	# 定义一个数组，用于存放整除后的商
        while True:
            array.append(str(num % 2))
            num //= 2
            if num == 0:
                break
        return ''.join(array[::-1])		# 列表切片倒序排列后使用join凭接

• 十进制转七进制/八进制/六进制/…

class Solution:
    def convertToBase7(self, num):
        array = []
        if num < 0:
            flag = True
            num = -num
        else:
            flag = False
        while True:
            array.append(str(num % 7)) # 数字7可以为6、5、4、3....十进制转为几进制就写数字几,下同。
            num //= 7
            if num == 0:
                break
        if flag:
            array.append("-")
        return ''.join(array[::-1])

问题二：

• 七进制转十进制

class Solution:
    def convertToBase7(self, num):
        array = []
        if num < 0:
            flag = True
            num = -num
        else:
            flag = False
        n = len(str((num)))
        str_num = str(num)
        count = 0
        sum = 0
        j = 1
        while True:
            for i in str_num:
                count = n - j
                sum = sum + int(i)*(7**count)
                # count += 1
                if j > n:
                    break
                j += 1
            array.append(sum)
            array = str(array)
            return array

3.相对名次（原题506）

给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（“Gold Medal”, “Silver Medal”, “Bronze Medal”）。

(注：分数越高的选手，排名越靠前。)

示例 1:

输入: [5, 4, 3, 2, 1]
输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
解释: 前三名运动员的成绩为前三高的，因此将会分别被授予 “金牌”，“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and "Bronze Medal").
余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。

提示:

1. N 是一个正整数并且不会超过 10000。
2. 所有运动员的成绩都不相同。

（1）思路：

使用ranks维护一个 nums -> 索引的映射。之后对ranks进行降序排列
（2）代码：

• 写法一

class Solution:
    def findRelativeRanks(self, nums):
        ranks = []
        for i in range(len(nums)):
            ranks.append([nums[i], i])
        ranks.sort(key=lambda a: a[0], reverse=True)
        for i in range(len(nums)):
            if i == 0:
                nums[ranks[i][1]] = "Gold Medal"
            if i == 1:
                nums[ranks[i][1]] = "Silver Medal"
            if i == 2:
                nums[ranks[i][1]] = "Bronze Medal"
            if i > 2:
                nums[ranks[i][1]] = str(i + 1)
        return nums

写法二:

class Solution:
    def findRelativeRanks(self, nums):
        num = sorted(nums, reverse=True)		# 降序排序
        ranks = {}								# 设置一个空字典存储数据
        for i in range(len(num)):
            if i == 0:
                ranks[num[i]] = 'Gold Medal'
            elif i == 1:
                ranks[num[i]] = 'Silver Medal'
            elif i == 2:
                ranks[num[i]] = 'Bronze Medal'
            else:
                ranks[num[i]] = num.index(num[i]) + 1	# 其他名次分别额外排序

        new_nums = []
        for element in nums:
            new_nums.append(str(ranks[element]))	# 字典转化为字符串输出
        return new_nums

思考：如果是排名越靠前，分数越低呢？
主要就是将下面的代码

num = sorted(nums, reverse=True)	

改为：

num = sorted(nums, reverse=False)	

4.完美数（原题507）

对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。

给定一个 整数 n， 如果他是完美数，返回 True，否则返回 False

示例：

输入: 28
输出: True
解释: 28 = 1 + 2 + 4 + 7 + 14

（1）思路：

暴力破解法，不断遍历符合要求的数。

（2）代码：

• 超时示范

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        factor = []
        for i in range(1, num):
            if num % i == 0:
                factor.append(i)
        if sum(factor) == num:
            return True
        else:
            return False

• 在枚举时，我们只需要从1到sqrl（n）进行枚举即可，因为如果n有一个大于sqrl的因数x，则一定会有一个小于sqrl(n)的因数n/x。只需要计算到一半就好了，代码如下：

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 1:
            return False
        mid = int(math.sqrt(num))
        result = 0
        i = 2
        while i <= mid:
            if num % i == 0:
                result += i + num / i
            i += 1
        return result + 1 == num

5.反转字符串（原题344）

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

方法一：

（1）思路：

双指针，头尾指针元素相互交换，然后移动指针即可。易错点在于一定要保证左指针小于右指针

（2）代码：

class Solution:
    def reverseString(self, s):
        i = 0
        n = len(s)
        j = n-1
        while (i <= (int(n/2))) and (i<j):
            s[i],s[j] = s[j],s[i]
            i += 1
            j -= 1
        return s

• 优化

class Solution:
    def reverseString(self, s):
        i, j = 0, len(s) - 1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1
        return s

方法二：（纯pyhton）

s.reverse()

s[:] = s[::-1]

for i in range(len(s)//2):
	s[i],s[-i-1]=s[-i-1],s[i]

6.反转字符串II（原题541）

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

输入: s = "abcdefg", k = 2
输出: "bacdfeg"

提示：

1. 该字符串只包含小写英文字母。
2. 给定字符串的长度和 k 在 [1, 10000] 范围内。

（1）思路;

看了一遍题目，通俗一点说就是，每隔k个反转k个，末尾不够k个时全部反转。这里我们直接反转每个2k字符块

（2）代码：

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
    	lst = list(s)
    	for i in range(0,len(lst),2*k):
    		lst[i:i+k] = reversed(lst[i:i+k])
    	return ''.join(lst)

本文地址：https://blog.csdn.net/qq_38824818/article/details/107437320