Algorithm(1) tips in c/c++ algorithm questions

练习题目总是断断续续的,因此感觉从来也没有在某一个时间段内达到很高的水平,总是隔一段时间再做题有些基本的内容就忘记了(发人深思)。而且平时项目里用c/c++并没有那么频繁,有一些零零碎碎的操作不便于快速回忆,于是那些做题目时会用到的内容还是梳理在一起比较好,也相当于是一个系统整理了。

输入输出初始化相关

做pat的时候对于输入输出的要求比较严格,特别是对于输入输出的相关内容,但是letcode这里还好,只是写函数就行,要自己声明class 之后在class中实现对应的方法,总之两种模式都要很好的掌握,因为不知道笔试面试时候的oj会是哪一种。

  • while(scanf(“%d”,&n)!=EOF){}这个基本上是pat里面开始的时候数据输入的基本模式了,这里就是从标准输入输入一个整数到变量n中,要是格式化的输入,比如一行中多个数字,写成scanf(“%d %d %d”,&a,&b,&c)这样。
  • scanf(“%c”,&c) 从标准输入输入字符到变量c中
  • 对于那种测试用例会循环出入的情况,pat中的那种,可以用一个getchar()将多余的回车符吸收掉,特别是与gets(str)一起使用的时候。但是连续使用scanf就并不会存在这种问题,scanf本身会忽略掉前面输入的最后一个回车符。
  • 采用scanf输入 scanf(“%s”,str)输入遇到空格会被认为是当前字符串结束,要是使用gets(str)的话,会一直默认读取到正行的末尾才结束(遇到换行为止),即使中间有空格。
  • sscanf 在一些情况下也有很好的使用,比如下面场景,需要读取矩阵,每行的元素可能是两个也可能是三个,如果是两个的话,value就为default这个时候就要同时支持两个或者3个值的读入,可以使用 buffer + sscanf 的操作,sscanf会返回一个int,标记到底几个值读取成功。一段示例代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    char line[256];
    if (fgets(line, sizeof(line), f) != NULL)
    {
    if (sscanf(line, "%d %d %lg", &rIndex[i], &cIndex[i], &tmp) == 2)
    {
    tmp = 1;
    }
    }
  • c++ 里面输出bool的时候 直接是 0 1 类型的

  • 数组初始化的多种方式,直接使用中括号,或者使用memset int a[260] = {0};int b[260];memset(b,0,sizeof(b));
  • 数字转化为字符串 sprintf(s, “%d”, 123); 可以把数字 123 转化为 字符串123注意sprintf对应的头文件为cstdio
  • 注意字符串转化为数字的操作,直接用cstdlib中的atoi函数就可以进行操作。但是把string类型的数据转换为int类型的时候,需要这样操作int result = atoi(s.c_str());因为atoi这个函数的声明方式如下int atoi(const char *nptr);,所以要用到string转数组的操作。
  • pat那种读入文件用例的技巧 测试用例 以及 main函数都需要自己写 这个时候最好是通过一个文件的形式把每次的测试用例读进来 这样可以避免每次手工重新输入
  • pat那种题目 需要从文件中读取进来多个测试用例的情况 记住在main函数开始的时候freopen("in.txt","r",stdin);注意 在多组输入的时候 每次在while开始的时候 记得把相关的实例都清空 比如vector以及map相关的实例 在while循环多次的时候 不要把旧的信息也给带上去
  • 在niucode上面或者leetcode上面,需要每次提交的是第一个class然后把方法写在class中,注意在自己写main文件的时候,先声明一个类,然后再调用其中的public 方法。比如 classinstance 之后 classinstance.这样进行操作。至于在声明的的时候加不加new,可以参考这个http://www.cnblogs.com/frustrate2/archive/2012/08/14/2637475.html。
  • using namespace std 在有一点紧张的时候,总是忘记这个的输入

//http://blog.csdn.net/cogbee/article/details/8931838 chr* char[] stirng
//http://stackoverflow.com/questions/10186765/char-array-vs-char-pointer-in-c

