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").
余下的两名运动员,我们只需要通过他们的成绩计算将其相对名次即可。
提示:
- N 是一个正整数并且不会超过 10000。
- 所有运动员的成绩都不相同。
(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"
提示:
- 该字符串只包含小写英文字母。
- 给定字符串的长度和
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
上一篇: 一文秒懂python正则表达式常用函数