刷题笔记

c++和java刷题中一些函数和用法的整理,包括一些模板,目前是为了应付机试

C/C++

  • 可以代替所有include的操作
1
2
3
//即其他所有include操作都不用写了
#include <bits/stdc++.h>
using namespace std;
  • 遍历字符串的每个字符
1
2
3
for(int i=0;i<n.length();i++){
cout<<n[i]<<"\t";
}
  • 将字符转化为int型整数

count=n[i]-'0';

  • 用printf(“%f”,a)输出float或者double数字时,会携带很多的0,用cout输出就没有

  • 控制程序循环输入

1
2
3
while(scanf("%d",&n)!=EOF){
printf("\n");
}
  • 以两种方式定义sort函数

1.直接定义一个比较函数,然后在sort函数的参数中将其调用

1
2
3
bool cmp(const int & A, const int & B){
return A>B; //如果修改为return A<B就还原为了升序排列
}

调用时sort(save,save+n,cmp); //对原数组进行降序排序

当cmp返回true的时候,表示cmp第一个参数排在第二参数前面。

2.重载运算符

1
2
3
4
5
6
7
8
9
10
11
struct E{
char name[100];
int age;
int score;
bool operator < (const E &b) const{
int temp = strcmp(name,b.name);
if(score!=b.score) return score<b.score;
else if(temp!=0) return temp<0;
else return age<b.age;
}
}buf[1000];
  • 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
1.strcmp()
//strcmp用来比较两个字符数组(字符串)的大小
//若参数1>参数2,返回正数;若参数1<参数2,返回负数;若参数1=参数2,返回0
if(strcmp(str1,str2) == 0){
printf("str1 equals str2!");
}
2.replace()
//(1)用str替换指定字符串从起始位置pos开始长度为len的字符
string& replace (size_t pos, size_t len, const string& str);
str.replace(str.find("a"),2,"#");
//(2)用str替换 迭代器起始位置 和 结束位置 的字符
string& replace (const_iterator i1, const_iterator i2, const string& str);
str.replace(str.begin(),str.begin()+5,"#");
//(3)用substr的指定子串(给定起始位置和长度)替换从指定位置上的字符串
string& replace (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen);
str=str.replace(0,5,substr,substr.find("1"),4); //用substr的指定字符串替换s
3.reverse() //反转字符串
//(1)对于用char定义的字符串,使用string.h中的strrev函数
//(2)对于string类型的,使用algorithm中的reverse函数
reverse(a.begin(),a.end());
4.substr(pos,n) //提取从pos开始长度为n的字符串
  • string与int的转化
1
2
3
4
5
6
//int转化为string
char *itoa( int value, char *string,int radix);
//value:欲转换的数据; string:目标字符串的地址; radix:转换后的进制数,可以是10进制、16进制等; 返回指向string这个字符串的指针
//string转化为int(long)
int i = static_cast<int>(strtol(s.c_str(),&end,16));
  • 生成随机数
1
2
3
4
5
6
7
8
srand((unsigned)time(NULL));
for(int i=0;i<10;i++){
printf("%d",rand() % 2); //[0,1]
}
printf("\n");
for(int i=0;i<10;i++){
printf("%d",rand() % 5 + 3); //[3,7]
}
  • 以固定的格式输出字符串
1
2
3
4
//例如输出二位数字,即1要输出01
printf("%02d",i);
//保留三位小数
printf("%.3f",pi);
  • 几种常见的输入字符串方式

scanf("%s",str);

cin>>str;

getline(cin,broken); (这种方式可以一次输入一行,以换行符为输入结束单位,中间可以包含空格)

  • 使用malloc函数为链表节点分配内存空间
1
2
3
4
5
//C
int *p = (typename*)malloc(sizeof(typename));
//C++
int *p = new int[10000];
  • 优先队列(堆)
1
2
3
4
5
6
#include <queue>
priority_queue<int> Q; //默认是大根堆
priority_queue<int, vector<int>, greater<int> > Q; //小根堆
Q.push(i);
int x = Q.top();
Q.pop();
  • 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
