g-var.com | G-VAR's Blog

Recent Posts

Full Tag Index

Posts in “Leetcode”

LeetCode 6 | Longest Consecutive Sequence

Mon, May 11, 2015
转载请注明出处! 原文链接:LeetCode 6 | Longest Consecutive Sequence 描述 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. Your algorithm should run in O(n) complexity. 分析 如果允许 O(n log n) 的复杂度,那么可以先排序,可是本题要求 O(n)。 由于序列里的元素是无序的,又要求 O(n),首先要想到用哈希表。 用一个哈希表 unordered_map<int, bool> used 记录每个元素是否使用,对每个元素,以该元素为中心,往左右扩张,直到不连续为止,记录下最长的长度。 代码 func longestConsecutive(A []int) int { used := map[int]bool{} for _, vA := range A { used[vA] = false } longest := 0 for _, vA := range A { if used[vA] { continue } length := 1 used[vA] = true j := vA + 1; for _, ok := used[j]; ok&&j<len(A); _, ok = used[j] { used[j] = true length++ j++ } m := vA - 1 for _, ok := used[m]; ok&&m<len(A); _, ok = used[j] { used[m] = true length++ m-- } if longest < length { longest = length } } return longest } [ 转载必须在正文中标注并保留原文链接、译文链接等信息。]

LeetCode 5 | Median of Two Sorted Arrays

Fri, May 8, 2015
转载请注明出处! 原文链接:LeetCode 5 | Median of Two Sorted Arrays 描述 There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log(m + n)). 分析 这是一道非常经典的题。这题更通用的形式是,给定两个已经排序好的数组,找到两者所有元素中第 k 大的元素。 O(m + n) 的解法比较直观,直接 merge 两个数组,然后求第 k 大的元素。 不过我们仅仅需要第 k 大的元素,是不需要“排序”这么复杂的操作的。可以用一个计数器,记录当前已经找到第 m 大的元素了。同时我们使用两个指针 pA 和 pB,分别指向 A 和 B 数组的第一个元素,使用类似于 merge sort 的原理,如果数组 A 当前元素小,那么 pA++,同时 m++;如果数组 B 当前元素小,那么 pB++,同时 m++。最终当 m 等于 k 的时候,就得到了我们的答案,O(k) 时间,O(1) 空间。但是,当 k 很接近 m + n 的时候,这个方法还是 O(m + n) 的。 有没有更好的方案呢?我们可以考虑从 k 入手。如果我们每次都能够删除一个一定在第 k 大元素之前的元素,那么我们需要进行 k 次。但是如果每次我们都删除一半呢?由于 A 和 B 都是有序的,我们应该充分利用这里面的信息,类似于二分查找,也是充分利用了“有序”。 假设 A 和 B 的元素个数都大于 k/2,我们将 A 的第 k/2 个元素(即 A[k/2-1])和 B 的第 k/2个元素(即 B[k/2-1])进行比较,有以下三种情况(为了简化这里先假设 k 为偶数,所得到的结论对于 k 是奇数也是成立的): • A[k/2-1] == B[k/2-1] • A[k/2-1] > B[k/2-1] • A[k/2-1] < B[k/2-1] 如果 A[k/2-1] < B[k/2-1],意味着 A[0] 到 A[k/2-1 的肯定在 A [ B 的 top k 元素的范围内,换句话说,A[k/2-1 不可能大于 A [ B 的第 k 大元素。留给读者证明。 因此,我们可以放心的删除 A 数组的这 k/2 个元素。同理,当 A[k/2-1] > B[k/2-1] 时,可以删除 B 数组的 k/2 个元素。 当 A[k/2-1] == B[k/2-1] 时,说明找到了第 k 大的元素,直接返回 A[k/2-1] 或 B[k/2-1]即可。 因此,我们可以写一个递归函数。那么函数什么时候应该终止呢? • 当 A 或 B 是空时,直接返回 B[k-1] 或 A[k-1]; • 当 k=1 是,返回 min(A[0], B[0]); • 当 A[k/2-1] == B[k/2-1] 时,返回 A[k/2-1] 或 B[k/2-1] 代码 func findMedianSortedArrays(A []int, m int, B []int, n int) int { total := m + n con := total & 0x1 if con == 1 { return findKth(A, m, B, n, total / 2 + 1) } else { return (findKth(A, m, B, n, total / 2) + findKth(A, m, B, n, total / 2 + 1)) / 2; } } func findKth(A []int, m int, B []int, n int, k int) int{ if m > n { return findKth(B, n, A, m, k) } if m == 0 { return B[k - 1] } if k == 1 { if A[0] > B[0] { return B[0] } else { return A[0] } } var iA int = 0 if k / 2 > m { iA = m } else { iA = k / 2 } iB := k - iA if A[iA - 1] < B[iB - 1] { sA := A[:iA] return findKth(sA, m - iA, B, n, k - iA) } else if A[iA - 1] > B[iB - 1] { sB := B[:iB] return findKth(A, m, sB, n - iB, k - iB) } else { return A[iA - 1] } } [ 转载必须在正文中标注并保留原文链接、译文链接等信息。]

LeetCode 4 | Search in Rotated Sorted Array II

Thu, May 7, 2015
转载请注明出处! 原文链接:LeetCode 4 | Search in Rotated Sorted Array II 描述 Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array. 分析 允许重复元素,则上一题中如果 A[m]>=A[l], 那么 [l,m] 为递增序列的假设就不能成立了,比如 [1,3,1,1,1]。 如果 A[m]>=A[l] 不能确定递增,那就把它拆分成两个条件: • 若 A[m]>A[l],则区间 [l,m] 一定递增 • 若 A[m]==A[l] 确定不了,那就 l++,往下看一步即可。 代码 func search(A []int, n int, target int ) bool { first := 0 last := n for first !

LeetCode 3 | Search in Rotated Sorted Array

Wed, May 6, 2015
转载请注明出处! 原文链接:LeetCode 3 | Search in Rotated Sorted Array 描述 Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. 分析 二分查找,难度主要在于左右边界的确定。 代码 func search(A []int, n int, target int ) int { first := 0 last := n for first !

LeetCode 2 | Remove Duplicates From Sorted Array II

Wed, May 6, 2015
转载请注明出处! 原文链接:LeetCode 2 | Remove Duplicates From Sorted Array II 描述 Follow up for ”Remove Duplicates”: What if duplicates are allowed at most twice? For example, Given sorted array A = [1,1,1,2,2,3], Your function should return length = 5, and A is now [1,1,2,2,3] 分析 加一个变量记录一下元素出现的次数即可。这题因为是已经排序的数组,所以一个变量即可解决。如果是没有排序的数组,则需要引入一个 hashmap 来记录出现次数。 代码 func removeDuplicates(A []int, n int ) int { if n <= 2 { return n } index := 2 for i:=2; i<n; i++ { if A[i] !

LeetCode 1 | Remove Duplicates From Sorted Array

Wed, May 6, 2015
转载请注明出处! 原文链接:LeetCode 1 | Remove Duplicates From Sorted Array 描述 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2]. 分析 无 代码 func removeDuplicates(A []int, n int ) int { if n == 0 { return 0 } index := 0 for i:=1; i<n; i++ { if A[index] !