布尔运算符的短路

首先, 什么是表达式?

表达式是运算符和它们的操作数的序列，它指定一项计算。

表达式的求值可以产生一个结果（比如 2+2 的求值产生结果 4），也可能产生副作用（比如对 std::printf(“%d”,4) 的求值在标准输出上打印字符 ‘4’）。

以下代码每一行的内容都是一个表达式:

1
2
3
4
5
6

a = 1
a++
a = a * a + a - a | a
foo()
foo(a+a)
a == a

注意, a++ 是表达式, a++; 就是一个语句了

其次, 什么是表达式的副作用?

表达式, 顾名思义, 是有一个值的. 很多情况下我们求一个表达式的值, 是为了使用它的值. 在求值的过程中对于变量的修改等操作被称为表达式的副作用.

比如, 对于表达式 y++, y的值+1就是这个表达式的副作用.

比如, 对于以下函数:

1
2
3
4

int foo(){
    static int i = 0;
    return ++i;
}

对于表达式 foo(), i 的值的变化就是他的副作用.

再比如, 对于表达式 printf("%d",a) + 1, 输出了a的值就是他的副作用.

布尔运算符的短路.

对于 “逻辑与(&&)” 和 “逻辑或(||)” 这两个运算, 他们有一个不同于其他运算符的特点, 就是运算符短路.

对于与运算, 如果他左边的表达式(也叫第一操作数)计算完是假的话, 无论右边的表达式(也叫第二操作数)的结果是多少, 最终的结果一定是假, 因此此时不会计算第二操作数, 第二操作数的副作用也不会发生.

对于与运算, 如果他左边的表达式(也叫第一操作数)计算完是真的话, 无论右边的表达式(也叫第二操作数)的结果是多少, 最终的结果一定是真, 因此此时不会计算第二操作数, 第二操作数的副作用也不会发生.

如, 对于以下代码:

1
2
3
4
5

int a,b,c;
a = 1;
b = 1;
c = a++ || b++;
printf("%d%d%d\n",a,b,c);

因为表达式a++的计算结果为1, 也就是真, 因此不会计算b++, 程序会输出211.

蓝桥杯北京工业大学模拟赛 2020.03.15

1. 问题描述

在计算机存储中，15.125GB是多少MB？

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果 为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

2. 问题描述

1200000有多少个约数（只计算正约数）。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

3. 问题描述

在1至2019中，有多少个数的数位中包含数字9？

注意，有的数中的数位中包含多个9，这个数只算一次。例如，1999这个数包含数字9，在计算只是算一个数。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

4. 问题描述

一棵包含有2019个结点的树，最多包含多少个叶结点？

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

5. 问题描述

一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如1135是一个数位递增的数，而1024不是一个数位递增的数。

给定正整数 n，请问在整数 1 至 n 中有多少个数位递增的数？

输入格式

输入的第一行包含一个整数 n。

输出格式

输出一行包含一个整数，表示答案。

样例输入

1

30

样例输出

1

26

评测用例规模与约定

对于 40% 的评测用例，1 <= n <= 1000。

对于 80% 的评测用例，1 <= n <= 100000。

对于所有评测用例，1 <= n <= 1000000。

6. 问题描述

小明对类似于 hello 这种单词非常感兴趣，这种单词可以正好分为四段，第一段由一个或多个辅音字母组成，第二段由一个或多个元音字母组成，第三段由一个或多个辅音字母组成，第四段由一个或多个元音字母组成。

给定一个单词，请判断这个单词是否也是这种单词，如果是请输出yes，否则请输出no。

元音字母包括 a, e, i, o, u，共五个，其他均为辅音字母。

输入格式

输入一行，包含一个单词，单词中只包含小写英文字母。

输出格式

输出答案，或者为yes，或者为no。

样例输入1

1

lanqiao

样例输出2

1

yes

样例输入1

1

world

样例输出2

1

no

7. 问题描述

在数列 a[1], a[2], …, a[n] 中，如果对于下标 i, j, k 满足 0<i<j<k<n+1 且 a[i]<a[j]<a[k]，则称 a[i], a[j], a[k] 为一组递增三元组，a[j]为递增三元组的中心。

