逆序数的计算
常规的做法
时间：O(N^2)
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 int foo(const vector<int>& array)
6 {
7 int ret = 0;
8 for (vector<int>::size_type i = 0; i != array.size() - 1; ++i)
9 {
10 for (vector<int>::size_type j = i + 1; j != array.size(); ++j)
11 {
12 if (array[i] > array[j])
13 {
14 ++ret;
15 }
16 }
17 }
18 return ret;
19 }
20
21 int main()
22 {
23 vector<int> array;
24
25 for (int i = 10; i > 0; --i)
26 {
27 array.push_back(i);
28 }
29 cout << foo(array) << endl;
30 return 0;
31 }
改进的做法
利用分治法，借助归并排序求解逆序数。
时间复杂度：O(NlogN)
在归并排序的基础做一个修改即可：
不是算右边的相对左边的逆序数，这样太过于繁杂
而是算左边相当于右边的逆序数，这样可以就在这一个地方做统一处理
即当检测到左边大于右边的时候，则所有剩下的左边的数都相对于当前右边的数大，所以逆序数都要加 1 。
count += (end1 - begin1 + 1);
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstring>
4 using namespace std;
5
6 int count = 0;
7
8 void merge(int array[], int low, int mid, int high)
9 {
10 int i, k;
11 int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
12 int begin1 = low;
13 int end1 = mid;
14 int begin2 = mid + 1;
15 int end2 = high;
16
17 for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
18 if(array[begin1]<=array[begin2])
19 {
20 temp[k] = array[begin1++];
21
22 }
23 else
24 {
25 //++count;
26
27 // 不是算右边的相对左边的逆序数，这样太过于繁杂
28 // 而是算左边相当于右边的逆序数，这样可以就在这一个地方做统一处理
29 count += (end1 - begin1 + 1);
30 temp[k] = array[begin2++];
31 }
32 if(begin1 <= end1) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾
33 {
34 memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
35 //count += (end1 - begin1 + 1) * (high - mid);
36 }
37 if(begin2 <= end2) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾
38 memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
39 memcpy(array+low, temp, (high-low+1)*sizeof(int));//将排序好的序列拷贝回数组中
40 free(temp);
41 }
42
43 int merge_sort(int array[], unsigned int first, unsigned int last)
44 {
45 int mid = 0;
46 if(first<last)
47 {
48 mid = (first+last)/2;
49 merge_sort(array, first, mid);
50 merge_sort(array, mid+1,last);
51 merge(array,first,mid,last);
52 }
53 return count;
54 }
55
56
57 int foo(int array[], int n)
58 {
59 return merge_sort(array, 0, n - 1);
60 }
61
62 int main()
63 {
64 int array[] = {9, 10, 8, 7, 6, 5, 4, 3, 2, 1, 0};
65 // int array[] = {1, 3, 2, 4, 3};
66 // int array[] = {1, 3, 2};
67 cout << foo(array, sizeof (array) / sizeof (*array)) << endl;
68 return 0;
69 }
http://www.cnblogs.com/dskit/archive/2009/12/16/1625942.html
http://hi.baidu.com/xiaohanhoho/blog/item/277a09392a0e4722b8998fdc.html
http://www.cppblog.com/asp/articles/14261.html
http://www.cublog.cn/u2/62093/showart_484338.html
http://blog.csdn.net/guzhilei1986/archive/2008/04/10/2276782.aspx
posted @
2011-06-22 01:11 unixfy 阅读(547) |
评论 (0) |
编辑 收藏归并排序是稳定的
时间复杂度：O(NlogN)
空间复杂度：O(N)
合并 + 递归
http://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
http://baike.baidu.com/view/90797.htm
http://sjjg.js.zwu.edu.cn/SFXX/paixu/paixu6.5.1.html
http://www.zjhyzx.net/Article/ShowArticle.asp?ArticleID=924
http://learn.akae.cn/media/ch11s04.html
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.5.1.1.htm
1 #include <iostream>
2 #include <cstdlib>
3 #include <cstring>
4 using namespace std;
5
6 void merge(int array[], int low, int mid, int high)
7 {
8 int i, k;
9 int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
10 int begin1 = low;
11 int end1 = mid;
12 int begin2 = mid + 1;
13 int end2 = high;
14
15 for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
16 if(array[begin1]<=array[begin2])
17 temp[k] = array[begin1++];
18 else
19 temp[k] = array[begin2++];
20 if(begin1 <= end1) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾
21 memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
22 if(begin2 <= end2) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾
23 memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
24 memcpy(array+low, temp, (high-low+1)*sizeof(int));//将排序好的序列拷贝回数组中
25 free(temp);
26 }
27
28 void merge_sort(int array[], unsigned int first, unsigned int last)
29 {
30 int mid = 0;
31 if(first<last)
32 {
33 mid = (first+last)/2;
34 merge_sort(array, first, mid);
35 merge_sort(array, mid+1,last);
36 merge(array,first,mid,last);
37 }
38 }
39
40 int main()
41 {
42 int a[8] = {4, 7, 5, 3, 2, 8, 6, 1};
43 for (int i = 0; i != 8; ++i)
44 {
45 cout << a[i] << ' ';
46 }
47 cout << endl;
48 merge_sort(a, 0, 7);
49 for (int i = 0; i != 8; ++i)
50 {
51 cout << a[i] << ' ';
52 }
53 cout << endl;
54 }
posted @
2011-06-22 00:13 unixfy 阅读(110) |
评论 (0) |
编辑 收藏基数排序、桶排序
这里介绍一下非比较排序
头绪比较乱
编程珠玑 I 第一节中就讲到一种排序方法：大批量的数排序，内存有限，利用 bitmap 可以很好的解决。时间为 O(N) 。
对于不重复出现的数的集合，也就是说对于某个数最多只出现一次。可以利用 bitmap 来解决。因为一个 bit 只有两个状态： 0 和 1 。
1.
对于重复出现的数，可以利用一般类型数组来解决。对于每个数，以每个数为索引，记录以该索引的元素自加 1 。处理完后，扫描这个辅助数组，将记录的信息，也就是索引的次数，把索引以次数存入原来数组中。
2.
这种直接以待排序的数为索引，需要很大的辅助数组。所以可以利用针对待排序的数的每位来处理，每个位的范围也就是 0 - 9 十的大小。对于多维的待排序数处理方式有两种。即从左到右和从右到左。
从左到右：左面的排完序后，整体次序不变了，只是调整的次位的相对顺序。
从右到左：右面的排完序后，整体的次序还会有变化的，只不过是随着从右到左，依次调整的次数越来越少了。
3.
桶排序，对于一系列待排序数，可以先按照各个数的属性将所有数分配到各个桶里。这样后，对于每个桶里的数可以使用插入排序进行各个桶的排序。
1 #include <iostream>
2 #include <vector>
3 #include <cstring>
4 using namespace std;
5
6 void sort(vector<int>& array)
7 {
8 int temp[1000];
9 memset(temp, 0, sizeof (int) * 1000);
10 for (vector<int>::size_type i = 0; i != array.size(); ++i)
11 {
12 ++temp[array[i]];
13 }
14 array.clear();
15 for (int i = 0; i < 1000; ++i)
16 {
17 while (temp[i]-- != 0)
18 {
19 array.push_back(i);
20 }
21 }
22 }
23
24 int main()
25 {
26 vector<int> array;
27 for (int i = 0; i < 10; ++i)
28 {
29 array.push_back(i);
30 }
31 for (int i = 10; i >= 0; --i)
32 {
33 array.push_back(i);
34 }
35 sort(array);
36 for (vector<int>::size_type i = 0; i < array.size(); ++i)
37 {
38 cout << array[i] << ' ';
39 }
40 cout << endl;
41 return 0;
42 }
posted @
2011-06-21 22:45 unixfy 阅读(371) |
评论 (0) |
编辑 收藏排序的作用
几个问题
·删除数组中大于一定数的所有数
·查找少量数中重复出现的数
·在数组中找到两个等于一给定数的二元组
如何解决这些问题？
·排序，二分查找，删除
·排序，遍历
·排序，左右遍历检测，如果小向右走，如果大向左走
排序是基本的算法，到处都会用到。
解决问题的关键在于对处理对象进行调整。也就是做预处理工作。
posted @
2011-06-21 21:19 unixfy 阅读(216) |
评论 (0) |
编辑 收藏
之前读过间断读过两遍。
迫于找工作压力，现再次翻阅。
1. 让 CPU 占用率听你指挥
刷新周期
int main()
{
for (; ; )
{
for (int i = 0; i < 960000; ++i)
{
sleep(10);
}
}
}
while ((GetTickCount() - startTime) <= busyTime);
2. 中国象棋将帅问题
struct
{
unsigned char a : 4;
unsigned char b : 4;
} i;
i.a, i.b;
3. 一摞烙饼的排序
排序问题
每次找到最大的
4. 买书问题
贪心算法的反例
5. 快速找到出故障机器
ID
哈希表
<异或>
·0 保持
·1 取反
·A ^ A = 0
两个出问题，如果是不同的两个，可以解决，即是根据异或原理，把所有 ID 分成两部分，以某一位是 0 还是 1 分开。在分开的两部分中每个部分，采用异或的方法进行解决。
利用不变量进行解决
·加法不变量
·乘法不变量
·平方和不变量
6. 饮料供货
7. 光影切割问题
问题转换
逆序的分治计算方法
8. 小飞的电梯调度算法
直观暴力解法
N1, N2, N3
逐层遍历
9. 高效率地安排见面会
10. 双线程高效下载
·下载
·写入磁盘
11. NIM(1) 一排石头的排序
posted @
2011-06-20 16:23 unixfy 阅读(97) |
评论 (0) |
编辑 收藏字符串旋转问题
需要 O(N) 的时间，O(1) 的空间
借助字符串翻转
ABCEFG
((ABC)'(EFG)')'
=(CBAGFE)'
=EFGABC
对一个字符串，进行给定位置的逆转。
1 #include <iostream>
2 using namespace std;
3
4 void swap(char& a, char& b)
5 {
6 a ^= b;
7 b ^= a;
8 a ^= b;
9 }
10
11 void reverse(char* s, int l, int h)
12 {
13 while (l < h)
14 {
15 swap(s[l++], s[h--]);
16 }
17 }
18
19 int getLen(char* s)
20 {
21 int ret = 0;
22 while (*s++ != '\0')
23 {
24 ++ret;
25 }
26 return ret;
27 }
28
29 char* rotate(char* s, int pos)
30 {
31 int t = getLen(s) - 1;
32 reverse(s, 0, pos - 1);
33 reverse(s, pos, t);
34 reverse(s, 0, t);
35 return s;
36 }
37
38 int main()
39 {
40 char s[100];
41 int pos;
42 while (cin >> s >> pos)
43 {
44 cout << rotate(s, pos) << endl;
45 }
46 return 0;
47 }
http://www.cppblog.com/jake1036/archive/2011/03/05/141163.html
posted @
2011-06-17 22:58 unixfy 阅读(119) |
评论 (0) |
编辑 收藏
连续内存，溢出
1 #include <iostream>
2 using namespace std;
3
4 template <typename T>
5 class DoulStack
6 {
7 private:
8 T* data_;
9 int top1_;
10 int top2_;
11 unsigned size_;
12 public:
13 DoulStack(unsigned size = 1000) : data_(new T[size]), top1_(0), top2_(size - 1), size_(size)
14 {
15 if (data_ == 0)
16 {
17 exit(1);
18 }
19 }
20 DoulStack(const DoulStack& ds) : data_(new T[ds.size_]), top1_(ds.top1_), top2_(ds.top2_), size_(ds.size_)
21 {
22 if (data_ == 0)
23 {
24 exit(1);
25 }
26 memcpy(data_, ds.data_, sizeof (T) * ds.size_);
27 }
28 DoulStack& operator = (const DoulStack& ds)
29 {
30 if (this != &ds)
31 {
32 delete [] data_;
33 data_ = new T[ds.size_];
34 if (data_ == 0)
35 {
36 exit(1);
37 }
38 top1_ = ds.top1_;
39 top2_ = ds.top2_;
40 size_ = ds.size_;
41 memcpy(data_, ds.data_, sizeof (T) * ds.size_);
42 }
43 return *this;
44 }
45 ~DoulStack()
46 {
47 delete [] data_;
48 }
49 bool empty()
50 {
51 return empty1() && empty2();
52 }
53 bool full()
54 {
55 return top1_ - 1 == top2_;
56 }
57 bool resize(unsigned size)
58 {
59 T* temp = new T[size];
60 if (temp == 0)
61 {
62 exit(1);
63 }
64 for (int i = 0; i != top1_; ++i)
65 {
66 temp[i] = data_[i];
67 }
68 for (int i = size - 1, j = size_ - 1; j != top2_; --i, --j)
69 {
70 temp[i] = data_[j];
71 }
72 size_ = size;
73 delete [] data_;
74 data_ = temp;
75 }
76 void push1(const T& t)
77 {
78 if (full())
79 {
80 resize(size_ * 2);
81 }
82 data_[top1_++] = t;
83 }
84 void push2(const T& t)
85 {
86 if (full())
87 {
88 resize(size_ * 2);
89 }
90 data_[top2_--] = t;
91 }
92 void pop1()
93 {
94 --top1_;
95 }
96 void pop2()
97 {
98 ++top2_;
99 }
100 T top1()
101 {
102 return data_[top1_ - 1];
103 }
104 T top2()
105 {
106 return data_[top2_ + 1];
107 }
108 bool empty1()
109 {
110 return top1_ == 0;
111 }
112 bool empty2()
113 {
114 return top2_ == size_ - 1;
115 }
116 };
117
118 int main()
119 {
120 DoulStack<int> ds;
121 for (int i = 0; i < 10; ++i)
122 {
123 ds.push1(i);
124 ds.push2(9 - i);
125 }
126 while (!ds.empty1())
127 {
128 cout << ds.top1() << endl;
129 ds.pop1();
130 }
131 while (!ds.empty2())
132 {
133 cout << ds.top2() << endl;
134 ds.pop2();
135 }
136 cout << ds.empty() << endl;
137 }
posted @
2011-06-17 15:30 unixfy 阅读(143) |
评论 (0) |
编辑 收藏
摘要: 前缀匹配
网络层的数据报网络，在路由器转发功能实现中会用到前缀匹配，即是对 IP 地址与路由表中的目的地址范围的公共部分进行前缀匹配。由于有的前缀存在包含的问题，对有些 IP 地址会造成多重匹配，短的匹配会造成 IP 的转发错误。所以可以遵循 最长前缀匹配原则 进行匹配。
首先做一个 ip 转换的实现从 unsigned int 32 位整型数到 ip 字符串的转换从 ip 字符串到 unsi...
阅读全文
posted @
2011-06-17 14:36 unixfy 阅读(761) |
评论 (0) |
编辑 收藏
来自于《高质量程序设计指南——C++/C 语言》
实现类似 copy 的功能
1 #include <cstdio>
2 using namespace std;
3
4 int main(int argCount, char* argValue[])
5 {
6 FILE* srcFile = 0, *destFile = 0;
7 int ch = 0;
8 if (argCount != 3)
9 {
10 printf("Usage: %s src-file-name dest-file-name\n", argValue[0]);
11 }
12 else
13 {
14 if ((srcFile = fopen(argValue[1], "r")) == 0)
15 {
16 printf("Can not open source file \"%s\"!", argValue[1]);
17 }
18 else
19 {
20 if ((destFile = fopen(argValue[2], "w")) == 0)
21 {
22 printf("Can not open destination file \"%s\"!", argValue[2]);
23 fclose(srcFile);
24 }
25 else
26 {
27 while ((ch = fgetc(srcFile)) != EOF)
28 {
29 fputc(ch, destFile);
30 }
31 printf("Successful to copy a file!\n");
32 fclose(srcFile);
33 fclose(destFile);
34 return 0;
35 }
36 }
37 }
38 return 1;
39 }
posted @
2011-06-16 21:48 unixfy 阅读(112) |
评论 (0) |
编辑 收藏
找到 50 亿个 32 位整型数中出现重复的数。
可行的方法是利用位图。32 位数的范围是 0~2^32 - 1
开辟一个 2^32 个 bit 的空间，大小约为 512 MB。
一次扫描每一个数，检测以该数为索引的那个 bit 是否为 0 ，若为 0 ，则说明过去不存在，将其置为 1，如果为 1 则说明以前出现过，则说明该数是重复出现的。
这个问题解决的关键在于用待检测数去做索引，利用随即存取的特点，可以做到 O(1) 的效率。用数本身做索引是一种高效的方法。
1 #include <iostream>
2 #include <bitset>
3 #include <vector>
4 #include <cmath>
5 using namespace std;
6
7 void foo(const vector<int>& arr)
8 {
9 bitset<1024> bs;
10
11 for (vector<int>::size_type i = 0; i != arr.size(); ++i)
12 {
13 if (bs[arr[i]] == 0)
14 {
15 bs[arr[i]].flip();
16 }
17 else
18 {
19 cout << arr[i] << endl;
20 }
21 }
22 }
23
24 int main()
25 {
26 vector<int> arr;
27 for (int i = 0; i < 100; ++i)
28 {
29 arr.push_back(i);
30 }
31 arr.push_back(5);
32 arr.push_back(25);
33
34 foo(arr);
35 return 0;
36 }
关键在于这个位图如何实现。STL 中有个 bitset 就好可以做这个工作。
但是如果需要仔细实现一个该如何办？也就是说自己实现一个 bitset
实现一个类似的 bitset
http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.2/bitset-source.html
http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.2/bitset.html
http://blog.sina.com.cn/s/blog_4d3a41f40100kxnw.html
http://blog.sina.com.cn/s/articlelist_1295663604_0_1.html
更进一步学习 bitset ，《STL 源码剖析》中应该有所介绍
关键是对 bit 的读写如何操作。
1 #include <iostream>
2 #include <bitset>
3 #include <vector>
4 #include <cmath>
5 using namespace std;
6
7 template <unsigned NUM>
8 class MyBitset
9 {
10 private:
11 char* data_;
12 unsigned numbits;
13 unsigned numchars;
14 public:
15 MyBitset() : numbits(NUM), numchars(NUM / 8 + 1)
16 {
17 data_ = new char[numchars];
18 if (data_ == 0)
19 {
20 exit(1);
21 }
22 memset(data_, 0, numchars);
23 }
24 unsigned operator [] (unsigned pos)
25 {
26 char c = data_[pos / 8];
27 unsigned t = pos - pos / 8 * 8;
28 while (t > 0)
29 {
30 c <<= 1;
31 --t;
32 }
33 if (c & 128)
34 {
35 return 1;
36 }
37 else
38 {
39 return 0;
40 }
41 }
42 void set(unsigned pos)
43 {
44 char* p = data_ + pos / 8;
45 unsigned t = pos - pos / 8 * 8;
46 char temp = pow(2.0, 8.0 - t);
47 *p |= temp;
48 }
49 };
50
51 void foo(const vector<int>& arr)
52 {
53 // bitset<1024> bs;
54 MyBitset<1024> bs;
55
56 for (vector<int>::size_type i = 0; i != arr.size(); ++i)
57 {
58 if (bs[arr[i]] == 0)
59 {
60 // bs[arr[i]].flip();
61 bs.set(arr[i]);
62 }
63 else
64 {
65 cout << arr[i] << endl;
66 }
67 }
68 }
69
70 int main()
71 {
72 vector<int> arr;
73 for (int i = 0; i < 100; ++i)
74 {
75 arr.push_back(i);
76 }
77 arr.push_back(5);
78 arr.push_back(25);
79
80 foo(arr);
81 return 0;
82 }
posted @
2011-06-16 17:17 unixfy 阅读(487) |
评论 (2) |
编辑 收藏