## CCI题目4-3：Tree from Sorted Array

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

```
//
//  main.cpp
//  CCI.4.3.Tree from Sorted Array
//
//  Created by Qiu Xiangyu on 12-11-24.
//

#include
#include
using namespace std;

struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int val, TreeNode *l, TreeNode *r) {
value = val;
left = l;
right = r;
}
TreeNode(int val = 0) {
value = val;
left = NULL;
right = NULL;
}
};

TreeNode *buildTreeFromSortedArray(vector &arr, size_t istart, size_t iend) {
if (istart > iend) {
return NULL;
}
int imid = (istart + iend + 1) / 2;
TreeNode *root = new TreeNode(arr[imid]);
root->left = buildTreeFromSortedArray(arr, istart, imid - 1);
root->right = buildTreeFromSortedArray(arr, imid + 1, iend);
return root;
}
TreeNode *buildTreeFromSortedArray(vector &arr) {
return buildTreeFromSortedArray(arr, 0, arr.size() - 1);
}

int main(int argc, const char * argv[])
{
// insert code here...
std::cout << "Hello, World!\n";
vector arr = {1,2,3,4,5,6,7,8,9,10};
TreeNode *root = buildTreeFromSortedArray(arr);
return 0;
}
```

## CCI题目4-2：判断图中的两个节点是否连通

Given a directed graph, design an algorithm to find out whether there is a route be- tween two nodes.

```
//
//  main.cpp
//  CCI.4.2.Reachable in Graph
//
//  Created by Qiu Xiangyu on 12-11-24.
//

#include
#include
#include
using namespace std;
enum VisitState {
Unvisite = 0,
Visiting = 1,
Visited = 2
};
class GraphNode {
public:
VisitState visiteState;
};
class Graph {

public:
void setAllVisiteState(VisitState targetState);
bool isNodeInGraph(GraphNode *node);
bool isNodeConnectToNode(GraphNode *sourceNode, GraphNode *targetNode) {
if (!isNodeInGraph(sourceNode) || !isNodeInGraph(targetNode)) {
return false;
}
setAllVisiteState(Unvisite);
//unvisit, not visited at all
//visiting, in the queue, but not examed and expaned
//vivited, expanded and visited.
queue q;
q.push(sourceNode);
while (q.size()) {
GraphNode *curNode = q.front();
q.pop();
if (curNode->visiteState == Visited) {
continue;
}
if (curNode == targetNode) {
return true;
}
curNode->visiteState = Visited;
for (list::iterator it = adjacents.begin(); it != adjacents.end(); ++it) {
GraphNode *cnode = *it;
if (cnode->visiteState == Unvisite) {
cnode->visiteState = Visiting;
q.push(cnode);
}
}
}
return false;
}
};

int main(int argc, const char * argv[])
{
// insert code here...
std::cout << "Hello, World!\n";
return 0;
}
```

## CCI题目4-1：Check Balance of a Binary Tree，二叉树的基本算法

PS.但是按照书上的solution，代码翻译出来的题意，对于叶子节点的理解是说Null节点。

1.从string初始化一棵树（借鉴leetcode的表示方法）
2.递归实现的inorder，preorder，postorder深度优先遍历
3.queue实现的广度优先遍历

Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

Code

<

pre>
//
// main.cpp
// CCI.4.1.Check Balance of a Tree
//
// Created by Qiu Xiangyu on 12-11-21.
//

# include

using namespace std;

struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int val, TreeNode *l, TreeNode *r) {
value = val;
left = l;
right = r;
}
TreeNode(int val = 0) {
value = val;
left = NULL;
right = NULL;
}
};