给定一个数列，请问数列中有多少个元素可能是递增三元组的中心。

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数 a[1], a[2], …, a[n]，相邻的整数间用空格分隔，表示给定的数列。

输出格式

输出一行包含一个整数，表示答案。

样例输入

1
2

5
1 2 5 3 5

样例输出

1

2

样例说明

a[2] 和 a[4] 可能是三元组的中心。

评测用例规模与约定

对于 50% 的评测用例，2 <= n <= 100，0 <= 数列中的数 <= 1000。

对于所有评测用例，2 <= n <= 1000，0 <= 数列中的数 <= 10000。

8. 问题描述

小明想知道，满足以下条件的正整数序列的数量：

1. 第一项为 n；

2. 第二项不超过 n；

3. 从第三项开始，每一项小于前两项的差的绝对值。
   计算，对于给定的 n，有多少种满足条件的序列。

输入格式

输入一行包含一个整数 n。

输出格式

输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。

样例输入

1

4

样例输出

1

7

样例说明

以下是满足条件的序列：

1
2
3
4
5
6
7

4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4

评测用例规模与约定

对于 20% 的评测用例，1 <= n <= 5；

对于 50% 的评测用例，1 <= n <= 10；

对于 80% 的评测用例，1 <= n <= 100；

对于所有评测用例，1 <= n <= 1000。

9. 问题描述

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。

小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。

这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。

请告诉小明，k 个月后空地上哪些地方有草。

输入格式

输入的第一行包含两个整数 n, m。

接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。

接下来包含一个整数 k。

输出格式

输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。

样例输入

1
2
3
4
5
6

4 5
.g...
.....
..g..
.....
2

样例输出

1
2
3
4

gggg.
gggg.
ggggg
.ggg.

评测用例规模与约定

对于 30% 的评测用例，2 <= n, m <= 20。

对于 70% 的评测用例，2 <= n, m <= 100。

对于所有评测用例，2 <= n, m <= 1000，1 <= k <= 1000。

10. 问题描述

小明要组织一台晚会，总共准备了 n 个节目。然后晚会的时间有限，他只能最终选择其中的 m 个节目。

这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。

小明发现，观众对于晚上的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。

小明给每个节目定义了一个好看值，请你帮助小明选择出 m 个节目，满足他的要求。

输入格式

输入的第一行包含两个整数 n, m ，表示节目的数量和要选择的数量。

第二行包含 n 个整数，依次为每个节目的好看值。

输出格式

输出一行包含 m 个整数，为选出的节目的好看值。

样例输入

5 3
3 1 2 5 4

样例输出

3 5 4

样例说明

选择了第1, 4, 5个节目。

评测用例规模与约定

对于 30% 的评测用例，1 <= n <= 20；

对于 60% 的评测用例，1 <= n <= 100；

对于所有评测用例，1 <= n <= 100000，0 <= 节目的好看值 <= 100000。

从结构体走向对象

本文能够让你大致理解面向对象的一些概念, 但是以下一切内容均不适用于参加OO课程的考试, 如果爆零, 后果自负.

部分语法的介绍

1. C++语言中, 定义结构体变量时, 类型中的struct可以省略, 如"struct 结构体名 变量名"可以简写为"结构体名 变量名 ". 以下均为简写形式.
2. Java语言中, 所有内置的大写开头的类型都是类, 所有对象都是"引用变量", 可以理解为不能做运算的指针.
   (指针运算指, 数组首项地址+1等于第二项地址的这种运算.)
   如:

   1 2 3 4 5 6

   // int不是类, 是基本类型 // a是普通变量: int a = 0; // Integer是类, b,c是引用变量: Integer b = 0; Integer c = 0;

   上面的代码可以简单地理解为, a是一个int类型变量, 内容是0.
   b是一个指向Integer变量的指针, 他指向的值是0.
   c同理.
   因此, b==c 判断的是b和c是否指向同一个对象. 判断b和c相等应该用b.equals(c).
