东方博宜OJ

东方博宜OJ网站
CSP文档

8 字符型

8.1 字符型

1967 输出字符的ASCII码

#include <bits/stdc++.h>
using namespace std;

int main()
{
   
	char c;
	cin >> c;
	cout << (int)(c) << endl;
	return 0;
}

1968 输出ASCII码对应的字符

#include<bits/stdc++.h>
using namespace std;
 
int main() 
{
   
    int x;
    cin >> x;
    char c = x;
    cout << c;
    return 0;
}

1970 判断是什么字符

#include <bits/stdc++.h>
using namespace std;

int main()
{
   
	char c;
	cin >> c;
	if (isdigit(c))
	{
   
		cout << "digit" << endl;
	}
	if (isupper(c))
	{
   
		cout << "upper" << endl;
	}
	if (islower(c))
	{
   
		cout << "lower" << endl;
	}
	return 0;
}

1971 大小写转换

#include <bits/stdc++.h>
using namespace std;

int main()
{
   
	char a[20];
	int i = 0;
	cin >> a;
	for(; a[i]; i++)
	{
   
		if (a[i] >= 'a' && a[i] <= 'z')
        {
   
        	a[i] -= 32;
        }
		else if (a[i] >= 'A' && a[i] <= 'Z')
        {
   
            a[i] += 32;
        }
	}
	for (i = 0; a[i]; i++)
	{
   	
		cout << a[i];
	}
	return 0;
}

1093 打印小写字母表

#include <bits/stdc++.h>
using namespace std;

int main()
{
   
    string s;
    for (char c = 'a'; c <= 'z'; c++)
    {
   
    	s += c;
    	if (c == 'm' || c == 'z')
    	{
   
    		s += '\n';
    	}
    }
    for (char c = 'z'; c >= 'a'; c--)
    {
   
    	s += c;
    	if (c == 'n')
    	{
   
    		s += '\n';
    	}
    }
    cout << s;
    return 0;
}

8.2 字符串基础

1093. 打印小写字母表

#include <bits/stdc++.h>
using namespace std;

int main()
{
   
	string s; //字符串
	for (char c = 'a'; c <= 'z'; c++)
	{
   
		s += c;
		if (c == 'm' || c == 'z')
		{
   
			s += '\n';
		}
	}
	for (char c = 'z'; c >= 'a'; c--)
	{
   
		s += c;
		if (c == 'n')
		{
   
			s += '\n';
		}
	}
	cout << s;
	return 0;
}

8.3 字符串进阶

15 深度优先搜索-DFS

15.1深搜基础

1435. 数池塘（八方向）

#include <bits/stdc++.h>
using namespace std;
int n, m, s;
char a[100][100];
int fx[8] = {
   0, 0 , 1 , -1 , -1 , -1 , 1 , 1};
int fy[8] = {
   1, -1 , 0 , 0 , -1 , 1 , 1 , -1};

void dfs(int x, int y)
{
   
	a[x][y] = '.';
	int tx, ty;
	for (int i = 0; i < 8; i++)
	{
   
		tx = x + fx[i];
		ty = y + fy[i];
		if (a[tx][ty] == 'W')
		{
   
			dfs(tx, ty);
		}
	}
}

int main()
{
   
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
   
		for (int j = 1; j <= m; j++)
		{
   
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++)
	{
   
		for (int j = 1; j <= m; j++)
		{
   
			if (a[i][j] == 'W')
			{
   
				s++;
				dfs(i, j);
			}
		}
	}
	cout << s << endl;
	return 0;
}

15.2 最少步数问题

1432. 走出迷宫的最少步数

总结：
最少步数深搜类型题目：
1、准备两个数组char类型（地图） 记录最小步数的int类型数组
2、用深搜就会用到两个方向数组
3、#include <climits> //最大最小值头文件
4、最少步数类型题目一般不记录走过路径

INT_MAX : int 类型最大值
INT_MIN : int类型最小值
详细：C/C++之最值limits.h(climits)和limits头文件

#include <bits/stdc++.h>
using namespace std;
int n, m, d[50][50];
char a[50][50]; //地图

int fx[4] = {
   0, 1, 0, -1};
int fy[4] = {
   1, 0, -1, 0};

void dfs(int x, int y, int dep) //dep:步数
{
   
	d[x][y] = dep;
	int tx, ty;
	for (int i = 0; i < 4; i++)
	{
   
		tx = x + fx[i];
		ty = y + fy[i];
		//如果tx, ty可以搜索（该点在地图内，且该点是'.' , 且走到该点的步数更少）
		if (a[tx][ty] == '.' && dep + 1 < d[tx][ty])
		{
   
			dfs(tx, ty, dep + 1);
		}
	}
}

