LeetCode-Part 3
(最近刷的题还只是简单的,链表二叉树全还给老师了..但是好多这种类型的,要抓紧复习一下~)
#1460 通过翻转子数组使两个数组相等
给你两个长度相同的整数数组 target 和 arr 。
每一步中,你可以选择 arr 的任意 非空子数组 并将它翻转。你可以执行此过程任意次。
如果你能让 arr 变得与 target 相同,返回 True;否则,返回 False 。
思路:
第一个思路:判断target中的元素是不是在arr中也有,如果有的话sum+1,最后判断如果sum=target的长度,那就返回True,但是没有考虑出现次数的问题
第二个思路:在第一个思路的基础上加上判断次数,如果target[i]的次数=arr[i]的次数,sum+count(i),但是当一个元素出现多次的时候,毙
最终的思路:对两个数组进行排序,然后当target[i]=arr[i]的时候sum+1,最后判断sum是否等于target的长度
代码:
class Solution:
def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
sum = 0
target.sort()
arr.sort()
for i in range(len(target)):
if target[i] == arr[i]:
sum += 1
else:
continue
if sum == len(target):
return True
else:
return False
#728 自除数
自除数 是指可以被它包含的每一位数除尽的数。
例如,128 是一个自除数,因为 128 % 1 == 0,128 % 2 == 0,128 % 8 == 0。
还有,自除数不允许包含 0 。
给定上边界和下边界数字,输出一个列表,列表的元素是边界(含边界)内所有的自除数。
思路:
对于区间的数字:
如果该数字中含0,则肯定不是自除数,跳过。
如果该数字能将该数中含有的每位数字整除,则该数为自除数,此处要满足的条件是每位都可以整除,所以判断条件可以改为否定的,如果有一个不能整数,则跳出循环
代码:
class Solution:
def selfDividingNumbers(self, left: int, right: int) -> List[int]:
res = []
res=[]
for i in range(left,right+1):
if '0' in str(i):
continue
for j in str(i):
if i%int(j)!=0:
break
else:
res.append(i)
return res
面试题 01.01 判定字符是否唯一
实现一个算法,确定一个字符串 s
的所有字符是否全都不同。
思路:
本题是判断字符串中的每个字符是否只出现一次,直接用set()将原字符转成集合
(set() 函数创建一个无序不重复元素集,可进行关系测试,删除重复数据,还可以计算交集、差集、并集等。)
然后判断set()之后的长度和原字符串的长度是否相等,若相等则为True,反之为False
代码:
class Solution:
def isUnique(self, astr: str) -> bool:
bstr = set(astr)
if len(astr) == len(bstr):
return True
else:
return False
剑指Offer 50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。
思路:
一次遍历,如果某一个在字符串中出现的次数为1,则返回该字符并跳出循环;如果遍历到最后也没有出现这样的字符则返回空格
代码:
class Solution:
def firstUniqChar(self, s: str) -> str:
for i in s:
if s.count(i) == 1:
return i
break
return " "
剑指Offer 21.调整数组顺序使奇数位于偶数前边
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。
思路:
建立两个空数组,遍历原数组,把奇数偶数分别放在不同的空数组中,最后返回两个数组的和
代码:
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
a = []
b = []
for i in nums:
if i%2 != 0:
a.append(i)
else:
b.append(i)
return a+b
剑指Offer 57. 和为s的两个数字
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
思路:
两重循环太low了
然后就有了这个思路,遍历一次,判断target-i是否在数组中
至于为什么转成集合,因为提交的时候发现系统测试的输入有几页那么多........提示我超出时间限制,然后看到别人讲(in 在列表里面搜索是O(n)复杂度,但在集合里是O(1))
代码:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums = set(nums)
a = []
for i in nums:
if (target-i) in nums:
a.append(i)
a.append(target-i)
break
return a
剑指Offer 03.数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
思路:
第一种思路是先遍历,然后判断每一个i在数组中出现的次数是不是1,若不是一则返回,但是太费时间了,于是——
第二种:先排序,这样相同的数字会在一起,再遍历,如果某一个元素和它临近的一个相同,则返回。
代码:
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums)-1):
if nums[i] == nums[i+1]:
return nums[i]
break
剑指Offer 53-|| 0~n-1缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
思路:
等差数列求和,把不缺数字的数列和求出来,然后减去数组的求和就得出不在该数组的数字
代码:
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = len(nums)*(len(nums)+1)/2
return int(res - sum(nums))
#977 有序数组的平方
给定一个按非递减顺序排序的整数数组 A
,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。
思路:
一次遍历,用第i个元素的平方替换该元素,最后对新得到的数组进行排序
代码:
class Solution:
def sortedSquares(self, A: List[int]) -> List[int]:
for i in range(len(A)):
A[i] = A[i]*A[i]
A.sort(reverse=False)
return A
#1491 去掉最低工资和最高工资后的工资平均值
给你一个整数数组 salary ,数组里每个数都是 唯一 的,其中 salary[i] 是第 i 个员工的工资。
请你返回去掉最低工资和最高工资以后,剩下员工工资的平均值。
思路:
移除数组中最大值和最小值,然后sum求和除以长度
代码:
class Solution:
def average(self, salary: List[int]) -> float:
salary.remove(max(salary))
salary.remove(min(salary))
b = sum(salary)/len(salary)
return b
本文地址:https://blog.csdn.net/qq_34253926/article/details/107638550
上一篇: C语言if选择结构语句详解
下一篇: Python求算数平方根和约数的方法汇总