Leetcode468. 验证IP地址
Leetcode468. 验证IP地址
题目描述
编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。
如果是有效的 IPv4 地址，返回 "IPv4" ；
如果是有效的 IPv6 地址，返回 "IPv6" ；
如果不是上述类型的 IP 地址，返回 "Neither" 。
IPv4 地址由十进制数和点来表示，每个地址包含 4 个十进制数，其范围为 0 - 255， 用(“.”)分割。比如，172.16.254.1；
同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。
IPv6 地址由 8 组 16 进制的数字来表示，每组表示 16 比特。这些组数字通过 (“:”)分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 addres ...
Leetcode460. LFU 缓存
Leetcode460. LFU 缓存
题目描述
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
实现 LFUCache 类：
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。
注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。
示例：
12 ...
Leetcode394. 字符串解码
Leetcode394. 字符串解码
题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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"
解题思路
栈方法
这道题考察字符串的处 ...
Leetcode322. 零钱兑换
Leetcode322. 零钱兑换
题目描述
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
123输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1
示例 2：
12输入：coins = [2], amount = 3输出：-1
示例 3：
12输入：coins = [1], amount = 0输出：0
示例 4：
12输入：coins = [1], amount = 1输出：1
示例 5：
12输入：coins = [1], amount = 2输出：2
提示：
1≤coins.length≤121 \leq coins.length \leq 121≤coins.length≤12
1≤coins[i]≤231−11 \leq coins[i] \leq 2^{31} - 11≤coins[i]≤231−1
0≤amount≤1040 \leq amou ...
Leetcode283. 移动零
Leetcode283. 移动零
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
12输入: [0,1,0,3,12]输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
解题思路
方法一：两层循环
刚开始我想复杂了，首先逐个遍历整个数组，如果碰到0，那么就在这个元素后面找一个非0的进行交换，如果找不到非0的，说明已经完成了。
参考代码如下：
123456789101112131415void moveZeroes(vector<int>& nums){ for(int i=0;i<nums.size();++i) { if(nums[i]!=0) continue; int j=i+1; for(;j<nums.size();++j) { if(nums[j]==0) continue; swa ...
Leetcode240. 搜索二维矩阵 II
Leetcode240. 搜索二维矩阵 II
题目描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
12输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5输出：true
示例 2：
12输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20输出：false
提示：
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
−109<=matix[i][j]<=109-10^9 <= matix[i][j] <= 10^9−109<=matix[ ...
Leetcode239. 滑动窗口最大值
Leetcode239. 滑动窗口最大值
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
1234567891011输入：nums = [1,3,-1,-3,5,3,6,7], k = 3输出：[3,3,5,5,6,7]解释：滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例 2：
12输入：nums = [1], k = 1输出：[1]
示例 3：
12输入：n ...
Leetcode 236. 二叉树的最近公共祖先
Leetcode 236. 二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例
示例 1：
123输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出：3解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
123输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出：5解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
12输入：root = [1,2], p = 1, q = 2输出：1
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q ...
Leetcode234. 回文链表
Leetcode234. 回文链表
题目描述
请判断一个链表是否为回文链表。
示例 1:
12输入: 1->2输出: false
示例 2:
12输入: 1->2->2->1输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解题思路
这道题的思路很简单。算法主要分为三部分：
找出中间结点
中间结点可以通过快慢指针来寻找。设置两个指针，初始为首节点，然后一个指针一次走两步，一个指针一次走一步，当后一个指针走到末尾的时候，前一个指针指向的就是中间结点。
将链表的后半部分反转
将链表的后半部分反转，那么就可以通过同步比较链表的前半部分和反转后的后半部分来判断是否是回文链表。
链表的反转可以用递归，也可以用迭代法实现，这两种算法会影响整体算法的空间复杂度。
链表反转的实现可以参看文章反转链表中的示例代码。
对比判断链表的前半部分和反转后的后半部分来判断是否是回文链表
时间复杂度：O(n)O(n)O(n)
空间复杂度：O(1)O(1)O(1) 或者 $ O(n) $
当使用迭代法实现链表反转的时候，空间复杂度为O(1 ...
Leetcode232. 用栈实现队列
Leetcode232. 用栈实现队列
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
示例：
12345678910111213输入：["MyQueue", "push&quo ...