首页 > 其他分享 >字节青训-判断数组是否单调、判断回旋镖的存在、字符串解码问题、小F的矩阵值调整、数字字符串中圆圈的数量计算 、小Q的非素数和排列问题

字节青训-判断数组是否单调、判断回旋镖的存在、字符串解码问题、小F的矩阵值调整、数字字符串中圆圈的数量计算 、小Q的非素数和排列问题

时间：2024-11-19 20:16:51浏览次数：3  
标签：字符 判断 nums int 样例 数组 字符串 青训

目录

一、判断数组是否单调

问题描述

测试样例

解题思路：

解题思路

数据结构选择

算法步骤

 最终代码：

运行结果：

​编辑 

 二、判断回旋镖的存在

问题描述

测试样例

解题思路： 

解题思路

算法步骤

最终代码：

运行结果：

​编辑 

三、字符串解码问题

问题描述

测试样例

 解题思路：

问题理解

数据结构选择

算法步骤

具体步骤

 最终代码：

运行结果：

​编辑 

四、小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

解题思路：

要判断一个数组是否为单调数组，我们需要检查数组是否满足以下两个条件之一：

  1. 单调递增：对于所有索引 i <= j，nums[i] <= nums[j]。
  2. 单调递减：对于所有索引 i <= j，nums[i] >= nums[j]。

解题思路

  1. 初始化标志：

    • 我们可以使用两个布尔变量 isIncreasing 和 isDecreasing 来分别表示数组是否单调递增和单调递减。
    • 初始时，将这两个变量都设置为 true。

  2. 遍历数组：

    • 从数组的第二个元素开始，逐个比较当前元素和前一个元素。
    • 如果当前元素小于前一个元素，则将 isIncreasing 设置为 false。
    • 如果当前元素大于前一个元素，则将 isDecreasing 设置为 false。

  3. 判断结果：

    • 遍历结束后，如果 isIncreasing 或 isDecreasing 中有一个为 true，则说明数组是单调的，返回 true。
    • 否则，返回 false。

数据结构选择

  • 使用布尔变量来记录数组的单调性。

算法步骤

  1. 初始化 isIncreasing 和 isDecreasing 为 true。
  2. 遍历数组，比较相邻元素。
  3. 根据比较结果更新 isIncreasing 和 isDecreasing。
  4. 返回 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;
        }
    }
    
    // 如果数组是单调递增或单调递减，返回 true
    return 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

解题思路： 

要判断三个点是否构成一个回旋镖，我们需要确保以下几点：

  1. 三点不共线：三个点不能在同一条直线上。可以通过计算斜率来判断。如果三个点的斜率不同，则它们不共线。

  2. 三点互不相同：三个点的坐标不能完全相同。

解题思路

  1. 计算斜率：

    • 对于点 A(x1, y1) 和点 B(x2, y2)，斜率公式为 (y2 - y1) / (x2 - x1)。
    • 为了避免除零错误，可以使用乘法来比较斜率：(y2 - y1) * (x3 - x1) 和 (y3 - y1) * (x2 - x1)。如果这两个值不相等，则三点不共线。

  2. 检查点是否相同：

    • 直接比较三个点的坐标，确保它们互不相同。

算法步骤

  1. 检查三个点是否互不相同。
  2. 计算并比较斜率，判断三点是否共线。

最终代码：

#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，其中包含小写英文字母。字符串的解码规则如下：

  1. 字符 'x' 应解码为 'y'，字符 'y' 应解码为 'x'。
  2. 字符 'a' 应解码为 'b'，字符 'b' 应解码为 'a'。
  3. 所有其他字符保持不变。

你的任务是返回解码后的字符串。

测试样例

样例1：

输入：N = 5, S = "xaytq"
输出：'ybxtq'

样例2：

输入：N = 6, S = "abcxyz"
输出：'bacyxz'

样例3：

输入：N = 3, S = "zzz"
输出：'zzz'

 解题思路：

问题理解

我们需要根据给定的规则对字符串进行解码。具体规则如下：

  1. 字符 'x' 应解码为 'y'，字符 'y' 应解码为 'x'。
  2. 字符 'a' 应解码为 'b'，字符 'b' 应解码为 'a'。
  3. 所有其他字符保持不变。

数据结构选择

由于我们只需要对字符串中的每个字符进行简单的替换操作，因此不需要复杂的数据结构。我们可以直接使用字符串和字符数组来处理。

算法步骤

  1. 遍历字符串：我们需要遍历字符串中的每一个字符。
  2. 替换字符：根据字符的不同，进行相应的替换操作。
  3. 构建结果字符串：将替换后的字符逐个添加到结果字符串中。

具体步骤

  1. 创建一个空的结果字符串。
  2. 遍历输入字符串的每一个字符：
    • 如果字符是 'x'，将其替换为 'y'。
    • 如果字符是 'y'，将其替换为 'x'。
    • 如果字符是 'a'，将其替换为 'b'。
    • 如果字符是 'b'，将其替换为 'a'。
    • 其他字符保持不变。
  3. 将替换后的字符添加到结果字符串中。
  4. 返回结果字符串。

 最终代码：

#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>> 来表示。

