开发者社区> 小边小边不秃头> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

【解题周报】week2 解题周报

简介: people change
+关注继续查看

@TOC

刚刚分流结束,进入了计科的计算机工程,算是阴差阳错圆了最初的梦想,当然了,也只能以不正当手段实习了,以后~ 同学们一起好好造电脑( 一想到还跟颜神同班同学就好开心啊~: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. 拷贝构造函数调用场景:

    // 1.传参
    void Fun(A a) {}
    // 2.传返回值
    A Fun()
    {
        A a;
        return a;
    }
  2. 一道非常经典的题目:如下代码共调用多少次拷贝构造函数?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次:

<img src=" title="image-20220707175638866">

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

<img src=" title="image-20220707183037649">

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

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;
    }
};
  1. 如果友元函数重载一个运算符时,其参数表中没有任何参数则说明该运算符是?

    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

来复习一波知识点:

  1. 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)释放空间
  2. 对于静态成员变量:是可以用对象.或者类名::来访问的

    不能在类内初始化?有这样一个特例,用const修饰时

    class A
    {
    private:
        const static int _a = 10;
        static int _b;
    };
    
    int A::_b = 20;

  1. 模板声明中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

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

  1. C++语言中不能重载的是:..*::? :sizeof其实你也该明白,重载这些干什么?!
  2. 初始化顺序,与该成员在初始化成员在初始化列表出现的次序无关,而与成员在类中出现的先后次序保持一致;在继承体系中,同理,与在初始化列表出现的次序无关,而与继承顺序相关。
  3. 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?

    <img src=" title="image-20220709173420563">

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

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

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

  1. operator=只能作为类的成员函数重载,是对的!

    想想~ 好像在类外弄成友元看上去也可以实现这逻辑。但是就是不行,编译器会报错:“operator= 必须是静态成员函数”!

    // 欢迎用如下代码验证
    A& operator=(A& a1, const A& a2)
    {
        if(&a1 != &a2)
            a1._a = a2._a;
        return a1;
    }
  2. 静态数据成员(非const类型)必须在类外初始化。嗯嗯,这话真严谨。
  3. 又是这个经典的会调用几次构造函数这个题:

    若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

咱再来复习一波儿知识点?!

  1. 一道挺有意思的题:不能通过编译的

    myClass::~myClass()
    {
        delete this;
        this = NULL;
    }
    • 不要在析构函数中delete this,可以通过编译,但运行时会崩溃。因为,众所周知delete要做两个工作:调用析构函数释放对象中资源,调用operator delete(p)释放对象空间(底层是free),这样陷入无限递归......
    • this = nullptr; 是这句编译不过,因为this指针的类型是Type* const this ,不能修改它的指向!
  2. C++中关于堆和栈的说法:堆只能动态分配,栈可以静态或动态分配的。

    栈也可以动态吗?是的,你可能没见过,事实上,我也没见过。。C标准库中提供了alloca函数void* __cdecl alloca(size_t),是在栈上申请空间,且退出栈自动释放,不用手动释放。

  3. 有些类就是可以没有拷贝构造函数。。比如你这样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;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
图解Webpack——实现Plugin
图解Webpack——实现Plugin
74 0
阻塞队列实现原理
阻塞队列实现原理
67 0
斯坦福-随机图模型-week2.2_
title: 斯坦福-随机图模型-week2.2 tags: note notebook: 6- 英文课程-9-Probabilistic Graphical Models 1: Representation --- 斯坦福-随机图模型-week2.2 习题 1。
929 0
斯坦福-随机图模型-week2.4_
title: 斯坦福-随机图模型-week2.4 tags: note notebook: 6- 英文课程-9-Probabilistic Graphical Models 1: Representation --- 斯坦福-随机图模型-week2.
911 0
斯坦福-随机图模型-week1.2_
title: 斯坦福-随机图模型-week1.2 tags: note notebook: 6- 英文课程-9-Probabilistic Graphical Models 1: Representation --- 斯坦福-随机图模型-week1.
711 0
Flask学习笔记(2)-login_page
Flask学习笔记(2)-login_page 命令行 1.cd mysite进入mysite目录。2.git log查看git记录后按Q退出。 Code for login_page @app.route("/login/", methods=["GET", "POST"]) def login(): if request.
1159 0
2.2 基于webpack进行开发
Hello world 文件目录 hello --- hello.js --- index.js --- index.html hello.js module.
781 0
【使用 Weex 和 Vue 开发原生应用】 2 编写独立页面
> 系列文章的目录在 [这里](http://www.atatech.org/articles/71868) 在配置完开发环境之后,就可以开始写应用了。在写应用之前,肯定会先划分好页面,一个一个独立着写的。 不过,首先要明确的是,使用 Weex 写出来的是原生应用,页面的概念还和 Web 上一样吗? ## Weex 里“页面”的概念 > 写的有些乱,与下边内容关系不太,不
3610 0
Web2py也有意思的
多学学,以后可以方便的自己写代码了。 对于各种WEB框架,这也是打一个基础的时候。 相信学入门了,对PHP的,JAVA的WEB框架,都是能理解更深入的。 def index(): """ example action using the internationali...
684 0
+关注
小边小边不秃头
计工造电脑人(
59
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载