int main()
{
   
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
   
		for (int j = 1; j <= m; j++)
		{
   
			//输入
			cin >> a[i][j];
			d[i][j] = INT_MAX;
		}
	}
	dfs(1, 1, 1);
	cout << d[n][m] << endl;
	return 0;
}

15.3 回溯与路径打印

1431. 迷宫的第一条出路

总结：
1、定义两个数组：
（1）存储地图
（2）记录路径（易错：行：范围是全部图案的两倍 列：记录x和y两列）
2、方向数组（如何确定方向）
 d[x][y] 
(1)行： 往下走，x表示x + 1; 往上走，x表示x - 1(分别对应上下)
(2)列： 往右走，y表示y + 1; 往左走，y表示y - 1(分别对应左右)
(3)往哪个方向走，哪个方向的值就会变
(4)按照左、上、右、下顺序：
  fx[4] = {
   0, -1, 0, 1};
  fy[4] = {
   -1, 0, 1, 0};
3、打印后面带"."或带其他符号类型可参考以下程序：
 void print(int k)
{
   
	for (int i = 1; i <= k; i++)
	{
   
		cout << "(" << r[i][1] << "," << r[i][2] << ")";
		if (i != k)
		{
   
			cout << "->";
		}
	}
}
(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)
4、打印路线类型题目：一般要记录走过路线

#include <bits/stdc++.h>
using namespace std;

int n;
char a[30][30]; //地图
int r[410][3]; //路径

int fx[4] = {
   0, -1, 0, 1};
int fy[4] = {
   -1, 0, 1, 0};

void print(int k)
{
   
	for (int i = 1; i <= k; i++)
	{
   
		cout << "(" << r[i][1] << "," << r[i][2] << ")";
		if (i != k)
		{
   
			cout << "->";
		}
	}
	exit(0);
}

void dfs(int x, int y, int k)
{
   
	//1.赋值给数组
	r[k][1] = x;
	r[k][2] = y;
	//2.标记走过的路线
	a[x][y] = '1';
	//3.判断是不是终点
	if (x == n && y == n)
	{
   
		print(k);
	}
	//4.遍历四个方向
	int tx, ty;
	for (int i = 0; i < 4; i++)
	{
   
		tx = x + fx[i];
		ty = y + fy[i];
		//5.判断在不在范围内
		if (a[tx][ty] == '0')
		{
   
			dfs(tx, ty, k + 1);
		}
	}
}


int main()
{
   
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
   
		for (int j = 1; j <= n; j++)
		{
   
			cin >> a[i][j];
		}
	}
	dfs(1, 1, 1);
	return 0;
}

1360. 卒的遍历

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[20][3];
//先向下，下边走到头就向右
int fx[2] = {
   1, 0};
int fy[2] = {
   0, 1};
int c; //计数器

void print(int k)
{
   
	c++;
	cout << c << ":";
	for (int i = 1; i < k; i++)
	{
   
		cout << a[i][1] << "," << a[i][2] << "->";
	}
	cout << n << "," << m << endl;
}

void dfs(int x, int y, int k)
{
   
	a[k][1] = x;
	a[k][2] = y;
	//走到终点，打印路径
	if (x == n && y == m)
	{
   
		print(k);
		return;
	}
	int tx, ty;
	for (int i = 0; i < 2; i++)
	{
   
		tx = x + fx[i];
		ty = y + fy[i];
		if (tx >= 1 && ty >= 1 && tx <= n && ty <= m)
		{
   
			dfs(tx, ty, k + 1);
		}
	}
}

int main()
{
   
	cin >> n >> m;
	dfs(1, 1, 1);
	return 0;
}

1739. 迷宫的所有路径

#include <bits/stdc++.h>
using namespace std;

int n, c;
int a[30][3];
bool f[10][10];
//按照右、下、左、上顺序进行搜索
int fx[4] = {
   0, 1, 0, -1};
int fy[4] = {
   1, 0, -1, 0};

void print(int k)
{
   
	c++;
	cout << c << ":";
	for (int i = 1; i < k; i++)
	{
   
		cout << a[i][1] << "," << a[i][2] << "->";
	}
	cout << n << "," << n << endl;
}