a.assign(b.begin(), b.begin()+3); //b为向量,将b的0~2个元素构成的向量赋给a
a.assign(4,2); //是a只含4个元素,且每个元素为2
a.back(); //返回a的最后一个元素
a.front(); //返回a的第一个元素
a[i]; //返回a的第i个元素,当且仅当a[i]存在
a.clear(); //清空a中的元素
a.empty(); //判断a是否为空,空则返回ture,不空则返回false
a.pop_back(); //删除a向量的最后一个元素
a.erase(a.begin()+1,a.begin()+3); //删除a中第1个(从第0个算起)到第2个元素,也就是说删除的元素从a.begin()+1算起(包括它)一直到a.begin()+3(不包括它)
a.push_back(5); //在a的最后一个向量后插入一个元素,其值为5
a.insert(a.begin()+1,5); //在a的第1个元素(从第0个算起)的位置插入数值5,如a为1,2,3,4,插入元素后为1,5,2,3,4
a.insert(a.begin()+1,3,5); //在a的第1个元素(从第0个算起)的位置插入3个数,其值都为5
a.insert(a.begin()+1,b+3,b+6); //b为数组,在a的第1个元素(从第0个算起)的位置插入b的第3个元素到第5个元素(不包括b+6),如b为1,2,3,4,5,9,8,插入元素后为1,4,5,9,2,3,4,5,9,8
a.size(); //返回a中元素的个数;
a.capacity(); //返回a在内存中总共可以容纳的元素个数
a.resize(10); //将a的现有元素个数调至10个,多则删,少则补,其值随机
a.resize(10,2); //将a的现有元素个数调至10个,多则删,少则补,其值为2
a.reserve(100); //将a的容量(capacity)扩充至100,也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才显得有意义,因为这将避免内存多次容量扩充操作(当a的容量不足时电脑会自动扩容,当然这必然降低性能)
a.swap(b); //b为向量,将a中的元素和b中的元素进行整体性交换
a==b; //b为向量,向量的比较操作还有!=,>=,<=,>,<
vector<vector<int> > store(n); //定义一个长度为n的二维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
#include<math.h>
abs(); //绝对值函数
acos(); //反余弦函数
asin(); //反正弦函数
atan(); //反正切函数
exp(); //e的x次方
cos(); //余弦函数
sin(); //正弦函数
tan(); //正切函数
ceil(); //求不小于x的最小整数
cosh(); //求x的双曲余弦值
fabs(); //求浮点数x的绝对值
fmod(); //计算x/y的余数
frexp();//把浮点数x分解成尾数和指数
hypot();//对于给定的直角三角形的两个直角边,求其斜边的长度。
ldexp();//装载浮点数
log(); //e为底对数
log10();//10为底对数
modf(); //把数分为指数和尾数
pow(); //计算x的y次幂
sinh(); //求x的双曲正弦值
sqrt(); //开方
tanh(); //求x的双曲正切值

