秃头哥编程

本文基于LeetCode第146. LRU 缓存机制进行实现。题目运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。实现 LRUCache 类：LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则

2021-09-20 LeetCode每日一题链接：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/标签：数组、动态规划题目给定一个未排序的整数数组，找到最长递增子序列的个数。示例 1:输入: [1,3,5,4,7]输出: 2解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。示例 2:输入: [2,2,2,2,2]输出: 5解释: 最长递

2021-09-15 LeetCode每日一题链接：https://leetcode-cn.com/problems/find-peak-element/标签：数组、二分查找题目峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。示例 1：输入：num

2021-09-14 LeetCode每日一题链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/标签：数组、双指针、字符串、排序题目给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。示例 1：输入：s =

2021-09-13 LeetCode每日一题链接：https://leetcode-cn.com/problems/number-of-boomerangs/标签：数组、数学、哈希表题目给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。返回平面上所有回旋镖的数量。示例 1：输入：points = [[0,0

链接：https://leetcode-cn.com/problems/russian-doll-envelopes/标签：数组、二分查找、动态规划、排序题目给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。注意：不允许

2021-09-05 LeetCode每日一题链接：https://leetcode-cn.com/problems/implement-rand10-using-rand7/标签：数学、拒绝采样、概率与统计、随机化题目已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。不要使用系统的 Math.random() 方法。示例 1:输入: 1输出: [7]示例 2:输入: 2输出: [8,4]示例

2021-09-03 LeetCode每日一题链接：https://leetcode-cn.com/problems/smallest-k-lcci/标签：数组、分治、快速选择、排序、堆题目设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。示例：输入： arr = [1,3,5,7,2,4,6,8], k = 4输出： [1,2,3,4]提示：0 <= len(arr) <= 1000000 <= k <= min(100000, len(

2021-09-02 LeetCode每日一题链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/标签：链表、双指针题目输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。示例：给定一个链

2021-08-31 LeetCode每日一题链接：https://leetcode-cn.com/problems/corporate-flight-bookings/标签：数组、前缀和题目这里有 n 个航班，它们分别从 1 到 n 进行编号。有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seat

2021-08-26 LeetCode每日一题链接：https://leetcode-cn.com/problems/boats-to-save-people/标签：贪心、排序、数组、双指针题目第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。返回载到每一个人所需的最小船数。(保证每个人都能被船载)。示例 1：输入：people = [1,2], limit = 3输出：1解释：1 艘

2021-08-22 LeetCode每日一题链接：https://leetcode-cn.com/problems/escape-the-ghosts/标签：数组、数学题目你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 target = [xtarget, ytarget] 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts[i] = [xi, yi] 出发。所有输入均为 整数坐标 。每一回合，你和阻碍者们可以同时向东，西，南，北

2021-08-21 LeetCode每日一题链接：https://leetcode-cn.com/problems/string-compression/标签：字符串、双指针题目给你一个字符数组 chars ，请使用下述算法压缩：从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：如果这一组长度为 1 ，则将字符追加到 s 中。否则，需要向 s 追加字符，后跟这一组的长度。压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，

2021-08-20 LeetCode每日一题链接：https://leetcode-cn.com/problems/reverse-string-ii/标签：字符串、双指针题目给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。示例 1：输入：s = "abcdefg", k = 2输出："bacdfeg"

2021-08-19 LeetCode每日一题链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string/标签：字符串、双指针题目给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。元音字母包括 ‘a’、‘e’、‘i’、‘o’、‘u’，且可能以大小写两种形式出现。示例 1：输入：s = "hello"输出："holle"示例 2：输入：s = "leetcode"输出："leotcede"提示

2021-08-14 LeetCode每日一题链接：https://leetcode-cn.com/problems/count-unhappy-friends/标签：数组、模拟题目给你一份 n 位朋友的亲近程度列表，其中 n 总是 偶数 。对每位朋友 i，preferences[i] 包含一份 按亲近程度从高到低排列 的朋友列表。换句话说，排在列表前面的朋友与 i 的亲近程度比排在列表后面的朋友更高。每个列表中的朋友均以 0 到 n-1 之间的整数表示。所有的朋友被分成几对，配对情况以列表

2021-08-10 LeetCode每日一题链接：https://leetcode-cn.com/problems/arithmetic-slices/标签：数组、动态规划题目如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。子数组 是数组中的一个连续序列。示例 1：输入

2021-08-08 LeetCode每日一题链接：https://leetcode-cn.com/problems/n-th-tribonacci-number/标签：数学、记忆化搜索、动态规划题目泰波那契序列 Tn 定义如下：T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2给你整数 n，请返回第 n 个泰波那契数 Tn 的值。示例 1：输入：n = 4输出：4解释：T_3 = 0 + 1 + 1

2021-08-04 LeetCode每日一题链接：https://leetcode-cn.com/problems/valid-triangle-number/标签：数组、排序、二分、双指针题目给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。示例 1:输入: [2,2,3,4]输出: 3解释:有效的组合是: 2,3,4 (使用第一个 2)2,3,4 (使用第二个 2)2,2,3注意:数组长度不超过1000。数组里整数的范围为 [0, 1

2021-08-01 LeetCode每日一题链接：https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix/标签：数组、矩阵、哈希表、排序题目给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。

