面试资料

跳跃游戏给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。 示例 1： 123输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 示例 2： 123输入：nums = [3,2,1,0,4]输出：false解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。 提示： 1 <= nums.length <= 104 0 <= nums[i] <= 105 遍历数组，维护一个能到达的最远距离变量maxRange，如果当前遍历到的位置大于上一个maxRange说明此位置不可达，返回fakse 12345678910111213class Solution { public boolean canJump(int[] nums) &# ...

买卖股票的最佳时机给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 1234输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2： 123输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。 提示： 1 <= prices.length <= 105 0 <= prices[i] <= 104 第i天卖出股票赚到的最大利润等于当前股票价格减去之前股票的最低价格 12345678910111213141516c ...

数据流的中位数中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。 例如 arr = [2,3,4] 的中位数是 3 。 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。 实现 MedianFinder 类: MedianFinder() 初始化 MedianFinder 对象。 void addNum(int num) 将数据流中的整数 num 添加到数据结构中。 double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。 示例 1： 12345678910111213输入["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"][[], [1], [2], [], [3], []]输出[null, null, null, 1.5, n ...

前K个高频元素给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 12输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2] 示例 2: 12输入: nums = [1], k = 1输出: [1] 提示： 1 <= nums.length <= 105 k 的取值范围是 [1, 数组中不相同的元素的个数] 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。 统计出来每个元素出现的频率和最大频率maxFre。每轮循环遍历整个哈希表找到频率为maxFre的元素加入答案，循环结束之后maxFre--,直到找到前K个元素。 因为数据范围很大，所以为了节省空间可以找到数组中的最大值和最小值，都减去最小值，将下标映射到从0开始 123456789101112131415161718192021222324252627282930313233class Soluti ...

数组中的第K个最大元素给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 12输入: [3,2,1,5,6,4], k = 2输出: 5 示例 2: 12输入: [3,2,3,1,2,4,5,5,6], k = 4输出: 4 提示： 1 <= k <= nums.length <= 105 -104 <= nums[i] <= 104 使用快速选择算法，快速选择每一趟结束之后，就找到了哨兵最终的位置，并且哨兵左边的所有元素都小于等于哨兵，右边的元素都大于等于哨兵，跟据下标判断要返回的元素在左边还是右边，只递归其中一边，平均时间复杂度是O(n) 123456789101112131415161718192021222324252627class Solution { int n = 0; public int findKthLargest(int[] n ...

柱形图中最大的矩形给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 示例 1: 123输入：heights = [2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为 10 示例 2： 12输入： heights = [2,4]输出： 4 提示： 1 <= heights.length <=105 0 <= heights[i] <= 104 用每个柱子的长度都作为高求出最大矩形面积就是答案。高度已经确定了就是柱子的高，宽度是从该柱子向左向右出发能扩展多少距离。当遇到左边第一个比它低的柱子停下来，遇到右边第一个比他低的柱子停下来，这就是最大的宽度。问题就变成了求元素左右两边距离最近的小于元素的值，用单调栈解决。 1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { public int largestR ...

每日温度给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 示例 1: 12输入: temperatures = [73,74,75,71,69,72,76,73]输出: [1,1,4,2,1,1,0,0] 示例 2: 12输入: temperatures = [30,40,50,60]输出: [1,1,1,0] 示例 3: 12输入: temperatures = [30,60,90]输出: [1,1,0] 提示： 1 <= temperatures.length <= 105 30 <= temperatures[i] <= 100 单调栈用来快速求出某个元素左边比它小（大）的最近元素，和右边比它小（大）的最近元素。 对于大压小的栈： 如果当前元素比栈顶大，直接入栈 如果当前元素比栈顶小，将栈顶元素弹出，当前元素为栈顶元素的右边更小的最近元素，新栈顶元素为原栈顶元素左边最近更小 ...

字符串解码给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。 示例 1： 12输入：s = "3[a]2[bc]"输出："aaabcbc" 示例 2： 12输入：s = "3[a2[c]]"输出："accaccacc" 示例 3： 12输入：s = "2[abc]3[cd]ef"输出："abcabccdcdcdef" 示例 4： 12输入：s = "abc3[cd]xyz"输出："abccdcdcdxyz" 提示： 1 <= s.length <= 30 s ...

最小栈设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。 示例 1: 12345678910111213141516输入：["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);mi ...

有效的括号给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 示例 1： 输入：s = “()” 输出：true 示例 2： 输入：s = “()[]{}” 输出：true 示例 3： 输入：s = “(]” 输出：false 示例 4： 输入：s = “([])” 输出：true 提示： 1 <= s.length <= 104 s 仅由括号 '()[]{}' 组成 利用栈来存储括号，如果是左括号直接进，如果是右括号，从栈顶检测是否有匹配的左括号，如果没有或栈为空，返回false,全部遍历完毕且栈为空，返回true 123456789101112131415161718192021222324cl ...