刚刚分流结束，进入了计科的计算机工程，算是阴差阳错圆了最初的梦想，当然了，也只能以不正当手段实习了，以后~ 同学们一起好好造电脑( 一想到还跟颜神同班同学就好开心啊~:heart_eyes:

正文开始@一个人的乐队:guitar:

Day 07

复习一些小知识点：

构造函数中，成员变量一定要通过初始化列表来初始化的是？
静态成员不用，因为它由类对象共享，在类外初始化一次就行。
关于友元函数，要把握住友元函数不是成员函数。

1. Fibonacci数列

题目链接：Fibonacci数列_牛客题霸_牛客网 (nowcoder.com)

很简单的题目，就是一个斐波那契数列求解，你早该烂熟于心了。

#include<iostream>

using namespace std;

int main() 
{
    int N = 0;
    cin >> N;
    int count = 0;
    int a = 0;
    int b = 1;
    int c = 0;
    
    while (1) 
    {
        c = a + b;
        a = b;
        b = c;
        if (c > N)
            break;
    }
    int x = b - N;
    int y = N - a;
    cout << (x < y ? x : y) << endl;
    return 0;
}

2. 合法括号串

题目链接：合法括号序列判断_牛客题霸_牛客网 (nowcoder.com)

这是栈和队列的经典题目，思路可以回看我之前的文章，当然了，咱们现在直接用STL.

你还是得注意)这样的情况。

class Parenthesis {
public:
    bool chkParenthesis(string A, int n) {
        // write code here
        stack<char> st;
        for(auto e : A)
        {
            if (e == '(')
            {
                st.push(e);
            }
            else if (e == ')')
            {
                if (st.empty())
                    return false; //多出了右半边
                else
                    st.pop();
            }
            else
                return false;
        }

        return st.empty(); //多出了左半边
    }
};

Day 08

复习一些小点：

拷贝构造函数调用场景：

// 1.传参
void Fun(A a) {}
// 2.传返回值
A Fun()
{
    A a;
    return a;
}

一道非常经典的题目：如下代码共调用多少次拷贝构造函数？7次

Widget fun(Widget u)
{
    Widget v(u);
    Widget w = v;
    return w;
}

int main()
{
    Widget x;
    Widget y = fun(fun(x));
    return 0;
}

经过分析应当是9次：

但事实上，编译器在返回处会做一些优化：因此是7次

为了方便观察，我们打印一下进行调试观察：

class Widget
{
public:
    Widget()
    {
        cout << "Widget()" << endl;
    }

    Widget(const Widget& w)
    {
        cout << "Widget(const Widget& w)" << endl;
    }

    Widget& operator=(const Widget& w)
    {
        cout << "Widget& operator=(const Widget& w)" << endl;
    }

    ~Widget()
    {
        cout << "~Widget()" << endl;
    }
};

如果友元函数重载一个运算符时，其参数表中没有任何参数则说明该运算符是？
```
A 一元运算符
B 二元运算符
C 重载错误
```
运算符重载有这样两种情况：
- 重载成类的成员函数：由于隐藏的this指针的存在，形参数目比看起来多1
- 重载成类的友元函数：必须有一个类类型参数

1. 字典序排序

题目链接：两种排序方法_牛客题霸_牛客网 (nowcoder.com)

关键在于字典序排序，别忘了C++中是可以直接进行字符串大小比较的。

#include<iostream>
#include<string>
#include<vector>

using namespace std;

bool isLength(vector<string>& v)
{
    int i = 1;
    for(int i = 0; i<v.size()-1;i++)
    {
        if (v[i].size() > v[i + 1].size()) 
        {
            return false;
        }
    }
    return true;
}

bool isLexicographically(vector<string>& v) {
    for(int i = 0;i < v.size()-1;i++)
    {
        if (v[i]>v[i + 1]) 
        {
            return false;
        } 
    }
    return true;
}

int main() 
{
    int n = 0;
    cin >> n;
    vector<string> v(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> v[i];
    }
    if (isLength(v) && isLexicographically(v))
        cout << "both" << endl;
    else if (isLexicographically(v))
        cout << "lexicographically" << endl;
    else if (isLength(v))
        cout << "lengths" << endl;
    else
        cout << "none" << endl;
    return 0;
}

