求整数 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.cppblog.com/jake1036/archive/2011/05/18/146698.html
posted @
2011-07-23 11:03 unixfy 阅读(150) |
评论 (0) |
编辑 收藏关于含有成员指针的类的复制控制
一个类中如果含有了指针成员，在不加任何措施的时候，复制类对象是做的位复制操作，即是所谓的浅拷贝，两个对象的指针式一样的值，指向同一块内存区。
这种情况下，当一个对象删除其成员指针指向的内存区后，另一个对象的指针成员指向的内存区也就被释放了。
如果第一个对象析构时删除了这个内存区，那么在第二对象析构时造成同一块内存多次被释放，程序崩溃。
解决这个问题有常规上有两种方法
一是，进行深拷贝，在拷贝构造函数和复制运算符中进行相应的内存分配和复制工作。析构的时候只是各自析构各自的。
二是，采用引用计数手段，在拷贝构造函数和复制运算符中对引用计数进行分析，多个复制对象的指针成员只指向同一个内存区，在最后一个对象析构的时候才最终将这个内存区释放掉。
引用计数的好处是，可以节省内存分配、拷贝、内存释放所带来的效率消耗，以及节省内存。
http://www.cppblog.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 阅读(264) |
评论 (0) |
编辑 收藏第一个只出现一次的字符
一个字符串中，查找其中第一个只出现一次的字符。
这里建设这个字符串中的字符可以使英文大小写字符也可以是数字字符。
http://www.cppblog.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 阅读(303) |
评论 (0) |
编辑 收藏从上向下遍历二叉树
树的层次遍历
图的广度遍历
首先是要定义二叉树节点的结构体
建立二叉树
层次遍历，需要一个队列辅助
建立一棵二叉树
递归的前序、中序、后序遍历
层次遍历
http://www.cppblog.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 阅读(162) |
评论 (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 阅读(330) |
评论 (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.cppblog.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 阅读(84) |
评论 (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 阅读(344) |
评论 (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 阅读(148) |
评论 (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 阅读(184) |
评论 (0) |
编辑 收藏