實現一棵多叉樹
這棵樹可以有任意多顆子樹 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 閱讀(4959) |
評論 (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 閱讀(364) |
評論 (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.shnenglu.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.shnenglu.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.shnenglu.com/jake1036/archive/2011/05/22/146909.html
36 在字符串中刪除指定的字符
給定兩個字符串，刪除第一個字符串中在第二個字符串出現的字符
例如：
"abcefgh", "abcef"
得到：
"gh"
先對第二個字符串，做 hash 記錄要刪除的字符
然后遍歷第一個字符串，根據 hash 表，判斷當前字符是否是要刪除的那個字符
對第一個字符串的處理，可以利用一個指針和一個已刪除的字符數目記錄
也可以利用兩個指針，分別記錄當前遍歷的字符和刪除后的字符串記錄
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
posted @
2011-07-23 22:55 unixfy 閱讀(154) |
評論 (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.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
posted @
2011-07-23 22:07 unixfy 閱讀(447) |
評論 (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.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
posted @
2011-07-23 21:48 unixfy 閱讀(746) |
評論 (0) |
編輯 收藏31 隨機生成只輸出一次的 1-100 的 100 個元素
隨機生成下標，將這個下標生成的值與 end 交換，然后 --end
繼續在 0-end 范圍內隨機生成下標，然后將這個下標與 end 對應的元素交換，--end
直到生成完 100 個元素
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 << ' ';
}
}
擴展：在函數體內不聲明變量，求字符串的長度
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
posted @
2011-07-23 21:27 unixfy 閱讀(100) |
評論 (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.shnenglu.com/jake1036/archive/2011/05/20/146689.html
http://www.shnenglu.com/jake1036/archive/2011/05/20/146816.html
posted @
2011-07-23 21:09 unixfy 閱讀(73) |
評論 (0) |
編輯 收藏使數組中的奇數位于偶數之前
從數組兩端遍歷，檢測當前元素的奇偶性，條件允許時交換，直到兩個索引交叉。
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 }
posted @
2011-07-23 20:20 unixfy 閱讀(216) |
評論 (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.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 }
posted @
2011-07-23 16:23 unixfy 閱讀(95) |
評論 (0) |
編輯 收藏判斷棧的 push 和 pop 序列是否正確
有兩個隊列分別是 push 隊列和 pop 隊列
判斷其入棧出棧序列是否正確
利用一個輔助棧 tmp
掃描 pop 隊列
對 pop 隊列的首元素進行檢測，首先檢測 tmp 棧頂元素是否與 pop 隊首元素一樣，如果一樣則將則將 tmp 棧頂元素刪除。
如果不一樣，則遍歷整個 push 隊列，將不一樣的壓入到 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 }
posted @
2011-07-23 13:14 unixfy 閱讀(236) |
評論 (0) |
編輯 收藏