TreeNode *buildTreeFromString(string s) {
if (s.size() == 0 || s[0] == ‘#’) {
return NULL;
}
TreeNode *root = NULL;
queue<TreeNode**> que;
que.push(&root);
int v = 0;
bool isnull = false;
int istr = 0;
while (true) {
if (istr >= s.size() || s[istr] == ‘,’) {

```        TreeNode **ppnode = que.front();
que.pop();

if (ppnode && !isnull) {
TreeNode *newNode = new TreeNode(v);
*ppnode = newNode;
que.push(&newNode->left);
que.push(&newNode->right);
} else {
que.push(NULL);
que.push(NULL);
}

if (istr >= s.size()) {
break;
}

v = 0;
} else {
if (s[istr] == '#') {
v = 0;
isnull = true;
} else {
v = 10 * v + s[istr] - '0';
isnull = false;
}
}
++istr;
}
return root;```

}

void inorder(TreeNode root, void (nodeHandler)(TreeNode* node) ) {
if (root == NULL) {
cout<<“null\n”;
return;
}
inorder(root->left, nodeHandler);
nodeHandler(root);
inorder(root->right, nodeHandler);
}

void preorder(TreeNode root, void (nodeHandler)(TreeNode* node) ) {
if (root == NULL) {
cout<<“null\n”;
return;
}
nodeHandler(root);
preorder(root->left, nodeHandler);
preorder(root->right, nodeHandler);
}

void postorder(TreeNode root, void (nodeHandler)(TreeNode* node) ) {
if (root == NULL) {
cout<<“null\n”;
return;
}
postorder(root->left, nodeHandler);
postorder(root->right, nodeHandler);
nodeHandler(root);
}

void breadthfirst(TreeNode root, void (nodeHandler)(TreeNode* node)) {
queue<TreeNode*> que;
que.push(root);
int count = root ? 1 : 0;
while (que.size()) {
TreeNode *node = que.front();
que.pop();
if (node) {
–count;
nodeHandler(node);
que.push(node->left);
que.push(node->right);
if (node->left) {
++count;
}
if (node->right) {
++count;
}
} else {
cout<<“n\n”;
que.push(NULL);
que.push(NULL);
}
if (0 == count) {
break;
}
}
}

void printNode(TreeNode *node) {
cout<value<<endl;
}

int mindepth(TreeNode *node) {
if (NULL == node) {
return 0;
}
int rightMin = mindepth(node->right);
if (node->left) {
int leftMin = mindepth(node->left);
if (node->right) {
return 1 + (leftMin < rightMin ? leftMin : rightMin);
} else {
return 1 + leftMin;
}
} else {
return 1 + rightMin;
}
}
int maxdepth(TreeNode *node) {
if (NULL == node) {
return 0;
}
int leftmax = maxdepth(node->left);
int rightmax = maxdepth(node->right);
return 1 + (leftmax > rightmax ? leftmax : rightmax);
}
bool isBalance(TreeNode *root) {
int dmax = maxdepth(root);
int dmin = mindepth(root);
return abs(dmax – dmin) <= 1;
}
int main(int argc, const char * argv[])
{
// insert code here…
std::cout << “Hello, World!\n”;
string instr = “1,2,3,4,#,#,#,5”;
TreeNode *root = buildTreeFromString(instr);
int dmax = maxdepth(root);
int dmin = mindepth(root);
cout<<“dmax:”<<dmax<<“,dmin:”<<dmin<<endl;
cout<<“Is balance:”<<isBalance(root)<<endl;
return 0;
}

## CCI题目：3-6：Stack Sort

1.逐个从st中pop元素，先pop到一个临时变量，如果pop出来的元素比临时变量小，则直接进入buffer，否则，把临时变量顶入buffer，st新pop到临时变量。

2.将buffer中的元素全部倒回st
3.重复1，2两步，直到1中第一种情况不出现为止。

《CCI》上的解法更效率一些（在阶上没有提升），就是在st到buffer中处理的过程中，允许中途将buffer中的元素倒回一部分到st，直到临时变量找到位置，然后继续将st向buffer倒。直到st为空。

Write a program to sort a stack in ascending order. You should not make any assump- tions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

Code

<

pre>

//
// main.cpp
// CCI.3.6.Sort a Stack
//
// Created by Qiu Xiangyu on 12-11-20.
//

# include

using namespace std;
void sortStack(stack &st) {
stack buffer;
bool bubble = true;
int rnd = 1;
while (bubble) {
cout<<“round “<<rnd++<<endl;
bubble = false;
//1.dump numbers from st to buffer and change the order of them
int middle = st.top();
st.pop();
while (st.size()) {
if (middle > st.top()) {
//if st.top is less than the one pop before, then pop to buffer
buffer.push(st.top());
bubble = true;
} else {
//if st.top is ge the one pop before, then push the middle to buffer ,then pop to middle
buffer.push(middle);
middle = st.top();
}
st.pop();
}
buffer.push(middle);
//2.dump buffer to st
while (buffer.size()) {
st.push(buffer.top());
buffer.pop();
}
}
}
int main(int argc, const char * argv[])
{
std::cout << “Hello, World!\n”;
stack st;
srand((unsigned int)clock());
for (int i = 0; i < 100; ++i) {
st.push(rand() % 10);
}
sortStack(st);
while (st.size()) {
cout<<st.top()<<endl;
st.pop();
}
return 0;
}

## CCI题目3-5：Queue using Two Stacks

Implement a MyQueue class which implements a queue using two stacks.

Code

<

pre>

//
// main.cpp
// CCI.3.5.Queue using Two Stacks
//
// Created by Qiu Xiangyu on 12-11-20.
//

# include

using namespace std;

//stacks like:
// instack: [old , … , new
// outstack: old, … , new]
template
class StackQueue {
stack _inStack;
stack _outStack;
void dumpToInStack() {
while (_outStack.size()) {
_inStack.push(_outStack.top());
_outStack.pop();
}
}
void dumpToOutStack() {
while (_inStack.size()) {
_outStack.push(_inStack.top());
_inStack.pop();
}
}
public:
void push(T val) {
dumpToInStack();
_inStack.push(val);
}
void pop() {
dumpToOutStack();
_outStack.pop();
}
T *top() {
dumpToOutStack();
if (_outStack.size()) {
return &_outStack.top();
}
return NULL;
}
size_t size() {
return _inStack.size() + _outStack.size();
}
};
int main(int argc, const char * argv[])
{

```// insert code here...
std::cout << "Hello, World!\n";
StackQueue<int> qu;
for (int i = 0; i < 10; ++i) {
qu.push(i);
}
while (qu.size()) {
int v = *qu.top();
cout<<v<<endl;
qu.pop();
}
return 0;```

}

## CCI题目3-4：Hanoi Tower

1.将n-1个盘子，从0移动到1，将stack1用作临时stack；
2.将最下面的第n个盘子，从0移动到2；
3.将刚才放到临时stack1的n-1个盘子，移动到stack2。

In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks.

Code

```
//
//  main.cpp
//  CCI.3.4.Hanoi Tower
//
//  Created by Qiu Xiangyu on 12-11-20.
//

#include
#include
using namespace std;

void move(stack stacks[], int count, int sourceIndex, int targetIndex, int tempIndex) {
if (count == 0) {
return;
}
//moving the top of plants to temporary stack, leaving the last one
move(stacks,count - 1,sourceIndex,tempIndex,targetIndex);
//moving the last plate to the target stack
int plate = stacks[sourceIndex].top();
cout<<"moving plate "< stacks[3];
for (int i = 0; i < count; ++i) {
stacks[0].push(count - i);
}
//solve it
move(stacks,count,0,2,1);
}

int main(int argc, const char * argv[])
{
// insert code here...
std::cout << "Hello, World!\n";
hanoi(10);
return 0;
}
```

## CCI题目3-3：Set Of Stacks

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. There- fore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOf- Stacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

```
//
//  main.cpp
//  CCI.3.3.SetOfStack
//
//  Created by Qiu Xiangyu on 12-11-20.
//

#include
#include
using namespace std;

template
class stackNode {
public:
T                value;
stackNode    *pre;
};

template
class singleStack {
int              _size;
stackNode    *_top;
public:
singleStack() {
_size = 0;
_top = NULL;
}
int size() {
return _size;
}
T *top() {
return _top ? &_top->value : NULL;
}
void push(T val) {
stackNode *newnode = new stackNode();
newnode->value = val;
newnode->pre = _top;
_top = newnode;
++_size;
}
void pop() {
if (_top) {
stackNode *oldtop = _top;
_top = _top->pre;
delete oldtop;
--_size;
}
}
};

template
class setOfStack {
int                          _size;
int                          _singleLmt;
vector >      _stacks;
public:
setOfStack(int sizeLimitOnSingleStack = 10){
_singleLmt = sizeLimitOnSingleStack;
_size = 0;
}
void push(T val) {
if (_stacks.size() > 0 && _stacks.back().size() < _singleLmt) {
singleStack &targetStack = _stacks.back();
targetStack.push(val);
} else {
cout<<"new stack for item: "< newstack;
newstack.push(val);
_stacks.push_back(newstack);
}
++_size;
}
void pop() {
if (_stacks.size() > 0) {
singleStack &targetStack = _stacks.back();
targetStack.pop();
if (targetStack.size() == 0) {
cout<<"remove stack at size: "<<_size< 0) {
return _stacks.back().top();
}
return NULL;
}
};

int main(int argc, const char * argv[])
{
// insert code here...
std::cout << "Hello\n";
setOfStack stk(3);
for (int i = 0; i < 10; ++i) {
stk.push(i);
}
while (stk.size() > 0) {
int v = * stk.top();
cout<
```

## CCI题目3-2：Min Stack

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

<

pre>

//
// main.cpp
// CCI.3.2.Min Stack
//
// Created by Qiu Xiangyu on 12-11-19.
//

# include

using namespace std;

template
class stackNode {
public:
Ts value;
stackNode pre;
stackNode *min;
stackNode() {pre = NULL;}
stackNode(Ts&avalue, stackNode
thePre):value(avalue),pre(thePre) {;}
};

template
class minStack {
int _size;
stackNode *_top;
public:
minStack() {
_size = 0;
_top = NULL;
}
void push(T value) {
stackNode *newnode = new stackNode(value,_top);
stackNode *minnode = newnode;
if (_top && _top->min->value < minnode->value) {
minnode = _top->min;
}
newnode->min = minnode;
_top = newnode;
}
void pop() {
if (_top) {
stackNode *lastNode = _top;
_top = lastNode->pre;
delete lastNode;
}
}
T *top() {
if (_top) {
return &_top->value;
}
return NULL;
}
T *min() {
if (_top) {
return &_top->min->value;
}
return NULL;
}
};

int main(int argc, const char * argv[])
{
std::cout << “Hello\n”;
minStack teststack;
for (int i = 0; i < 10; ++i) {
teststack.push(10 – i);
}
for (int i = 0; i < 10; ++i) {
teststack.push(i);
}
while (teststack.top()) {
int val = teststack.top();
cout<<“v(“<<val<<“),m(“<<
teststack.min()<<“)\n”;
teststack.pop();
}
return 0;
}

## CCI题目3-1：Three Stacks in One Array

Describe how you could use a single array to implement three stacks.

```
//
//  main.cpp
//  CCI.3.1.Three Stacks in One Array
//
//  Created by Qiu Xiangyu on 12-11-17.
//

#include
using namespace std;

template
class stackNode {
public:
Ts                value;
stackNode    *pre;
stackNode() {pre = NULL;}
stackNode(Ts&avalue, stackNode*thePre):value(avalue),pre(thePre) {;}
};

template
class triStack {
int              stackSize[3];
stackNode    *tops[3];
stackNode    *empty;
stackNode    *buffer = NULL;
int              bufferSize = 0;
inline stackNode *getEmptySlot() {
if (empty == NULL) {
return NULL;
}
stackNode *etop = empty;
empty = etop->pre;
return etop;
}
inline void reuse(stackNode * node) {
node->pre = empty;
empty = node;
}
public:
inline int totleSize() {
int sum = 0;
for (int i = 0; i < 3; ++i) {
sum += stackSize[i];
}
return sum;
}
inline bool isFull() {
return NULL == empty;
}
bool push(int stackIndex,T value) {
if (stackIndex < 0 || stackIndex >= 3) {
return false;
}
stackNode *slot = getEmptySlot();
if (NULL == slot) {
//stack full
return false;
}
stackNode *last = tops[stackIndex];
slot->pre = last;
tops[stackIndex] = slot;
++stackSize[stackIndex];
return true;
}
bool pop(int stackIndex) {
if (stackIndex < 0 || stackIndex >= 3) {
return false;
}
stackNode *top = tops[stackIndex];
if (NULL == top) {
return false;
}
tops[stackIndex] = top->pre;
--stackSize[stackIndex];
reuse(top);
}
T *top(int stackIndex) {
if (stackIndex < 0 || stackIndex >= 3) {
//error
return NULL;
}
stackNode *topNode = tops[stackIndex];
if (NULL == topNode) {
return NULL;
}
return &topNode->value;
}
triStack(int totalSize) {
if (totalSize > 0) {
bufferSize = totalSize;
buffer = new stackNode [bufferSize];

//initilize the empty chain.
stackNode * last = NULL;
for (int i = 0; i < bufferSize; ++i) {
stackNode *pnode = buffer + i;
pnode->pre = last;
last = pnode;
}
empty = buffer + bufferSize - 1;

//initilize the stacks
for (int i = 0; i < 3; ++i) {
tops[i] = NULL;
stackSize[i] = 0;
}
} else {
cout<<"Error stack size\n";
}
}
~triStack() {
if (buffer) {
delete buffer;
buffer = NULL;
}
}
};

int main(int argc, const char * argv[])
{
std::cout << "Hello\n";

triStack teststack(3);
if (true != teststack.push(0, 0)) cout<<"err\n";
if (true != teststack.push(1, 1)) cout<<"err\n";
if (true != teststack.push(2,2)) cout<<"err\n";
if (false != teststack.push(2,3)) cout<<"err\n";
if (true != teststack.isFull()) cout<<"err\n";
return 0;
}
```

## CCI题目2-5：Find Loop

Given a circular linked list, implement an algorithm which returns node at the begin- ning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C

<

pre>
Node * findLoop(Node *pHead) {
map exmap;
if (exmap.find(pHead) != exmap.end()) {
}
}
return NULL;
}

Node *findLoopEx(Node *pHead) {
Node *pRunner = pHead;
Node *pWalker = pHead;
int step = 0;

```//each step of walker, runner goes two.
while (pRunner) {
pRunner = pRunner->next;
if (++step == 2) {
pWalker = pWalker->next;
step = 0;
if (pRunner == pWalker) {
break;
}
}
}
if (!pRunner) {
return NULL;//no loop
}
//then they meet at the k posotion before loop started
//and the k is nodes before loop start
//so let runner back to head and with speed of 1
//they go simutaniously, when next meet, that position is the loop start point
while (pWalker) {
if (pWalker == pRunner) {
return pWalker;
}
pWalker = pWalker->next;
pRunner = pRunner->next;
}
return NULL;//something wrong```

}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
Node *phead = loopList(10, 8);
cout<<“process…”<<endl;
Node *pLoop = findLoop(phead);
printList(pLoop);
cout<<“done”<<endl;
return 0;
}

