已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到： 注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。 给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 你必须尽可能减少整个过程的操作步骤。 示例 1： 示例 2： 提示： 进阶：这道题与 寻找旋转排序数组中的最小值 类似，但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？ 解题： 官方解答： 1.二分查找
Month: April 2023
LeetCode 153 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 你必须设计一个时间复杂度为O(log n) 的算法解决此问题。 示例 1： 示例 2： 示例 3： 提示： 解题： 官方解答： 1.二分查找
LeetCode 152 乘积最大子数组
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个32-位 整数。 子数组 是数组的连续子序列。 示例 1: 示例 2: 提示: 解题： 官方解答： 1.动态规划
LeetCode 151 反转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。 示例 1： 示例 2： 示例 3： 提示： 进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用O(1) 额外空间复杂度的 原地 解法。 解题： 官方解答：
LeetCode 150 逆波兰表达式求值
给你一个字符串数组 tokens ，表示一个根据逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意： 示例1： 示例2： 示例3： 提示： 逆波兰表达式： 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。 逆波兰表达式主要有以下两个优点： 解题： 官方解答： 1.栈 2.数组模拟栈
LeetCode 149 直线上最多的点数
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。 示例 1： 示例 2： 提示： 解题： 官方解答： 1.哈希表
LeetCode 148 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 示例 1： 示例 2： 示例 3： 提示： 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 解题： 昨天的方法拿过来结果超时了。。。 官方解答： 1.自顶向下归并排序 2.自底向上归并排序
LeetCode 147 对链表进行插入排序
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。 插入排序 算法的步骤: 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。 对链表进行插入排序。 示例 1： 示例 2： 提示： 解题： 官方解答： 1.从前往后找插入点
LeetCode 146 LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现 LRUCache 类： 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 示例： 提示： 解题： 代码超时了。。。 官方解答： 1.哈希表 + 双向链表