w****x
发帖数: 2483 | 1
没意思
单链表的quick sort就可以了
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
void sort(NODE* pNode, int nLen)
{
if (NULL == pNode || nLen <= 0)
return;
int nCount = 0;
int nPivot = pNode->nVal;
NODE* pPrev = pNode;
NODE* pIterBeg = pPrev->pNext;
NODE* pIterEnd = pIterBeg;
while (NULL != pIterEnd)
{
if (pIterEnd->nVal < nPivot)
{
swap(pIterBeg->nVal, pIterEnd->nVal);
pPrev = pPrev-... 阅读全帖 |
|
x*********w
发帖数: 533 | 2 quick sort版本
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
void sort(NODE* pNode, int nLen)
{
if (NULL == pNode || nLen <= 0)
return;
int nCount = 0;
int nPivot = pNode->nVal;
NODE* pPrev = pNode;
NODE* pIterBeg = pPrev->pNext;
NODE* pIterEnd = pIterBeg;
while (NULL != pIterEnd)
{
if (pIterEnd->nVal < nPivot)
{
swap(pIterBeg->nVal, pIterEnd->nVal);
pPrev = pPrev->pNext;
... 阅读全帖 |
|
p*****3
发帖数: 488 | 3 给个我以前写的吧，快速排序版本的
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
void sort(NODE* pNode, int nLen)
{
if (NULL == pNode || nLen <= 0)
return;
int nCount = 0;
int nPivot = pNode->nVal;
NODE* pPrev = pNode;
NODE* ... 阅读全帖 |
|
w****x
发帖数: 2483 | 4 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int x) : nVal(x), pLft(NULL), pRgt(NULL) {}
};
struct TreeIter
{
stack m_stk;
void movNext()
{
if (m_stk.empty())
return;
NODE* pCur = m_stk.top();
if (pCur->pRgt != NULL)
{
pushLft(pCur->pRgt);
return;
}
while (!m_stk.empty() && pCur != m_stk.top()->pLft)
{
pCur = m_stk.top();
m_stk.pop... 阅读全帖 |
|
w****x
发帖数: 2483 | 5
struct EVENT
{
int nStart;
int nEnd;
bool bFlg;
EVENT(int a, int b) : nStart(a), nEnd(b) { bFlg = false; }
};
struct ENDPOINT
{
int nIndex;
bool bStart;
int nVal;
};
bool lessThan(const ENDPOINT& ed1, const ENDPOINT& ed2)
{
return ed1.nVal < ed2.nVal;
}
void setFlg(EVENT events[], int n)
{
if (events == NULL || n <= 0)
return;
ENDPOINT* ends = new ENDPOINT[n*2];
for (int i = 0; i < n; i++)
{
ends[2*i].bStart = true;
ends[2*... 阅读全帖 |
|
c*********n
发帖数: 128 | 6 刚刚开始学java.
我做的事情是类似于C中scanf完成的功能
目前找到一种方法, 想问一下这个是不是java程序常用的方法, 如果不是, 那么常用的方
法
是什么?
我找到的实现方法如下:
首先
InputStreamReader isr = new InputStreamReader ( System.in );
StreamTokenizer st = new StreamTokenizer ( isr );
然后使用方法st.nextToken()
判断st.nextToken()的返回值(返回ttype),
如果ttype等于TT_NUMBER, 说明读取的是一个number, 并且该number将被存放于st.nval
然后读取st.nval就可以得到该数
是这样实现的么? 还有更好的实现方法么?
关于这个方法我还有一个问题, 根据我查的文档nval是double型变量啊, 那要读入int变
量
怎么办呢?
nval:
public double nval
If the current token is a number, this field contains |
|
w****x
发帖数: 2483 | 7 //Merge two BST
//O(n) solution
//1. Change BST into linked list
//2. Merge 2 linked lists
//3. Change linked list into a balanced BST
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
////////////////////change BST to linked list///////////////////////////////
void _inner_chng_link(NODE* pNode, NODE*& ph, NODE*& pt)
{
if (NULL == pNode) return;
NODE* pLft1 = pNode;
NODE* pLft2 = pNode;
_inner_chng_link(pNode->pLft... 阅读全帖 |
|
w****x
发帖数: 2483 | 8
那是相当简洁啊~~~
全干掉：
/*
Given a sorted linked list, delete all duplicate numbers, leave only
distinct numbers from original list. e.g., given 1->2->3->3->4->4->5, return
1->2->5. Given 1->1->1->2->3, return 2->3.
*/
struct NODE
{
int nVal;
NODE* pNxt;
NODE(int n) : nVal(n), pNxt(NULL) {}
};
NODE* RemoveDupNodes(NODE* pHead)
{
assert(pHead);
NODE* pCur = pHead;
NODE* pPrev = NULL;
while (pCur != NULL)
{
NODE* pIter = pCur->pNxt;
bool bDel = false;
... 阅读全帖 |
|
w****x
发帖数: 2483 | 9
啊，不好意思，丢错版本了
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
NODE* mergeTwoList(NODE* p1, NODE* p2)
{
if (NULL == p1 && NULL == p2)
return NULL;
if (NULL == p1) return p2;
if (NULL == p2) return p1;
NODE* pIter1 = p1;
NODE* pIter2 = p2;
NODE* pIter = NULL;
NODE* pHead = NULL;
while (pIter1 != NULL && pIter2 != NULL)
{
NODE* pSmall = NULL;
if (pIter1->nVal < pIter2->nVal)
{
p... 阅读全帖 |
|
w****x
发帖数: 2483 | 10
写一个
//Merge two BST
//O(n) solution
//1. Change BST into linked list
//2. Merge 2 linked lists
//3. Change linked list into a balanced BST
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
////////////////////change BST to linked list///////////////////////////////
void _inner_chng_link(NODE* pNode, NODE*& ph, NODE*& pt)
{
if (NULL == pNode) return;
NODE* pLft1 = pNode;
NODE* pLft2 = pNode;
_inner_chng_link(pNode-... 阅读全帖 |
|
w****x
发帖数: 2483 | 11 这题作的不下5遍了, 说实话, 第一次做还挺不容易的:
============带parent===========================
void InOrderPrint(NODE* pRoot)
{
assert(pRoot);
NODE* pCur = pRoot;
while (pCur != NULL)
{
while (pCur->pLft != NULL)
{
cout<nVal<
pCur = pCur->pLft;
}
cout<nVal<
//The ending condition is tricky but simple
while (pCur != NULL)//use "pCur != NULL" rather than "pCur->pParent
!= NULL"
... 阅读全帖 |
|
w****x
发帖数: 2483 | 12 /*
Serialize/DeSerialize a tree
*/
struct NODE
{
int nVal;
vector vec;
NODE(int n) : nVal(n) {}
};
void _inner_serial(NODE* pNode, char*& p)
{
if (NULL == pNode)
return;
*p++ = pNode->vec.size();
*p++ = pNode->nVal;
for (vector::iterator it = pNode->vec.begin();
it != pNode->vec.end(); it++)
_inner_serial(*it, p);
}
const char* Serialize(NODE* pRoot, char mem[])
{
if (NULL == mem || NULL == pRoot)
return NULL;
char... 阅读全帖 |
|
w****x
发帖数: 2483 | 13 //How to find a value in a skip list
//about skip-list http://en.wikipedia.org/wiki/File:Skip_list.svg
struct SKIP_NODE
{
int nVal;
vector links;
};
//sort like binary search, scope down to decrease the searching range
SKIP_NODE* Find(SKIP_NODE* pHead, int x)
{
assert(pHead);
SKIP_NODE* pCur = pHead;
int nIndex = pHead->links.size() - 1;
while (nIndex >= 0)
{
if (pCur->nVal == x)
return pCur;
if (pCur->links[nIndex] == NULL ||
... 阅读全帖 |
|
w****x
发帖数: 2483 | 14 /*
Serialize/DeSerialize a tree
*/
struct NODE
{
int nVal;
vector vec;
NODE(int n) : nVal(n) {}
};
void _inner_serial(NODE* pNode, char*& p)
{
if (NULL == pNode)
return;
*p++ = pNode->vec.size();
*p++ = pNode->nVal;
for (vector::iterator it = pNode->vec.begin();
it != pNode->vec.end(); it++)
_inner_serial(*it, p);
}
const char* Serialize(NODE* pRoot, char mem[])
{
if (NULL == mem || NULL == pRoot)
return NULL;
char... 阅读全帖 |
|
w****x
发帖数: 2483 | 15 /*
Serialize/DeSerialize a tree
*/
struct NODE
{
int nVal;
vector vec;
NODE(int n) : nVal(n) {}
};
void _inner_serial(NODE* pNode, char*& p)
{
if (NULL == pNode)
return;
*p++ = pNode->vec.size();
*p++ = pNode->nVal;
for (vector::iterator it = pNode->vec.begin();
it != pNode->vec.end(); it++)
_inner_serial(*it, p);
}
const char* Serialize(NODE* pRoot, char mem[])
{
if (NULL == mem || NULL == pRoot)
return NULL;
char... 阅读全帖 |
|
w****x
发帖数: 2483 | 16
不知道有没有其他bug
int myatoi(const char* p)
{
assert(p);
int nFlg = 1;
if ('-' == *p)
nFlg = -1;
if ('-' == *p || '+' == *p)
p++;
if ('\0' == *p)
throw CException("Invalid expression");
int nRet = 0;
while('\0' != *p)
{
if (*p < '0' || *p > '9')
throw CException("Invalid character");
int nVal = *p - '0';
int nNew = nRet*10 + nFlg * nVal;
if (nRet != 0 && ((nNew & 0x80000000) != (nRet & 0x80000000)))
... 阅读全帖 |
|
w****x
发帖数: 2483 | 17 5 minutes
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet->pRgt);
return pRet;
}
private:
void PushLefts(NODE* pNode)
{
while (NULL != pNode)
{
m_stk.p... 阅读全帖 |
|
w****x
发帖数: 2483 | 18 //Get all trees according to preorder
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
void GetComb(int a[], int n, vector& vec)
{
if (n <= 0)
return ;
if (n == 1)
{
vec.push_back(new NODE(a[0]));
return;
}
vector vecTmp1;
GetComb(a+1, n-1, vecTmp1);
for (vector::iterator it = vecTmp1.begin();
it != vecTmp1.end(); it++)
{
NODE* pRoot = ne... 阅读全帖 |
|
w****x
发帖数: 2483 | 19 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class CIterator
{
public:
CIterator(NODE* pRoot)
{
pushLft(pRoot);
}
NODE* GetNext()
{
if (m_stk.empty()) return NULL;
NODE* pRet = stk.top();
stk.pop();
pushLft(pRet->pRgt);
return pRet
}
private:
void pushLft(NODE* pNode)
{
NODE* pIt... 阅读全帖 |
|
w****x
发帖数: 2483 | 20 /*
add sibling pointer to the right sibling of each node in a tree, O(n) time,
O(1) space.
5 minutes thinking, 10 minutes coding, a hint he gave me: recursion
*/
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE* pSibling;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL), pSibling(NULL) {}
};
void LinkRightFromParent(NODE* pNode, NODE* pParent)
{
if (pNode == NULL) return;
//Under this situation, the current node will connect to the child of
current parent
if (pPa... 阅读全帖 |
|
w****x
发帖数: 2483 | 21 /*
add sibling pointer to the right sibling of each node in a tree, O(n) time,
O(1) space.
5 minutes thinking, 10 minutes coding, a hint he gave me: recursion
*/
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE* pSibling;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL), pSibling(NULL) {}
};
void LinkRightFromParent(NODE* pNode, NODE* pParent)
{
if (pNode == NULL) return;
//Under this situation, the current node will connect to the child of
current parent
if (pPa... 阅读全帖 |
|
w****x
发帖数: 2483 | 22
的却是很好的一个方案，不需要用heap, 因为一定是连续的
void _inner_mclosest(NODE* pNode, int nTg, int m, deque& que)
{
if (NULL == pNode)
return;
_inner_mclosest(pNode->pLft, nTg, m, que);
if (que.size() < m)
que.push_back(pNode);
else
{
if (abs(pNode->nVal - nTg) < abs(que.front()->nVal - nTg))
{
que.pop_front();
que.push_back(pNode);
}
}
_inner_mclosest(pNode->pRgt, nTg, m, que);
}
bool getMClosest2(NODE* pRoot, int nTg... 阅读全帖 |
|
w****x
发帖数: 2483 | 23 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
int getHeight(NODE* pNode, bool bLft)
{
int nRet = 0;
NODE* pIter = pNode;
while (NULL != pIter)
{
if (bLft)
pIter = pIter->pLft;
else
pIter = pIter->pRgt;
nRet++;
}
return nRet;
}
int getNum(int h)
{
return pow((double)2, h) -1;
}
int getNumberOfNodes(NODE* pRoot)
{
NODE* pNode = pRoot;
int h = get... 阅读全帖 |
|
p*****3
发帖数: 488 | 24 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet->pRgt);
return pRet;
}
private:
void PushLefts(NODE* pNode)
{
while (NULL != pNode)
{
m_stk.push(pNode)... 阅读全帖 |
|
w**x
发帖数: 362 | 25 your code is not C++, but C.
No constructor.
No operator()++.
No destructor.
No current iter.
why void PushLefts(NODE* pNode) ?
Left is left not lefts.
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet... 阅读全帖 |
|
c**i
发帖数: 6973 | 26 Hans M. Kristensen, Chinese Jin-SSBNs Getting Ready? FAS Strategic Security
Blog, June 2, 2011
http://www.fas.org/blog/ssp/2011/06/jin2011.php
My comment:
(a) Xiaopingdao naval base
A Chinese-language web site refers to it as 小平岛潜艇基地; whether it is a
nval base or submarine base is debatable.
(b) Please take notice of a dialogue, beyond the text.
Rick says: "How does the author know the Chinese military only has a limited
capability to communicate with the submarines while at sea?
Reply: "The se... 阅读全帖 |
|
