leetcode刷题记录

1. 爬楼梯

import numpy as np
class Solution:
    def climbStairs(self, n: int) -> int:
        res=np.zeros(n+1,np.int)
        res[0],res[1]=1,1
        for i in range(2,n+1):
            res[i] = res[i - 1] + res[i - 2]
        return int(res[n])

 2.强盗抢劫

题目描述：抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以

import numpy as np
import math
class Solution:
    #初始化比较麻烦 dp[0]=nums[0] dp[1]=max(nums[0],nums[1]) 
    #递推公式 dp[i]=max(dp[i-1],dp[i-2]+nums[i])
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if(len(nums)==1):
            return nums[0]
        dp=np.zeros(len(nums)+1,np.int)
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])
        for index in range(2,len(nums)):
            dp[index]=max(dp[index-1],dp[index-2]+nums[index])
        return int(dp[len(nums)-1])

3.强盗在环形街区抢劫

这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

import numpy
class Solution:
    def rob(self, nums: List[int]) -> int:
        #一个是从0到n-1，另一个是从1到n
        if not nums:
            return 0
        if(len(nums)==1):
            return nums[0]
        if(len(nums)==2):
            return max(nums[0],nums[1])
        dp1,dp2=numpy.zeros(len(nums),numpy.int),numpy.zeros(len(nums),numpy.int)
        dp1[0]=nums[0]
        dp1[1]=max(nums[1],nums[0])
        for index1 in range(2,len(nums)-1):
            dp1[index1]=max(dp1[index1-1],dp1[index1-2]+nums[index1])
        nums2=nums[1:]
        dp2[0]=nums2[0]
        dp2[1]=max(nums2[0],nums2[1])
        for index2 in range(2,len(nums)-1):
            dp2[index2]=max(dp2[index2-1],dp2[index2-2]+nums2[index2])
        return int(max(dp1[len(nums)-2],dp2[len(nums)-2]))

4.最短路径的和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

import numpy as np
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        #初始化 dp[0][0] = grid[0][0];
        #第一行第一列均为之前求和
        #dp[row][col]=min(dp[row-1][col],dp[row][col-1])+grid[row][col]
        rows=len(grid)
        cols=len(grid[0])
        dp=np.zeros((rows,cols),dtype=np.int32)
        dp[0][0] = grid[0][0];
        for row in range(1,rows):
            dp[row][0]=dp[row-1][0]+grid[row][0]
        for col in range(1,cols):
            dp[0][col]=dp[0][col-1]+grid[0][col]
        for row in range(1,rows):
            for col in range(1,cols):
                dp[row][col]=min(dp[row-1][col],dp[row][col-1])+grid[row][col]
        return int(dp[rows-1][cols-1])

5.矩阵的总路径数

import numpy as np
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        #初始状态第一行第一列全是1
        #dp[i][j]=dp[i-1][j]+dp[i][j-1]
        dp=np.zeros((m,n),np.int32)
        for i in range(m):
            for j in range(n):
                if(i==0 or j==0):
                    dp[i][j]=1
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
        return int(dp[m-1][n-1])

6:数组中等差递增子区间的个数

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，以下数列为等差数列:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。

1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。如果满足以下条件，则称子数组(P, Q)为等差数组：元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

import numpy as np
class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        #dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。
        # dp[2] = 1
        # [0, 1, 2]
        # dp[3] = dp[2] + 1 = 2
        # [0, 1, 2, 3], // [0, 1, 2] 之后加一个 3
        # [1, 2, 3]     // 新的递增子区间
        # dp[4] = dp[3] + 1 = 3
        # [0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4
        # [1, 2, 3, 4],    // [1, 2, 3] 之后加一个 4
        # [2, 3, 4]        // 新的递增子区间
        if not A or len(A)<=2:
            return 0
        dp=np.zeros(len(A),np.int)
        dp[0],dp[1]=0,0
        for i in range(2,len(A)):
            if(A[i]-A[i-1]==A[i-1]-A[i-2]):
                dp[i]=dp[i-1]+1        
        return int(sum(dp))

 7.分割整数的最大乘积

