算法刷题小技巧【持续补充~】

简介: 算法刷题小技巧【持续补充~】

前言

欢迎提供新技巧,可在评论区留言~

使用scanf格式化读取数据

eg:

scanf("%d.%d.%d %d.%d.%d",&a,&b,&c,&d,&e,&f);
//可以读取数据格式为1.2.4 2.14.15

输入字符串 getline

使用getline函数:

cin.getline()也是常用的读取整行string的方式。

getline()操作的对象是string,cin.getline()操作的对象的char数组

cin.getline()函数读取至新行结尾或直到达到最大限制的整行文本。函数定义如下:

// (buffer, stream_size, delimiter)
istream& getline(char*, int size, char='\n')

// The delimiter character is considered as '\n'
istream& getline(char*, int size)

  1. 提取字符直到定界符。
  2. 将字符存储在缓冲区中。
  3. 提取的最大字符数为size-1。
cin.getline() 使用举例
#include <iostream> 
using namespace std; 
int main() 
{ 
    char str[20]; 
    cin.getline(str, 20); 
    cout << str; 
    return 0; 
}

两种getline函数
有两种getline函数:
库函数 string 和 iostream 均有getline函数

#include<string> // 全局的函数
istream& getline (istream& is, string& str, char delim);
istream& getline (istream& is, string& str);

#include <iostream> // 成员函数
istream& getline (char* s, streamsize n);
istream& getline (char* s, streamsize n, char delim);

注意iostream的getline是将读取的字符串存储在char数组中而不可以将该参数声明为string类型,
因为C++编译器无法执行此默认转换。

getline使用举例
#include <iostream>
#include <string>
using namespace std;
int main() {
  string s;
  getline(cin, s);
  cout << s;  
  system("pause");
  return 0;
}   

输入多行字符串(行数未知)

string str;
vector<string> v;
while (getline(cin, str)) //读取输入的一行数据
{
  if (str.size() == 0) break; //如果读取的是空,则读取结束
  v.push_back(str);
}


截断字符串

substr:返回一个从指定位置开始的指定长度的子字符串

stringvar.substr(start, [length])
/*
参数
stringvar   必选项。要提取子字符串的字符串文字或 String 对象。
start       必选项。所需的子字符串的起始位置。字符串中的第一个字符的索引为 0。
length      可选项。在返回的子字符串中应包括的字符个数。

说明
如果 length 为 0 或负数,将返回一个空字符串。如果没有指定该参数,则子字符串将延续到 stringvar 的最后。
*/

字符串转浮点数 stof函数

使用方法和stoi函数一样

stof判断"5.2abc"这类字符串时视"5.2"为合法,"abc"不合法,但实际上5.2abc不合法

举例:

PAT甲级真题1108 求平均值

基本任务非常简单:给定 N 个实数,请你计算它们的平均值。

但是令事情变得复杂的是,某些输入数字可能不合法。

合法输入数字指 [−1000,1000] 范围内的精确到不超过 2 个小数位的实数。

在计算平均值时,不得将这些非法数字计算在内。

输入格式

第一行包含整数 N。

第二行包含 N 个输入数字,数字之间用空格隔开。

输出格式

按照输入的顺序,对于每个输入的非法数字,在一行中输出 ERROR: X is not a legal number,其中 X 是非法输入。

最后一行,输出 The average of K numbers is Y,其中 K 是合法输入的数量,Y 是它们的平均值,注意保留两位小数。

如果平均值无法计算,则将 Y 替换为 Undefined。

如果 K 仅为 1,则输出 The average of 1 number is Y。

数据范围

1≤N≤1000