map操作

```void mapTest(){
map testmap;
//insert key,val in map:
testmap[1] = true;
testmap[666] = false;
//find key in map
map::iterator it = testmap.find(1);
if (it != testmap.end()) {
//key if found in map
int key = it->first;//this is key
bool val = it->second;//this is val;
it->second = !val;
}
//delete a key
testmap.erase(1);
}
```

## CCI题目2-4：Add Two Numbers in Link List

You have two numbers represented by a linked list, where each node contains a sin- gle digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8

## CCI题目2-3:Remove Node at Middle of a Link List

Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e

<

pre>
void RemoveMiddle(Node **ppHead) {
//1,2 del 0; 3,4 del 1; …
return;
}
Node *pRunner = (
Node **ppPre = ppHead;
bool move = false;
while (pRunner) {
pRunner = pRunner->next;
if (move) {
ppPre = &(*ppPre)->next;
}
move = !move;
}
//hold the removing one
pRunner = *ppPre;
//delete it from list
*ppPre = pRunner->next;
//delete it
delete pRunner;
}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
// instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
// instr = “10,9,8,7,6,5,4,3,2,1,0”;
// instr = “0,1,2,3,4,5,6,7,8,9,10”;
instr = “”;
// cin>>instr;
Node *phead = strToList(instr);
cout<<“process…”<<endl;
cout<<“done”<<endl;
return 0;
}

