array series

从一个 Integer Array 中去掉重复元素 void removeDup(vector &seq) { if(seq.size() == 0 || seq.size() == 1) return; map cnt; int src, dst; src=dst=0 for( ; src

binary tree

find the nth largest number in a binary search tree input: bst tree root, holder of result output: error code int bstNthLargest(node *root, int *result, int *n) { if(!root) return -1; if(root->right) bstNthLargest(root->right, result, n); if(*n==0) return 0; if(*n==1) { *result = root->v; *n = 0; return 0; } *n--; if(root->left) bstNthLargest(root->left, result, n); return -1; } find binary tree height int getTreeHeight(node *root) { if(!root) return 0; if(!root->left && !root->right) return 1; int leftH = getTreeHight(root->left); int rightH = getTreeHight(root->right); return max(leftH, rightH)+1; }

linked list series

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. void removeDuplicated(node* ll) { if(!ll) return; if(!ll->next) return; node* ptr1, ptr2; ptr1 = ll; ptr2 = ptr1->next; while(1) { if(ptr1->v == ptr2->v) { while(ptr1->v == ptr2->v) { node* ptr3 = ptr2->next; llDeleteNode(ll,ptr3); ptr2 = ptr3; if(!ptr2) break; } llDeleteNode(ll, ptr1); if(!ptr2) return; if(!ptr2->next) return; ptr1 = ptr2; ptr2 = ptr2->next; } } } Given a singly linked list swap the adjacent nodes in the list 1-4-5-6-3 4-1-6-5-3 void llReverse2(node** ll) { node *p1, *p2; p1 = *ll; if(!p1) return; if(!p1->next) return; *ll = p1->next; p2 = NULL; while(p1 && p1->next) { node *p3, *p4; p3 = p1; p4 = p1->next; p1 = p4->next; if(p2) p2->next = p4; p4->next = p3; p3->next = p1; p2 = p3; } }

Linked list

////Node class in C++
#include <iostream>;

class Node {
public:
double value;
Node* next;

public:
Node(){ value = 0; next = NULL; }

Node(double x){ value = x; next = NULL;}
};

////Single linked list in C++

#include "Node.h";
#include <stdio.h>;
using namespace std;

class SingleListedList{
public:
Node* head;
SingleListedList(){ head = NULL; }
SingleListedList(Node* node){ node = head; }

void Insert(int position, Node* newNode);
void InsertBehindFirst(int value, Node* newNode);
void Delete(int position);
void DeleteFirstValue(int value);
private:
void insertNodeBehind(Node* current, Node* newNode);
};

void SingleListedList::Insert(int position, Node* newNode){
//determine if valid paramter
if (position < 1){
cout << "The input parameters are not valid.";
return;
}
if(newNode == NULL){
cout << "The node to be inserted is NULL." << endl;
return;
}

//boundary - beginning
if (head == NULL){
if(position > 1){
cout << "The linked list does not exist and the inserted position is not from the beginning." << endl;
return;
}
else{
head = newNode;
return;
}
}

//boundary case -- head
if(head != NULL && position == 1){
newNode->next = head;
head = newNode;
return;
}

int pos = 1;
Node* current = head;

while ((pos < (position-1)) && current != NULL){
pos++;
current = current -> next;
}

//boudary - terminated
if (current == NULL){
cout << "The linked list is not long enough, and the position is beyond the index." << endl;
return;
}

//happy path
insertNodeBehind(current, newNode);

return;
}

void SingleListedList::InsertBehindFirst(int value, Node* newNode){
//check input parameter
if(newNode == NULL){
cout << "The new node is NULL." << endl;
return;
}
if(head == NULL){
cout << "The linked list does not exist." << endl;
return;
}

if (head->value == value){
insertNodeBehind(head, newNode);
return;
}

Node* current = head;

do{
current = current->next;
} while(current->value != value && current->next != NULL);

if (current->value == value){
insertNodeBehind(current, newNode);
} else {
cout << "The value is not found." << endl;
}

return;
}

void SingleListedList::Delete(int position){
//check condition
//check input variable
if (position < 1){
cout << "Can node delete node with invalid position index." << endl;
return;
}
//check external condition
if(head == NULL) {
cout << "Empty list and no node to delete" << endl;
return;
}

//boundary case
if (position == 1){
head = head -> next;
return;
}

int currPos = 2;
Node* prep = head;
Node* curr = head->next;

//find location
while (currPos != position && curr != NULL){
currPos++;
prep = curr;
curr = curr->next;
}

//delete the node
if (curr != NULL) {
prep->next = curr->next;
} else {
cout << "The position does not exist" << endl;
}

return;
}

void SingleListedList::DeleteFirstValue(int value){
//check condition
if (head == NULL) {
cout << "empty list" << endl;
return;
}

//boundary case - head
if (head->value == value){
head = head->next;
return;
}

//happy path
Node* prep = head;
Node* curr = head->next;

while (curr->value != value && curr->next != NULL){
prep = curr;
curr = curr->next;
}

if (curr->value == value){
prep->next = curr->next;
} else {
cout << "cannot find the node." << endl;
}

return;
}

void SingleListedList::insertNodeBehind(Node* current, Node* newNode){
if(current == NULL){
cout << "The node is invalid, and we cannot insert another node behind." <<endl;
return;
}

Node* temp = current;
current = current -> next;
temp -> next = newNode;
newNode -> next = current;
}

////Linked list test


#include "LinkedList.h";

void printLinkedList(SingleListedList* singleList);
void printRevertLinkedList(Node* node);
void printRevertedLinkedListSimp(Node* node);

void LikedListTest(){
//test Node
Node node1;
double x = 8;
Node* node8 = new Node(x);
node1.next = node8;
cout << "output the nodes in order" << endl;
cout << node1.value << "->" << node1.next->value << endl;

//test Insert in SingleLinkedList
SingleListedList* singleList = new SingleListedList();
Node* newNode = new Node(-1);
//boudary case
singleList->Insert(2, newNode);
//happy path
singleList->head = node8;
for(int i=0;i<5;i++){
newNode = new Node(i);
singleList->Insert(1, newNode);
}
newNode = new Node(5);
singleList->Insert(2,newNode);

    newNode = new Node(9);
singleList->InsertBehindFirst(9, newNode);
singleList->InsertBehindFirst(8, newNode);

//test happy path for insert
printLinkedList(singleList);
printRevertLinkedList(singleList->head);
cout << "end" << endl;
printRevertedLinkedListSimp(singleList->head);
cout << "end" << endl;

//test happy path for delete
singleList->Delete(1);
printLinkedList(singleList);
singleList->DeleteFirstValue(3);
printLinkedList(singleList);
}

void printLinkedList(SingleListedList* singleList){
    Node* current = singleList->head;

if(current == NULL){
cout << "Empty List" << endl;
return;
}

cout << current->value << "->";
while(current->next != NULL){
current = current->next;
cout << current->value << "->";
}
cout << "end" << endl;

return;
}

dynamic programming series

1. Longest Common Sequence (LCS)
code from wikipedia:


#!/usr/bin/env python
def lcs(x,y):
    n = len(x)
    m = len(y)
    table = dict()

    for i in range(n):
        for j in range(m):
            if i == 0 or j == 0:
                table[i,j] = 0
            elif x[i-1] == y[j-1]:
                table[i,j] = table[i-1,j-1] + 1
            else:
                table[i,j] = max(table[i-1,j],table[i,j-1])

    def recon(i,j):
        if i == 0 or j == 0:
            return []
        elif x[i-1] == y[j-1]:
            return recon(i-1,j-1) + [x[i-1]]
        elif table[i-1,j] > table[i,j-1]:
            return recon(i-1,j)
        else:
            return recon(i,j-1)

    return recon(n,m)

if __name__ == "__main__":
    x = ['a','b','c','d','e','f','g']
    y = ['b','c','e','f','g']

    print lcs(x,y)

2. edit distance

int editDistance(vector<char> &x, vector<char> &y)
{
int m[x.size()+1][y.size()+1];

/*
m is for bookkeeping distances of x[0...i] y[0...j]
*/
for(int i=0; i<x.size()+1; i++) m[i][0] = 0;
for(int j=0; j<y.size()+1; j++) m[0][j] = 0;
for(int i=1; i<x.size()+1; i++)
{
for(int j=1; j<y.size()+1; j++)
{
int c1 = m[i-1][j-1] + (x[i-1] == y[i-1] ? 0 : 1);
int c23 = min(m[i-1][j] , m[i][j-1]);
m[i][j] = min(c1,c23);
}
}
return m[x.size()][y.size()]
}

3. coin change problem

#include <cstdio>

#include <vector>

#include <algorithm>

using std::sort;

using std::vector;

const int minCoinChange(const int amount, vector<int> &coins)

{

sort(coins.begin(), coins.end());

int f[amount+1][coins.size()];

for(int i=0; i<(amount+1); i++)

{

for(int j=0; j<coins.size(); j++)

{

if(i == 0) {f[i][j] = 0; continue;}

//if(i == coins[j]) {f[i][j] = 1; continue;}

if(j == 0) {f[i][j] = ((i%coins[j] == 0) ? i/coins[j] : 0); continue;}

if(i < coins[j]) {f[i][j] = f[i][j-1]; continue;}

if((f[i-coins[j]][j]+1)<f[i][j-1]) f[i][j] = f[i-coins[j]][j]+1;

else f[i][j] = f[i][j-1];

}

}

for(int i=0; i<(amount+1); i++)

{

for(int j=0; j<coins.size(); j++)

printf("%d ", f[i][j]);

printf("\n");

}

int min = amount;

int cnt = 1;

for(int j=0; j<coins.size(); j++)

{

if(f[amount][j] < min) min = f[amount][j];

}

for(int j=0; j<coins.size(); j++)

{

if(f[amount][j] == min)

{

printf("solution %d: %d = ", cnt++, amount);

int curCoin=j;

int curAmt=amount;

for(int k=0; k < min; k++)

{

if(curAmt >= coins[curCoin] && f[curAmt][curCoin] == f[curAmt - coins[curCoin]][curCoin] + 1)

{

printf("%d ", coins[curCoin]);

curAmt -= coins[curCoin];

}

else

{

curCoin--;

k--;

}

}

printf("\n");

}

}

printf("coins needed for amount %d is %d\n", amount, min);

return min;

}

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … ,a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3] 

#include <vector>
#include <algorithm>
#include <cstdio>
 
using namespace std;
 
int combinationSum(vector<int> &candidates, int target)
{
        int numCombs;
        int am[candidates.size()+1][target+1];
        for(int i=0; i<=candidates.size(); i++) am[i][0] = 0;
        for(int j=0; j<=target; j++) am[0][j] = 0;
 
        for(int i=1; i<=candidates.size(); i++)
        {
                for(int j=1; j<=target; j++)
                {
                        int cur = candidates[i-1];
                        am[i][j] = am[i-1][j];
                        if(j-cur == 0) am[i][j] = am[i-1][j]+1;
                        if(j-cur > 0)
                        {
                                am[i][j] = am[i-1][j] + am[i][j-cur];                           
                        }
                }
        }
        for(int i=0; i<=candidates.size(); i++)
        {
                for(int j=0; j<=target; j++)
                {
                        printf("%d ", am[i][j]);
                }
                printf("\n");
        }
        return am[candidates.size()][target];
}
 
int main()
{
        int a[] = {2,3,6,7};
        vector<int> candidates(a, a+sizeof(int));
        int allCombs = combinationSum(candidates, 7);
        printf("%d\n", allCombs);
        return 0;
}

misc

//4.linkedlist有无环 （fast/slow runner）

typedef struct Node{
int value;
struct Node* next;
}node;

bool hasLoop(node* ll)
{
node *fast, *slow;
fast = slow = ll;
bool isLoop=false;
while(fast!=NULL)
{
if(fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
if(fast == slow) return true;
}

return isLoop;
}

node * mToLast(node * ll, int m)
{
node * fast, *slow;
fast = slow = ll
for(int i=0; i<m; i++)
{
if(fast == NULL) return NULL;
fast = fast->next;
}
while(fast != NULL)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}

node* mToLastBST(node *root, int m, int *cnt)
{
node *tmp;
if(!root) return NULL;
if(root->right)
{
tmp=mToLastBST(root->right, m, cnt);

}
if(*cnt == m) return tmp;
else *cnt +=1;

if(*cnt == m) return root;
if(root->left)
{
tmp=mToLastBST(root->left, m, cnt);
}
if(*cnt == m) return tmp;
else return NULL;
}

void createList(node **head)
{
*head = NULL;
return ;
}

void deleteList(node **head)
{
node* ptr1, *ptr2;
ptr1 = *head;
while(ptr1)
{
ptr2 = ptr1->next;
free(ptr1);
ptr1 = ptr2;
}
return;
}

void listDeleteNode(node **head, node * toDel)
{
node *ptr, *tmp;
//if it is head
if(*head == toDel)
{
head = *head->next;
free(toDel);
return;
}
ptr = *head;
while(ptr->next != toDel && ptr->next != NULL)
{
ptr = ptr->next;
}
if(ptr->next == toDel)
{
ptr->next = toDel->next;
free(toDel);
}
return;
}

//两个字符串，求出unique characters，即只出现在一个string中的char
//（array[26]，用0-3标记）
vector<char> uniqueChars(char* a, char* b)
{
int charCnt[26];
for(int i=0; i<26; i++) charCnt[i] = 0;

char *tmp;
tmp = a;
while(tmp!='\0')
{
if(charCnt[*tmp-'a'] == 0) charCnt[*tmp-'a'] = 1;
tmp++;
}
//find unique chars
tmp = b;
while(tmp!='\0')
{
if(charCnt[*tmp-'a'] == 0) charCnt[*tmp-'a'] = 2;
if(charCnt[*tmp-'a'] == 1) charCnt[*tmp-'a'] = 3;
tmp++;
}
vector<char> result = new vector<char>;
for(int i=0; i<26; i++)
{
if(charCnt[i] == 1 || charCnt[i] == 2) result.push_back((char)(i+(int)'a'));
}
return result;
}

/*tree mirror
root
l r
ll lr rl rr

root
r l
rr rl rl ll
*/

void treeMirror(node * root)
{


if(root->left) treeMirror(root->left);
if(root->right) treeMirror(root->right);

swap(root->left, root->right);
return;

}


int occurrance(vector<int> & seq, int n)
{
//assuming n does exist in seq
//find the beginning where seq[c]==n
int begin, end;
int a, b, c;
a = 0;
b = seq.size()-1;
c = (a+b)/2;
while(a<b)
{
if(n<seq[c] || (n==seq[c] && n==seq[c-1])) {b=c-1;}
else if(n>seq[c]) {a=c+1;}
else break;
}
begin = c;

//find the end where seq[c]==n
a = 0;
b = seq.size()-1;
c = (a+b)/2;
while(a<b)
{
if(n<seq[c]) {b=c-1;}
else if(n>seq[c] || (n==seq[c] && n==seq[c+1])) {a=c+1;}
else break;
}
end = c;
return end-begin+1;
}

直方图系列