LeetCode常见题目整理汇总1

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

LeetCode链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description
题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
关键：先遍历链表获得总长度，再找到需要删除的位置，将节点对应的指针修改或删除。
代码：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {
    }

    ListNode(int x) : val(x), next(nullptr) {
    }

    ListNode(int x, ListNode *next) : val(x), next(next) {
    }
};

int getLength(ListNode *head) {
    int length = 0;
    while (head) {
        ++length;
        head = head->next;
    }
    return length;
}

ListNode *removeNthFromEnd(ListNode *head, int n) {
    ListNode *dummy = new ListNode(0, head);
    int length = getLength(head);
    ListNode *cur = dummy;
    for (int i = 1; i < length - n + 1; ++i) {
        cur = cur->next;
    }
    cur->next = cur->next->next;
    ListNode *ans = dummy->next;
    delete dummy;
    return ans;
}


int main() {
    ListNode *head = NULL;
    ListNode node1 = {1, head};
    ListNode node2 = {2, head};
    ListNode node3 = {3, head};
    ListNode node4 = {4, head};
    ListNode node5 = {5, head};

    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;

    head = &node1;
    while (head != nullptr) {
        cout << head->val << endl;
        head = head->next;
    }

    head = &node1;
    head = removeNthFromEnd(head, 2);

    head = &node1;
    while (head != nullptr) {
        cout << head->val << endl;
        head = head->next;
    }

    return 0;
}

两两交换链表中的节点

LeetCode链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description
题目描述：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
关键：可以通过递归的方式实现两两交换链表中的节点。用head表示原始链表的头节点，新的链表的第二个节点，用newHead表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是newHead.next。令head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为head的下一个节点。然后令newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点newHead。
代码：

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {
    }

    ListNode(int x) : val(x), next(nullptr) {
    }

    ListNode(int x, ListNode *next) : val(x), next(next) {
    }
};

ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = head.next;
    head.next = swapPairs(newHead.next);
    newHead.next = head;
    return newHead;
}

合并两个有序链表

LeetCode链接：https://leetcode.cn/problems/merge-two-sorted-lists/description
题目描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
关键：可以采用递归方式。两个链表头部值较小的一个节点与剩下元素的merge操作结果合并。
代码：

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {
    }

    ListNode(int x) : val(x), next(nullptr) {
    }

    ListNode(int x, ListNode *next) : val(x), next(next) {
    }
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) {
        return l2;
    } else if (l2 == nullptr) {
        return l1;
    } else if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

反转链表

LeetCode链接：https://leetcode.cn/problems/reverse-linked-list/description
题目描述：给你单链表的头节点head，请你反转链表，并返回反转后的链表。
关键：在遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
代码：

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {
    }

    ListNode(int x) : val(x), next(nullptr) {
    }

    ListNode(int x, ListNode *next) : val(x), next(next) {
    }
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

回文链表

LeetCode链接：https://leetcode.cn/problems/palindrome-linked-list/description
题目描述：给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。
关键：可以将值复制到数组中后用双指针法。确定数组列表是否回文很简单，我们可以使用双指针法来比较两端的元素，并向中间移动。一个指针从起点向中间移动，另一个指针从终点向中间移动。在起点放置一个指针，在结尾放置一个指针，每一次迭代判断两个指针指向的元素是否相同，若不同，返回false；相同则将两个指针向内移动，并继续判断，直到两个指针相遇。
代码：

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {
    }

    ListNode(int x) : val(x), next(nullptr) {
    }

    ListNode(int x, ListNode *next) : val(x), next(next) {
    }
};

bool isPalindrome(ListNode* head) {
    vector<int> vals;
    while (head != nullptr) {
        // emplace_back是C++11引入的容器成员函数，用于在顺序容器（如std::vector、std::list等）尾部直接构造元素，避免临时对象的拷贝或移动开销。功能上等价于push_back()
        vals.emplace_back(head->val);
        head = head->next;
    }
    for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {
        if (vals[i] != vals[j]) {
            return false;
        }
    }
    return true;
}

环形链表

