2017年2月26日 星期日

【Python】Codility in Python : Lesson 10 - Prime and composite numbers【CountFactors】

Prime and composite numbers 第一題:【CountFactors】
Count factors of given number n.

A positive integer D is a factor of a positive integer N
if there exists an integer M such that N = D * M.

For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function:

  def solution(N)

that, given a positive integer N, returns the number of its factors.

For example, given N = 24, the function should return 8,
because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.

Assume that:
  N is an integer within the range [1..2,147,483,647].


方法一:用平方根的方式推算
Correctness:100%、Performance:100%
```python import math def solutionBySqrt(N): result = 0 squareRoot = math.sqrt(N) for index in range(1, math.ceil(squareRoot)): if N % index == 0: result += 2 if squareRoot == math.ceil(squareRoot): result += 1 return result ```

方法二:用 lambda 寫法一行解決,可惜效能太差 ...
Correctness:100%、Performance:0%
```python def solutionByLambda(N): return len(list(filter(lambda x: N % x == 0, range(1, N+1)))) ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 9 - Maximum slice problem【MaxSliceSum】

Maximum slice problem 第三題:【MaxSliceSum】
Find a maximum sum of a compact subsequence of array elements.

A non-empty zero-indexed array A consisting of N integers is given.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A.
The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

Write a function:

  def solution(A)

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:

A[0] = 3 A[1] = 2 A[2] = -6
A[3] = 4 A[4] = 0

the function should return 5 because:

(3, 4) is a slice of A that has sum 4,
(2, 2) is a slice of A that has sum −6,
(0, 1) is a slice of A that has sum 5,

no other slice of A has sum greater than (0, 1).

Assume that:
  N is an integer within the range [1..1,000,000];
  each element of array A is an integer within the range [−1,000,000..1,000,000];
  the result will be an integer within the range [−2,147,483,648..2,147,483,647].


方法一:使用 loop 慢慢取最大值
Correctness:100%、Performance:100%
```python def solution(S): maxSlice = 0 result = A[0] length = len(A) for value in A: maxSlice = max(value, maxSlice + value) result = max(result, maxSlice) return result ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 9 - Maximum slice problem【MaxProfit】

Maximum slice problem 第二題:【MaxProfit】
Given a log of stock prices compute the maximum possible earning.

A zero-indexed array A consisting of N integers is given.
It contains daily prices of a stock share for a period of N consecutive days.
If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N,
then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P].
Otherwise, the transaction brings loss of A[P] − A[Q].

For example, consider the following array A consisting of six elements such that:

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367

If a share was bought on day 0 and sold on day 2,
a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048.
If a share was bought on day 4 and sold on day 5,
a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354.
Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.

Write a function,

  def solution(A)

that, given a zero-indexed array A consisting of N integers
containing daily prices of a stock share for a period of N consecutive days,
returns the maximum possible profit from one transaction during this period.
The function should return 0 if it was impossible to gain any profit.

For example, given array A consisting of six elements such that:

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367

the function should return 356, as explained above.

Assume that:

N is an integer within the range [0..400,000];
each element of array A is an integer within the range [0..200,000].


方法一:用最小價格取最大利潤
Correctness:100%、Performance:100%
```python def solution(S): minPrice = sys.maxsize profit = 0 for number in A: minPrice = min(number, minPrice) profit = max(number - minPrice, profit) return profit ```

完整練習題 source code 請參閱:github

2017年2月24日 星期五

【Python】Codility in Python : Lesson 9 - Maximum slice problem【MaxDoubleSliceSum】

Maximum slice problem 第一題:【MaxDoubleSliceSum】
Find the maximal sum of any double slice.

A non-empty zero-indexed array A consisting of N integers is given.

A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.

The sum of double slice (X, Y, Z) is the total of
A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].

For example, array A such that:

  A[0] = 3
  A[1] = 2
  A[2] = 6
  A[3] = -1
  A[4] = 4
  A[5] = 5
  A[6] = -1
  A[7] = 2

contains the following example double slices:

  double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
  double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16,
  double slice (3, 4, 5), sum is 0.

The goal is to find the maximal sum of any double slice.

Write a function:

  def solution(A)

that, given a non-empty zero-indexed array A consisting of N integers,
returns the maximal sum of any double slice.

For example, given:

  A[0] = 3
  A[1] = 2
  A[2] = 6
  A[3] = -1
  A[4] = 4
  A[5] = 5
  A[6] = -1
  A[7] = 2

