lc1015

对n%k不影响结果(关于%的trick～

 

鸽巢原理：模k的结果只有0到k-1 种可能，循环k次后没有n % k=0，余数会出现重复，后续也不会再出现0，可判定不存在这样的n。

 class Solution {
public:
    int smallestRepunitDivByK(int k) {
        int n = 1 % k;
        for (int i = 1; i <= k; ++i) {
            if (n == 0) {
                return i;
            }
            n = (n * 10 + 1) % k;
        }
        return -1;
    }
};

Floyd & sos dp

 
1. 关于「状态定义」
 
可以把它想象成给问题“贴标签”。比如你要解决“从家到公司的最短路线”

得先明确“当前在哪个路口”“已经走了多远”这些信息，这些就是状态

没有这些标签，就没法把大问题拆成小问题一步步解决。
 
2. 「Floyd算法的节点编号限制」
 
Floyd是用来找所有点之间最短路径的算法

它的证明里有时会加入“节点编号大小”的限制（比如只考虑编号≤k的节点作为中间点），这就像给问题“划范围”——先解决小范围的子问题（比如只允许1号节点当中间点），再扩展到更大的范围（允许1、2号节点当中间点），最终覆盖所有情况

这样能把复杂的全局问题拆成可处理的局部子问题。

 
3. 「SOSDP（子集和动态规划）的大小限制」
 
SOSDP是用来处理子集相关问题的算法（比如“选一些元素，它们的和满足什么条件”）

它也会对元素编号做大小限制，比如“只考虑前k个元素的子集”。

这样做的目的和Floyd类似：先解决小范围的子集问题，再逐步扩展，避免一下子面对所有元素的复杂情况，从而缩小问题的“规模”（复杂度）。

 
4. 「异曲同工之妙」
 
Floyd和SOSDP虽然解决的问题不同，但思路是相通的——通过“限制范围（比如节点编号、元素编号的大小）”把大问题拆成层层递进的子问题，先解决小的，再扩展到大的，最终得到全局的解。这种“分而治之”的思路在算法里很常见，就像不同的工具却用了同一种“拆解问题”的逻辑~
 
简单来说，这些讨论的核心就是：算法里经常通过“给状态加限制（比如编号大小）”来把复杂问题拆成简单子问题，从而高效解决。

 

lc1135

prim 最小生成树 dijstr变种

class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int, int>>> g(n + 1);
        for (auto& c : connections) {
            int u = c[0], v = c[1], cost = c[2];
            g[u].emplace_back(v, cost);
            g[v].emplace_back(u, cost);
        }

       // vector<int> dist(n + 1, INT_MAX);
        vector<bool> visited(n + 1, false);
       // dist[1] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.emplace(0, 1);

        int totalCost = 0;
        int cnt = 0;

        while (!pq.empty()) {
            auto [cost, u] = pq.top();
            pq.pop();

            if (visited[u]) continue;
            visited[u] = true;
            totalCost += cost;
            cnt++;

            for (auto [v, w] : g[u]) {
                if (!visited[v]）
                    pq.emplace(w, v);
                
            }
        }

        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                return -1;
            }
        }
        return totalCost;
    }
};

两处：
 
-  dist[1] = 0;  和  pq.emplace(0, 1); ：这是算法的起点初始化。

选择从城市 1 开始构建最小生成树，将城市 1 的“初始连接成本”设为 0 

-  if (!visited[v] && dist[v] > w) { dist[v] = w; } ：这是更新更优路径的逻辑。

dist[v] 记录当前到城市 v 的最小连接成本， w 是从城市 u 到 v 的直接成本(这步这题可删去)

如果发现从 u 到 v 的直接成本 w 比之前记录的 dist[v] 更小，就更新 dist[v] 为 w ，确保始终保留最小成本的连接方式。

 

 

lc1273

邻接表建图后pair<int, int> dfs(int node)

return dfs(0).second;

class Solution {

    vector<vector<int>> g;

    vector<int> value;

public:

    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {

        g.resize(nodes);

        this->value = value;

        for (int i = 0; i < nodes; ++i) {

            if (parent[i] != -1) {

                g[parent[i]].push_back(i);

            }

        }

        return dfs(0).second;

    }

    pair<int, int> dfs(int node) {

        int sum = value[node];

        int cnt = 1;

        for (int child : g[node]) {

            auto [childSum, childCnt] = dfs(child);

            sum += childSum;

            cnt += childCnt;

        }

        if (sum == 0) 

            cnt = 0; // 子树和为0，节点数记为0

        return {sum, cnt};

    }

};