f**********t
发帖数: 1001 | 1 // Given a binary tree where all the right nodes are either leaf nodes with
a sibling (a left node that shares the same parent node) or empty, flip it
upside down and turn it into a tree where the original right nodes turned
into left leaf nodes. Return the new root.
// {1,2,3,4,5}, to [4,5,2,#,#,3,1]
class BiTree {
struct Node {
char val;
Node *left, *right;
Node(char c) : val(c), left(nullptr), right(nullptr) {}
};
Node *_root;
public:
BiTree(string s) {
queue qu... 阅读全帖 |
|
s***e
发帖数: 403 | 2 没有什么太大的难度啊
设置两个变量，back_left, back_right，然后先向左移动。在向parent移动的时候识
别是从左边子树移动来的还是从右边子树移动来的。如果是从右边子树移动来的说明所
有右边子树已经访问过，所以就向上移动，否则访问右边子树。最后从右边移动到root
的时候表明访问完毕。需要考察的也就是根节点的右子树是否访问完全。
下面是代码，可能有bug，不过思路大致如此。
struct TreeNode
{
TreeNode* parent;
TreeNode* left;
TreeNode* right;
int value;
explicit TreeNode(int val, TreeNode* p=nullptr) :
parent(p), left(nullptr), right(nullptr), value(val)
{}
};
void traverse(TreeNode* node)
{
TreeNode* iter=node;
bool backleft=false... 阅读全帖 |
|
a******e
发帖数: 710 | 3 开始只是想到了O(n)的算法。 O(m)的算法可以这么实现
#include
#include
using namespace std;
struct DListNode {
char val;
DListNode *prev;
DListNode * next;
DListNode(char v): val(v), prev(nullptr), next(nullptr) {}
};
void printList(DListNode* head){
while (head!=nullptr) {
cout<val<<", ";
head = head->next;
}
cout<
}
void printSet(unordered_set &s) {
for (auto iter=s.begin(); iter!=s.end(); ++iter)
cout<<(*ite... 阅读全帖 |
|
b*******e
发帖数: 123 | 4 今天刚做的。
vector preorderTraversal(TreeNode *root) {
if(root == nullptr) return {};
vector res;
stack stack;
stack.push(root);
while(!stack.empty()){
auto top = stack.top(); stack.pop();
res.push_back(top->val);
if(top->right!=nullptr) stack.push(top->right);
if(top->left !=nullptr) stack.push(top->left);
}
return res;
}
vector postorderTraversal(TreeNode *root) {
if(root==nullptr) return {};
stack stack;
stack.push(root);
v... 阅读全帖 |
|
a****r
发帖数: 87 | 5 An iterative version:
TreeNode *transform(TreeNode *root){
if(root == nullptr) return nullptr;
TreeNode *parent = nullptr;
TreeNode *cur = root;
TreeNode *b1 = nullptr;
TreeNode *b2 = nullptr;
while(cur){
// save the left and right child info before wiping them out.
TreeNode *a = cur->left;
b2 = cur->right;
cur->left = b1;
cur->right = parent;
// move to the next step
b1 = b2;
parent = cur;
... 阅读全帖 |
|
A*******e
发帖数: 2419 | 6 4）家族树，每个点左右指针指向自己的父亲和母亲，每个点存对应二叉堆的索引。
A）给一个这种树，给每个点标出对应二叉堆的索引值。
B）任意给一个节点（不需要输入根节点），输出这个点所在的层数。
C）任意给一个节点（不需要输入根节点），输出这个点和根节点的关系（e.g. 是
根节点父亲的母亲就输出“MF”）。
// 编码从0开始。
void SetParent(Node* root) {
if (root == nullptr) return;
root->id = 0;
SetParentHelper(root);
}
void SetParentHelper(Node* root) {
if (root->father != nullptr) {
root->father = root->id * 2 + 1;
SetParentHelper(root->father);
}
if (root->mother != nullptr) {
root->mother = root->id * 2 + 2;
SetPa... 阅读全帖 |
|
d**d
发帖数: 389 | 7 vector grandparents(TreeNode* root)
{
set s;
dfs(nullptr, nullptr, root, s);
std::vector res(s.begin(), s.end());
return res;
}
void dfs( TreeNode* g, TreeNode* p, TreeNode* root, set&res)
{
if (root == nullptr) return;
if (root->left == nullptr && root->right == nullptr)
{
if (g) res.insert(g->val);
return;
}
if (root->left)
dfs(p, root, root->left, res);
if (root->right)
dfs(p, root, root->right, res... 阅读全帖 |
|
s***e
发帖数: 403 | 8 /**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
map corresponding;
corresponding[nullptr] = nullptr;
RandomListNode* nhead = new RandomListNode(0);
RandomListNode* last = ... 阅读全帖 |
|
a****r
发帖数: 87 | 9 我的算法：
对两个BST同时进行in-order traversal in an iterative way.
bool is_BST_eq(TreeNode *r1, TreeNode *r2){
if(r1 == nullptr && r2 == nullptr) return true;
stack st1;
stack st2;
TreeNode *p = r1;
TreeNode *n1 = nullptr;
TreeNode *q = r2;
TreeNode *n2 = nullptr;
while(true){
// iterative inorder traversal for r1
while(!st1.empty() || p){
if(p){
st1.push(p);
p = p->left;
... 阅读全帖 |
|
x***7
发帖数: 11 | 10
T_T打了很多字回复的时候忘记密码了。。。。然后没了。。。
线段树嘛大概这样，我们建立一个[1..n]这个区间的线段树，每个叶子节点标记为1，
其他节点的值为这个节点下面有多少个为1的叶子节点。
【查找k大】
看左子树有多少个为1的节点，如果大于等于k，那么就在左子树找。如果不到k，那么
就在右子树找k-左子树为1的叶子节点个数。
当你找到相应的叶子节点，那么他表示的区间[l,r](l == r)，l或者r就是我们要找的[
1..n]里面的第k个数啦。
【删除】
就是把那个叶子节点标记为0，其他包含这个节点的区间当然就是num--
代码上面有人也回复了的，大概差不多。
-----
我自己写了个，测了几个简单的数据，不保证是对的。
struct TreeNode {
TreeNode *left, *right;
int val;
int l, r;
TreeNode (int _l, int _r) : l(_l), r(_r), left(nullptr), right(nullptr) {
}
TreeNode (int _val,... 阅读全帖 |
|
f********y
发帖数: 156 | 11 貌似 tail->up -> down。其实up / down 可以交换，你在flatten的时候先处理谁，那
么在unflatten也要先处理它。
Deflatten的唯一是因为 up / down 指针在flatten以后还保留着。flatten 只是把上
下层的表头连到了当前层的尾巴。
Deflatten的时候，觉得应该BFS。 貌似分层的问题，染色的问题，都是BFS。（ 楼主
原帖里的link 中有个递归做deflatten的函数，感觉不大对）
void deflatten(Node* pHead) {
if(! pHead ) {
return;
}
queue q;
q.push(pHead);
while(!q.empty()) {
Node* p = q.front();
q.pop();
while... 阅读全帖 |
|
y***d
发帖数: 2330 | 12 真要搞死人了，这什么改进，
char* pc = nullptr; // OK
int * pi = nullptr; // OK
bool b = nullptr; // OK. b is false.
int i = nullptr; // error
生怕人不搞昏啊 |
|
f**********t
发帖数: 1001 | 13 // Given a doubly linked list with a data item, a previous and a next ptr
along with another pointer "child" that may point to the head of another
doubly linked list of same type(it will lead to a general tree type of
structure) or it may be null. Flatten the tree into a linked list... minimum
space and time complexity(order n). The doubly linked lists's head and tail
are given.
struct List;
struct ListNode {
char val;
ListNode *pre, *next;
List *child;
};
struct List {
ListNode *head, *... 阅读全帖 |
|
a***e
发帖数: 413 | 14 多谢各位，但现在试着在纸上跑程序，但有些就是搞不清哪里错了，比如这个
Copy List with Random Pointer
A linked list is given such that each node contains an additional random
pointer which could point to
any node in the list or null.
Return a deep copy of the list.
我看了idea，自己写了如下程序，但就是
Submission Result: Runtime Error
Last executed input:
{-1,#}
看了半天，试着一步一步走进去，还是不知道哪里错了，打算在VS里面debug一下看。
觉得和能通过的答案没有多少区别啊。。。。。。。。
My wrong answer.
/**
* Definition for sin... 阅读全帖 |
|
a***e
发帖数: 413 | 15 多谢各位，但现在试着在纸上跑程序，但有些就是搞不清哪里错了，比如这个
Copy List with Random Pointer
A linked list is given such that each node contains an additional random
pointer which could point to
any node in the list or null.
Return a deep copy of the list.
我看了idea，自己写了如下程序，但就是
Submission Result: Runtime Error
Last executed input:
{-1,#}
看了半天，试着一步一步走进去，还是不知道哪里错了，打算在VS里面debug一下看。
觉得和能通过的答案没有多少区别啊。。。。。。。。
My wrong answer.
/**
* Definition for sin... 阅读全帖 |
|
j********x
发帖数: 2330 | 16 用0没什么问题
Bs的原话
Should I use NULL or 0?
In C++, the definition of NULL is 0, so there is only an aesthetic
difference. I prefer to avoid macros, so I use 0. Another problem with NULL
is that people sometimes mistakenly believe that it is different from 0 and/
or not an integer. In pre-standard code, NULL was/is sometimes defined to
something unsuitable and therefore had/has to be avoided. That's less common
these days.
If you have to name the null pointer, call it nullptr; that's what it's
going t... 阅读全帖 |
|
w*******e
发帖数: 285 | 17 用bfs level print同时记住每个node的parent,看到leaf node就向上一直找到root
//none re-cursive level order, BFS
void levelorder(treenode* root){
if (root == nullptr) return;
map parent;
parent[root] = nullptr;
queue q;
q.push(root);
while (!q.empty()) {
auto cur = q.front(); q.pop();
if (cur->left) {
parent[cur->left] = cur;
q.push(cur->left);
}
if (cur->right) {
parent[cur->right] = cur;
q.push(cur->right);
}... 阅读全帖 |
|
a***e
发帖数: 413 | 18 下面这两个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])... 阅读全帖 |
|
a****r
发帖数: 87 | 19 C++ R-way trie implementation. Coursera princeton algorithm II 讲的很详细。
const int N = 26;
struct TrieNode{
int val;
vector link;
TrieNode(int x=-1): val(x), link(N){}
};
class Trie{
public:
Trie(){
root = new TrieNode;
}
void put(string &key, int val){
put(root, key, val, 0);
}
int get(string &key){
TrieNode *t = get(root, key, 0);
if(t) return t->val;
else return -1;
}
void remove(string &key){... 阅读全帖 |
|
a****r
发帖数: 87 | 20 C++ R-way trie implementation. Coursera princeton algorithm II 讲的很详细。
const int N = 26;
struct TrieNode{
int val;
vector link;
TrieNode(int x=-1): val(x), link(N){}
};
class Trie{
public:
Trie(){
root = new TrieNode;
}
void put(string &key, int val){
put(root, key, val, 0);
}
int get(string &key){
TrieNode *t = get(root, key, 0);
if(t) return t->val;
else return -1;
}
void remove(string &key){... 阅读全帖 |
|
b******i
发帖数: 914 | 21 贴个code，不过只test了几种case
/*
给一个list of string 和一个string s， 返回s是不是在list当中， s里可以包含一
个*代表一个任意字符。
*/
#include
#include
#include
using namespace std;
struct TrieNode {
TrieNode():is_word(false),children(26,nullptr) {}
bool is_word;
vector children;
};
class Solution {
public:
bool string_in_list(vector strings, string s) {
if(s.length() == 0 || strings.size() == 0)
return false;
// construct trie
... 阅读全帖 |
|
N******K
发帖数: 10202 | 22 当有成员变量 m_ClassA_member 的时候
p1 = new object1;
p2 = new object2;
p3 = new object3;
p4 = new object4;
ClasseA::function A(input (i.e., const): p1, p2 , output p3 p4)
{
temp1= shared_ptr(new ObjectTemp1);
temp2= shared_ptr(new ObjectTemp2);
m_ClassA_member = new(xxx);
do somthing using p1 p2 temp 1 temp2 to update p3 p4
} //delete temp1, delete temp2
ClassA()
{
m_ClassA_member = nullptr;
}
~ClassA()
{
if (m_ClassA_member != nullptr)
delete m_ClassA_member ;
} |
|
r*********n
发帖数: 4553 | 23 传说中的pruning? 在recursion的时候设置一个全局flag，如果达到条件，就直接返回
比如在binary tree里面寻找一个key，
class BT{
bool found;
void contain(Node* nd, int key){
if(found) return;
if(nd == nullptr) return;
if(nd->val == key){
found = true;
return;
}
contain(nd->left, key);
contain(nd->right, key);
}
public:
BT():found(false){}
bool contain(Node* root, int key){
contain(root, key);
return found;
}
};
如果没有found，那么每个node都要check一遍。如果key刚好在最左下角的node里面，
那么上面这个方法只需要check那个node的height那么多... 阅读全帖 |
|
h*z
发帖数: 33 | 24 C++ looks shorter.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *sortList(ListNode *head) {
if (!head || !head->next) return head;
ListNode *slow = head;
ListNode *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
Lis... 阅读全帖 |
|
t****t
发帖数: 6806 | 25
abi=application binary interface, 最主要的是决定函数怎么调用, 还有name
mangling, exception的处理
api还用说么.
stack unwind until caught, or until another exception (terminate())
unexpected()
EDIT:搞混了, 是terminate(). unexpected发生在扔出说明里没有的异常时.
const, reference, parent class w/o default ctor
reference can not be reseated, can not have nullptr value
suspect
这个太泛泛了, 必须得有点背景才行吧. 比如说看/proc/pid里的东西, 但是看什么就
很难说了. |
|
a***e
发帖数: 413 | 26 这些题看着容易，老是写不对或者代码很冗长，有大牛们指点一下如何提高么？
呜呜，不知道哪年哪月才能刷完一遍，有同学互勉一下么？
比如
Given a linked list and a value x, partition it such that all nodes less
than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the
two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
我的
Runtime Error
Last executed input:
{1}, 0
ListNode *partition(ListNode *head, int x) {
... 阅读全帖 |
|
a***e
发帖数: 413 | 27 Ft, 用VS不到半分钟就发现问题。。。。。。。。。。。。
// while(cur){
while(cur&&oc){ //加这个check就行了
oc->next = oc->next->next;
oc = oc->next;
if (cur->next){
cur->next = cur->next->next;
cur = cur->next;
}
}
但这段程序就不用那么多check
//
RandomListNode dummy(-1);
for (RandomListNode* cur = head, *new_cur = &dummy;
cur != nullptr; ) {
new_cur->next = cur->next;
new... 阅读全帖 |
|
a***e
发帖数: 413 | 28 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt
不知道啊，但好像是可以得。我是觉得这种写法很简单， 比起同样的naive matching
char *strStr(const char *haystack, const char *needle) {
// if needle is empty return the full string
if (!*needle) return (char*) haystack;
const char *p1;
const char *p2;
const char *p1_advance = haystack;
for (p2 = &needle[1]; *p2; ++p2) {
p1_advance++; // advance p1_advance M-1 times
}
for (p1 = haystack; *p1_advance; p1_advance++) {
char *p1_old = (char*) p1;
p2 = needle;
while (*p1... 阅读全帖 |
|
a***e
发帖数: 413 | 29 找到一个解释比wiki清楚的source
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.h
下面是根据那个原理写的KMP，这下觉得清楚多了。和正在学习的同学共享一下。。。
。。。顺便多谢各位。。。。
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int pos = kmpSearch(haystack, needle);
if (pos == -1) return nullptr;
else return haystack + pos;
}
static void kmpPreprocess(const char *p, vector &b)
{
int i = 0, j = -1;
b[i] = j;
const int m = strlen(p);
... 阅读全帖 |
|
i****n
发帖数: 42 | 30 In my understanding, this piece of code actually does nothing except that,
the default constructor of foo will be called, a will be initialize as 0,
and b will be initialized as nullptr, and a default destructor will
eventually be called before doSth() goes out of scope. Moreover, since doSth
() is called, a function pointer will be pushed into a stack, and pop up
after doSth() goes out of scope. That is it. However, the interviewer was
not satisfied with my answer, so I am here to ask if anythi... 阅读全帖 |
|
m*****n
发帖数: 2152 | 31 a and b are not initialized, but "a" has been allocated some memory and the
value in a's memory can be anything, not necessary to be zero. b also point
to some memory (not necessary to be nullptr) which can be anything.
doSth
besides |
|
|
h******o
发帖数: 6 | 33 bool helper(TreeNode *node, int min, int max) {
if (node == nullptr) return true;
return node->val < max && node->val > min && helper(node->left, min
, node->val) && helper(node->right, node->val, max);
}
bool isValidBST(TreeNode *root) {
if (root && (root->val == INT_MIN || root->val == INT_MAX)) {
if (!root->left && !root->right) {
return true;
}
}
return helper(root, INT_MIN, INT_MAX);
}
fail {-21... 阅读全帖 |
|
k*******a
发帖数: 433 | 34 个数写成0不会抛出异常吧，-1应该就会。
delete的时候，如果一个指针是nullptr,delete这个指针没问题啊，但是如果直接写
delete null应该编译不过吧。
请指教，谢谢！ |
|
l*s
发帖数: 783 | 35 MSDN上的code不work?
private:
void button1_Click( Object^ /*sender*/, System::EventArgs^ /*e*/ )
{
Stream^ myStream;
SaveFileDialog^ saveFileDialog1 = gcnew SaveFileDialog;
saveFileDialog1->Filter = "txt files (*.txt)|*.txt|All files (*.*)|*.*
";
saveFileDialog1->FilterIndex = 2;
saveFileDialog1->RestoreDirectory = true;
if ( saveFileDialog1->ShowDialog() == ::DialogResult::OK )
{
if ( (myStream = saveFileDialog1->OpenFile()) != nullptr )
|
|
t****t
发帖数: 6806 | 36 来自主题: Programming版 - 一道面试题 current c++ is a bit messy in this point. i heard c++0x is proposing a new
keyword "nullptr" for null pointer and pointer type.
is |
|
r*****3
发帖数: 143 | 37 中文名: 新C++标准：C++0x 概述
原名: Overview of the New C++ : C++0x
作者: Scott Meyers
图书分类: 软件
资源格式: PDF
版本: 英文文字版
出版社: Artima
书号: 978-0-596-80197-6
发行时间: 2011年
地区: 美国
语言: 英文
简介:
内容介绍：
Specification of the next version of C++ (“C++0x”) is nearing completion,
and many compilers (e.g., Visual C++ and Gnu C++) already offer several
features from the revised language. And such features! auto-declared
variables reduce typing drudgery and syntactic noise; Unicode and threading
support address important functional... 阅读全帖 |
|
h*c
发帖数: 1859 | 38 C++11好像引入了好多关键字。。。
不喜
不过nullptr还是不错的，以前用NULL， BS用0，0是很不好的一个东西啊 |
|
w***g
发帖数: 5958 | 39 1. nullptr和constexpr这两个关键字定义的一点美感也没有。形式上已经和Ritchie高
下立现了。要我说还不如把NULL引入成关键字来的好。这样实际上还是跟C兼容的。
2. 什么时候用auto什么时候不适合用或者不能用auto不是很直观。
除了上面两点吹毛求疵的问题以外，我觉得C++更容易写了。 |
|
t****t
发帖数: 6806 | 40 constexpr我也确实不是很喜欢, 感觉为优化而优化了, 还不如引入var-size array呢.
nullptr我倒觉得没什么, 从一致性的角度来说, NULL这样的大写习惯上是macro, 不合
适成为关键字.
auto我觉得没问题, 多写写就清楚了:) |
|
h*c
发帖数: 1859 | 41 C++11好像引入了好多关键字。。。
不喜
不过nullptr还是不错的，以前用NULL， BS用0，0是很不好的一个东西啊 |
|
w***g
发帖数: 5958 | 42 1. nullptr和constexpr这两个关键字定义的一点美感也没有。形式上已经和Ritchie高
下立现了。要我说还不如把NULL引入成关键字来的好。这样实际上还是跟C兼容的。
2. 什么时候用auto什么时候不适合用或者不能用auto不是很直观。
除了上面两点吹毛求疵的问题以外，我觉得C++更容易写了。 |
|
t****t
发帖数: 6806 | 43 constexpr我也确实不是很喜欢, 感觉为优化而优化了, 还不如引入var-size array呢.
nullptr我倒觉得没什么, 从一致性的角度来说, NULL这样的大写习惯上是macro, 不合
适成为关键字.
auto我觉得没问题, 多写写就清楚了:) |
|
y0
发帖数: 231 | 44 Nullptr就是一个明证.
主要是Sutter等微软的5毛在标准委员会里搀沙子 |
|
|
t****t
发帖数: 6806 | 46 you do know null pointer is traditionally expressed by number 0, don't you?
in fact, literal integer 0 is the only way to express null pointer. NULL is
simply a macro form of literal integer 0. you want a warning everytime null
pointer is used?
of course, in c++11, there is this new nullptr keyword.
from
level |
|
t****t
发帖数: 6806 | 47 basically you want to mix PP stage with compile stage.
i think this is generally a very bad idea, unless absolutely necessary. NULL
(not null) or 0 is simply the same token, i think there is more important t
hings to warn about, e.g. multi-value-change-between-sequence-point type of
error; this is implementable and worth the trouble.
distinguishing null or 0 is not worth it. besides there is this new nullptr
keyword now. |
|
q****x
发帖数: 7404 | 48 如下代码，检查空指针和清空集合的责任应该是caller还是callee？按garbage in
garbage out的原则，这两个语句都可以省掉，caller自己负责。但这样好吗？
大家倾向哪种风格？理由是？
void GetNames(set* names) {
if (names == nullptr) return;
name.clear();
for (const string& name = stream.get()) {
names.insert(name);
}
return;
} |
|
q****x
发帖数: 7404 | 49 nullptr check probably is always necessary, as it's critical and cheap.
container clear, on the other hand, is debatable. in this sample code,
actually i think skipping clear is even a bug. |
|
q****x
发帖数: 7404 | 50 比如下面这个：
void foo(int* p) {
assert(p != nullptr);
*p = 100;
}
这里有没有assert都没区别吧？程序总是要崩溃的。
另外加assert使得binary崩溃似乎也不是什么好办法。 |
|