void dfs(int x, int y, int k)
{
   
	a[k][1] = x;
	a[k][2] = y;
	if (x == n && y == n)
	{
   
		print(k);
		return;
	}
	int tx, ty;
	for (int i = 0; i < 4; i++)
	{
   
		tx = x + fx[i];
		ty = y + fy[i];
		if (tx >= 1 && ty >= 1 && tx <= n && ty <= n && f[tx][ty] == false)
		{
   
			//标记走过了
			f[tx][ty] = true;
			//递归
			dfs(tx, ty, k + 1);
			//回溯
			f[tx][ty] = false;
		}
	}
}

int main()
{
   
	cin >> n;
	f[1][1] = true;
	dfs(1, 1, 1);
	return 0;
}

15.4 回溯与全排列

1308.全排列的结果

总结：
一维数组（没有二维数组）
1、定义int/char数组 + bool类型数组
2、调用递归
3、递归第一步：遍历方向
4、递归第二步：判断有没有被标记过
5、递归第三步：进来先标记，然后赋值
6、递归第四步：满足条件就打印，否则就递归
7、记得回溯！

#include <bits/stdc++.h>
using namespace std;

int n, a[10];
bool f[10];

void print()
{
   
	for (int i = 1; i <= n; i++)
	{
   
		cout << a[i] << " ";
	}
	cout << endl;
}


//递归函数——为a数组赋值
void fun(int k)
{
   
	for (int i = 1; i <= n; i++)
	{
   
		if (f[i] == false)
		{
   
			a[k] = i;
			//标记数字i被用过了
			f[i] = true;
			if (k == n)
			{
   
				print();
			}
			else
			{
   
				//递归原理
				fun(k + 1); 
			}
			//回溯
			f[i] = false;
		}
	}
}

int main()
{
   
	cin >> n;
	fun(1);
	return 0;
}

1358.素数环

#include <bits/stdc++.h>
using namespace std;

int n, a[20], c;
bool f[20];

bool prime(int n)
{
   
	for (int i = 2; i <= sqrt(n); i++)
	{
   
		if (n % i == 0)
		{
   
			return false;
		}
	}
	if (n == 1) 
	{
   
		return false;
	}
	return true;
}

void print()
{
   
	c++;
	cout << c << ":";
	for (int i = 1; i <= n; i++)
	{
   
		cout << a[i] << " ";
	}
	cout << endl;
}

void fun(int k)
{
   
	for (int i = 1; i <= n; i++)
	{
   
		//1、i没有被用过 2、且i和前一个数的和是素数
		if (f[i] == false && (k == 1 || prime(i + a[k - 1]) == true))
		{
   
			a[k] = i;
			f[i] = true;
			if (k == n && prime(a[k] + a[1]))
			{
   
				print();
			}
			else
			{
   
				fun(k + 1);
			}
			//回溯
			f[i] = false;
		}
	}
}

int main()
{
   
	cin >> n;
	fun(1);
	cout << "total:" << c << endl;
	return 0;
}

15.5 深搜综合

16 广度优先搜索-BFS

16.1 广搜基础-用广搜实现深搜

16.2 广搜求最少步数和最短路径

16.3 广搜综合

17 动态规划-DP

18 二分

18.1 二分查找

1236. 二分查找

总结:
分治:将一个规模为 N 的问题分解为  个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法。

二分查找步骤：
1、定义一个初始位置 r(需要赋初始值)，left,right,mid
2、while循环条件固定位left<=right
3、先判断中点是不是目标值，如果是就break；
4、在判断是不是在左边，左边将mid-1赋值给right
5、在判断是不是在右边，右边将mid+1值赋给left
6、注意重点：
(1)left = mid+1 左加
(2)right = mid-1 右减

分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。在讨论二分查找的最佳结果时，我们通常是在讨论其最佳时间复杂度，即在最理想的情况下，算法需要比较的次数。
<mark>在最佳情况下，二分查找的时间复杂度是 O(1)</mark>，这发生在要查找的元素正好是数组的中间元素时。也就是说，在最佳情况下，你只需要进行一次比较就能找到目标元素。
<mark>二分查找算法的最坏情况时间复杂度是 O(log n)</mark>，其中 “n” 是数组中的元素数量。这种情况发生在所查找的元素位于数组的一端或根本不存在于数组中。

<mark>解法一：(非递归解法——二分)</mark>

#include <bits/stdc++.h>
using namespace std;

