LeetCode:LRU 缓存机制

题目

前言:

推荐官方题解:https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/

注:对高性能的 LRU 理解,会有一定提升作用

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制

实现 LRUCache 类:

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • · 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
阅读更多

LeetCode:有序数组中的单一元素

题目

给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。

示例 1:

1
2
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
阅读更多

LeetCode:动物收容所

题目

动物收容所。有家动物收容所只收容狗与猫,且严格遵守“先进先出”的原则。在收养该收容所的动物时,收养人只能收养所有动物中“最老”(由其进入收容所的时间长短而定)的动物,或者可以挑选猫或狗(同时必须收养此类动物中“最老”的)。换言之,收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构,实现各种操作方法,比如enqueuedequeueAnydequeueDogdequeueCat。允许使用Java内置的LinkedList数据结构。

enqueue方法有一个animal参数,animal[0]代表动物编号,animal[1]代表动物种类,其中 0 代表猫,1 代表狗。

dequeue*方法返回一个列表[动物编号, 动物种类],若没有可以收养的动物,则返回[-1,-1]

示例1:

1
2
3
4
5
 输入:
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
输出:
[null,null,null,[0,0],[-1,-1],[1,0]]
阅读更多

LeetCode:前 K 个高频元素

题目

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

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

示例 2:

1
2
输入: nums = [1], k = 1
输出: [1]
阅读更多

LeetCode:实现 strStr()

题目

实现 strStr() 函数。

给你两个字符串 haystackneedle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回  -1

说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1:

1
2
输入:haystack = "hello", needle = "ll"
输出:2
阅读更多

LeetCode:移除元素

题目

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地修改输入数组

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

阅读更多

LeetCode:判断能否形成等差数列

题目

给你一个数字数组 arr

如果一个数列中,任意相邻两项的差总等于同一个常数,那么这个数列就称为 等差数列

如果可以重新排列数组形成等差数列,请返回 true ;否则,返回 false

示例 1:

1
2
3
输入:arr = [3,5,1]
输出:true
解释:对数组重新排序得到 [1,3,5] 或者 [5,3,1] ,任意相邻两项的差分别为 2 或 -2 ,可以形成等差数列。
阅读更多

LeetCode:最大数

题目

给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

示例 1:

1
2
输入:nums = [10,2]
输出:"210"
阅读更多

LeetCode:提莫攻击

题目

在《英雄联盟》的世界中,有一个叫 “提莫” 的英雄,他的攻击可以让敌方英雄艾希(编者注:寒冰射手)进入中毒状态。现在,给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间,你需要输出艾希的中毒状态总时长。

你可以认为提莫在给定的时间点进行攻击,并立即使艾希处于中毒状态。

示例1:

1
2
3
4
5
输入: [1,4], 2
输出: 4
原因: 第 1 秒初,提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟,直到第 2 秒末结束。
第 4 秒初,提莫再次攻击艾希,使得艾希获得另外 2 秒中毒时间。
所以最终输出 4 秒。
阅读更多

LeetCode:有序数组中出现次数超过25%的元素

题目

给你一个非递减的 有序 整数数组,已知这个数组中恰好有一个整数,它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

示例:

1
2
输入:arr = [1,2,2,6,6,6,6,7,10]
输出:6
阅读更多

LeetCode:搜索旋转排序数组 II

题目

已知存在一个按非降序排列的整数数组 nums ,数组中的值不必互不相同。

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4]

给你 旋转后 的数组 nums 和一个整数 target ,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ,则返回 true ,否则返回 false

阅读更多

LeetCode:删除有序数组中的重复项 II

题目

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现两次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

阅读更多

LeetCode:检查两个字符串数组是否相等

题目

给你两个字符串数组 word1word2 。如果两个数组表示的字符串相同,返回 true ;否则,返回 false

数组表示的字符串 是由数组中的所有元素 按顺序 连接形成的字符串。

示例 1:

