目录
一、判断数组是否单调
问题描述
测试样例
解题思路:
解题思路
数据结构选择
算法步骤
最终代码:
运行结果:
编辑
二、判断回旋镖的存在
问题描述
测试样例
解题思路:
解题思路
算法步骤
最终代码:
运行结果:
编辑
三、字符串解码问题
问题描述
测试样例
解题思路:
问题理解
数据结构选择
算法步骤
具体步骤
最终代码:
运行结果:
编辑
四、小F的矩阵值调整
问题描述
测试样例
解题思路:
问题理解
数据结构选择
算法步骤
最终代码:
运行结果:
编辑
五、数字字符串中圆圈的数量计算
问题描述
测试样例
解题思路:
问题理解
数据结构选择
算法步骤
具体步骤
最终代码:
运行结果:
编辑
六、小Q的非素数和排列问题
问题描述
测试样例
解题思路
问题理解
数据结构选择
算法步骤
关键点
最终代码:
运行结果:
编辑
一、判断数组是否单调
问题描述
小S最近在研究一些数组的性质,她发现有一种非常有趣的数组被称为 单调数组。如果一个数组是单调递增或单调递减的,那么它就是单调的。
- 当对于所有索引
i <= j
时,nums[i] <= nums[j]
,数组nums
是单调递增的。 - 当对于所有索引
i <= j
时,nums[i] >= nums[j]
,数组nums
是单调递减的。
你需要编写一个程序来判断给定的数组nums
是否为单调数组。如果是,返回true
,否则返回false
。
测试样例
样例1:
输入:
nums = [1, 2, 2, 3]
输出:True
样例2:
输入:
nums = [6, 5, 4, 4]
输出:True
样例3:
输入:
nums = [1, 3, 2, 4, 5]
输出:False
解题思路:
要判断一个数组是否为单调数组,我们需要检查数组是否满足以下两个条件之一:
- 单调递增:对于所有索引
i <= j
,nums[i] <= nums[j]
。 - 单调递减:对于所有索引
i <= j
,nums[i] >= nums[j]
。
解题思路
-
初始化标志:
- 我们可以使用两个布尔变量
isIncreasing
和isDecreasing
来分别表示数组是否单调递增和单调递减。 - 初始时,将这两个变量都设置为
true
。
- 我们可以使用两个布尔变量
-
遍历数组:
- 从数组的第二个元素开始,逐个比较当前元素和前一个元素。
- 如果当前元素小于前一个元素,则将
isIncreasing
设置为false
。 - 如果当前元素大于前一个元素,则将
isDecreasing
设置为false
。
-
判断结果:
- 遍历结束后,如果
isIncreasing
或isDecreasing
中有一个为true
,则说明数组是单调的,返回true
。 - 否则,返回
false
。
- 遍历结束后,如果
数据结构选择
- 使用布尔变量来记录数组的单调性。
算法步骤
- 初始化
isIncreasing
和isDecreasing
为true
。 - 遍历数组,比较相邻元素。
- 根据比较结果更新
isIncreasing
和isDecreasing
。 - 返回
isIncreasing
或isDecreasing
中为true
的结果。
最终代码:
#include <iostream>
#include <vector>
using namespace std;bool solution(vector<int> nums) {// 初始化标志变量bool isIncreasing = true;bool isDecreasing = true;// 遍历数组,从第二个元素开始for (int i = 1; i < nums.size(); ++i) {// 如果当前元素小于前一个元素,则数组不是单调递增if (nums[i] < nums[i - 1]) {isIncreasing = false;}// 如果当前元素大于前一个元素,则数组不是单调递减if (nums[i] > nums[i - 1]) {isDecreasing = false;}}// 如果数组是单调递增或单调递减,返回 truereturn isIncreasing || isDecreasing;
}int main() {bool result1 = solution(vector<int>{1, 2, 2, 3});bool result2 = solution(vector<int>{6, 5, 4, 4});bool result3 = solution(vector<int>{1, 3, 2, 4, 5});cout << (result1 == true) << endl;cout << (result2 == true) << endl;cout << (result3 == false) << endl;
}
运行结果:
二、判断回旋镖的存在
问题描述
小M正在玩一个几何游戏,给定一个二维平面上的三个点 points
,其中每个点用坐标 points[i] = [xi, yi]
表示。如果三点构成一个回旋镖,则返回 true
。回旋镖的定义是三点不在一条直线上,并且这三个点互不相同。
请你帮助小M判断这些点是否构成一个回旋镖。
测试样例
样例1:
输入:
points = [[1, 1], [2, 3], [3, 2]]
输出:True
样例2:
输入:
points = [[1, 1], [2, 2], [3, 3]]
输出:False
样例3:
输入:
points = [[0, 0], [1, 1], [1, 0]]
输出:True
解题思路:
要判断三个点是否构成一个回旋镖,我们需要确保以下几点:
-
三点不共线:三个点不能在同一条直线上。可以通过计算斜率来判断。如果三个点的斜率不同,则它们不共线。
-
三点互不相同:三个点的坐标不能完全相同。
解题思路
-
计算斜率:
- 对于点
A(x1, y1)
和点B(x2, y2)
,斜率公式为(y2 - y1) / (x2 - x1)
。 - 为了避免除零错误,可以使用乘法来比较斜率:
(y2 - y1) * (x3 - x1)
和(y3 - y1) * (x2 - x1)
。如果这两个值不相等,则三点不共线。
- 对于点
-
检查点是否相同:
- 直接比较三个点的坐标,确保它们互不相同。
算法步骤
- 检查三个点是否互不相同。
- 计算并比较斜率,判断三点是否共线。
最终代码:
#include <iostream>
#include <vector>
using namespace std;bool solution(vector<vector<int>>& points) {// 获取三个点的坐标int x1 = points[0][0], y1 = points[0][1];int x2 = points[1][0], y2 = points[1][1];int x3 = points[2][0], y3 = points[2][1];// 检查三个点是否互不相同if (x1 == x2 && y1 == y2) return false;if (x1 == x3 && y1 == y3) return false;if (x2 == x3 && y2 == y3) return false;// 计算并比较斜率// 使用乘法来避免除零错误// 如果 (y2 - y1) * (x3 - x1) 不等于 (y3 - y1) * (x2 - x1),则三点不共线if ((y2 - y1) * (x3 - x1) != (y3 - y1) * (x2 - x1)) {return true;}return false;
}int main() {vector<vector<int>> v1 = {{1, 1}, {2, 3}, {3, 2}};vector<vector<int>> v2 = {{1, 1}, {2, 2}, {3, 3}};vector<vector<int>> v3 = {{0, 0}, {1, 1}, {1, 0}};cout << (solution(v1) == true) << endl;cout << (solution(v2) == false) << endl;cout << (solution(v3) == true) << endl;return 0;
}
运行结果:
三、字符串解码问题
问题描述
小R正在处理一个包含小写字母的字符串解码问题。给定一个长度为N
的字符串S
,其中包含小写英文字母。字符串的解码规则如下:
- 字符
'x'
应解码为'y'
,字符'y'
应解码为'x'
。 - 字符
'a'
应解码为'b'
,字符'b'
应解码为'a'
。 - 所有其他字符保持不变。
你的任务是返回解码后的字符串。
测试样例
样例1:
输入:
N = 5, S = "xaytq"
输出:'ybxtq'
样例2:
输入:
N = 6, S = "abcxyz"
输出:'bacyxz'
样例3:
输入:
N = 3, S = "zzz"
输出:'zzz'
解题思路:
问题理解
我们需要根据给定的规则对字符串进行解码。具体规则如下:
- 字符
'x'
应解码为'y'
,字符'y'
应解码为'x'
。 - 字符
'a'
应解码为'b'
,字符'b'
应解码为'a'
。 - 所有其他字符保持不变。
数据结构选择
由于我们只需要对字符串中的每个字符进行简单的替换操作,因此不需要复杂的数据结构。我们可以直接使用字符串和字符数组来处理。
算法步骤
- 遍历字符串:我们需要遍历字符串中的每一个字符。
- 替换字符:根据字符的不同,进行相应的替换操作。
- 构建结果字符串:将替换后的字符逐个添加到结果字符串中。
具体步骤
- 创建一个空的结果字符串。
- 遍历输入字符串的每一个字符:
- 如果字符是
'x'
,将其替换为'y'
。 - 如果字符是
'y'
,将其替换为'x'
。 - 如果字符是
'a'
,将其替换为'b'
。 - 如果字符是
'b'
,将其替换为'a'
。 - 其他字符保持不变。
- 如果字符是
- 将替换后的字符添加到结果字符串中。
- 返回结果字符串。
最终代码:
#include <iostream>
#include <string>std::string solution(int N, const std::string& S) {// 创建一个空的结果字符串std::string result = "";// 遍历输入字符串的每一个字符for (char c : S) {// 根据字符的不同,进行相应的替换操作if (c == 'x') {result += 'y';} else if (c == 'y') {result += 'x';} else if (c == 'a') {result += 'b';} else if (c == 'b') {result += 'a';} else {// 其他字符保持不变result += c;}}// 返回结果字符串return result;
}int main() {std::cout << (solution(5, "xaytq") == "ybxtq") << std::endl;std::cout << (solution(6, "abcxyz") == "bacyxz") << std::endl;std::cout << (solution(3, "zzz") == "zzz") << std::endl;
}
运行结果:
四、小F的矩阵值调整
问题描述
小F得到了一个矩阵。如果矩阵中某一个格子的值是偶数,则该值变为它的三倍;如果是奇数,则保持不变。小F想知道调整后的矩阵是什么样子的。
测试样例
样例1:
输入:
a = [[1, 2, 3], [4, 5, 6]]
输出:[[1, 6, 3], [12, 5, 18]]
样例2:
输入:
a = [[7, 8, 9], [10, 11, 12]]
输出:[[7, 24, 9], [30, 11, 36]]
样例3:
输入:
a = [[2, 4], [6, 8]]
输出:[[6, 12], [18, 24]]
解题思路:
问题理解
你需要处理一个矩阵,矩阵中的每个元素如果是偶数,则将其值变为原来的三倍;如果是奇数,则保持不变。最终返回调整后的矩阵。
数据结构选择
- 输入是一个二维的整数矩阵,可以使用
vector<vector<int>>
来表示。 - 输出也是一个二维的整数矩阵,同样使用
vector<vector<int>>
来表示。
算法步骤
- 遍历矩阵:使用嵌套循环遍历矩阵中的每一个元素。
- 判断奇偶性:对于每一个元素,判断其是否为偶数。
- 如果是偶数,将其值变为原来的三倍。
- 如果是奇数,保持不变。
- 返回结果:遍历完成后,返回调整后的矩阵。
最终代码:
#include <vector>
#include <iostream>
using namespace std;vector<vector<int>> solution(vector<vector<int>> a) {// 遍历矩阵中的每一个元素for (int i = 0; i < a.size(); ++i) {for (int j = 0; j < a[i].size(); ++j) {// 判断当前元素是否为偶数if (a[i][j] % 2 == 0) {// 如果是偶数,将其值变为原来的三倍a[i][j] *= 3;}// 如果是奇数,保持不变(不需要额外操作)}}// 返回调整后的矩阵return a;
}int main() {cout << (solution({{1, 2, 3}, {4, 5, 6}}) == vector<vector<int>>{{1, 6, 3}, {12, 5, 18}}) << endl;cout << (solution({{7, 8, 9}, {10, 11, 12}}) == vector<vector<int>>{{7, 24, 9}, {30, 11, 36}}) << endl;cout << (solution({{2, 4}, {6, 8}}) == vector<vector<int>>{{6, 12}, {18, 24}}) << endl;return 0;
}
运行结果:
五、数字字符串中圆圈的数量计算
问题描述
小I拿到了一串数字字符,她想知道这串数字中一共有多少个圆圈。具体规则如下:
- 数字0、6、9各含有一个圆圈。
- 数字8含有两个圆圈。
- 其他数字不含有任何圆圈。
测试样例
样例1:
输入:
s = "1234567890"
输出:5
样例2:
输入:
s = "8690"
输出:5
样例3:
输入:
s = "1111"
输出:0
解题思路:
问题理解
你需要计算一个字符串中所有数字字符的圆圈总数。每个数字字符的圆圈数量如下:
- 数字
0
、6
、9
各含有一个圆圈。 - 数字
8
含有两个圆圈。 - 其他数字不含有任何圆圈。
数据结构选择
由于我们只需要遍历字符串中的每个字符并计算其对应的圆圈数量,因此不需要复杂的数据结构。我们可以使用一个简单的数组或映射来存储每个数字字符对应的圆圈数量。
算法步骤
- 初始化一个数组或映射,存储每个数字字符对应的圆圈数量。
- 遍历字符串中的每个字符,根据字符查找对应的圆圈数量并累加。
- 返回累加的结果。
具体步骤
- 创建一个数组
circleCount
,其中circleCount[i]
表示数字i
的圆圈数量。 - 遍历输入字符串
s
,对于每个字符c
,将其转换为对应的数字digit
,然后累加circleCount[digit]
到总数中。 - 返回累加的总数。
最终代码:
#include <iostream>
#include <string>int solution(const std::string& s) {// 初始化圆圈数量数组int circleCount[10] = {1, 0, 0, 0, 0, 0, 1, 0, 2, 1}; // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9// 初始化圆圈总数int totalCircles = 0;// 遍历字符串并累加圆圈数量for (char c : s) {int digit = c - '0'; // 将字符转换为对应的数字totalCircles += circleCount[digit]; // 累加圆圈数量}// 返回累加的结果return totalCircles;
}int main() {std::cout << (solution("1234567890") == 5) << std::endl;std::cout << (solution("8690") == 5) << std::endl;std::cout << (solution("1111") == 0) << std::endl;
}
运行结果:
六、小Q的非素数和排列问题
问题描述
小C对排列很感兴趣,她想知道有多少个长度为n的排列满足任意两个相邻元素之和都不是素数。排列定义为一个长度为n的数组,其中包含从1到n的所有整数,每个数字恰好出现一次。
测试样例
样例1:
输入:
n = 5
输出:4
样例2:
输入:
n = 3
输出:0
样例3:
输入:
n = 6
输出:24
解题思路
问题理解
我们需要找到长度为 n
的排列,使得任意两个相邻元素之和都不是素数。排列是一个包含从 1
到 n
的所有整数的数组,每个数字恰好出现一次。
数据结构选择
由于我们需要生成和检查排列,可以使用递归或迭代的方式来生成所有可能的排列,并检查每个排列是否满足条件。
算法步骤
- 生成排列:可以使用递归或迭代的方式生成所有可能的排列。
- 检查相邻元素之和:对于每个生成的排列,检查相邻元素之和是否为素数。
- 统计满足条件的排列:如果一个排列满足条件,则计数加一。
关键点
- 素数判断:需要一个函数来判断一个数是否为素数。
- 排列生成:可以使用递归或迭代的方式生成所有排列。
最终代码:
#include <iostream>
#include <vector>
#include <cmath>// 判断一个数是否为素数
bool is_prime(int num) {if (num <= 1) return false;if (num == 2) return true;if (num % 2 == 0) return false;for (int i = 3; i <= std::sqrt(num); i += 2) {if (num % i == 0) return false;}return true;
}// 递归生成排列并检查
void generate_permutations(int n, std::vector<int>& current_permutation, std::vector<bool>& used, int& count) {if (current_permutation.size() == n) {// 检查当前排列是否满足条件bool valid = true;for (int i = 0; i < n - 1; ++i) {if (is_prime(current_permutation[i] + current_permutation[i + 1])) {valid = false;break;}}if (valid) {count++;}return;}for (int i = 1; i <= n; ++i) {if (!used[i]) {// 剪枝:如果当前排列的最后一个元素与i的和是素数,则跳过if (!current_permutation.empty() && is_prime(current_permutation.back() + i)) {continue;}current_permutation.push_back(i);used[i] = true;generate_permutations(n, current_permutation, used, count);current_permutation.pop_back();used[i] = false;}}
}int solution(int n) {std::vector<bool> used(n + 1, false);std::vector<int> current_permutation;int count = 0;generate_permutations(n, current_permutation, used, count);return count;
}int main() {std::cout << (solution(5) == 4) << std::endl;std::cout << (solution(3) == 0) << std::endl;std::cout << (solution(6) == 24) << std::endl;
}