2.4#
缺失的第一个正数 (掌握程度：低)#
完全不会的题，这个也太难了，只知道要做原地换值但是却不知道怎么写
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// 1. 原地哈希
for (int i = 0; i < n; i++) {
//nums[i] != nums[nums[i] - 1]) 表示 x 对应的值不在值应在的下标 值1对应下标0
while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
// 2. 查找第一个缺失的正数
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 3. 如果 1..n 都在
return n + 1;
}
};从前序与中序遍历序列构造二叉树 (掌握程度：低)#
又在冒充中等题了，这个这么难竟然还是中等题，一点都不会
/**
* 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:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode* build(vector<int>& preorder, int pL, int pR, vector<int>& inorder, int iL, int iR) {
if (pL > pR) return nullptr;
// 1. 根节点
int rootVal = preorder[pL];
TreeNode* root = new TreeNode(rootVal);
// 2. 在 inorder 中找到根
int k = iL;
while (inorder[k] != rootVal) k++;
int leftSize = k - iL;
// 3. 构建左右子树
root->left = build(preorder, pL + 1, pL + leftSize, inorder, iL, k - 1);
root->right = build(preorder, pL + leftSize + 1, pR, inorder, k + 1, iR);
return root;
}
};子集 (掌握程度：中)#
选与不选的经典回溯
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void dfs(vector<int>& nums, int i, int n) {
if (i == n) {
ans.push_back(path);
return;
}
dfs(nums, i + 1, n);
path.push_back(nums[i]);
dfs(nums, i + 1, n);
path.pop_back();
}
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0, nums.size());
return ans;
}
};链表中倒数的第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* trainingPlan(ListNode* head, int cnt) {
ListNode* fast = head;
for (int i = 0; i < cnt; i++) {
fast = fast->next;
}
ListNode* slow = head;
while (fast) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
};反转字符串中的单词 (掌握程度：中)#
会写但是具体实现还是有点记不住
class Solution {
public:
string reverseWords(string s) {
string ans = "";
int n = s.size();
int i = n - 1;
while (i >= 0) {
while (i >= 0 && s[i] == ' ') i--;
if (i < 0) break;
int j = i;
while (j >= 0 && s[j] != ' ') j--;
if (!ans.empty()) ans.push_back(' ');
ans += s.substr(j + 1, i - j);
i = j - 1;
}
return ans;
}
};