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
头文件 #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))

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

相比分配一整块内存 缺点是效率问题 参考这个
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
http://blog.csdn.net/hnust_xiehonghao/article/details/7942541
http://blog.csdn.net/longshengguoji/article/details/8546286
输出的地方要特别注意一下 定义一个printSet 里面通过迭代器来进行操作
注意set使用到的题目做的还不是很多 set与multiset通过底层是红黑树
只要使用好了 往往能省好多事
比如 Contains Duplicate III 这个题

关于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
关于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()
如果查询成功会返回一个迭代器,这个迭代器又有两个元素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;

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
26
27
#include 
#include
#include
#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的相关操作

推荐文章