//http://zhidao.baidu.com/link?url=xf4JoYof1TJ0GG0QsW_qsEIxvdRQCtG8TOn0ZT7ikSB7qN7JQbULPSqpe0wuxhiFUflCOmN50Xpblrhetk-RmK

  • 设置MAX_NUM的时候可以采用如下操作,instead of using 999999.
1
2
#include <limits.h>
int x = INT_MAX;
  • 善于使用sprintf,特别是在字符串需要按照特定的方式拼接然后再进行输出的时候,比如输入的是hour与minutes,输出的是按照特定格式返回的字符串,此时就需要灵活地才用sprintf将多个输入的字符串按照指定的格式要求拼接起来。

关于头文件

常用的要记住的如下

1
2
3
4
5
6
7
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> //sort之类的排序要用到
#include <vector>
#include <queue>
#include <map>

基本结构及其常用方法

队列模板的使用

1
2
3
4
5
6
7
头文件 #include<queue>
queue<Node> Q 声明一个Node类型的队列
Q.push(arrynode[i]) arrynode中的第i个元素入队
Q.front()返回队头元素(在BFS的时候pop与front往往是结合起来使用)
Q.pop() 弹出对头元素 直接队首元素出队 并不返回元素
Q.empty()判断队列是否为空
Q.size()返回队列中元素的数目 (注意这里的括号)

关于双端队列

1
2
3
4
5
6
7
8
#include<deque>
deque<int> d
d.push_back(value)
d.push_front(value)
d.pop_back(value)
d.pop_front(value)
d.back() //return last element
d.fron() //return first element

vector向量的使用

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
头文件 #include<vector>
vector<type>v 定义一个type类型的向量
v[i]通过下标返回第i个元素
v.front()获取并返回首元素
v.back()获取并返回尾元素
v.push_back(x) 向尾部插入元素x(注意这里要使用push_back而不是insert)
v.pop_back()删除尾元素
v.size()获取并返回v的长度
v.empty()判断v是否为空 若空则返回true 否则返回false
v.clear()清空
vector<int>::iterator == find(A.begin(),A.end(),3);查找标记为3的元素是否包含在向量中
要注意一下这里的find是alogrithom的方法 并不是vector中自带的方法
http://blog.csdn.net/helonsy/article/details/6859075
vc 6.0中查看vector中的元素的方法:
http://blog.sina.com.cn/s/blog_70441c8e0101hjtl.html

关于vector中元素的复制:
1、vector是一个构造对象,不能直接使用=符号进行复制,必须迭代每个元素来复制。或者重载=操作符。
2、大致有一下几种方法实现用于把一个vector复制给另一个vector:
方法1:
vector<int > v1(v2);//声明
方法2:使用swap进行赋值:
vector<int > v1();v1.swap(v2);//将v2赋值给v1,此时v2变成了v1
方法3:使用函数assign进行赋值:
vector<int > v1;//声明v1
v1.assign(v2.begin(), v2.end());//将v2赋值给v1
方法4:使用循环语句赋值,效率较差
vector<int >::iterator it;//声明迭代器
for(it = v2.begin();it!=v2.end();++it){//遍历v2,赋值给v1
v1.push_back(it);
}

vector类型可以支持嵌套 即使说vector里面的每一个元素 又是一个vector
比如这样 vector<vector<int> > shortestPaths;
注意后面两个>> 要用 “ ”分割开 否则会被识别成右移符号

对vector进行遍历:
http://www.2cto.com/kf/201404/291689.html

vector嵌套操作的时候进行初始化 初始化都是0
vector< vector<int> > dp(row,vector<int>(line))