2021-07-27 LeetCode每日一题链接：https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/标签：二叉树、深度优先搜索题目给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。更正式地说，root.val = min(root.left.val, root.right.val) 总成立。给

2021-07-23 LeetCode每日一题链接：https://leetcode-cn.com/problems/check-if-all-the-integers-in-a-range-are-covered/标签：数组、哈希表、前缀和题目给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [starti, endi] 表示一个从 starti 到 endi 的 闭区间 。如果闭区间 [left, right] 内每个整数都被 ran

2021-07-22 LeetCode每日一题链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/标签：哈希表、链表题目给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中

2021-07-21 LeetCode每日一题链接：https://leetcode-cn.com/problems/minimize-maximum-pair-sum-in-array/标签：数组、排序、双指针、贪心题目一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。给你一个长

2021-07-15 LeetCode每日一题链接：https://leetcode-cn.com/problems/maximum-element-after-decreasing-and-rearranging/标签：贪心、数组、排序题目给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：arr 中 第一个 元素必须为 1 。任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 <= i < arr.l

1、什么是摩尔投票法博耶-摩尔多数投票算法（英语：Boyer–Moore majority vote algorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。对于数据流

2021-07-07 LeetCode每日一题链接：https://leetcode-cn.com/problems/count-good-meals/标签：数组、哈希表题目大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。你可以搭配 任意 两道餐品做一顿大餐。给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 109 + 7 取余。注意，只要

2021-07-06 LeetCode每日一题链接：https://leetcode-cn.com/problems/display-table-of-food-orders-in-a-restaurant/标签：数组、哈希表、字符串、有序集合、排序题目给你一个数组 orders，表示客户在餐厅中完成的订单，确切地说， orders[i]=[customerNamei,tableNumberi,foodItemi] ，其中 customerNamei 是客户的姓名，tableNumberi 是客

链接：https://leetcode-cn.com/problems/minimum-window-substring/标签：哈希表、字符串、滑动窗口题目给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。示例 1：输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"示例 2：输入：s = "a"

2021-07-04 LeetCode每日一题链接：https://leetcode-cn.com/problems/set-mismatch/标签：位运算、数组、哈希表、排序题目集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。示例 1：输入：

2021-07-03 LeetCode每日一题链接：https://leetcode-cn.com/problems/sort-characters-by-frequency/标签：哈希表、字符串、桶排序、计数、排序、堆（优先队列）题目给定一个字符串，请将字符串里的字符按照出现的频率降序排列。示例 1:输入:"tree"输出:"eert"解释:'e'出现两次，'r'和't'都只出现一次。因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。示例 2

2021-07-02 LeetCode每日一题链接：https://leetcode-cn.com/problems/maximum-ice-cream-bars/标签：贪心、数组、排序题目夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。给你价格数组 costs 和现金量 coins ，请你计算

2021-07-01 LeetCode每日一题链接：https://leetcode-cn.com/problems/chuan-di-xin-xi/标签：深度优先搜索、广度优先搜索、图、动态规划题目小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：（1）有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0（2）每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。

2021-06-29 LeetCode每日一题链接：https://leetcode-cn.com/problems/excel-sheet-column-title/标签：数学、字符串题目给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。例如：A -> 1B -> 2C -> 3...Z -> 26AA -> 27AB -> 28 ...输入：columnNumber = 1输出："A" 输

2021-06-28 LeetCode每日一题链接：https://leetcode-cn.com/problems/bus-routes/标签：广度优先搜索、数组、哈希表题目给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1

2021-06-27 LeetCode每日一题链接：https://leetcode-cn.com/problems/snakes-and-ladders/标签：广度优先搜索、数组、矩阵题目N x N 的棋盘 board 上，按从 1 到 N*N 的数字给方格编号，编号 从左下角开始，每一行交替方向。例如，一块 6 x 6 大小的棋盘，编号如下：r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 board[r][c] != -1，那个蛇或梯子的目的地将会是

2021-06-26 LeetCode每日一题链接：https://leetcode-cn.com/problems/sliding-puzzle/标签：广度优先搜索、数组、哈希表题目在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板

2021-06-25 LeetCode每日一题链接：https://leetcode-cn.com/problems/open-the-lock/标签：广度优先搜索、数组、哈希表、字符串题目你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字为 ‘0000’ ，一

1、了解全排列和回溯所谓全排列就是从n个元素中取出n个元素按照一定的顺序进行排列，所有的排列情况叫做全排列。这n个元素又分为两种情况，一种是n个元素存在重复元素，一种是n个元素不存在重复元素。不存在重复元素的好办，关键是存在重复元素的，我们在求解过程中需要进行处理。回溯法，名字很高大上，其实本质就是穷举。这里我们结合三道题来理解如何使用回溯法解决全排列问题。（1）46. 全排列（2）47. 全排列 II（3）剑指 Offer 38. 字符串的排列2、全排列问题分析比如给定数组[1, 2, 3

2021-05-03 LeetCode每日一题链接：https://leetcode-cn.com/problems/reverse-integer/正常情况下，此题使用int肯定会溢出的，所以需要在循环中提前判断一下是否超过[-2^31, 2^31 - 1]。class Solution { public int reverse(int x) { int res = 0; while (x != 0) { int temp = x %