一、15. 三数之和
提示
中等
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
class Solution:
def threeSum(self,nums):
res=[]
nums.sort()
n=len(nums)
if n<3:
return []
for i in range(n):
if nums[i]>0:
return res
L=i+1
R=n-1
while L<R:
if nums[i]+nums[L]+nums[R]==0:
res.append([nums[i],nums[L],nums[R]])
while L<R and nums[L]==nums[L+1]:
L=L+1
while L<R and nums[R]==nums[R-1]:
R=R-1
L=L+1
R=R-1
elif nums[i]+nums[L]+nums[R]>0:
R=R-1
else:
L=L+1
return res
nums = [-1, 0, 1, 2, -1, -4]
res = Solution()
rrr = res.threeSum(nums)
print(rrr)
二、16. 最接近的三数之和
中等
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1
输出：0
思路：排序+双指针
我们将数组排序，然后遍历数组，对于每个元素nums[i],我们使用指针j和k分别指向i+1和n-1
计算三数之和，如果三数和等于target，则直接返回target，否则根据与target的差值更新答案
如果三数之和大于target，则将R向左移动一位，否则将L向右移动一位。
class Solution:
def threeSumClosest(self,nums,target):
ans=inf
nums.sort()
n=len(nums)
if n<3:
return []
for i in range(n):
L=i+1
R=n-1
while L<R:
if nums[i]+nums[L]+nums[R]==target:
return target
t=nums[i]+nums[L]+nums[R]
if abs(t-target)<abs(ans-target):
ans=t
if t>target:
R=R-1
else:
L=L+1
return ans
s = Solution()
nums = [-1, 2, 1, -4]
target = 1
print(s.threeSumClosest(nums, target))
特别注意：
from math import inf是从math库中导入inf常量。
inf表示正无穷大的数值。它可以用于比较和计算中的特殊情况。
以下是一个示例代码，演示了如何使用inf常量：
from math import inf
# 比较inf常量
print(inf > 100) # 输出：True
print(inf < 1000) # 输出：False
# 计算inf常量
print(inf + 10) # 输出：inf
print(inf * 2) # 输出：inf
print(inf / 3) # 输出：inf
在上面的示例中，我们可以看到inf常量与其他数值进行比较时，inf常量始终被认为是最大的数值。
在计算中，任何数值与inf常量相加、相乘或相除，结果都将是inf常量。
三、49. 字母异位词分组
中等
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
class Solution:
def func(self,strs):
d=defaultdict(list)
for item in strs:
key=''.join(sorted(item))
d[key].append(item)
return list(d.values())
ss=Solution()
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(ss.func(strs))
四、53. 最大子数组和
中等
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
class S53:
def func(self, nums):
result = 0 # 存放结果
count = 0 # 记录累加和
for i in range(len(nums)):
count += nums[i]
if count > result: # 取区间累计的最大值（相当于不断确定最大值子序终止位置）
result = count
if count <= 0: # 相当于重置最大子序列起始位置，因为遇到附属一定拉低总和
count = 0
return result
r = S53()
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(r.func(nums))
五、189. 轮转数组
中等
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
思路：
先整体反转数组，即反转[0,n-1]区间
然后分别反转[0,k-1]和[k,n-1]区间即为结果
具体举例如下：
例如将4-5-6-7-8向右轮转3个位置。即k=3。首先整体翻转
然后分别翻转[0,k−1]和[k,n−1]（先后无所谓）
如下翻转8-7-6
再翻转5-4，得到最后的结果
class Solution:
def retate(self,nums,k):
k=k%len(nums) #映射后的下标的位置
self.reverse(nums,0,len(nums)-1)
self.reverse(nums,0,k-1)
self.reverse(nums,k,len(nums)-1)
return nums
def reverse(self,nums,start,end):
while start<end:
nums[start],nums[end]=nums[end],nums[start]
start+=1
end-=1
ss=Solution()
nums = [1,2,3,4,5,6,7]
k = 3
print(ss.retate(nums, k))
六、179. 最大数
中等
相关标签
相关企业
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2]
输出：“210”
示例 2：
输入：nums = [3,30,34,5,9]
输出：“9534330”
思路：1、先将列表的数字通过map函数映射为字符串，再转化为列表
2、将列表中的字符，通过sorted方法按照降序排序
3、遍历字符串，如果相邻两个字符的首字符相同，判断当前字符的末尾与下一个字符的首位进行比较，如果当前字符的末位小于下一个字符的首位，则进行交换位置
def fn(nums):
#todo 1先根据首位排序
s = list(map(str, nums)) #利用map映射函数
print(s) #['3', '30', '34', '5', '9']
ordered = sorted(s, key=lambda x: x, reverse=True) #通过sorted降序排序
print(ordered) #['9', '5', '34', '30', '3']
#todo 2、首位相同的，进行二次排序
for i in range(len(ordered) - 1):
#todo 如果相邻两个字符的首字符相同，
if ordered[i][0] == ordered[i + 1][0]:
# todo 判断当前字符的末尾与下一个字符的首位进行比较，
#todo 如果当前字符的末位小于下一个字符的首位，则进行交换位置
if int(ordered[i][-1]) < int(ordered[i + 1][0]):
ordered[i], ordered[i + 1] = ordered[i + 1], ordered[i]
return ''.join(ordered)
nums = [10,2]
res=fn(nums)
print(res)