下面是一道求一个球的半径和体积

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
#include<math.h>
int main()
{
double pi=acos(-1),x1,x2,x3,y1,y2,y3,r,v;
while(scanf("%lf%lf%lf%lf%lf%lf",&x1,&x2,&x3,&y1,&y2,&y3)!=EOF)
{
r=sqrt(pow(x1-y1,2)+pow(x2-y2,2)+pow(x3-y3,2));
v=4*pi*pow(r,3)/3;
printf("%.3lf %.3lf\n",r,v);
}
return 0;
}
  • 日期问题
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
//问题描述:求两个给定日期的差值
//把问题统一到一个特定日期与一个原点日期的差值,当要求两个特定的日期之间的天数差时,我们只需要将它们与原点日期的天数相减,
//然后再将它们各自的天数差相减,就能得到它们之间的天数差
#include <stdio.h>
#define ISYEAP(x) x%100 != 0 && x%4 == 0 || x%400 == 0 ? 1:0 //判断是否是闰年
int dayofmonth[13][2]={
0,0,
31,31,
28,29,
31,31,
30,30,
31,31,
30,30,
31,31,
31,31,
30,30,
31,31,
30,30,
31,31
};
struct date{
int day;
int month;
int year;
void nextday(){
day++;
if(day>dayofmonth[month][ISYEAP(year)]){
day=1;
month++;
if(month>12){
month=1;
year++;
}
}
}
};
int buf[5001][13][32];
int abs(int x){
return x<0? -x:x;
}
int main(){
date temp;
temp.year=0;
temp.day=1;
temp.month=1;
int cnt=0;
while(temp.year!=5001){
buf[temp.year][temp.month][temp.day]=cnt;
temp.nextday();
cnt++;
}
int d1,m1,y1;
int d2,m2,y2;
while(scanf("%4d%2d%2d",&y1,&m1,&d1)!=EOF){
scanf("%4d%2d%2d",&y2,&m2,&d2);
printf("%d\n",abs(buf[y2][m2][d2]-buf[y1][m1][d1])+1);
}
return 0;
}
  • 最大公约数与最小公倍数
1
2
3
4
5
6
7
8
9
10
11
//辗转相除法,即a和b的公约数与b和a%b的公约数相等
int gcd(int a,int b){
if(b==0) return a;
else return gcd(b,a%b);
}
//当得到a和b的最大公约数d之后,可以马上得到a和b的最小公倍数是ab/d。
int lcm(int a,int b){
int d = gcd(a,b);
return a/d*b;
}
  • map

当题目中为根据学号(学号唯一)来寻找学生这种类型,用STL中的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
//变量声明
map<string, string> mapStrdent;
//用insert函数插入pair
mapStudent.insert(pair<string, string>("r000", "student_zero"));
//用"array"方式插入
mapStudent["r123"] = "student_first";
mapStudent["r456"] = "student_second";
//查找
iter = mapStudent.find("r123");
if(iter != mapStudent.end())
cout<<"Find, the value is"<<iter->second<<endl;
else
cout<<"Do not Find"<<endl;
//删除
//迭代器删除
iter = mapStudent.find("r123");
mapStudent.erase(iter);
//用关键字删除
int n = mapStudent.erase("r123");//如果删除了会返回1,否则返回0
//用迭代器范围删除 : 把整个map清空
mapStudent.erase(mapStudent.begin(), mapStudent.end());
//等同于mapStudent.clear()
  • C++二进制转换
1
2
3
4
5
6
7
8
9
10
11
12
string getBinarySequence(int num){
string ans="";
while(num){
if(num&1){
ans="1"+ans;
}else{
ans="0"+ans;
}
num>>=1;
}
return ans;
}

Java

  • BigInteger类
1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
BigInteger a = new BigInteger("222200");
int b = 1000;
BigInteger c = BigInteger.valueOf(b);
a = a.divide(c);
System.out.println(a);
>>> 222

一些计算方法及参数介绍

1
2
3
4
5
6
7
8
9
10
11
12
13
1.valueOf(parament);
2.add();
3.substract();
4.multiply();
5.devide();
6.remainder(); //取余数
7.pow();
8.gcd(); //最大公约数
9.abs();
10.negate();//去反数
11.mod();
12.max(); min();
13.compareTo(); //比较大小
  • 进制转换
1
2
3
4
5
6
7
import java.math.BigInteger;
import java.util.Scanner;
//大数运算
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext())
System.out.println(scanner.nextBigInteger().toString(16));

使用change函数可以实现任意进制的转换

1
2
3
private static String change(String num, int from, int to) {
return new BigInteger(num, from).toString(to);
}

Integer对象的进制转化

1
2
3
4
5
6
7
8
9
10
11
System.out.println("把2,8,16的数字的字符串形式,转化为10进制:");
System.out.println(Integer.parseInt("10", 10));
System.out.println(Integer.parseInt("10", 2));
System.out.println(Integer.parseInt("10", 8));
System.out.println(Integer.parseInt("10", 16));
System.out.println("把10进制,转化为2,8,16进制:");
System.out.println(Integer.toString(10));
System.out.println(Integer.toBinaryString(10));
System.out.println(Integer.toOctalString(10));
System.out.println(Integer.toHexString(10));
  • 字符串操作
