ARST打卡第202周[202/521]

Linmin.Shan included in ARST

2023-03-19 2842 words 6 minutes

Contents

Algorithm

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

思路: 这个题目一看就是找规律:

无限次操作，所以b只分奇数偶数，a看其无限次累加能获得的所有个位数的质数
分为奇数位置的一组数字，和偶数位置的一组数字
如果b是偶数，那么只有奇数位置能累加到a值
- 所以偶数位置直接循环移动位置成最小值即可
- 奇数位置累加到对应最小值
如果b为奇数，那么奇数位列和偶数位列各自得到一组最小值，然后更小的作为前导

所以直接枚举位置操作，看看题解

发现题解有很多的优化点:

关于轮转循环终止，直接用s拼接串用vis[i]下标来确定终止循环
关于累加a的次数可以限定到10次即可(因为10次后又回归到了个位数原点)
轮转最大公约数(gcd)优化有个数学定理，直观上也能感受到
然后就是累加过程中,因为都是一起追加，是只要确定头部最小即可

 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


class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        int n = s.size();
        string res = s;
        s = s + s;
        int g = gcd(b, n);
        
        auto add = [&](string& t, int start) {
            int minVal = 10, times = 0;
            for (int i = 0; i < 10; i++) {
                int added = ((t[start] - '0') + i * a) % 10;
                if (added < minVal) {
                    minVal = added;
                    times = i;
                }
            }
            for (int i = start; i < n; i += 2) {
                t[i] = '0' + ((t[i] - '0') + times * a) % 10;
            }
        };

        for (int i = 0; i < n; i += g) {
            string t = s.substr(i, n);
            add(t, 1);
            if (b % 2) {
                add(t, 0);
            }
            res = min(res, t);
        }
        return res;
    }
};

Review

拒绝的力量

勇敢地说"不"有如下好处:

让你成为一个自尊自爱的人，不会什么事情都答应别人，能够建立合理的边界感
能让你更加专注于你自己想要做的事情，而不是被外界的请求，诱惑给干扰
筛选掉一些想要摆弄你的人际关系，而留下那些真正尊重你想法的人际关系

Tips

如何将现有 git 仓库中的子目录分离为独立仓库并保留其提交历史

Share_vscode-cpp IntelliSense解析开发包到系统路径而非指定的项目路径原因探索以及解决方案

背景

自己学习一个项目，项目里有改造过的levelDB包，但是vscode-cpp插件解析代码的时候，一直把代码解析到了/usr/include下面，而非"${workspaceFolder}/third-party/leveldb/src/include"路径

c_cpp_properties.json 文件配置如下。按道理来说会通过"${workspaceFolder}/**" 这个配置递归到所有的子目录，但是为啥不行呢

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


{
    "configurations": [
        {
            "name": "Linux",
            "includePath": [
                "${workspaceFolder}/**",
            ],
            "defines": [],
            "compilerPath": "/usr/bin/gcc",
            "cStandard": "c11",
            "cppStandard": "c++14",
            "intelliSenseMode": "linux-gcc-x64"
        }
    ],
    "version": 4
}

原因探索

通过google内容无果后，改用ChatGPT先学习相关知识点

IntelliSense 链接本地leveldb目录失败，一直链接系统leveldb

如果 IntelliSense 链接本地 leveldb 目录失败，而一直链接到了系统 leveldb，可能有以下几个原因：

检查头文件路径是否正确在 c_cpp_properties.json 文件的 “includePath” 中，确保添加了本地 leveldb 头文件的路径，并且路径与本地 leveldb 头文件的实际路径相符。如果路径不正确，则 IntelliSense 将无法找到本地 leveldb 头文件并使用系统头文件。

检查 leveldb 的命名空间是否正确在 C++ 代码中，确保使用了正确的 leveldb 命名空间。如果命名空间不正确，则编译器将无法找到正确的 leveldb 头文件并使用系统头文件。在 leveldb 头文件中，命名空间应该是 leveldb，例如：

1

#include "leveldb/db.h"

检查 leveldb 库是否链接正确如果您的项目需要链接 leveldb 库，您需要在 tasks.json 文件中添加链接 leveldb 库的任务，并确保编译器可以找到库文件。

检查 C_Cpp.intelliSenseEngine 设置在 VS Code 中，如果您使用的是 Tag Parser 引擎，则 IntelliSense 将无法处理 leveldb 头文件。您需要将 C_Cpp.intelliSenseEngine 设置为 Default 或 IncludeCompletion，以启用 IntelliSense 处理 leveldb 头文件。