int n, a[1000000], r = -1, x;
int main()
{
   
	cin >> n;
	for (int i = 0; i < n; i++)
	{
   
		cin >> a[i];
	}
	cin >> x;
	int left = 0, right = n - 1, mid;
	while (left <= right)
	{
   
		mid = (left + right) / 2;
		if (a[mid] == x)
		{
   
			r = mid;
			break;
		}
		else if (x < a[mid])
		{
   
			right = mid - 1;
		}
		else if (x > a[mid])
		{
   
			left = mid + 1;
		}
	}
	cout << (r == -1 ? -1 : r + 1) << endl;
	return 0;
}

<mark>解法二：(递归解法)</mark>

#include <bits/stdc++.h>
using namespace std;

int n, a[1000000], x;

int fun(int left, int right)
{
   
	if (left > right) return -1;
	int mid = (left + right) / 2;
	if (x == a[mid])
	{
   
		return mid + 1;
	}
	else if (x < a[mid])
	{
   
		return fun(left, mid - 1);
	}
	else if (x > a[mid])
	{
   
		return fun(mid + 1, right);
	}
	
}

int main()
{
   
	cin >> n;
	for (int i = 0; i < n; i++)
	{
   
		cin >> a[i];
	}
	cin >> x;
	cout << fun(0, n - 1) << endl;
	return 0;
}

1010 数组元素的排序

<mark>一题多结！</mark>

<mark>1、快速排序</mark>

总结：
1、左右指针赋值 
2、基准值赋值
3、第一次划分子区间 
4、寻找不符合的左、右区域 
5、将两边不符合的值进行交换 
6、交换后需要下标增加和减少
7、调用递归重新将左右子区域划分

这是一个经典的快速排序（Quick Sort）算法的实现。快速排序的<mark>平均时间复杂度为O(n log n)，但最坏情况下时间复杂度为O(n^2)</mark>。 在你的代码中，快速排序递归调用的方式可能导致最坏情况的发生，因此<mark>最坏情况下时间复杂度为O(n^2)</mark>。
快速排序的时间复杂度的平均和最坏情况取决于选择的基准元素以及数据的分布情况。在最好情况下，每次选择的基准元素都能将数组均匀地分成两部分，此时时间复杂度接近O(n log n)。

解法一：

#include <bits/stdc++.h>
using namespace std;
int a[100000];

void quick(int left,int right)
{
   
	//1、左右指针赋值 
	int i = left; 
	int j = right;
	
	//2、基准值赋值
	int mid = (left+right) / 2;
	 
	//3、第一次划分子区间 
	while(i <= j)
	{
   
		//4、寻找不符合的左、右区域 
		while(a[i] < a[mid])	i++;
		while(a[j] > a[mid])  	j--;
		//5、将两边不符合的值进行交换 
		if(i <= j)
		{
   
			swap(a[i],a[j]);
			// 6、交换后需要下标增加和减少
			i++;
			j--;
		} 
		
		//7、调用递归重新将左右子区域划分
		// 前提是还属于左右区域范围内 
		if(left <= j) quick(left, j);
		if(i <= right) quick(i, right); 
	} 
}
int main()
{
   
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
   
		cin >> a[i];
	}
	
	quick(0, n - 1);
	
	for(int i = 0; i < n; i++)
	{
   
		cout << a[i] << " ";
	}
	
	return 0;
}

解法二：

#include <bits/stdc++.h>
using namespace std;

int n, a[100000];