## CCI习题2-2：nTh From the last

Implement an algorithm to find the nth to last element of a singly linked list.

<

pre>
//zero based n th from the rear
Node * nThFromLast(Node *pHead, int n) {
if (n < 0) {
cout<<“n below 0″<<endl;
return NULL;
}
Node *pCur = pHead;
Node *pRun = pHead;
//1.let pRun go n position before pCur
for (int i = 0; i <= n; ++i) {
if (!pRun) {
cout<<“Not enough nodes”<<endl;
return NULL;//no enough nodes in the link list
}
pRun = pRun->next;
}
//2.go paralell untile pRun become NULL
while (pRun) {
pRun = pRun->next;
pCur = pCur->next;
}
return pCur;
}
int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
// instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
instr = “10,9,8,7,6,5,4,3,2,1,0”;
// cin>>instr;
Node *phead = strToList(instr);
cout<<“process…”<<endl;
Node *pNth = nThFromLast(phead,10);//test 10,9,5,1,0,12,-11
if (pNth) {
cout<value<<endl;
}
cout<<“done”<<endl;
return 0;
}

## CCI习题2-1： Remove Duplicates

Remove Duplicates
Write code to remove duplicates from an unsorted linked list.
How would you solve this problem if a temporary buffer is not allowed?

<br>

