【刷题笔记(编程题)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种

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;
}