阶乘末尾零优化

发表于 2024-09-25 | 分类于 c语言 | 暂无评论

在计算 (b!) 的末尾有多少个连续的0时，可以通过模拟阶乘的乘法来计算整个大数阶乘，再统计结果中末尾的0的数量。然而，当 (b) 很大时，这种直接模拟阶乘的方法会导致运行时间和空间效率较低，容易超时。

实际上，计算一个数的阶乘末尾有多少个0并不需要真的计算出整个阶乘。阶乘末尾0的数量实际上取决于阶乘中因子5的数量（因为2的数量总是比5多）。因此，可以采用数学方法来计算。

优化方法

计算 (b!) 末尾0的数量的核心在于统计从1到(b)中，能够被5整除的数的个数，以及更高次方（如25, 125, …）的个数。具体的公式为：

一直计算到

优化后的代码

#include<iostream>
using namespace std;

int main() 
{
    int b;
    cin >> b;
    int count = 0;
    for (int i = 5; i <= b; i *= 5) 
    {
        count += b / i;
    }
    cout << count << "\n";
    return 0;
}

解释

i 从5开始，每次乘以5，直到 ( i > b ) 为止。
b / i 表示当前阶乘数范围内包含多少个可以被当前的5次方整除的数。
将每一步的结果累加即可得到 (b!) 中因子5的总数，这就是末尾0的数量。

这种方法的时间复杂度是 (O(\log b))，相比原算法效率极高，能轻松处理非常大的 (b) 值，从而避免超时问题。

int类型的变量size()方法返回值进行比较。

发表于 2024-09-25 | 分类于 c语言 | 暂无评论

从截图中，可以看到程序虽然被正确接受（Accepted），但编译时出现了一些警告。主要问题如下：

警告信息

警告内容显示在以下位置：

warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

原因

这些警告是因为在您的 for 循环中，使用了 int 类型的变量 i 与 std::string 的 size() 方法返回值进行比较。而 size() 方法的返回值是一个无符号整数类型 (std::string::size_type)，通常是 size_t，在很多系统中定义为 long unsigned int。因此，当您用 int 类型的 i 和无符号的 size_t 进行比较时，编译器会提示这种有符号与无符号类型的比较可能导致潜在的问题。

解决方案

您可以将循环变量 i 的类型从 int 改为 std::string::size_type 或者 size_t，以确保类型一致。例如：

for (std::string::size_type i = 0; i < s1.size(); ++i) {
    // Your code
}

或者：

for (size_t i = 0; i < s1.size(); ++i) {
    // Your code
}

总结

虽然这些警告不会影响程序的运行，但为了代码的健壮性和可维护性，建议按照上述方法修改代码，消除这些警告。

C++ 字典实现方法

发表于 2024-09-24 | 分类于 c语言 | 暂无评论

在C++中没有像Python那样的内置“字典”（即dict）这种直接的数据类型，但可以使用std::map或者std::unordered_map来实现类似字典的功能。这些容器位于C++标准库的<map>或<unordered_map>头文件中。

这两者都允许将“键-值对”进行存储和查找，像Python的字典一样，不过它们有一些区别：

std::map：

是一个有序的关联容器，底层实现通常为红黑树。
存储的键值对是有序的，按照键的顺序自动排序。
查找、插入、删除的时间复杂度为O(log n)。

例子：

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> myMap;

    myMap["apple"] = 1;
    myMap["banana"] = 2;

    std::cout << "apple: " << myMap["apple"] << std::endl;

    // 遍历
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

std::unordered_map：

是一个无序的关联容器，底层实现通常为哈希表。
键值对是无序的，插入顺序与存储顺序无关。
查找、插入、删除的平均时间复杂度为O(1)，但最坏情况下可能为O(n)。

