NeonSean

NeonSean
17小时前
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int j = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != val) nums[j++] = nums[i];
}
return j;
}
};


#### 递归

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> res;
vector<int> inorderTraversal(TreeNode* root) {
if (root == NULL) return {};
if (root->left) {
inorderTraversal(root->left);
}
res.push_back(root->val);
if (root->right) {
inorderTraversal(root->right);
}
return res;
}
};


#### 迭代

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if (!root) return {};
stack<TreeNode*> stk;
vector<int> res;
TreeNode* p = root;
while (p || !stk.empty()) {
if (p) {
stk.push(p);
p = p->left;
}else {
p = stk.top();
stk.pop();
res.push_back(p->val);
p = p->right;
}
}
return res;
}
};


class Solution {
public:
vector<string> res;
dfs(s, 0, 0, "");
return res;
}
void dfs(const string& s, int u, int k, string path) {
if (u == s.size()) {
if (k == 4) {
path.pop_back();
res.push_back(path);
}
return;
}
if (k == 4) return;
for (int i = u, t = 0; i < s.size(); i ++) {
if (i > u && s[u] == '0') break;
t = t * 10 + s[i] - '0';
if (t <= 255) dfs(s, i + 1, k + 1, path + to_string(t) + '.') ;
else break;
}
}
};


/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* dummy = new ListNode(-1);

ListNode* a = dummy;
for (int i = 0; i < m - 1; i++) a = a->next;
ListNode* b = a->next;
ListNode* c = b->next;
for (int i = 0; i < n - m; i++) {
auto t = c->next;
c->next = b;
b = c;
c = t;
}
a->next->next = c;
a->next = b;
return dummy->next;
}
};


class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
else if (p && q && p->val == q->val) return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
else return false;
}
};


class Solution {
public:
int numDecodings(string s) {
int n = s.size();
s = ' ' + s;
vector<int> f(n + 1);
f[0] = 1;
for (int i = 1; i <= n; i++) {
if (s[i] >= '1' && s[i] <= '9') f[i] += f[i-1];
if (i > 1) {
int t = (s[i-1] - '0') * 10 + (s[i] - '0');
if (t >= 10 && t <= 26) f[i] += f[i-2];
}
}
return f[n];
}
};


class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int res = 0;
int n = nums.size();
vector<int> f(n);

for (int i = 0; i < n; i++) {
f[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
f[i] = max(f[i], f[j] + 1);
}
}
res = max(res, f[i]);
}
return res;
}
};


class Solution {
public:
int maxEnvelopes(vector<vector<int>>& env) {
sort(env.begin(), env.end());
int n = env.size();
int res = 0;
vector<int> f(n,1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (env[i][0] > env[j][0] && env[i][1] > env[j][1]) {
f[i] = max(f[i], f[j] + 1);
}
}
res = max(res, f[i]);
}
return res;
}
};


class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_multiset<int> s;
vector<int> res;
for (auto c : nums1) s.insert(c);
for (auto c : nums2) {
if (s.count(c)) {
res.push_back(c);
s.erase(s.find(c));
}
}
return res;
}
};


class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> s;
vector<int> res;
for (int c : nums1) s.insert(c);
for (int c : nums2) {
if (s.count(c)) {
res.push_back(c);
s.erase(c);
}
}
return res;
}
};