二进制的叮当喵

Leetcode169. 多数元素 题目描述 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 $ \lfloor n/2 \rfloor$的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1： 12输入：[3,2,3]输出：3 示例 2： 12输入：[2,2,1,1,1,2,2]输出：2 进阶： 尝试设计时间复杂度为 O(n)O(n)O(n)、空间复杂度为$ O(1) $的算法解决此问题。 解题思路 这道题最简单的方法就是哈希法。也就是同一个哈希表去存储每一个元素以及出现的次数，然后返回出现次数大于$ \lfloor n/2 \rfloor$的元素。 这个方法简单易懂，但是时间复杂度为O(n)O(n)O(n)，空间复杂度也为O(n)O(n)O(n)，不符合要求。 如果要把空间复杂度优化到O(1)O(1)O(1)，我们就需要采用非常有名的**$Boyer-Moore $投票算法。** 摩尔投票法充分利用了题目中的一直条件——数组中一定存在出现次数 大于 $ \lfloor n/2 \rfloor的元素。那么如果把多数元素记为 ...

Leetcode165. 比较版本号 题目描述 给你两个版本号 version1 和 version2 ，请你比较它们。 版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。 返回规则如下： 如果 *version1* > *version2* 返回 1， 如果 *version1* < *version2* 返回 -1， 除此之外返回 0。 示例 1： 123输入：version1 = ...

Leetcode162. 寻找峰值 题目描述 峰值元素是指其值大于左右相邻值的元素。 给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。 示例 1： 123输入：nums = [1,2,3,1]输出：2解释：3 是峰值元素，你的函数应该返回其索引 2。 示例 2： 1234输入：nums = [1,2,1,3,5,6,4]输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。 提示： 1≤nums.length≤10001 \leq nums.length \leq 10001≤nums.length≤1000​ −231≤nums[i]≤231−1-2^{31} \leq nums[i] \leq 2^{31} - 1−231≤nums[i]≤231−1​ 对于所有有效的 i 都有 nums[i] != nums[i + 1] **进阶：**你可以实现时间复杂度为 O(logN) 的 ...

Leetcode153. 寻找旋转排序数组中的最小值 题目描述 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。 示例 1： 123输入：nums = [3,4,5,1,2]输出：1解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。 示例 2： 123输入：nums = [4,5,6,7,0,1,2]输出：0解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。 示例 3： 123输入： ...

Leetcode148. 排序链表 题目描述 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 进阶： 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 示例 1： 12输入：head = [4,2,1,3]输出：[1,2,3,4] 示例 2： 12输入：head = [-1,5,3,4,0]输出：[-1,0,3,4,5] 示例 3： 12输入：head = []输出：[] 提示： 链表中节点的数目在范围 $[0, 5 \times 10^4] $内 −105≤Node.val≤105-10^5 \leq Node.val \leq 10^5−105≤Node.val≤105 解题思路 链表的排序是一道很经典的题目，可以实现的排序算法有很多种。本道题主要实现了链表的归并排序。 链表的归并排序的思想与数组的归并排序并无二致，也可以分为递归和迭代两种方式来实现。 在具体的实现过程中主要有以下几点差别： 在数组中需要合并两个有序数组，那么在链表中就需要合并两个有序链表。具体实现方法可以参见Leetcode21.合并两 ...

Leetcode 146：LRU 缓存机制 题目描述 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。 实现 LRUCache 类： LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？ 示例 1234567891011121314151617输入["LRUCache", "put", "put", "get", "put", "get", "put", "get& ...

Leetcode143. 重排链表 题目描述 给定一个单链表 L：L0→L1→…→L**n-1→Ln ， 将其重新排列后变为： L0→L**n→L1→L**n-1→L2→L**n-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例 1: 1给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2: 1给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3. 解题思路 这道题可以简单粗暴莽一波。思路就是先找到中间结点，然后将中间结点之后的结点进行反转，接着把两半部分链表按题目要求连接起来。 示例代码如下。 示例代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546struct ListNode { int val; ListNode *next; ListNode() : val(0), n ...

Leetcode138. 复制带随机指针的链表 题目描述 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 he ...

Leetcode129. 求根节点到叶节点数字之和 题目描述 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字： 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。 叶节点 是指没有子节点的节点。 示例 1： 123456输入：root = [1,2,3]输出：25解释：从根到叶子节点路径 1->2 代表数字 12从根到叶子节点路径 1->3 代表数字 13因此，数字总和 = 12 + 13 = 25 示例 2： 1234567输入：root = [4,9,0,5,1]输出：1026解释：从根到叶子节点路径 4->9->5 代表数字 495从根到叶子节点路径 4->9->1 代表数字 491从根到叶子节点路径 4->0 代表数字 40因此，数字总和 = 495 + 491 + 40 = 1026 提示： 树中节点的数目在范围 [1, 1000] 内 0 <= Node. ...

Leetcode128. 最长连续序列 题目描述 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1： 123输入：nums = [100,4,200,1,3,2]输出：4解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 示例 2： 12输入：nums = [0,3,7,2,5,8,4,6,0,1]输出：9 提示： 0≤nums.length≤1050 \leq nums.length \leq 10^50≤nums.length≤105 −109≤nums[i]≤109-10^9 \leq nums[i] \leq 10^9−109≤nums[i]≤109 解题思路 哈希法 这道题要求求解最长的连续序列，序列中的元素是整数。最容易想到的办法就是暴力解法，对于每一个元素去查找它的后继元素是不是在所给的整数数组中，但是这样的时间复杂度很高。对于其中判断后继元素在不在整数数组中的时候，我们可以用哈希表去优化它，这样可以减少一次遍历的时间复杂度。 如果 ...