684. 冗余连接

题目描述 在本问题中, 树指的是一个连通且无环的无向图。 输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。 结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ,满足 u < v,表示连接顶点u 和v的无向图的边。 返回一条可以删去的边,使得结果图是一个有着N个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。 示例 1: 输入: [[1,2], [1,3], [2,3]] 输出: [2,3] 解释: 给定的无向图为: 1 / \ 2 – 3 示例 2: 输入: [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4] 解释: 给定的无向图为: 5 – 1 – 2 | | 4 -…

Read more

287. 寻找重复数

题目描述 给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。 示例 1: 输入: [1,3,4,2,2] 输出: 2 示例 2: 输入: [3,1,3,4,2] 输出: 3 说明: 不能更改原数组(假设数组是只读的)。 只能使用额外的 O(1) 的空间。 时间复杂度小于 O(n2) 。 数组中只有一个重复的数字,但它可能不止重复出现一次。 https://leetcode-cn.com/problems/find-the-duplicate-number/ 解法1 首先,题目说了不能更改数组、且空间复杂度为O(1),那么我们就不能够使用排序算法。此外,时间复杂度要求小于O(n^2),就不能够使用暴力法(双重循环遍历每个元素)。 题目描述了有n+1个元素,值域为[1, n],这就提示我们:我们可以用数组内容作为数组的索引。例如nums = [1,3,4,2,2]: 索引 0 1 2 3 4内容 1 3 4 2 2从索引为0开始,使用数组内容作为索引遍历:nums[0] = 1nums[1] = 3nums[3] = 2nums[2] = 4nums[4] = 2nums[2]…

Read more