【刷题笔记(编程题)05】另类加法、走方格的方案数、井字棋、密码强度等级

1. 另类加法

给定两个int A和B。编写一个函数返回A+B的值，但不得使用+或其他算数运算符。
测试样例：
1,2
返回：3
示例 1
输入
输出

思路1:
二进制0101和1101的相加
0 1 0 1
1 1 0 1
其实就是
不带进位的结果1000
和进位产生的1010相加
无进位加法： 两个二进制数异或后得到的结果
就是它们无进位相加的结果
进位： 两个二进制数按位与后左移1位
就是它们相加的进位结果
在每一轮计算中
利用异或运算符计算不进位部分
利用与运算符和左移运算符计算进位部分
并将进位部分赋值给另一个操作数
直到没有进位为止
最终，不进位部分的结果即为加法的结果

class UnusualAdd {
public:
    int addAB(int A, int B) {
        while (B) {
            int a = A ^ B;
            int b = (A & B) << 1; 
            A = a;
            B = b;
        }
        return A;
    }
};

2. 走方格的方案数

请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
注：沿棋盘格之间的边缘线行走
数据范围：
输入描述
输入两个正整数n和m，用空格隔开。(1≤n,m≤8)
输出描述
输出一行结果
示例 1
输入
2 2
输出
6

思路1: 递归
本题说的是沿着边缘线走
而非在格子里面走
第一步可以往右或往下
起始路径(0, 0)可以选择沿着
(0+1, 0)和(0, 0+1)的路径走
而(0+1, 0)和(0, 0+1)是起始路径(0, 0)的子问题
继续往下递归，用(i, j)表示当前位置
后续限制边界的向下或向右
因为不能走回头路
当向下(向右)走到边界
表示只有向右(向下)这一条路径可走
即可结束递归，无需完全走到右下角

#include <iostream>
using namespace std;

int scheme(int i, int j, int n, int m)
{
    if (i == n || j == m)
        return 1;
    return scheme(i + 1, j, n, m) + scheme(i, j + 1, n, m);
}

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

思路2: 动态规划
用dp[i][j]表示到第 i 行 j 列为止的路径数
它等于到它左边的路径数
加上到它上边的路径数的总和
如果是首行或者首列路径数为1

(0, 0)到(0, 1)只有1条路径
(0, 0)到(1, 0)也只有1条路径
(0, 0)到(1, 1)的路径等于
它左边的路径加上它上边的路径
(0, 0)到(0, 1)的路径加上(0, 0)到(1, 0)的路径
1 + 1 = 2

int main() {
    int n, m;
    while(cin >> n >> m){
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); 
        //dp[i][j]表示到第i行j列为止的路径数
        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= m; j++){
                if(i == 0 && j == 0) //起始位置只有一条路径
                    dp[i][j] = 1;
                else if(i == 0) //起始行，等于左边列的路径
                    dp[i][j] = dp[i][j - 1];
                else if(j == 0) //起始列，等于上边行的路径
                    dp[i][j] = dp[i - 1][j];
                else //等于左边加上边的路径
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        cout << dp[n][m] << endl;
    }
    return 0;
}

3. 井字棋

给定一个二维数组board，代表棋盘，其中元素为1的代表是当前玩家的棋子，0表示没有棋子，-1代表是对方玩家的棋子。当一方棋子在横竖斜方向上有连成排的及获胜（及井字棋规则），返回当前玩家是否胜出。
测试样例：
[[1,0,1],[1,-1,-1],[1,-1,0]]
返回：true
示例 1
输入
输出

思路1:
先判断两个对角线
再for循环判断横纵

class Board {
public:
    bool checkWon(vector<vector<int> > board) {
        if (board[0][0] + board[1][1] + board[2][2] == 3
        || board[0][2] + board[1][1] + board[2][0] == 3)
            return true;
        for (int i = 0; i < board.size(); i++) {
            if (board[i][0]+board[i][1]+board[i][2] == 3)
                return true;
            if (board[0][i]+board[1][i]+board[2][i] == 3)
            	return true;
        }
        return false;
    }
};

4. 密码强度等级

密码按如下规则进行计分，并根据不同的得分为密码进行安全等级划分。
一、密码长度:
5 分: 小于等于4 个字符
10 分: 5 到7 字符
25 分: 大于等于8 个字符
二、字母:
0 分: 没有字母
10 分: 密码里的字母全都是小（大）写字母
20 分: 密码里的字母符合”大小写混合“
三、数字:
0 分: 没有数字
10 分: 1 个数字
20 分: 大于1 个数字
四、符号:
0 分: 没有符号
10 分: 1 个符号
25 分: 大于1 个符号
五、奖励（只能选符合最多的那一种奖励）:
2 分: 字母和数字
3 分: 字母、数字和符号
5 分: 大小写字母、数字和符号
最后的评分标准:
= 90: 非常安全
= 80: 安全（Secure）
= 70: 非常强
= 60: 强（Strong）
= 50: 一般（Average）
= 25: 弱（Weak）
= 0: 非常弱（Very_Weak）
对应输出为：
VERY_SECURE
SECURE
VERY_STRONG
STRONG
AVERAGE
WEAK
VERY_WEAK
请根据输入的密码字符串，进行安全评定。
注：
字母：a-z, A-Z
数字：0-9
符号包含如下： (ASCII码表可以在UltraEdit的菜单view->ASCII Table查看)
!"#KaTeX parse error: Can't use function '\]' in math mode at position 76: …I码：0x3A~0x40) [\̲]̲^_` …@NoNoN
输出
VERY_SECURE
说明
样例的密码长度大于等于8个字符，得25分；大小写字母都有所以得20分；有两个数字，所以得20分；包含大于1符号，所以得25分；由于该密码包含大小写字母、数字和符号，所以奖励部分得5分，经统计得该密码的密码强度为25+20+20+25+5=95分。
示例 2
输入
Jl)M:+
输出
AVERAGE
说明
示例2的密码强度为10+20+0+25+0=55分。