import numpy as np
class Solution:
    def integerBreak(self, n: int) -> int:
        #dp[i]表示整数i对应的最大乘积，dp[i]的值应是dp[j]*(i-j),j属于[1,i-1]的最大值，
        #同时注意dp[i]对应的值是经过拆分了的，所以还应判断两个数拆分的情况，即j*(i-j)的值，取最大即可。像2拆成1+1，积是1
        dp=np.zeros(n+1,np.int)
        dp[0],dp[1]=0,0
        for i in range(2,n+1):
            for j in range(0,i):
                dp[i]=max(dp[i],dp[j]*(i-j),j*(i-j))
        return dp[n]

8. 按平方数来分割整数

import numpy as np
import math
class Solution:
    def numSquares(self, n: int) -> int:
        #dp[i]表示i平方和最小所需要的个数
        #dp[i]=min(dp[i],dp[i-j*j]+1)
        dp=np.zeros(n+1,np.int)
        dp[0],dp[1]=0,1
        for i in range(2,n+1):
            dp[i]=i
            for j in range(1,int(math.sqrt(i))+1):
                dp[i]=min(dp[i],dp[i-j*j]+1)
        return int(dp[n])

9. 最长递增子序列

import numpy as np
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp=np.zeros(len(nums),np.int)
        dp[0]=1
        for i in range(1,len(nums)):
            dp[i]=1
            for j in range(0,i):
                if(nums[i]>nums[j]):
                    dp[i]=max(dp[i],dp[j]+1)
        return int(max(dp))

10.最长数对链

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 :

输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]

import numpy as np
class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        #dp[i]表示以第i 个元素结尾最多书对链长度
        #dp[i]=max(dp[j]+1,dp[i])
        #返回列表中最大的
        dp=[0]*len(pairs)
        dp[0]=1
        pairs.sort(key = lambda x:x[1])
        for i in range(1,len(pairs)):
            dp[i]=1
            for j in range(i):
                if(pairs[j][1]<pairs[i][0]):
                    dp[i]=max(dp[j]+1,dp[i])
        return max(dp)

11:最长波动序列个数

import numpy as np
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        #首先对list进行去重
        #dp[i]代表下标i之前的最大,如果是当前元素是摆动dp[i]=dp[i-1]+1,否则dp[i]=dp[i-1]
        result=[]
        if not nums:
            return 0
        result.append(nums[0])
        for i in range(1,len(nums)):
            if(nums[i]!=nums[i-1]):
                result.append(nums[i])
        if(len(result)<=2):
            return len(result)
        dp=np.zeros(len(result),np.int)
        dp[0],dp[1]=1,2
        for i in range(2,len(result)):
            if((result[i]-result[i-1])*(result[i-1]-result[i-2])<0):
                dp[i]=dp[i-1]+1
            else:
                dp[i]=dp[i-1]
        return dp[len(result)-1]

12:最长公共子序列

import numpy as  np
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m,n=len(text1),len(text2)
        dp=np.zeros((m+1,n+1),np.int)
        for i in range(1,m+1):
            for j in range(1,n+1):
                if(text2[j-1]==text1[i-1]):
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        return dp[m][n]

待定更新

双指针问题

1、两数之和 II - 输入有序数组

题目描述：在有序数组中找出两个数，使它们的和为 target。

使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

• 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
• 如果 sum > target，移动较大的元素，使 sum 变小一些；
• 如果 sum < target，移动较小的元素，使 sum 变大一些。

数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        list=[]
        first,latest=0,len(numbers)-1
        while(first<latest):
            if(numbers[first]+numbers[latest]==target):
                list.append(first+1)
                list.append(latest+1)
                return list
            elif(numbers[first]+numbers[latest]>target):
                latest=latest-1
            else:
                first=first+1

2.平方数之和

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

题目描述：判断一个非负整数是否为两个整数的平方和。

可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。

本题和 167. Two Sum II - Input array is sorted 类似，只有一个明显区别：一个是和为 target，一个是平方和为 target。本题同样可以使用双指针得到两个数，使其平方和为 target。

本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。

因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。

import math
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        first,latest=0,int(math.sqrt(c))
        while(first<=latest):
            sum=first*first+latest*latest
            if(sum==c):
                return True
            elif(sum>c):
                latest=latest-1
            else:
                first=first+1
        return False