LeetCode链接：https://leetcode.cn/problems/linked-list-cycle/description
题目描述：给你一个链表的头节点head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。如果链表中存在环，则返回true。否则，返回false。
关键：遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。可以使用哈希表来存储所有已经访问过的节点。每次到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到遍历完整个链表即可。
代码：

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {
    }

    ListNode(int x) : val(x), next(nullptr) {
    }

    ListNode(int x, ListNode *next) : val(x), next(next) {
    }
};

bool hasCycle(ListNode *head) {
    // 需要包含unordered_set头文件
    unordered_set<ListNode*> seen;
    while (head != nullptr) {
        if (seen.count(head)) {
            return true;
        }
        seen.insert(head);
        head = head->next;
    }
    return false;
}

排序链表

LeetCode链接：https://leetcode.cn/problems/sort-list/description
题目描述：给你链表的头结点head，请将其按升序排列并返回排序后的链表。
关键：对链表自顶向下归并排序的过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于1，即当链表为空或者链表只包含1个节点时，不需要对链表进行拆分和排序。1.找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动2步，慢指针每次移动1步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。2.对两个子链表分别排序。3.将两个排序后的子链表合并，得到完整的排序后的链表。
代码：

ListNode* sortList(ListNode* head) {
    return sortList(head, nullptr);
}

ListNode* sortList(ListNode* head, ListNode* tail) {
    if (head == nullptr) {
        return head;
    }
    if (head->next == tail) {
        head->next = nullptr;
        return head;
    }
    ListNode* slow = head, *fast = head;
    while (fast != tail) {
        slow = slow->next;
        fast = fast->next;
        if (fast != tail) {
            fast = fast->next;
        }
    }
    ListNode* mid = slow;
    return merge(sortList(head, mid), sortList(mid, tail));
}

ListNode* merge(ListNode* head1, ListNode* head2) {
    ListNode* dummyHead = new ListNode(0);
    ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
    while (temp1 != nullptr && temp2 != nullptr) {
        if (temp1->val <= temp2->val) {
            temp->next = temp1;
            temp1 = temp1->next;
        } else {
            temp->next = temp2;
            temp2 = temp2->next;
        }
        temp = temp->next;
    }
    if (temp1 != nullptr) {
        temp->next = temp1;
    } else if (temp2 != nullptr) {
        temp->next = temp2;
    }
    return dummyHead->next;
}

二叉树的最大深度

LeetCode链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description
题目描述：给定一个二叉树root，返回其最大深度。
关键：二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。通过递归调用函数实现需求。注意二叉树的节点在C++中的具体实现，其实和链表是类似的。不同的是二叉树的节点有两个指针，分别指向其两个子节点。
代码：

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(): val(0), left(nullptr), right(nullptr) {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }

    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {
    }
};

int maxDepth(TreeNode *root) {
    if (root == nullptr) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}


int main() {
    TreeNode node1 = {1, nullptr, nullptr};
    TreeNode node2 = {2, nullptr, nullptr};
    TreeNode node3 = {3, nullptr, nullptr};
    TreeNode node4 = {4, nullptr, nullptr};
    TreeNode node5 = {5, nullptr, nullptr};
    TreeNode node6 = {6, nullptr, nullptr};
    TreeNode node7 = {7, nullptr, nullptr};

    node1.left = &node2;
    node1.right = &node3;
    node2.left = &node4;
    node2.right = &node5;
    node5.left = &node6;
    node5.right = &node7;

    TreeNode *root = &node1;
    cout << maxDepth(root) << endl;

    return 0;
}

二叉树的直径

LeetCode链接：https://leetcode.cn/problems/diameter-of-binary-tree/description
题目描述：给你一棵二叉树的根节点，返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。
关键：可以使用深度优先搜索。定义一个递归函数depth(node)计算dnode，函数返回该节点为根的子树的深度。先递归调用左儿子和右儿子求得它们为根的子树的深度L和R。递归搜索每个节点并设一个全局变量ans记录dnode的最大值，最后返回ans-1即为树的直径。
代码：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(): val(0), left(nullptr), right(nullptr) {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }

    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {
    }
};