算法步骤

  1. 遍历矩阵：使用嵌套循环遍历矩阵中的每一个元素。
  2. 判断奇偶性：对于每一个元素，判断其是否为偶数。
    • 如果是偶数，将其值变为原来的三倍。
    • 如果是奇数，保持不变。
  3. 返回结果：遍历完成后，返回调整后的矩阵。

最终代码：

#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 含有两个圆圈。
  • 其他数字不含有任何圆圈。

数据结构选择

由于我们只需要遍历字符串中的每个字符并计算其对应的圆圈数量，因此不需要复杂的数据结构。我们可以使用一个简单的数组或映射来存储每个数字字符对应的圆圈数量。

算法步骤

  1. 初始化一个数组或映射，存储每个数字字符对应的圆圈数量。
  2. 遍历字符串中的每个字符，根据字符查找对应的圆圈数量并累加。
  3. 返回累加的结果。

具体步骤

  1. 创建一个数组 circleCount，其中 circleCount[i] 表示数字 i 的圆圈数量。
  2. 遍历输入字符串 s，对于每个字符 c，将其转换为对应的数字 digit，然后累加 circleCount[digit] 到总数中。
  3. 返回累加的总数。

最终代码：

#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 的所有整数的数组，每个数字恰好出现一次。

数据结构选择

由于我们需要生成和检查排列，可以使用递归或迭代的方式来生成所有可能的排列，并检查每个排列是否满足条件。

算法步骤

  1. 生成排列：可以使用递归或迭代的方式生成所有可能的排列。
  2. 检查相邻元素之和：对于每个生成的排列，检查相邻元素之和是否为素数。
  3. 统计满足条件的排列：如果一个排列满足条件，则计数加一。

关键点

  • 素数判断：需要一个函数来判断一个数是否为素数。
  • 排列生成：可以使用递归或迭代的方式生成所有排列。

最终代码：

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

运行结果：

标签：字符,判断,nums,int,样例,数组,字符串,青训
From： https://blog.csdn.net/m0_73302939/article/details/143894344

相关文章

  • 【入门】字符串的反码c++
    #include<bits/stdc++.h>usingnamespacestd;intmain(){ //一、分析问题 //已知：一个长度不超过80个字符的字符串。 //未知：字符串的反码。 //关系：如果这是一个小写字符，则它和字符a的距离与它的反码和字符z的距离相同；如果是一个大写字符，则它和字符A的距离与它......
  • 7-14 判断回文字符串
    输入一个字符串，判断该字符串是否为回文。回文就是字符串中心对称，从左向右读和从右向左读的内容是一样的。输入格式:输入在一行中给出一个不超过80个字符长度的、以回车结束的非空字符串。输出格式:输出在第1行中输出字符串。如果它是回文字符串，在第2行中输出Yes，否则输出No......
  • Windows注册表REG_SZ字符串值增加回车换行
    前言全局说明在新建文本时，默认里面是空的，但Windows支持，在注册表里添加Data键值，来增加。默认键类型是REG_SZ字符串单行文本，但是要回车换行正常情况下就不支持了经过两天的网上查找和GPTchat查询，总结了一下注册表，修改有风险！修改前，请备份注册表，修改有风险！修改前，请备份注册表......
  • 记录个Java/Groovy的小问题：空字符串调用split函数返回非空数组
    问题复现最近写了一个groovy替换程序增量流水线脚本(会Java也能看懂)，示意脚本如下：//获取文件列表方法deflistFiles(folder){defoutput=sh(script:"ls${folder}",returnStdout:true).trim()returnoutput.split('\n')asList}//调用以上方法获取lib目录下......
  • 【问chatgpt】一段 golang 代码中，把一个字符串池的类名写成了 arena， 这有什么典故吗?
    作者:张富春(ahfuzhang)，转载时请注明作者和引用链接，谢谢！cnblogs博客zhihuGithub公众号:一本正经的瞎扯在Go编程中，将一个字符串池类名命名为arena是有一定背景和意义的。这个命名通常源于以下几个方面的典故或技术理念：“Arena”的字面意义“Arena”在英文中是“......
  • NFLS 字符串题单笔记（未完结）
    POI2010Antisymmetry对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。manacher板子，写就完了#include<bits/stdc++.......
  • string，字符串使用指南
    string创建创建一个字符串或者字符串数组如下用cin输入，可以读一整串字符直到空格或换行才结束#include<iostream>usingnamespacestd;constintN=9;intmain(){ strings; stringstrs[N]; cin>>s; for(inti=0;i<N;i++) { cin>>strs[i];......
  • 【Python入门】探索Python字符串的奥秘：常用方法全解析
    ......
  • 代码随想录算法训练营第八天（LeetCode344.反转字符串；LeetCode541.反转字符串Ⅱ；卡码网54
    LeetCode344.反转字符串题目链接:反转字符串题目链接思路这道题目让我们进行字符串的反转，其实直接使用reverse相关的函数就可以解决问题。但是解决问题的时候，如果这道题目使用库函数就可以直接解决，就最好不要使用库函数；如果库函数只是题目中解法的一小步，那么就使用......
  • JavaScript 字符串的常用方法有哪些
    速览JavaScript字符串的常用方法包括charAt、charCodeAt、concat、indexOf、lastIndexOf、slice、substring、toLowerCase、toUpperCase、trim、replace、split、padStart、padEnd等。详答1.基本信息JavaScript中的字符串是一种原始数据类型，提供了丰富的操作方法来处......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99