编程学习
博客里已经有Rust学习了，但那个准备更一些从零开始学习的东西
这篇博客就记录一下我在刷牛客和leetcode时，发现的一些小知识吧，因为不限语言，所以叫做编程学习
1.牛客 CPP11判断季节
题目：CPP11判断季节
这里我首先想到的解法是使用 if - else 判断结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>
using namespace std;
int main() {
int month;
cin >> month;
if (month == 3 || month == 4 || month == 5) {
cout << "春季";
} else if (month == 6 || month == 7 || month == 8) {
cout << "夏季";
} else if (month == 9 || month == 10 || month == 11) {
cout << "秋季";
} else if (month == 1 || month == 2 || month == 12) {
cout << "冬季";
} else {
cout << "不合法";
}
return 0;
}
|
但总感觉这样实现不太优雅，看题解发现有人使用switch 判断结构：
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
|
#include <iostream>
#include <ostream>
using namespace std;
int main() {
int month;
cin >> month;
switch (month) {
case 1:
case 2:
case 12:
cout << "冬季" << endl;
break;
case 3:
case 4:
case 5:
cout << "春季" << endl;
break;
case 6:
case 7:
case 8:
cout << "夏季" << endl;
break;
case 9:
case 10:
case 11:
cout << "秋季" << endl;
break;
default:
cout << "不合法" << endl;
}
return 0;
}
|
但是这样写得还是有点不太优雅
最后看最高赞题解是这样，同样是switch 判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <iostream>
using namespace std;
int main() {
int month;
cin >> month;
if(month < 1 || month > 12) //优先判断是否合法月份
cout << "不合法" << endl;
else{
switch(month){ //根据月份判断
case 3 ... 5: //连续的值
cout << "春季" << endl; break;
case 6 ... 8:
cout << "夏季" << endl; break;
case 9 ... 11:
cout << "秋季" << endl; break;
default:
cout << "冬季" << endl;
}
}
return 0;
}
|
这样写的原因是，首先为了避免使用麻烦的 if - else ,选择使用switch ， 而且因为是判断季节，月份的值大多是连续的，所以可以使用case的连续写法：在case中，可以用x…y表示范围在 [x,y] 的值，两边都是闭区间。
所以在代码中 case3: case4: case5: 就变成了 case 3...5: 最后冬季不连续，就使用 default 代替，由于已经使用 if 将月份值限制在 1 - 12范围内，除去以上三种情况就剩冬季了
2.牛客 CPP12 求 1~n之间偶数的和
题目： CPP12 求 1~n之间偶数的和
好久没写了连while的用法都忘了，按理说以前这个同样在牛客上用rust写过，应该是不能忘的QAQ
while 循环和 for 循环本质是同一种循环的两种不同形式
while 循环事先只设定好了循环的终点，在此范围内不断执行语句，具体其他的限制条件在循环内部定义
for 循环则事先设定好了循环的终点，以及循环的规则（如 i++ 设定在循环外）
因此while循环要比 for 循环稍微灵活一些
在Rust 中，在程序编译时，编译器会把 while 去糖化变成 “一个无限循环 + 一个条件判断和 break” ，类似于这样：
1
2
3
4
5
|
let mut i = 0;
while i < 10 {
println!("{}", i);
i += 1;
}
|
在 MIR 层面，它会被转换成类似下面这样的逻辑：
1
2
3
4
5
6
7
8
9
10
|
let mut i = 0;
loop {
if i < 10 {
// 循环体
println!("{}", i);
i += 1;
} else {
break; // 条件不满足，退出循环
}
}
|
同样的，编译器也会对 for 循环做相似的去糖化处理：
去糖化过程：for -> while let -> loop
Rust 中的 for 循环之所以强大和灵活，是因为它本质上是在遍历一个迭代器（Iterator），因此，任何一个 for 循环都会被编译器转换成一个使用 while let 和迭代器的等价结构
- 牛客 CPP13 计算一个数的阶乘
CPP13 计算一个数的阶乘
最适合区分递归和迭代的题目，但我只想到了迭代的实现，忘记递归是怎么实现的了
迭代：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long factorial = 1;
for (int i = 2; i <= n; i++) {
factorial *= i;
}
cout << factorial << endl;
return 0;
}
|
递归：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>
using namespace std;
long long fac(int n) {
if (n == 1) {
return 1;
}
return fac(n-1) * n;
}
int main() {
int n;
cin >> n;
long long factorial = fac(n);
cout << factorial << endl;
return 0;
}
|
这里遇见了一个小小的问题，C++中函数声明必须在调用前，但Rust就不需要
这里写一下相同的问题使用Rust是如何解决的：
迭代：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
use std::io;
fn main() {
let mut stdin = String::new();
io::stdin().read_line(&mut stdin).expect("");
let n = stdin
.trim()
.parse()
.expect("");
let mut x = 1;
for i in 2..=n {
x *= i;
}
println!("{}", x);
}
|
递归：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
use std::io;
fn main() {
let mut stdin = String::new();
io::stdin().read_line(&mut stdin).expect("");
let n = stdin
.trim()
.parse()
.expect("");
let x = factorial(n);
println!("{}", x);
}
fn factorial(n: i64) -> i64 {
if n == 1 {
return 1;
}
return n * factorial(n - 1);
}
|
- 牛客CPP2 实现四舍五入
这里看到了两种做法,第一种实现是:
由于C++中double类型是自动四舍五入的,所以直接格式化输出0位小数:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <iostream>
using namespace std;
int main() {
double a;
cin >> a;
printf("%.0f", a);
return 0;
}
|
在题解中看到更加优雅的实现方法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <iostream>
using namespace std;
int main() {
double d;
cin >> d;
if (d > 0) {
cout<<(int)(d+0.5);
}
else {
cout<<(int)(d-0.5);
}
return 0;
}
|
这个是游戏编程里常用的方法,正数浮点数+0.5(负数浮点数-0.5)后强制类型转换相当于四舍五入
这个原理是:由于强制转型的时候程序会直接截断小数(向零取整),所以对任意一个正数加0.5,如果它的小数部分>0.5 则进一,然后直接截断,对于负数同理,减去0.5,然后向零取整.
这样就实现了四舍五入的功能.
endl 和 /n 的区别:
endl: endl 会输出 ‘\n’ ,然后立即刷新缓冲区并输出到屏幕上,由于要刷新缓冲区, endl 会比 \n 慢一点
5.牛客CPP4 获取两数中的较大值
1
2
3
4
5
6
7
8
9
10
11
12
|
#include <iostream>
using namespace std;
int main() {
int a;
int b;
scanf("%d%d", &a,&b);
printf("%d", a>b?a:b);
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
|
#include <iostream>
#include <vector>
void selection_sort(std::vector<int> &nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
int k = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k]) {
k = j;
}
}
std::swap(nums[i], nums[k]);
}
}
int main() {
int n;
std::cin >> n;
std::vector<int> nums(n);
for (int i = 0; i < n; i++) {
std::cin >> nums[i];
}
selection_sort(nums);
for (int i = 0; i < n; i++) {
std::cout << nums[i] << " ";
}
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
|
#include <iostream>
#include <vector>
void bubble_sort(std::vector<int> &nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
std::swap(nums[j], nums[j + 1]);
}
}
}
}
int main() {
int n;
std::cin >> n;
std::vector<int> nums(n);
for (int i = 0; i < n; i++) {
std::cin >> nums[i];
}
bubble_sort(nums);
for (int i = 0; i < n; i++) {
std::cout << nums[i] << " ";
}
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
|
#include <iostream>
#include <vector>
void bubble_sort(std::vector<int> &nums) {
int n = nums.size();
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
std::swap(nums[j], nums[j + 1]);
}
}
}
}
int main() {
int n;
std::cin >> n;
std::vector<int> nums(n);
for (int i = 0; i < n; i++) {
std::cin >> nums[i];
}
bubble_sort(nums);
for (int i = 0; i < n; i++) {
std::cout << nums[i] << " ";
}
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
|
#include <iostream>
#include <vector>
void bubble_sort(std::vector<int> &nums) {
int n = nums.size();
for (int i = n - 1; i > 0; i--) {
bool flag = false; // 在这里每轮重置flag
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j+1]) {
std::swap(nums[j], nums[j+1]);
flag = true;
}
}
if (!flag) {
break;
}
}
}
int main() {
int n;
std::cin >> n;
std::vector<int> nums(n);
for (int i = 0; i < n; i++) {
std::cin >> nums[i];
}
bubble_sort(nums);
for (int i = 0; i < n; i++) {
std::cout << nums[i] << " ";
}
return 0;
}
|
这里有个每轮重置flag的细节我一开始没有注意到,如果把flag定义在所有循环的外面,那么如果遇到只需要交换一次的情况,由于第一轮已经将flag设置为true,后续即使不再交换,还是会过排序逻辑,优化就失效了;但如果每轮重置flag的话,就可以很好地应对只交换少量次数的情况了,效率也提高了一些.