The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return
[0,1,3,2]. Its gray code sequence is:00 - 0 01 - 1 11 - 3 10 - 2Note:
For a given n, a gray code sequence is not uniquely defined.
For example,
[0,2,3,1] is also a valid gray code sequence according to the above definition.For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
---------------------------------------------------------------------------------
Solution#1, see patterns below
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> ret;
ret.push_back(0);
for (int i = 0; i < n; i++) {
int size = ret.size();
int bit = 1 << i;
for (int j = size - 1; j >= 0; j--) {
ret.push_back(ret[j] + bit);
}
}
return ret;
}
};
Solution#2, from internetclass Solution {
public:
vector<int> grayCode(int n) {
vector<int> ret;
int count = 0x01 << n;
for(int i = 0 ; i < count; ++i) {
ret.push_back(i ^ (i>>1));
}
return ret;
}
};
Subsets IIGiven a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- The solution set must not contain duplicate subsets.
If S =
[1,2,2], a solution is:[ [2], [1], [1,2,2], [2,2], [1,2], [] ]----------------------------------------------------------
Solution #1. Similar to #78 Subsets
Add a hashset to skip duplicates
class Solution {
public:
void subsets(vector<int> S, vector<vector<int> > &ret, vector<int> cur) {
int length = S.size();
unordered_set<int> mapping;
for (int i = 0; i < length; i++) {
vector<int> temp = cur;
int head = S[0];
S.erase(S.begin());
if (mapping.find(head) == mapping.end()) {
mapping.insert(head);
temp.push_back(head);
ret.push_back(temp);
subsets(S,ret,temp);
}
}
}
vector<vector<int> > subsetsWithDup(vector<int> &S) {
sort(S.begin(),S.end());
vector<vector<int> > ret;
vector<int> cur;
ret.push_back(cur);
subsets(S,ret,cur);
return ret;
}
};
Update Nov-19-2014 Solution#2 iterative
如果 不重复，从头插。
如果是重复数字，只需插入到前一次所插入的数列中
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
vector<int> empty;
vector<vector<int> > rt;
rt.push_back(empty);
sort(S.begin(),S.end());
int size = 0;
for (int i = 0; i < S.size(); i++) {
int start = 0;
if (i > 0 && S[i] == S[i - 1]) {
start = size;
}
size = rt.size();
for (; start < size; start++) {
vector<int> temp = rt[start];
temp.push_back(S[i]);
rt.push_back(temp);
}
}
return rt;
}
};
Java, 递归，去重
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> rt = new ArrayList<>();
dfs(rt, nums, 0, new ArrayList<>());
return rt;
}
private void dfs(List<List<Integer>> rt, int[] nums, int index, List<Integer> sofar) {
rt.add(sofar);
for (int i = index; i < nums.length; i++) {
if (i > index && nums[i] == nums[i - 1]) continue;
List<Integer> tmp = new ArrayList<>(sofar);
tmp.add(nums[i]);
dfs(rt, nums, i + 1, tmp);
}
}
}
迭代
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> rt = new ArrayList<>();
rt.add(new ArrayList<Integer>());
Arrays.sort(nums);
int lastSize = 0;
for (int i = 0; i < nums.length; i++) {
List<List<Integer>> rt_tmp = new ArrayList<>();
int size = rt.size();
if (i > 0 && nums[i] == nums[i - 1]) {
size = lastSize;
}
for (int j = size; j > 0; j--) {
int index = rt.size() - j;
List<Integer> inner = new ArrayList<>(rt.get(index));
inner.add(nums[i]);
rt_tmp.add(inner);
}
lastSize = rt_tmp.size();
rt.addAll(rt_tmp);
}
return rt;
}
}
Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree
{1,#,2,3}, 1
\
2
/
3
return [1,3,2].Note: Recursive solution is trivial, could you do it iteratively?
-----------------------------------------------
Iterative approach
Solution #1, add a boolean value to indicate visited status
Other solutions:
http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.html
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> ret;
stack<pair<TreeNode*,bool> > s;
s.push(make_pair(root,false));
while (!s.empty()) {
pair<TreeNode*,bool> p = s.top();
if (p.first != NULL) {
if (p.second == false) {
s.top().second = true;
s.push(make_pair(p.first->left,false));
}else {
ret.push_back(p.first->val);
s.pop();
s.push(make_pair(p.first->right,false));
}
}else {
s.pop();
}
}
return ret;
}
};
Update Nov-19-2014 basic idea: when a node is traversed for the second time, its value will be printed
当每一个node的左节点为NULL时，则需要打印这个node
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
stack<TreeNode *> st;
vector<int> rt;
while (!st.empty() || root != NULL) {
if (root) {
st.push(root);
root = root->left;
}else {
rt.push_back(st.top()->val);
root = st.top()->right;
st.pop();
}
}
return rt;
}
};
＊表示怀疑＊方法三，用2个stack，一个用来存第一次visit的node，一个是第二次visit的node方法四，Threaded binary tree. O(n) time, O(1) space 每往左走一个node，把之前node贴在它左子树的最右下角, 这是根据inorder traversal的特性决定的。算法见leetcode
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List inorderTraversal(TreeNode root) {
List rt = new ArrayList<>();
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
root = cur;
cur = cur.left;
TreeNode rightMost = cur;
while (rightMost.right != null) {
rightMost = rightMost.right;
}
rightMost.right = root;
root.left = null;
}else {
rt.add(cur.val);
cur = cur.right;
}
}
return rt;
}
}
No comments:
Post a Comment