int ans;

int depth(TreeNode* rt){
    if (rt == NULL) {
        return 0; // 访问到空节点了，返回0
    }
    int L = depth(rt->left); // 左儿子为根的子树的深度
    int R = depth(rt->right); // 右儿子为根的子树的深度
    ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans
    return max(L, R) + 1; // 返回该节点为根的子树的深度
}

int diameterOfBinaryTree(TreeNode* root) {
    ans = 1;
    depth(root);
    return ans - 1;
}

二叉树的中序遍历

LeetCode链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/description
题目描述：给定一个二叉树的根节点root ，返回它的中序遍历。
关键：二叉树的遍历有多种方法，包括前序遍历、中序遍历和后序遍历。前序遍历访问顺序为根节点→左子树→右子树‌，中序遍历访问顺序为左子树→根节点→右子树‌，后序遍历访问顺序为左子树→右子树→根节点‌。对于中序遍历，整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
- inorder(root)表示当前遍历到root节点的答案，那么按照定义，我们只要递归调用
- inorder(root.left)来遍历root节点的左子树，然后将root节点的值加入答案，再递归调用
- inorder(root.right)来遍历root节点的右子树即可，递归终止的条件为碰到空节点。
代码：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(): val(0), left(nullptr), right(nullptr) {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }

    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {
    }
};

void inorder(TreeNode* root, vector<int>& res) {
    if (!root) {
        return;
    }
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    inorder(root, res);
    return res;
}

二叉树的层序遍历

LeetCode链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/description
题目描述：给你二叉树的根节点root，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。
关键：可以使用广度优先搜索。和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取si个元素。
代码：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(): val(0), left(nullptr), right(nullptr) {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }

    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {
    }
};

vector<vector<int>> levelOrder(TreeNode* root) {
    vector <vector <int>> ret;
    if (!root) {
        return ret;
    }

    queue <TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int currentLevelSize = q.size();
        ret.push_back(vector <int> ());
        for (int i = 1; i <= currentLevelSize; ++i) {
            auto node = q.front(); q.pop();
            ret.back().push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    
    return ret;
}

翻转二叉树

LeetCode链接：https://leetcode.cn/problems/invert-binary-tree/description
题目描述：给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。
关键：从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以root为根节点的整棵子树的翻转。
代码：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(): val(0), left(nullptr), right(nullptr) {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }

    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {
    }
};

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    TreeNode* left = invertTree(root->left);
    TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

对称二叉树

LeetCode链接：https://leetcode.cn/problems/symmetric-tree/description
题目描述：给你一个二叉树的根节点root，检查它是否轴对称。
关键：可以递归判断。如果一个树的左子树与右子树镜像对称，那么这个树是对称的。通过「同步移动」两个指针的方法来遍历这棵树，p指针和q指针一开始都指向这棵树的根，随后p右移时，q左移，p左移时，q右移。每次检查当前p和q节点的值是否相等，如果相等再判断左右子树是否对称。
代码：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(): val(0), left(nullptr), right(nullptr) {
    }

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
    }

    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {
    }
};

bool check(TreeNode *p, TreeNode *q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}

bool isSymmetric(TreeNode* root) {
    return check(root->left, root->right);
}

旋转图像

LeetCode链接：https://leetcode.cn/problems/rotate-image/description
题目描述：给定一个n×n的二维矩阵matrix表示一个图像。请你将图像顺时针旋转90度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
关键：核心是找到旋转前后元素之间的关系。对于矩阵中第i行的第j个元素，在旋转后，它出现在倒数第i列的第j个位置。
代码：

 void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    // C++ 这里的 = 拷贝是值拷贝，会得到一个新的数组
    auto matrix_new = matrix;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            matrix_new[j][n - i - 1] = matrix[i][j];
        }
    }
    // 这里也是值拷贝
    matrix = matrix_new;
}

搜索二维矩阵

