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

Recent Posts

Full Category Index

Posts in “Project”

CheckIO 3 | House Password

Wed, Aug 10, 2016
转载请注明出处! 原文链接:CheckIO 3 | House Password 任务: 斯蒂芬和索菲亚对于一切都使用简单的密码,忘记了安全性。请你帮助尼古拉开发一个密码安全检查模块。如果密码的长度大于或等于10个符号,至少有一个数字,一个大写字母和一个小写字母,该密码将被视为足够强大。密码只包含ASCII拉丁字母或数字。 输入: 密码 (str, unicode)。 输出: 密码的安全与否,作为布尔值(bool),或者任何可以转换和处理为布尔值的数据类型。你会在结果看到转换后的结果(True 或 False)。 Example: checkio(‘A1213pokl’) == False checkio(‘bAse730onE’) == True checkio(‘asasasasasasasaas’) == False checkio(‘QWERTYqwerty’) == False checkio(‘123456123456’) == False checkio(‘QwErTy911poqqqq’) == True 如何使用: 如果你担心你的应用或服务的安全性,您可以检查用户密码的复杂性。你可以使用这些技巧要求你的用户的密码符合多个条件(标点符号或unicode)。 前提:: re.match(”[a-zA-Z0-9]+“, password) 0 < len(password) ≤ 64 答案: def checkio(data): if len(data)>9: if any(i.isupper() for i in data) and any(i.islower() for i in data) and any(i.isdigit() for i in data): return True else: return False else: return False 其它答案:

CheckIO 2 | Median

Wed, Aug 10, 2016
转载请注明出处! 原文链接:CheckIO 2 | Median 任务: 中位数是一个可将数值集合划分为相等的上下两部分的一个数值。如果列表数据的个数是奇数,则列表中间那个数据就是列表数据的中位数;如果列表数据的个数是偶数,则列表中间那2个数据的算术平均值就是列表数据的中位数。在这个任务里,你将得到一个含有自然数的非空数组(X)。你必须把它分成上下两部分,找到中位数。 输入: 一个作为数组的整数(int)列表(list)的。 输出: 数组的中位数(int, float). 范例: checkio([1, 2, 3, 4, 5]) == 3 checkio([3, 1, 2, 5, 3]) == 3 checkio([1, 300, 2, 200, 1]) == 2 checkio([3, 6, 20, 99, 10, 15]) == 12.5 如何使用: 中位数在概率论和统计学中得到应用,它偏态分布中有显著的价值。例如:我们想从一组数据中知道人们的平均财富 – 100人一个月收入100美元,10人一个月收入1,000,000美元。如果我们算平均值,得到的是91000美元。这是一个完全没有向我们展示真实情况的奇怪的值。所以在这种情况下,中位数会给我们更有用的值和较好的描述。 维基百科的文章。 前提: 1 < len(data) ≤ 1000 all(0 ≤ x < 10 ** 6 for x in data) 答案:

CheckIO 1 | Non Unique Element

Tue, Aug 9, 2016
最近在学习Python,听说了一个叫CheckIO的网站(需要翻墙),是通过游戏的方式以Python来解答各种问题,正好可以通过该网站的任务来加深对Python的理解,希望以后能有时间每天做一两道题,在此记录的是不是我的答案,只记录一下比较经典的答案,基于Python 2.7。 转载请注明出处! 原文链接:CheckIO 1 | Non Unique Element 任务: 你将得到一个含有整数(X)的非空列表。在这个任务里,你应该返回在此列表中的非唯一元素的列表。要做到这一点,你需要删除所有独特的元素(这是包含在一个给定的列表只有一次的元素)。解决这个任务时,不能改变列表的顺序。例如:[1,2,3,1,3] 1和3是非唯一元素,结果将是 [1, 3, 1, 3]。 输入: 一个含有整数的列表。 输出: 一个含有不唯一元素的整数列表。 范例: checkio([1, 2, 3, 1, 3]) == [1, 3, 1, 3] checkio([1, 2, 3, 4, 5]) == [] checkio([5, 5, 5, 5, 5]) == [5, 5, 5, 5, 5] checkio([10, 9, 10, 10, 9, 8]) == [10, 9, 10, 10, 9] 如何使用: 这个任务将帮助您了解如何操作数组,这是解决更复杂的任务的基础。这个概念可以很容易地推广到真实世界的任务。例如你需要通过删除低频的元素(噪声)来使统计数据更清楚。 前提: 0 < |X| < 1000

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] !