3. 这篇推送只讲概念, 不需要完全理解代码是什么意思, 具体语法部分都做了注释. 之后大概还会有推送来讲语法. 如果那里有代码不明白什么意思欢迎联系我或者后台给我留言.

类

啥是类? 最简单的来说, 就是 C 语言中的结构体.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
 * 定义一个类, 叫做Student.
 */
public class Student {
    /**
     * Student中的一个字符串类型的变量
     */
    String name;

    /**
     * Student中一个int类型的变量
     */
    int ID;
}

在最开始非面向对象的编程中, 我们经常会用多个变量来描述同一对象的多个属性: 比如定义一个名字变量, 一个学号变量. 后来, 随着计算机科学的发展, 编程语言中支持了 结构体 这样一个特性, 能够让我们把 描述同一个东西不同属性 的多个变量统一管理. 结构体这一个概念, 到了面向对象的语言中, 结构体发展为了类的概念.

可以把类理解为C语言中的结构体+方法.

方法

在很多情况下, 我们之前编写的一些函数是针对某一个结构体提供的. 比如, 链表的删除某个节点的函数就可以认为是针对某个节点定义的, 效果是删除这个节点后面的一个节点.

我们可以把这样的函数定义为一个全局的函数, 把一个结构体变量作为参数传入这个函数:

1
2
3

node* remove(node *now){
    ...
}

但是, 如果这样自定义我们就会在别的任何地方都没法再次定义一个 remove 函数了. 这个只针对 node* 的函数占据了一个全局的名字 (或者说, 符号). 无疑, 这样的实现非常 不优雅. 因此, 我们更应该把进和 node* 这一个变量相关的函数定义成一个 node* 的 成员函数, 也叫 方法.

1
2
3
4
5
6
7
8
9
10
11

struct node {
    int data;
    node *;

    node* remove(){
// 使用this指针访问当前的变量
// 这里仅仅演示如何使用
// 本程序并无法真的工作.
        return this->next;
    }
};

如果这样定义remove函数, 就不会污染全局的作用域, 同时也不用我们显示的声明参数, 只需要如下调用:

1
2

node* a;
a->remove();

即可自动把 a 或 a的地址 作为 this指针 参数传入给 remove 函数.

因此, 方法就是针对某一个类的函数, 为了方便我们把它放到类里面. 构造一个对象的函数是一个特殊的成员函数, 叫做类的构造函数.

继承

其实, 编程语言演进的过程就是一代代程序程序员偷懒的过程 . 自从有了结构体的方法这东西之后, 人们就在想如果好几个结构体都有相同的方法, 能不能直接重复用一下?

比如对于如下几个结构体:

1
2
3
4
5
6
7
8

struct shirt{ 
    double price = 9.15;
    void printPrice();
};
struct trousers {
    double price = 2.33;
    void printPrice();
};

这两个结构体都分别有一个printPrice函数, 内容也都是一样的, 但是要写两次, 非常的不优雅, 于是人们引入了继承的概念:

May there be inheritance!

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Clothes {
    double price;
    void printPrice(){
        // 输出price
    }
}
// 定义Shirt类, 继承 Clothes 类.
class Shirt extends Clothes{
    double price = 9.15;
}
// 同上, 继承 Clothes 类.
class Trousers extends Clothes{
    double price = 2.33;
}

这样, printPrice 函数只需要写一次. 从某个类继承, 或者说派生出来的类, 会拥有父类的所有属性以及方法. 子类也可以对应的重写这些方法.

同时, 对于以上的代码中, 显然 Clothes 类和别的类有一个很大的区别. 我们会创建一个 Shirt 类的对象, 但是我们不会执行 new Clothes(). Clothes 类存在的意义在于提供给别人继承, 我们不会实例化这个类, 因此我们把这个类定义为抽象类(abstract class):

1
2
3
4
5
6
7

// 定义抽象类
abstract class Clothes {
    double price;
    void printPrice(){
        System.out.println(this.price);
    }
}

一个抽象类的意义是提供给别人来继承. 代码中的 abstract 标记了这是一个抽象类.

