做海报好的psd网站,修改wordpress头像自定义插件,广州大石附近做网站的公司,cmsv6官方免费下载142. 环形链表 II
问题描述
给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返回 null。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1 输入head [3,2,0,-4], pos 1
输出返回索引为 1 的链表节点
解释链表中有一个环其尾部连接到第二个节点。示例 2 输入head [1,2], pos 0
输出返回索引为 0 的链表节点
解释链表中有一个环其尾部连接到第一个节点。示例 3 输入head [1], pos -1
输出返回 null
解释链表中没有环。提示
链表中节点的数目范围在范围 [0, 104] 内-105 Node.val 105pos 的值为 -1 或者链表中的一个有效索引
**进阶**你是否可以使用 O(1) 空间解决此题
解题思路与代码实现
解题思路I:
使用辅助集合存储访问过的节点
如果有环第一个遇到的访问过的节点即为入环的第一个节点
如果无环返回null class Solution {public ListNode detectCycle(ListNode head) {ListNode pos head;SetListNode visited new HashSetListNode(); // 记录访问过的节点while (pos ! null) {if (visited.contains(pos)) {return pos;} else {visited.add(pos);}pos pos.next;}return null;}
}解题思路II
先判断是否有环使用快慢指针初始时fast和slow都指向headfast指针每次走两步slow指针每次走一步如果有环fast移到head头结点然后fast和slow每次都走一步相遇时返回相遇节点如果无环则返回null。
public class Solution {public ListNode detectCycle(ListNode head) {if(head null || head.next null){ // 节点数量小于等于1不可能有环return null;}// 快慢指针判断是否有环ListNode slow head ,fast head; while(fast!null slow!null){slow slow.next; // slow走一步fast fast.next; // fast走两步if(fast!null fast.next ! null){fast fast.next;}else{ // fast 指针走过链表末端说明链表无环return null; }if(fast slow){ // 二者指向同一节点fast head;break;}}//有环while (fast ! null){if (fast slow ){return fast;}fast fast.next;slow slow.next;}return null;}
}踩坑点
无
92. 反转链表 II
问题描述
给你单链表的头指针 head 和两个整数 left 和 right 其中 left right 。请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。
示例 1 输入head [1,2,3,4,5], left 2, right 4
输出[1,4,3,2,5]示例 2
输入head [5], left 1, right 1
输出[5]提示
链表中节点数目为 n1 n 500-500 Node.val 5001 left right n
进阶 你可以使用一趟扫描完成反转吗
解题思路与代码实现
解题思路:
将链表划分为三部分[1, left)、[left, right]、[right1, n]
扫描链表将[left, right]区间的中间链表反转后重新拼接
需要注意特殊的情况导致的NPE如左链表不存在右链表不存在
class Solution {/*** 反转从位置 left 到位置 right 的链表节点*/public ListNode reverseBetween(ListNode head, int left, int right) {if (head null || head.next null) { // 节点数不超过1的链表直接返回return head;}int count 1; // 计数器ListNode cur head; // 辅助指针ListNode leftHead head, leftTail null; // 左链表头尾结点while (cur ! null count left) {leftTail cur;cur cur.next;count;}if (leftTail ! null) { // 左链表不为空leftTail.next null;}ListNode midHead cur, midTail null; // 需要翻转的中间链表头尾结点while (cur ! null count right) {midTail cur;cur cur.next;count;}if (midTail ! null){midTail.next null;}ListNode rightHead cur; // 右链表的头结点ListNode[] nodes reverseList(midHead); // 中间链表反转if ( leftTail null) {leftHead nodes[0];} else {leftTail.next nodes[0];}nodes[1].next rightHead;return leftHead;}/*** 反转链表返回值包含反转后新链表的头尾节点*/private ListNode[] reverseList(ListNode head) {ListNode newTail head, newHead null; // 新链表的头尾节点ListNode current head, post null; // 辅助指针while (current ! null) {post current.next;current.next newHead;newHead current;current post;}return new ListNode[]{newHead, newTail};}}踩坑点
NPE
146. LRU 缓存
问题描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例
输入
[LRUCache, put, put, get, put, get, put, get, get, get]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {11}
lRUCache.put(2, 2); // 缓存是 {11, 22}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4提示
1 capacity 30000 key 100000 value 105最多调用 2 * 105 次 get 和 put
解题思路与代码实现
解题思路:
使用哈希表缓存键值对使用双端队列实现LRU最近最少使用算法最近最少访问的key放在队头最新访问的key放在队尾。
调用get方法若key存在将key从双端队列中移除并重新添加到队尾
调用put方法
若key存在更新value同时将key从双端队列中移除并重新添加到队尾
若key不存在
如果缓存未满直接插入到缓存中并将key保存到双端队列的队尾
如果缓存已满先从队头移除一个旧key同时移除缓存然后将新的key-value添加到缓存并将key保存到双端队列的队尾。
class LRUCache {private HashMapInteger, Integer map null; // 存储键值对private int capacity 0; // 缓存容量private DequeInteger deque null; // 辅助双端队列实现lru算法淘汰先入队的public LRUCache(int capacity) {this.capacity capacity;map new HashMap(capacity);deque new LinkedList();}/*** 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1** param key 关键字key*/public int get(int key) {if (map.containsKey(key)) {// key被访问调整其在队列中的位置deque.remove(key);deque.addLast(key);return map.get(key);}return -1;}/*** 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。* 如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。** param key 关键字* param value 关键字对应的值*/public void put(int key, int value) {// 如果关键字 key 已经存在则变更其数据值 valueif (map.containsKey(key)) {// 更新原有key在队列中的位置deque.remove(key);} else if (map.size() capacity) { // key不存在且容量不充足// 找到最久未使用的关键字key移除Integer oldKey deque.removeFirst();map.remove(oldKey);}// 入队deque.addLast(key);// 存在则更新不存在则加入map.put(key, value);}
}
/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj new LRUCache(capacity);* int param_1 obj.get(key);* obj.put(key,value);*/踩坑点
236. 二叉树的最近公共祖先
问题描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
示例 1 输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1
输出3
解释节点 5 和节点 1 的最近公共祖先是节点 3 。示例 2
输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4
输出5
解释节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例 3
输入root [1,2], p 1, q 2
输出1提示
树中节点数目在范围 [2, 105] 内。-109 Node.val 109所有 Node.val 互不相同 。p ! qp 和 q 均存在于给定的二叉树中。
解题思路与代码实现
解题思路:
解题思路是通过递归后序遍历二叉树查找节点 p 和 q 的最近公共祖先。如果当前节点为 null 或者是 p 或 q 中的一个直接返回当前节点。递归地在左右子树中查找 p 和 q并根据返回结果判断
如果左子树返回 null右子树返回 null则 p 和 q 不在当前树中返回 null。如果左子树返回非 null右子树返回 null则 p 和 q 都在左子树中返回左子树的结果。如果左子树返回 null右子树返回非 null则 p 和 q 都在右子树中返回右子树的结果。如果左右子树分别返回非 null则当前节点即为 p 和 q 的最近公共祖先返回当前节点。
class Solution {/*** 返回p、q在root树中的最近公共祖先*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 当root为null或者p、q之一为root时返回rootif (root null || root p || root q) {return root;}// 后序遍历TreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);if (left null right null) { // p或q不在root树中return null;} else if (left null) { // 在右子树中找到了p、qreturn right;} else if (right null) { // 左子树中找到了p、qreturn left;} else { // p、q分别在左右子树中return root;}}
}踩坑点
124. 二叉树中的最大路径和
问题描述
二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root 返回其 最大路径和 。
示例 1 输入root [1,2,3]
输出6
解释最优路径是 2 - 1 - 3 路径和为 2 1 3 6示例 2 输入root [-10,9,20,null,null,15,7]
输出42
解释最优路径是 15 - 20 - 7 路径和为 15 20 7 42提示
树中节点数目范围是 [1, 3 * 104]-1000 Node.val 1000
解题思路与代码实现
解题思路:
通过递归后序遍历二叉树来求解节点及其子树的最大路径和。
在递归过程中空节点视为0对于每个节点计算其左右子树的最大路径和如果为负数则视作0然后更新全局变量 res记录可能的最大路径和最后返回以当前节点为根的子树中包含当前节点的最大路径和。
class Solution {private int res Integer.MIN_VALUE; // 记录全局最大路径和/*** 返回以root为根节点的子树中的最大路径和* param root 当前节点* return 当前节点及其子树的最大路径和*/public int maxPathSum(TreeNode root) {postOrder(root); // 调用后序遍历函数return res; // 返回最大路径和}/*** 后序遍历递归函数计算以当前节点为根的子树的最大路径和* param root 当前节点* return 当前节点及其子树的最大贡献值即单侧最大路径和*/private int postOrder(TreeNode root) {if (root null) { // 如果当前节点为空返回0return 0;}// 计算左右子树的最大贡献值小于0的贡献值视为0int leftVal Math.max(0, postOrder(root.left));int rightVal Math.max(0, postOrder(root.right));// 更新全局最大路径和res Math.max(res, leftVal rightVal root.val);// 返回当前节点及其子树的最大贡献值单侧最大路径和return root.val Math.max(leftVal, rightVal);}
}
踩坑点
373. 查找和最小的 K 对数字
问题描述
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)其中第一个元素来自 nums1第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
示例 1:
输入: nums1 [1,7,11], nums2 [2,4,6], k 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]示例 2:
输入: nums1 [1,1,2], nums2 [1,2,3], k 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]提示:
1 nums1.length, nums2.length 105-109 nums1[i], nums2[i] 109nums1 和 nums2 均为 升序排列1 k 104k nums1.length * nums2.length
解题思路与代码实现
解题思路:
初始时将所有的 (i,0) 对入堆这是因为 (i,0) 对应的数对是数组 nums1 的前 k 个元素与 nums2 的第一个元素的和这些是最小的数对之一。
在每次从堆中取出数对 (i,j) 后将 (i,j1) 入堆。这是因为 (i,j1) 对应的数对是数组 nums1[i] 和 nums2[j1] 的和可能成为下一个可能的最小数对。这样做可以保证堆中始终是当前可能的最小数对集合确保了答案的正确性和最小性。
class Solution {/*** 返回两个数组 nums1 和 nums2 中前 k 个最小的数对* param nums1 第一个数组* param nums2 第二个数组* param k 最小数对的个数* return 前 k 个最小数对的列表*/public ListListInteger kSmallestPairs(int[] nums1, int[] nums2, int k) {ListListInteger ans new ArrayList(k); // 预分配空间PriorityQueueint[] pq new PriorityQueue((a, b) - a[0] - b[0]); // 小顶堆// 初始将所有 (i,0) 入堆其中 i 为 0 到 nums1.length - 1for (int i 0; i Math.min(nums1.length, k); i) {pq.add(new int[] { nums1[i] nums2[0], i, 0 });}// 依次取出堆中最小的数对加入结果列表同时将其下一个数对 (i, j1) 入堆while (ans.size() k !pq.isEmpty()) {int[] p pq.poll(); // 取出当前最小的数对int i p[1];int j p[2];ans.add(List.of(nums1[i], nums2[j])); // 加入结果列表// 如果 nums2 中仍有下一个元素将其与 nums1[i] 的和入堆if (j 1 nums2.length) {pq.add(new int[] { nums1[i] nums2[j 1], i, j 1 });}}return ans; // 返回前 k 个最小数对的列表}
}
踩坑点
暴力枚举所有组合导致超时
530. 二叉搜索树的最小绝对差
问题描述
给你一个二叉搜索树的根节点 root 返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数其数值等于两值之差的绝对值。
示例 1 输入root [4,2,6,1,3]
输出1示例 2 输入root [1,0,48,null,null,12,49]
输出1提示
树中节点的数目范围是 [2, 104]0 Node.val 105
解题思路与代码实现
解题思路:
二叉搜索树的性质中序遍历的数组是升序排列的。
所以最小绝对值差必然在|根节点值-左子树最大值| 和|根节点值-右子树最小值|在中序遍历数组中它们三者是相邻的。
public int getMinimumDifference(TreeNode root) {int res Integer.MAX_VALUE; // 初始化最小绝对差为最大整数Integer pre null; // 用于记录中序遍历时前一个节点的值// 非递归中序遍历二叉搜索树StackTreeNode stack new Stack(); // 辅助栈TreeNode cur root; // 辅助指针while (cur ! null || !stack.isEmpty()) {if (cur ! null) {stack.push(cur);cur cur.left; // 往左子树遍历} else {TreeNode node stack.pop(); // 弹出栈顶节点if (pre ! null) {res Math.min(res, Math.abs(pre - node.val)); // 更新最小绝对差}pre node.val; // 更新前一个节点的值为当前节点的值cur node.right; // 遍历右子树}}return res;}踩坑点
