二叉搜索树中第K小的元素 中等 递归提前终止与记录所需数据的典型题
class Solution { int i = 0; int res = 0; public: int kthSmallest(TreeNode* root, int k) { if (root == nullptr) return 0; int l = kthSmallest(root->left, k); if (++i == k) {res = root->val; return res;} int r = kthSmallest(root->right, k); return res; } };这道题使用栈也是可以做的
剑指 Offer 61. 扑克牌中的顺子 简单 依然是一道看似简单的题，想不到思路也做不出来
class Solution { public: bool isStraight(vector<int>& nums) {//不能有重复元素,最大的牌不能比非0最小牌大4 sort(nums.begin(),nums.end()); int i = 0 ; while(nums[i]==0)i++; for(int j =i;j<4;j++){ //判断其中是否有大小相同的牌 if(nums[j] == nums[j+1]) return false; } //最大的牌和非0最小牌不能超过4 return nums[4]-nums[i]<=4; } };二叉树的直径 简单题
class Solution { int res = 0; int depth(TreeNode* root){ if (root == NULL) return 0; int l = depth(root->left); int r = depth(root->right); return max(l, r) + 1; } public: int diameterOfBinaryTree(TreeNode* root) { if (root == NULL) return 0; res = max(res, depth(root->left)+depth(root->right)); res = max(res, diameterOfBinaryTree(root->left)); res = max(res, diameterOfBinaryTree(root->right)); return res; } };这不是最优解，一般简单都会有个问题，就是重复递归，作为简单题，面试官肯定会追问这个问题，因此我们需要最优解，这样才能在面试时百战百胜
class Solution { 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; // 返回该节点为根的子树的深度 } public: int diameterOfBinaryTree(TreeNode* root) { ans = 1; depth(root); return ans - 1; } };路径总和 简单 这类题很多，记住下面的模板
class Solution { bool pathSum(TreeNode* root, int sum){ if (root == NULL) return false; sum -= root->val; if (sum == 0 && root->left == NULL && root->right == NULL) return true; return pathSum(root->left, sum) || pathSum(root->right, sum); } public: bool hasPathSum(TreeNode* root, int sum) { return pathSum(root, sum); } };路径总和 II 重点 一样的模板
class Solution { vector<vector<int>> res; void hasPathSum(TreeNode* root, int sum, vector<int> temp){ if (root == NULL) return; sum -= root->val; temp.push_back(root->val); if (sum == 0 && root->left == NULL && root->right == NULL) res.push_back(temp); hasPathSum(root->left, sum, temp); hasPathSum(root->right, sum, temp); } public: vector<vector<int>> pathSum(TreeNode* root, int sum) { if (root == NULL) return {}; vector<int> temp; hasPathSum(root, sum, temp); return res; } };二叉树中的最大路径和 困难
class Solution { int res = INT_MIN; int pathSum(TreeNode* root){ if (root == NULL) return 0; // 递归计算左右子节点的最大贡献值 // 只有在最大贡献值大于 0 时，才会选取对应子节点 int l = max(pathSum(root->left), 0); int r = max(pathSum(root->right), 0); // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值 res = max(res, root->val+l+r); // 返回节点的最大贡献值 return root->val+max(l, r); } public: int maxPathSum(TreeNode* root) { pathSum(root); return res; } };打家劫舍 II 中等 循环数组打劫，需要注意的是首位相邻了。
class Solution { int robrob(vector<int>& nums){ if (nums.empty()) return 0; vector<int> dp(nums.size()+2, 0); int res = 0; for (int i=0; i<nums.size(); i++){ dp[i+2] = max(dp[i+1], dp[i]+nums[i]); res = max(dp[i+2], res); } return res; } public: int rob(vector<int>& nums) { if (nums.empty()) return 0; if (nums.size() == 1) return nums[0]; vector<int> dp1(nums.begin(), nums.end()-1); vector<int> dp2(nums.begin()+1, nums.end()-1); vector<int> dp3(nums.begin()+1, nums.end()); return max(max(robrob(dp1), robrob(dp2)), robrob(dp3)); } };打家劫舍 III 中等
class Solution { //pair的含义：<最大值(包含当前节点)，最大值(不包含当前节点)> pair<int, int> dfs(TreeNode *root) { if (root == nullptr) return {0, 0}; auto l_pair = dfs(root->left); auto r_pair = dfs(root->right); auto rob1 = root->val + l_pair.second + r_pair.second; auto rob2 = max(l_pair.first, l_pair.second) + max(r_pair.first,r_pair.second); return {rob1, rob2}; } public: int rob(TreeNode* root) { auto res = dfs(root); return max(res.first, res.second); } };有效的括号 简单 用模拟法，加入栈，适时弹出匹配的，最后栈不为空为false，否则true
class Solution { public: bool isValid(string s) { if (s.empty()) return true; stack<char> stk; for (int i=0; i<s.length(); i++){ switch (s[i]){ case '(': stk.push(s[i]); break; case '[': stk.push(s[i]); break; case '{': stk.push(s[i]); break; case ')': if (!stk.empty() && stk.top()=='(') stk.pop(); else stk.push(s[i]); break; case ']': if (!stk.empty() && stk.top()=='[') stk.pop(); else stk.push(s[i]); break; case '}': if (!stk.empty() && stk.top()=='{') stk.pop(); else stk.push(s[i]); break; default: break; } } if (!stk.empty()) return false; return true; } };有效括号的嵌套深度 中等 这种题随缘吧，没见过真做不出来
class Solution { public: /* 知道如何计算嵌套深度，问题就很简单了：只要在遍历过程中，我们保证栈内一半的括号属于序列 A，一半的括号属于序列 B，那么就能保证拆分后最大的嵌套深度最小，是当前最大嵌套深度的一半。要实现这样的对半分配，我们只需要把奇数层的 ( 分配给 A，偶数层的 ( 分配给 B 即可。对于上面的例子，我们将嵌套深度为 1 和 3 的所有括号 (()) 分配给 A，嵌套深度为 2 的所有括号 ()()() 分配给 B。 此外，由于在这个问题中，栈中只会存放 (，因此我们不需要维护一个真正的栈，只需要用一个变量模拟记录栈的大小。 */ vector<int> maxDepthAfterSplit(string seq) { int d = 0; vector<int> ans; for (char& c : seq) if (c == '(') { ++d; ans.push_back(d % 2); } else { ans.push_back(d % 2); --d; } return ans; } };最长有效括号 困难
class Solution { public: int longestValidParentheses(string s) { int maxans = 0; stack<int> stk; stk.push(-1); for (int i = 0; i < s.length(); i++) { if (s[i] == '(') stk.push(i); else{ stk.pop(); if (stk.empty()) stk.push(i); else maxans = max(maxans, i-stk.top()); } } return maxans; } };括号生成 中等
class Solution { vector<string> res; void helper(string s, int ln, int rn, int n){ if (ln < 0 || rn < 0) return; if (s.length() == n && ln == rn) res.push_back(s); helper(s+'(', ln-1, rn, n); if (ln < rn) helper(s+')', ln, rn-1, n); } public: vector<string> generateParenthesis(int n) { helper("", n, n, 2*n); return res; } };奇偶链表 中等 注意这种题，分奇偶，那么可以进行拆分处理
class Solution { public: ListNode* oddEvenList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* node1 = new ListNode(-1); ListNode* root1 = node1; ListNode* node2 = new ListNode(-1); ListNode* root2 = node2; int i = 0; while (head != nullptr){ if (i % 2 == 0){ node1->next = head; node1 = node1->next; } else{ node2->next = head; node2 = node2->next; } head = head->next; i++; } node2->next = nullptr; node1->next = root2->next; return root1->next; } };合并区间 中等 理清思路就不难。学会面试的时候边做边分析
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vector<vector<int>> res; res.push_back(intervals[0]); for (int i=1; i<intervals.size(); i++){ auto temp = res.back(); res.pop_back(); if (intervals[i][0] <= temp[1]) { temp[0] = min(intervals[i][0], temp[0]); temp[1] = max(intervals[i][1], temp[1]); res.push_back(temp); } else{ res.push_back(temp); res.push_back(intervals[i]); } } return res; } };合并K个排序链表 困难
ListNode* mergeKLists(vector<ListNode*>& lists) { if (lists.empty()) return NULL; auto mycmp = [](const ListNode* a, const ListNode* b){return a->val > b->val;}; priority_queue<ListNode*, vector<ListNode*>, decltype(mycmp)> que(mycmp); for (auto node:lists) { if (node != NULL)//排除为NULL的情况 que.push(node); } ListNode* node = new ListNode(-1); ListNode* root = node; while (!que.empty()) { auto temp = que.top(); que.pop(); node->next = temp; node = node->next; if (temp->next != NULL)//排除为NULL的情况 que.push(temp->next); } return root->next; }手写堆
class Solution { void heap(vector<ListNode*>& lists, int p){ for (int parent=p; parent*2+1<lists.size();){ int child = parent*2+1; if (child+1<lists.size() && lists[child]->val>lists[child+1]->val) child++; if (lists[parent]->val < lists[child]->val) break; swap(lists[parent], lists[child]); parent = child; } } void createheap(vector<ListNode*>& lists){ for (int i=lists.size()/2; i>=0; i--) heap(lists, i); } public: ListNode* mergeKLists(vector<ListNode*>& lists) { if (lists.empty()) return NULL; vector<ListNode*> res; for (auto l:lists)//排除NULL的情况 if (l != NULL) res.push_back(l); createheap(res); ListNode* node = new ListNode(-1); ListNode* root = node; while (!res.empty()) { auto temp = res[0]; res.erase(res.begin());//数组这里效率是很低的，不过没想到好办法 node->next = temp; node = node->next; if (temp->next != NULL)//排除NULL的情况 res.insert(res.begin(), temp->next); heap(res, 0); } return root->next; } };最长公共子序列 中等 动态规划经典问题，学会自己找子结构和递推公式
class Solution { public: int longestCommonSubsequence(string text1, string text2) { /* dp(X, Y) dp(X-1, Y-1)+1 s1[X-1] == s2[Y-1] max(dp(X, Y-1), dp(X-1, Y)) s1[X-1] != s2[Y-1] */ if (text1.empty() || text2.empty()) return 0; vector<vector<int>> dp(text1.length()+1, vector<int>(text2.length()+1, 0)); for (int i=0; i<text1.length(); i++){ for (int j=0; j<text2.length(); j++){ if (text1[i] == text2[j]) dp[i+1][j+1] = dp[i][j] + 1; else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]); } } return dp[text1.length()][text2.length()]; } };