1
2
3
4
5
6
7
8
9
//java中的split()切分时,将一个字符串根据切分字符转化为一个字符串数组,要注意切分表示要用("\+要切分的字符")
String[] str = string.split("\\.");
//使用StringBuilder替换某个指定位置的字符串
StringBuilder sb = new StringBuilder("18698587234");
sb.replace(3, 7, str);
//reverse操作
new StringBuffer(str).reverse().toString();
  • 正则表达式
1
2
3
4
5
6
7
8
9
10
11
//将剩下的消息内容根据正则表达式解析出基本的键值对消息,在根据等号将键值对放入map<string,string>中,返回该map信息
private Map<String, String> handel_main(String information) {
Map<String, String> data = new HashMap<>();
Pattern pattern = Pattern.compile("[a-zA-Z]{4}=[a-zA-Z0-9/-]*");
Matcher matcher = pattern.matcher(information);
while (matcher.find()) {
String[] data_split = matcher.group().split("=");
data.put(data_split[0], data_split[1]);
}
return data;
}
  • 使用Collections工具类对Linkedlist进行排序
1
2
3
4
5
6
7
8
Collections.sort(list,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if(o1>o2) return 1;
else if(o1==o2) return 0;
else return -1;
}
});

求矩阵的幂

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
#include <stdio.h>
#define N 11
void Pow(int result[N][N], int a[N][N], int n)//求result*a,结果存入result
{
int i, j, k;
int c[N][N];//用来暂时保存结果
for(i=0; i<n; i++) {
for(j=0; j<n; j++) c[i][j]=0;
}
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
for(k=0; k<n; k++) c[i][j]+=result[i][k]*a[k][j]; //重点
}
}
for(i=0; i<n; i++) {
for(j=0; j<n; j++) result[i][j]=c[i][j];
}
}
int main()
{
int n, k;
int i, j;
int a[N][N], result[N][N];
while(scanf("%d %d", &n ,&k)!=EOF)
{
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
scanf("%d", &a[i][j]);
result[i][j]=a[i][j];
}
}
for(i=1; i<k; i++) Pow(result, a, n);
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
printf("%d", result[i][j]);
if(j==n-1) printf("\n");
else printf(" ");
}
}
}
return 0;
}

二叉树

  • 递归建立二叉树
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
#include <iostream>
#include <string>
using namespace std;
string str;
int i;
struct TreeNode
{
char val;
struct TreeNode *lchild, *rchild;
TreeNode(char c) :val(c), lchild(NULL), rchild(NULL) {}
};
TreeNode* createTree() { //递归建立二叉树
char c = str[i++];
if (c == '#') return NULL;
TreeNode *root = new TreeNode(c);
root->lchild = createTree();
root->rchild = createTree();
return root;
}
void inOrderTraversal(TreeNode* root) {
if (!root) return;
inOrderTraversal(root->lchild);
cout << root->val << " ";
inOrderTraversal(root->rchild);
}
int main() {
while (cin >> str) {
i = 0;
TreeNode *root = createTree();
inOrderTraversal(root);
cout << endl;
}
return 0;
}
  • 给出前序和中序遍历,还原二叉树
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
struct Node{
Node *lchild,*rchild;
char c;
}Tree[50];
int loc; //静态数组中已经分配的
char str1[30],str2[30];
Node *create(){ //申请一个结点空间返回指向其的指针
Tree[loc].lchild = Tree[loc].rchild = NULL;
return &Tree[loc++];
}
//由给出的前序序列和中序序列还原树,并返回根节点
Node *build(int s1,int e1,int s2,int e2){ //前序是str1[s1]到str1[e1],后序是str2[s2]到str2[e2]
Node *ret = create();
ret->c = str1[s1];
int rootIdx;
for(int i=s2;i<=e2;i++){ //将前序的这个结点从中序序列中找出
if(str2[i] == str1[s1]){
rootIdx = i;
break;
}
}
if(rootIdx != s2)
ret->lchild = build(s1+1,s1+ (rootIdx - s2),s2,rootIdx-1);
if(rootIdx != e2)
ret->rchild = build(s1 + (rootIdx-s2) + 1,e1,rootIdx+1,e2);
return ret;
}
int main(){
while(scanf("%s",str1)!=EOF){
scanf("%s",str2);
loc = 0;
int l1 = strlen(str1);
int l2 = strlen(str2);
Node *T = build(0,l1-1,0,l2-1);
postOrder(T);
printf("\n");
}
return 0;
}
  • 二叉排序树的建立
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
//通过递归插入结点
Node *insert(Node *T,int x){
if(T==NULL){
T = create();
T->c = x;
return T;
}
else if(T->c > x)
T->lchild = insert(T->lchild,x);
else if(T->c < x)
T->rchild = insert(T->rchild,x);
return T;
}
int main(){
int n;
loc =0;
Node *T=NULL;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
T = insert(T,x);
}
}
return 0;
}
  • 平衡树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//AVL树
