刷题笔记

算法 阅读量

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.

访客数 : | 访问量 :