<

pre>
//
// main.cpp
// CCI.2.1.RemoveDuplicate
//
// Created by Qiu Xiangyu on 12-11-14.
//

# include

using namespace std;
struct Node{
int value;
Node *next;
Node(int val):value(val),next(NULL) {;}
};
Node *strToList(string str){
Node *phead = NULL;
Node **ppnext = &phead;
int v = 0;
bool rem = false;
for (int i = 0; i < str.size(); ++i) {
char c = str[i];
if (c >= ‘0’ && c <= ‘9’) {
v = 10 * v + (c – ‘0’);
rem = true;
} else {
*ppnext = new Node(v);
ppnext = &((*ppnext)->next);
v = 0;
rem = false;
}
}
if (rem) {
*ppnext = new Node(v);
}
}
void printList(Node *phead) {
cout<<“List : “;
cout<value;
cout<<“,”;
}
}
cout<<endl;
}

void removeDuplicate(Node *pHead) {
Node *pCur = pHead;
while (pCur) {
Node **ppNext = &pCur->next;
while (*ppNext) {
Node *pNext = *ppNext;
if (pNext->value == pCur->value) {
*ppNext = pNext->next;
delete pNext;
pNext = NULL;
} else {
ppNext = &(*ppNext)->next;
}
}
pCur = pCur->next;
}
}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
// cin>>instr;
Node *phead = strToList(instr);
cout<<“process…”<<endl;
cout<<“done”<<endl;
return 0;
}

