力扣初级算法(Python)(二)

简介: 力扣初级算法(Python)(二)

力扣初级算法(Python)(一):https://developer.aliyun.com/article/1538127

6 排序和搜索

6.1 合并两个有序数组

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # 两个中存在空数组的时,直接返回
        if m == 0:
            nums1[:] = nums2[:]
            return
        if n == 0:
            return
 
        index1,index2 = 0,0
        t = []
        while index1<m and index2<n:
            if nums1[index1] <= nums2[index2]:
                t.append(nums1[index1])
                index1 += 1
            else:
                t.append(nums2[index2])
                index2 += 1 
        
        if index1 < m:
            t += nums1[index1:m]
        else:
            t += nums2[index2:n]
 
        nums1[:] = t[:]

6.2 第一个错误的版本

二分搜索

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
 
class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        mid = n//2
        left = 0
        right = n
        while  not self.isFirstBad(mid):
            if isBadVersion(mid):
                right = mid-1 
            else:
                left = mid+1
            mid = (left+right)//2
        return mid
            
 
 
    def isFirstBad(self,n):
        if isBadVersion(n) and not isBadVersion(n-1):
            return True
        else:
            return False

7 动态规划

7.1爬楼梯

直接用递归会在n较大时超时。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1 or n == 2:
            return n
        ans = [0,1,2]
        i = 3
        while i <= n:
            ans.append(ans[i-1]+ans[i-2])
            i +=1
 
        return ans[n]

7.2 买卖股票的最佳时机

只能一次买卖。

所以当前能获得的最大利润为:当前卖出价-之前最低价(price-min_price)。

只要在遍历中更新每一天可获得的最大利润。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        r = 0
        min_price = float('inf')  # float('inf')表示正无穷
        for price in prices:
            min_price = min(min_price, price)  # 截止到当前的最低价(买入价)
            r = max(r, price - min_price)  # 截止到目前的最高利润
        return r

7.3 最大子序和

@yichendai

dp[i] 表示终点在i的子序列的最佳子序和,这样就可以建立其dp[i]和dp[i-1]的关系。

dp[i] = max(dp[i - 1], 0) + nums[i]

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        length = len(nums)
        dp = [0 for i in range(length)]
        max_r = nums[0]
        for i in range(length):
            dp[i] = max(dp[i - 1], 0) + nums[i]
            max_r = max(max_r,dp[i])
 
        return max_r

7.4 打家劫舍

核心就是决定在第i个房间偷还是不偷,偷就是dp[i-2] + nums[2],不偷就是dp[i-1],两者取max。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) <=0 :
            return 0
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0],nums[1])
        dp = [0 for i in nums]
        dp[0] = nums[0]
        dp[1] = max(nums[1],dp[0])
        i = 2
        while i < len(nums) :
            dp[i] = max(dp[i-2]+nums[i],dp[i-1])
            i += 1
        length = len(nums)
        return dp[length-1]

空间优化:实际上每次只会用到dp[i-2]和dp[i-1] ,可以用两个变量代替数组。

@NeilJi

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) <=0 :
            return 0
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0],nums[1])
        pre1 = nums[0]
        pre2 = max(nums[0],nums[1])
        max_r = 0
        i = 2
        while i < len(nums) :
            max_r = max(pre1+nums[i],pre2)
            (pre1,pre2) = (pre2,max_r)
            i += 1
        return  max_r

8 设计问题

8.1 打乱数

主要问题是打乱数组的实现,可以使用随机下标交换

import random
class Solution:
 
    def __init__(self, nums: List[int]):
        self.length = len(nums)
        self.reset_nums = nums[:]
        self.shuffle_nums  = nums[:]
 
 
    def reset(self) -> List[int]:
        return self.reset_nums
 
 
    def shuffle(self) -> List[int]:
        i = 0
        while i < self.length:
            t = random.randint(1,self.length-1)
            self.shuffle_nums[i],self.shuffle_nums[t] = self.shuffle_nums[t],self.shuffle_nums[i]
            i += 1
        return self.shuffle_nums
 
 
 
 
# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

8.2 最小栈

要求在常数时间内检索到最小元素,而栈的push和pop操作都可能改变最小元素。

考虑用一个栈来保存最小元素。

class MinStack:
 
    def __init__(self):
        self.min_v = []
        self.stack = []
 
 
    def push(self, val: int) -> None:
        self.stack.append(val)
        if len(self.min_v) == 0 or  val <= self.min_v[len(self.min_v)-1]:
            self.min_v.append(val)
 
 
    def pop(self) -> None:
        t = self.stack.pop()
        if t ==  self.min_v[len(self.min_v)-1]:
            self.min_v.pop()
 
 
    def top(self) -> int:
        return self.stack[len(self.stack)-1]
 
 
    def getMin(self) -> int:
        return self.min_v[len(self.min_v)-1]
 
 
 
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

