题目链接：合并 K 个升序链表给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。方法一：暴力/** * Definition for singly-linked list. * 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) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { vector<int> nodes; for (int i = 0;i < lists.size();i++) { ListNode* cur = lists[i]; while (cur != nullptr) { nodes.push_back(cur->val); cur = cur->next; } } sort(nodes.begin(),nodes.end()); ListNode head(0); ListNode* tmp = &head; //tmp = nullptr; //head->next = tmp; for (int i = 0;i < nodes.size();i++) { tmp->next = new ListNode(nodes[i]); tmp = tmp->next; } return head.next; } };
题目链接：K 个一组翻转链表给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。方法一：链表反转class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { // 统计节点个数 int n = 0; for (ListNode* cur = head; cur; cur = cur->next) { n++; } ListNode dummy(0, head); ListNode* p0 = &dummy; ListNode* pre = nullptr; ListNode* cur = head; // k 个一组处理 for (; n >= k; n -= k) { for (int i = 0; i < k; i++) { // 同 92 题 ListNode* nxt = cur->next; cur->next = pre; // 每次循环只修改一个 next，方便大家理解 pre = cur; cur = nxt; } ListNode* nxt = p0->next; // p0->next 是小循环最后一个节点 （即开头的第一个节点，反转后变成小循环最后一个节点） p0->next->next = cur; // cur 是下一个循环开始 ，把本次循环最后一个节点（p0->next）连接新一轮循环 p0->next = pre; //把p0->next 指向反转后的第一个节点（反转前的最后一个节点）用来连接旧循环和本次循环 p0 = nxt; // p0变成本次循环最后一个点 即新循环上一个点 } return dummy.next; } };
题目链接：二叉树中的最大路径和二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。方法一：递归/** * Definition for a binary tree node. * 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) {} * }; */ class Solution { public: int dfs(TreeNode* root,int &ans) { if (root == nullptr) return 0; int l_val = dfs(root->left,ans); int r_val = dfs(root->right,ans); ans = max(ans,l_val+r_val+root->val); return max(max(l_val,r_val) + root->val,0); } int maxPathSum(TreeNode* root) { int ans = INT_MIN; dfs(root,ans); return ans; } };
题目链接：数据流的中位数中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。例如 arr = [2,3,4] 的中位数是 3 。例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。实现 MedianFinder 类:MedianFinder() 初始化 MedianFinder 对象。void addNum(int num) 将数据流中的整数 num 添加到数据结构中。double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。方法一：堆class MedianFinder { public: priority_queue<int, vector<int>, greater<int>> A; // 小顶堆，保存较大的一半 priority_queue<int, vector<int>, less<int>> B; // 大顶堆，保存较小的一半 MedianFinder() { } void addNum(int num) { if (A.size() != B.size()) { A.push(num); B.push(A.top()); A.pop(); } else { B.push(num); A.push(B.top()); B.pop(); } } double findMedian() { return A.size() != B.size() ? A.top() : (A.top() + B.top()) / 2.0; } };
题目链接：柱状图中最大的矩形给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。方法一：单调栈class Solution { public: int largestRectangleArea(vector<int>& heights) { heights.insert(heights.begin(),0); heights.push_back(0); stack<int> s; int res = 0; for (int i = 0;i < heights.size();i++) { while (s.size() && heights[s.top()] > heights[i]) { int cur = s.top(); s.pop(); res = max(res,(i - 1 - s.top()) * heights[cur]); } s.push(i); } return res; } };
题目链接：最长有效括号给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。方法一：栈class Solution { public: int longestValidParentheses(string s) { vector<int> t; stack<int> ss; for (int i = 0;i < s.size();i++) { if (s[i] == '(') { ss.push(i); }else { if (ss.size() && s[ss.top()] == '(') { t.push_back(ss.top()); t.push_back(i); ss.pop(); } } } int ans = 0; int tt = 1; sort(t.begin(),t.end()); for (int i = 1;i < t.size();i++) { if (t[i] == t[i-1] + 1) { tt++; ans = max(ans,tt); }else { tt = 1; } } return ans; } };
题目链接：N 皇后按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。方法一：回溯class Solution { public: vector<vector<string>> ans; int m[15][15]; bool check(int x,int y,int n) { for (int i = 0;i < x;i++) { if (m[i][y]) return false; } for (int i = 0;i < y;i++) { if (m[x][i]) return false; } int num = min(x,y); // 左上 for (int i = 1;i <= num;i++) { if (m[x-i][y-i]) return false; } num = min(x,n-y); //右上 for (int i = 1;i <= num;i++) { if (m[x-i][y+i]) return false; } num = min(n-x,n-y); return true; } void f(int n,int x) { if (x >= n) { vector<string> t; for (int i = 0;i < n;i++) { string s = ""; for (int j = 0;j < n;j++) { if (m[i][j] == 1) { s += "Q"; }else { s += "."; } } t.push_back(s); } ans.push_back(t); return ; } for (int i = 0;i < n;i++) { if (check(x,i,n)) { m[x][i] = 1; f(n,x+1); m[x][i] = 0; } } } vector<vector<string>> solveNQueens(int n) { f(n,0); return ans; } };
题目链接：缺失的第一个正数给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。方法：哈希表class Solution { public: int firstMissingPositive(vector<int>& nums) { unordered_map<int,int> m; for (int num:nums) { m[num]++; } for (int i = 1;i <= nums.size();i++) { if (m.find(i) == m.end()) return i; } return 0; } };
题目链接：最小覆盖子串给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。方法：滑动窗口class Solution { public: string minWindow(string s, string t) { if (s.empty() || t.empty() || t.size() > s.size()) { return ""; } int need[128] = {0}; for (char c : t) { need[(unsigned char)c]++; } int needCount = t.size(); // 还需要匹配多少字符 int left = 0, right = 0; int minLen = INT_MAX; // 当前找到的最短长度 int start = 0; // 最优区间的起始位置 while (right < (int)s.size()) { char rc = s[right]; if (need[(unsigned char)rc] > 0) { needCount--; // 用掉一个需要的字符 } need[(unsigned char)rc]--; // 窗口中多了一个 rc right++; // 当前窗口已经包含了所有需要的字符，开始尽量缩小左边界 while (needCount == 0) { // 更新最小区间 if (right - left < minLen) { minLen = right - left; start = left; } char lc = s[left]; need[(unsigned char)lc]++; // 移出左边字符 if (need[(unsigned char)lc] > 0) { // 移出了一个“必须”的字符，窗口不再满足条件 needCount++; } left++; } } // 注意 substr 的第二个参数是长度，不是右边界 return minLen == INT_MAX ? "" : s.substr(start, minLen); } };
题目链接：滑动窗口最大值给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。方法：单调队列class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { if (nums.size() == 0 || k == 0) return {}; deque<int> d; vector<int> res(nums.size()-k+1); for (int j = 0,i = 1-k; j < nums.size();i++,j++) { if (i > 0 && d.front() == nums[i-1]) { d.pop_front(); } while (!d.empty() && d.back() < nums[j]) d.pop_back(); d.push_back(nums[j]); if (i >= 0) { res[i] = d.front(); } } return res; } };