s*****n
发帖数: 994 | 1 Implement a function string balanceParanthesis(string s); which given a
string s consisting of some parenthesis returns a string s1 in which
parenthesis are balanced and differences between s and s1 are minimum.
Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
")))(((" -> ""
Is my idea correct:?
void eliminate (int left[], int right[],leftsize, rightsize)//in left right
there are position info. left[0] is the position of first left paranthesis
{
sort (left, left+leftsize);
sort (right, right+rightsize);
... 阅读全帖 |
|
s*****n
发帖数: 994 | 2 Implement a function string balanceParanthesis(string s); which given a
string s consisting of some parenthesis returns a string s1 in which
parenthesis are balanced and differences between s and s1 are minimum.
Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
")))(((" -> ""
Is my idea correct:?
void eliminate (int left[], int right[],leftsize, rightsize)//in left right
there are position info. left[0] is the position of first left paranthesis
{
sort (left, left+leftsize);
sort (right, right+rightsize);
... 阅读全帖 |
|
c********e
发帖数: 186 | 3 1. 以A中数字为key排序（B随之排序）
2. 建树，把A中数字从大到小插入到书中，每个node记录左右子树的大小leftsize，
rightsize：
现在插入数字a with b
1. 如果leftsize+1>=b，递归插入右子树且b=b-leftsize-1（已有leftsize+1数在a
之前）
2. 否则，插入左子树。
3. 若插入的子树为空，则插入到这个位置。
3. 中序打印 |
|
a***e
发帖数: 413 | 4 下面这两个1.2.写法都是O（N^2)吧？为啥2说是O（N）呢？另外，看到lc上一个
discussion的iterative的解法3.https://oj.leetcode.com/discuss/2297/the-
iterative-solution-is-easier-than-you-think
时间复杂度是O（N）吧？
我看了helper的function signature能写出1，对2中用到的好多STL要搜索才能写出来
，不熟。
Binary tree和recursion现在是我最弱处，多谢！
1.
class Solution {
public:
TreeNode *buildTree(vector &preorder, vector &inorder) {
if (preorder.size()==0) return NULL;
else if (preorder.size()==1)
{
TreeNode *t = new TreeNode(preorder[0])... 阅读全帖 |
|
s**x
发帖数: 7506 | 5 刚刚整理了一下这道题, 这是我搜集到的思路， 自己写的 code.
//Solution 1: using in order traversal.
// Time is O(n).
Node *getKth1(Node *root, int &k)
{
if (root == NULL)
return NULL;
Node *res =
getKth(root->left, k);
if (res != NULL)
return res;
if (k == 1)
return root;
k--;
return getKth(root->right, k);
}
// Solution 2: If each node has its
// left sub-tree size info, we can do
// time O(logn).
Node *getKth(Node *root, int k)
{
if (root == NULL)
... 阅读全帖 |
|
l*******0
发帖数: 95 | 6 其实这就是一个简单的二叉树插入问题
class TreeNode {
int val;
int offset;
int smaller;
TreeNode left, right;
int leftSize;
TreeNode(int offset, int val) {this.offset = offset; this.val = val; }
}
public class CountingTree {
private TreeNode root;
TreeNode[] buffer;
public CountingTree(int size) {
buffer = new TreeNode[size];
}
public void insert(int offset, int val) {
TreeNode node = new TreeNode(offset, val);
if(root == null)... 阅读全帖 |
|
p*****2
发帖数: 21240 | 7 18.6 第三个解两个疑问
1. if (leftSize==rank+1) 为什么不是leftSize==rank呢？
2. max(array, left, leftEnd), 难道这个不就是pivot? |
|
