我是靠谱客的博主 健壮面包,这篇文章主要介绍LeetCode高频面试题记录(一),现在分享给大家,希望可以做个参考。

LeetCode高频面试题记录(一)

K 个一组翻转链表 困难

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution { ListNode* reverseList(ListNode *a, ListNode *b){ ListNode *pre=NULL, *cur = a, *nxt; while (cur != b){ nxt = a->next; a = a->next; cur->next = pre; pre = cur; cur = nxt; } return pre; } public: ListNode* reverseKGroup(ListNode* head, int k) { if (head == NULL || head->next == NULL) return head; ListNode *a = head; ListNode *b = head; for (int i=0; i<k; i++){ if (b == NULL) return a; b = b->next; } ListNode *node = reverseList(a, b); a->next = reverseKGroup(b, k); return node; } };

买卖股票的最佳时机 III 困难
参考学习:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-wen/

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution { public: int maxProfit(vector<int>& prices) { if (prices.empty()) return 0; int max_k = 2; vector<vector<vector<int>>> dp(prices.size(),vector<vector<int>>(max_k+1,vector<int>(2,0))); for (int i=0; i<prices.size(); i++){ for (int k=max_k; k>=1; k--){ if (i-1 == -1){ dp[i][k][0] = 0; dp[i][k][1] = -prices[i]; continue; } dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]); dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]); } } return dp[prices.size()-1][max_k][0]; } };

最佳买卖股票时机含冷冻期 中等

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution { public: int maxProfit(vector<int>& prices) { if (prices.empty()) return 0; if (prices.size() < 2) return 0; vector<vector<int>> dp(prices.size(),vector<int>(2,0)); dp[0][0] = 0; // 第一天,不持有股票 dp[0][1] = -prices[0]; // 第一天,持有股票 dp[1][0] = max(dp[0][0], dp[0][1] + prices[1]); // 第二天,不持有股票 dp[1][1] = max(dp[0][0]-prices[1], dp[0][1]); // 第二天,持有股票 for (int i=2; i<prices.size(); i++){ dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]); dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i]); } return dp[prices.size()-1][0]; } };

买卖股票的最佳时机 II 简单

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution { public: int maxProfit(vector<int>& prices) { vector<vector<int>> dp(prices.size(), vector<int>(2, 0)); dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i=1; i<prices.size(); i++){ dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]); dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]); } return dp[prices.size()-1][0]; } };

三数之和 中等

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { if (nums.size() < 3) return {}; sort(nums.begin(), nums.end()); int left,right; vector<vector<int>> res; for (int i=0; i<nums.size(); i++){ if (nums[i] > 0) break; if (i > 0 && nums[i] == nums[i-1]) continue; left = i + 1; right = nums.size()-1; while (left < right){ int sum = nums[i] + nums[left] + nums[right]; if (sum == 0){ res.push_back({nums[i], nums[left], nums[right]}); while (left<right && nums[left] == nums[left+1]) left++; while (left<right && nums[right] == nums[right-1]) right--; left++; right--; } else if (sum > 0) right--; else left++; } } return res; } };