the function should return 17,
because no double slice of array A has a sum of greater than 17.

Assume that:

N is an integer within the range [3..100,000];
each element of array A is an integer within the range [−10,000..10,000].


方法一:參考 martinkysel.com 提供的做法
Correctness:100%、Performance:100%
```python def solution(S): length = len(A) start = [0] * length end = [0] * length for i in reversed(range(length-1)): start[i] = max(0, start[i+1] + A[i]) for i in range(1, length): end[i] = max(0, end[i-1] + A[i]) maxDoubleSlice = 0 for i in range(1, length-1):  maxDoubleSlice = max(maxDoubleSlice, start[i+1] + end[i-1]) return maxDoubleSlice ```

完整練習題 source code 請參閱:github

2017年2月23日 星期四

【Python】Codility in Python : Lesson 8 - Leader【EquiLeader】

Leader 第二題:【EquiLeader】
Find the index S such that the leaders of the sequences A[0], A[1], ...,
A[S] and A[S + 1], A[S + 2], ..., A[N - 1] are the same.

A non-empty zero-indexed array A consisting of N integers is given.

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences
A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.

For example, given array A such that:

  A[0] = 4
  A[1] = 3
  A[2] = 4
  A[3] = 4
  A[4] = 4
  A[5] = 2

we can find two equi leaders:

0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.
The goal is to count the number of equi leaders.

Write a function:

  def solution(A)

that, given a non-empty zero-indexed array A consisting of N integers,
returns the number of equi leaders.

For example, given:

  A[0] = 4
  A[1] = 3
  A[2] = 4
  A[3] = 4
  A[4] = 4
  A[5] = 2

the function should return 2, as explained above.

Assume that:

  N is an integer within the range [1..100,000];
  each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].


方法一:先 groupby 再用 loop 的方式慢慢解
Correctness:100%、Performance:100%
```python from itertools import groupby def solution(S): d = dict() key = value = -1 maxGroup = max(groupby(sorted(A)), key = lambda x: len(list(x[1]))) key = maxGroup[0] value = len(list(filter(lambda x: x == key, A))) length = len(A) if value <= length / 2: return 0 left = 0 right = value count = 0 for i in range(length): if A[i] == key: left += 1 right -= 1 if left > (i+1) / 2 and right > (length - i - 1) / 2: count += 1 return count ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 8 - Leader【Dominator】

Leader 第一題:【Dominator】
Find an index of an array such that its value occurs at more than half of indices in the array.
A zero-indexed array A consisting of N integers is given.
The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

  A[0] = 3 A[1] = 4 A[2] = 3
  A[3] = 2 A[4] = 3 A[5] = -1
  A[6] = 3 A[7] = 3

The dominator of A is 3 because it occurs in 5 out of 8 elements of A
(namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

  def solution(A)

that, given a zero-indexed array A consisting of N integers,
returns index of any element of array A in which the dominator of A occurs.
The function should return −1 if array A does not have a dominator.

Assume that:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
For example, given array A such that

  A[0] = 3 A[1] = 4 A[2] = 3
  A[3] = 2 A[4] = 3 A[5] = -1
  A[6] = 3 A[7] = 3

the function may return 0, 2, 4, 6 or 7, as explained above.


方法一:使用 groupby 的方式再 loop 慢慢解
Correctness:100%、Performance:100%
```python from itertools import groupby def solution(S): if len(A) == 1: return 0 dominator = -1 dominatorCount = 0 for k, v in groupby(sorted(A)): length = len(list(v)) if(length > dominatorCount): dominator = k dominatorCount = length if dominator == -1: return -1 index = -1 for i in range(0, len(A) - 1): if(A[i] == dominator): if(i == 0 or A[i] == A[i+1]): index = i return index if(dominatorCount > (len(A) / 2)) else -1 ```

完整練習題 source code 請參閱:github

2017年2月22日 星期三

【Python】Codility in Python : Lesson 7 - Stacks and Queues【Nesting】

Stacks and Queues 第四題:【Nesting】
Determine whether given string of parentheses is properly nested.
A string S consisting of N characters is called properly nested if:

S is empty;
S has the form "(U)" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

  def solution(S)

that, given a string S consisting of N characters,
returns 1 if string S is properly nested and 0 otherwise.

For example, given S = "(()(())())", the function should return 1 and given S = "())",
the function should return 0, as explained above.

Assume that:

  N is an integer within the range [0..1,000,000];
  string S consists only of the characters "(" and/or ")".


方法一:用 append 和 pop 實作 stack 的概念
Correctness:100%、Performance:100%
```python def solution(S): stack = [] for sign in S: if sign == '(': stack.append(sign) else: if len(stack) == 0: return 0 stackLast = stack[-1] if sign == ')' and stackLast == '(': stack.pop() else: return 0 return 1 if len(stack) == 0 else 0 ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 7 - Stacks and Queues【Fish】

