实现一棵多叉树
这棵树可以有任意多颗子树 0-n
1
2 3 4
5 6 7 8
输入建立二叉树，输入的格式是每个节点的具体数据和拥有的孩子数目
例如上面的树是这样建成的：
1 3
2 2
5 0
6 0
3 1
7 0
4 1
8 0
1 #include <iostream>
2 #include <vector>
3 #include <queue>
4 using namespace std;
5
6 struct node
7 {
8 int item;
9 vector<node*> children;
10 };
11
12 node* build()
13 {
14 int t, n;
15 cin >> t >> n;
16 node* p = 0;
17 p = new node;
18 p->item = t;
19 for (int i = 0; i != n; ++i)
20 {
21 p->children.push_back(build());
22 }
23 return p;
24 }
25
26 void level(node* root)
27 {
28 if (root != 0)
29 {
30 node* t;
31 queue<node*> q;
32 q.push(root);
33 while (!q.empty())
34 {
35 t = q.front();
36 cout << t->item << ' ';
37 q.pop();
38 for (vector<node*>::size_type i = 0; i != t->children.size(); ++i)
39 {
40 q.push(t->children[i]);
41 }
42 }
43 }
44 }
45
46 int main()
47 {
48 node* root = 0;
49 root = build();
50 level(root);
51 return 0;
52 }
posted @
2011-07-26 16:34 unixfy 阅读(4915) |
评论 (0) |
编辑 收藏一个规划性问题
12个工厂分布在一条东西向高速公路的两侧，工厂距离公路最西端的距离分别是0、4、5、10、12、18、27、30、31、38、39、47.在这12个工厂中选取3个原料供应厂，使得剩余工厂到最近的原料供应厂距离之和最短，问应该选哪三个厂 ？
这是阿里云实习的笔试题
这个类似于电梯调度算法，电梯调度是一个点，这里是三个点。
最直观的做法是枚举所有的情况，P(12, 3)。
其实也就是这样。三个 for 循环，但是这就是一种暴力的解法。
1 #include <iostream>
2 #include <cmath>
3 using namespace std;
4
5 int min3(int a, int b, int c)
6 {
7 a = a < b ? a : b;
8 return a < c ? a : c;
9 }
10
11 int bar(int a[], int n, int x, int y, int z)
12 {
13 int ret = 0;
14 for (int i = 0; i != n; ++i)
15 {
16 ret += min3(abs(a[x] - a[i]), abs(a[y] - a[i]), abs(a[z] - a[i]));
17 }
18 return ret;
19 }
20
21 int foo(int a[], int n, int& p1, int& p2, int& p3)
22 {
23 int ret = 10000;
24 int tmp = 0;
25 for (int i = 0; i != n; ++i)
26 {
27 for (int j = 0; j != n; ++j)
28 {
29 for (int k = 0; k != n; ++k)
30 {
31 tmp = bar(a, n, i, j, k);
32 if (tmp < ret)
33 {
34 ret = tmp;
35 p1 = i;
36 p2 = j;
37 p3 = k;
38 }
39 // cout << i << ' ' << j << ' ' << k << endl;
40 // cout << tmp << endl;
41 }
42 }
43 }
44 return ret;
45 }
46
47 int main()
48 {
49 int a[] = {0, 4, 5, 10, 12, 18, 27, 30, 31, 38, 39, 47};
50 int x, y, z;
51 int d;
52 d = foo(a, sizeof (a) / sizeof (*a), x, y, z);
53 cout << d << endl;
54 cout << x << ' ' << y << ' ' << z << endl;
55 return 0;
56 }
posted @
2011-07-26 11:43 unixfy 阅读(357) |
评论 (0) |
编辑 收藏面试题分析小结-3
33 O(1) 删除单链表中的节点
常规的方法是从 head 遍历到待删除节点 p 的上一个节点 q
q->next = p->next;
delete p;
遍历到 p 的时间复杂度是 O(N)
既然知道了 p ，则就可以 O(1) 得到下一个节点 t ，将 t 的值拷贝到 p 所指的节点，然后删除 t 即可。
t = p->next;
p->data = t->data;
p->next = t->next;
delete t;
这样时间复杂度是 O(1)
要考虑 p 是不是最后一个节点，但是最终不会影响 O(1) 的时间复杂度
void delete(node* p, node* head)
{
if (p == 0 || head == 0)
{
return;
}
if (p->next != 0)
{
node* t = p->next;
p->data = t->data;
p->next = t->next;
delete t;
t = 0;
}
else
{
node * t = head;
while (t->next != p)
{
t = t->next;
}
t->next = 0;
delete p;
p = 0;
}
}
http://www.cppblog.com/jake1036/archive/2011/05/21/146879.html
34 找出数组中唯一出现一次的两个数
如果一个数组中其他数都是出现偶数次，只有一个数出现奇数次，则可以直接对这个数组中的所有元素进行异或运算，最终的结果即是这个出现奇数次的数。
异或运算的特性。
这里是有两个数出现了一次，其他数都出现了两次。
对整个数组进行异或运算，所得到的结果即是这两个数的异或值 a ^ b = c
考虑 c
考虑 c 的某位为 1 的那位，比如考虑最低的那个为 1 的位
根据这个位，把原数组分成两部门，即该位为 1 的集合和为 0 的集合，a 和 b 必然被分开，然后对这两个集合分别做异或运算，即可得到相应的 a 和 b 。
异或运算的特性：
a ^ (全 0) = a
a ^ (全 1) = ~a
a ^ a = 0
偶数个 a 异或 = 0
奇数个 a 异或 = a
http://www.cppblog.com/jake1036/archive/2011/05/21/146881.html
35 找出两个链表的第一个共同节点
这个题目也可以简化为判断两个单链表是否交叉
1.
最直观的解法是两个循环，直接检测，O(M * N)
2.
对每个节点的地址哈希 O(M + N)
3.
遍历两个链表，取得长度，然后再次遍历，先遍历长的那个链表，提前走 t 步，然后共同向后走，检测第一次两个节点地址是否一样，如果一样，则是那个共同节点。O(M + N)
4.
交叉的链表是 Y 型的，将其中一个链表 a 连到另一个链表 b 尾部，从 a 的 head 遍历，如果再次回到了 a 的 head 即可判定 a 和 b 是交叉的。如果想找到交叉节点，则同时从 a 的 head 和 b 的 head 遍历，直到 a 的 head 和 b 的 head 遇到一起时，这时 a 的 head 也就是 b 的 head 即是指向的那个公共节点。
http://www.cppblog.com/jake1036/archive/2011/05/22/146909.html
36 在字符串中删除指定的字符
给定两个字符串，删除第一个字符串中在第二个字符串出现的字符
例如：
"abcefgh", "abcef"
得到：
"gh"
先对第二个字符串，做 hash 记录要删除的字符
然后遍历第一个字符串，根据 hash 表，判断当前字符是否是要删除的那个字符
对第一个字符串的处理，可以利用一个指针和一个已删除的字符数目记录
也可以利用两个指针，分别记录当前遍历的字符和删除后的字符串记录
http://www.cppblog.com/jake1036/archive/2011/05/22/146944.html
http://baike.baidu.com/view/15482.htm
http://zh.wikipedia.org/wiki/ASCII
http://zh.wikipedia.org/wiki/File:ASCII_Code_Chart-Quick_ref_card.jpg
posted @
2011-07-23 22:55 unixfy 阅读(148) |
评论 (0) |
编辑 收藏boost 中的 noncopyable
// boost
class noncopyable
{
protected:
noncopyable() {}
~noncopyable() {}
private:
noncopyable(const noncopyable&);
const noncopyable& operator = (const noncopyable&);
};
class test : public noncopyable
{
};
int main()
{
test a, b;
// test b(a);
// c = a;
}
这是通过继承的方式来实现的 noncopy
也可以通过组合的方式
class noncopyable
{
public:
noncopyable() {}
~noncopyable() {}
private:
noncopyable(const noncopyable&);
const noncopyable& operator = (const noncopyable&);
}
class test
{
private:
noncopyable noncopyable_;
};
int main()
{
test a, c;
// test b(a);
// c = a;
}
http://www.cppblog.com/luke/archive/2009/03/13/76411.html
http://ebenzhang.blogbus.com/tag/noncopyable/
http://hi.baidu.com/jrckkyy/blog/item/e6b241de1645735f95ee37de.html
http://hi.baidu.com/jrckkyy/home
http://blog.csdn.net/alai04/article/details/577798
http://www.boost.org/doc/libs/1_47_0/boost/noncopyable.hpp
posted @
2011-07-23 22:07 unixfy 阅读(441) |
评论 (0) |
编辑 收藏不能被继承的类、不能被拷贝的类、只能定义一个对象的类
不能被继承的类
将构造函数和析构函数定义为私有的，这样派生类在构造基类子对象时就不能调用基类私有的构造函数。
class T
{
private:
T() {}
~T() {}
public:
static T* create()
{
return new T();
}
static T* release(T*& p)
{
delete p;
p = 0;
}
};
见构造函数和析构函数声明为 private ，也限制了本身的对象创建。利用静态成员函数来创建创建和释放对象。
这种方式只能在堆上创建对象。
如果还想在栈上创建对象，利用友元机制，声明友元类，可以调用友元类的 private 构造函数和析构函数，但是友元关系不能被继承。其中一个友元类 virtual 继承自含有 private 构造函数和析构函数的被友元类。
不能拷贝的类
拷贝意味着拷贝构造函数和复制运算符，将拷贝构造函数和赋值运算符声明为 protected 的，并且不需要实现。
class T
{
protected:
T(const T& rhs);
T& operator = (const T& rhs);
};
只能声明一个对象的类
即是单例模式
将构造函数声明为 private 以防在栈上随意定义对象
定义一个 static 的本类型指针，只是指向唯一的一个对象
定义一个 static 成员函数，用于获得指向唯一的那个对象的指针
class T
{
private:
T() {}
~T() {}
static T* pt;
public:
static T* getInstance()
{
if (pt == 0)
{
pt = new T();
}
return pt;
}
};
T* T::pt = 0;
http://www.cppblog.com/jake1036/archive/2011/05/21/146870.html
http://blog.csdn.net/xkyx_cn/article/details/2245038
http://www.cublog.cn/u3/112083/showart_2237163.html
http://blog.csdn.net/ericming200409/article/details/5975874
http://blog.csdn.net/wulibin136/article/details/6347215
http://www.cppblog.com/unixfy/archive/2011/04/29/145340.html
posted @
2011-07-23 21:48 unixfy 阅读(736) |
评论 (0) |
编辑 收藏31 随机生成只输出一次的 1-100 的 100 个元素
随机生成下标，将这个下标生成的值与 end 交换，然后 --end
继续在 0-end 范围内随机生成下标，然后将这个下标与 end 对应的元素交换，--end
直到生成完 100 个元素
http://www.cppblog.com/jake1036/archive/2011/05/20/146818.html
31 倒序输出链表中的元素
采用递归的策略
void print(node* p)
{
if (p != 0)
{
print(p->next);
cout << p->item << ' ';
}
}
扩展：在函数体内不声明变量，求字符串的长度
int length(const char* s)
{
if (*s != '\0')
{
return 1 + length(++s);
}
else
{
return 0;
}
}
#include <iostream>
using namespace std;
int length(const char* s)
{
if (*s != '\0')
{
return length(++s) + 1;
}
else
{
return 0;
}
}
int main()
{
char s[100];
while (cin >> s)
{
cout << length(s) << endl;
cout << strlen(s) << endl;
}
}
http://www.cppblog.com/jake1036/archive/2011/05/21/146869.html
posted @
2011-07-23 21:27 unixfy 阅读(95) |
评论 (0) |
编辑 收藏几个面试题的小分析
面试题 100 - 20 最长公共子串
求两个字符串的最长公共子串，不需要连续
根据当前的两个字符 a[i] b[j]
m[i][j]
= max(m[i - 1][j], m[i][j - 1], m[i - 1][j - 1] + k)
if (a[i] = b[j]) k = 1
else k = 0
m[LenA][LenB]
记录路径，根据 max 去哪个值，记录 m 矩阵的走势，是向右、向下还是向右下
求路径的时候，利用辅助矩阵 t[][] 记录的走势状态，递归求出具体的最长公共子串。
面试题 100 - 30 异常安全的复制
一般函数指针成员的类对象，对 operator = 进行重载
在重载的函数体内，有可能造成重新分配内存失败，造成了异常，原来的内存空间已经被释放掉了，无法恢复之前的状态。例如：
T& T::operator = (const T& rhs)
{
if (this != &rhs)
{
delete [] pdata;
pdata = new Type[];
copy(...);
}
return *this;
}
这种情况下，可能 new 失败造成异常，但是 pdate 指向的内存已经被释放。
为了异常安全
采用临时多一份的策略
第一种方法是，使用一个临时指针，给这个指针分配块内存，然后删除原来的内存，将这个临时指针赋值给本对象中的指针成员。
T& T::operator = (const T& rhs)
{
if (this != &rhs)
{
Type * temp = new Type[];
copy(...);
delete [] pdata;
pdata = temp;
}
return *this;
}
第二种方法也是用临时多一份的策略，使用一个临时本类型的对象，利用拷贝构造函数，然后交换临时对象与本对象。
T& T::operator = (const T& rhs)
{
if (this != &rhs)
{
T temp(rhs);
swap(*this, temp);
}
return *this;
}
这里交换的是 *this 和 temp 的指针的值，而不是指针成员指向的内存内容，也就是说是做的对象的位交换。
这种有了一个临时对象，可以不用做自赋值的检测。即便是自赋值，也不会造成原数据的丢失。可以写成：
T& T::operator = (const T& rhs)
{
T temp(rhs);
swap(*this, temp);
return *this;
}
上面的第一种做法，也可以不做自赋值检测。
最上面的非异常安全的做法是
1
0
1
当 0 过后，可能在产生 1 的时候异常，就无法恢复了。
临时多一份的策略是
1
2
1
即便在产生 2 的过程中发生了异常，仍然有一个，所以是异常安全的。
两个发生异常的阶段分别是
0->1
1->2
关键要看异常前的情况，如果异常前就保证有效，则即使发生了异常也没有问题，即是异常安全的。
http://www.cppblog.com/jake1036/archive/2011/05/20/146689.html
http://www.cppblog.com/jake1036/archive/2011/05/20/146816.html
posted @
2011-07-23 21:09 unixfy 阅读(69) |
评论 (0) |
编辑 收藏使数组中的奇数位于偶数之前
从数组两端遍历，检测当前元素的奇偶性，条件允许时交换，直到两个索引交叉。
http://www.cppblog.com/jake1036/archive/2011/05/20/146798.html
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 struct node
7 {
8 int m_;
9 public:
10 node(int i = 0) : m_(i) {};
11 int m() const
12 {
13 return m_;
14 }
15 };
16
17 bool operator < (const node& lhs, const node& rhs)
18 {
19 if (lhs.m() % 2 == 1 && rhs.m() % 2 == 0)
20 {
21 return true;
22 }
23 else if (lhs.m() % 2 == 0 && rhs.m() % 2 == 1)
24 {
25 return false;
26 }
27 else
28 {
29 return lhs.m() < rhs.m();
30 }
31 }
32
33 bool operator == (const node& lhs, const node& rhs)
34 {
35 return lhs.m() == rhs.m();
36 }
37
38 bool operator > (const node& lhs, const node& rhs)
39 {
40 return !(lhs < rhs || lhs == rhs);
41 }
42
43 void foo(int a[], int n)
44 {
45 int left = 0, right = n - 1;
46 while (left < right)
47 {
48 while (left < right && (a[left] & 0x01) == 1)
49 {
50 ++left;
51 }
52 while (right > left && (a[right] & 0x01) == 0)
53 {
54 --right;
55 }
56 if (left < right)
57 {
58 a[left] ^= a[right];
59 a[right] ^= a[left];
60 a[left] ^= a[right];
61 }
62 }
63 }
64
65 int main()
66 {
67 int a[] = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};
68 vector<node> test;
69 for (int i = 0; i != sizeof (a) / sizeof (*a); ++i)
70 {
71 test.push_back(node(a[i]));
72 }
73 foo(a, sizeof (a) / sizeof (*a));
74 for (int i = 0; i != sizeof (a) / sizeof (*a); ++i)
75 {
76 cout << a[i] << ' ';
77 }
78 cout << endl;
79
80 sort(test.begin(), test.end());
81 for (vector<node>::size_type i = 0; i != test.size(); ++i)
82 {
83 cout << test[i].m() << ' ';
84 }
85 cout << endl;
86
87 sort(test.begin(), test.end(), greater<node>());
88 for (vector<node>::size_type i = 0; i != test.size(); ++i)
89 {
90 cout << test[i].m() << ' ';
91 }
92 cout << endl;
93 }
posted @
2011-07-23 20:20 unixfy 阅读(212) |
评论 (0) |
编辑 收藏求给定值的连续序列
例如给定值是 15
则有：
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
求解
设定一个区间 [left, right]
计算 left 到 right 之间的所有和 sum
若 sum 小于给定值 n 则 right 右移
若 sum 大于给定值 n 则 left 右移
若 sum 等于给定值 n 则 left 右移
[left, right] 的初始是 [1, 1]
另一个问题
求解一个集合中两个元素之和等于给定值
先对这个集合进行排序，然后从两端遍历，若和大于给定值则右边的标记左移，若和小于给定值则左边的值右移。
http://www.cppblog.com/jake1036/archive/2011/05/19/146745.html
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 int bar(int left, int right)
6 {
7 return (left + right) * (right - left + 1) / 2;
8 }
9
10 void foo(vector<vector<int> >& result, int n)
11 {
12 result.clear();
13 int left = 1, right = 1;
14 int t;
15 while (left <= n / 2)
16 {
17 t = bar(left, right);
18 if (t < n)
19 {
20 ++right;
21 }
22 else if (t > n)
23 {
24 ++left;
25 }
26 else
27 {
28 vector<int> v;
29 for (int i = left; i <= right; ++i)
30 {
31 v.push_back(i);
32 }
33 result.push_back(v);
34 ++left;
35 }
36 }
37 }
38
39 int main()
40 {
41 int n;
42 vector<vector<int> > result;
43 while (cin >> n)
44 {
45 foo(result, n);
46 for (vector<vector<int> >::size_type i = 0; i != result.size(); ++i)
47 {
48 for (vector<int>::size_type j = 0; j != result[i].size(); ++j)
49 {
50 cout << result[i][j] << ' ';
51 }
52 cout << endl;
53 }
54 }
55 return 0;
56 }
posted @
2011-07-23 16:23 unixfy 阅读(90) |
评论 (0) |
编辑 收藏判断栈的 push 和 pop 序列是否正确
有两个队列分别是 push 队列和 pop 队列
判断其入栈出栈序列是否正确
利用一个辅助栈 tmp
扫描 pop 队列
对 pop 队列的首元素进行检测，首先检测 tmp 栈顶元素是否与 pop 队首元素一样，如果一样则将则将 tmp 栈顶元素删除。
如果不一样，则遍历整个 push 队列，将不一样的压入到 tmp 中，直到遇到一样的。
http://www.cppblog.com/jake1036/archive/2011/05/19/146731.html
1 #include <iostream>
2 #include <queue>
3 #include <stack>
4 using namespace std;
5
6 bool foo(queue<int>& in, queue<int>& out)
7 {
8 stack<int> tmp;
9 int t;
10 while (!out.empty())
11 {
12 t = out.front();
13 out.pop();
14 if (!tmp.empty() && t == tmp.top())
15 {
16 cout << "出栈：" << tmp.top() << endl;
17 tmp.pop();
18 }
19 else
20 {
21 int find = false;
22 while (!in.empty())
23 {
24 if (t != in.front())
25 {
26 cout << "入栈：" << in.front() << endl;
27 tmp.push(in.front());
28 in.pop();
29 }
30 else
31 {
32 cout << "入栈：" << in.front() << endl;
33 tmp.push(in.front());
34 in.pop();
35 cout << "出栈：" << tmp.top() << endl;
36 tmp.pop();
37 find = true;
38 break;
39 }
40 }
41 if (!find)
42 {
43 return false;
44 }
45 }
46 }
47 return true;
48 }
49
50 int main()
51 {
52 queue<int> in, out;
53 int t, n;
54 while (cin >> n)
55 {
56 for (int i = 0; i != n; ++i)
57 {
58 cin >> t;
59 in.push(t);
60 }
61 for (int i = 0; i != n; ++i)
62 {
63 cin >> t;
64 out.push(t);
65 }
66 cout << foo(in ,out) << endl;
67 }
68 }
posted @
2011-07-23 13:14 unixfy 阅读(228) |
评论 (0) |
编辑 收藏