leetcode刷题总结——数组

77 阅读 0 评论 51 点赞

我是靠谱客的博主斯文电灯胆，最近开发中收集的这篇文章主要介绍leetcode刷题总结——数组，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

输入：nums = [3,3], target = 6
输出：[0,1]

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap=dict()
        for i,num in enumerate(nums):
            if target-num in hashmap:
                return [hashmap[target-num],i]
            hashmap[nums[i]]=i

11. 盛最多水的容器

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l,r = 0, len(height) - 1
        max_area = 0
        while( l < r):
            area = (r - l) * min(height[l], height[r])
            max_area = max(max_area, area)
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return max_area

88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6]

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.
        """
        nums1[m:]=nums2
        nums1.sort()

122. 买卖股票的最佳时机 II

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        n = len(prices)
        for i in range(1,n):
            ans += max(0, prices[i] - prices[i - 1])
        return ans

135. 分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。

输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

正确代码：

class Solution:
    def candy(self, ratings: List[int]) -> int:
        length=len(ratings)
        res=[1]*length
        for i in range(1,length):
            if ratings[i-1]<ratings[i]:
                res[i]=res[i-1]+1
        for i in list(range(length-1,0,-1)):
            if ratings[i]<ratings[i-1]:
                res[i-1]=max(res[i-1],res[i]+1)

        return sum(res)

错误代码：

class Solution:
    def candy(self, ratings: List[int]) -> int:
        length=len(ratings)
        res=[1]*length
        for i in range(1,length):
            if ratings[i-1]>ratings[i]:
                res[i-1]=res[i-1]+1
        for i in range(1,length):
            if ratings[i-1]<ratings[i]:
                res[i]=res[i]+1
        return sum(res)

class Solution:
    def candy(self, ratings: List[int]) -> int:
        length=len(ratings)
        res=[1]*length
        for i in range(1,length):
            if ratings[i-1]<ratings[i]:
                res[i]=res[i-1]+1
        for i in list(range(length-1,0,-1)):
            if ratings[i]<ratings[i-1]:
                res[i-1]=res[i]+1
        return sum(res)

167. 两数之和 II - 输入有序数组

给定一个已按照升序排列的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从 1 开始计数，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2

正确代码：

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        low,high=0,len(numbers)-1
        while low<high:
            if target==numbers[low]+numbers[high]:
                return [low+1,high+1]
            elif target>numbers[low]+numbers[high]:
                low+=1
            else:
                high-=1

错误代码：

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        res=[]
        for num in  numbers:
            if target-num in numbers:
                res.append(numbers.index(num)+1)
                res.append(numbers.index(target-num)+1)
                return res

435. 无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

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

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

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

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

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

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

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

错误代码：

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

452. 用最少数量的箭引爆气球

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x:x[1])
        num =1
        right=points[0][1]
        for i in range (1,len(points)):
            if right<points[i][0]:
                right=points[i][1]
                num+=1
        return num

455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

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

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        a=0
        b=0
        while a<len(g) and b<len(s) :
            if g[a]<=s[b]:
                a+=1
            b+=1
        return a

524. 通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

正确代码

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:

        dictionary.sort(key = lambda x: (-len(x), x))

        for word in dictionary:
            index = 0
            for ch in word:
                index = s.find(ch, index) + 1  # find输出-1:False
                if not index:
                    break
            else:       # 这里用else语句保证break之后不会执行，正常循环结束会执行
                return word
        return ''

错误代码：

如果包含子字符串返回开始的索引值，否则返回-1

>>>info = 'abca'
>>> print info.find('a')    # 从下标0开始，查找在字符串里第一个出现的子串，返回结果：0
0
>>> print info.find('a',1)  # 从下标1开始，查找在字符串里第一个出现的子串：返回结果3
3
>>> print info.find('3')    # 查找不到返回-1
-1
>>>

"abpcplea" ["ale","apple","monkey","plea", "abpcplaaa","abpcllllll","abccclllpppeeaaaa"]

class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
                ## 用好python内置函数sort()、find(),比双指针效率更高
        ## 可以用元组表示多关键字排序，第一关键字是长度降序，第二关键字是字符串本身字典序
        dictionary.sort(key = lambda x: (-len(x), x))

        for word in dictionary:
            for ch in word:
                index = s.find(ch) + 1  # find输出-1:False
                if not index:
                    break
                return word
        return ''

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        hashmap = set()
        for num in nums:
            if num not in hashmap:
                hashmap.add(num)
            else:return num

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

正确代码：判断矩阵是否为空

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:return False 
        i,j=0,len(matrix[0])-1
        while 0<=j and i<len(matrix):
            if target==matrix[i][j]:
                return True
            elif target>matrix[i][j]:
                i+=1
            else:
                j-=1
        return False

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        return list(i for i in range(1,10**n))

剑指 Offer 31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        res,i=[],0
        for num in pushed:
            res.append(num)
            while res and res[-1]==popped[i]:
                res.pop()
                i+=1
        return True if not res else False

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        res=dict()
        length=len(nums)
        for num in nums:
           res[num]=1 if num not in res.keys() else res[num]+1
           if res[num]>length/2:return num

剑指 Offer 40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        return heapq.nsmallest(k,arr)

1418. 点菜展示表

给你一个数组 orders，表示客户在餐厅中完成的订单，确切地说， orders[i]=[customerNamei,tableNumberi,foodItemi] ，其中 customerNamei 是客户的姓名，tableNumberi 是客户所在餐桌的桌号，而 foodItemi 是客户点的餐品名称。

请你返回该餐厅的点菜展示表。在这张表中，表中第一行为标题，其第一列为餐桌桌号 “Table” ，后面每一列都是按字母顺序排列的餐品名称。接下来每一行中的项则表示每张餐桌订购的相应餐品数量，第一列应当填对应的桌号，后面依次填写下单的餐品数量。

注意：客户姓名不是点菜展示表的一部分。此外，表中的数据行应该按餐桌桌号升序排列。

class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        cout=defaultdict(list)
        menu=set()
        #统计订单量
        for order in orders:
            cout[order[1]].append(order[2])
            menu.add(order[2])
        menu_list=list(menu)
        menu_list.sort()
        title=["Table"]+menu_list

        #分配具体的数据，由字典储存转化为数组      
        temp=["0"]*len(title)
        result=[]
        for keys,values in cout.items():
            temp=["0"]*len(title)
            temp[0]=keys
            for value in values:
                index=title.index(value)
                temp[index]= str(int(temp[index])+1)
            result=result+[temp]
        result.sort(key=lambda x:int(x[0]))
        return [title]+result

错误代码：

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        length=len(nums)
        ans=length+1
        i,rk=0,0
        summery=0
        while rk<length :
            summery=summery+nums[rk]
            while summery>=target:
                ans=min(ans,rk-i+1)
                summery-=nums[i]
                i+=1
            rk+=1
        return 0 if ans==length+1 else ans

1711. 大餐计数

大餐是指恰好包含两道不同餐品的一餐，其美味程度之和等于 2 的幂。

你可以搭配任意两道餐品做一顿大餐。

给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同大餐的数量。结果需要对 109 + 7 取余。

注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。

输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。

输入：deliciousness = [1,1,1,3,3,3,7]
输出：15
解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。

1 <= deliciousness.length <= 10^5
0 <= deliciousness[i] <= 2^20

class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:       
        powersOfTwo = [2**i for i in range(23)]
        mod = 10 ** 9 + 7
        cnts, ans = Counter(), 0
        for num in deliciousness:
            for target in powersOfTwo:
                ans += cnts[target - num]
            cnts[num] += 1
        return ans % mod

from collections import Counter
colors = ['red', 'blue', 'red', 'green', 'blue', 'blue']
c = Counter(colors)
print (dict(c))

{'red': 2, 'blue': 3, 'green': 1}

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

class Solution:
    def isValid(self, s: str) -> bool:
        res=[]
        a={')':'(',']':'[','}':'{'}
        #遍历字符串
        for i in s:
            #说明是左括号
            if i not in a:
                #加入栈
                res.append(i)
            #若都是右括号则无效，或者栈里已有左括号，但是i为右括号
            elif not res or a[i]!=res.pop():return False
        return not res

232. 用栈实现队列

class MyQueue(object):

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x):
        self.stack1.append(x)

    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    def peek(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]

    def empty(self):
        return not self.stack1 and not self.stack2

225. 用队列实现栈

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue1 = collections.deque()
        self.queue2 = collections.deque()


    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.queue2.append(x)
        while self.queue1:
            self.queue2.append(self.queue1.popleft())
        self.queue1, self.queue2 = self.queue2, self.queue1


    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.queue1.popleft()


    def top(self) -> int:
        """
        Get the top element.
        """
        return self.queue1[0]


    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return not self.queue1

703. 数据流中的第 K 大元素

class KthLargest:

    def __init__(self, k: int, nums: List[int]):

        self.k = k
        self.que = nums
        heapq.heapify(self.que)

    def add(self, val: int) -> int:

        heapq.heappush(self.que, val)
        while len(self.que) > self.k:
            heapq.heappop(self.que)
        return self.que[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

15. 三数之和

class Solution:
    def threeSum(self, nums):
        n = len(nums)
        nums.sort()
        ans = []
        # 枚举 a
        for first in range(n - 2):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            second = first + 1
            # 枚举 b
            while second < third:
                # 需要和上一次枚举的数不相同
                s = nums[first] + nums[second] + nums[third]
                if s < 0:
                    second += 1
                elif s > 0:
                    third -= 1
                else:
                    ans.append([nums[first], nums[second], nums[third]])
                    # 需要和上一次枚举的数不相同
                    while second < third and nums[second] == nums[second + 1]:
                        second += 1
                    # 需要和上一次枚举的数不相同
                    while second < third and nums[third] == nums[third - 1]:
                        third -= 1
                    second += 1
                    third -= 1
        return ans