1. 字母排序
分析——不排序解题
- 创建一个大小为128的数组sheet，序号表示ascii码强转为int表示的数值，对应的数组值表示该ascii码在输入字符串中出现的次数
- 设置一个max变量和id变量，max初值为0，从下标为((int)‘A’)开始遍历sheet数组，找到最大的值赋给max，对应的数组序号赋给id，如果最大的max值为0，表明字符串已经打印完毕了，结束程序。
- 将((char)id)打印max遍，然后回到第二步
代码——32行极简，比其他题解短10行
#include <iostream>
#include <string.h>
using namespace std;
int main() {
char str[1001];
while (scanf("%s", str) != EOF) {
int length = strlen(str);
int sheet[128] = {0};
for (int i = 0; i < length; i++) {
int index = (int)str[i];
sheet[index]++;
}
while (true) {
int max = 0;
int id;
for (int i = (int)'A'; i < 128; i++) {
if (sheet[i] > max) {
max = sheet[i];
id = i;
}
}
if (max == 0) {
break;
}
for (int i = 0; i < max; i++) {
printf("%c", (char)id);
}
sheet[id] = 0;
}
printf("\n");
}
}
2. 动态查找的问题
分析——采用hash表
- 数据总数不超过十万，可以将hash表长设置为十万，采用最简单的线性探测法，一旦发生冲突就往后找
代码
这段代码本来是用vs写的，但是vs这个软件老毛病就是总是觉得你写得不安全，然后不让你编译通过，于是抛弃vs使用dev c++
另外一个让我讨厌的是sql server，珍爱生命，远离ms家的软件。
// ConsoleApplication1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
using namespace std;
int num[100001];//静态内存区默认的初始值是0
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int temp;
scanf("%d", &temp);
int j = 0;
while (true) { //线性探测法
if (num[(temp + j) % 100000] == 0) {
num[(temp + j) % 100000] = temp;
break;
}
j++;
}
}
int m;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int temp;
scanf("%d", &temp);
int j = 0;
while (true) { //线性探测法
if (num[(temp + j) % 100000] == 0) {
printf("no\n");
num[(temp + j) % 100000] = temp;
break;
} else if (num[(temp + j) % 100000] == temp) {
printf("find\n");
break;
}
j++;
}
}
return 0;
}
3. 分离字符串
分析
- 使用if判断条件放入指定数组即可
代码
#include <iostream>
#include <string.h>
using namespace std;
char abc[201];//字母
char _12[201];//数字
char spe[201];//符号
//将每次放入数组的操作写成一个函数，每次放入字符都在后面放一个结束符'\0'，这样方便输出
void operate(char *a, int b, char c) {
*(a + b) = c;
*(a + b + 1) = '\0';
}
int main() {
char str[201];
while (scanf("%s", str) != EOF) {
int p_a = 0, p_1 = 0, p_s = 0;
int length = strlen(str);
for (int i = 0; i < length; i++) {
if (str[i] <= 'z' && str[i] >= 'a' || str[i] <= 'Z' && str[i] >= 'A') {
operate(abc, p_a++, str[i]);
} else if (str[i] <= '9' && str[i] >= '0' ) {
operate(_12, p_1++, str[i]);
} else {
operate(spe, p_s++, str[i]);
}
}
printf("%s\n%s\n%s\n", abc, _12, spe);
}
return 0;
}
4. 打印杨辉三角形
分析——使用队列构造
- 入队一个1
- 对行数 i i i 开始遍历，每行的元素数目等于行数 i i i
- 第
i
i
i 行前
i
−
1
i-1
i−1 个元素循环执行这样的操作：
- 队首元素值赋temp
- 然后队首出队，打印temp值
- temp值加上当前队首值，和入队
- 第 i i i 行第 i i i 个元素一定是1，因此直接打印1和一个换行符，同时要将一个1入队
b站视频：【【3.6链队列和队列的应用（包括杨辉三角）-2 考研《数据结构C语言版》严蔚敏知识点讲解】】在49:40处对这一过程进行了手动推导，如果对上面的分析不理解，可以点击链接去听一下讲解。
代码
#include <cstdio>
#include <queue>
using namespace std;
int main() {
int n;
while (scanf("%d", &n) != EOF) {
queue<int> tri;
tri.push(1);
for (int i = 0; i < n; i++) {//行遍历
for (int j = 0; j < i; j++) {
int temp = tri.front(); //获取队首
tri.pop();
printf("%d ", temp);
temp += tri.front();
tri.push(temp);
}
tri.push(1);
printf("1\n");
}
}
return 0;
}
5. 回文数判定
分析
数字位数都确定是5位了，直接用字符串接住，看看0和4序号、1和3序号的数字是不是一样的就好
代码
#include <cstdio>
#include <queue>
using namespace std;
int main() {
char num[5];
while (scanf("%s", num) != EOF) {
getchar();
if (num[0] == num[4] && num[1] == num[3]) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}
6.求三角形面积
分析——使用正弦公式计算面积
代码
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
struct position {
double x;
double y;
};
position tri[3];
void caculate(double *str) {
for (int i = 0; i < 3; i++) {
tri[i].x = str[i * 2];
tri[i].y = str[i * 2 + 1];
}
position a, b;
a.x = tri[1].x - tri[0].x;
a.y = tri[1].y - tri[0].y;
b.x = tri[2].x - tri[0].x;
b.y = tri[2].y - tri[0].y;
double a_length = sqrt(pow(a.x, 2) + pow(a.y, 2));
double b_length = sqrt(pow(b.x, 2) + pow(b.y, 2));
double cos = (abs(a.x * b.x + a.y * b.y)) / (a_length * b_length);
double sin = sqrt(1 - pow(cos, 2));
double s = 0.5 * a_length * b_length * sin;
printf("%.2lf\n", s);
}
int main() {
double str[6];
while (scanf("%lf", &str[0]) != EOF) {
for (int i = 1; i < 6; i++) {
scanf("%lf", &str[i]);
}
caculate(str);
}
return 0;
}
注意点
- 所有的数值类型都应该是double，否则会报错
- 下面这行代码，如果乘法不加括号，会出现错误答案
double cos = (abs(a.x * b.x + a.y * b.y)) / (a_length * b_length);
分析——使用海伦公式计算面积
【海伦公式】
代码
#include<bits/stdc++.h>
using namespace std;
struct point{
double x;
double y;
}A,B,C;
double len(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
while(scanf("%lf %lf %lf %lf %lf %lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y)!=EOF){
double ac = len(A,C);
double ab = len(A,B);
double bc = len(B,C);
double p = (ac+bc+ab)/2;
double s = sqrt(p*(p-ac)*(p-bc)*(p-ab));
printf("%.2lf\n",s);
}
}
