2.11#
长度最小的子数组 (掌握程度：中)#
滑动窗口 + 前缀和 难度不高，知道怎么写就还好
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int left = 0, sum = 0, ans = INT_MAX;
for (int right = 0; right < n; right++) {
sum += nums[right];
while (sum >= target) {
ans = min(ans, right - left + 1);
sum -= nums[left];
left++;
}
}
return ans == INT_MAX ? 0 : ans;
}
};两两交换链表中的节点 (掌握程度：高)#
一道链表，不过这个要用哨兵节点之前有一次写就忘记了，然后就是两个节点的交换要注意一下顺序，否则就会失败
/**
* 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* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = dummy;
while (cur->next && cur->next->next) {
ListNode* first = cur->next;
ListNode* second = cur->next->next;
first->next = second->next;
second->next = first;
cur->next = second;
cur = first;
}
return dummy->next;
}
};基本计算器 II (掌握程度：低)#
知道是栈，但是具体实现还是有点记不住
class Solution {
public:
int calculate(string s) {
stack<int> numSt;
char op = '+';
int num = 0;
int n = s.size();
for (int i = 0; i < n; i++) {
if (s[i] >= '0' && s[i] <= '9') {
num = num * 10 + (s[i] - '0');
}
if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
if (op == '+') {
numSt.push(num);
} else if (op == '-') {
numSt.push(-num);
} else if (op == '*') {
int last = numSt.top(); numSt.pop();
numSt.push(last * num);
} else if (op == '/') {
int last = numSt.top(); numSt.pop();
numSt.push(last / num);
}
op = s[i];
num = 0;
}
}
int ans = 0;
while (!numSt.empty()) {
ans += numSt.top();
numSt.pop();
}
return ans;
}
};删除排序链表中的重复元素 (掌握程度：高)#
简单题，删除而且不需要哨兵节点
/**
* 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) {
if (head == nullptr) return nullptr;
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
int val = cur->val;
if (cur->next->val == val) {
cur->next = cur->next->next;
} else {
cur = cur->next;
}
}
return head;
}
};翻转二叉树 (掌握程度：高)#
二叉树的简单题，有点类似那个对称二叉树
/**
* 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* invertTree(TreeNode* root) {
if (root == nullptr) return root;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};多数元素 (掌握程度：中)#
正常来说，用排序取中间值就行，但是面试很大可能是让我们写摩尔投票，这个我就不太熟练了
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = 0;
int votes = 0;
for (int i = 0; i < nums.size(); i++) {
int num = nums[i];
if (votes == 0) {
candidate = num;
votes = 1;
} else if (num == candidate) {
votes++;
} else {
votes--;
}
}
return candidate;
}
};移动零 (掌握程度：高)#
双指针简单题，将非零的元素放在前面
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int i0 = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
swap(nums[i], nums[i0]);
i0++;
}
}
}
};单词拆分 (掌握程度：中)#
热题100的，要用上哈希和动态规划
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
unordered_set<string> set(wordDict.begin(), wordDict.end());
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 0; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && set.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};最长重复子数组 (掌握程度：中)#
多维动态规划
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
int ans = 0;
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (nums1[i] == nums2[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
ans = max(ans, dp[i + 1][j + 1]);
}
}
}
return ans;
}
};