多态

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

// 定义抽象类 Animal
abstract class Animal {
    // 要求继承这个类的类必须实现
    // bark方法, 同时提供一个默认的
    // bark方法.
    void bark(){
        System.out.println("bark");
    }
}

// 定义dog继承自animal
class Dog extends Animal{
    // 重写bark方法
    void bark(){
        System.out.println("Woof");
    }
}

// 定义cat继承自animal
class Cat extends  Animal{
    // 重写bark方法
    void bark(){
        System.out.println("Meow~");
    }
}

上述代码中, Animal类规定了继承他的类要实现 bark() 方法. 那么, 对于如下的代码, 会输出什么呢?

1
2
3
4
5

Animal a = new Dog();
// 创建一个Dog, 进行隐式类型转换,
// 转换为 Animal.

a.bark();

上面说到, Java中类的变量都是引用变量, 因此上面代码可以不严谨的理解为: 定义一个 指向Animal类型的指针 a,

在这里, a 是一个Animal类型的引用, 指向一个Dog对象. 但是, 尽管他是 Animal 类型的引用, 调用 a.bark()时仍然调用的是 Dog 的 bark() 方法.

多态, 狭义上指同一个名字(符号)指代多个物体. 在上面代码中, 如果不知道a指向的类型是什么, 调用 a.bark() 有三种可能的情况. 这就利用了多态的性质.

例子以及面向对象的好处.

在C语言中, 由于没有这些特性, 极大地存在着代码冗余重复的现象, 如: printf 函数用于格式化并向控制台输出内容, sprintf 用于格式化并向字符串写入内容, fprintf 用于格式化并向文件写入内容.

上面的三个函数, 都完成了格式化这一个步骤, 但是代码被编写了三次. 如果需要向网络连接中格式化并写入内容, 则又需要重复一遍格式化的操作. 面向对象就能很好地解决这个问题.

如, 如果我们要向一个文件写入内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 注: 下面的注释从里往外看

// 把新建的缓存输出流对象作为参数
// 传入格式化输出流
PrintWriter out = new PrintWriter(

    // 把新建的编码输出流对象
    // 作为参数传入给缓存输出流
    // 让缓存输出流对象往
    // 编码输出流输出
    new BufferedWriter(

        // 把新建的文件输出流对象
        // 作为参数, 传入编码输出流, 
        // 规定编码输出流把编码后
        // 的内容输出到文件输出流
        new OutputStreamWriter(

            // 新建一个文件输出流对象
            // 写入filename.txt
            new FileOutputStream("filename.txt")
        )
    )
);

上面代码中, 几个类的构造函数分别为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

FileOutputStream(String name)
// 文件输出流, 参数是文件名
// 向指定文件输出内容
// 只能输出二进制的数据

OutputStreamWriter(OutputStream out)
// 编码输出流, 向某个输出流输出
// 除了接受二进制数据还可以接受字符串
// 将字符串编码后输出

BufferedWriter(Writer out)
// 缓存编码输出流
// 输入的东西缓存后输出

PrintWriter(Writer out)
// 格式化流
// 把输入的东西按照格式要求
// 变成字符串, 传入底层流.

可以看到, FileOutputStream 接受文件名作为参数, 单纯负责向文件中写入内容.

OutputStreamWriter 接受任何 OutputStream 对象, 用于转换写入内容的编码.

BufferedWriter 接受一个 Writer, 用于缓存即将写入 Writer 的内容.

PrintWriter 接受一个 Writer, 用于格式化输入, 写入 Writer 中.

高内聚, 低耦合的设计模式就体现在了这里: 一个 OutputStream 类只需要实现 write 方法, 只能写入二进制字节数据, 而一个 Writer 负责处理编码问题, 可以写入字符串, 负责把写入的字符串编码为二进制字节数据, 而 BufferedWriter 则负责缓存上层写入的内容, 也同样只提供了写入字符串的方法. PrintWriter 负责提供格式化的方法, 可以格式化并写入 int double char string 等多种类型.