1
2
3
4
5
6
输入:word1 = ["ab", "c"], word2 = ["a", "bc"]
输出:true
解释:
word1 表示的字符串为 "ab" + "c" -> "abc"
word2 表示的字符串为 "a" + "bc" -> "abc"
两个字符串相同,返回 true
阅读更多

LeetCode:笨阶乘

题目

通常,正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如,factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

相反,我们设计了一个笨阶乘 clumsy:在整数的递减序列中,我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符:乘法(*),除法(/),加法(+)和减法(-)。

例如,clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而,这些运算仍然使用通常的算术运算顺序:我们在任何加、减步骤之前执行所有的乘法和除法步骤,并且按从左到右处理乘法和除法步骤。

另外,我们使用的除法是地板除法(floor division),所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数:给定一个整数 N,它返回 N 的笨阶乘。

阅读更多

LeetCode:电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

阅读更多

LeetCode:颜色分类

题目

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 12 分别表示红色、白色和蓝色。

示例 1:

1
2
输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]
阅读更多

LeetCode:变位词组

题目

编写一种方法,对字符串数组进行排序,将所有变位词组合在一起。变位词是指字母相同,但排列不同的字符串。

注意:本题相对原题稍作修改

示例:

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
阅读更多

LeetCode:整数反转

题目

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31,  2^31 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

示例 1:

1
2
输入:x = 123
输出:321
阅读更多

LeetCode:平方数之和

题目

给定一个非负整数 c ,你要判断是否存在两个整数 ab,使得 a2 + b2 = c

示例 1:

1
2
3
输入:c = 5
输出:true
解释:1 * 1 + 2 * 2 = 5
阅读更多

LeetCode:被围绕的区域

题目

给你一个 m x n 的矩阵 board ,由若干字符 'X''O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O''X' 填充。

示例 1:

阅读更多

LeetCode:统计最大组的数目

题目

给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和(每一位上的数字相加),然后把数位和相等的数字放到同一个组中。

请你统计每个组中的数字数目,并返回数字数目并列最多的组有多少个。

示例 1:

1
2
3
4
输入:n = 13
输出:4
解释:总共有 9 个组,将 1 到 13 按数位求和后这些组分别是:
[1,10],[2,11],[3,12],[4,13],[5],[6],[7],[8],[9]。总共有 4 个组拥有的数字并列最多。
阅读更多

LeetCode:设计停车系统

题目

请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位:大,中和小,每种尺寸分别有固定数目的车位。

请你实现 ParkingSystem 类:

  • ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类,三个参数分别对应每种停车位的数目。
  • bool addCar(int carType) 检查是否有 carType 对应的停车位。 carType 有三种类型:大,中,小,分别用数字 1, 2 和 3 表示。一辆车只能停在  carType 对应尺寸的停车位中。如果没有空车位,请返回 false ,否则将该车停入车位并返回 true 。
阅读更多

LeetCode:HTML 实体解析器

题目

「HTML 实体解析器」 是一种特殊的解析器,它将 HTML 代码作为输入,并用字符本身替换掉所有这些特殊的字符实体。

HTML 里这些特殊字符和它们对应的字符实体包括:

  • 双引号:字符实体为 &quot; ,对应的字符是 " 。
  • 单引号:字符实体为 &apos; ,对应的字符是 ' 。
  • 与符号:字符实体为 &amp; ,对应对的字符是 & 。
  • 大于号:字符实体为 &gt; ,对应的字符是 > 。
  • 小于号:字符实体为 &lt; ,对应的字符是 < 。
  • 斜线号:字符实体为 &frasl; ,对应的字符是 / 。

给你输入字符串 text ,请你实现一个 HTML 实体解析器,返回解析器解析后的结果。

阅读更多

LeetCode:最大正方形

题目

在一个由 '0''1' 组成的二维矩阵内,找到只包含 '1' 的最大正方形,并返回其面积。

示例 1:

1
2
输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:4
阅读更多

LeetCode:螺旋矩阵 II

题目

给你一个正整数 n ,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

示例 1:

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