Stacks and Queues 第三題:【Fish】
N voracious fish are moving along a river. Calculate how many fish are alive.
You are given two non-empty zero-indexed arrays A and B consisting of N integers.
Arrays A and B represent N voracious fish in a river,
ordered downstream along the flow of the river.

The fish are numbered from 0 to N − 1.
If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q.
Initially, each fish has a unique position.

Fish number P is represented by A[P] and B[P].
Array A contains the sizes of the fish. All its elements are unique.
Array B contains the directions of the fish.
It contains only 0s and/or 1s, where:

  0 represents a fish flowing upstream,
  1 represents a fish flowing downstream.

If two fish move in opposite directions and there are no other (living) fish between them,
they will eventually meet each other.
Then only one fish can stay alive − the larger fish eats the smaller one.
More precisely, we say that two fish P and Q meet each other
when P < Q, B[P] = 1 and B[Q] = 0,
and there are no living fish between them. After they meet:

  If A[P] > A[Q] then P eats Q, and P will still be flowing downstream,
  If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream.

We assume that all the fish are flowing at the same speed.
That is, fish moving in the same direction never meet.
The goal is to calculate the number of fish that will stay alive.

For example, consider arrays A and B such that:

  A[0] = 4 B[0] = 0
  A[1] = 3 B[1] = 1
  A[2] = 2 B[2] = 0
  A[3] = 1 B[3] = 0
  A[4] = 5 B[4] = 0

Initially all the fish are alive and all except fish number 1 are moving upstream.
Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too.
Finally, it meets fish number 4 and is eaten by it.
The remaining two fish, number 0 and 4, never meet and therefore stay alive.

Write a function:

  def solution(A, B)

that, given two non-empty zero-indexed arrays A and B consisting of N integers,
returns the number of fish that will stay alive.

For example, given the arrays shown above, the function should return 2, as explained above.

Assume that:

  N is an integer within the range [1..100,000];
  each element of array A is an integer within the range [0..1,000,000,000];
  each element of array B is an integer that can have one of the following values: 0, 1;
  the elements of A are all distinct.


方法一:用 append 和 pop 實作 stack 的概念
Correctness:100%、Performance:100%
```python def solution(A, B): result = 0 stack = [] for i in range(0, len(A)): if B[i] == 1: # 往下游的放入 stack stack.append(A[i]) result += 1 else: # 往下游跟往上游的比較,如果下游的較弱就被吃掉 while(stack and A[i] > stack[-1]): stack.pop() result -= 1 if(not stack): result += 1 return result ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 7 - Stacks and Queues【StoneWall】

Stacks and Queues 第二題:【StoneWall】
Cover "Manhattan skyline" using the minimum number of rectangles.
You are going to build a stone wall.
The wall should be straight and N meters long, and its thickness should be constant;
however, it should have different heights in different places.
The height of the wall is specified by a zero-indexed array H of N positive integers.
H[I] is the height of the wall from I to I+1 meters to the right of its left end. In particular,
H[0] is the height of the wall's left end and H[N−1] is the height of the wall's right end.

The wall should be built of cuboid stone blocks (that is, all sides of such blocks are rectangular).
Your task is to compute the minimum number of blocks needed to build the wall.

Write a function:

  def solution(H)

that, given a zero-indexed array H of N positive integers specifying the height of the wall,
returns the minimum number of blocks needed to build it.

For example, given array H containing N = 9 integers:

  H[0] = 8 H[1] = 8 H[2] = 5
  H[3] = 7 H[4] = 9 H[5] = 8
  H[6] = 7 H[7] = 4 H[8] = 8

the function should return 7. The figure shows one possible arrangement of seven blocks.

Assume that:
  N is an integer within the range [1..100,000];
  each element of array H is an integer within the range [1..1,000,000,000].


方法一:用 append 和 pop 實作 stack 的概念
Correctness:100%、Performance:100%
```python def solution(H): count = 0 stack = [] for n in H: while(stack and stack[-1] > n): stack.pop() if(stack and stack[-1] == n): continue stack.append(n) count += 1 return count ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 7 - Stacks and Queues【Brackets】