void quick(int left, int right)
{
   
    if (left >= right) return; // 增加的基本情况检查，避免不必要的递归调用

    int i = left, j = right;
    int pivot = a[(left + right) / 2]; // 保存中间值

    while (i <= j)
    {
   
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j)
        {
   
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    if (left < j) quick(left, j);
    if (i < right) quick(i, right);
}

int main()
{
   
    cin >> n;
    for (int i = 0; i < n; i++)
    {
   
        cin >> a[i];
    }
    quick(0, n - 1);
    for (int i = 0; i < n; i++)
    {
   
        cout << a[i] << " ";
    }
    return 0;
}

<mark>2、冒泡排序</mark>

普通解法：

#include <bits/stdc++.h>
using namespace std;

int n, a[100000];

int main()
{
   
	cin >> n;
	for (int i = 0; i < n; i++)
	{
   
		cin >> a[i];
	}
	for (int i = 1; i <= n - 1; i++)
	{
   
		for (int j = 0; j <= n - i - 1; j++)
		{
   
			if (a[j] > a[j + 1])
			{
   
				swap(a[j], a[j + 1]);
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
   
		cout << a[i] << " ";
	}
	return 0;
}

改良解法：

#include <bits/stdc++.h>
using namespace std;

int n, a[100000];
bool f; //标记是否产生过交换

int main()
{
   
	cin >> n;
	for (int i = 0; i < n; i++)
	{
   
		cin >> a[i];
	}
	for (int i = 1; i <= n - 1; i++)
	{
   
		f = false; //假设没有产生过交换
		for (int j = 0; j <= n - i - 1; j++)
		{
   
			if (a[j] > a[j + 1])
			{
   
				swap(a[j], a[j + 1]);
				f = true;
			}
		}
		if (f == false)
		{
   
			break; //不需要继续排序
		}
	}
	for (int i = 0; i < n; i++)
	{
   
		cout << a[i] << " ";
	}
	return 0;
}

<mark>3、选择排序（冒泡排序改良版——减少交换次数！）</mark>

选择排序思想：
（1）外层循环比较n-1轮
（2）内层循环找出最大的数的下标不是它本轮最后一个数的下标n-i
（3）交换a[ma] , a[n-i]

<mark>错误写法！</mark>

#include <bits/stdc++.h>
using namespace std;

int a[1000], n, maxn;

int main()
{
   
	cin >> n;
	for (int i = 0; i < n; i++)
	{
   
		cin >> a[i];
	}
	for (int i = 1; i <= n - 1; i++)
	{
   
		for (int j = 1; j <= n - i; j++)
		{
   
			maxn = max(a[j], a[maxn]);
		}
	}
	for (int i = 0; i < n; i++)
	{
   
		cout << a[i] << " ";
	}
	return 0;
}
//到最后没交换！

<mark>正确写法！</mark>

#include <bits/stdc++.h>
using namespace std;

int a[1000], n, maxn;

int main()
{
   
	cin >> n;
	for (int i = 0; i < n; i++)
	{
   
		cin >> a[i];
	}
	for (int i = 1; i <= n - 1; i++)
	{
   
		//假设本轮中下标为0的数是最大数！
		maxn = 0;
		for (int j = 1; j <= n - i; j++)
		{
   
			if (a[j] > a[maxn])
			{
   
				maxn = j;
			}
		}
		//如果第i轮最大数下标不是本轮最后一个数下标(n - i)，交换它们
		if (maxn != n - i)
		{
   
			swap(a[maxn], a[n - i]);
		}
	}
	for (int i = 0; i < n; i++)
	{
   
		cout << a[i] << " ";
	}
	return 0;
}

<mark>4、桶排序（非常简单！）</mark>

总结：
桶排序也叫箱排序工作的原理是:
统计每个元素出现的个数，然后利用桶的下标已经有序的原理，按照每个数出现的次数循环输出。
因此，桶排序要求数组元素数值必须是小范围内的数!
什么情况下不适合用桶排序?
如果数据量不大，但数据中有一个数特别大，则不适合用桶排序!
如：2, 5, 3, 3, 8, 9, 1, 2, 7, 6, 100000

#include <bits/stdc++.h>
using namespace std;

int a[10000], n, x;

int main()
{
   
	cin >> n;
	for (int i = 0; i < n; i++)
	{
   
		cin >> x;
		a[x]++;
	}
	for (int i = 1; i <= 1000; i++)
	{
   
		for (int j = 1; j <= a[i]; j++)
		{
   
			cout << i << " ";
		}
	}
	return 0;
}

<mark>5、插入排序</mark>

总结：
插入排序将数组分成前后 2 块:
前一块: 有序区间(0 到 i - 1);
后一块: 无序区间(i 到 n - 1);
排序思想:
从无序区间中选择一个数字，插入到有序区间中。有序区间扩大一位，无序区间减少一位。直到有序区间覆盖整个数组。

#include <bits/stdc++.h>
using namespace std;

int a[10100], n, k, i, j, t;

int main()
{
   
	cin >> n;
	for (int i = 0; i < n; i++)
	{
   
		cin >> a[i];	
	}
	//循环无序区（a[0]默认在有序区中）
	for (i = 1; i < n; i++)
	{
   
		//循环有序区
		for (j = 0; j < i; j++)
		{
   
			//找到有序区中第一个比要插入的数大的数
			if (a[j] >= a[i])
			{
   
				break;
			}
		}
		if (j != i)
		{
   
			t = a[i];
			for (int k = i - 1; k >= j; k--)
			{
   
				a[k + 1] = a[k];
			}
			a[j] = t;
		}
	}
	for (int i = 0; i < n; i++)
	{
   
		cout << a[i] << " ";
	}
	return 0;
}

19 并查集

会续更！！！