二叉树中的最大路径和 困难

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution { public: int PathSum(TreeNode* root, int& val) { if(root == NULL) return 0; // 若左子树和比0小,则它取值=0,因为加上负数,最大值会变小;右子树同理 int left_max = max(PathSum(root->left, val), 0); int right_max = max(PathSum(root->right, val), 0); int new_path_sum = root->val + right_max + left_max; // 如果new_path_sum < maxn, 则最大路径不包括当前的root节点,只包括左(或右)节点 val = max(val, new_path_sum); // 最大和路径只能是左子树 or 右子树,不能同时选 return root->val + max(left_max, right_max); } int maxPathSum(TreeNode* root) { int val = INT_MIN; PathSum(root, val); return val; } };

二叉树的右视图 中等
BFS

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution { public: vector<int> rightSideView(TreeNode* root) { if (root == NULL) return {}; vector<int> res; queue<TreeNode*> que; que.push(root); while (!que.empty()){ int len = que.size(); for (int i=0; i<len; i++){ auto temp = que.front(); que.pop(); if (i == len-1) res.push_back(temp->val); if (temp->left != NULL) que.push(temp->left); if (temp->right != NULL) que.push(temp->right); } } return res; } };

DFS

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution { vector<int> res; public: void dfs(TreeNode* root, int depth) { if (root == NULL) return; // 先访问 当前节点,再递归地访问 右子树 和 左子树。 // 如果当前节点所在深度还没有出现在res里,说明在该深度下当前节点是第一个被访问的节点,因此将当前节点加入res中。 if (depth == res.size()) res.push_back(root->val); depth++; dfs(root->right, depth);//注意这里是先访问右节点 dfs(root->left, depth); } vector<int> rightSideView(TreeNode* root) { if (root == NULL) return {}; dfs(root, 0); return res; } };

无重复字符的最长子串 中等偏难
学习网址:https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution { public: int lengthOfLongestSubstring(string s) { if (s.empty()) return 0; int res = 1; int k = 0; for (int i=1; i<s.length(); i++){ int temp = 1; for (int j=k; j<i; j++){ if (s[i] == s[j]) k = j + 1; else temp++; } res = max(res, temp); } return res; } };

滑窗思路

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char, int> window; int left = 0, right = 0; int res = 0; // 记录结果 while (right < s.size()) { char c = s[right]; right++; window[c]++;// 进行窗口内数据的一系列更新 // 判断左侧窗口是否要收缩 while (window[c] > 1) { char d = s[left]; left++; window[d]--;// 进行窗口内数据的一系列更新 } // 在这里更新答案 res = max(res, right - left); } return res; } };

找到字符串中所有字母异位词 中等偏难
滑窗模板——必须牢记

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution { public: vector<int> findAnagrams(string s, string p) { unordered_map<char, int> window; unordered_map<char, int> need; for (char c:p) need[c]++; int left = 0; int right = 0; int valid = 0; vector<int> res; while (right < s.length()){ char c = s[right]; right++; if (need.count(c) > 0){//扩大窗口 window[c]++; if (window[c] == need[c]) valid++; } while (right-left >= p.size()){ if (valid == need.size())//处理数据 res.push_back(left); char d = s[left]; left++; if (need.count(d) > 0){//缩小窗口 if (window[d] == need[d]) valid--; window[d]--; } } } return res; } };

最小覆盖子串 困难

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
string minWindow(string s, string t) { unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; int valid = 0; // 记录最小覆盖子串的起始索引及长度 int start = 0, len = INT_MAX; while (right < s.size()) { // c 是将移入窗口的字符 char c = s[right]; // 右移窗口 right++; // 进行窗口内数据的一系列更新 if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; } // 判断左侧窗口是否要收缩 while (valid == need.size()) { // 在这里更新最小覆盖子串 if (right - left < len) { start = left; len = right - left; } // d 是将移出窗口的字符 char d = s[left]; // 左移窗口 left++; // 进行窗口内数据的一系列更新 if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } // 返回最小覆盖子串 return len == INT_MAX ? "" : s.substr(start, len); }

合并两个有序数组 简单
看似简单,若是没思路还是做不出来,这道题要从后比较,避免移位

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i = m-1; int j = n-1; int t = m-1; while (i >= 0 && j >= 0){ if (nums1[i] < nums2[j]){ nums1[t+n] = nums2[j]; j--; } else{ nums1[t+n] = nums1[i]; i--; } t--; } for (int i=j; i>=0; i--,t--) nums1[t+n] = nums2[i]; } };

将有序数组转换为二叉搜索树 简单

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution { public: TreeNode* sortedArrayToBST(vector<int> nums) { if (nums.empty()) return NULL; int mid = nums.size() / 2; TreeNode* root = new TreeNode(nums[mid]); vector<int> leftTree(nums.begin(), nums.begin()+mid);//这里要注意,不是mid+1 vector<int> rightTree(nums.begin()+mid+1,nums.end()); root->left = sortedArrayToBST(leftTree); root->right = sortedArrayToBST(rightTree); return root; } };

先序遍历构造二叉树 简单

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution { public: TreeNode* bstFromPreorder(vector<int>& preorder) { if (preorder.empty()) return nullptr; TreeNode* root = new TreeNode(preorder[0]); int temp; for (int i=0;i<preorder.size();i++) if (preorder[0]<preorder[i]) {temp=i;break;} preorder.erase(preorder.begin()); vector<int> lpreorder(preorder.begin(), preorder.begin()+temp-1); vector<int> rpreorder(preorder.begin()+temp-1, preorder.end()); root->left = bstFromPreorder(lpreorder); root->right = bstFromPreorder(rpreorder); return root; } };

平衡二叉树 简单

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution { int depth(TreeNode* root){ if (root == NULL) return 0; int leftl = depth(root->left); int rightr = depth(root->right); return max(leftl, rightr)+1; } public: bool isBalanced(TreeNode* root) { if (root == NULL) return true; return isBalanced(root->left) && isBalanced(root->right) && (abs(depth(root->left)-depth(root->right))<2); } };

这个方法有大量重复递归,相对慢了。下面方法进行了剪枝

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution { int depth(TreeNode* root){ if (root == NULL) return 1; int l = depth(root->left); if (l == -1) return -1; int r = depth(root->right); if (r == -1) return -1; return (abs(l-r)<2) ? max(l, r)+1 : -1; } public: bool isBalanced(TreeNode* root) { return depth(root) != -1; } };

二叉树的最近公共祖先 中等

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || root == p || root == q) return root; TreeNode *left = lowestCommonAncestor(root->left, p, q); TreeNode *right = lowestCommonAncestor(root->right, p, q); if (left == NULL) return right; if (right== NULL) return left; return root; } };

零钱兑换 II 中等

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution { public: int change(int amount, vector<int>& coins) { vector<int> dp(amount+1, 0); dp[0] = 1; for (int i=0; i<coins.size(); i++){ for (int j=coins[i]; j<=amount; j++){ dp[j] += dp[j-coins[i]]; } } return dp[amount]; } };

零钱兑换 中等

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount+1, amount+1); dp[0] = 0; for (int i=1; i<=amount; i++){ int temp = amount+1; for (int j=0; j<coins.size(); j++){ if (i >= coins[j]) temp = min(dp[i-coins[j]], temp); } dp[i] = temp + 1; } return dp[amount] > amount ? -1 : dp[amount]; } };

删除排序链表中的重复元素 简单
思路理清楚就不难,链表要注意头尾节点的处理,这个搞清楚了就简单了

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (head == NULL || head->next == NULL) return head; ListNode* root = head; while (head != NULL && head->next != NULL){ if (head->val == head->next->val) head->next = head->next->next; else head = head->next; } return root; } };

删除排序链表中的重复元素 II 中等
这道题一定要理清思路,不然做不出来,实际思路其实不难,但一定要理清。链表题解题就是一定要思路清晰。借助头结点是常用方法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode* dummy = new ListNode(-1); dummy->next = head; ListNode *cur = dummy, *pre; while (cur){ pre = cur; cur = cur->next; while (cur && cur->next && cur->next->val == cur->val){ int temp = cur->val; while (cur && cur->val == temp) cur = cur->next; } pre->next = cur; } return dummy->next; } };

