函数指针

函数指针是指向函数的指针变量。 因而“函数指针”本身首先应是指针变量,只不过该指针变量指向函数。这正如用指针变量可指向整型变量、字符型、数组一样,这里是指向函数。如前所述,C在编译时,每一个函数都有一个入口地址,该入口地址就是函数指针所指向的地址。有了指向函数的指针变量后,可用该指针变量调用函数,就如同用指针变量可引用其他类型变量一样,在这些概念上是一致的。函数指针有两个用途:调用函数和做函数的参数。

阅读全文

poj: 3253-Fence Repair

##Description

Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the “kerf”, the extra length lost to sawdust when a sawcut is made; you should ignore it, too.

阅读全文

STL中的priority_queue

如果碰到需要使用优先级序列的时候,可以不用自己去实现,使用STL中的便是,
STL其它还提供了许多有用的工具,要善加利用。

下面是C++ Reference中priority_queue的使用的例子,知道这些应该就够了:

1
2
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;

阅读全文

poj: 2431-Expedition

##Description

A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor drivers, the cows unfortunately managed to run over a rock and puncture the truck’s fuel tank. The truck now leaks one unit of fuel every unit of distance it travels.

阅读全文

标准类库中的sort()函数

由于有时候需要对数组啊之类的进行排序,那么是不是要自己动手写个快排呢,当然不是!

标准类库中自带一个很强大的sort()函数,在Expedition一题中,就用到了sort()。

下面是c++ Reference中sort()的一些用法,应该足够用了吧。

阅读全文

set & map

###1.set

如果需要使用二叉搜索树时,可以不用自己来实现,用STL中的set就可以。

使用set的话必须包含set的头文件。

set的操作如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main() {
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
ivec.push_back((int)i);
ivec.push_back((int)i); // duplicate copies of each number
}
// iset holds unique elements from ivec
set<int> iset(ivec.begin(), ivec.end()); //初始化操作,也可以直接申明,而不初始化
cout << ivec.size() << endl; // prints 20
cout << iset.size() << endl; // prints 10,set中都是唯一的键值
iset.insert(11); //insert操作
set<int>::iterator set_it;
set_it = iset.find(1); // returns iterator that refers to the element with key == 1
if (set_it != iset.end()) cout<<"found"<<endl;
else cout<<"not found"<<endl;
set_it = iset.find(12); // returns iterator == iset.end()
if (set_it != iset.end()) cout<<"found"<<endl;
else cout<<"not found"<<endl;
cout<<iset.count(1)<<endl; // returns 1
cout<<iset.count(12)<<endl; // returns 0
iset.erase(11); //erase 删除操作
for (set_it = iset.begin(); set_it != iset.end(); set_it++) {
cout<<*set_it<<endl;
}
}

阅读全文

动态规划: Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

阅读全文

动态规划: Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by
deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:

S = "rabbbit", T = "rabbit"

Return 3.

阅读全文

DFS: 部分和问题与01背包

###部分和问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
此题见于挑战程序设计竞赛书30页
给定整数 a 1 、a 2 、…、a n ,判断是否可以从中选出若干数,使它们的和恰好为 k。
*/
#include <iostream>
using namespace std;
const int MAX_N = 20;
int a[MAX_N];
int k;
/*
此题为经典的深度优先搜索,特征就是一个问题共分几步,每步都有几种可能,
我们可以通过递归来实现这样的问题
这种方法的一个缺点就是时间复杂度很高,为O(2^n),只适合解决规模较小的问题
*/
bool rec(int i, int j) {
bool res = false;
if (i == n) {
if (j == 0) {
res = true;
}
} else if (j < a[i]) {
res = rec(i + 1, j);
} else {
res = rec(i + 1, j) || rec(i + 1, j - a[i]);
}
return res;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin>>a[i];
}
cin>>k;
if (rec(0, k)) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
}

阅读全文

动态规划: Decode Ways

A message containing letters from A-Z is being encoded to numbers using the >following mapping:

'A' -> 1

'B' -> 2

...

'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

阅读全文