这样的设计, 使得功能的拓展变得很方便, 比如我们要向一个自定义的东西中写入数据, 完全可以只实现一个 OutputStream 而复用 OutputStreamWriter, BufferedWriter, PrintWriter 等很多和写入数据有关的类.

所以, 这样的实际模式大概是被不断加需求改需求的产品经理逼出来的

感谢 ☁️学长,

(如果可以的话, 能关注一下这个公众号吗)

蓝桥杯校内模拟赛题解-1

1. 在计算机存储中，15.125GB是多少MB？

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。

答案: 15488

解析:

还要解析???

2. 1200000有多少个约数（只计算正约数）。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。

答案: 96

解析:

1. 暴力解法:

1
2
3
4
5
6

int ans = 0;
for(int i = 1; i <= 1200000; ++ i) {
    if(1200000 % i == 0) {
        ++i;
    }
}

2. 一般解法:
   分解质因数, 得: 1200000 = 2^735^5.

约数个数为等于: 826 = 96.

3. 在1至2019中，有多少个数的数位中包含数字9？

注意，有的数中的数位中包含多个9，这个数只算一次。例如，1999这个数包含数字9，在计算只是算一个数。

答案: 544

解析:

1. 快速解法:

1
2
3
4
5
6
7

int ans = 0;
for(int i = 1; i <= 2019; ++ i){
    if(to_string(i).find("9") != string::npos){
        ans++;
    }
}
cout<<ans<<endl;

2. 一般解法:

1
2
3
4
5
6
7
8
9
10
11
12

int ans = 0;
for(int i = 1; i <= 2019; ++ i){
    int now = i;
    while(now){
        if(now % 10 == 9){
            ans ++;
            break;
        }
        now /= 10;
    }
}
cout<<ans<<endl;

4. 一棵包含有2019个结点的树，最多包含多少个叶结点？

答案: 2018, 如果题目问的是二叉树就是1010.

解析:

正常的树叶子节点最多显然2018个. 如果是二叉树, 为了保证叶子节点最多我们要使得每一个非叶子节点都有两个孩子. 显然, 一棵满二叉树满足这个条件.

对于一个2047个节点的满二叉树, 共有1024个叶子节点, 我们**“成对的”**删去其中的28个之后, 正好剩余2019个节点. 删掉了28个叶子节点后, 他们的父节点也就成为了新的叶子节点, 因此叶子节点减少了14个. 答案就是1024 - 14.

上述证明不严谨

5. 问题描述

一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如1135是一个数位递增的数，而1024不是一个数位递增的数。

给定正整数 n，请问在整数 1 至 n 中有多少个数位递增的数？

输入格式

输入的第一行包含一个整数 n。

输出格式

输出一行包含一个整数，表示答案。

样例输入

1

30

样例输出

1

26

评测用例规模与约定

对于 40% 的评测用例，1 <= n <= 1000。

对于 80% 的评测用例，1 <= n <= 100000。

对于所有评测用例，1 <= n <= 1000000。

题解:

暴力即可, 时间复杂度为 O(n * log10(n)).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int n = 0;
int ans = 0;
cin>>n;
for(int _ = 1; _ <= n; ++ _) {
    int i = _;
    int flag = 1;
    int last = i % 10;
    while(1){
        i /= 10;
        if(i == 0) {
            break;
        }
        if(last >= i % 10) {
            last = i % 10;
        }else{
            flag = 0;
            break;
        }
    }
    ans += flag;
}
cout<<ans<<endl;

6. 问题描述

小明对类似于 hello 这种单词非常感兴趣，这种单词可以正好分为四段，第一段由一个或多个辅音字母组成，第二段由一个或多个元音字母组成，第三段由一个或多个辅音字母组成，第四段由一个或多个元音字母组成。

给定一个单词，请判断这个单词是否也是这种单词，如果是请输出yes，否则请输出no。

元音字母包括 a, e, i, o, u，共五个，其他均为辅音字母。

输入格式

输入一行，包含一个单词，单词中只包含小写英文字母。

输出格式

输出答案，或者为yes，或者为no。

样例输入1

1

lanqiao