9 数学

找规律题

9.1 Fizz Buzz

if else练习

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        list = []
        for i in range(1,n+1):
            if i % 3 == 0 and i % 5 == 0:
                list.append("FizzBuzz")
            elif i % 3 == 0:
                list.append("Fizz")
            elif i % 5 == 0:
                list.append("Buzz")
            else:
                list.append(str(i))
        return list

9.2 计数质数

爱氏筛求质数

class Solution:
    def countPrimes(self, n: int) -> int:
        isPrimes = [True for _ in range(n)]
        count = 0
        for i in range(2,n):
            if isPrimes[i]:
                count += 1
                #埃氏筛,i的倍数不是素数
                for j in range(2*i,n,i):
                    isPrimes[j] = False
        
        return count

9.3 3的幂

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        t = 1
        while  t < n :
            t *= 3
        return True if t == n else False

9.4 罗马数字转整数

可以用字典做

class Solution:
    def romanToInt(self, s: str) -> int:
        store = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        strs = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        maps = dict(zip(strs,store))
        result = 0
        i = 0
        while i < len(s):
            if i+1 < len(s) and s[i:i+2] in maps:
                result += maps.get(s[i:i+2])
                i += 2
            else:
                result += maps.get(s[i:i+1])
                i += 1
        return result

10 其它

前3题和二进制相关,用到位运算符。

10.1 位1的个数

class Solution:
    def hammingWeight(self, n: int) -> int:
        # 第一种解法 使用python特性 bin(3) = ob11
        #return bin(n).count("1")
        
        # 第二种使用 位运算 特性 & 与预算符号,  >> 右进位预算符号
        res = 0
        while n:
            res += n & 1  # res +=  (n & 1) 11&1 =1 , 10&1=0 比较最后一位相同1,不同0
            n >>= 1 # 右滑动进位
        return res

10.2 汉明距离

异或后用10.1求1个数

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        #return bin(x^y).count("1")
        
        cnt = 0
        z = x^y
        while z:
            cnt += z & 1
            z >>= 1
            
        return cnt

10.3 颠倒二进制位

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for i in range(32):
            res <<= 1
            res += (n & 1)
            n >>= 1
            
        return res

10.4 杨辉三角

找规律

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[]for _ in range(numRows)]
        res[0] = [1]
        for i in range(1,numRows):
            res[i].append(1)
            for j in range(0,len(res[i-1])-1):
                res[i].append(res[i-1][j] + res[i-1][j+1])
            res[i].append(1)
 
        return res

10.5 有效的括号

用栈匹配括号

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in range(0,len(s)):
            c = s[i]
            if c == '(' or c =='[' or c =='{':
                stack.append(c)
            else:
                if len(stack) == 0:
                    return False
                left = stack.pop()
                if (c == ')' and left == '(') :
                    continue
                elif (c == ']' and left == '['):
                    continue
                elif (c == '}' and left == '{'):
                    continue
                else: 
                    return False
        
        if len(stack) == 0:
            return True
        else:
            return False

10.6 缺失数字

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        
        length = len(nums)
        jg = [False for _ in range(length+1)]
        for num in nums:
            jg[num] = True
        return jg.index(False)
        

在评论区看到的求和及异或方法。

求和:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
 
        length = len(nums)
        sum_n = (length+1)*length//2
        sum_nums = sum(nums)
        return sum_n - sum_nums

a^b^a = a^a^b = b,  b和a异或两次还等于b。

在下面的循环中,最终nums[i]中存在的数都会异或两次消掉,得到nums[i]中缺失的数。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        length = len(nums)
        xor = 0
        for i in range(length):
            xor  ^= nums[i] ^ (i+1)
        
        return xor
相关文章
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
1天前
|
机器学习/深度学习 数据采集 搜索推荐
Python基于深度学习算法实现图书推荐系统项目实战
Python基于深度学习算法实现图书推荐系统项目实战
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现PCA降维和KNN人脸识别模型(PCA和KNeighborsClassifier算法)项目实战
Python实现PCA降维和KNN人脸识别模型(PCA和KNeighborsClassifier算法)项目实战
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
|
1天前
|
机器学习/深度学习 数据采集 算法
Python实现GWO智能灰狼优化算法优化支持向量机回归模型(svr算法)项目实战
Python实现GWO智能灰狼优化算法优化支持向量机回归模型(svr算法)项目实战