1.31#
前K个高频元素 (掌握程度：低) [面试未做出]#
想到是桶排序了，但是具体的部分未实现出来，然后面试官还不知道这个解法，下去还是得重点看一下
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
int maxCnt = 0;
for (int x : nums) {
cnt[x]++;
maxCnt = max(maxCnt, cnt[x]);
}
vector<vector<int>> buckets(maxCnt + 1);
for (auto& [x, count] : cnt) {
buckets[count].push_back(x);
}
vector<int> ans;
for (int i = maxCnt; i >= 0 && ans.size() < k; i--) {
for (int num : buckets[i]) {
ans.push_back(num);
if (ans.size() == k) break;
}
}
return ans;
}
};func topKFrequent(words []string, k int) []int {
feq := map[string]int{}
maxCnt := 0
for _, word := range words {
feq[word]++
maxCnt = max(maxCnt, feq[word])
}
buckets := make([][]string, maxCnt + 1)
for word, cnt := range feq {
buckets[cnt] = append(buckets[cnt], word)
}
res := []string{}
for i := maxCnt; i >= 0 && len(res) < k; i-- {
for _, word := range buckets[i] {
res = append(res, word)
if len(res) == k {
break
}
}
}
return res;
}接雨水 (掌握程度： 中)#
双指针，但是边界处理还是记得不太清楚
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int sufMax = height[n - 1], preMax = height[0];
int ans = 0, left = 0, right = n - 1;
while (left < right) {
preMax = max(preMax, height[left]);
sufMax = max(sufMax, height[right]);
if (preMax < sufMax) {
ans += preMax - height[left];
left++;
} else {
ans += sufMax - height[right];
right--;
}
}
return ans;
}
};最长公共子序列 (掌握程度：高)#
转移方程是我见过最简单之一的多维动态规划了
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n1 = text1.size(), n2 = text2.size();
vector<vector<int>> dp(n1 + 1, vector<int> (n2 + 1, 0));
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; 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[n1][n2];
}
};二叉树中的最大路径和 (掌握程度：中)#
刷了很多次的最大路径和，还是较为熟练的，除了递归的返回值
/**
* 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 ans = INT_MIN;
int dfs(TreeNode* node) {
if (node == nullptr) return 0;
int left = dfs(node->left);
int right = dfs(node->right);
ans = max(ans, left + right + node->val);
return max(0, max(left, right) + node->val);
}
int maxPathSum(TreeNode* root) {
dfs(root);
return ans;
}
};复原IP地址 (掌握程度：低)#
只知道是回溯，但是具体实现是一点都不知道
class Solution {
public:
vector<string> ans;
string path;
void dfs(string s, int n, int part, int i) {
if (part == 4) {
if (i == n) {
ans.push_back(path);
}
return;
}
int num = 0;
int len = path.size();
for (int j = i; j < n && j < i + 3; j++) {
num = num * 10 + (s[j] - '0');
if (num > 255) break;
if (j > i && s[i] == '0') break;
if (part > 0) path.push_back('.');
path += s.substr(i, j - i + 1);
dfs(s, n, part + 1, j + 1);
path.resize(len);
}
}
vector<string> restoreIpAddresses(string s) {
dfs(s, s.size(), 0, 0);
return ans;
}
};删除排序链表中的重复元素 II (掌握程度：中)#
除了刚开始没想起来要用哨兵节点，中间的循环还是有点印象的，因为要把所有重复的都删除了就意味着本身也要被删除，所以需要将节点前移一位避免节点断开
/**
* 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* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = dummy;
while (cur->next && cur->next->next) {
int val = cur->next->val;
if (cur->next->next->val = val) {
while (cur->next && cur->next->val = val) {
cur->next = cur->next->next;
}
} else {
cur = cur->next;
}
}
return dummy->next;
}
};