Difference between revisions of "Algorithm Problems"
From Hawk Wiki
(→Inverse Array) |
|||
| Line 75: | Line 75: | ||
cout << a[i] ; | cout << a[i] ; | ||
} | } | ||
| + | </pre> | ||
| + | ==Find duplicate numbers in array== | ||
| + | <pre> | ||
| + | <?php | ||
| + | /* | ||
| + | Find duplicate number in array | ||
| + | */ | ||
| + | //construct $b[n]=n | ||
| + | $b=array(); | ||
| + | $duplicateArr=array(); | ||
| + | $a=array("1","3","4","1","5","2","8","3","2244","1"); | ||
| + | for($i=0;$i<sizeof($a);$i++){ | ||
| + | if(isset($b[$a[$i]])) | ||
| + | array_push($duplicateArr,$a[$i]); | ||
| + | else | ||
| + | $b[$a[$i]]=$a[$i]; | ||
| + | } | ||
| + | var_dump($duplicateArr); | ||
| + | ?> | ||
</pre> | </pre> | ||
Revision as of 23:26, 22 February 2012
Contents
Binary Tree
Binary search
def search_binary_tree(node, key):
if node is None:
return None # key not found
if key < node.key:
return search_binary_tree(node.leftChild, key)
elif key > node.key:
return search_binary_tree(node.rightChild, key)
else: # key is equal to node key
return node.value # found key
Binary tree insert
/* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */
void InsertNode(Node* &treeNode, Node *newNode)
{
if (treeNode == NULL)
treeNode = newNode;
else if (newNode->key < treeNode->key)
InsertNode(treeNode->left, newNode);
else
InsertNode(treeNode->right, newNode);
}
Binary tree depth
///////////////////////////////////////////////////////////////////////
// Get depth of a binary tree
// Input: pTreeNode - the head of a binary tree
// Output: the depth of a binary tree
///////////////////////////////////////////////////////////////////////
int TreeDepth(SBinaryTreeNode *pTreeNode)
{
// the depth of a empty tree is 0
if(!pTreeNode)
return 0;
// the depth of left sub-tree
int nLeft = TreeDepth(pTreeNode->m_pLeft);
// the depth of right sub-tree
int nRight = TreeDepth(pTreeNode->m_pRight);
// depth is the binary tree
return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
Print linklist inversed
///////////////////////////////////////////////////////////////////////
// Print a list from end to beginning
// Input: pListHead - the head of list
///////////////////////////////////////////////////////////////////////
void PrintListReversely(ListNode* pListHead)
{
if(pListHead != NULL)
{
// Print the next node first
if (pListHead->m_pNext != NULL)
{
PrintListReversely(pListHead->m_pNext);
}
// Print this node
printf("%d", pListHead->m_nKey);
}
}
Inverse Array
for (int i = 0; i < b; i=i++){
char temp1 = a[i];
a[i] = a[(b-1)-i];
a[(b-1)-i] = temp1;
cout << a[i] ;
}
Find duplicate numbers in array
<?php
/*
Find duplicate number in array
*/
//construct $b[n]=n
$b=array();
$duplicateArr=array();
$a=array("1","3","4","1","5","2","8","3","2244","1");
for($i=0;$i<sizeof($a);$i++){
if(isset($b[$a[$i]]))
array_push($duplicateArr,$a[$i]);
else
$b[$a[$i]]=$a[$i];
}
var_dump($duplicateArr);
?>
