Python 刷Leetcode题库，顺带学英语单词（45）

Count Primes

Count the number of prime numbers less than a non-negative number, n.    [#204]

Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.     [#209]

Example：
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.   [#215]

Examples:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

题意：在未排序的数组中找出第k大的数

>>> KthLargest = lambda lst,k:sorted(lst,reverse=True).index(k-1)
>>> nums = [3,2,1,5,6,4]; k = 2
>>> KthLargest(nums, k)
5
>>> nums = [3,2,3,1,2,4,5,5,6]; k = 4
>>> KthLargest(nums, k)
4
>>> 
>>> # 或者：
>>> KthLargest = lambda lst,k:list(reversed(sorted(lst))).index(k-1)
>>> nums = [3,2,1,5,6,4]; k = 2
>>> KthLargest(nums, k)
5
>>> nums = [3,2,3,1,2,4,5,5,6]; k = 4
>>> KthLargest(nums, k)
4
>>>