样例输出2

1

yes

样例输入1

1

world

样例输出2

1

no

解析

暴力即可, 时间复杂度O(n).

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

inline bool aeiou(char c) {
    return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u';
}
int pos = 0;
int count = 0;
int size = str.size();
for (; pos < size; ++pos) {
    if (!aeiou(str[pos])) {
        count++;
    } else {
        break;
    }
}
if (count == 0) {
    cout << "no" << endl;
    return 0;
}
count = 0;
for (; pos < size; ++pos) {
    if (aeiou(str[pos])) {
        count++;
    } else {
        break;
    }
}
if (count == 0) {
    cout << "no" << endl;
    return 0;
}
count = 0;
for (; pos < size; ++pos) {
    if (!aeiou(str[pos])) {
        count++;
    } else {
        break;
    }
}
if (count == 0) {
    cout << "no" << endl;
    return 0;
}
count = 0;
for (; pos < size; ++pos) {
    if (aeiou(str[pos])) {
        count++;
    } else {
        break;
    }
}
if (count == 0) {
    cout << "no" << endl;
    return 0;
}
cout << "yes" << endl;

7. 问题描述

在数列 a[1], a[2], …, a[n] 中，如果对于下标 i, j, k 满足 0<i<j<k<n+1 且 a[i]<a[j]<a[k]，则称 a[i], a[j], a[k] 为一组递增三元组，a[j]为递增三元组的中心。

给定一个数列，请问数列中有多少个元素可能是递增三元组的中心。

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数 a[1], a[2], …, a[n]，相邻的整数间用空格分隔，表示给定的数列。

输出格式

输出一行包含一个整数，表示答案。

样例输入

1
2

5
1 2 5 3 5

样例输出

1

2

样例说明

a[2] 和 a[4] 可能是三元组的中心。

评测用例规模与约定

对于 50% 的评测用例，2 <= n <= 100，0 <= 数列中的数 <= 1000。

对于所有评测用例，2 <= n <= 1000，0 <= 数列中的数 <= 10000。

题解