反转链表 简单

复制代码
1
2
3
4
5
6
7
8
9
10
11
class Solution { public: ListNode* reverseList(ListNode* head) { if (head == NULL || head->next == NULL) return head; ListNode* node = reverseList(head->next); head->next->next = head; head->next = NULL; return node;//注意返回谁 } };

两两交换链表中的节点 中等难度
这两道题有助于把递归可以想清楚,静态思考与动态思考。

复制代码
1
2
3
4
5
6
7
8
9
10
11
class Solution { public: ListNode* swapPairs(ListNode* head) { if (head == NULL || head->next == NULL) return head; ListNode* node = head->next; head->next = swapPairs(head->next->next); node->next = head; return node; } };

数组第K个最大数 中等
这道题我们可以构建最小堆来实现。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution { void heap(vector<int>& nums, int p){ for (int parant=p; parant*2+1<nums.size();){ int child = parant*2+1; if (child+1 < nums.size() && nums[child] > nums[child+1]) child++; if (nums[parant] <= nums[child]) break; swap(nums[parant], nums[child]); parant = child; } } void buildHeap(vector<int>& nums){ for (int i=nums.size()/2; i>=0; i--) heap(nums, i); } public: int findKthLargest(vector<int>& nums, int k) { vector<int> temp(nums.begin(), nums.begin()+k); buildHeap(temp);//这里我们是构建最小堆,最大堆其实不能很好的完成 for (int i=k; i<nums.size(); i++){ if (temp[0] < nums[i]){ temp[0] = nums[i];//插入元素 heap(temp, 0);//再次构建 } } return temp[0]; } };

螺旋矩阵 中等
这道题还是一样,要求把思路理清楚

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; int l=0; int t=0; int r=matrix[0].size()-1; int b=matrix.size()-1; vector<int> res; while (1){ for (int i=l; i<=r; i++) res.push_back(matrix[t][i]); if (++t > b) break; for (int i=t; i<=b; i++) res.push_back(matrix[i][r]); if (--r < l) break; for (int i=r; i>=l; i--) res.push_back(matrix[b][i]); if (--b < t) break; for (int i=b; i>=t; i--) res.push_back(matrix[i][l]); if (++l > r) break; } return res; } };

将每个元素替换为右侧最大元素 简单
看似简单并不简单,要想到才行
我个人用了双端队列来解决

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution { public: vector<int> replaceElements(vector<int>& arr) { deque<int> que; int len = arr.size()-1; que.push_front(arr[len]); for (int i=len; i>=1; i--){ int temp = que.front(); if (arr[i] >= temp) que.push_front(arr[i]); } vector<int> res; for (int i=0; i<arr.size()-1; i++){ if (arr[i] == que.front()) que.pop_front(); res.push_back(que.front()); } res.push_back(-1); return res; } };

不是最优解,下面解法是最优解

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution { public: vector<int> replaceElements(vector<int>& arr) { int n = arr.size(); vector<int> ans(n); ans[n - 1] = -1; for (int i = n - 2; i >= 0; --i) { ans[i] = max(ans[i + 1], arr[i + 1]); } return ans; } };

接雨水 困难

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution { public: int trap(vector<int>& height) { int left_max = 0; int right_max = 0; int res = 0; int left = 0; int right = height.size()-1; while (left < right){ if (height[left] <= height[right]){ if (height[left] >= left_max) left_max = height[left]; else res += left_max - height[left]; left++; } else{ if (height[right] >= right_max) right_max = height[right]; else res += right_max - height[right]; right--; } } return res; } };

相交链表 简单
链表的题都是看似简单,实际要注意NULL的问题

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA == NULL || headB == NULL) return NULL; ListNode *tempA = headA; ListNode *tempB = headB; while (tempA != tempB){ tempA = tempA->next; tempB = tempB->next; if (tempA == NULL && tempB == NULL)//这里同时为空时跳出,避免死循环 return NULL; if (tempA == NULL) tempA = headB; if (tempB == NULL) tempB = headA; } return tempA; } };

单词拆分 中等

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordDictSet; for (auto word: wordDict) wordDictSet.insert(word); vector<bool> dp(s.size()+1, false); dp[0] = true; for (int i=1; i<=s.size(); ++i) { for (int j=0; j<i; ++j) { if (dp[j] && wordDictSet.find(s.substr(j, i-j)) != wordDictSet.end()) { dp[i] = true; break; } } } return dp[s.size()]; } };

最后

以上就是健壮面包最近收集整理的关于LeetCode高频面试题记录(一)的全部内容,更多相关LeetCode高频面试题记录(一)内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(62)

评论列表共有 0 条评论

立即
投稿
返回
顶部