2. 求最小公倍数

题目链接：求最小公倍数_牛客题霸_牛客网 (nowcoder.com)

法一：暴力硬解，从两数较大的开始枚举，当然了，你面试时候写这个就寄了。。但这也就笔试考考吧~

#include<iostream>

using namespace std;

int main()
{
    int A, B;
    cin >> A >> B;
    int n = A > B ? A : B;
    while (1)
    {
        if (n%A == 0 && n%B == 0)
        {
            break;
        }
        n++;
    }
    cout << n << endl;
    return 0;
}

法二：需要一个数学知识，两个数的最小公倍数，是两个数的乘积除以最大公约数

最大公约数你固然可以暴力枚举，但是辗转相除法求取非常快：除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，这是高中填选设计程序框图就爱出的，当时怎么也没想来学计算机呀！

// 辗转相除法如下：24/36
36/24 = 1 余12
24/12 = 2 余0 取除数12   
---------------------------
虽然叫做辗转相除法，但是在程序中都是用余数来判断的
36%24 = 12
24%12 = 0 此时取除数12

代码如下 ——

int main()
{
    int A, B;
    cin >> A >> B;
    int a = A;
    int b = B;
    while(int c = a%b)
    {
        a = b;
        b = c;
    }
    cout << (A*B)/b << endl;
    return 0;
}

Day 09

来复习一波知识点：

new/delete 底层实现原理

malloc/realloc/calloc —— free
new —— delete
new [] —— delete[]

一定要匹配使用，否则可能产生内存泄漏/程序崩溃。

new T
    1.调用operator new(size)申请空间-->底层调用malloc
    2.调用T的构造函数，对申请的空间初始化
delete p
    1.调用析构函数释放p指向对象中的资源
    2.调用operator delete释放p指向的空间-->底层调用free
注：new/delete只能释放单个元素的空间

new T[N]
    1.调用operator new [](size)申请空间-->底层调用operator new(size)申请空间
    2.调用N次T的构造函数
delete[] p
    1.调用N次析构函数释放p指向的N个对象
    2.调用operator delete[] p释放空间-->底层调用的是operator delete(p)释放空间

对于静态成员变量：是可以用对象.或者类名::来访问的
不能在类内初始化？有这样一个特例，用const修饰时
```
class A
{
private:
    const static int _a = 10;
    static int _b;
};

int A::_b = 20;
```

模板声明中typename和class可以混用

1. 另类加法

题目链接：另类加法_牛客题霸_牛客网 (nowcoder.com)

显然只能通过位运算，我去，这不就是那个数字逻辑的半加器嘛 ——

当前二进制位的项S：a^b
进位项C：a&b << 1

直至两项中其中一个值为0递归结束。

1+3 = ?
0001
0011
_____________________________
S = 0010
C = 0010
_____________________________
S = 0000
C = 0100 此时有一个数为0，则另一个数即是两数之和

代码如下——

class UnusualAdd {
public:
    int addAB(int A, int B) {
        // write code here
        if(A == 0)
            return B;
        if(B == 0)
            return A;
        int S = A^B;
        int C = (A&B)<<1; 
        return addAB(S, C);
    }
};

2. 走方格的方案数

题目链接：走方格的方案数_牛客题霸_牛客网 (nowcoder.com)

今天是递归专场吧。。大事化小，小事化了。

所有问题归结为相同的子问题：向右/向下
走到终点，则找到一个解决方案

#include<iostream>

using namespace std;

int n = 0;
int m = 0;
int count = 0;

void Route(int i, int j)
{
    if(i == n && j == m)
        count++;
    if(i < n)
        Route(i+1, j);
    if(j < m)
        Route(i, j+1);
}

int main()
{
    cin >> n >> m;
    Route(0, 0);
    cout << count << endl;
    return 0;
}

Day10

咱还是来巩固一下小知识点吧！

C++语言中不能重载的是：.、.*、::、? : 、sizeof其实你也该明白，重载这些干什么？！
初始化顺序，与该成员在初始化成员在初始化列表出现的次序无关，而与成员在类中出现的先后次序保持一致；在继承体系中，同理，与在初始化列表出现的次序无关，而与继承顺序相关。

C/C++中被const修饰的常量，能否被修改？yes

