完成Python基础算法和数据结构练习。
Keep doubling
1 | def double_until_all_digits(n, giveup = 1000): |
Given a positive integer n , keep multiplying it by two until the current number contains each of the digits 0 to 9 at least once. Return the number of doublings that were necessary to reach this goal. If the number has been multiplied giveup times without reaching this goal, the function should give up and return -1.
| n | giveup | Expected result |
|---|---|---|
| 1 | 1000 | 68 |
| 1234567890 | 1000 | 0 |
| 555 | 10 | -1 |
Ignore each item after its k:th occurrence
1 | def remove_after_kth(items, k = 1): |
Given a list of items , some of which may be duplicated, create and return a new list that is otherwise the same as items , but only up to k occurrences of each element are kept, and all occurrences of that element after those first k are discarded.
Hint: loop through the items , maintaining a dictionary that remembers how many times you have already seen each element, updating this count as you go and appending each element to the result list only if its count is still less than or equal to k. Note also the counterintuitive but still completely legitimate edge case of k==0 that has a well defined answer of an empty list!
| items | k | Expected result |
|---|---|---|
| [42, 42, 42, 42, 42, 42, 42] | 3 | [42, 42, 42] |
| [‘tom’, 42, ‘bob’, ‘bob’, 99, ‘bob’, ‘tom’, ‘tom’, 99] | 2 | [‘tom’, 42, ‘bob’, ‘bob’, 99, ‘tom’, 99] |
| [1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1] | 1 | [1, 2, 3, 4, 5] |
| [1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5] | 3 | [1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 1, 5] |
| [42, 42, 42, 99, 99, 17] | 0 | [] |
First item that is preceded by k smaller items
1 | def first_preceded_by_smaller(items, k = 1): |
Given a list of items , find and return the value of the first element that has at least k preceding smaller elements in items , in the sense of the ordinary Python order comparison less than applied to these items. If there is no such element anywhere in items , this function should return None . Note that the k smaller items do not need to be consecutive immediate predecessors of the current item, but can be any k items from the initial prefix of the list before the current element.
| items | k | Expected result |
|---|---|---|
| [4, 4, 5, 6] | 2 | 5 |
| [42, 99, 16, 55, 7, 32, 17, 18, 73] | 3 | 18 |
| [42, 99, 16, 55, 7, 32, 17, 18, 73] | 8 | None |
| [‘bob’, ‘carol’, ‘tina’, ‘alex’, ‘jack’, ‘emmy’, ‘tammy’, ‘sam’, ‘ted’] | 4 | ‘tammy’ |
| [9, 8, 7, 6, 5, 4, 3, 2, 1, 10] | 1 | 10 |
| [42, 99, 17, 3, 12] | 2 | None |
Pull down your neighbours
1 | def eliminate_neighbours(items): |
Given the sequence of integer items that are guaranteed to be some permutation of positive integers from 1 to n where n is the length of the list, consider the following operation: Find the smallest number from those that still remain in the list, and remove that number and the larger of its current immediate neighbours from the list. The function should keep doing this repeatedly until the largest number in the original list gets eliminated, and return the number of removal operations that were needed to achieve this goal.
For example, given the list [5, 2, 1, 4, 6, 3] , the operation would remove element 1 and its current larger neighbour 4 , resulting in the list [5, 2, 6, 3] . Applied again, the same operation would now remove 2 and its current larger neighbour 6 , thus reaching the goal in two steps.
| items | Expected result |
|---|---|
| [1, 6, 4, 2, 5, 3] | 1 |
| [8, 3, 4, 1, 7, 2, 6, 5] | 3 |
| [8, 5, 3, 1, 7, 2, 6, 4] | 4 |
| [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] | 5 |
| range(1, 10001) | 5000 |
| [1000] + list(range(1, 1000)) | 1 |
The bottleneck of the running time is computing the new list that results from removing two elements from it. Try to think up some way to solve this problem that alleviates this expensive operation.
What do you hear, what do you say?
1 | def count_and_say(digits): |
Given a string of digits that is guaranteed to contain only digit characters from ‘0123456789’ , read that string “out loud” by saying how many times each digit occurs consecutively in the current bunch of digits, and then return the string of digits that you just said out loud. For example, given the digits ‘222274444499966’ , we would read it out loud as “four twos, one seven, five fours, three nines, two sixes” for the result string ‘4217543926’ .
| digits | Expected result |
|---|---|
| ‘333388822211177’ | ‘4338323127’ |
| ‘11221122’ | ‘21222122’ |
| ‘123456789’ | ‘111213141516171819’ |
| ‘777777777777777’ | ‘157’ |
| ‘’ | ‘’ |
| ‘1’ | ‘11’ |
(This particular operation, when executed on a list of items instead of a string, is usually called “run-length encoding”. When executed on a string of numerical digits, it also has the following cute little puzzle associated with it. Given the empty string, this function returns an empty string, and given the string ‘22’ that contains two twos, this function returns the same string ‘22’. Are there any other strings of digits for which this function returns the exact same string as it was given? Either find another such digit string, or prove that no such digit string can exist.)
Bishops on a binge
1 | def safe_squares_bishops(n, bishops): |
On a generalized n-by-n chessboard, there are some number of bishops , each bishop represented as a tuple (row, column) of the row and the column of the square that contains that bishop. (The rows and columns are numbered from 0 to n - 1.) A chess bishop covers all squares that are on the same diagonal with that bishop arbitrarily far into any of the four diagonal compass directions. Given the board size n and the list of bishops on that board, count the number of empty squares that are safe, that is, are not covered by any bishop.
To quickly check whether two squares (r1, c1) and (r2, c2) are in some diagonal with each other, you can use the test abs(r1-r2) == abs(c1-c2) to determine whether the horizontal distance of those squares equals their vertical distance, which is both necessary and sufficient for those squares to lie on the same diagonal. This way you don’t need to write the logic separately for each of the four diagonal directions, but one test handles all four diagonals in one swoop.
| n | bishops | Expected result |
|---|---|---|
| 10 | [] | 100 |
| 4 | [(2, 3), (0, 1)] | 11 |
| 8 | [(1, 1), (3, 5), (7, 0), (7, 6)] | 29 |
| 2 | [(1, 1)] | 2 |
| 6 | [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)] | 18 |
| 100 | [(row, (row*row) % 100) for row in range(100)] | 6666 |
Up for the count
1 | def counting_series(n): |
The counting series “1234567891011121314151617181920212223” … is an infinitely long string of digits 0-9 that consists of the positive integers written in ascending order without any separators between the individual numbers. This function should return the integer digit that is in the position n of the counting series, with positions starting from 0 as usual in computing.
Of course, the automated tester will again try out values of n large enough that anybody trying to solve this problem by constructing the counting series as an explicit string would run out of time and space long before receiving the answer. Instead, you should observe that the structure of this infinite sequence is quite straightforward, as it starts with 9 single-digit numbers, followed by 90 two-digit numbers, followed by 900 three-digit numbers, and so on. This regular and predictable structure allows you to skip prefixes of this series in exponentially widening leaps and bounds, until you reach the position n and find out the digit that is waiting for you there.
| n | Expected result |
|---|---|
| 0 | 1 |
| 100 | 5 |
| 10000 | 7 |
| 10**100 | 6 |
Out of curiosity, has the digit that is waiting for you in position n been there waiting for you eternally since the dawn of time? Or did it come to existence the moment that somebody first posed this problem, or only when somebody solved this problem up to the position n ? What is your intuitive stance on this thorny and ancient philosophical issue high above this author’s pay grade?
Do all mathematical structures and the answers to all possible questions about these structures already exist in the static and timeless Platonic plane of perfect forms for us to discover by means of reason? Or are at least some mathematical truths created by social agreement so that the nature of their existence is similar to that of fictional characters such as Donald Duck and James Bond, brought into existence by the conscious choices of their creators?
Revorse the vewels
1 | def reverse_vowels(text): |
Given a text string, create and return a new string constructed by finding all its vowels (for simplicity, in this problem vowels are the letters found in the string ‘aeiouAEIOU’ ) and reversing their order, while keeping all other characters exactly as they were in their original positions. However, to make the result look prettier, the capitalization of each moved vowel must be the same as that of the vowel that was originally in the target position. For example, reversing the vowels of ‘Ilkka’ should produce ‘Alkki’ instead of ‘alkkI’ .
Along with many possible other ways, one straightforward way to compute this vowel reversal starts with collecting all vowels of text into a separate list, and initializing the result to an empty string.. After that, iterate through all positions of the original text . Whenever the current position contains a vowel, take one from the end of the list of the vowels. Convert that vowel to either upper- or lowercase depending on the case of the vowel that was originally in that position, and append it to result . Otherwise, append the character from the same position of the original text to the result as it were.
| text | Expected result |
|---|---|
| ‘Revorse the vewels’ | ‘Reverse the vowels’ |
| ‘Ilkka Markus Kokkarinen’ | ‘Elkki Markos Kukkaranin’ |
| ‘Hello world’ | ‘Hollo werld’ |
| ‘abcdefghijklmnopqrstuvwxyz’ | ‘ubcdofghijklmnepqrstavwxyz’ |
| ‘This is Computer Science I!’ | ‘This es Cempiter Scuonci I!’ |
Everybody do the Scrooge Shuffle
1 | def spread_the_coins(piles, left, right): |
Identical coins have been placed on the integer number line so that the position i initially contains piles[i] coins for positions i that are inside piles , that is, 0 <= i < len(piles) . All other positions on the integer line both ways towards the positive and negative infinity initially contain zero coins. After this, any position that contains at least left + right coins is unstable . As long as some position i is unstable, exactly left coins from position i spill into the predecessor position i-1 , and exactly right coins spill into the successor position i+1 .
It turns out that the stable end state of this back-and-forth dance is always unique, and will be reached after a finite number of steps regardless of the order in which the unstable positions are processed. This function should compute and return this stable terminal position as a two-tuple (start, coins) where start is the leftmost position index that ends up with at least one coin spill into it (the first initial pile is located at position zero). The list of coins indicates how many coins end up in each position, spanning the positions from start up to whatever position ends up being the highest non-empty position. (Whenever some pile contains k (left + right) coins for some positive integer k ] 0 , you can scoop k left coins into the predecessor pile and k * right coins into the successor pile in a single move to speed up the convergence.)
The brand new difficulty of this problem in this collection is handling the negative positions during computation, and quickly finding some unstable position to process. Yes, Kemosabe, Python lists can indeed be prepended from front, but that operation can get inefficient as it has to make room for the new element with a linear time reorganization. However, ordinary lists are basically special cases of dictionaries with indices restricted to natural numbers…
| piles | left | right | Expected result |
|---|---|---|---|
| [20] | 3 | 2 | (-4, [3, 1, 4, 2, 4, 2, 4]) |
| [8, 4] | 3 | 2 | (-2, [3, 1, 3, 3, 2]) |
| [111, 12, 12] | 19 | 6 | (-6, [19, 13, 13, 13, 13, 13, 10, 23, 18]) |
Calkin-Wilf sequence
1 | def calkin_wilf(n) |
The nodes of the Calkin-Wilf tree , when read in level order so that the elements in each level are read from left to right, produce the linear sequence of all possible positive integer fractions . Almost as if by magic, this construction guarantees every positive integer fraction to appear exactly once in this sequence. Even more wonderfully, each fraction is guaranteed to appear in its simplest reduced form! To perform the following calculations, you should import the handy data types Fraction and deque from the standard library modules fractions and collections .
Your function should return the n :th element of this sequence. First, create a new instance of deque and append the first fraction 1/1 to “prime the pump”, so to speak, to initiate the production of the values of this sequence. Then repeat the following procedure n times. Pop the fraction currently in front of the queue using the deque method popleft , extract its numerator and denominator p and q , and push the two new fractions p / (p + q) and (p + q) / q to the back of the queue. Return the fraction object that was popped in the final round.
| n | Expected result |
|---|---|
| 10 | 3/5 |
| 1000 | 11/39 |
| 100000 | 127/713 |
(Actually, once you reach n//2+1 , you could stop pushing in any new values and save some significant memory. At that point the queue already contains the entire result you need…