LeetCode链接：https://leetcode.cn/problems/search-a-2d-matrix/description
题目描述：给你一个满足下述两条属性的mxn整数矩阵：每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数target，如果target在矩阵中，返回true；否则，返回false。
关键：最简单的方法是遍历整个二维矩阵并逐个比较。更加复杂的一点的算法是利用题目给出的矩阵元素性质采用二分查找。可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。
代码：

bool searchMatrix(vector<vector<int>> matrix, int target) {
    
    // upper_bound是C++标准库中的高效二分查找函数，主要用于在有序序列中定位第一个大于目标值的位置‌，包含在<algorithm>中
    auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {
        return b < a[0];
    });

    if (row == matrix.begin()) {
        return false;
    }
    --row;
    
    // binary_search是C++标准库中的高效查找函数，用于在有序序列中快速判断目标值是否存在‌，包含在<algorithm>中
    return binary_search(row->begin(), row->end(), target);
}

岛屿数量

LeetCode链接：https://leetcode.cn/problems/number-of-islands/solutions
题目描述：给你一个由’1’（陆地）和’0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
关键：可以采用深度优先搜索。可以将二维网格看成一个无向图，竖直或水平相邻的1之间有边相连。为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的1都会被重新标记为0。最终岛屿的数量就是我们进行深度优先搜索的次数。
代码：

void dfs(vector<vector<char>>& grid, int r, int c) {
    int nr = grid.size();
    int nc = grid[0].size();

    grid[r][c] = '0';
    if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
    if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
    if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
    if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
}


int numIslands(vector<vector<char>>& grid) {
    int nr = grid.size();
    if (!nr) return 0;
    int nc = grid[0].size();

    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
        for (int c = 0; c < nc; ++c) {
            if (grid[r][c] == '1') {
                ++num_islands;
                dfs(grid, r, c);
            }
        }
    }

    return num_islands;
}

矩形面积

LeetCode链接：https://leetcode.cn/problems/rectangle-area/description
题目描述：给你二维平面上两个由直线构成且边与坐标轴平行/垂直的矩形，请你计算并返回两个矩形覆盖的总面积。每个矩形由其左下顶点和右上顶点坐标表示：第一个矩形由其左下顶点(ax1, ay1)和右上顶点(ax2, ay2)定义。第二个矩形由其左下顶点(bx1, by1)和右上顶点(bx2, by2)定义。
关键：两个矩形覆盖的总面积等于两个矩形的面积之和减去两个矩形的重叠部分的面积。
代码：

int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
    int area1 = (ax2 - ax1) * (ay2 - ay1), area2 = (bx2 - bx1) * (by2 - by1);
    int overlapWidth = min(ax2, bx2) - max(ax1, bx1), overlapHeight = min(ay2, by2) - max(ay1, by1);
    int overlapArea = max(overlapWidth, 0) * max(overlapHeight, 0);
    return area1 + area2 - overlapArea;
}

圆和矩形是否有重叠

LeetCode链接：https://leetcode.cn/problems/circle-and-rectangle-overlapping/description
题目描述：给你一个以(radius, xCenter, yCenter)表示的圆和一个与坐标轴平行的矩形(x1, y1, x2, y2)，其中 (x1, y1)是矩形左下角的坐标，而(x2, y2)是右上角的坐标。如果圆和矩形有重叠的部分，请你返回true，否则返回false。换句话说，请你检测是否存在点(xi, yi)，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。
关键：圆心临界位置的轨迹是一个圆角矩形——如果尝试把圆心向「圆角矩形」内部移动，就一定会出现公共点；如果向「圆角矩形」外部移动，就不会出现公共点。那么问题就转化成了判断圆心是否在这个圆角矩形内，如果在就表示有公共点，否则没有公共点。
代码：

long long distance(int ux, int uy, int vx, int vy) {
    return (long long)pow(ux - vx, 2) + (long long)pow(uy - vy, 2);
}

bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
    /* 圆心在矩形内部 */
    if (x1 <= xCenter && xCenter <= x2 && y1 <= yCenter && yCenter <= y2) {
        return true;
    }
    /* 圆心在矩形上部*/
    if (x1 <= xCenter && xCenter <= x2 && y2 <= yCenter && yCenter <= y2 + radius) {
        return true;
    }
    /* 圆心在矩形下部*/
    if (x1 <= xCenter && xCenter <= x2 && y1 - radius <= yCenter && yCenter <= y1) {
        return true;
    }
    /* 圆心在矩形左部*/
    if (x1 - radius <= xCenter && xCenter <= x1 && y1 <= yCenter && yCenter <= y2) {
        return true;
    }
    /* 圆心在矩形右部*/
    if (x2 <= xCenter && xCenter <= x2 + radius && y1 <= yCenter && yCenter <= y2) {
        return true;
    }
    /* 矩形左上角 */
    if (distance(xCenter, yCenter, x1, y2) <= radius * radius)  {
        return true;
    }
    /* 矩形左下角 */
    if (distance(xCenter, yCenter, x1, y1) <= radius * radius) {
        return true;
    }
    /* 矩形右上角 */
    if (distance(xCenter, yCenter, x2, y2) <= radius * radius) {
        return true;
    }
    /* 矩形右下角 */
    if (distance(xCenter, yCenter, x1, y2) <= radius * radius) {
        return true;
    }
    /* 无交点 */
    return false;
}

完美矩形

LeetCode链接：https://leetcode.cn/problems/perfect-rectangle/description
题目描述：给你一个数组rectangles，其中rectangles[i] = [xi, yi, ai, bi]表示一个坐标轴平行的矩形。这个矩形的左下顶点是(xi, yi) ，右上顶点是(ai, bi)。如果所有矩形一起精确覆盖了某个矩形区域，则返回true；否则，返回false。
关键：由于精确覆盖意味着矩形的边和顶点会重合在一起，可统计每个矩形顶点的出现次数。除了要满足矩形区域的面积等于所有矩形的面积之和，还要满足矩形区域四角的顶点只能出现一次，且其余顶点的出现次数只能是两次或四次。在代码实现时，我们可以遍历矩形数组，计算矩形区域四个顶点的位置，以及矩形面积之和，并用哈希表统计每个矩形的顶点的出现次数。遍历完成后，检查矩形区域的面积是否等于所有矩形的面积之和，以及每个顶点的出现次数是否满足上述要求。
代码：

def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
    area, minX, minY, maxX, maxY = 0, rectangles[0][0], rectangles[0][1], rectangles[0][2], rectangles[0][3]
    cnt = defaultdict(int)
    for rect in rectangles:
        x, y, a, b = rect[0], rect[1], rect[2], rect[3]
        area += (a - x) * (b - y)

        minX = min(minX, x)
        minY = min(minY, y)
        maxX = max(maxX, a)
        maxY = max(maxY, b)

        cnt[(x, y)] += 1
        cnt[(x, b)] += 1
        cnt[(a, y)] += 1
        cnt[(a, b)] += 1

    if area != (maxX - minX) * (maxY - minY) or cnt[(minX, minY)] != 1 or cnt[(minX, maxY)] != 1 or cnt[(maxX, minY)] != 1 or cnt[(maxX, maxY)] != 1:
        return False

    del cnt[(minX, minY)], cnt[(minX, maxY)], cnt[(maxX, minY)], cnt[(maxX, maxY)]

    return all(c == 2 or c == 4 for c in cnt.values())

爬楼梯

LeetCode链接：https://leetcode.cn/problems/climbing-stairs/description
题目描述：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
关键：可以使用动态规划。
代码：

int climbStairs(int n) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i) {
        p = q; 
        q = r; 
        r = p + q;
    }
    return r;
}

Menu

LeetCode常见题目整理汇总1

Jul 30,2025 16121 words 58 min

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

两两交换链表中的节点

合并两个有序链表

反转链表

回文链表

环形链表

排序链表

二叉树的最大深度

二叉树的直径

二叉树的中序遍历

二叉树的层序遍历

翻转二叉树

对称二叉树

旋转图像

搜索二维矩阵

岛屿数量

矩形面积

圆和矩形是否有重叠

完美矩形

爬楼梯