欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-03 19:59:59
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.下一个更大元素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)思路:
day17_原题496/504/506/507/541
(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

相关标签: leetcode刷题