iltonmi

NEU-China

5509

iltonmi
8小时前

### 经典双堆（题解看注释）

#### C++ 代码

class MedianFinder {
private:
priority_queue<int, vector<int>, greater<int>> bigger;
priority_queue<int> smaller;
public:
/** initialize your data structure here. */
MedianFinder() {

}

smaller.push(num);
if(smaller.size() - bigger.size() == 1 && !bigger.empty()) {
if(smaller.top() > bigger.top()) {
int a = smaller.top(); smaller.pop();
int b = bigger.top(); bigger.pop();
smaller.push(b); bigger.push(a);
}
} else if(smaller.size() - bigger.size() == 2) {
bigger.push(smaller.top()); smaller.pop();
}
}

double findMedian() {
if(smaller.size() - bigger.size() == 1) return smaller.top();
else return (smaller.top() + bigger.top()) / 2.0;
}
};

// if we use a array
// the insert may be slow, the worst o(N)
// the find is o(logN)

// we know that when insert a value in an sorted sequence
// the left part and the right part will change at most 1 value
// the value may be changed because the inserted value
// or the left part may be changed because swim up to the right part

// so lets seperate 2 parts and give a way to find the changed value
// when smaller part's value need to swim up to the bigger part
// we should find the biggest value of the smaller part
// so we need a big top heap
// and in order to know whether the value is bigger than
// the smallest value of the bigger part
// we need a small top heap for bigger part

// so here the strategy is 2 heaps
// whenever the insertion occurs, we insert the value to the smaller part first.
// if the smaller part's size bigger than bigger part over 1,
// we need to compare the top of 2 part, and swap if necessary
// the median will be the  top of smaller part
// if the smaller part's size bigger than bigger part over 2,
// move the top of smaller part to bigger part
// the median will be the median of 2 top

/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* double param_2 = obj->findMedian();
*/


iltonmi
9小时前
struct Node {
bool is_end;
Node *next[26];
char val;
Node() {
memset(next, 0, sizeof(next));
this->is_end = false;
}
Node(char val) : val(val) {
memset(next, 0, sizeof(next));
this->is_end = false;
}
};

class Trie {
private:
Node* root;
public:
/** Initialize your data structure here. */
Trie() {
this->root = new Node();
}

~Trie() {
queue<Node*> q;
q.push(this->root);
while(q.size()) {
auto p = q.front(); q.pop();
for(int i = 0; i < 26; i++)
if(p->next[i]) q.push(p->next[i]);
delete p;
}
}

/** Inserts a word into the trie. */
void insert(string word) {
Node *node = this->root;
for(auto& ch : word) {
if(!node->next[ch - 'a']) {
node->next[ch - 'a'] = new Node(ch);
}
node = node->next[ch - 'a'];
}
node->is_end = true;
}

/** Returns if the word is in the trie. */
bool search(string word) {
Node *node = this->root;
for(auto& ch : word) {
if(!node->next[ch - 'a']) return false;
node = node->next[ch - 'a'];
}
return node->is_end;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Node *node = this->root;
for(auto& ch : prefix) {
if(!node->next[ch - 'a']) return false;
node = node->next[ch - 'a'];
}
return true;
}
};

/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/



iltonmi
23小时前

### 层次遍历

#### C++ 代码 O(N)