希望这些解决方案可以帮助您解决问题。

IntelliSense 查找头文件顺序

IntelliSense 在查找头文件时通常按照以下顺序进行查找：

查找项目内的头文件：首先，IntelliSense 会查找项目内所有包含路径下的头文件，包括在 C/C++ 配置文件 c_cpp_properties.json 中配置的路径，以及通过 #include 包含的头文件。
查找系统头文件：如果在项目内找不到所需的头文件，IntelliSense 会继续查找系统的标准头文件路径，通常是 /usr/include 或 /usr/local/include。
查找其他路径：如果在项目内和系统路径中都找不到所需的头文件，IntelliSense 可能会查找其他路径，例如通过 -I 选项指定的路径。

需要注意的是，如果多个头文件有相同的名称，IntelliSense 只会使用查找顺序中第一个找到的头文件。如果需要使用某个特定的头文件，可以使用完整路径或相对路径包含该头文件。

另外，如果您在代码中使用了非标准的头文件，例如第三方库的头文件，建议在 c_cpp_properties.json 中将这些头文件路径添加到 “includePath” 中，以便 IntelliSense 正确地查找和处理这些头文件。

IntelliSense 引擎要使用的递归路径是否有限制

在 IntelliSense 中，引擎使用递归路径来查找头文件和解析代码。对于大多数情况，递归路径的深度没有限制，也就是说，引擎可以一直往下递归查找，直到找到需要的头文件或达到系统的递归深度限制。

然而，当递归路径太深时，可能会导致 IntelliSense 的性能下降，并可能导致其无法正确地解析代码。因此，为了避免这种情况，建议在配置 C_Cpp.default.includePath 和 C_Cpp.default.forcedInclude 时，尽量将递归路径限制在合理的范围内，只包括必要的路径，避免不必要的递归和性能下降。

另外，对于某些引擎（如 Tag Parser 引擎），由于其实现方式的限制，可能会导致递归路径深度限制更加严格。在这种情况下，建议使用默认引擎或 IncludeCompletion 引擎，以获得更好的性能和代码解析能力。

重新尝试

看到ChatGPT回答的问题之后，检查确认了自己所有的配置都没有问题，但是自己却还是遇到这个问题，所以怀疑是缓存空间不够，导致项目头文件递归受限。

因此自己做了指定头文件的尝试:

添加"third-party/leveldb/src/include"到c_cpp_properties.json 文件中, 然后居然就成功了，~~所以之前添加的"third-party/leveldb/src/include/**"是错的，正好忽略掉了include目录(**往下递归)~~

继续尝试，

"${workspaceFolder}/third-party/leveldb/src/include"也可以
"${workspaceFolder}/third-party/**" 就失败了，导致链接到了/usr/include/leveldb/slice.h
"${workspaceFolder}/third-party/leveldb/**" 也失败了
"${workspaceFolder}/third-party/leveldb/src/**" 也失败了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


{
    "configurations": [
        {
            "name": "Linux",
            "includePath": [
                "${workspaceFolder}/**",
                "third-party/leveldb/src/include"
            ],
            "defines": [],
            "compilerPath": "/usr/bin/gcc",
            "cStandard": "c11",
            "cppStandard": "c++14",
            "intelliSenseMode": "linux-gcc-x64"
        }
    ],
    "version": 4
}

问题最终原因总结

因为确实**会进行递归操作，于是猜测是level的包递归路径太深时，可能会导致 IntelliSense 的性能下降或者缓存不足，于是导致其无法正确地解析代码，导致对于 includePath 支持的内容有些折中，所以最终导致出现较深的本地目录只有在精确命名时才能找到，否则认为本地没有，于是去找系统目录，发现系统目录有，于是显示系统目录的leveldb

关于项目内其他路径较深头文件为啥解析没出问题

对于其他的一些同样路径较深的头文件，可能是因为本地和系统目录都没找到，最后通过找-I指定的路径找到了本地项目头文件，所以看起来像是提前找了本地项目一样

此类问题解决方案

对于较深的第三方包，通过精准指定目录，去防止IntelliSense跳转到系统头文件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


{
    "configurations": [
        {
            "name": "Linux",
            "includePath": [
                "${workspaceFolder}/**",
                "${workspaceFolder}/third-party/leveldb/src/include"
            ],
            "defines": [],
            "compilerPath": "/usr/bin/gcc",
            "cStandard": "c11",
            "cppStandard": "c++14",
            "intelliSenseMode": "linux-gcc-x64"
        }
    ],
    "version": 4
}