9. 日常算法

1. 相交链表

题目来源

方法一：暴力枚举

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int l1 = 0, l2 = 0;
        ListNode* cur1 = headA, * cur2 = headB;
        // 计算两个长度
        while (cur1 || cur2){
            if (cur1){
                l1++;
                cur1 = cur1->next;
            }
            if (cur2){
                l2++;
                cur2 = cur2->next;
            }
        }
        int l3 = l1 > l2 ? l1 - l2 : l2 - l1;
        ListNode *longer = headA, *shorter = headB;
        if (l2 > l1){
            longer = headB;
            shorter = headA;
        }
        // 让长的先走差值步数
        for (int i = 0; i < l3; i++) longer = longer->next;
        while (longer != shorter){
            longer = longer->next;
            shorter = shorter->next;
        }
        return shorter;
    }
};

方法二：哈希

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> exist;
        ListNode* cur = headA;
        while (cur){
            exist.insert(cur);
            cur = cur->next;
        }
        cur = headB;
        while (cur){
            if (exist.count(cur)){
                return cur;
            }
            cur = cur->next;
        }
        return nullptr;
    }
};

方法三：双指针

实现原理是：

• pa指向headA的头结点，pb指向headB的头结点
• 如果pa指向了nullptr则将其指向headB的头结点，如果pb指向了nullptr则将pb指向headA的头结点
• 假设headA和headB没有相交的节点长度为a和b，相交部分长度为c
• 这样pa做过的路长就是 a + c + b，而pb走过的长度是 b + c + a，所以最终是会走到同一个地方的。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pa = headA, *pb = headB;
        while (pa != pb){
            pa = pa == nullptr ? headB : pa->next;
            pb = pb == nullptr ? headA : pb->next;
        }
        return pa;
    }
};

2. LCR 121. 寻找目标值 - 二维数组

题目来源
m*n 的二维数组 plants 记录了园林景观的植物排布情况，具有以下特性：
每行中，每棵植物的右侧相邻植物不矮于该植物；
每列中，每棵植物的下侧相邻植物不矮于该植物。

请判断 plants 中是否存在目标高度值 target。

示例 1：
输入：plants = [[2,3,6,8],[4,5,8,9],[5,9,10,12]], target = 8
输出：true

方法就是从右上角或者左下角作为起点，这样换个角度就是一个搜索二叉树，左边比根小，右边比根大。

// 递归
class Solution {
public:
    bool check(vector < vector<int>> & plants, int x, int y) {
        return (x < plants.size() && y >= 0);
    }
    bool dfs(vector < vector<int>> & plants, int x, int y, int target) {
        if (!check(plants, x, y)) return false;
        if (plants[x][y] < target){
            if (dfs(plants, x + 1, y, target)) return true;
        }else if (plants[x][y] > target){
            if (dfs(plants, x, y - 1, target)) return true;
        }else{
            return true;
        }
        return false;
    }
    bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
        if (plants.size() == 0 || plants[0].size() == 0)
            return 0;
            // 从右上角开始，左边比plants[x][y]小，下面比plants[x][y]大；
        return dfs(plants, 0, plants[0].size() - 1, target);
    }
};

//循环
class Solution {
public:
    bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
        if (plants.size() == 0 || plants[0].size() == 0) return 0; 
        int i = 0, j = plants[0].size() - 1;
        while (j >= 0 && i < plants.size()){
            if (plants[i][j] > target) j--;
            else if (plants[i][j] < target) i++;
            else return true;
        }
        return false;
    }
};