Stacks and Queues 第一題:【Brackets】
Determine whether a given string of parentheses is properly nested.
A string S consisting of N characters is considered to be properly nested
if any of the following conditions is true:

S is empty;
S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

  def solution(S)

that, given a string S consisting of N characters,
returns 1 if S is properly nested and 0 otherwise.

For example, given S = "{[()()]}", the function should return 1
and given S = "([)()]", the function should return 0, as explained above.

Assume that:
  N is an integer within the range [0..200,000];
  string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".


方法一:用 append 和 pop 實作 stack 的概念
Correctness:100%、Performance:100%
```python def solution(S): stack = [] for sign in S: if sign == '(' or sign == '[' or sign =='{': stack.append(sign) else: if len(stack) == 0: return 0 stackLast = stack[-1] if sign == ')' and stackLast == '(': stack.pop() elif sign == ']' and stackLast == '[': stack.pop() elif sign == '}' and stackLast == '{': stack.pop() else: return 0 return 1 if len(stack) == 0 else 0 ```

完整練習題 source code 請參閱:github

2017年2月21日 星期二

【Python】Codility in Python : Lesson 6 - Sorting【NumberOfDiscIntersections】

Sorting 第四題:【NumberOfDiscIntersections】
Compute the number of intersections in a sequence of discs.
We draw N discs on a plane. The discs are numbered from 0 to N − 1.
A zero-indexed array A of N non-negative integers, specifying the radiuses of the discs, is given.
The J-th disc is drawn with its center at (J, 0) and radius A[J].

We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs
have at least one common point (assuming that the discs contain their borders).

The figure below shows discs drawn for N = 6 and A as follows:

  A[0] = 1
  A[1] = 5
  A[2] = 2
  A[3] = 1
  A[4] = 4
  A[5] = 0

There are eleven (unordered) pairs of discs that intersect, namely:

discs 1 and 4 intersect, and both intersect with all the other discs;
disc 2 also intersects with discs 0 and 3.
Write a function:

  def solution(A)

that, given an array A describing N discs as explained above,
returns the number of (unordered) pairs of intersecting discs.
The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Given array A shown above, the function should return 11, as explained above.

Assume that:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [0..2,147,483,647].


方法一:Thiago Papageorgiou 大大提供的做法
Correctness:100%、Performance:100%
```python upper = sorted([k + v for k, v in enumerate(A)]) lower = sorted([k - v for k, v in enumerate(A)]) j = 0 counter = 0 for i, v in enumerate(upper): while j < len(upper) and v >= lower[j]: counter += j-i j += 1 if counter > 10**7 : return -1 return counter ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 6 - Sorting【Triangle】

Sorting 第三題:【Triangle】
Determine whether a triangle can be built from a given set of edges.
A zero-indexed array A consisting of N integers is given.
A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].

For example, consider array A such that:

  A[0] = 10 A[1] = 2 A[2] = 5
  A[3] = 1 A[4] = 8 A[5] = 20

Triplet (0, 2, 4) is triangular.

Write a function:

  def solution(A)

that, given a zero-indexed array A consisting of N integers,
returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:

  A[0] = 10 A[1] = 2 A[2] = 5
  A[3] = 1 A[4] = 8 A[5] = 20

the function should return 1, as explained above. Given array A such that:

  A[0] = 10 A[1] = 50 A[2] = 5
  A[3] = 1

the function should return 0.

Assume that:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].


方法一:使用任兩邊大於第三邊的簡易判斷方法
Correctness:100%、Performance:100%
```python A = sorted(A) for i in range(0, len(A)-2): if(A[i] + A[i+1] > A[i+2]): return 1 return 0 ```

完整練習題 source code 請參閱:github

2017年2月20日 星期一

【Python】Codility in Python : Lesson 6 - Sorting【MaxProductOfThree】

Sorting 第二題:【MaxProductOfThree】
Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).
A non-empty zero-indexed array A consisting of N integers is given.
The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).

For example, array A such that:

  A[0] = -3
  A[1] = 1
  A[2] = 2
  A[3] = -2
  A[4] = 5
  A[5] = 6

contains the following example triplets:

(0, 1, 2), product is −3 * 1 * 2 = −6
(1, 2, 4), product is 1 * 2 * 5 = 10
(2, 4, 5), product is 2 * 5 * 6 = 60

Your goal is to find the maximal product of any triplet.

Write a function:

  def solution(A)

that, given a non-empty zero-indexed array A,
returns the value of the maximal product of any triplet.

For example, given array A such that:

  A[0] = -3
  A[1] = 1
  A[2] = 2
  A[3] = -2
  A[4] = 5
  A[5] = 6

the function should return 60, as the product of triplet (2, 4, 5) is maximal.


方法一:使用 max 取值的簡易方法
Correctness:100%、Performance:100%
```python def solution(A): A = sorted(A) return max(A[-3] * A[-2] * A[-1], A[-1] * A[0] * A[1]) ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 6 - Sorting【Distinct】

