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

LeetCode-Part 3

程序员文章站 2022-03-03 10:53:41
#1460 通过翻转子数组使两个数组相等给你两个长度相同的整数数组target和arr。每一步中,你可以选择arr的任意 非空子数组并将它翻转。你可以执行此过程任意次。如果你能让 arr变得与 target相同,返回 True;否则,返回 False 。思路:第一个思路:判断target中的元素是不是在arr中也有,如果有的话sum+1,最后判断如果sum=target的长度,那就返回True,但是没有考虑出现次数的问题第二个思路:在第一个思路的基础上加......

(最近刷的题还只是简单的,链表二叉树全还给老师了..但是好多这种类型的,要抓紧复习一下~)

#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

相关标签: LeetCode