【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

【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

【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

【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

【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

【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