yxc

212.2万

yxc
15小时前

yxc
1天前

yxc
2天前
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& q) {
sort(q.begin(), q.end(), [](vector<int> a, vector<int> b) {
return a[1] < b[1];
});
if (q.empty()) return 0;
int res = 1, r = q[0][1];
for (int i = 1; i < q.size(); i ++ )
if (q[i][0] >= r) {
res ++;
r = q[i][1];
}
return q.size() - res;
}
};


yxc
2天前
class Solution {
public:
int countSegments(string s) {
int res = 0;
for (int i = 0; i < s.size(); i ++ ) {
if (s[i] == ' ') continue;
int j = i + 1;
while (j < s.size() && s[j] != ' ') j ++ ;
res ++ ;
i = j - 1;
}
return res;
}
};


yxc
2天前
class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
unordered_set<string> S;
for (auto& s: bank) S.insert(s);
unordered_map<string, int> dist;
queue<string> q;
q.push(start);
dist[start] = 0;
char chrs[4] = {'A', 'T', 'C', 'G'};

while (q.size()) {
auto t = q.front();
q.pop();
for (int i = 0; i < t.size(); i ++ ) {
auto s = t;
for (char c: chrs) {
s[i] = c;
if (S.count(s) && dist.count(s) == 0) {
dist[s] = dist[t] + 1;
if (s == end) return dist[s];
q.push(s);
}
}
}
}
return -1;
}
};


yxc
2天前
class AllOne {
public:
struct Node {
Node *left, *right;
int val;
unordered_set<string> S;

Node (int _val) {
val = _val;
left = right = NULL;
}
}*left, *right;
unordered_map<string, Node*> hash;

/** Initialize your data structure here. */
AllOne() {
left = new Node(INT_MIN), right = new Node(INT_MAX);
left->right = right, right->left = left;
}

Node* add_to_right(Node* node, string key, int val) {
if (node->right->val == val) node->right->S.insert(key);
else {
auto t = new Node(val);
t->S.insert(key);
t->right = node->right, node->right->left = t;
node->right = t, t->left = node;
}
return node->right;
}

Node* add_to_left(Node* node, string key, int val) {
if (node->left->val == val) node->left->S.insert(key);
else {
auto t = new Node(val);
t->S.insert(key);
t->left = node->left, node->left->right = t;
node->left = t, t->right = node;
}
return node->left;
}

void remove(Node* node) {
node->left->right = node->right;
node->right->left = node->left;
delete node;
}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(string key) {
if (hash.count(key) == 0) hash[key] = add_to_right(left, key, 1);
else {
auto t = hash[key];
t->S.erase(key);
hash[key] = add_to_right(t, key, t->val + 1);
if (t->S.empty()) remove(t);
}
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
if (hash.count(key) == 0) return;
auto t = hash[key];
t->S.erase(key);
if (t->val > 1) {
hash[key] = add_to_left(t, key, t->val - 1);
} else {
hash.erase(key);
}
if (t->S.empty()) remove(t);
}

/** Returns one of the keys with maximal value. */
string getMaxKey() {
if (right->left != left) return *right->left->S.begin();
return "";
}

/** Returns one of the keys with Minimal value. */
string getMinKey() {
if (left->right != right) return *left->right->S.begin();
return "";
}
};

/**
* Your AllOne object will be instantiated and called as such:
* AllOne* obj = new AllOne();
* obj->inc(key);
* obj->dec(key);
* string param_3 = obj->getMaxKey();
* string param_4 = obj->getMinKey();
*/


yxc
2天前
/*
// Definition for a Node.
class Node {
public:
int val;
Node* prev;
Node* next;
Node* child;
};
*/

class Solution {
public:
return res[0];
}

while (cur) {
tail = cur;
if (cur->child) {
auto t = dfs(cur->child);
cur->child = NULL;
t[1]->next = cur->next;
if (cur->next) cur->next->prev = t[1];
cur->next = t[0];
t[0]->prev = cur;
cur = t[1]->next;
tail = t[1];
} else {
cur = cur->next;
}
}
}
};


yxc
2天前
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
if (!root) return res;
queue<Node*> q;
q.push(root);
while (q.size()) {
int len = q.size();
vector<int> line;
while (len -- ) {
auto t = q.front();
q.pop();
line.push_back(t->val);
for (auto c: t->children) q.push(c);
}
res.push_back(line);
}
return res;
}
};


yxc
2天前
/*
// Definition for a QuadTree node.
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft;
Node* topRight;
Node* bottomLeft;
Node* bottomRight;

Node() {
val = false;
isLeaf = false;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}

Node(bool _val, bool _isLeaf) {
val = _val;
isLeaf = _isLeaf;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}

Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
val = _val;
isLeaf = _isLeaf;
topLeft = _topLeft;
topRight = _topRight;
bottomLeft = _bottomLeft;
bottomRight = _bottomRight;
}
};
*/

class Solution {
public:
vector<vector<int>> s;

Node* construct(vector<vector<int>>& w) {
int n = w.size();
s = vector<vector<int>>(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + w[i - 1][j - 1];
return dfs(1, 1, n, n);
}

Node* dfs(int x1, int y1, int x2, int y2) {
int n = x2 - x1 + 1;
int sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
if (sum == 0 || sum == n * n) return new Node(!!sum, true);
auto node = new Node(0, false);
int m = n / 2;
node->topLeft = dfs(x1, y1, x1 + m - 1, y1 + m - 1);
node->topRight = dfs(x1, y1 + m, x1 + m - 1, y2);
node->bottomLeft = dfs(x1 + m, y1, x2, y1 + m - 1);
node->bottomRight = dfs(x1 + m, y1 + m, x2, y2);
return node;
}
};


yxc
2天前
class Solution {
public:
int characterReplacement(string s, int k) {
int res = 0;
for (char c = 'A'; c <= 'Z'; c ++ ) {
for (int i = 0, j = 0, cnt = 0; i < s.size(); i ++ ) {
if (s[i] == c) cnt ++ ;
while (i - j + 1 - cnt > k) {
if (s[j] == c) cnt -- ;
j ++ ;
}
res = max(res, i - j + 1);
}
}
return res;
}
};