刷题《面试经典150题》（第九天）

学习目标：

• 刷完面试经典150题
• 链接: 面试经典150题

学习内容：

• 跳跃游戏 II - 力扣（LeetCode）
• H 指数 - 力扣（LeetCode）
• 盛最多水的容器 - 力扣（LeetCode）
• 矩阵置零 - 力扣（LeetCode）
• 最小栈 - 力扣（LeetCode）

学习时间：

4.30

知识点

学习内容：

跳跃游戏 II - 力扣（LeetCode）

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i] i + j < n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达
nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:

输入: nums = [2,3,0,1,4] 输出: 2

这道题可真恶心，想法是用bfs，可是一直超时超时超时！！！

道心破碎，时间怎么来都是超时
抄答案吧呜呜呜

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        maxPos, end, step = 0, 0, 0
        for i in range(n - 1):
            if maxPos >= i:
                maxPos = max(maxPos, i + nums[i])
                if i == end:
                    end = maxPos
                    step += 1
        return step

H 指数 - 力扣（LeetCode）

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h
指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h
篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

示例 1：

输入：citations = [3,0,6,1,5] 输出：3 解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3,
0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
示例 2：

输入：citations = [1,3,1] 输出：1

直接暴力出答案

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        h=1
        if len(citations)==1:
            if citations[0]==0:
                return 0
            else:
                return h
        for i in range(len(citations)):   #一共有n篇论文，h指数介于1和n之间，所以遍历n次
            sum=0           #用来记录引用次数大于h指数的数量
            for j in citations:         #j是每篇论文引用的次数，如果j>h,则sum+1
                if j>=h:
                    sum+=1
                if sum>=h:
                    break           #已经满足当前h指数的要求了
            if sum<h:
                break               #本次的h指数不满足，停止循环
            h+=1
        return h-1
if __name__ == "__main__":
    a=Solution()
    citations = [11,15]
    print(a.hIndex(citations))

盛最多水的容器 - 力扣（LeetCode）

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

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

输入：height = [1,1] 输出：1

终于碰到一道正常题了，这个应该不难吧，如果不懂的话，可以留言，评论。我将秒回复～～～

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left=0
        right = len(height)-1
        max_water = -1
        while left<right:
            max_water=max(max_water,min(height[left],height[right])*(right-left))
            if height[left]<height[right]:
                left+=1
            else:
                right-=1
        return max_water



if __name__ == "__main__":
    a=Solution()
    height=[1,2,1]
    print(a.maxArea(height))

矩阵置零 - 力扣（LeetCode）

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

比上一题还简单

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        r=len(matrix)       #行
        c=len(matrix[0])    #列
        qr=[]   #存行
        qc=[]   #存列
        for i in range(r):
            for j in range(c):
                if matrix[i][j] == 0:
                    if i not in qr:
                        qr.append(i)
                    if j not in qc:
                        qc.append(j)
        for i in qr:    #第i行
            for k in range(c):
                matrix[i][k]=0
        for j in qc:
            for k in range(r):
                matrix[k][j]=0
        return matrix

if __name__ == "__main__":
    a=Solution()
    matrix = [[1,1,1],[1,0,1],[1,1,1]]
    print(a.setZeroes(matrix))

最小栈 - 力扣（LeetCode）

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop()
删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。

示例 1:

输入： [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

class MinStack(object):

    def __init__(self):
        self.stack = []
        self.mins = 1<<32


    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.stack.append(val)
        self.mins = min(self.stack)


    def pop(self):
        """
        :rtype: None
        """
        self.stack.pop()
        if len(self.stack)!=0:
            self.mins = min(self.stack)
        else:
            self.mins = 1<<32


    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]

    def getMin(self):
        """
        :rtype: int
        """
        return self.mins


# 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()
if __name__ == "__main__":
    obj = MinStack()
    obj.push(-2)
    obj.push(0)
    obj.push(-3)
    obj.getMin()
    obj.pop()
    obj.pop()
    obj.top()
    obj.getMin()

最后成果

• 跳跃游戏 II - 力扣（LeetCode）
• H 指数 - 力扣（LeetCode）
• 盛最多水的容器 - 力扣（LeetCode）
• 矩阵置零 - 力扣（LeetCode）
• 最小栈 - 力扣（LeetCode）

结论

道友，加油！！