3.反转字符串中元音字母

class Solution:
    def reverseVowels(self, s: str) -> str:
        first,latest=0,len(s)-1
        char_list=['a','o','e','i','u','A','E','I','O','U']
        temp_list=[]
        #str字符串可以看成数组，但是不能修改
        for ele in s:
            temp_list.append(ele)
        while(first<latest):
            if(temp_list[first] in char_list and temp_list[latest] in char_list):
                temp=temp_list[first]
                temp_list[first]=temp_list[latest]
                temp_list[latest]=temp
                first+=1
                latest-=1
            elif(temp_list[first] in char_list and temp_list[latest] not in char_list):
                latest-=1
            else:
                first+=1
        result=''
        for ele in temp_list:
            result+=ele
        return result

4:回文子串

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

class Solution:
    def validPalindrome(self, s: str) -> bool:
        first,late=0,len(s)-1
        for i in range(int(len(s)/2)):
            if(s[i]==s[late-i]):
                continue
            else:
                return self.judge(s,i+1,late-i) or self.judge(s,i,late-i-1)
        return True
        
    def judge(self,s,i,j):
        first,late=i,j
        count=0
        while(first<late):
            if(s[first]==s[late]):
                first+=1
                late-=1
            else:
                return False
        return True

5:链表是否有环

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        p,q=head,head
        if(head==None or head.next==None):
            return False
        while(q.next!=None and p!=None):
            p=p.next
            q=q.next.next
            if(p==q):
                return True
        return False

3.贪心思想

1、分饼干问题

输入: [1,2,3], [1,1]

输出: 1

解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        m,n=len(g),len(s)
        g.sort()
        s.sort()
        i,j,count=0,0,0
        while(i<m and j<n):
            if(g[i]<=s[j]):
                count+=1
                i+=1
                j+=1
            else:
                j+=1
        return count

2.无重叠区间（求删除个数）

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x:x[1])
        count=1
        end=intervals[0][1]
        for i in range(1,len(intervals)):
            if(intervals[i][0]>=end):
                count+=1
                end=intervals[i][1]
            else:
                continue
        return len(intervals)-count

3.飞镖气球

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        #求不重叠区间个数，就是飞镖个数
        if not points:
            return 0
        points.sort(key=lambda x:x[1])
        count=1
        end=points[0][1]
        for i in range(1,len(points)):
            if(points[i][0]<=end):
                continue
            end=points[i][1]
            count+=1
        return count

4.买卖股票（一次交易）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #一次交易
        if not prices:
            return 0
        max_profit=0
        min_price=prices[0]
        for i in range(1,len(prices)):
            min_price=min(prices[i],min_price)
            max_profit=max(max_profit,prices[i]-min_price)
        return max_profit

5.买卖股票（多次交易）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #多次交易
        if not prices:
            return 0
        sum_profit=0
        for i in range(1,len(prices)):
            if(prices[i]>prices[i-1]):
                sum_profit+=prices[i]-prices[i-1]
        return sum_profit

6.种花问题

题目描述：flowerbed 数组中 1 表示已经种下了花朵。花朵之间至少需要一个单位的间隔，求解是否能种下 n 朵花。

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        #只需要判断前后即可，防止考虑边界问题，在前后加上[0]，只要连续出现在三个[0]就可以种花
        flowerbed=[0]+flowerbed+[0]
        count=0
        for i in range(1,len(flowerbed)-1):
            if(flowerbed[i-1]==0 and flowerbed[i]==0 and flowerbed[i+1]==0):
                flowerbed[i]=1
                count+=1
        if(count>=n):
            return True
        else:
            return False
        

4.栈与队列

1.判断括号

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

2:数组中元素与下一个比它大的元素之间的距离（气温问题）

Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

import numpy as np
class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack=[]
        res=np.zeros(len(T),np.int)
        stack.append(0)
        for cur_index in range(1,len(T)):
            while(len(stack)!=0 and T[cur_index]>T[stack[-1]]):#判断条件
                pre_index=stack.pop()
                res[pre_index]=cur_index-pre_index
            stack.append(cur_index)
        return res

3.