例子：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> myUnorderedMap;

    myUnorderedMap["apple"] = 1;
    myUnorderedMap["banana"] = 2;

    std::cout << "apple: " << myUnorderedMap["apple"] << std::endl;

    // 遍历
    for (const auto& pair : myUnorderedMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

总结

C++中的std::map和std::unordered_map可以实现类似Python字典的功能。
std::map是有序的，而std::unordered_map是无序的。
使用哪种容器取决于你的使用场景：如果你需要按键有序存储，选择std::map；如果你不关心顺序，且希望更快的查找速度，选择std::unordered_map。

c语言和c++中关于字符串操作的函数

发表于 2024-09-21 | 分类于 c语言 | 暂无评论

在C语言中，常用的字符串操作函数包括以下几种：

strlen()：计算字符串的长度（不包括末尾的空字符）。
```
size_t strlen(const char *str);
```
strcpy()：将源字符串复制到目标字符串。
```
char *strcpy(char *dest, const char *src);
```
strcat()：将源字符串追加到目标字符串后。
```
char *strcat(char *dest, const char *src);
```
strcmp()：比较两个字符串，返回负数、0或正数，分别表示小于、等于或大于。
```
int strcmp(const char *str1, const char *str2);
```
strncpy()：从源字符串复制指定长度到目标字符串。
```
char *strncpy(char *dest, const char *src, size_t n);
```
strstr()：在目标字符串中查找子串的首次出现。
```
char *strstr(const char *haystack, const char *needle);
```

sprintf()：将格式化数据写入字符串。

int sprintf(char *str, const char *format, ...);

这些函数是C标准库中的常用函数，处理字符串复制、比较、拼接和搜索等操作。

在C++中，字符串操作主要依赖于std::string类，以下是常用的字符串操作函数：

length() 或 size()：返回字符串的长度。
```
size_t length() const;
```

substr()：从指定位置开始提取子串。

std::string substr(size_t pos = 0, size_t len = npos) const;

find()：查找子串在字符串中的首次出现位置。
```
size_t find(const std::string& str, size_t pos = 0) const;
```
append()：将一个字符串追加到当前字符串末尾。
```
std::string& append(const std::string& str);
```

insert()：在指定位置插入字符串。

std::string& insert(size_t pos, const std::string& str);

erase()：删除字符串中的一部分。

std::string& erase(size_t pos = 0, size_t len = npos);

replace()：用一个字符串替换部分内容。

std::string& replace(size_t pos, size_t len, const std::string& str);

compare()：比较两个字符串。

int compare(const std::string& str) const;

这些函数可以用于方便地操作和处理C++中的std::string对象。

cin和getline区别

发表于 2024-09-21 | 分类于 c语言 | 暂无评论

cin 和 getline 都是 C++ 中用于从标准输入读取数据的方式，但它们之间有一些关键的区别，主要在于它们处理输入的方式不同。下面详细说明它们的差异：

1. 读取方式

cin：逐个读取单个数据项（通常以空白字符作为分隔符）。比如，当你使用 cin >> s; 读取一个字符串时，它会跳过任何空格、换行符或制表符，只读取直到遇到下一个空白字符为止。
- 示例：
```
string s;
cin >> s;
// 输入 "hello world" 输出 s = "hello" (只读取第一个单词)
```
getline：读取一整行的输入，直到遇到换行符为止。它会将整行的内容，包括空格、制表符，作为输入的一部分。
- 示例：
```
string s;
getline(cin, s);
// 输入 "hello world" 输出 s = "hello world" (读取整个字符串)
```

2. 分隔符的处理

cin：使用空白字符（空格、换行符、制表符）作为分隔符。当它遇到这些字符时，读取就会结束，剩余的部分不会被读取。
getline：使用换行符 \n 作为分隔符。当它遇到换行符时，读取才会结束，它会读取空格和制表符，并且将它们视为字符串的一部分。

3. 空白字符的处理

cin：跳过空白字符。它只会读取第一个非空白字符开始的数据。
getline：会读取空白字符并将它们作为字符串的一部分，直到遇到换行符为止。

4. 处理换行符的区别

cin：读取数据后，剩下的换行符会留在输入缓冲区中，可能影响后续的输入。
- 例如，在 cin >> n; 之后，如果使用 getline，getline 会直接读取到那个留在缓冲区中的换行符 \n，导致行为异常。
getline：getline 会消耗输入缓冲区中的换行符，并读取整行数据。

示例代码解释 `cin` 和 `getline` 的区别：

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    string s;

    // 使用cin读取一个整数
    cin >> n;  // 读取一个整数，假设输入是5，缓冲区中会留下换行符

    // 使用getline读取字符串
    getline(cin, s);  // 由于cin >> n没有消耗掉换行符，getline会直接读取这个换行符，导致s是空字符串

    cout << "n: " << n << endl;
    cout << "s: " << s << endl;

    return 0;
}

输出：

输入：
5
hello world

输出：
n: 5
s:

解释：

当使用 cin >> n; 读取整数时，输入缓冲区中会残留一个换行符 \n。随后调用 getline(cin, s) 会读取到这个换行符，因此字符串 s 将是一个空字符串。

如何解决这个问题：

在使用 getline 之前，可以先使用 cin.ignore() 来清除输入缓冲区中的换行符。

cin >> n;
cin.ignore();  // 清除缓冲区中的换行符
getline(cin, s);

总结：

cin：适合读取单个数据项，跳过空白字符，不能读取带空格的字符串。
getline：适合读取一整行数据，包括空格和制表符，遇到换行符结束。

因此，根据不同的需求选择 cin 还是 getline。