LeetCode高频面试题记录（一）

83 阅读 0 评论 55 点赞

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

LeetCode高频面试题记录（一）

K 个一组翻转链表困难

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/

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];
}
};

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

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 简单

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];
}
};

三数之和中等

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;
}
};

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

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

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

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-/

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;
}
};

滑窗思路

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;
}
};

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

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;
}
};

最小覆盖子串困难

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);
}

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

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];
}
};

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

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;
}
};

先序遍历构造二叉树简单

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;
}
};

平衡二叉树简单

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);
}
};

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

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;
}
};

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

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 中等

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];
}
};

零钱兑换中等

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];
}
};

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

/**
* 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 中等
这道题一定要理清思路，不然做不出来，实际思路其实不难，但一定要理清。链表题解题就是一定要思路清晰。借助头结点是常用方法

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;
}
};

反转链表简单

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;//注意返回谁
}
};

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

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个最大数中等
这道题我们可以构建最小堆来实现。

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];
}
};

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

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;
}
};

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

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;
}
};

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

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;
}
};

接雨水困难

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的问题

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;
}
};

单词拆分中等

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()];
}
};