Longest Substring with At Most Two Distinct Characters
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s =
“eceba”,T is "ece" which its length is 3.
------------------------------------------------------
have two counters for each char, once a third char comes in, exhaust either counter, then set it to the third char
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
char first = '\0', second = '\0';
int count1 = 0, count2 = 0;
int start = 0,longest = 0;
for (int i = 0; i < s.length(); i++) {
if (count1 == 0 && count2 == 0) {
first = s[i];
count1++;
}else if (count2 == 0 && first != s[i]) {
second = s[i];
count2++;
}else if (first == s[i]) {
count1++;
}else if (second == s[i]) {
count2++;
}else {
while (true) {
if (s[start] == first) count1--;
else count2--;
start++;
if (count1 == 0) {
first = s[i];
count1 = 1;
break;
}
if (count2 == 0) {
second = s[i];
count2 = 1;
break;
}
}
}
longest = max(longest,i - start + 1);
}
return longest;
}
};
网上看到的,i, j 记录2个不同char的最新位置
int lengthOfLongestSubstringTwoDistinct(string s) {
int i = 0, j = -1;
int maxLen = 0;
for (int k = 1; k < s.size(); k++) {
if (s[k] == s[k-1]) continue;
if (j > -1 && s[k] != s[j]) {
maxLen = max(maxLen, k - i);
i = j + 1;
}
j = k - 1;
}
return maxLen > (s.size() - i) ? maxLen : s.size() - i;
}
更新
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
unordered_map<char,int> dic;
int start = 0, longest = 0;
for (int i = 0; i < s.length(); i++) {
if (dic.find(s[i]) != dic.end()) {
dic[s[i]]++;
}else {
dic[s[i]] = 1;
}
while (dic.size() > 2) {
dic[s[start]]--;
if (dic[s[start]] == 0) {
dic.erase(s[start]);
}
start++;
}
longest = max(longest,i - start + 1);
}
return longest;
}
};
Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling
next() will return the next smallest number in the BST.Note:
next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.Credits:
Special thanks to @ts for adding this problem and creating all test cases. ----------------------------------------------------------------
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
TreeNode *p = root;
while (p != NULL) {
st.push(p);
p = p->left;
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
return st.size() > 0;
}
/** @return the next smallest number */
int next() {
if (st.empty()) throw exception();
TreeNode *rt = st.top();
TreeNode *p = rt->right;
st.pop();
while (p != NULL) {
st.push(p);
p = p->left;
}
return rt->val;
}
private:
stack<TreeNode *> st;
};
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
Another implementation
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
current = root;
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !st.empty() || current != NULL;
}
/** @return the next smallest number */
int next() {
while (current != NULL) {
st.push(current);
current = current->left;
}
current = st.top();
st.pop();
int rt = current->val;
current = current->right;
return rt;
}
private:
stack<TreeNode*> st;
TreeNode *current;
};
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
更新
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
this->root = root;
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !st.empty() || root != NULL;
}
/** @return the next smallest number */
int next() {
while (!st.empty() || root) {
if (root != NULL) {
st.push(root);
root = root->left;
}else {
TreeNode *rt = st.top();
st.pop();
root = rt->right;
return rt->val;
}
}
}
private:
stack<TreeNode *> st;
TreeNode *root;
};
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
Java, Jun-14-2018
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
private Stack st;
public BSTIterator(TreeNode root) {
st = new Stack<>();
pushToStack(root);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !st.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode cur = st.pop();
pushToStack(cur.right);
return cur.val;
}
private void pushToStack(TreeNode root) {
while (root != null) {
st.push(root);
root = root.left;
}
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
No comments:
Post a Comment