vector init by the {} notation, this is convenience for writing the test case
std::vector<std::vector<int>> grid{{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
we can also inter the empty vector by using {} direactly

注意整理行和列要是确定了之后才能进行如下操作

相比分配一整块内存 缺点是效率问题 参考这个
https://scicomp.stackexchange.com/questions/3159/is-it-a-good-idea-to-use-vectorvectordouble-to-form-a-matrix-class-for-high/3162

使用vector之后空间就不连续了

但这样做的方便之处就是可以控制所分配的空间的大小 而不用在开始的时候就确定好空间的大小
比如如下的代码
scanf("%d\n", &n);
std::vector<std::vector<int> > matrix(3, vector<int>(n,0));
在读入了n之后才初始化vector并分配对等大小的空间,但这样做确定是空间是不连续的,在对performance要求敏感的代码上需要进一步进行优化。

还有就是注意嵌套vector的时候 里面的元素中的template部分仅仅是一个字段 不要和map弄混淆了

声明一个维vector时候参数的初始化
vector fvec(10);
// 10 elements, each initialized to 0
vector ivec4(10, -1);
// 10 elements, each initialized to -1
向量使用sort排序
http://blog.csdn.net/hnu_zxc/article/details/6746029
注意!!!如果写成class的形式的话 并且把cmp函数写在class内部 那cmp一定要写成 static 的形式 否则编译器会找不到sort函数 认为它是被重载过了的
sort (myvector.begin(), myvector.end(), cmp);
在struct中包含vector:
struct DataItem
{
int start;
int end;
int weight;
int flag;
struct DataItem *next;
};
typedef struct HeadNode
{
int maxweight;
vector<struct DataItem *> edgeV;
} HeadNode;
int main()
{
vector<struct HeadNode *> HashArray;
int i;
for (i = 0; i < 11; i++)
{
vector<struct DataItem *> ev;
struct DataItem *item = (struct DataItem *)malloc(sizeof(struct DataItem));
item->start = i + 1;
item->end = i + 1;
item->weight = 1;
item->flag = 0;
item->next = NULL;
ev.push_back(item);
HeadNode *node = new (HeadNode);
node->edgeV = ev;
node->maxweight = i;
HashArray.push_back(node);
}
}
这里要注意如下:
* vector 是c++才支持的,因此初始化struct的instance的时候,一定要用new而不是malloc,由于习惯问题,常常一上手就用malloc,这样会导致vector中的值发生一些奇怪的变化,这种问题往往还特别难定位,都是由于惯性思维导致的。注意上下文环境,从而做出正确的选择。
* 再一个结构体定义的时候还是都按照c++的风格来吧,c的风格就是感觉很冗余。


关于iterate的同时又进行删除的操作, 主要是采用erase返回iterator的做法

auto iter = a.begin();
while (iter != a.end()) {
if (*iter > 30) {
iter = a.erase(iter);
}
else {
++iter;
}
}

还有另外一种操作是

for ( ; it != res.end(); ) {
if (condition) {
it = res.erase(it);
} else {
++it;
}
}

关于set容器

1
2
3
4
5
6
7
8
http://blog.csdn.net/hnust_xiehonghao/article/details/7942541
http://blog.csdn.net/longshengguoji/article/details/8546286
输出的地方要特别注意一下 定义一个printSet 里面通过迭代器来进行操作
注意set使用到的题目做的还不是很多 set与multiset通过底层是红黑树
只要使用好了 往往能省好多事
比如 Contains Duplicate III 这个题
set 中的元素默认是ascending排列的
set 与 multiset 的关键区别是集合中是否可以包含重复的元素

关于string的操作

string输入 每次使用string的时候 总是很焦虑 因为输入总是搞不好 其实很容易

参考这个,关键是风格的统一:

http://blog.sina.com.cn/s/blog_7044b2550100p4ao.html

1
2
3
4
5
6
7
8
C语法:
char buf[20]; gets(buf); 可以用scanf("%s",buf)进行输入
C++语法:
如果用string buf;来保存:
getline(cin,buf);(推荐)
由于在做题的时候 大多是情况都是混合风格 对于用惯了scanf的那种多个输入值的循环判断风格 之后再判断是不是结束的时候 可以通过buf的长度来进行判断
如果buf.size()==0说明输入的是一个空字符串 这个时候就break出循环
如果用char buf[255]; 来保存: cin.getline( buf, 255 );

在一个很长的串中vector words,根据某个标记进行分割,把这个完整的串分割成几个小部分,把每一个分割出来的部分存在一个vector当中,这个操作可能会常常用到,总之要熟练使用,下面这个是以” “为例进行分割。

1
2
3
4
5
6
7
8
9
10
11
vector<string> words;
int leftIdx = 0;
int rightIdx = 0;
while (rightIdx < str.size())
{
while (rightIdx < str.size() && str[rightIdx] != ' ')
rightIdx++;
words.push_back(str.substr(leftIdx, rightIdx-leftIdx));
leftIdx = rightIdx+1;
rightIdx = rightIdx+1;
}

注意这里的substr要特别留意一下,主要是两个参数的含义,第一个参数为子数组的起始位置,第二个参数是字数组的长度,就是从起始位置开始,往后延伸多少个数字。(之前有一次机试的时候 把这里理解成了右边界 导致浪费了很多时间调试 这些小地方一定要注意)

有时可能会用到string转化成为字符串数组的操作:

string 是c++标准库里面其中一个,封装了对字符串的操作
把string转换为char* 有3中方法:
1.data

1
2
string str="abc"; 
const char *p=str.data();

2.c_str

1
2
string str="gdfd"; 
char *p=str.c_str();

比如在使用atoi函数将一个string类型的字符串转化为int类型的时候,就需要用这个操作。
还要注意下c_strdata的区别,data()函数返回的内容没有以\0结尾,而c_str()返回的是str,并且以\0结尾
3.copy
比如

1
2
3
4
5
string str="hello"; 
char p[40];
str.copy(p,5,0); //这里5,代表复制几个字符,0代表复制的位置
*(p+5)='/0'; //要手动加上结束符
cout <<p;

string扩容,如果对于原来的string直接进行操作的话,直接.resize()这样就好。

要是在后面继续添加元素,直接:
添加元素 直接 string s=”abc” s=s+”new string” 这样就可以

char* char[] string 三者的相互转化

以下是一个三种不同类型的元素进行转化的例子

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
50
51
52
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main()
{
printf("-----------char* to char[] and string----------\n");
//char *¡¡to char[]
char * sptr="hello world";
printf("sptr output: %s\n",sptr);
char charstr[20];
strcpy(charstr, sptr);
printf("charstr output: %s\n",charstr);
//char* to string
string s =sptr;
//error
//printf("string output: %s\n",s);
printf("string output: %s\n",s.c_str());
printf("string output: %s\n",s.data());
printf("-----------char[] to char* and string----------\n");
//char[] to char *
char chararry[20]="hello world";
printf("chararry output: %s\n",chararry);
sptr=chararry;
printf("sptr output: %s\n",sptr);
//char[] to string
s=chararry;
printf("string output: %s\n",s.c_str());
printf("-----------string to char* and char[]----------\n");
s="goodbye world!";
//invalid conversion from const char * to char*
//sptr=s.data();
const char* csptr;
csptr=s.data();
printf("csptr output: %s\n",csptr);
strcpy(chararry,csptr);
printf("chararry output: %s\n",sptr);
int len=strlen(chararry);
printf("the len of chararry: %d\n",len);
int len2=s.length();
/*
failed to sort
const char * temp=s.data();
sort(temp,temp+len2);
printf("string output after sort: %s\n",s.data());
*/
sort(chararry,chararry+len);
printf("chararry output after sort: %s\n",chararry);
return 0;
}

array 退化为指针的操作

1
2
3
4
5
6
//如果函数期望输入的形参是一个指针 但是传入的是一个数组
char s[10] = "hello";
printSomething(s);
//编译器会认为实际输入的内容如下
char s[10] = "hello";
printSomething(&s[0]);

实际刷题时候的tips
因为涉及到函数的调用与返回值,所以char 类型总是难以避免的,一种是直接使用 char + string 类型解决问题,一种是使用 char* + char[] 类型解决问题,总是不要混用,大部分刷题时用到的功能,使用str类的函数都可以解决的,比如strlen求字符串的长度以及 strcpy进行数组元素的拷贝。除了按照指定元素分割这个需要自己实现之外,其他的基本上都可以满足了,千万不要在这种小的地方耗费时间进去。

有一些地方是string无法解决的,因为s.data()返回的是const char 所以不能修改其元素?,所以要是想进行sort操作的话,还是需要转化为array类型,char 类型想要转化为array类型,还是需要用到strcpy赋值一遍过去!!!

map常用操作

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
关于map的一些常用操作(关键时候这个还是很好用的) 
比如一个map<String,int>
插入或者检索某个元素的时候 直接map[str]=number就OK了 还是比较好用的
元素查找
map.find(key)
返回的是迭代器 如果没有 就返回 map.end() 注意这里迭代器形式的书写
// 定义一个迭代器
map<int,int>::iterator iter
// 进行查找
iter = mapStudent.find(1);
if(iter != mapStudent.end())
{
// map 迭代器的第一个值为key 第二个值为value
Cout<<”Find, the value is ”<<iter->second<<endl;
}
else
{
Cout<<”Do not Find”<<endl;
}

char数组转化成string 这个比较好用(这个很关键 因为map声明的时候 只是支持string类型的 而精细控制的时候用字符串数组又比较好 所以输入的时候可以用字符串数组 最后声明map的时候再转化为string类型)
map.insert(make_pair(string(字符串数组),value))
注意前面的make_pair的操作
或者直接 <mapneme>[key]=value 采用这种直接添加 key-value 值的形式定义
map的操作好好整理一下:
http://www.oschina.net/question/234345_48876
map.find(key)操作会在map中查询key值如果查询失败会返回map.end()
a simple way to adjust if a specifc value is in map is to use the m.count(key) to adjust if the return value is 0
如果查询成功会返回一个迭代器,这个迭代器又有两个元素iterator->first和iterator->second两个元素分别代表 关键字 以及 实际存储的数据(即value值)
清空map中的元素
map.clear()
关于map的遍历操作:
http://blog.csdn.net/windren06/article/details/8141921
map<string,int>::iterator it;
for(it=m.begin();it!=m.end();++it)
cout<<"key: "<<it->first <<" value: "<<it->second<<endl;
return 0;

another important fact that the default value of the coresponding type will be returned if the key not exist in the map, for the following code, the output vlaue is 0:

std::map<int , int > m;
int b = m[1];
std::cout << a << std::endl;

stack的常用操作

具体题目 队列和栈相关的的那个章节中 获取最小值的栈

1
2
3
4
5
6
7
8
9
10
11
12
13
//像stack这种操作 肯定是不需要自己实现的
//在做题目的时候 学会直接利现成的操作
//栈的初始化操作
stack <int> stacktest
//判断一个栈在开始的时候是否为空 如果为空 则返回true
//注意 在初始的时候对于 stack 是否为空的判断是特别关键 并且容易出错的
stacktest.empty()
//push一个元素
stacktest.push(<intvalue>)
//pop一个元素
stacktest.pop
//返回栈的top元素
stacktest.top()

其他零零碎碎的

在letcode里面和pat不一样,通常只需要自己写一个完整的函数就好,不用考虑输入输出的问题,注意c++的面向对象的写法,一个class里面声明一个public 方法,main函数相当于是自己写的一个测试用例了。

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
#include 
...
#include
using namespace std;
class Solution {

int findsolution(int left,int right,int nowindex,int sum,vector &v){
...

}
public:
int threeSumClosest(vector& nums, int target) {
...
int min=findsolution(i+1,len-1,i,target,nums);
...
};
int main(){

Solution s;
vector v;
int answer;

int a[4] = {-1,2,1,-4};
int i;
for (i=0;i<4;i++){ v.push_back(a[i]);="" }="" answer="s.threeSumClosest(v,1);" printf("%d",answer);="" return="" 0;="" <="" code="">

在parallel 中的 windows下 fn+ALT+f5 那样来调试 f8是调整格式

关于编译器的使用

在codeblock的时候 要新建 terminal project 之后才能在新建的source文件中继续执行debug的相关操作

推荐文章