代码随想录算法训练营第三天|417. 太平洋大西洋水流问题|24. 两两交换链表中的节点|19.删除链表的倒数第N个节点|面试题 02.07. 链表相交|

417. 太平洋大西洋水流问题

水往高处流，先记录两个海祥往高处流所能留到的地址，之后将他们的合并区域进行输出

static const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};class Solution {
public:vector<vector<int>> heights;void dfs(int row, int col, vector<vector<bool>> & ocean) {int m = ocean.size();int n = ocean[0].size();if (ocean[row][col]) {return;}ocean[row][col] = true;for (int i = 0; i < 4; i++) {int newRow = row + dirs[i][0], newCol = col + dirs[i][1];if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {dfs(newRow, newCol, ocean);}}}vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {this->heights = heights;int m = heights.size();int n = heights[0].size();vector<vector<bool>> pacific(m, vector<bool>(n, false));vector<vector<bool>> atlantic(m, vector<bool>(n, false));for (int i = 0; i < m; i++) {dfs(i, 0, pacific);}for (int j = 1; j < n; j++) {dfs(0, j, pacific);}for (int i = 0; i < m; i++) {dfs(i, n - 1, atlantic);}for (int j = 0; j < n - 1; j++) {dfs(m - 1, j, atlantic);}vector<vector<int>> result;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (pacific[i][j] && atlantic[i][j]) {result.push_back({i,j});}}}return result;}
};

24. 两两交换链表中的节点

在纸上画一画

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode*_head=new ListNode(0);_head->next=head;ListNode*cur=_head;while(cur->next!=nullptr&&cur->next->next!=nullptr){ListNode*tmp=cur->next->next->next;ListNode*tmp1=cur->next->next;cur->next->next->next=cur->next;cur->next->next=tmp;cur->next=tmp1;cur=cur->next->next;}return _head->next;}
};

19.删除链表的倒数第N个节点

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode*_head=new ListNode(0);_head->next=head;ListNode*cur=_head;int size=0;while(cur->next!=nullptr){cur=cur->next;size++;}size=size-n;cur=_head;while(size--){cur=cur->next;}cur->next=cur->next->next;return _head->next;}
};

还有另外一种写法，双指针快慢，先让快指针走n，然后再让慢指针和快指针一起走，当快指针为null的时候删除慢指针，返回头节点

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n-- && fast != NULL) {fast = fast->next;}fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点while (fast != NULL) {fast = fast->next;slow = slow->next;}slow->next = slow->next->next; // ListNode *tmp = slow->next;  C++释放内存的逻辑// slow->next = tmp->next;// delete nth;return dummyHead->next;}
};

面试题 02.07. 链表相交

很有意思的解法，正常的解法应该是先都过一遍，然后看大家的尺寸
然后，把双方指针移到短指针开始的位置开始比较，相等返回，不相等噶

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