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.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#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.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#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);
    list adjacentNodes(GraphNode *node);
    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;
            list adjacents = adjacentNodes(curNode);
            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,二叉树的基本算法

这里我把题目理解为,任意两个叶子节点(左右子树都空)的深度不超过1.
那就计算一下一棵树的叶子节点中最大的深度和最小的深度,两者不超过1即可。

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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

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 *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);
breadthfirst(root, printNode);
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

其实是冒泡排序,两个stack来回倒腾。
代码展示的是比较直观的算法,对st排序,用另一个栈buffer作为辅助空间,那么:

1.逐个从st中pop元素,先pop到一个临时变量,如果pop出来的元素比临时变量小,则直接进入buffer,否则,把临时变量顶入buffer,st新pop到临时变量。
最后把临时变量push进buffer。
2.将buffer中的元素全部倒回st
3.重复1,2两步,直到1中第一种情况不出现为止。

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

此外,想到一个O(nlogn)的方法,就是,既然要用到额外最多s.size()的空间,还不如建一个最大值堆,把从stackpop出来的内容放到堆里面,然后将最大值逐个push回去。O(n logn),比参考答案快。



题目
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.
注:是允许用额外的Stack作为辅助空间的。



Code

<

pre>

//
// main.cpp
// CCI.3.6.Sort a Stack
//
// Created by Qiu Xiangyu on 12-11-20.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

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

用两个stack来模拟queue。
一个叫做instack,一个叫做outstack。
当push的时候,将所有的item导入instack,然后push into instack。
当pop的时候,将所有的item导入outstack,然后outstack.pop()。
这样就可以先进先出了。



题目
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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

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

这是一个经典问题,经典解法。要将n个盘子从stack0,移动到stack2,只需要做以下三步:
1.将n-1个盘子,从0移动到1,将stack1用作临时stack;
2.将最下面的第n个盘子,从0移动到2;
3.将刚才放到临时stack1的n-1个盘子,移动到stack2。

这是递归的办法,也可以将这个递归展开,只需要多用一个stack记录程序的状态。



题目
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.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#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

就用一个vector来装所有的stack。
遇到push操作,先查看最后一个stack有没有装满。没有的话直接push进该栈即可;否则新建一个stack,push进去然后将这个栈加入vector。
遇到pop操作,将最后一个stack进行pop操作,然后如果该stack空了的话,从vector移除该栈。
遇到top操作,返回最后一个stack的top即可。
遇到popAt操作,和pop类似,完了之后查看一下栈是否为空,如果空了的话,就将该栈从vector移除。



题目
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).
FOLLOW UP
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.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#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

开始想的只需要track每个push进来的条目,就可以在O(1)返回最小元素了。push()没问题,但是pop()的时候就遇到问题了,需要知道pop了这个元素之后的下一个最小的元素是谁。。。

于是就在每一个stackNode上设置一个pointer来track当这个stackNode在最顶端的时候,此时的最小栈位置。这样就可以pop(),push(),min()都是O(1)了。



题目
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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

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

一个简单的办法是把array均分成三段,每段用作一个stack;
更灵活的方法是把这个array当链表用。每个节点放一个value和一个pointer,每个pointer指向栈下一位。



题目
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.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#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

建一个hash来做,从前往后扫描,遇到重复的输出就可以了。(findLoop)
最后有c++中map的简单实用例子。



另外cci上写了一个更有意思的算法,就是两个指针在链表上跑,一个快一个慢,慢的跑一步,快的跑两步。
当他们相遇的时候,让快的那个到链表开头,然后两个指针以相等的速度(一比一),继续跑,再次相遇的时候就是loop的开始点。

为什么?
假设有一个n米长的环形跑道,两个人一快一慢(2:1)从同一个起点开跑。下次相遇在哪儿?起点,而且是快的跑了两圈,慢的一圈。
进一步,如果快的那个先跑了k米呢?那他们应该相遇在距起点k米的位置。因为Sl = t, Sh = 2t + k,而令Sh = Sl + pn,可以得到t = pn – k。也就是他们总会在这个位置相遇。
所以此时让快的那个回到起点,(起点正好距循环开始k米),下次相遇,就是循环开始点。
这个想法很巧(findLoopEx)



题目
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;
while (pHead) {
if (exmap.find(pHead) != exmap.end()) {
return pHead;
}
exmap[pHead] = true;
pHead = pHead->next;
}
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
pRunner = pHead;
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);
printList(phead);
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-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; …
if (!(ppHead)) {
return;
}
Node *pRunner = (
ppHead)->next;
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);
printList(phead);
cout<<“process…”<<endl;
RemoveMiddle(&phead);
printList(phead);
cout<<“done”<<endl;
return 0;
}

CCI习题2-2:nTh From the last

画一个链表出来,实际看看就知道怎么写了。
用一个pointer pRun在前面从pHead先跑n个位置。(如果中途为NULL,说明输入的数大于了链表长度)
然后用另一个pointer pCur从pHead开始,和pRun同步往后跑,直到pRun为NULL,这个时候返回pCur就可以了。



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



代码,只贴主要部分,用到的其它辅助函数和Node结构参见2-1

<

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);
printList(phead);
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

如果可用缓存的话,可以建一个hashtable,然后track每一个值有没有出现过;
否则的话,只能O(n2)去跑了(见下面代码)



Remove Duplicates
Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

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);
}
return phead;
}
void printList(Node *phead) {
cout<<“List : “;
while (phead) {
cout<value;
if (phead->next) {
cout<<“,”;
}
phead = phead->next;
}
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);
printList(phead);
cout<<“process…”<<endl;
removeDuplicate(phead);
printList(phead);
cout<<“done”<<endl;
return 0;
}

CCI习题1-8:Is Rotation

先判断长度是否相等;
然后将第一个字符串s0和自己连接变成s00,调用isSubstring,判断s1是否是s00的一个子串就可以了。



题目
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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

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-5:Replace Space

用gets可以输入带空格的字符串,遇到enter结束。

第一遍扫描获得输入字符串的长度len和其中空格的个数spaceCount。那么输出字符串长度应该是len + 2 * spaceCount
第二遍扫描将输入字符串中非空格字符直接复制到输入字符串中,空格替换成”%20″



题目
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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

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

第一个方法直接将输入字符串排序,然后比较。
时间复杂度是O(nlogn),空间是O(1)

第二个方法是hash,统计每个字符出现的个数。
时间复杂度是O(n),空间O(n)



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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

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

直接从头到尾扫描,用一个int来做hash表。
代码默认输入字符在’a’ – ‘z’之间,如果超出的话用作hash表的int扩展一下就行了,算法本身不变。



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.
FOLLOW UP
Write the test cases for this method.



代码

<

pre>

//
// main.cpp
// CCI.1.3.RemoveDuplicationsInString
//
// Created by Qiu Xiangyu on 12-11-13.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

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

从0到len / 2 – 1,交换cstr[i] 和 cstr[len – 1 – i]就可以了。
交换两个值用了一个trick,就是三次异或。



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.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

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》.



用一个int做为hash表,记录每个单词是否已经存在。从头到尾扫描一下string的每一个字符就可以了。
时间复杂度O(n)
空间复杂度O(1)



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;

}