求整數 n 的二進制表示中 1 的個數
1.
采用除二取余法
while (n != 0)
{
if (n % 2 == 1)
{
++ret;
}
n /= 2;
}
這種方法對于 n 是正數的時候沒有問題，而且需要是整數。
如果 n 是負整數，則需要與機器相關，如果 n = -3, 則 n % 2 有余 -1 ，這種情況下，得到的最終結果是 0，對于任何的負整數結果都是 0
也可以通過移位的方法做：
while (n != 0)
{
ret += (n & 1);
n >>= 1;
}
這種方法對于正數是可行的，并且不限于整數
但是對于負數，由于最高位是 1 ，做的意味是邏輯移位，移位后高位還是 1 ，程序進入了死循環。
2.
對 1 進行左移位，做位運算
int flag = 1;
int ret = 0;
while (flag != 0)
{
if ((flag & n) != 0)
{
++ret;
}
flag << 1
}
這種方法不是對 n 進行的移位，而是對 flag 移的位，不會造成 n 移位帶來的死循環。當 flag 移到 sizeof (flag) * 8 位時，歸零，循環終止。
3.
采用 n & (n - 1) 操作
以上兩種方法都是做了 sizeof (type) * 8 次循環
采用 n & (n - 1) 的方式，只需做 n 的二進制中含有 1 的個數次循環即可。
while (n != 0)
{
++ret;
n &= (n - 1);
}
http://www.shnenglu.com/jake1036/archive/2011/05/18/146698.html
posted @
2011-07-23 11:03 unixfy 閱讀(150) |
評論 (0) |
編輯 收藏關于含有成員指針的類的復制控制
一個類中如果含有了指針成員，在不加任何措施的時候，復制類對象是做的位復制操作，即是所謂的淺拷貝，兩個對象的指針式一樣的值，指向同一塊內存區。
這種情況下，當一個對象刪除其成員指針指向的內存區后，另一個對象的指針成員指向的內存區也就被釋放了。
如果第一個對象析構時刪除了這個內存區，那么在第二對象析構時造成同一塊內存多次被釋放，程序崩潰。
解決這個問題有常規上有兩種方法
一是，進行深拷貝，在拷貝構造函數和復制運算符中進行相應的內存分配和復制工作。析構的時候只是各自析構各自的。
二是，采用引用計數手段，在拷貝構造函數和復制運算符中對引用計數進行分析，多個復制對象的指針成員只指向同一個內存區，在最后一個對象析構的時候才最終將這個內存區釋放掉。
引用計數的好處是，可以節省內存分配、拷貝、內存釋放所帶來的效率消耗，以及節省內存。
http://www.shnenglu.com/jake1036/archive/2011/05/17/146594.html
淺拷貝
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4
5 class str
6 {
7 private:
8 char* s_;
9 public:
10 str(const char* s = "")
11 {
12 s_ = new char[strlen(s) + 1];
13 if (s_ != 0)
14 {
15 strcpy(s_, s);
16 }
17 }
18 ~str()
19 {
20 delete [] s_;
21 }
22 char* s() const
23 {
24 return s_;
25 }
26 };
27
28 ostream& operator << (ostream& out, const str& s)
29 {
30 out << s.s() << endl;
31 return out;
32 }
33
34 int main()
35 {
36 str s1 = "123";
37 str s2(s1);
38 cout << s1 << endl;
39 cout << s2 << endl;
40 }
深拷貝
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4
5 class str
6 {
7 private:
8 char* s_;
9 public:
10 str(const char* s = "")
11 {
12 s_ = new char[strlen(s) + 1];
13 if (s_ != 0)
14 {
15 strcpy(s_, s);
16 }
17 }
18 str(const str& s)
19 {
20 s_ = new char[strlen(s.s_) + 1];
21 if (s_ != 0)
22 {
23 strcpy(s_, s.s_);
24 }
25 }
26 str& operator = (const str& s)
27 {
28 if (this != &s)
29 {
30 delete [] s_;
31 s_ = new char[strlen(s.s_) + 1];
32 if (s_ != 0)
33 {
34 strcpy(s_, s.s_);
35 }
36 }
37 return *this;
38 }
39 ~str()
40 {
41 delete [] s_;
42 }
43 char* sr() const
44 {
45 return s_;
46 }
47 };
48
49 ostream& operator << (ostream& out, const str& s)
50 {
51 out << s.sr() << endl;
52 return out;
53 }
54
55 int main()
56 {
57 str s1 = "123";
58 str s2(s1);
59 cout << s1 << endl;
60 cout << s2 << endl;
61 }
引用計數
引用計數的實現是通過在類對象中增加一個指向 int 型的指針，這個指針指向的那個 int 即是計數，記錄指針指向的那塊內存被幾個對象共用著。
采用引用計數，在構造函數、析構函數、拷貝構造函數、復制運算符中，都要對這個指向 int 的指針進行操作，并且需要判斷指針指針指向 int 的變化情況，當為 0 時，則要釋放掉指針指向的內存。
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4
5 class str
6 {
7 private:
8 char* s_;
9 int* pcount_;
10 public:
11 str(const char* s = "")
12 {
13 s_ = new char[strlen(s) + 1];
14 if (s_ != 0)
15 {
16 strcpy(s_, s);
17 pcount_ = new int;
18 if (pcount_ != 0)
19 {
20 *pcount_ = 1;
21 }
22 }
23 }
24 str(const str& s)
25 {
26 s_ = s.s_;
27 pcount_ = s.pcount_;
28 ++(*pcount_);
29 }
30 str& operator = (const str& s)
31 {
32 if (this != &s)
33 {
34 --(*pcount_);
35 if (*pcount_ == 0)
36 {
37 if (s_ != 0)
38 {
39 delete [] s_;
40 s_ = 0;
41 }
42 delete pcount_;
43 pcount_ = 0;
44 }
45 s_ = s.s_;
46 pcount_ = s.pcount_;
47 ++(*pcount_);
48 }
49 return *this;
50 }
51 ~str()
52 {
53 --(*pcount_);
54 if (*pcount_ == 0)
55 {
56 // cout << "test" << endl;
57 if (s_ != 0)
58 {
59 delete [] s_;
60 s_ = 0;
61 }
62 delete pcount_;
63 pcount_ = 0;
64 }
65 }
66 char* sr() const
67 {
68 return s_;
69 }
70 };
71
72 ostream& operator << (ostream& out, const str& s)
73 {
74 out << s.sr() << endl;
75 return out;
76 }
77
78 int main()
79 {
80 str s1 = "123";
81 str s2(s1);
82 cout << s1 << endl;
83 cout << s2 << endl;
84 }
85
posted @
2011-07-22 17:20 unixfy 閱讀(265) |
評論 (0) |
編輯 收藏第一個只出現一次的字符
一個字符串中，查找其中第一個只出現一次的字符。
這里建設這個字符串中的字符可以使英文大小寫字符也可以是數字字符。
http://www.shnenglu.com/jake1036/archive/2011/05/17/146542.html
解決方案是：
用 map 記錄每個字符的出現次數，以及第一次出現的索引。
然后遍歷 map ，找到出現 1 次且索引最小的那個字符。
1 #include <iostream>
2 #include <string>
3 #include <map>
4 using namespace std;
5
6 char findHeadOnce(const string& s)
7 {
8 map<char, int> times;
9 map<char, int> indexes;
10 for (string::size_type i = 0; i != s.size(); ++i)
11 {
12 ++times[s[i]];
13 if (times[s[i]] == 1)
14 {
15 indexes[s[i]] = i;
16 }
17 }
18 int idx = s.size();
19 for (map<char, int>::const_iterator cit = indexes.begin(); cit != indexes.end(); ++cit)
20 {
21 if (times[cit->first] == 1 && idx > cit->second)
22 {
23 idx = cit->second;
24 }
25 }
26 if (idx < s.size())
27 {
28 return s[idx];
29 }
30 else
31 {
32 return '*';
33 }
34 }
35
36 int main()
37 {
38 string s;
39 while (cin >> s)
40 {
41 cout << findHeadOnce(s) << endl;
42 }
43 }
posted @
2011-07-22 16:21 unixfy 閱讀(305) |
評論 (0) |
編輯 收藏從上向下遍歷二叉樹
樹的層次遍歷
圖的廣度遍歷
首先是要定義二叉樹節點的結構體
建立二叉樹
層次遍歷，需要一個隊列輔助
建立一棵二叉樹
遞歸的前序、中序、后序遍歷
層次遍歷
http://www.shnenglu.com/jake1036/archive/2011/05/17/146537.html
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4
5 struct node
6 {
7 int data;
8 node* left;
9 node* right;
10 };
11
12 void addNode(int item, node*& root)
13 {
14 if (root == 0)
15 {
16 root = new node;
17 root->data = item;
18 root->left = 0;
19 root->right = 0;
20 return;
21 }
22 else
23 {
24 node* p = root, * p2;
25 while (p != 0)
26 {
27 p2 = p;
28 if (item < p->data)
29 {
30 p = p->left;
31 }
32 else
33 {
34 p = p->right;
35 }
36 }
37 node* q = new node;
38 q->data = item;
39 q->left = 0;
40 q->right = 0;
41 if (p2->data > q->data)
42 {
43 p2->left = q;
44 }
45 else
46 {
47 p2->right = q;
48 }
49 }
50 }
51
52 void preOrder(node* root)
53 {
54 if (root != 0)
55 {
56 cout << root->data << ' ';
57 preOrder(root->left);
58 preOrder(root->right);
59 }
60 }
61
62 void inOrder(node* root)
63 {
64 if (root != 0)
65 {
66 inOrder(root->left);
67 cout << root->data << ' ';
68 inOrder(root->right);
69 }
70 }
71
72 void postOrder(node* root)
73 {
74 if (root != 0)
75 {
76 postOrder(root->left);
77 postOrder(root->right);
78 cout << root->data << ' ';
79 }
80 }
81
82 void levelOrder(node* root)
83 {
84 if (root != 0)
85 {
86 queue<node*> q;
87 node* t;
88 q.push(root);
89 while (!q.empty())
90 {
91 t = q.front();
92 q.pop();
93 cout << t-> data << ' ';
94 if (t->left != 0)
95 {
96 q.push(t->left);
97 }
98 if (t->right != 0)
99 {
100 q.push(t->right);
101 }
102 }
103 }
104 }
105
106 int main()
107 {
108 int a[] = {5, 2, 7, 4, 9, 8, 3, 6, 1};
109 node* root = 0;
110 for (int i = 0; i != sizeof (a) / sizeof (*a); ++i)
111 {
112 // cout << i << endl;
113 addNode(a[i], root);
114 }
115 preOrder(root);
116 cout << endl;
117 inOrder(root);
118 cout << endl;
119 postOrder(root);
120 cout << endl;
121 levelOrder(root);
122 cout << endl;
123 return 0;
124 }
posted @
2011-07-22 15:44 unixfy 閱讀(165) |
評論 (0) |
編輯 收藏《Unix Curses 庫導論-翻譯版》 下載地址
原文檔地址：
http://heather.cs.ucdavis.edu/~matloff/UnixAndC/CLanguage/Curses.pdf
CSDN 下載地址：
http://download.csdn.net/source/3459634
本站下載
posted @
2011-07-21 17:25 unixfy 閱讀(127) |
評論 (0) |
編輯 收藏
摘要:
Unix Curses 庫導論
Norman Matloff
http://heather.cs.ucdavis.edu/~matloff/
原版地址：http://heather.cs.ucdavis.edu/~matloff/UnixAndC/CLanguage/Curses.pdf
加州大...
閱讀全文
posted @
2011-07-21 17:12 unixfy 閱讀(338) |
評論 (0) |
編輯 收藏一個關于數組的問題
一個數組 {5, 2, 9, 4, 7}
這個數組有 5 個元素
這 5 個元素的位置依次是 1 2 3 4 5
這 5 個元素的從小到大的順序是 3 1 5 2 4
數組中的一個元素，有三個屬性即：
元素本身 A 5 2 9 4 7
原來在數組中的位置 B 1 2 3 4 5
從小到大的順序 C 3 1 5 2 4
給定一個數組，如何得到每個元素的這三個屬性？
對于每個元素，知道其中一個屬性，如何得到另外兩個屬性
B 和 C 都是從 1 到 5 的。
對 B 可以排個序，然后按索引取即可。
C 也是如此。
對于 A ，因為其是有間隔的，如果直接按索引，可能會浪費空間。可以采用哈希去做 O(1) 。
也可以直接對其進行一遍掃描 O(N) 。
或者建立平衡二叉樹 O(logN) 。
1 #include <iostream>
2 #include <cstdlib>
3 using namespace std;
4
5 struct Element
6 {
7 int value;
8 int position;
9 int order;
10 };
11
12 int cmpByValue(const void* a, const void* b)
13 {
14 return ((Element*)a)->value - ((Element*)b)->value;
15 }
16
17 int cmpByPosition(const void* a, const void* b)
18 {
19 return ((Element*)a)->position - ((Element*)b)->position;
20 }
21
22 int cmpByOrder(const void* a, const void* b)
23 {
24 return ((Element*)a)->order - ((Element*)b)->order;
25 }
26
27 int main()
28 {
29 int a[] = {5, 2, 9, 4, 7};
30 Element els[5];
31 for (int i = 0; i != 5; ++i)
32 {
33 els[i].value = a[i];
34 els[i].position = i + 1;
35 }
36 qsort(els, 5, sizeof (*els), cmpByValue);
37
38 for (int i = 0; i != 5; ++i)
39 {
40 els[i].order = i + 1;
41 }
42
43 for (int i = 0; i != 5; ++i)
44 {
45 cout << els[i].value << ' ' << els[i].position << ' ' << els[i].order << endl;
46 }
47 cout << endl;
48
49 qsort(els, 5, sizeof (*els), cmpByPosition);
50
51 for (int i = 0; i != 5; ++i)
52 {
53 cout << els[i].value << ' ' << els[i].position << ' ' << els[i].order << endl;
54 }
55 cout << endl;
56
57 qsort(els, 5, sizeof (*els), cmpByOrder);
58 for (int i = 0; i != 5; ++i)
59 {
60 cout << els[i].value << ' ' << els[i].position << ' ' << els[i].order << endl;
61 }
62
63 return 0;
64 }
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/http://www.slyar.com/blog/stdlib-qsort.htmlhttp://www.shnenglu.com/qywyh/articles/3405.htmlhttp://pubs.opengroup.org/onlinepubs/009695399/functions/qsort.htmlhttp://linux.die.net/man/3/qsorthttp://en.wikipedia.org/wiki/Qsorthttp://msdn.microsoft.com/en-us/library/aa272872(v=vs.60).aspx
posted @
2011-07-20 11:32 unixfy 閱讀(88) |
評論 (0) |
編輯 收藏求 n! 的尾部連續的 0 的個數
這個題目在網上的一個面試題中出現過
《編程之美》里也有這個問題
求末尾有多少 0
關鍵是對 n! 進行質因數分解，分解得到的質因數有 1 2 3 5 7 11 ...
觀察這些質因數我們可以知道 0 是由 2 和 5 相乘得到的
質因數 2 的個數和 5 的個數決定了 0 的個數
2 的個數大于等于 5 的個數
這里 0 的個數即是質因數中 5 的個數
對 1 - n 的每個數，計算其內有多少個質因數 5 ，所得的結果即是 n! 的尾部連續的 0 的個數。
1 #include <iostream>
2 using namespace std;
3
4 int foo(int n)
5 {
6 int ret = 0, t;
7 for (int i = 1; i <= n; ++i)
8 {
9 t = i;
10 while (t % 5 == 0)
11 {
12 ++ret;
13 t /= 5;
14 }
15 }
16 return ret;
17 }
18
19 int main()
20 {
21 int n;
22 while (cin >> n)
23 {
24 cout << foo(n) << endl;
25 }
26 return 0;
27 }
posted @
2011-07-19 22:12 unixfy 閱讀(362) |
評論 (0) |
編輯 收藏符合數 A 定義的數
d(n) = n + n 的各位之和
d(78) = 78 + 7 + 8 = 93
定義數 A ：數 A 找不到一個數 B 可有 d(B) = A ，即 A 不能由其他數生成。
找出 1 - 10000 里所有符合數 A 的數。
根據 d 的定義 d(a) = b，我們知道對每一個 a 有 a < b
要找到 1 - 10000 里所有的符合 A 的數，即是找到不存在 d(B) = A 的數 A 。
可以設定一個 10001 大小的數組，遍歷整個數組，計算每個下標 B 對應的 d(B) A 。將以 A 為下標的元素設置狀態。
遍歷完后，即可確定要找的符合數 A 的數。
1 #include <iostream>
2 using namespace std;
3
4 int sum(int n)
5 {
6 int ret = 0;
7 while (n != 0)
8 {
9 ret += n % 10;
10 n /= 10;
11 }
12 return ret;
13 }
14
15 void findA(int a[], int n)
16 {
17 memset(a, 0, sizeof (*a) * n);
18 int t = 0;
19 for (int i = 1; i <= n; ++i)
20 {
21 if ((t = i + sum(i) <= n))
22 {
23 a[i + sum(i)] = 1;
24 }
25 }
26 }
27
28 int main()
29 {
30 int n;
31 const int size = 10001;
32 int a[size + 1];
33
34 findA(a, size);
35
36 for (int i = 1; i <= size; ++i)
37 {
38 if (a[i] == 0)
39 {
40 cout << i << ' ';
41 }
42 }
43 cout << endl;
44
45 return 0;
46 }
posted @
2011-07-19 21:59 unixfy 閱讀(150) |
評論 (0) |
編輯 收藏按一定概率打印數，不是隨機數
打印的數是隨機生成的，但是總體上看，不同的隨機數打印出來的次數要不同。
打印 1000 個隨機數，隨機數的范圍是 0-100，這 1000 個隨機數根據其大小出現次數的比例不同，1 出現的比例最小，100 出現的比率最大。
需要注意的東西
隨機數的范圍 m
隨機參數的依據，這里的依據是根據隨機數的大小確定的，即使函數中的 t
產生的隨機數的個數 n
保存的結果 a ，a 中保存的其實不是 rand 產生的數，而是根據 rand 產生的數進而確定的 t 的下標
統計結果的 s
這里用到了 rand 函數，a 中保存的不是直接取自 rand ，而是根據 rand 產生的數間接得到的 t 的那個下標，因為題目就是要求根據不同的概率打印出數，這個數其實不是隨機數了。
實現：
1 #include <iostream>
2 #include <string>
3 #include <ctime>
4 #include <cstdlib>
5 #include <cstring>
6 using namespace std;
7
8 // 結果存于 a 中，產生 n 個結果
9 // 范圍是從 1 - m
10 int foo(int a[], int s[], int n, int m)
11 {
12 int* t = new int [m];
13 t[0] = 1;
14 for (int i = 1; i < m; ++i)
15 {
16 t[i] = t[i - 1] + i + 1;
17 }
18 int MAX = (1 + m) * m / 2;
19
20 // cout << t[m - 1] << endl;
21 // cout << MAX << endl;
22
23 srand(time(0));
24 int e = 0;
25 int r = 0;
26 for (int i = 0; i < n; ++i)
27 {
28 r = (rand() % MAX) + 1;
29 //cout << "r: " << r << endl;
30 for (int j = m - 1; j >= 0; --j)
31 {
32 if (r > t[j])
33 {
34 a[e++] = j + 1 + 1;
35 break;
36 }
37 else if (r == t[j])
38 {
39 a[e++] = j + 1;
40 break;
41 }
42 }
43 /*
44 for (int j = 0; j < m; ++j)
45 {
46 if (r <= t[j])
47 {
48 //cout << j + 1 << endl;
49 a[e++] = j + 1;
50 break;
51 }
52 }
53 */
54 }
55
56 memset(s, 0, sizeof (*s) * m);
57 for (int i = 0; i != n; ++i)
58 {
59 ++s[a[i] - 1];
60 }
61 }
62
63 int main()
64 {
65 int n = 0, m = 0;
66 int* a, * s;
67 while (cin >> n >> m)
68 {
69 a = new int [n];
70 s = new int [m];
71 foo(a, s, n, m);
72
73 for (int i = 0; i < n; ++i)
74 {
75 cout << a[i] << ' ';
76 }
77 cout << endl;
78
79 for (int i = 0; i != m; ++i)
80 {
81 cout << i + 1 << ": " << s[i] << endl;
82 }
83 }
84 return 0;
85 }
posted @
2011-07-19 14:20 unixfy 閱讀(186) |
評論 (0) |
編輯 收藏