#include<stdio.h>
struct node{
int data,height; //height为当前的结点的高度
node *lchild,*rchild;
};
node *newNode(int v){ //新建立一个新结点
node *Node = new node;
Node->data = v;
Node->lchild = Node->rchild = NULL;
return Node;
}
int getHeight(node *root){
if(root == NULL) return 0;
return root->height;
}
//计算平衡因子
int getBalanceFactor(node *root){
return getHeight(root->rchild) - getHeight(root->lchild);
}
void updateHeight(node *root){
root->height = max(getHeight(root->lchild),getHeight(root->rchild)+1);
}
  • 查询一个图中连通子图的个数(并查集)
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
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
#define N 1000
int Tree[N];
int findRoot(int x){
if(Tree[x] == -1) return x;
else{
int tmp = findRoot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}
int main(){
int n,m;
while(scanf("%d",&n)!=EOF && n!=0){
scanf("%d",&m);
for(int i=1;i<=n;i++) Tree[i] = -1; //初始化
while(m-- != 0){
int a,b;
scanf("%d%d",&a,&b);
a = findRoot(a);
b = findRoot(b); //查找边的两个顶点所在集合信息(加到并查集中)
if(a != b) Tree[a] = b; //若两个顶点不在同一个集合则合并这两个集合
}
int ans = 0;
for(int i=1;i<=n;i++)
if(Tree[i] == -1) ans++; //统计所有节点中根节点的个数
printf("%d\n",ans-1);
}
return 0;
}

查询最长相同字串(数组)

1
2
3
4
5
6
7
8
9
10
11
12
13
int p=0,q=0,count=0,max=0; //两个指针来寻找最大相同字串
while(q<n-1){
//printf("%d\n",b[q]);
if(b[p] == b[q]){
q++;
count++;
if(max < count) max = count;
}
else{
p = q;
count = 0;
}
}

dfs问题(图像相邻点)

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
#include<bits/stdc++.h>
using namespace std;
#define N 105
int m,n,d;
int a[N][N];
int vis[N][N];
int dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int abs1(int a){
if(a<0)
a = 0-a;
return a;
}
void dfs(int x,int y){
int i,cx,cy;
for(i=0;i<8;i++){
cx = x+dir[i][0];
cy = y+dir[i][1];
if(cx>=0&&cx<n&&cy>=0&&cy<m&&!vis[cx][cy]&&abs1(a[cx][cy]-a[x][y])<=d){
vis[cx][cy]=1;
dfs(cx,cy);
}
}
return;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&d);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&a[i][j]);
vis[i][j] = 0;
}
}
int res = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!vis[i][j]){
res++;
vis[i][j] = 1;
dfs(i,j);
}
}
}
printf("%d\n",res);
}
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2016 - 2019 Dreaouth All Rights Reserved.

访客数 : | 访问量 :