前言

虽然平时自己也都是一天一题，但是感觉做完就忘，所以准备留下一些东西，以后可以方便复习和整理。

为了保证质量，将不会做简单题，如果当天是简单题，会另找一道中等或困难的题作为代替。

2023-3-19

1625. 执行操作后字典序最小的字符串

题解

基础

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    string findLexSmallestString(string s, int a, int b)
    {
        int strSize = s.size();

        unordered_set<string> uSet;
        uSet.insert(s);
        queue<string> stringQueue;
        stringQueue.push(s);

        string minString = s;

        string str;
        string tempStr;
        int tempInt;
        while(!stringQueue.empty())
        {
            str = stringQueue.front();

            tempStr = str.substr(b, strSize-b) + str.substr(0, b);
            if(!uSet.count(tempStr))
            {
                uSet.insert(tempStr);
                stringQueue.push(tempStr);
                minString = min(minString, tempStr);
            }

            for(int i = 1; i < strSize; i++)
            {
                if(i & 1)
                {
                    str[i] = str[i] + a;
                    if(str[i] > '9')
                        str[i] -= 10;
                }
            }

            if(!uSet.count(str))
            {
                uSet.insert(str);
                stringQueue.push(str);
                minString = min(minString, str);
            }

            // cout<<tempStr<<endl;

            stringQueue.pop();
        }

        return minString; 
    }
};

执行用时：188 ms, 在所有 C++ 提交中击败了30.00%的用户
内存消耗：74.3 MB, 在所有 C++ 提交中击败了28.00%的用户

把广搜改成了深搜（容器从 queue 变成了 stack）。

执行用时：180 ms, 在所有 C++ 提交中击败了30.00%的用户
内存消耗：74.5 MB, 在所有 C++ 提交中击败了26.00%的用户

速度变快，但是内存消耗变大了。

进阶

感觉优化方向更多的是通过分奇偶讨论，就不在此赘述了。

探索

queue 和 stack 的底层区别

底层容器的选择会影响 queue 和 stack 的性能和空间占用。queue 默认使用 deque 作为底层容器，而 stack 默认使用 deque 或 vector 作为底层容器。使用不同的底层容器会影响到 queue 和 stack 的内存占用和执行时间。

deque 是一个双端队列，支持在两端高效地插入和删除元素。由于它的内存分配方式比较特殊，可以避免元素的频繁拷贝，因此在插入和删除元素时比较快，但是会占用一定的额外空间。如果使用 deque 作为底层容器，queue 和 stack 的性能表现通常比使用 vector 好，但是会占用更多的内存。

vector 是一个动态数组，支持在末尾高效地插入和删除元素，但在头部插入和删除元素比较慢。由于它的内存分配方式比较简单，只需要一块连续的内存区域，因此它的空间占用比较紧凑。如果使用 vector 作为底层容器，queue 和 stack 的性能表现可能会比 deque 差一些，但是会占用更少的内存。

说实话这个 stack 底层在 vector 和 deque 中的切换，就像 mysql 底层在 vector 和 map 间的切换。

string 转 int

想把 string 强转成 int，结果报错了。

reinterpret_cast from ‘std::string’ (aka ‘basic_string‘) to ‘int’ is not allowed

去查了一下 string 的源码，不过就是都是用模板写的，阅读起来太麻烦了，下次再拜读吧，看了一下别人实现的 string，感觉并不是不能再加个 operator int。

问了一下 chatGPT，给的答案还是很中肯的。

使用reinterpret_cast将std::string转换为int是不安全的，因为它涉及到类型的不同。std::string是一个类类型，而int是一个基本数据类型。reinterpret_cast运算符可以强制转换指针或引用类型到任何其他类型的指针或引用，但是如果指针或引用指向的内存没有正确对齐或者指向的数据类型与目标类型不匹配，那么可能会导致未定义行为。

对于std::string类型，它的实现方式可能因编译器和库而异，因此不能保证在所有情况下使用reinterpret_cast将std::string转换为int是安全的。另外，std::string类型可能包含指向堆内存的指针，这意味着如果你尝试将std::string对象强制转换为int，那么可能会得到指针的值，而不是字符串表示的整数值。

相反，C++标准库提供了std::stoi函数来将字符串转换为整数类型，它是一种更安全和可靠的方法。使用std::stoi，你可以将字符串转换为整数值，并在转换失败时抛出异常，因此你可以轻松地处理转换错误的情况。

reinterpret_cast是C++中一种强制类型转换运算符，用于将一个指针或引用类型转换为另一种指针或引用类型，或将指针或引用类型转换为整数类型。它的实现原理取决于编译器和平台的具体实现，但通常会将指针或引用的值重新解释为其他类型的值，而不进行任何转换。

在将指针或引用转换为整数类型时，reinterpret_cast通常将指针或引用的值视为一个无符号整数，并将其强制转换为目标类型。这种转换可能会导致未定义行为，因为它依赖于指针或引用的值的内部表示方式。如果指针或引用指向的内存没有正确对齐或者指向的数据类型与目标类型不匹配，那么将会产生未定义行为。

总之，reinterpret_cast的实现原理是将指针或引用的值重新解释为其他类型的值，它的行为取决于指针或引用的值的内部表示方式，并且可能会导致未定义行为。因此，建议在使用reinterpret_cast时谨慎操作，并确保转换的类型之间存在充分的兼容性和正确性。