Sorting 第一題:【Distinct】
Compute number of distinct values in an array.
Write a function

  def solution(A)

that, given a zero-indexed array A consisting of N integers,
returns the number of distinct values in array A.


方法一:直接取 set 長度的簡易方法
Correctness:100%、Performance:100%
```python def solution(A): return len(set(A)) ```

完整練習題 source code 請參閱:github

2017年2月19日 星期日

【Python】Codility in Python : Lesson 5 - Prefix Sums【MinAvgTwoSlice】

Prefix Sums 第四題:【MinAvgTwoSlice】
Find the minimal average of any slice containing at least two elements.
A non-empty zero-indexed array A consisting of N integers is given.
A pair of integers (P, Q), such that 0 ≤ P < Q < N,
is called a slice of array A (notice that the slice contains at least two elements).
The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice.
To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

For example, array A such that:

  A[0] = 4
  A[1] = 2
  A[2] = 2
  A[3] = 5
  A[4] = 1
  A[5] = 5
  A[6] = 8

contains the following example slices:

slice (1, 2), whose average is (2 + 2) / 2 = 2;
slice (3, 4), whose average is (5 + 1) / 2 = 3;
slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.

The goal is to find the starting position of a slice whose average is minimal.

Write a function:

  def solution(A)

that, given a non-empty zero-indexed array A consisting of N integers,
returns the starting position of the slice with the minimal average.
If there is more than one slice with a minimal average,
you should return the smallest starting position of such a slice.

For example, given array A such that:

  A[0] = 4
  A[1] = 2
  A[2] = 2
  A[3] = 5
  A[4] = 1
  A[5] = 5
  A[6] = 8

the function should return 1, as explained above.


方法一:用 Prefix Sums 的方法
Correctness:100%、Performance:100%
```python import sys def solution(A): result = 0 length = len(A) valueList = [0] for i in range(length): valueList.append(valueList[i] + A[i]) minAvg = sys.float_info.max for i in range(length - 1): index1 = i + 1 index2 = i + 2 avg = (valueList[index1 + 1] - valueList[i]) / 2.0 if(avg < minAvg): minAvg = avg result = i if(i < length - 2): avg = (valueList[index2 + 1] - valueList[i]) / 3.0 if(avg < minAvg): minAvg = avg result = i return result ```

完整練習題 source code 請參閱:github

2017年2月18日 星期六

【Python】Codility in Python : Lesson 5 - Prefix Sums【GenomicRangeQuery】

Prefix Sums 第三題:【GenomicRangeQuery】
Find the minimal nucleotide from a range of sequence DNA.
A DNA sequence can be represented as a string consisting of the letters A, C, G and T,
which correspond to the types of successive nucleotides in the sequence.
Each nucleotide has an impact factor, which is an integer.
Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively.
You are going to answer several queries of the form:
What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?

The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters.
There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers.
The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides
contained in the DNA sequence between positions P[K] and Q[K] (inclusive).

For example, consider string S = CAGCCTA and arrays P, Q such that:

  P[0] = 2  Q[0] = 4
  P[1] = 5  Q[1] = 5
  P[2] = 0  Q[2] = 6

The answers to these M = 3 queries are as follows:

The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice),
whose impact factors are 3 and 2 respectively, so the answer is 2.
The part between positions 5 and 5 contains a single nucleotide T,
whose impact factor is 4, so the answer is 4.
The part between positions 0 and 6 (the whole string) contains all nucleotides,
in particular nucleotide A whose impact factor is 1, so the answer is 1.
Write a function:

def solution(S, P, Q)

that, given a non-empty zero-indexed string S consisting of N characters
and two non-empty zero-indexed arrays P and Q consisting of M integers,
returns an array consisting of M integers specifying the consecutive answers to all queries.

The sequence should be returned as:

a Results structure (in C), or
a vector of integers (in C++), or
a Results record (in Pascal), or
an array of integers (in any other programming language).
For example, given the string S = CAGCCTA and arrays P, Q such that:

  P[0] = 2  Q[0] = 4
  P[1] = 5  Q[1] = 5
  P[2] = 0  Q[2] = 6

the function should return the values [2, 4, 1], as explained above.


方法一:用 mapping 先記錄各字元最早出現的位置
Correctness:100%、Performance:100%
```python mapping = {"A":100001, "C":100001, "G":100001} def solutionByMapping(S, P, Q): length = len(S) matrix = [([0] * length) for i in range(len(mapping))] for i in range(length-1, -1, -1): mapping[S[i]] = i matrix[0][i] = mapping['A'] matrix[1][i] = mapping['C'] matrix[2][i] = mapping['G'] length = len(P) result = [0] * length for i in range(length): if matrix[0][P[i]] <= Q[i]: result[i] = 1 elif matrix[1][P[i]] <= Q[i]: result[i] = 2 elif matrix[2][P[i]] <= Q[i]: result[i] = 3 else: result[i] = 4 return result ```

方法二:使用 slice 概念的簡易方法(效能O(N*M)被扣分)
Correctness:100%、Performance:33%
```python def solutionBySlice(S, P, Q): result = [] length = len(P) for i in range(length): temp = (S[P[i]:Q[i]+1]) if "A" in temp: result.append(1) elif "C" in temp: result.append(2) elif "G" in temp: result.append(3) elif "T" in temp: result.append(4) return result ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 5 - Prefix Sums【MaxCounters】

Prefix Sums 練習題的第二題題目是【MaxCounters】
Calculate the values of counters after applying all alternating operations:
increase counter by 1; set value of all counters to current maximum.

方法一:按照規則用 loop 慢慢解
```python def solution(N, A): result = [0] * N minValue = 0 maxValue = 0 for number in A: index = number - 1 if(index == N): minValue = maxValue continue result[index] = max(result[index], minValue) + 1 maxValue = max(maxValue, result[index]) for i in range(N): result[i] = max(result[i], minValue) return result ```

完整練習題 source code 請參閱:github

2017年2月17日 星期五

【Python】Codility in Python : Lesson 5 - Prefix Sums【CountDiv】

Prefix Sums 練習題的第一題題目是【CountDiv】
Compute number of integers divisible by k in range [a..b].

方法一:使用 math.floor 的簡易方法
```python def solutionByFloor(A, B, K): return int((math.floor(B / K) - math.floor((A - 1) / K))) ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 4 - Counting Elements【MaxCounters】

Counting Elements 練習題的第四題題目是【MaxCounters】
Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

方法一:按照規則 loop 慢慢解
```python def solution(N, A): result = [0] * N minValue = 0 maxValue = 0 for number in A: index = number - 1 if(index == N): minValue = maxValue continue result[index] = max(result[index], minValue) + 1 maxValue = max(maxValue, result[index]) for i in range(N): result[i] = max(result[i], minValue) return result ```

完整練習題 source code 請參閱:github

2017年2月16日 星期四

【Python】Codility in Python : Lesson 4 - Counting Elements【FrogRiverOne】

Counting Elements 練習題的第三題題目是【FrogRiverOne】
Find the earliest time when a frog can jump to the other side of a river.

方法一:使用 set 的簡易方式
```python def solution(X, A): S = set() count = len(A) for i in range(0, count): S.add(A[i]) if(len(S) == X): return i return -1 ```

完整練習題 source code 請參閱:github

2017年2月15日 星期三

【Python】Codility in Python : Lesson 4 - Counting Elements【PermCheck】

Counting Elements 練習題的第二題題目是【PermCheck】
Check whether array A is a permutation.

