每日练习-9

目录

1、井字棋

2、密码强度等级

3、二维数组中的查找

4.调整数组奇数偶数

5.旋转数组中的最小元素

6、替换空格

---

1、井字棋

解析：井字棋有四种情况表示当前玩家获胜，行全为1， 列全为1，主对角全为1，  副对角全为1。遍历board的每一行，每一列，每一条对角线，检查是否有连成一排的的棋子，如果有，返回True。如果遍历完没有找到连成一排的棋子，返回False。

代码如下：

class Board {public:bool checkWon(vector<vector<int> > board) {int sum = 0;int row = board.size();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;}}}for (int j = 0; j < row; j++) {//再看每一列sum = 0;for (int i = 0; i < row; i++) {sum += board[j][i];if (sum == row) {return true;}}}//检查主对角线的和是是否等于rowsum = 0;for (int i = 0; i < row; i++) {sum += board[i][i];}if (sum == row)return true;//检查副对角线的和是是否等于rowsum = 0;for (int i = 0; i < row; i++) {sum += board[i][row - i - 1];}if (sum == row)return true;return false;}// write code here
};

2、密码强度等级

解析：这一道题思路很简单，由于不同种类的字符得分不同，同可以对每一个维度进行单独判断，即对于长度，字母，数字，符号单独判断，最后把所有的单项值根据题目要求相加，输出对应的安全级别。

代码如下：

#include <iostream>
#include <string>
using namespace std;
int score_count(string& str) {int digit = 0, symbol = 0;int lower = 0, upper = 0, charc = 0;int size = 0, sum = 0;for (auto ch : str) {if (ch >= 'a' && ch <= 'z') {lower++;charc++;} else if (ch >= 'A' && ch <= 'Z') {upper++;charc++;} else if (ch >= '0' && ch <= '9') {digit++;} else if ((ch >= 0x21 && ch <= 0x2F) ||(ch >= 0x3A && ch <= 0x40) ||(ch >= 0x5B && ch <= 0x60) ||(ch >= 0x7B && ch <= 0x7E)) {symbol++;}}size = str.size();if (size <= 4)sum += 5;else if (size <= 7)sum += 10;elsesum += 25;if (lower > 0 && upper > 0)sum += 20;else if (lower == charc || upper == charc)sum += 10;if (digit == 1)sum += 10;else if (digit > 1)sum += 20;if (symbol == 1)sum += 10;else if (symbol > 1)sum += 25;if (lower > 0 && upper > 0 && digit > 0 && symbol > 0)sum += 5;else if ((lower > 0 || upper > 0) && digit > 0 && symbol > 0)sum += 3;else if ((lower > 0 || upper > 0) && digit > 0 && symbol == 0)sum += 2;return sum;
}
int main() {string str;while (cin >> str) {int score = score_count(str);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;
}

3、二维数组中的查找

解析：这是一个经典的算法问题，一种常见的方法是从二维数组的右上角或左下角开始，根据目标整数和当前元素的大小关系，逐步缩小查找范围，直到找到目标整数或者超出数组边界。这种方法的时间复杂度是O(m+n)，其中m和n分别是二维数组的行数和列数。

代码如下：

class Solution {public:bool Find(int target, vector<vector<int> >& array) {int row = array.size();int col = array[0].size();int i = 0;int j = col - 1;while (i < row && j > -1) {if (array[i][j] == target) {return true;} else if (array[i][j] > target) {j--;} else if (array[i][j] < target){i++;}}return false;}};

4.调整数组奇数偶数

解析：这是一个数组的奇偶数分割问题，可以用双指针的方法来实现。双指针的方法是用两个变量分别指向数组的头部和尾部，然后同时向中间移动，每次移动时判断当前指向的元素是奇数还是偶数，如果是奇数就保持不变，如果是偶数就和另一个指针指向的元素交换位置，直到两个指针相遇或者交错为止。

代码如下：

class Solution {
public:vector<int> reOrderArrayTwo(vector<int>& array) {int left=0;int right=array.size()-1;int term=0;while(left<right){while(array[left]%2==1){left++;}while(array[right]%2==0){right--;}if(left<right){term=array[left];array[left]=array[right];array[right]=term;}}return array;}
};

5.旋转数组中的最小元素

解析：旋转数组中的最小元素是一个常见的算法问题，可以用二分法来解决。二分法的思路是用两个指针分别指向数组的首尾，然后根据中间元素和右指针指向的元素的大小关系，缩小查找范围，直到找到最小元素或者两个指针相遇。

代码如下：

#include <iostream>
#include<vector>
using namespace std;int main() {vector<int> arr;int n;while(cin>>n){arr.push_back(n);}int left=0;int right=arr.size()-1;while(left<right){int mid=left+(right-left)/2;if(arr[mid]>arr[right]){left=mid+1;}else if(arr[mid]<arr[right]){right=mid;}else right=right-1;}cout<<arr[left]<<endl;return 0;}

6、替换空格

解析：

首先，我们需要遍历字符串s，找出其中有多少个空格，这样我们就可以计算出替换后的字符串长度。然后，我们需要从后往前修改字符串s，使用两个指针i和j，分别指向原字符串和新字符串的末尾。接下来，我们需要判断s[i]是否是空格，如果不是，就直接复制到s[j]，然后i和j都向前移动一位；如果是，就在s[j]处依次填入’0’，‘2’和’%'，然后i向前移动一位，j向前移动三位。最后，我们需要重复上述步骤，直到i和j相等为止，这样就完成了空格的替换。

代码如下：

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @return string字符串*/string replaceSpace(string s) {int count = 0;for (char c : s) {if (c == ' ') count++;}// 如果没有空格，直接返回if (count == 0) return s;// 计算替换后的字符串长度int len = s.length();int newLen = len + count * 2;// 从后往前修改字符串s，使用两个指针i和jint i = len - 1;int j = newLen - 1;// 扩充字符串s的容量s.resize(newLen);// 当i和j不相等时，循环执行while (i != j) {// 如果s[i]不是空格，就复制到s[j]，然后i和j都向前移动一位if (s[i] != ' ') {s[j] = s[i];i--;j--;} else {// 如果s[i]是空格，就在s[j]处依次填入'0'，'2'和'%'，然后i向前移动一位，j向前移动三位s[j] = '0';s[j - 1] = '2';s[j - 2] = '%';i--;j -= 3;}}return s;}
};