#include <iostream>

using namespace std;

int main(void) {
    const int a = 10;
    int* p = (int*)(&a);
    *p = 20;
    cout << "a = " << a << ", *p = " << *p << endl;
    return 0;
}

这种走后门的方式的确修改了a的值。。但是我们打印时，却惊奇的发现a还是10？

这是因为，编译器编译时，发现在读取常量中的内容时，会直接用常量的内容替换。

1. 三子棋

咱就是说，这破题也太没水准了，其实这破题牛客只检查了三子棋的。。

题目链接：井字棋_牛客题霸_牛客网 (nowcoder.com)

class Board {
  public:
    bool checkWon(vector<vector<int>> board) {
        // write code here
        int row = board.size();
        // 1.行
        int sum = 0;
        for (int i = 0; i < row; i++) {
            sum = 0;
            for (int j = 0; j < row; j++) {
                sum += board[i][j];
                if (sum == row)
                    return true;
            }
        }
        
        // 2.列
        for (int j = 0; j < row; j++) {
            sum = 0;
            for (int i = 0; i < row; i++) {
                sum += board[i][j];
                if (sum == row)
                    return true;
            }
        }
        
        // 3.对角线
        sum = 0;
        for(int i = 0;i<row;i++)
        {
            sum += board[i][i];
        }
        if(sum == row)
            return true;
        
        sum = 0;
        for(int i = 0; i<row;i++)
        {
            sum += board[row-i-1][row-i-1];
        }
        if(sum == row)
            return true;
        
        return false;
    }
};

2. 密码强度等级

有一种题，叫做不难但烦。。

题目链接：密码强度等级_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int score = 0;
    
    int length = s.size();
    if (length >= 8)
        score += 25;
    else if (length >= 5)
        score += 10;
    else
        score += 5;
    
    // 检测字母
    bool A = false;
    bool a = false;
    for (auto e : s) {
        if (e >= 'a' && e <= 'z') {
            a = true;
        } else if (e >= 'A' && e <= 'Z') {
            A = true;
        }
    }
    if (A && a)
        score += 20;
    else if (A || a)
        score += 10;
    
    // 检测数字
    bool N = false;
    int count = 0;
    for (auto e : s) {
        if (e >= '0' && e <= '9') {
            N = true;
            count++;
        }
    }
    if (count > 1)
        score += 20;
    else if (count == 1)
        score += 10;
    
    // 检测符号
    bool S = false;
    count = 0;
    for (auto e : s) {
        if ((e >= 0x21 && e <= 0x2F)
                || (e >= 0x3A && e <= 0x40)
                || (e >= 0x5B && e <= 0x60)
                || (e >= 0x7B && e <= 0x7E)) {
            S = true;
            count++;
        }
    }
    if (count > 1)
        score += 25;
    else if (count == 1)
        score += 10;
    
    //奖励
    if (A && a && N && S)
        score += 5;
    else if ((A || a) && N && S)
        score += 3;
    else if ((A || a) && N)
        score += 2;
    
    if (score >= 90)
        cout << "VERY_SECURE" << endl;
    else if (score >= 80)
        cout << "SECURE" << endl;
    else if (score >= 70)
        cout << "VERY_STRONG" << endl;
    else if (score >= 60)
        cout << "STRONG" << endl;
    else if (score >= 50)
        cout << "AVERAGE" << endl;
    else if (score >= 25)
        cout << "WEAK" << endl;
    else
        cout << "VERY_WEAK" << endl;
    return 0;
}

Day11

咱先来复习几个小知识点：

operator=只能作为类的成员函数重载，是对的！
想想~ 好像在类外弄成友元看上去也可以实现这逻辑。但是就是不行，编译器会报错：“operator= 必须是静态成员函数”！
```
// 欢迎用如下代码验证
A& operator=(A& a1, const A& a2)
{
    if(&a1 != &a2)
        a1._a = a2._a;
    return a1;
}
```
静态数据成员（非const类型）必须在类外初始化。嗯嗯，这话真严谨。
又是这个经典的会调用几次构造函数这个题：
若PAT是一个类，则程序运行时，PAT (*ad) [3];，调用PAT的构造函数的次数是：这只是一个数组指针罢了，0次

1. 最近公共祖先