所以说 std::stoi 只是包装了转换算法，顺便问一下用了什么算法吧。

算法复杂度是 **O(n)**，当时它说用了高效的状态机算法，这让我想起了这个学期的课《编译原理》。

高效的状态机算法是指一种利用状态机的概念来处理输入序列的算法。状态机是一种计算模型，它包含一个有限状态集合和一组转移函数，可以对输入序列进行解析和处理。

在状态机算法中，输入序列被看作是状态机的输入，状态机根据当前的输入字符和当前状态，执行状态转移，直到达到某个终止状态为止。这种算法具有快速、高效、可扩展性强等特点，通常可以用于解析和处理大规模的文本、数据流、网络数据等。

对于字符串转换为整数的问题，状态机算法可以将字符串中的每个字符看作状态机的输入字符，并根据不同的状态来处理不同的输入字符。例如，当输入字符是数字时，状态机将其解释为整数位，并根据当前状态来计算结果。当输入字符是非数字字符或字符串结束符时，状态机停止运行，并返回最终结果。

在实现std::stoi函数时，使用状态机算法可以避免遍历字符串多次，从而提高了算法的效率。状态机算法的复杂度通常为O(n)，其中n是输入序列的长度，因此具有很好的性能和可扩展性。

其实我在学习状态机的时候也一直有个疑问，就是。

状态机的实现难道不就是switch吗，我通过for遍历字符串，对每一位进行switch操作，不也能达到一样的效果吗

说实话，一说状态机我就想到了文法和语法（目前也只学到这），目前据它的回答来看，状态机主要的优点在于可以模块化处理，方便管理。

实际上，状态机的实现并不一定是用 switch 语句来完成，虽然 switch 语句可以实现状态转移，但是 switch 语句的嵌套层数会随着状态数的增加而增加，从而导致代码难以阅读和维护。

状态机的实现通常需要利用指针、函数指针、函数对象等技术，将状态和转移函数抽象出来，从而实现状态转移和处理。这样可以将状态机的代码模块化，易于理解和维护。

在字符串转换为整数的问题中，状态机算法的实现可以使用一个状态指针和一组转移函数来完成。状态指针指向当前状态，转移函数根据当前状态和输入字符的不同，执行相应的操作，并更新状态指针。这样可以将状态转移和操作分离开来，从而实现代码的模块化和复用。

使用 for 循环遍历字符串，对每一位进行 switch 操作，也可以实现字符串转换为整数的功能，但是这种实现方式会使代码变得复杂，难以阅读和维护。相比之下，使用状态机算法可以将代码模块化，易于理解和维护，从而提高代码的可读性和可维护性。

看了它给我写的代码，我大概能懂它什么意思了，不过具体的可以等之后上课再看看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int strToInt(string str) {
    int n = str.size();
    int sign = 1;
    int ans = 0;
    int i = 0;

    // 定义状态转移函数
    enum State { kStart, kSign, kNumber, kEnd };
    State state = kStart;
    auto get_state = [&](char c) {
        if (isspace(c)) return kStart;
        if (c == '+' || c == '-') return kSign;
        if (isdigit(c)) return kNumber;
        return kEnd;
    };

    // 定义状态转移过程
    while (i < n && state != kEnd) {
        char c = str[i];
        state = get_state(c);
        switch (state) {
            case kStart:
                break;
            case kSign:
                sign = (c == '-') ? -1 : 1;
                break;
            case kNumber:
                ans = ans * 10 + (c - '0');
                ans = (sign == 1) ? min(ans, INT_MAX) : min(ans, -(long long)INT_MIN);
                break;
            case kEnd:
                break;
        }
        ++i;
    }

    return ans * sign;
}

将临时对象绑定至非常量左值引用

例行报错，忘加 const 了，因为左值引用不能被改，没有 const 不安全，但是印象中还可以用 forawrd 和 move 实现（虽然我没用过），正好试试。

刚刚把 move 过来的右值保存到右值引用里了，还给它存数组里了，结果又报错了。

右值引用本身可以保存到数组中，但需要注意的是，保存的右值引用对象必须还存在于其声明周期中。因为右值引用实际上是一个对象的别名，如果被引用的对象在其声明周期结束后被销毁了，那么对于这个右值引用的访问就是未定义的行为。

正好问问右值引用的底层原理，为什么不能改数。

右值引用在底层硬件上的实现原理并不是通过向寄存器取数来实现的。在 C++ 中，引用的实现基于指针，引用被编译器翻译成指针，在内部使用时，编译器会把引用替换成指向所引用对象的指针。因此，右值引用也是被编译器实现成一个指向右值的指针。在底层硬件上，它和指针的实现方式是相同的。

在计算机体系结构中，寄存器是比内存更快的存储器件，但是寄存器数量有限，因此通常只有少量的变量会存储在寄存器中。对于大部分的变量和数据结构，它们通常存储在内存中。

在 C++ 中，右值引用是一种语法机制，用于表示可以移动的对象，但是在底层实现中，右值引用是指针的一种形式，是用于访问对象的地址。因此，它的实现方式与指针相同，不涉及到向寄存器取数的操作。

不过说实话仔细想想，不能改数不是底层上能不能做到的问题，而是这样不安全。