1. 括号生成
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
情况有限的回溯法。要注意的是，只有剩余右括号数大于剩余左括号数的时候，才可以插入右括号（此时才有匹配的左括号）。
代码
class Solution {
private:
void backtracking(vector<string>& ans, string path, int left, int right) {
if (!left && !right) {
ans.push_back(path);
return;
}
if (left) {
path += "(";
backtracking(ans, path, left - 1, right);
path.pop_back();
}
if (right && right > left) {
path += ")";
backtracking(ans, path, left, right - 1);
path.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
backtracking(ans, "", n, n);
return ans;
}
};2. 整数反转
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
溢出处理耽误了好一会，本来想用异常捕获直接做的，但是好像没生效。最后是在乘十之前检查下是否已经大于上界除以10的值，是的话直接返回0。
代码
class Solution {
public:
int reverse(int x) {
string sx = to_string(x);
string sy(sx.rbegin(), sx.rend());
if (sx[0] == '-') sy.pop_back();
int y = 0;
for (int i = 0; i < sy.size(); ++i) {
if (y > (1LL << 31) / 10) return 0;
y = y * 10 + (sy[i] - '0');
}
if (sx[0] == '-') y *= -1;
return y;
}
};3. 找出中枢整数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
分析题意，不难发现返回值总在有限区间内，且判断值是否符合限制也比较简单，仅需要常数空间和时间，因此想到二分法查找答案。当固定 x 的值，可以很容易求出左右两部分的和（等差数列），验证是否相等，若不等，则根据大小关系缩小区间即可。
代码
class Solution {
public:
int pivotInteger(int n) {
int low = 1, high = n;
while (low <= high) {
int mid = (low + high) / 2;
int res1 = (1 + mid) * mid / 2;
int res2 = (mid + n) * (n - mid + 1) / 2;
if (res1 == res2) return mid;
else if (res1 < res2) low = mid + 1;
else high = mid - 1;
}
return -1;
}
};4. 追加字符以获得子序列
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
看到之后没有细想，以为直接求最长公共子序列，然后用 t 的长度减掉子序列的长度即可。测试发现输出不对，才反应过来，应该求的是以 t 的首部开始的连续子串在 s 中出现的长度，然后再用 t的长度减去它。
因为看到熟悉的算法所以兴奋地忘了先去手动验证用例，急着先去代码实现，所以后面改代码又浪费了时间。
代码
class Solution {
public:
int appendCharacters(string s, string t) {
int i = 0, j = 0;
for (; i < s.size() && j < t.size();) {
if (s[i] == t[j]) {
++i;
++j;
} else {
++i;
}
}
return t.size() - j;
}
};5. 从链表中移除节点
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
之前遇到题目总是一根筋正着去想。昨天刚写了一些题，认识到逆向思维的重要性。具体到这道题，初看下，如果顺着链表正向走，那么要知道当前结点是否应当删除，是有些麻烦的。但是如果反着来，就变得异常容易，只要记录和更新遍历过程中的最大元素，在遍历过程中遇到小于最大元素的值，就将其记录为需要删除，最后再正向遍历删除这些结点即可。
先将结点值记录在一个数组中，方便反向遍历，然后将需要删除的值放到栈中，最后遍历链表去依次删除栈内元素对应的结点即可。时间、空间复杂度均为 O(n) 。
代码
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
ListNode* dummy = new ListNode;
dummy->next = head;
vector<int> nums;
ListNode* cur = head;
while (cur) {
nums.push_back(cur->val);
cur = cur->next;
}
if (nums.size() == 1) return head;
int rightMaxNum = nums[nums.size() - 1];
stack<int> toBeDel;
for (int i = nums.size() - 2; i >= 0; --i) {
if (rightMaxNum > nums[i]) toBeDel.push(nums[i]);
else rightMaxNum = max(rightMaxNum, nums[i]);
}
ListNode* pre = dummy;
cur = head;
while (cur) {
if (!toBeDel.empty() && cur->val == toBeDel.top()) {
toBeDel.pop();
pre->next = cur->next;
cur = cur->next;
} else {
pre = cur;
cur = cur->next;
}
}
return dummy->next;
}
};6. 统计中位数为 K 的子数组
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
应该说这题我的思路是正确的，但不知道怎么实现。
对于一个子数组，k 能否作为其中位数，取决于子数组中有多少元素大于它、小于它。如果前者跟后者数量一样（k 在正中间），或者前者比后者多一个（总共偶数个元素，k处于中间靠左），都可以满足条件。所以问题在于如何计算满足上述条件的情况总数。
参考这篇
代码
class Solution {
public:
int countSubarrays(vector<int>& nums, int k) {
int pos = -1;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == k) {
pos = i;
break;
}
}
map<int, int> mp;
mp[0] = 1;
for (int i = pos + 1, c = 0; i < nums.size(); ++i) {
c += nums[i] > k ? 1 : -1;
++mp[c];
}
int ans = mp[0] + mp[1];
for (int i = pos - 1, c = 0; i >= 0; --i) {
c += nums[i] < k ? 1 : -1;
ans += mp[c] + mp[c + 1];
}
return ans;
}
};
Comments NOTHING