ITeye博客

渔人

fishlife · 共 5 篇文章

二叉查找树

基本的二叉查找树代码: #include <iostream> using namespace std; struct node{ int data; struct node *parent; struct node *lchild; struct node *rchild; }; //输出 void display(struct node *p) { if (p) { display(p->lchild); cout<<p->data<<" "; display(p->rchild); } return; } //最小值节点 struct node *min(struct node *ro…

2010-05-10 12:44 · 算法 · 评论(0)

排序算法总结

首先是来自WIKI上的一些分类总结: 穩定的 泡沫排序 (bubble sort) — O( n 2 ) 鸡尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O( n 2 ) 插入排序 (insertion sort)— O( n 2 ) 桶排序 (bucket sort)— O( n ); 需要 O( k ) 額外空間 计数排序 (counting sort) — O( n + k ); 需要 O( n + k ) 額外空間 合併排序 (merge sort)— O( n log n ); 需要 O( n ) 額外空間 原地 合併排序 — O( n 2 ) 二叉排序树 排序 …

2010-04-27 21:52 · 算法 · 评论(0)

uva 10131 Is Bigger Smarter?

由最长递增子序列引申而来,先按体重进行排序。 #include<iostream> #include<stdlib.h> using namespace std; struct node{ int index; int w; int iq; }; struct node ele[1001]; int length; int dp[1001], pre[1001]; int cmp(const void *a, const void *b) { struct node *c = (node *)a; struct node *d = (node *)b; if(c->w != d->w) re…

2010-04-13 19:09 · ACM · 评论(0)

《Programming Challenges》Sulutions

Dynamic Programming 10131 - Is Bigger Smarter? | Solution 10069 - Distinct Subsequences | Solution 10154 - Weights and Measures | Solution 116 - Unidirectional TSP | Solution 10003 - Cutting Sticks | Solution 10261 - Ferry Loading | Solution 10271 - Chopsticks | Solution 10201 - Adventures in Movin…

2010-04-13 19:06 · 算法 · 评论(0)

《程序员面试攻略》题目总结

一. 链表 1. 链表中的倒数第m个元素 给定一个单向链表,请设计一个既节省时间又节省空间的算法来找出该链表中的倒数第m个元素。实现这个算法。 “倒数第m个元素”是这样规定的:当m=0时,链表的最后一个元素(尾元素)将被返回。 前进m步后启动一个“后指针” 2. 空链表和循环链表 给定一个链表,它可能是一个以"NULL"结尾的非循环链表,也可能是一个循环结构结尾的循环链表。写一个函数来判断该链表是一个循环链表还是一个非循环 链表,该函数不得对链表本身做任何修改。 用两个指针,一快一慢,如果是循环链表,快的指针迟早会 超过慢指针,时间复杂度:O(n),最多也是3n int DetermineT…

2010-04-11 20:20 · 找工之路 · 评论(0)