## CCI习题1-8：Is Rotation

Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).

<

pre>

//
// main.cpp
// CCI.1.8.IsRotateString
//
// Created by Qiu Xiangyu on 12-11-13.
//

# include

using namespace std;

bool isRotation(string &str0, string &str1) {
if (str0.size() != str1.size()) {
return false;
}
string str00 = str0 + str0;
size_t loc = str00.find(str1);
cout<<loc<<endl;
return loc < str00.size();
}

int main(int argc, const char * argv[])
{
// insert code here…
cout << “Input Str0 below:\n”;
string str0;
cin>>str0;
cout<<“Input Str0:”<<str0<<endl<<“Input Str1 below:”<<endl;
string str1;
cin>>str1;
cout<<“Input Str1:”<<str1<<endl;

```//process
bool isRotate = isRotation(str0,str1);
cout<<"Result : "<<isRotate<<endl;

return 0;```

}

## CCI习题1-7：Set Matrix Zeroes

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

LeetCode题目：Set Matrix Zeroes

## CCI习题1-6：Rotate Image

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

LeetCode题目：Rotate Image

## CCI习题1-5：Replace Space

Write a method to replace all spaces in a string with ‘%20’.

<

pre>
//
// main.cpp
// CCI.1.5.Replace Space
//
// Created by Qiu Xiangyu on 12-11-13.
//

# include

using namespace std;

char replaceSpace(char *cstr) {
if (NULL == cstr) {
return NULL;
}
size_t len = 0;
int spaceCount = 0;
while (cstr[len] != ‘\0’) {
if (cstr[len] == ‘ ‘) {
++spaceCount;
}
++len;
}
size_t finalLen = len + spaceCount * 2;
char *ret = new char[finalLen + 1];
size_t curi = 0;
while (
cstr != ‘\0’) {
if (*cstr == ‘ ‘) {
ret[curi++] = ‘%’;
ret[curi++] = ‘2’;
ret[curi++] = ‘0’;
} else {
ret[curi++] = *cstr;
}
++cstr;
}
ret[curi] = ‘\0’;
return ret;
}

int main(int argc, const char * argv[])
{
// insert code here…
cout << “Input below:\n”;
char cstr[200];
gets(cstr);
cout<<“Input:”<<cstr<<endl;

```//process
char *newstr = replaceSpace(cstr);
cout<<"Result : "<<newstr<<endl;
delete newstr;

return 0;```

}