题目链接：最近公共祖先_牛客题霸_牛客网 (nowcoder.com)

经画图找到父子关系：parent = child/2，无论左右孩子

跳出条件：两节点是同一节点
不等，则递归/迭代较大节点的父亲

class LCA {
public:
    int getLCA(int a, int b) {
        // write code here
        while(a != b)
        {
            if(a > b)
                a /= 2;
            else
                b /= 2;
        }
        return a;
    }
};

2. 连续bit1的个数

题目链接：求最大连续bit数_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>

using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    
    int cur = 0;
    int max = 0;
    for(int i = 0; i<32;i++)
    {
        if((n>>i)&1 == 1)
        {
            cur++;
        }
        else
        {
            if(cur > max)
                max = cur;
            cur = 0;   
        }
    }
    if(cur > max)
        max = cur;
    cout << max << endl;
    return 0;
}

这儿有个人(就是我)把它先转成二进制串儿了~ 估计是一下子没想起来怎么拿二进制位。。反正，也行~

#include<iostream>
#include<string>

using namespace std;

int main() {
    int n = 0;
    cin >> n;
    // 转成二进制串儿
    string s;
    while (n / 2) {
        s += (n % 2 + '0');
        n /= 2;
    }
    s += (n % 2 + '0');
    
    int cur = 0;
    int max = 0;
    for (auto e : s) {
        if (e == '1') {
            cur++;
        } else {
            if (cur > max)
                max = cur;
            cur = 0;
        }
    }
    if (cur > max)
        max = cur;
    cout << max << endl;
    return 0;
}

Day12

咱再来复习一波儿知识点？！

一道挺有意思的题：不能通过编译的
```
myClass::~myClass()
{
    delete this;
    this = NULL;
}
```
- 不要在析构函数中delete this，可以通过编译，但运行时会崩溃。因为，众所周知delete要做两个工作：调用析构函数释放对象中资源，调用operator delete(p)释放对象空间(底层是free)，这样陷入无限递归......
- this = nullptr; 是这句编译不过，因为this指针的类型是Type* const this ，不能修改它的指向！
C++中关于堆和栈的说法：堆只能动态分配，栈可以静态或动态分配的。
栈也可以动态吗？是的，你可能没见过，事实上，我也没见过。。C标准库中提供了alloca函数void* __cdecl alloca(size_t)，是在栈上申请空间，且退出栈自动释放，不用手动释放。
有些类就是可以没有拷贝构造函数。。比如你这样A(const A& a) = delete;声明一下，编译器就不再自动生成一份了。

1. 二进制插入

这就是唬人的题。。

题目链接：二进制插入_牛客题霸_牛客网 (nowcoder.com)

class BinInsert {
public:
    int binInsert(int n, int m, int j, int i) {
        // write code here
        return n|(m<<j);
    }
};

2. 查找组成一个偶数最接近的两个素数

题目链接：查找组成一个偶数最接近的两个素数_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>

using namespace std;

bool isPrime(int num) 
{
    for (int i = 2; i < num; i++) 
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

int main() 
{
    int N = 0;
    cin >> N;
    int a = N / 2;
    int b = N / 2;
    while (1) 
    {
        if (isPrime(a) && isPrime(b)) 
        {
            break;
        }
        a--;
        b++;
    }
    cout << a << endl;
    cout << b << endl;
    return 0;
}

【解题周报】week2 解题周报

Day 07

1. Fibonacci数列

2. 合法括号串

Day 08

1. 字典序排序

2. 求最小公倍数

Day 09

1. 另类加法

2. 走方格的方案数

Day10

1. 三子棋

2. 密码强度等级

Day11

1. 最近公共祖先

2. 连续bit1的个数

Day12

1. 二进制插入

2. 查找组成一个偶数最接近的两个素数

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【解题周报】week2 解题周报

Day 07

1. Fibonacci数列

2. 合法括号串

Day 08

1. 字典序排序

2. 求最小公倍数

Day 09

1. 另类加法

2. 走方格的方案数

Day10

1. 三子棋

2. 密码强度等级

Day11

1. 最近公共祖先

2. 连续bit1的个数

Day12

1. 二进制插入

2. 查找组成一个偶数最接近的两个素数

热门文章

最新文章

相关电子书