Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.
Machine 1 (sender) has the function:
string encode(vector<string> strs) {
// ... your code
return encoded_string;
}
Machine 2 (receiver) has the function:vector<string> decode(string s) {
//... your code
return strs;
}
So Machine 1 does:
string encoded_string = encode(strs);
and Machine 2 does:
vector<string> strs2 = decode(encoded_string);
strs2 in Machine 2 should be the same as strs in Machine 1.
Implement the
encode and decode methods.
Note:
- The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
- Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
- Do not rely on any library method such as
evalor serialize methods. You should implement your own encode/decode algorithm.
就是serialization 跟 de-serialization
class Codec {
public:
// Encodes a list of strings to a single string.
string encode(vector<string>& strs) {
string rt = "";
for (string s : strs) {
rt += to_string(s.length()) + "/" + s;
}
return rt;
}
// Decodes a single string to a list of strings.
vector<string> decode(string s) {
vector<string> rt;
int i = 0;
while (i < s.length()) {
int start = i;
string part = "",length = "";
while (isdigit(s[i])) {
length += s[i];
i++;
}
part = s.substr(i + 1,stoi(length));
rt.push_back(part);
i += stoi(length) + 1;
}
return rt;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.decode(codec.encode(strs));
Closest Binary Search Tree Value II
Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
- Given target value is a floating point.
- You may assume k is always valid, that is: k ≤ total nodes.
- You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?
Hint:
- Consider implement these two helper functions:
getPredecessor(N), which returns the next smaller node to N.getSuccessor(N), which returns the next larger node to N.
- Try to assume that each node has a parent pointer, it makes the problem much easier.
- Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
- You would need two stacks to track the path in finding predecessor and successor node separately.
COME_BACK
sliding window, 当pre与target差值小于suc的时，存入pre，再pre往前走
stack里存的值都是小于target或大于target，都有可能成为下一个pre或suc
其他方法：inorder遍历或者heap
/**
* 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:
stack<TreeNode*> parentSuc,parentPre;
TreeNode *getSuc(TreeNode *root,double target,bool flag) {
TreeNode *suc = NULL;
if (!parentSuc.empty()) {
suc = parentSuc.top();
parentSuc.pop();
}
while (root != NULL) {
if (flag && root->val == target) {
if (suc != NULL) parentSuc.push(suc);
return root;
}
if (root->val <= target) {
root = root->right;
}else {
if (suc != NULL) parentSuc.push(suc);
suc = root;
root = root->left;
}
}
return suc;
}
TreeNode *getPre(TreeNode *root,double target,bool flag) {
TreeNode *pre = NULL;
if (!parentPre.empty()) {
pre = parentPre.top();
parentPre.pop();
}
while (root != NULL) {
if (flag && root->val == target) {
if (pre != NULL) parentPre.push(pre);
return root;
}
if (root->val >= target) {
root = root->left;
}else {
if (pre != NULL) parentPre.push(pre);
pre = root;
root = root->right;
}
}
return pre;
}
vector<int> closestKValues(TreeNode* root, double target, int k) {
TreeNode *suc = getSuc(root,target,true);
TreeNode *pre = getPre(root,target,true);
vector<int> rt;
while (k > 0) {
if (suc == NULL) {
rt.push_back(pre->val);
pre = getPre(pre,pre->val,false);
}else if (pre == NULL) {
rt.push_back(suc->val);
suc = getSuc(suc,suc->val,false);
}else if (pre == suc) {
rt.push_back(pre->val);
pre = getPre(pre,pre->val,false);
suc = getSuc(suc,suc->val,false);
}else if (abs(suc->val - target) < abs(pre->val - target)) {
rt.push_back(suc->val);
suc = getSuc(suc,suc->val,false);
}else {
rt.push_back(pre->val);
pre = getPre(pre,pre->val,false);
}
k--;
}
return rt;
}
};
H-Index
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
For example, given
citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
Note: If there are several possible values for
h, the maximum one is taken as the h-index.
Hint:
- An easy approach is to sort the array first.
- What are the possible values of h-index?
- A faster approach is to use extra space.
用排序
class Solution {
public:
static bool cmp(int i,int j) {
return i > j;
}
int hIndex(vector<int>& citations) {
sort(citations.begin(),citations.end(),cmp);
int h = 0;
for (int i = 0; i < citations.size(); i++) {
if (citations[i] >= i + 1) {
h = i + 1;
}else break;
}
return h;
}
};
COME_BACK
hash map
注意h的范围只能是0 - n。从0开始，记录小于当前h index的总paper数量，如果剩余paper的数量大于等于当前的h index，则更新h index
class Solution {
public:
int hIndex(vector& citations) {
unordered_map cite;
for (int i = 0; i < citations.size(); i++) {
if (cite.find(citations[i]) == cite.end()) {
cite[citations[i]] = 1;
}else {
cite[citations[i]]++;
}
}
int count = 0, h = 0;
for (int i = 0; i <= citations.size(); i++) {
if (i <= (citations.size() - count)) h = i;
if (cite.find(i) != cite.end()) count += cite[i];
}
return h;
}
};
Paint Fence
There is a fence with n posts, each post can be painted with one of the k colors.
You have to paint all the posts such that no more than two adjacent fence posts have the same color.
Return the total number of ways you can paint the fence.
Note:
n and k are non-negative integers.
-------------------------------------------------------n and k are non-negative integers.
COME_BACK
在[i]点总paint的方法为在该点paint跟之前的同色 + 在该点paint跟之前的不同色
与之前的同色 = 在[i - 1]点的不同色的方法
与之前的不同色 = 在[i - 1]点的总paint方法 * (k - 1)
class Solution {
public:
int numWays(int n, int k) {
if (n == 0) return 0;
if (n == 1) return k;
int diff = k * (k - 1), same = k;
for (int i = 2; i < n; i++) {
int temp = (diff + same) * (k - 1);
same = diff;
diff = temp;
}
return diff + same;
}
};
No comments:
Post a Comment