2.3#
x 的平方根 (掌握程度： 低)#
只记得是二分但是具体的一点都不太清楚，所以还是抄的题解
class Solution {
public:
int mySqrt(int x) {
int left = 0, right = x;
int ans = 0;
while (left <= right) {
long long mid = (left + right) / 2;
if (mid * mid <= x) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
};滑动窗口最大值 (掌握程度：低)#
难度有点大的滑动窗口，因为这个用上了单调双向队列去解决的，不像其他的滑动窗口都是用双指针加哈希实现的，这个后续得花功夫去理解
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> ans;
deque<int> q;
for (int i = 0; i < n; i++) {
while (!q.empty() && nums[q.back()] <= nums[i]) {
q.pop_back();
}
q.push_back(i);
int leftIdx = i - k + 1;
if (q.front() < leftIdx) {
q.pop_front();
}
if (leftIdx >= 0) {
ans.push_back(nums[q.front()]);
}
}
return ans;
}
};最长有效括号 (掌握程度： 中)#
栈的处理我还是知道的，除了哨兵下标的存在和中间的答案的处理有点记不太清楚
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size();
int ans = 0;
stack<int> st;
st.push(-1);
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
st.push(i);
} else {
st.pop();
if (st.empty()) {
st.push(i);
}
ans = max(ans, i - st.top());
}
}
return ans;
}
};下一个排列 (掌握程度：低)#
一个对编码能力要求不高的题，但是很考验思维能力
- 为了满足最小变化，所以需要从最右边找到第一个非单调递减的数 如 123654 的3 所以 i = 2， nums[i] = 3
- 再从最右边开始找，找到一个最小但是比nums[i] 要大一点的数，123654 的 4 所以 j = 5, nums[j] = 4
- 交换之后 124653， 最后将交换的i的后面反转就变成最小的数了 124356
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = n - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}
};字符串转换整数 (atoi) (掌握程度：低)#
一点都不会写的题，考我我就等死吧我去了
class Solution {
public:
int myAtoi(string s) {
int n = s.size();
int ans = 0, i = 0, flag = 1;
while(s[i] == ' ') i++;
if (s[i] == '-') flag = -1;
if (s[i] == '+' || s[i] == '-') i++;
while (i < n && isdigit(s[i])) {
int num = s[i] - '0';
if (ans > INT_MAX / 10 || (ans == INT_MAX / 10 && num > 7)) {
return flag > 0 ? INT_MAX : INT_MIN;
}
ans = ans * 10 + num;
i++;
}
return flag > 0 ? ans : -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* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
int carry = 0;
while(l1 || l2 || carry > 0) {
int sum = carry;
if (l1) {
sum += l1->val;
l1 = l1->next;
}
if (l2) {
sum += l2->val;
l2 = l2->next;
}
ListNode* newNode = new ListNode(sum % 10);
cur->next = newNode;
cur = cur->next;
carry = sum / 10;
}
return dummy->next;
}
};爬楼梯 (掌握程度： 高)#
动态规划的简单题，动态规划那一套都懂，但是初始化和转移方程真的太难了
class Solution {
public:
int climbStairs(int n) {
vector<long long> dp(n + 2);
dp[0] = dp[1] = 1;
for (int i = 0; i < n; i++) {
dp[i + 2] = dp[i + 1] + dp[i];
}
return dp[n];
}
};零钱兑换 (掌握程度： 中)#
零钱兑换做了挺多次的了好像，但是还是记得不太清楚，边界处理和转移方程忘记了
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
if (dp[amount] > amount) return -1;
return dp[amount];
}
};字符串相乘 (掌握程度：低)#
一点都不会啊，完全没有头绪，看来只能背下来了
class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") return "0";
int m = num1.size(), n = num2.size();
vector<int> res(m + n, 0);
// 从最低位开始相乘
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int mul = (num1[i] - '0') * (num2[j] - '0');
int sum = mul + res[i + j + 1];
res[i + j + 1] = sum % 10; // 当前位
res[i + j] += sum / 10; // 进位
}
}
// 跳过前导 0
string ans;
for (int i = 0; i < m + n; i++) {
if (!(ans.empty() && res[i] == 0)) {
ans += res[i] + '0';
}
}
return ans;
}
};最小覆盖子串 (掌握程度：低)#
知道怎么写但是具体实现记得不太清楚了，是双指针结合哈希表形成的滑动窗口
class Solution {
public:
string minWindow(string s, string t) {
int cnt[128]{};
for(char c : t) cnt[c]++;
int left = 0, right = 0;
int need = t.size(), minLen = INT_MAX, start =0;
while (right < s.size()) {
if (cnt[s[right]] > 0) need--;
cnt[s[right]]--;
right++;
while (need == 0) {
if (right - left < minLen) {
minLen = right - left;
start = left;
}
cnt[s[left]]++;
if (cnt[s[left]] > 0) need++;
left++;
}
}
return minLen == INT_MAX ? "" : s.substr(start, minLen);
}
};