實(shí)現(xiàn)一棵多叉樹
這棵樹可以有任意多顆子樹 0-n
1
2 3 4
5 6 7 8
輸入建立二叉樹，輸入的格式是每個(gè)節(jié)點(diǎn)的具體數(shù)據(jù)和擁有的孩子數(shù)目
例如上面的樹是這樣建成的：
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 閱讀(4986) |
評(píng)論 (0) |
編輯 收藏一個(gè)規(guī)劃性問題
12個(gè)工廠分布在一條東西向高速公路的兩側(cè)，工廠距離公路最西端的距離分別是0、4、5、10、12、18、27、30、31、38、39、47.在這12個(gè)工廠中選取3個(gè)原料供應(yīng)廠，使得剩余工廠到最近的原料供應(yīng)廠距離之和最短，問應(yīng)該選哪三個(gè)廠 ？
這是阿里云實(shí)習(xí)的筆試題
這個(gè)類似于電梯調(diào)度算法，電梯調(diào)度是一個(gè)點(diǎn)，這里是三個(gè)點(diǎn)。
最直觀的做法是枚舉所有的情況，P(12, 3)。
其實(shí)也就是這樣。三個(gè) for 循環(huán)，但是這就是一種暴力的解法。
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 }
面試題分析小結(jié)-3
33 O(1) 刪除單鏈表中的節(jié)點(diǎn)
常規(guī)的方法是從 head 遍歷到待刪除節(jié)點(diǎn) p 的上一個(gè)節(jié)點(diǎn) q
q->next = p->next;
delete p;
遍歷到 p 的時(shí)間復(fù)雜度是 O(N)
既然知道了 p ，則就可以 O(1) 得到下一個(gè)節(jié)點(diǎn) t ，將 t 的值拷貝到 p 所指的節(jié)點(diǎn)，然后刪除 t 即可。
t = p->next;
p->data = t->data;
p->next = t->next;
delete t;
這樣時(shí)間復(fù)雜度是 O(1)
要考慮 p 是不是最后一個(gè)節(jié)點(diǎn)，但是最終不會(huì)影響 O(1) 的時(shí)間復(fù)雜度
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.shnenglu.com/jake1036/archive/2011/05/21/146879.html
34 找出數(shù)組中唯一出現(xiàn)一次的兩個(gè)數(shù)
如果一個(gè)數(shù)組中其他數(shù)都是出現(xiàn)偶數(shù)次，只有一個(gè)數(shù)出現(xiàn)奇數(shù)次，則可以直接對(duì)這個(gè)數(shù)組中的所有元素進(jìn)行異或運(yùn)算，最終的結(jié)果即是這個(gè)出現(xiàn)奇數(shù)次的數(shù)。
異或運(yùn)算的特性。
這里是有兩個(gè)數(shù)出現(xiàn)了一次，其他數(shù)都出現(xiàn)了兩次。
對(duì)整個(gè)數(shù)組進(jìn)行異或運(yùn)算，所得到的結(jié)果即是這兩個(gè)數(shù)的異或值 a ^ b = c
考慮 c
考慮 c 的某位為 1 的那位，比如考慮最低的那個(gè)為 1 的位
根據(jù)這個(gè)位，把原數(shù)組分成兩部門，即該位為 1 的集合和為 0 的集合，a 和 b 必然被分開，然后對(duì)這兩個(gè)集合分別做異或運(yùn)算，即可得到相應(yīng)的 a 和 b 。
異或運(yùn)算的特性：
a ^ (全 0) = a
a ^ (全 1) = ~a
a ^ a = 0
偶數(shù)個(gè) a 異或 = 0
奇數(shù)個(gè) a 異或 = a
http://www.shnenglu.com/jake1036/archive/2011/05/21/146881.html
35 找出兩個(gè)鏈表的第一個(gè)共同節(jié)點(diǎn)
這個(gè)題目也可以簡化為判斷兩個(gè)單鏈表是否交叉
1.
最直觀的解法是兩個(gè)循環(huán)，直接檢測(cè)，O(M * N)
2.
對(duì)每個(gè)節(jié)點(diǎn)的地址哈希 O(M + N)
3.
遍歷兩個(gè)鏈表，取得長度，然后再次遍歷，先遍歷長的那個(gè)鏈表，提前走 t 步，然后共同向后走，檢測(cè)第一次兩個(gè)節(jié)點(diǎn)地址是否一樣，如果一樣，則是那個(gè)共同節(jié)點(diǎn)。O(M + N)
4.
交叉的鏈表是 Y 型的，將其中一個(gè)鏈表 a 連到另一個(gè)鏈表 b 尾部，從 a 的 head 遍歷，如果再次回到了 a 的 head 即可判定 a 和 b 是交叉的。如果想找到交叉節(jié)點(diǎn)，則同時(shí)從 a 的 head 和 b 的 head 遍歷，直到 a 的 head 和 b 的 head 遇到一起時(shí)，這時(shí) a 的 head 也就是 b 的 head 即是指向的那個(gè)公共節(jié)點(diǎn)。
http://www.shnenglu.com/jake1036/archive/2011/05/22/146909.html
36 在字符串中刪除指定的字符
給定兩個(gè)字符串，刪除第一個(gè)字符串中在第二個(gè)字符串出現(xiàn)的字符
例如：
"abcefgh", "abcef"
得到：
"gh"
先對(duì)第二個(gè)字符串，做 hash 記錄要?jiǎng)h除的字符
然后遍歷第一個(gè)字符串，根據(jù) hash 表，判斷當(dāng)前字符是否是要?jiǎng)h除的那個(gè)字符
對(duì)第一個(gè)字符串的處理，可以利用一個(gè)指針和一個(gè)已刪除的字符數(shù)目記錄
也可以利用兩個(gè)指針，分別記錄當(dāng)前遍歷的字符和刪除后的字符串記錄
http://www.shnenglu.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
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;
}
這是通過繼承的方式來實(shí)現(xiàn)的 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.shnenglu.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
不能被繼承的類、不能被拷貝的類、只能定義一個(gè)對(duì)象的類
不能被繼承的類
將構(gòu)造函數(shù)和析構(gòu)函數(shù)定義為私有的，這樣派生類在構(gòu)造基類子對(duì)象時(shí)就不能調(diào)用基類私有的構(gòu)造函數(shù)。
class T
{
private:
T() {}
~T() {}
public:
static T* create()
{
return new T();
}
static T* release(T*& p)
{
delete p;
p = 0;
}
};
見構(gòu)造函數(shù)和析構(gòu)函數(shù)聲明為 private ，也限制了本身的對(duì)象創(chuàng)建。利用靜態(tài)成員函數(shù)來創(chuàng)建創(chuàng)建和釋放對(duì)象。
這種方式只能在堆上創(chuàng)建對(duì)象。
如果還想在棧上創(chuàng)建對(duì)象，利用友元機(jī)制，聲明友元類，可以調(diào)用友元類的 private 構(gòu)造函數(shù)和析構(gòu)函數(shù)，但是友元關(guān)系不能被繼承。其中一個(gè)友元類 virtual 繼承自含有 private 構(gòu)造函數(shù)和析構(gòu)函數(shù)的被友元類。
不能拷貝的類
拷貝意味著拷貝構(gòu)造函數(shù)和復(fù)制運(yùn)算符，將拷貝構(gòu)造函數(shù)和賦值運(yùn)算符聲明為 protected 的，并且不需要實(shí)現(xiàn)。
class T
{
protected:
T(const T& rhs);
T& operator = (const T& rhs);
};
只能聲明一個(gè)對(duì)象的類
即是單例模式
將構(gòu)造函數(shù)聲明為 private 以防在棧上隨意定義對(duì)象
定義一個(gè) static 的本類型指針，只是指向唯一的一個(gè)對(duì)象
定義一個(gè) static 成員函數(shù)，用于獲得指向唯一的那個(gè)對(duì)象的指針
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.shnenglu.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.shnenglu.com/unixfy/archive/2011/04/29/145340.html
31 隨機(jī)生成只輸出一次的 1-100 的 100 個(gè)元素
隨機(jī)生成下標(biāo)，將這個(gè)下標(biāo)生成的值與 end 交換，然后 --end
繼續(xù)在 0-end 范圍內(nèi)隨機(jī)生成下標(biāo)，然后將這個(gè)下標(biāo)與 end 對(duì)應(yīng)的元素交換，--end
直到生成完 100 個(gè)元素
http://www.shnenglu.com/jake1036/archive/2011/05/20/146818.html
31 倒序輸出鏈表中的元素
采用遞歸的策略
void print(node* p)
{
if (p != 0)
{
print(p->next);
cout << p->item << ' ';
}
}
擴(kuò)展：在函數(shù)體內(nèi)不聲明變量，求字符串的長度
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.shnenglu.com/jake1036/archive/2011/05/21/146869.html
幾個(gè)面試題的小分析
面試題 100 - 20 最長公共子串
求兩個(gè)字符串的最長公共子串，不需要連續(xù)
根據(jù)當(dāng)前的兩個(gè)字符 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]
記錄路徑，根據(jù) max 去哪個(gè)值，記錄 m 矩陣的走勢(shì)，是向右、向下還是向右下
求路徑的時(shí)候，利用輔助矩陣 t[][] 記錄的走勢(shì)狀態(tài)，遞歸求出具體的最長公共子串。
面試題 100 - 30 異常安全的復(fù)制
一般函數(shù)指針成員的類對(duì)象，對(duì) operator = 進(jìn)行重載
在重載的函數(shù)體內(nèi)，有可能造成重新分配內(nèi)存失敗，造成了異常，原來的內(nèi)存空間已經(jīng)被釋放掉了，無法恢復(fù)之前的狀態(tài)。例如：
T& T::operator = (const T& rhs)
{
if (this != &rhs)
{
delete [] pdata;
pdata = new Type[];
copy(...);
}
return *this;
}
這種情況下，可能 new 失敗造成異常，但是 pdate 指向的內(nèi)存已經(jīng)被釋放。
為了異常安全
采用臨時(shí)多一份的策略
第一種方法是，使用一個(gè)臨時(shí)指針，給這個(gè)指針分配塊內(nèi)存，然后刪除原來的內(nèi)存，將這個(gè)臨時(shí)指針賦值給本對(duì)象中的指針成員。
T& T::operator = (const T& rhs)
{
if (this != &rhs)
{
Type * temp = new Type[];
copy(...);
delete [] pdata;
pdata = temp;
}
return *this;
}
第二種方法也是用臨時(shí)多一份的策略，使用一個(gè)臨時(shí)本類型的對(duì)象，利用拷貝構(gòu)造函數(shù)，然后交換臨時(shí)對(duì)象與本對(duì)象。
T& T::operator = (const T& rhs)
{
if (this != &rhs)
{
T temp(rhs);
swap(*this, temp);
}
return *this;
}
這里交換的是 *this 和 temp 的指針的值，而不是指針成員指向的內(nèi)存內(nèi)容，也就是說是做的對(duì)象的位交換。
這種有了一個(gè)臨時(shí)對(duì)象，可以不用做自賦值的檢測(cè)。即便是自賦值，也不會(huì)造成原數(shù)據(jù)的丟失。可以寫成：
T& T::operator = (const T& rhs)
{
T temp(rhs);
swap(*this, temp);
return *this;
}
上面的第一種做法，也可以不做自賦值檢測(cè)。
最上面的非異常安全的做法是
1
0
1
當(dāng) 0 過后，可能在產(chǎn)生 1 的時(shí)候異常，就無法恢復(fù)了。
臨時(shí)多一份的策略是
1
2
1
即便在產(chǎn)生 2 的過程中發(fā)生了異常，仍然有一個(gè)，所以是異常安全的。
兩個(gè)發(fā)生異常的階段分別是
0->1
1->2
關(guān)鍵要看異常前的情況，如果異常前就保證有效，則即使發(fā)生了異常也沒有問題，即是異常安全的。
http://www.shnenglu.com/jake1036/archive/2011/05/20/146689.html
http://www.shnenglu.com/jake1036/archive/2011/05/20/146816.html
使數(shù)組中的奇數(shù)位于偶數(shù)之前
從數(shù)組兩端遍歷，檢測(cè)當(dāng)前元素的奇偶性，條件允許時(shí)交換，直到兩個(gè)索引交叉。
http://www.shnenglu.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 }
求給定值的連續(xù)序列
例如給定值是 15
則有：
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
求解
設(shè)定一個(gè)區(qū)間 [left, right]
計(jì)算 left 到 right 之間的所有和 sum
若 sum 小于給定值 n 則 right 右移
若 sum 大于給定值 n 則 left 右移
若 sum 等于給定值 n 則 left 右移
[left, right] 的初始是 [1, 1]
另一個(gè)問題
求解一個(gè)集合中兩個(gè)元素之和等于給定值
先對(duì)這個(gè)集合進(jìn)行排序，然后從兩端遍歷，若和大于給定值則右邊的標(biāo)記左移，若和小于給定值則左邊的值右移。
http://www.shnenglu.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 }
判斷棧的 push 和 pop 序列是否正確
有兩個(gè)隊(duì)列分別是 push 隊(duì)列和 pop 隊(duì)列
判斷其入棧出棧序列是否正確
利用一個(gè)輔助棧 tmp
掃描 pop 隊(duì)列
對(duì) pop 隊(duì)列的首元素進(jìn)行檢測(cè)，首先檢測(cè) tmp 棧頂元素是否與 pop 隊(duì)首元素一樣，如果一樣則將則將 tmp 棧頂元素刪除。
如果不一樣，則遍歷整個(gè) push 隊(duì)列，將不一樣的壓入到 tmp 中，直到遇到一樣的。
http://www.shnenglu.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 }