## CCI习题1-4：Anagrams

Write a method to decide if two strings are anagrams or not.

<

pre>

//
// main.cpp
// CCI.1.4.Anagram
//
// Created by Qiu Xiangyu on 12-11-13.
//

# include

using namespace std;

bool anagram(string &str0, string &str1) {
sort(str0.begin(),str0.end());
sort(str1.begin(),str1.end());
return str0 == str1;
}

bool anagram1(string &str0, string &str1) {
if (str0.size() != str1.size()) {
return false;
}
int map[256];
for (int i = 0; i < 256; ++i)
map[i] = 0;
for (int i = 0; i < str0.size(); ++i) {
map[str0[i]] ++;
}
for (int i = 0; i < str1.size(); ++i) {
— map[str1[i]];
}
for (int i = 0; i < 256; ++i) {
if (map[i] != 0) {
return false;
}
}
return true;
}

int main(int argc, const char * argv[])
{
// insert code here…
cout << “Input Str0 below:\n”;
string str0;
cin>>str0;
cout<<“Input Str0:”<<str0<<endl<<“Input Str1 below:”<<endl;
string str1;
cin>>str1;
cout<<“Input Str1:”<<str1<<endl;

```//process
bool isAnagram = anagram1(str0,str1);
cout<<"Result : "<<isAnagram<<endl;

return 0;```

}

## CCI习题1-3：Remove Duplications in String

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.
Write the test cases for this method.

<

pre>

//
// main.cpp
// CCI.1.3.RemoveDuplicationsInString
//
// Created by Qiu Xiangyu on 12-11-13.
//

# include

using namespace std;

void removeDuplicate(char cstr) {
if (cstr == NULL) {
return;
}
int map = 0;
char * curloc = cstr;
while(
cstr != ‘\0’) {
int hashc = *cstr – ‘a’;
int bit = 1 << hashc;
if (!(map & bit)) {
//no exist char
map = map | bit;
*curloc = *cstr;
++curloc;
}
++cstr;
}
*curloc = ‘\0’;
}

int main(int argc, const char * argv[])
{
// insert code here…
cout << “Input below:\n”;
char cstr[200];
scanf(“%s”,cstr);
cout<<“Input:”<<cstr<<endl;

```//process
removeDuplicate(cstr);
cout<<"Result : "<<cstr<<endl;

return 0;```

}

## CCI习题 1-2：Reverse C String

Write code to reverse a C-Style String. (C-String means that “abcd” is represented as five characters, including the null character.)

<

pre>
//
// main.cpp
// CCI.1.2.ReverseCString
//
// Created by Qiu Xiangyu on 12-11-13.
//

# include

using namespace std;

void reverseCString(char *cstr) {
if (cstr == NULL) {
return;
}
size_t len = strlen(cstr);
for (size_t i = 0; i < len / 2; ++i) {
//swap cstr[i] and cstr[len – 1 -i]
size_t li = len – 1 – i;
cstr[i] = cstr[i] ^ cstr[li];
cstr[li] = cstr[i] ^ cstr[li];
cstr[i] = cstr[i] ^ cstr[li];
}
}

int main(int argc, const char * argv[])
{
// insert code here…
cout << “Input below:\n”;
char cstr[200];
scanf(“%s”,cstr);
cout<<“Input:”<<cstr<<endl;

```//process
reverseCString(cstr);
cout<<"Revert Result : "<<cstr<<endl;

return 0;```

}

## CCI习题1-1：String Contain Unique Char

CCI指《Cracking the Coding Interview》.

1.1
Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

<

pre>

# include

using namespace std;

bool allUnique(string inputstr) {
int map = 0;//32bit
for(int i = 0; i < inputstr.size(); ++i) {
char c = inputstr[i];
int hashc = c – ‘a’;
int bit = 1 << hashc;
if (map & bit) {
return false;
} else {
map = map | bit;
}
}
return true;
}

int main(int argc, const char * argv[])
{
// insert code here…
cout << “Input below:\n”;
string inputstr;
cin>>inputstr;
cout<<“Input:”<<inputstr<<endl;

```//process
bool allunique = allUnique(inputstr);
cout<<"Result : "<<allunique<<endl;

return 0;```

}