如何选择模板网站建设,商务网站设计特色,可视化手机网站开发工具,安家堡网站建设搜索二维矩阵II 方法#xff1a;从右上角开始搜索
我们可以从矩阵的右上角开始进行搜索。如果当前元素 matrix[i][j] 等于 target#xff0c;我们直接返回 true。如果 matrix[i][j] 大于 target#xff0c;说明 target 只能出现在左边的列#xff0c;所以我们将列指针向左…搜索二维矩阵II 方法从右上角开始搜索
我们可以从矩阵的右上角开始进行搜索。如果当前元素 matrix[i][j] 等于 target我们直接返回 true。如果 matrix[i][j] 大于 target说明 target 只能出现在左边的列所以我们将列指针向左移动。如果 matrix[i][j] 小于 target说明 target 只能出现在下方的行所以我们将行指针向下移动。我们重复这个过程直到找到目标元素或者行列指针越界。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix null || matrix.length 0 || matrix[0].length 0){return false;}int m matrix.length;//行数int n matrix[0].length;//列数int row 0;//从第一行开始int col n-1;//从最后一列开始while(row m col 0){if(matrix[row][col] target){return true;}else if(matrix[row][col] target){col--;//当前元素大于目标左移}else{row;//当前元素小于目标下移}}return false;}
} 相交链表 双指针法 两个指针分别指向两个链表的头节点 我们设立两个指针 pA 和 pB分别指向链表 A 和链表 B 的头节点。 同时移动两个指针 每次移动一个指针如果当前指针指向的节点为空则将其指向另一个链表的头节点。这样做的目的是让两个指针在遍历完自己的链表后能够到达另一个链表的头节点最终相遇的地方就是交点。 相遇 如果两个指针相遇则返回相遇的节点如果两个指针同时指向 null则说明链表没有交点。
这种方法的核心思想就是“同步走互相切换”确保两个指针走过相同的路程因此可以在 O(m n) 时间复杂度内解决问题。
设「第一个公共节点」为 node 「链表 headA」的节点数量为 a 「链表 headB」的节点数量为 b 「两链表的公共尾部」的节点数量为 c 则有
头节点 headA 到 node 前共有 a−c 个节点 头节点 headB 到 node 前共有 b−c 个节点
考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB 做如下操作
指针 A 先遍历完链表 headA 再开始遍历链表 headB 当走到 node 时共走步数为 a(b−c) 指针 B 先遍历完链表 headB 再开始遍历链表 headA 当走到 node 时共走步数为 b(a−c) 如下式所示此时指针 A , B 重合并有两种情况
a(b−c)b(a−c) 若两链表 有 公共尾部 (即 c0 ) 指针 A , B 同时指向「第一个公共节点」node 。 若两链表 无 公共尾部 (即 c0 ) 指针 A , B 同时指向 null 。 因此返回 A 即可。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pA headA;ListNode pB headB;while(pA ! pB){pA (pA null) ? headB : pA.next;pB (pB null) ? headA : pB.next;}return pA;}
}
反转链表 双指针
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode cur head,pre null;while(cur ! null){ListNode tmp cur.next;cur.next pre;pre cur;cur tmp;}return pre;}
} 回文链表 思路
找到链表的中间节点使用快慢指针慢指针每次走一步快指针每次走两步最终快指针会指向链表的尾部慢指针则会指向链表的中间节点。反转后半部分链表将链表的后半部分进行反转反转后的链表与前半部分进行比较。比较前后部分比较反转后的后半部分与前半部分的节点值如果相同则该链表是回文链表。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if(head null || head.next null){return true;//链表为空或只有一个元素}ListNode slow head,fast head;//快指针走两步慢指针走一步直到快指针到达末尾while(fast ! null fast.next ! null){slow slow.next;fast fast.next.next;}//反转链表的后半部分ListNode secondHalf reverse(slow);ListNode firstHalf head;//比较前后部分的节点值while(secondHalf ! null){if(firstHalf.val ! secondHalf.val){return false;}firstHalf firstHalf.next;secondHalf secondHalf.next;}return true;}public ListNode reverse(ListNode head){ListNode prev null,curr head;while(curr ! null){ListNode temp curr.next;curr.next prev;prev curr;curr temp;}return prev;}
}
环形链表 初始化指针使用两个指针slow 和 fast。slow 每次走一步fast 每次走两步。判断是否相遇如果存在环slow 和 fast 会在环内相遇。如果没有环fast 会指向 null即链表的末尾。结束条件 如果 slow 和 fast 相遇则说明链表有环返回 true。如果 fast 到达 null则说明链表没有环返回 false。
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if(head null || head.next null){return false;}ListNode slow head,fast head;while(fast ! null fast.next ! null){slow slow.next;fast fast.next.next;if(slow fast){return true;}}return false;}
}
环形链表ll 使用快慢指针检查链表是否有环。如果有环重新定位慢指针到头节点同时让慢指针和快指针都以相同的速度每次一步向前走直到它们相遇。相遇的节点就是入环的第一个节点。
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head null || head.next null){return null;}ListNode slow head,fast head;while(fast ! null fast.next ! null){slow slow.next;fast fast.next.next;if(slow fast){//找到环的起点ListNode pointer head;while(pointer ! slow){pointer pointer.next;//pointer从头节点开始走slow slow.next;//slow从相遇点开始走}return pointer;}}return null;}
}
