力扣hot100学习记录(七)

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。

每列的元素从上到下升序排列。

题意

在二维矩阵中搜索是否存在一个目标值，该矩阵每一行每一列都是升序排列；

思路

从矩阵右上角开始判断，如果该点的值小于目标值，则这一行删除（因为该行其他值都小于该值），同理如果该点的值大于目标值，则这一列删除。以此来判断矩阵中是否存在目标值。

代码

class Solution {public:    bool searchMatrix(vector& matrix, int target) {        if(matrix.empty()|| matrix[0].empty()) return false;        int n = matrix.size(), m = matrix[0].size();        int i = 0, j = m - 1;        while(i = 0){            if(matrix[i][j] == target) return true;            else if(matrix[i][j] > target) j--;            else i++;        }        return false;    }};

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题意

给定两个单链表的头节点，找到两个单链表相交的起始节点。

思路

定义两个指针，分别从两个链表头开始搜索，如果搜到末尾（pA=null，则pA = headB），以此继续搜索，直到pA == pB，则为交点

代码

class Solution {public:    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {        auto p = headA, q = headB;        while(p != q){            p = p ? p -> next : headB;            q = q ? q -> next : headA;        }        return p;    }};