求整數(shù) n 的二進(jìn)制表示中 1 的個數(shù)
1.
采用除二取余法
while (n != 0)
{
if (n % 2 == 1)
{
++ret;
}
n /= 2;
}
這種方法對于 n 是正數(shù)的時候沒有問題，而且需要是整數(shù)。
如果 n 是負(fù)整數(shù)，則需要與機(jī)器相關(guān)，如果 n = -3, 則 n % 2 有余 -1 ，這種情況下，得到的最終結(jié)果是 0，對于任何的負(fù)整數(shù)結(jié)果都是 0
也可以通過移位的方法做：
while (n != 0)
{
ret += (n & 1);
n >>= 1;
}
這種方法對于正數(shù)是可行的，并且不限于整數(shù)
但是對于負(fù)數(shù)，由于最高位是 1 ，做的意味是邏輯移位，移位后高位還是 1 ，程序進(jìn)入了死循環(huán)。
2.
對 1 進(jìn)行左移位，做位運(yùn)算
int flag = 1;
int ret = 0;
while (flag != 0)
{
if ((flag & n) != 0)
{
++ret;
}
flag << 1
}
這種方法不是對 n 進(jìn)行的移位，而是對 flag 移的位，不會造成 n 移位帶來的死循環(huán)。當(dāng) flag 移到 sizeof (flag) * 8 位時，歸零，循環(huán)終止。
3.
采用 n & (n - 1) 操作
以上兩種方法都是做了 sizeof (type) * 8 次循環(huán)
采用 n & (n - 1) 的方式，只需做 n 的二進(jìn)制中含有 1 的個數(shù)次循環(huán)即可。
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 閱讀(159) |
評論 (0) |
編輯 收藏關(guān)于含有成員指針的類的復(fù)制控制
一個類中如果含有了指針成員，在不加任何措施的時候，復(fù)制類對象是做的位復(fù)制操作，即是所謂的淺拷貝，兩個對象的指針式一樣的值，指向同一塊內(nèi)存區(qū)。
這種情況下，當(dāng)一個對象刪除其成員指針指向的內(nèi)存區(qū)后，另一個對象的指針成員指向的內(nèi)存區(qū)也就被釋放了。
如果第一個對象析構(gòu)時刪除了這個內(nèi)存區(qū)，那么在第二對象析構(gòu)時造成同一塊內(nèi)存多次被釋放，程序崩潰。
解決這個問題有常規(guī)上有兩種方法
一是，進(jìn)行深拷貝，在拷貝構(gòu)造函數(shù)和復(fù)制運(yùn)算符中進(jìn)行相應(yīng)的內(nèi)存分配和復(fù)制工作。析構(gòu)的時候只是各自析構(gòu)各自的。
二是，采用引用計(jì)數(shù)手段，在拷貝構(gòu)造函數(shù)和復(fù)制運(yùn)算符中對引用計(jì)數(shù)進(jìn)行分析，多個復(fù)制對象的指針成員只指向同一個內(nèi)存區(qū)，在最后一個對象析構(gòu)的時候才最終將這個內(nèi)存區(qū)釋放掉。
引用計(jì)數(shù)的好處是，可以節(jié)省內(nèi)存分配、拷貝、內(nèi)存釋放所帶來的效率消耗，以及節(jié)省內(nèi)存。
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 }
引用計(jì)數(shù)
引用計(jì)數(shù)的實(shí)現(xiàn)是通過在類對象中增加一個指向 int 型的指針，這個指針指向的那個 int 即是計(jì)數(shù)，記錄指針指向的那塊內(nèi)存被幾個對象共用著。
采用引用計(jì)數(shù)，在構(gòu)造函數(shù)、析構(gòu)函數(shù)、拷貝構(gòu)造函數(shù)、復(fù)制運(yùn)算符中，都要對這個指向 int 的指針進(jìn)行操作，并且需要判斷指針指針指向 int 的變化情況，當(dāng)為 0 時，則要釋放掉指針指向的內(nèi)存。
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 閱讀(272) |
評論 (0) |
編輯 收藏第一個只出現(xiàn)一次的字符
一個字符串中，查找其中第一個只出現(xiàn)一次的字符。
這里建設(shè)這個字符串中的字符可以使英文大小寫字符也可以是數(shù)字字符。
http://www.shnenglu.com/jake1036/archive/2011/05/17/146542.html
解決方案是：
用 map 記錄每個字符的出現(xiàn)次數(shù)，以及第一次出現(xiàn)的索引。
然后遍歷 map ，找到出現(xiàn) 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 閱讀(313) |
評論 (0) |
編輯 收藏從上向下遍歷二叉樹
樹的層次遍歷
圖的廣度遍歷
首先是要定義二叉樹節(jié)點(diǎn)的結(jié)構(gòu)體
建立二叉樹
層次遍歷，需要一個隊(duì)列輔助
建立一棵二叉樹
遞歸的前序、中序、后序遍歷
層次遍歷
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 閱讀(172) |
評論 (0) |
編輯 收藏《Unix Curses 庫導(dǎo)論-翻譯版》 下載地址
原文檔地址：
http://heather.cs.ucdavis.edu/~matloff/UnixAndC/CLanguage/Curses.pdf
CSDN 下載地址：
http://download.csdn.net/source/3459634
本站下載
posted @
2011-07-21 17:25 unixfy 閱讀(133) |
評論 (0) |
編輯 收藏
摘要:
Unix Curses 庫導(dǎo)論
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 閱讀(345) |
評論 (0) |
編輯 收藏一個關(guān)于數(shù)組的問題
一個數(shù)組 {5, 2, 9, 4, 7}
這個數(shù)組有 5 個元素
這 5 個元素的位置依次是 1 2 3 4 5
這 5 個元素的從小到大的順序是 3 1 5 2 4
數(shù)組中的一個元素，有三個屬性即：
元素本身 A 5 2 9 4 7
原來在數(shù)組中的位置 B 1 2 3 4 5
從小到大的順序 C 3 1 5 2 4
給定一個數(shù)組，如何得到每個元素的這三個屬性？
對于每個元素，知道其中一個屬性，如何得到另外兩個屬性
B 和 C 都是從 1 到 5 的。
對 B 可以排個序，然后按索引取即可。
C 也是如此。
對于 A ，因?yàn)槠涫怯虚g隔的，如果直接按索引，可能會浪費(fèi)空間。可以采用哈希去做 O(1) 。
也可以直接對其進(jìn)行一遍掃描 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 閱讀(94) |
評論 (0) |
編輯 收藏求 n! 的尾部連續(xù)的 0 的個數(shù)
這個題目在網(wǎng)上的一個面試題中出現(xiàn)過
《編程之美》里也有這個問題
求末尾有多少 0
關(guān)鍵是對 n! 進(jìn)行質(zhì)因數(shù)分解，分解得到的質(zhì)因數(shù)有 1 2 3 5 7 11 ...
觀察這些質(zhì)因數(shù)我們可以知道 0 是由 2 和 5 相乘得到的
質(zhì)因數(shù) 2 的個數(shù)和 5 的個數(shù)決定了 0 的個數(shù)
2 的個數(shù)大于等于 5 的個數(shù)
這里 0 的個數(shù)即是質(zhì)因數(shù)中 5 的個數(shù)
對 1 - n 的每個數(shù)，計(jì)算其內(nèi)有多少個質(zhì)因數(shù) 5 ，所得的結(jié)果即是 n! 的尾部連續(xù)的 0 的個數(shù)。
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 閱讀(370) |
評論 (0) |
編輯 收藏符合數(shù) A 定義的數(shù)
d(n) = n + n 的各位之和
d(78) = 78 + 7 + 8 = 93
定義數(shù) A ：數(shù) A 找不到一個數(shù) B 可有 d(B) = A ，即 A 不能由其他數(shù)生成。
找出 1 - 10000 里所有符合數(shù) A 的數(shù)。
根據(jù) d 的定義 d(a) = b，我們知道對每一個 a 有 a < b
要找到 1 - 10000 里所有的符合 A 的數(shù)，即是找到不存在 d(B) = A 的數(shù) A 。
可以設(shè)定一個 10001 大小的數(shù)組，遍歷整個數(shù)組，計(jì)算每個下標(biāo) B 對應(yīng)的 d(B) A 。將以 A 為下標(biāo)的元素設(shè)置狀態(tài)。
遍歷完后，即可確定要找的符合數(shù) A 的數(shù)。
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 閱讀(160) |
評論 (0) |
編輯 收藏按一定概率打印數(shù)，不是隨機(jī)數(shù)
打印的數(shù)是隨機(jī)生成的，但是總體上看，不同的隨機(jī)數(shù)打印出來的次數(shù)要不同。
打印 1000 個隨機(jī)數(shù)，隨機(jī)數(shù)的范圍是 0-100，這 1000 個隨機(jī)數(shù)根據(jù)其大小出現(xiàn)次數(shù)的比例不同，1 出現(xiàn)的比例最小，100 出現(xiàn)的比率最大。
需要注意的東西
隨機(jī)數(shù)的范圍 m
隨機(jī)參數(shù)的依據(jù)，這里的依據(jù)是根據(jù)隨機(jī)數(shù)的大小確定的，即使函數(shù)中的 t
產(chǎn)生的隨機(jī)數(shù)的個數(shù) n
保存的結(jié)果 a ，a 中保存的其實(shí)不是 rand 產(chǎn)生的數(shù)，而是根據(jù) rand 產(chǎn)生的數(shù)進(jìn)而確定的 t 的下標(biāo)
統(tǒng)計(jì)結(jié)果的 s
這里用到了 rand 函數(shù)，a 中保存的不是直接取自 rand ，而是根據(jù) rand 產(chǎn)生的數(shù)間接得到的 t 的那個下標(biāo)，因?yàn)轭}目就是要求根據(jù)不同的概率打印出數(shù)，這個數(shù)其實(shí)不是隨機(jī)數(shù)了。
實(shí)現(xiàn)：
1 #include <iostream>
2 #include <string>
3 #include <ctime>
4 #include <cstdlib>
5 #include <cstring>
6 using namespace std;
7
8 // 結(jié)果存于 a 中，產(chǎn)生 n 個結(jié)果
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 閱讀(194) |
評論 (0) |
編輯 收藏