方法一:使用 set 判斷長度是否一致的簡易方式
```python def solutionBySet(A): S = set(A) return 1 if max(S) == len(S) and len(S) == len(A) else 0; ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 4 - Counting Elements【MissingInteger】

Counting Elements 練習題的第一題題目是【MissingInteger】
Find the minimal positive integer not occurring in a given sequence.

方法一:使用 in set 判斷內容值的簡易方式
```python def solutionByInSet(A): result = 1 s = set(A) while result in s: result += 1 return result ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 3 - Time Complexity【TapeEquilibrium】

Time Complexity 練習題的第三題題目是【TapeEquilibrium】
Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|.

方法一:使用遞減後取最小值的簡易方式
```python def solution(A): total = sum(A) result = sys.maxsize for i in range(0, len(A)): total -= A[i] * 2 result = min(result, math.fabs(total)) return int(result) ```

完整練習題 source code 請參閱:github

2017年2月14日 星期二

【Python】Codility in Python : Lesson 3 - Time Complexity【PermMissingElem】

Time Complexity 練習題的第二題題目是【PermMissingElem】
Find the missing element in a given permutation.

方法一:使用 N+1 階三角範圍來取值
```python def solutionByScope(A): total = 0 scope = float((len(A) + 1)) * float((len(A) + 2)) / 2 for value in A: total += value return (int)(scope - total) ```

完整練習題 source code 請參閱:github

2017年2月13日 星期一

【Python】Codility in Python : Lesson 3 - Time Complexity【FrogJmp】

Time Complexity 練習題的第一題題目是【FrogJmp】
Count minimal number of jumps from position X to Y.

方法一:使用 math.ceil 的簡易方式
```python def solutionByCeil(X, Y, D): return int(math.ceil((Y - X) / float(D))) ```

方法二:使用餘數判斷回傳的結果
```python def solutionByMod(X, Y, D):   return (Y - X) / D if (Y - X) % D == 0 else ((Y - X) / D) + 1 ```

完整練習題 source code 請參閱:github

【UTF-8】解決 PHP 實作 HTML to Excel,在 ie11 檔名出現亂碼的問題

一般來說,在 PHP 中要把 HTML 中的 TABLE 轉為 EXCEL,
只要加上下列 header 描述,就能自訂匯出的檔案名稱
```php <?php header("Content-Disposition: attachment; filename=" . $fileName . ".xls;); ?> ```

但偏偏使用 ie11 時,就是會莫名其妙產生中文檔名變成亂碼的問題,
此時必須再加上下列設定,才能將亂碼恢復成正常的顯示
```php <?php header("Content-Disposition: attachment; filename=" . $fileName . ".xls; filename*=UTF-8''" . urlencode($fileName) . ".xls"); ?> ```

【Python】Codility in Python : Lesson 2 - Arrays【CyclicRotation】

Arrays 練習題的第二題題目是【OddOccurrencesInArray】
Task : Rotate an array to the right by a given number of steps.

方法一:使用 pop & insert 的簡易方式
```python def solutionByPop(A, K): if(K > 0 and len(A) > 1): for i in range(0, K): A.insert(0, A.pop()) return A ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 2 - Arrays【OddOccurrencesInArray】

Arrays 練習題的第一題題目是【OddOccurrencesInArray】
Task : Find value that occurs in odd number of elements.

方法一:使用 XOR 的簡易方式
```python def solutionByXOR(A): result = 0 for number in (A): result ^= number return result ```

方法二:使用 groupby 的簡易方式
```python def solutionByGroup(A): for k, v in groupby(sorted(A)): if(len(list(v)) == 1): return k return 0 ```

方法三:使用排序後兩兩比較的檢查方式
```python def solutionByLoop(A): if(len(A) == 1): return A[0] else: sortedList = sorted(A) count = len(sortedList) - 1 for i in range(0, count, 2): if sortedList[i] != sortedList[i+1]: return sortedList[i] return sortedList[count] ```

完整練習題 source code 請參閱:github

【Python】Codility in Python : Lesson 1 - Iterations【BinaryGap】

Iterations 練習題的第一題題目是【BinaryGap】
Task : Find longest sequence of zeros in binary representation of an integer.

方法一:使用 Regular Expression 的簡易方法
```python def solutionByRegex(N): return len(max(re.findall('(0*)1', bin(N)[2:]))) if N > 0 else 0 ```

方法二:使用 strip 和 split 的簡易方法
```python def solutionBySplit(N): return len(max(bin(N)[2:].strip('0').strip('1').split('1'))) ```

完整練習題 source code 請參閱:github