输入样例1:
7
5 -3.2 aaa 9999 2.3.4 7.123 2.35
输出样例1:
ERROR: aaa is not a legal number
ERROR: 9999 is not a legal number
ERROR: 2.3.4 is not a legal number
ERROR: 7.123 is not a legal number
The average of 3 numbers is 1.38
输入样例2:
2
aaa -9999
输出样例2:
ERROR: aaa is not a legal number
ERROR: -9999 is not a legal number
The average of 0 numbers is Undefined
题解
//@魔法学徒:https://www.acwing.com/user/myspace/index/162238/
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int cnt = 0;    // 合法数字个数
    double sum = 0; // 合法数字总和

    while (n -- )
    {
        string num;
        cin >> num;
        double x;

        bool success = true;
        /*
        不加try catch报错terminate called after throwing an instance of 'std::invalid_argument' 
        what():  stof(若传入不可转化为浮点型的字符串)会抛出异常
        */
        try
        {
            size_t idx = sizeof(num); // size type 用来记录大小的数据类型
            x = stof(num, &idx);      // 字符串转换为float型
            // stof判断"5.2abc"这类字符串时视"5.2"为合法,"abc"不合法,但实际上5.2abc不合法
            if (idx < num.size()) success = false; // 经stof处理后变短的字符串不合法
        }
        catch(...)                    // 捕捉所有类型的异常 
        {
            success = false;          // 所有不合法的输入数字都设为error
        }

        if (x < -1000 || x > 1000) success = false;
        int k = num.find('.');
        if (k != -1 && num.size() - k > 3) success = false;// 不超过2个小数位(最后一位是num.size()-1)

        if (success) cnt ++, sum += x;
        else printf("ERROR: %s is not a legal number\n", num.c_str());
    }

    if (cnt > 1) printf("The average of %d numbers is %.2lf\n", cnt, sum / cnt);
    else if (cnt == 1) printf("The average of 1 number is %.2lf\n", sum);
    else puts("The average of 0 numbers is Undefined");

    return 0;
}

对二维数组去重

    std::vector<std::vector<int>> removeDuplicates(const std::vector<std::vector<int>>& arr) {
        std::vector<std::vector<int>> sortedArr = arr;

        // 对二维数组排序
        std::sort(sortedArr.begin(), sortedArr.end());

        // 去除重复项
        auto last = std::unique(sortedArr.begin(), sortedArr.end());
        sortedArr.erase(last, sortedArr.end());

        return sortedArr;
    }

在上述代码中,std::unique 函数用于去除连续的重复项,该函数位于 <algorithm> 头文件中。函数的原型如下:

template<class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last);

其中,first 和 last 是表示要处理的元素范围的迭代器,ForwardIt 是一个泛型类型。std::unique 函数会返回一个指向最后一个不重复元素之后位置的迭代器。这意味着,从 first 到 last 的范围内的所有连续重复元素都被移到了范围的末尾,并且返回的迭代器指向了新范围的终点。

在代码中,我们使用 std::unique 函数将数组 sortedArr 中的重复项移到了末尾,并将返回的迭代器保存在 last 变量中。然后,我们使用 erase 函数将重复项从数组中删除,其原型如下:

template<class Container, class Iterator>
Iterator erase(Container& cont, Iterator pos);

其中,cont 是容器,pos 是指向要删除元素位置的迭代器。erase 函数会从容器中删除指定位置的元素,并返回一个指向被删除元素之后位置的迭代器。

在我们的代码中,sortedArr 是一个二维向量,我们使用 erase 函数将 last 到 sortedArr.end() 范围内的元素从 sortedArr 中删除,即删除了末尾的重复项。

通过上述操作,我们使用 std::unique 函数和 erase 函数成功去除了二维数组中的连续重复项。

相关文章
|
7月前
|
机器学习/深度学习 存储 算法
【算法沉淀】刷题笔记:并查集 带权并查集+实战讲解
【算法沉淀】刷题笔记:并查集 带权并查集+实战讲解
|
7月前
|
自然语言处理 算法
算法刷题(二十三):Bigram 分词
算法刷题(二十三):Bigram 分词
70 0
|
6月前
|
存储 算法 C语言
【数据结构与算法 刷题系列】合并两个有序链表
【数据结构与算法 刷题系列】合并两个有序链表
|
2月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
21 0
|
4月前
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
|
4月前
|
算法 Python
【Leetcode刷题Python】改进的算法,高效求一个数的因子
一个高效的Python函数用于找出一个整数的所有因子,通过仅遍历到该数平方根的范围来优化性能。
47 0
|
6月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
6月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
6月前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
6月前
|
算法
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)
【数据结构与算法 刷题系列】判断链表是否有环(图文详解)