乍一看1e5还以为不能暴力, 结果一看n的范围是1e3, 果断暴力走起, 复杂度O(n^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int n = 0;
int data[1010] = {0};
cin>>n;
for(int i = 0; i < n; ++ i){
    cin>>data[i];
}
int ans = 0;
for(int i = 0; i < n; ++ i) {
    int flag = 0;
    for(int j = i-1; j >= 0; -- j){
        if(data[j] < data[i]){
            flag += 1;
            break;
        }
    }
    for(int j = i+1; j < n; ++ j){
        if(data[j] > data[i]){
            flag += 1;
            break;
        }
    }
    ans += (flag == 2);
}
cout<<ans<<endl;

Go 语言中让某个协程无限堵塞的几种方式.

Go 语言自带的 goroutine 特性会让我们需要在某些时候由 main 函数启动一些协程之后就无限阻塞, 让别的协程处理问题. 以下是一些方式:

死循环法

1

for {;}

使用这种方式会让你的程序 随机暴毙, 无法 Debug 找到问题出在哪儿.

原因: go 语言中的 goroutine 并不是线程, 当且仅当遇到系统调用和io操作等时候会主动让出自己的时间片等待外部数据. 但是, 当程序运行死循环的时候 并没有任何io操作, 不会主动让出自己的时间片. 又由于线程调度的原因, 程序会在一个随机时间进入死循环执行, 导致整个程序所有协程全部卡死.
Update: 新的版本的go语言中提供了抢占式的协程调度，不会出现这个卡死的问题。但是仍然不推荐使用这种方式。为什么要浪费CPU时间呢
不仅如此, 由于系统会在别的协程进行io操作的时候进行协程调度, 因此 表面上观察到的现象是别的协程在进行io操作的时候堵死整个程序 , 几乎无法找到bug在哪儿 🌝

死循环让出时间片法

1
2
3

for {
    runtime.Gosched()
}

死循环执行 runtime.Gosched() 这一函数, 执行这个函数会让出当前协程的时间片, 稍后再回到此协程. 不会出bug, 但是效率偏低. (因为仍然在不断地切换到这个协程.)

死循环Sleep法

1
2
3

for {
    time.Sleep(Time.Hour)
}

同上, 仍然有轻微的(但完全可以忽略)效率问题, 但是这样实现十分不优雅.

阻塞的读取空数据法:

1
2

blockChan := make(chan int)
a := <- blockChan

这种方法创建一个不会有数据的 Channel, 并试图从中读取数据. 因为永远读不到数据, 因此会堵塞这个协程.

无效率问题, 但是实现仍然不优雅.

WaitGroup法:

1
2
3

w := sync.WaitGroup{}
wg.Add(1)
wg.Wait()

创建一个WaitGroup, 调用 wait 方法无限等待. 无效率问题, 但是仍然不优雅(要写三行).

Select法:

1

select{}

select被用于同步或异步的从Channel中读取数据. 因为这里没有指定任何Channel, 同时没有default来进行异步读取, 程序会阻塞的试图从没有channel中读取数据.

没有创建任何变量, 0内存开销, 同时调度器也再也不会调度这个协程, 也同样没有性能开销.

(关键是只要一行)

Raw String 的巨坑

众所周知, 在编程语言中\字符有着特别的意义. 在一个字符串中, \字符会 “转义” 紧接着他的一个字符. 如, \n 会被转义为换行符, \t 会被转义为制表符等. 这种做法极大地方便了编程, 给予了我们一种方便的在字符串字面量 (源代码中的固定的量) 中表示一个无法输入的或者会破坏语法结构的字符的方式.

但是, 在有大量\的情况下我们不希望字符串中的 \ 字符被转义, 如在表示地址或正则表达式的时候. 因此, 很多语言提供了 Raw String 字面量, 在 Raw string 字面量中 \ 字符被视为普通的字符而不是转义符. 正如 Python 文档中描述的:

Both string and bytes literals may optionally be prefixed with a letter ‘r’ or ‘R’; such strings are called raw strings and treat backslashes as literal characters.

字符串与字节字面量都可以以一个 r 或者 R 前缀来表示原始字符串. 在原始字符串中, \ 字符被当做普通字符而不是转义符来处理.

正如, 在Python中:

1
2

>>> print(r"asd\nsd\nsd")
asd\nsd\nsd

\n 会保持原样输出而不是被替换为换行符.

那么, 问题来了: 下面的代码会输出什么?

1

print(r"\")

可能看到语法高亮的颜色不太对劲就会让你意识到, 在Python中输出一个这样的字符串会报错而不是输出一个 \ 字符. 在Python文档中这样写道:

Even in a raw literal, quotes can be escaped with a backslash, but the backslash remains in the result; for example, r""" is a valid string literal consisting of two characters: a backslash and a double quote; r"" is not a valid string literal (even a raw string cannot end in an odd number of backslashes). Specifically, a raw literal cannot end in a single backslash (since the backslash would escape the following quote character). Note also that a single backslash followed by a newline is interpreted as those two characters as part of the literal, not as a line continuation.

即使在一个原始字面量中, 引号仍然会被 \ 字符转义, 只不过 \ 字符仍然保留在结果中. 如: r""" 是一个合法的字符串而 r"" 会被认为缺少了一个引号.

这是因为, 在原始字面量的处理中, 并不是去掉了转义. 转义操作仍然在进行, 只不过正常情况下 ‘\n’ 会转移成换行符, 但是在原始字面量中会转移为字符串\n. 在分析那些字符需要转义的时候, 编译器(或者说解释器)并不清楚这个字符是否在一个 Raw String 中. 编译器会把他标记为需要转义, 在之后的步骤中再完成具体的转移操作. 但是对于 r"" 这个字符串, 在第一步的时候编译器会认为 \ 符号转义了后面的", 导致这个字符串的引号数量不匹配, 爆出语法错误.

(所以锅还是得丢给编译器)

注: 上文中编译器指广义上的编译器或解释器等.

感谢群里的小伙伴们, 没有你们的帮助和讨论就不会有这篇文章.