标签： todo

1766.互质树

目标

给你一个 n 个节点的树（也就是一个无环连通无向图），节点编号从 0 到 n - 1 ，且恰好有 n - 1 条边，每个节点有一个值。树的 根节点 为 0 号点。

给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值，edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。

当 gcd(x, y) == 1 ，我们称两个数 x 和 y 是 互质的 ，其中 gcd(x, y) 是 x 和 y 的 最大公约数 。

从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。

请你返回一个大小为 n 的数组 ans ，其中 ans[i]是离节点 i 最近的祖先节点且满足 nums[i] 和 nums[ans[i]] 是 互质的 ，如果不存在这样的祖先节点，ans[i] 为 -1 。

说明：

  • nums.length == n
  • 1 <= nums[i] <= 50
  • 1 <= n <= 10^5
  • edges.length == n - 1
  • edges[j].length == 2
  • 0 <= uj, vj < n
  • uj != vj

思路

今天这道题超时了，看了答案才发现节点值不超过50。没有注意到这个点，答案是先计算1到50内每个数字互质的数字列表。然后在dfs的时候记录节点值的最大深度，以及最近的编号。

我是直接记录了parent数组，一步一步向上找，在第35/37个案例超时了，这棵树是单链，并且除了根节点，向上找都不互质，只能从叶子找到根。

这样在递归中套递归直接堆栈溢出了。后来又将这两个递归分开，不溢出了，但还是超时。

后来又试图利用已求得的结果，记录了value -> 最近互质父节点编号的映射，错误地认为如果值相等就可以直接返回这个编号。其实是不对的，因为这二者之间的父节点也可能与当前节点互质。

其实我想到了应该维护一个去重的父节点序列，但是今天没时间了，只能去看答案了。预处理这个点没有想到，记录值的最大深度与最近编号这个也不好想，也许时间充裕可能会想到吧。

好多经过深度思考得到的复杂的算法，时间久了就会忘记许多细节。没必要非得自己想出来，有这时间多看看算法书进步的更快吧。

代码

// todo

性能

// todo

2009.使数组连续的最少操作数

目标

给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。

如果 nums 满足以下条件，那么它是 连续的 ：

  • nums 中所有元素都是 互不相同 的。
  • nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。

比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。

请你返回使 nums 连续 的 最少 操作次数。

示例 1：

输入：nums = [4,2,5,3]
输出：0
解释：nums 已经是连续的了。

示例 2：

输入：nums = [1,2,3,5,6]
输出：1
解释：一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ，是连续数组。

示例 3：

输入：nums = [1,10,100,1000]
输出：3
解释：一个可能的解是：
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ，是连续数组。

说明：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

思路

这道题让我们求将一个数组变为连续数组所需的最小操作，所谓连续数组指数组中元素各不相同，且max - min = nums.length - 1，也就是说如果将数组从小到大排序，会得到一个公差为1的数列。

我们首先将数组排序，然后初始的数组中会有不连续的边界，也会有相等的元素。如何处理才能使数列连续，并且保证操作数最小。

我陷入了这个困境，尝试了好几个小时，试图处理各种特殊情况。比如我会先找到最大的连续子序列并且记录边界的差值，然后以它为中心分别从后面、前面获取元素来填充这个边界。并且还要计数相同元素来填充边界，这里填充的时机也会对最小的操作有影响。有时需要先填充，有时则需要最后。总之，并没有一个统一的，明确的算法来满足所有情况。

看了官网的解答，应该使用滑动窗口思想。之前一直有看到这个题型分类，没想到这就是所谓的滑动窗口。

当我遇到困难的时候会有一种执念，不愿意去看题解，想知道沿着自己的思路下去为什么不行，到最后真的有点沮丧。这样我想起了迪杰斯特拉的一个采访。

An interview with Edsger W. Dijkstra

The computer science luminary, in one of his last interviews before his death in 2002, reflects on a programmer’s life.

There’s a curious story behind your “shortest path” algorithm.

In 1956 I did two important things, I got my degree and we had the festive opening of the ARMAC(Automatic Calculator Mathematical Centre, 自动计算器数学中心).

We had to have a demonstration. Now the ARRA(Automatic Relay Calculator Amsterdam, 自动继电器计算器 阿姆斯特丹), a few years earlier, had been so unreliable that the only safe demonstration we dared to give was the generation of random numbers, but for the more reliable ARMAC I could try something more ambitious. For a demonstration for noncomputing people you have to have a problem statement that non-mathematicians can understand; they even have to understand the answer. So I designed a program that would find the shortest route between two cities in the Netherlands, using a somewhat reduced roadmap of the Netherlands, on which I had selected 64 cities (so that in the coding six bits would suffice to identify a city).

What’s the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path, which I designed in about 20 minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a 20-minute invention. In fact, it was published in 1959, three years later. The publication is still quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. Without pencil and paper you are almost forced to avoid all avoidable complexities.

Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame. I found it in the early 1960s in a German book on management science—“Das Dijkstra’sche Verfahren” [“Dijkstra’s procedure”].

Suddenly, there was a method named after me. And it jumped again recently because it is extensively used in all travel planners. If, these days, you want to go from here to there and you have a car with a GPS and a screen, it can give you the shortest way.