思路1:
用好 if 和 else
对每个安全等级进行判断

#include <iostream>
using namespace std;

int passwordLength(string& s) {
    if (s.size() >= 5 && s.size() <= 7)
        return 10;
    else if (s.size() >= 8)
        return 25;
    else return 5;
}

int passwordLetter(string& s) {
    bool Capital = false, Lowercase = false;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z')
            Capital = true;
        else if (s[i] >= 'a' && s[i] <= 'z')
            Lowercase = true;
    }
    if (Capital == false && Lowercase == false)
        return 0;
    else if (Capital == true && Lowercase == true)
        return 20;
    else return 10;
}

int passwordFigure(string& s) {
    int count = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= '0' && s[i] <= '9')
            count++;
        if (count > 1) return 20;
    }
    if (count == 0) return 0;
    else return 10;
}

int passwordSymbol(string& s) {
    int count = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= 0x21 && s[i] <= 0x2F) count++;
        else if (s[i] >= 0x3A && s[i] <= 0x40) count++;
        else if (s[i] >= 0x5B && s[i] <= 0x60) count++;
        else if (s[i] >= 0x7B && s[i] <= 0x7E) count++;
    }
    if (count == 0) return 0;
    else if (count == 1) return 10;
    else return 25;
}

int passwordAward(int Letter, int Figure, int Symbol) {
    if (Letter == 20 && Figure >= 10 && Symbol >=10)
        return 5;
    else if (Letter == 10 && Figure >= 10 && Symbol >=10)
        return 3;
    else if (Letter == 10 && Figure >= 10)
        return 2;
    else return 0;
}

int main() {
    string s;
    cin >> s;
    int Length, Letter, Figure, Symbol, Award;
    Length = passwordLength(s);
    Letter = passwordLetter(s);
    Figure = passwordFigure(s);
    Symbol = passwordSymbol(s);
    Award = passwordAward(Letter, Figure, Symbol);
    int score = Length + Letter + Figure + Symbol + Award;
    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 if (score >= 0) cout << "VERY_WEAK" << endl;
    
    return 0;
}

class password {
public:
    password(string& s)
    : _pwd(s)
    {}

    void passwordLength() {
        if (_pwd.size() >= 5 && _pwd.size() <= 7)
            _score += 10;
        else if (_pwd.size() >= 8)
            _score += 25;
        else if (_pwd.size() <= 4) _score += 5;
    }

    void passwordLetter() {
        for (auto l : _pwd) {
            if (isupper(l)) 
                _bigLetter = true;
            else if (islower(l))
                _smallLetter = true;
        }
        if (_bigLetter && _smallLetter)
            _score += 20;
        else if (_bigLetter || _smallLetter ) 
            _score += 10;
    }

    void passwordFigure() {
        int count = 0;
        for (auto f : _pwd) {
            if (isdigit(f))  count++;
        }
        if (count >= 1) _Figure = true;
        if (count == 1) _score += 10;
        else if (count > 1) _score += 20;
}

    void passwordSymbol() {
        int count = 0;
        for (auto c : _pwd) {
            if (ispunct(c)) 
                count++;
        }
        if (count >= 1) _Symbol = true;
        if (count == 1) _score += 10;
        else if (count > 1) _score += 25;
    }

    void passwordAward() {
        if (_bigLetter && _smallLetter && _Figure && _Symbol)
            _score += 5;
        else if ((_bigLetter || _smallLetter) && _Figure && _Symbol)
            _score += 3;
        else if ((_bigLetter || _smallLetter) && _Figure)
            _score += 2;
    }

    void getTotalScore() {
        passwordLength();
        passwordLetter();
        passwordFigure();
        passwordSymbol();
        passwordAward();
    }

    void _printGrade() {
        getTotalScore();
        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 if (_score >= 0) cout << "VERY_WEAK" << endl;
    }
private:
    string _pwd;
    int _score = 0;
    bool _bigLetter = false;
    bool _smallLetter = false;
    bool _Figure = false;
    bool _Symbol = false;
};

int main() {
    string s;
    while (cin >> s) {
        password pwd(s);
        pwd._printGrade();
    }

    return 0;
}