/**
* 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:
// level traversal, if level k has x non-null nodes
// level k+1 must have 2 * x nodes, no matter non-null nodes' children are null or not
// if an encoded node is null, it's child wont be endoded
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string ans = "[";
queue<TreeNode*> q;
auto dummy = new TreeNode(1001);
if(root) q.push(root);
while(q.size()) {
int size = q.size();
bool has_child = false;
for(int i = 0; i < size; i++) {
auto p = q.front(); q.pop();
if(p->val == 1001)  ans += "null,";
else {
ans += to_string(p->val);
ans += ',';
if(p->left) q.push(p->left), has_child = true;
else q.push(dummy);
if(p->right) q.push(p->right), has_child = true;
else q.push(dummy);
}
}
if(!has_child) break;
}
if(ans.back() == ',') ans.pop_back();
ans += ']';
delete dummy;
return ans;
}

int read_int(string& data, int& idx) {
int val = 0;
bool neg = false;
if(data[idx] == '-') neg = true, idx++;
for(char ch = data[idx]; isdigit(ch); ch = data[++idx])
val = val * 10 + (ch - '0');
if(neg) val *= -1;
return val;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data.size() == 2) return NULL;
int idx = 1;
TreeNode* ans = new TreeNode(read_int(data, idx));
queue<TreeNode*> q;
q.push(ans);
while(q.size()) {
int n = q.size();
for(int i = 0; i < n; i++) {
auto p = q.front(); q.pop();
if(data[idx] == ',') idx++;
if(data[idx] == 'n') idx += 4;
else if(isdigit(data[idx]) || data[idx] == '-')
p->left = new TreeNode(read_int(data, idx)), q.push(p->left);

if(data[idx] == ',') idx++;
if(data[idx] == 'n') idx += 4;
else if(isdigit(data[idx]) || data[idx] == '-')
p->right = new TreeNode(read_int(data, idx)), q.push(p->right);
}
}
return ans;
}
};


iltonmi
1天前
/**
* 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:
int ans;
int treeDepth(TreeNode* root) {
this->ans = 0;
dfs(root, 0);
return ans;
}

void dfs(TreeNode* root, int depth) {
if(!root) return;
depth++;
ans = max(ans, depth);
dfs(root->left, depth);
dfs(root->right, depth);
}
};


iltonmi
1天前

#### 1. Morris遍历

class Solution {
public:
int minDiffInBST(TreeNode* root) {
int ans = INT_MAX;
TreeNode* prev = nullptr;
while(root) {
if(root->left) {
auto t = root->left;
while(t->right && t->right != root) t = t->right;
if(t->right == nullptr) t->right = root, root = root->left;
else {
ans = min(ans, root->val - t->val);
t->right = nullptr, prev = root, root = root->right;
}
} else {
if(prev) ans = min(ans, root->val - prev->val);
prev = root, root = root->right;
}
}
return ans;
}
};


#### 2. 非递归中序遍历

class Solution {
public:
int minDiffInBST(TreeNode* root) {
int ans = INT_MAX;
stack<TreeNode*> stk;
TreeNode* prev = nullptr;
while(root || stk.size()) {
if(root) {
stk.push(root);
root = root->left;
} else {
root = stk.top(); stk.pop();
if(prev) ans = min(ans, root->val - prev->val);
prev = root;
root = root->right;
}
}
return ans;
}
};


#### 3. 递归中序遍历

class Solution {
public:
int ans;
int minDiffInBST(TreeNode* root) {
this->ans = INT_MAX;
int pre = -1;
dfs(root, pre);
return ans;
}

void dfs(TreeNode* root, int& pre) {
if(!root) return;
dfs(root->left, pre);
if(pre != -1) ans = min(ans, root->val - pre);
pre = root->val;
dfs(root->right, pre);
}
};


iltonmi
1天前
class Solution {
public:
int minDiffInBST(TreeNode* root) {
int ans = INT_MAX;
TreeNode* prev = nullptr;
while(root) {
if(root->left) {
auto t = root->left;
while(t->right && t->right != root) t = t->right;
if(t->right == nullptr) t->right = root, root = root->left;
else {
ans = min(ans, root->val - t->val);
t->right = nullptr, prev = root, root = root->right;
}
} else {
if(prev) ans = min(ans, root->val - prev->val);
prev = root, root = root->right;
}
}
return ans;
}
};


iltonmi
1天前
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* res = NULL;
{
ListNode* tmp = head -> next;
}
return res;
}
};


iltonmi
2天前

### DP O(N)

#### C++ 代码

class Solution {
public:
int minSideJumps(vector<int>& obs) {
int n = obs.size();
int a[2][3] = {{1, 0, 1}, {-1, -1, -1}};
// 遍历全部列
for(int i = 1; i < n - 1; i++) {
int mj = n;
// 遍历全部行
for(int j = 0; j < 3; j++) {
// 有石头
if(j == obs[i] - 1) a[i % 2][j] = n + 1;
// 前面有石头，先标记一下
else if(obs[i - 1] - 1 == j) a[i % 2][j] = -1;
// 前面没石头，不用跳，记录最小值
else a[i % 2][j] = a[(i-1)%2][j], mj = min(mj, a[i % 2][j]);
// 如果这列，有2行可以通过直走到达，直走到A行再侧跳到B行，会不会相比直走到B行更优呢？
// 不可能，因为同一列最多相差1，A的前一列比B的前一列侧跳数量小1。
// 那么，直走到A后侧跳+1，和直走到B是一样的
}
// 侧跳到无法直达的地方
for(int j = 0; j < 3; j++)
if(a[i % 2][j] == -1) a[i % 2][j] = mj + 1;
}
int idx = (n-2)%2;
return min(a[idx][0], min(a[idx][1], a[idx][2]));
}
};



### BFS最短路 O(N)

#### C++ 代码

class Solution {
public:
// c = n + 1
// id = i * c + j
// id -> id + 1, for i in (0, 1, 2): i * c + id % c, if no stone...
// 细节多，容易错
int n;
static const int maxn = (int)1.5e6 + 10;
int dist[maxn];
bool vis[maxn];
int id(int i, int j) {
return i * n + j;
}

int minSideJumps(vector<int>& obs) {
this->n = obs.size();
memset(dist, 0x3f, sizeof(dist));
memset(vis, false, sizeof(vis));
deque<int> q;
q.push_back(id(1, 0));
dist[id(1, 0)] = 0;
while(q.size()) {
auto t = q.front(); q.pop_front();
if(vis[t]) continue;
vis[t] = true;
int x = t / n, y = t % n;
if(y == n - 1) continue;
if(obs[y + 1] - 1 != x) {
int tid = t + 1;
if(dist[t] < dist[tid])
dist[tid] = dist[t], q.push_front(tid);
}
for(int i = 0; i < 3; i++) {
if(i == x || obs[y] - 1 == i) continue;
int tid = id(i, y);
if(dist[t] + 1 < dist[tid])
dist[tid] = dist[t] + 1, q.push_back(tid);
}
}
int res = n + 1;
for(int i = 0; i < 3; i++) res = min(res, dist[i * n + n - 1]);
return res;
}
};



iltonmi
2天前
class Solution {
public:
int minSideJumps(vector<int>& obs) {
int n = obs.size();
int a[2][3] = {{1, 0, 1}, {-1, -1, -1}};
for(int i = 1; i < n - 1; i++) {
int mj = n;
for(int j = 0; j < 3; j++) {
if(j == obs[i] - 1) a[i % 2][j] = 0x3f3f3f3f;
else if(obs[i - 1] - 1 == j || a[(i-1)%2][j] == -1) a[i % 2][j] = -1;
else a[i % 2][j] = a[(i-1)%2][j], mj = min(mj, a[i % 2][j]);
}
for(int j = 0; j < 3; j++)
if(a[i % 2][j] == -1) a[i % 2][j] = mj + 1;
}
int idx = (n-2)%2;
return min(a[idx][0], min(a[idx][1], a[idx][2]));
}
};


iltonmi
2个月前