Contents

ARST打卡第202周[202/521]

Algorithm

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

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

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

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

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

  1. 关于轮转循环终止,直接用s拼接串用vis[i]下标来确定终止循环
  2. 关于累加a的次数可以限定到10次即可(因为10次后又回归到了个位数原点)
  3. 轮转最大公约数(gcd)优化有个数学定理,直观上也能感受到
  4. 然后就是累加过程中,因为都是一起追加,是只要确定头部最小即可
 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 在查找头文件时通常按照以下顺序进行查找:

  1. 查找项目内的头文件:首先,IntelliSense 会查找项目内所有包含路径下的头文件,包括在 C/C++ 配置文件 c_cpp_properties.json 中配置的路径,以及通过 #include 包含的头文件。
  2. 查找系统头文件:如果在项目内找不到所需的头文件,IntelliSense 会继续查找系统的标准头文件路径,通常是 /usr/include 或 /usr/local/include。
  3. 查找其他路径:如果在项目内和系统路径中都找不到所需的头文件,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
}