1956年，迪杰斯特拉与未婚妻在阿姆斯特丹逛商场累了，坐在咖啡厅的露台上喝咖啡，他想到了一个问题"从鹿特丹到格罗宁根最短的旅行路线是什么？"，并且在20分钟内构思了最短路径算法。该算法在三年后被发表在一篇三页的论文中，题为 A note on two problems in connexion with graphs。Dijkstra 因其对开发结构化编程语言的基本贡献而获得 1972 年图灵奖，但最短路径算法仍然是他最著名的工作。

During an interview in 2001, Edsger Wybe Dijkstra revealed that he designed the algorithm in just 20 minutes while shopping in Amsterdam with his fiancée in 1956.

He was inspired by the question, "What's the shortest way to travel from Rotterdam to Groningen?"

He designed it without pencil and paper. He even mentioned that the advantage of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities.

The algorithm was published three years later in a three-page article titled "A note on two problems in connexion with graphs".

https://twitter.com/LinuxHandbook/status/1754392486657798198

也许这就是天赋吧。我只是个普通人，不可能解决所有问题，没有什么可沮丧的。要努力站在巨人的肩膀上，知识并不是免费的，需要投入时间。所以没有必要死磕一个问题，快速高效的爬上去，然后当面对新的未知的问题时，再花费精力研究才对。

思考的意义可能就是让自己对困难、问题有了更深的体会，看解答要弄明白问题是如何解决的。

就以这个题为例，困难点在于如何使操作最小。虽然知道长度是固定的，但是并没有意识到如何遍历所有可能的操作方法并取其最小。陷入了具体的、面向过程的、针对案例而设计的算法之中。当我先入为主的认为，应该以最大连续子数组为中心不变，从两端借数填充这个错误的指导思想进行实现时，就注定得不到正确答案。

之所以开始会认为应该保持最大的连续子数组不变，是因为观察了几个测试案例，想当然的认为，既然最后要变成连续数组，那么保持最大的不变，操作数会最小，但其实并非如此。并且，先从后面填还是前面也是没有道理的，都是根据具体的测试案例写的。

也许其它时间，灵光一闪也会想到滑动窗口算法也说不定。如果之前接触过这个概念，那这个题还是挺简单的。

代码

// todo: 过几天自己实现一遍

性能

// todo

2192.有向无环图中一个节点的所有祖先

目标

给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。

给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。

请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。

如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。

说明：

  • 1 <= n <= 1000
  • 0 <= edges.length <= min(2000, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi <= n - 1
  • fromi != toi
  • 图中不会有重边。
  • 图是 有向 且 无环 的。

思路

这个题要求所有节点的祖先节点集合，最直接的想法就是广度遍历然后记录父节点，然后下一个节点的祖先节点就是其父节点加上父节点的祖先节点。

需要注意的点是图不一定连通，所以选定一个起点不一定能遍历到所有节点。如果直接将所有节点加入队列容易超时。解决方法是先找到没有父节点的根节点，然后再广度遍历。

如果节点已经在队列中就不需要重复放入队列了，因为该节点的祖先集合可以由队列中的节点一起更新。

代码

/**
 * @date 2024-04-04 21:49
 */
public class GetAncestors2192 {

    /** 先找出没有parent的节点放入队列，然后广度优先遍历即可*/
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<Integer>[] g = new ArrayList[n];
        Set<Integer>[] dp = new TreeSet[n];
        List<List<Integer>> res = new ArrayList<>(n);
        Deque<Integer> q = new ArrayDeque<>();
        boolean[] hasParent = new boolean[n];
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<>();
            dp[i] = new TreeSet<>();
        }
        for (int[] edge : edges) {
            g[edge[0]].add(edge[1]);
            hasParent[edge[1]] = true;
        }
        for (int i = 0; i < hasParent.length; i++) {
            if (!hasParent[i]) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            Integer from = q.poll();
            for (int i = 0; i < g[from].size(); i++) {
                dp[g[from].get(i)].addAll(dp[from]);
                dp[g[from].get(i)].add(from);
                if (!q.contains(g[from].get(i))) {
                    q.offer(g[from].get(i));
                }
            }
        }
        for (Set<Integer> integers : dp) {
            res.add(new ArrayList<>(integers));
        }
        return res;
    }
}

性能

勉强过关，官网还介绍了拓扑排序的方法，有机会再更新吧。

518.零钱兑换II

目标

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

说明：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

思路

// todo

代码

/**
 * @date 2024-03-25 8:31
 */
public class CoinChange {

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        CoinChange main = new CoinChange();
//        int amount = 5;
        int amount = 500;
        int[] coins = new int[]{1, 2, 5};
//        System.out.println(main.change(amount, coins));
//        System.out.println(main.change(amount, coins));
        System.out.println(main.change(amount, coins));
    }
}

性能

// todo

322.零钱兑换

目标

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

说明：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

思路

// todo

思考的方向错了，试图用贪心算法枚举可能的组合。做法是优先选面值最大的，取得余数，再计算下一个面值的余数，直到余数为0。但是这样得到的不一定是最优解。尝试将最大面值的个数减一，然后余数加上最大面值，重新计算。但是还是一样的，如果要调整的话，所有面值的个数都要调整，不能只调整最大的，后面的还用贪心，这样问题就不可解了。

代码

/**
 * @date 2024-03-24 0:04
 */
public class CoinChange {

    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        CoinChange main = new CoinChange();
//        int[] coins = new int[]{3, 7};
        int[] coins = new int[]{186, 419, 83, 408};
//        System.out.println(main.coinChange(coins, 9));
        System.out.println(main.coinChange(coins, 6249));
    }
}

性能

// todo