完成Python基础算法和数据结构练习。
Whenever they zig, you gotta zag
def is_zigzag(n):
—|—
Let us define that a positive integer n is a zigzag number (also called
“alternating number” in some material on combinatorics) if the series of
differences between its consecutive digits strictly alternates between
positive and negative steps. The step from the first digit to the second may
be either positive or negative. The function should determine whether its
parameter n is a zigzag number and answer with a simple truth value.
In the negative examples in the table below, the part of the number that
violates the zigzag property is highlighted in red.
| n | Expected result |
|---|---|
| 7 | True |
| 25391 | True |
| 90817263545463728185 | True |
| 16329 | False |
| 104175101096715 | False |
| 49573912009 | False |
Crack the crag
def crag_score(dice):
—|—
Crag (see the Wikipedia page for the rules and the scoring table needed in
this problem) is a dice game similar in style and spirit to (but much simpler
than) the more popular games of Yahtzee and Poker dice . Players repeatedly
roll three dice and assign the resulting patterns to scoring categories so
that once some roll has been assigned to a category, that category is
considered to have been spent and cannot be used again for any future roll.
These choices give this game a little bit more tactical flair on top of merely
rolling of these dice.
Given the list of pips of the three dice of the first roll, this function
should compute and return the highest possible score available when all
categories of the scoring table are still available for you to choose from ,
and all that matters is maximizing the score for this first roll. Note that
the examples on the Wikipedia page show the score that some dice would score
in that particular category , which is not necessarily even close to the
maximum score in principle attainable with that roll. For example, [1, 1, 1]
used in the category “Ones” would indeed score only three points in that
category, whereas that same roll would score a whopping 25 points in the
category “Three of a kind”. (The later problem “Optimal crag score” near the
end of this collection makes you recursively assign multiple rolls into
distinct categories to maximize the total score.)
This problem ought to be a straightforward exercise in if-else ladders
combined with simple sequence management. Your function should be swift and
sure to return the correct answer for every one of the 6 3 = 216 possible
argument value combinations. However, surely you will design your if-else
structures to handle entire equivalence classes of cases together in one step,
so that your entire ladder consists of far fewer than 216 separate steps…
| dice | Expected result |
|---|---|
| [1, 2, 3] | 20 |
| [4, 5, 1] | 5 |
| [3, 3, 3] | 25 |
| [4, 5, 4] | 50 |
| [1, 1, 1] | 25 |
| [1, 1, 2] | 2 |
Three summers ago
def three_summers(items, goal):
—|—
Given a list of positive integer items guaranteed to contain at least three
elements with all of its elements in sorted ascending order , determine
whether there exist exactly three separate items that together add up exactly
to the given positive integer goal .
You could, of course, solve this problem with three nested loops to go through
all possible ways to choose three elements from items , checking for each
triple whether it adds up to the goal . However, this approach would get
rather slow as the number of elements in the list increases, and of course the
automated tester used to grade this function will make those lists larger just
to make such solutions reveal themselves with their excessive consumption of
running time.
Since items are known to be sorted, better technique will find the answer
significantly faster. See the new example function two_summers in
listproblems.py that demonstrates how to quickly determine whether the sorted
list contains two elements that add up to the given goal . You can simply use
this function as a subroutine to speed up your search for three summing
elements, once you realize that the list contains three elements that add up
to goal if and only if it contains some element x so that the remaining list
contains two elements that add up to goal-x .
| items | goal | Expected result |
|---|---|---|
| [10, 11, 16, 18, 19] | 40 | True |
| [10, 11, 16, 18, 19] | 41 | False |
| [1, 2, 3] | 6 | True |
| (For the general subset sum problem used in later lectures as a recursion | ||
| example, the question of whether the given list of integers contains some | ||
| subset of k elements that together add up to given goal can be determined by | ||
| trying each element x in turn as the first element of this subset, and then | ||
| recursively determining whether the remaining elements after x contain some | ||
| subset of k - 1 elements that adds up to goal-x .) |
Count distinct sums and products
def count_distinct_sums_and_products(items):
—|—
Given a list of distinct integers guaranteed to be in sorted ascending order,
count how many different numbers can be constructed by either adding or
multiplying two numbers from this list. (The two chosen numbers do not need to
be distinct.) For example, given the list [2, 3, 4] , this function would
return 8, since there exist a total of eight distinct numbers that can be
constructed this way from 2, 3 and 4. Some of them can be constructed in
several different ways, such as 6 that is either 4 + 2 = 3 + 3 = 3 * 2, but
the number 6 should still be counted only once in the total tally.
This problem can be solved by simply looping through all possible ways to
choose a and b from the given list. Maintain a set that remembers all sums a+b
and products a*b that you have seen so far, and after having iterated through
all possible such pairs, return the final size of that set.
| items | Expected result |
|---|---|
| [] | 0 |
| [42] | 2 |
| [2, 3, 5, 7, 9, 11] | 29 |
| [x for x in range(1, 101)] | 2927 |
| [x*x for x in range(1, 101)] | 6533 |
| (This problem was inspired by the article “ How a Strange Grid Reveals Hidden | |
| Connections Between Simple Numbers “ in Quanta Magazine . ) |
Sum of two squares
def sum_of_two_squares(n):
—|—
Some positive integers can be expressed as a sum of two integers that each are
squares of some positive integer greater than zero. For example, 74 = 49 + 25 = 7^2 + 5^2 . This function should find and return a tuple of two
positive integers greater than zero whose squares together add up to n , or
return None if the parameter n cannot be broken into a sum of two squares.
To facilitate the automated testing, the returned tuple must give the larger
of its two numbers first. Furthermore, if some integer can be broken down to a
sum of squares in several different ways, return the way that maximizes the
larger number. For example, the number 85 allows two such representations 7^2 + 6^2 and 9^2 + 2^2 , of which this function must therefore return
(9, 2) .
The technique of two approaching indices that start from the beginning and end
of a sequence, respectively, and approach each other until they meet
somewhere, used in the function two_summers in one of our class examples, is
directly applicable to this problem. In this problem, these indices crawl
towards each other only one step at the time, whereas in binary search , one
index would jump halfway towards the other one in every round…
| n | Expected result |
|---|---|
| 1 | None |
| 2 | (1, 1) |
| 50 | (7, 1) |
| 8 | (2, 2) |
| 11 | None |
Carry on Pythonista
def count_carries(a, b):
—|—
Two positive integers a and b can be added together to produce their sum with
the usual integer column-wise addition algorithm that we all learned back when
we were but wee little children. Instead of the sum a+b that the language
could compute for you anyway, this problem asks you to count how many times
there is a carry of one into the next column caused by adding the two digits
in the current column (possibly including the carry from the previous column),
and return that total count. Your function should be efficient even when the
parameter integers a and b are enormous enough to require thousands of digits
to write down.
Hint: to extract the lowest digit of a positive integer n , use the expressionn % 10 . To extract all other digits except the lowest one, use the
expression n // 10 . You can use these simple integer arithmetic
operations to execute the steps of the column-wise integer addition so that
you don’t care about the actual result of the addition, but only the carry
that is produced in each column.
| a | b | Expected result |
|---|---|---|
| 99999 | 1 | 5 |
| 11111111111 | 2222222222 | 0 |
| 123456789 | 987654321 | 9 |
Count word dominators
def count_word_dominators(words):
—|—
If you already solved the earlier count_dominators problem, you might
notice that even though the problem was originally stated for lists of
integers, the logic of domination did not depend on this fact in any way. As
long as the individual elements can be compared with each other for order, the
Pythonic spirit of duck typing allows the very same count_dominators
function to handle a list of strings just as well as it handles a list of
integers! For example, the function call count_dominators(['dog', 'emu', 'cat', 'bee']) would return 3, since ‘emu’ , ‘cat’ and ‘bee’ dominate all
words after them in the lexicographical ordering. If your count_dominators
does not pass this hurdle, go back and edit it to have no baked-in assumptions
about elements being specifically integers.
However, things become more interesting if we define domination between words
of equal length with a rule that says that for a word to dominate another
word, for more than half of the positions the character in the first word is
strictly greater than the corresponding character in the other word. This
definition makes the domination a partial ordering so that, for example, the
word ‘dog’ dominates the word ‘cat’ , but neither word ‘dog’ and ‘arg’
dominates the other. Note also the intentional wording “ more than half” to
break ties between words of even length such as ‘aero’ and ‘tram’ , so that no
two words can possibly both dominate each other.
| words | Expected result |
|---|---|
| [‘sky’, ‘yat’] | 2 |
| [‘pun’, ‘ean’, ‘fiz’, ‘coe’] | 3 |
| [‘toph’, ‘prow’, ‘koku’, ‘okey’] | 2 |
| [‘ufo’, ‘hny’, ‘hun’, ‘ess’, ‘kab’] | 3 |
Duplicate digit bonus
def duplicate_digit_bonus(n):
—|—
Some people like to ascribe deep significance to numerical coincidences so
that consecutive repeated digits, such as a digital clock blinking 11:11 ,
seem special and personal to them. Such people then naturally find numbers
with repeated digits to be more valuable and important than all the ordinary
and pedestrian numbers without any obvious pattern. For example, getting into
a taxicab flashing an exciting number such as 1234 or 3333 would be far more
instagrammable than a more pedestrian taxicab adorned with some dull number
such as 1729.
Assume that some such person assign a meaningfulness score to every positive
integer so that every maximal block of k consecutive digits with k > 1
scores 10**(k-2) points for that block. A block of two digits scores one
point, three digits score ten points, four digits score a hundred points, and
so on. However, just to make this more interesting, there is also a special
rule in effect that if this block of digits is at the lowest end of the
number, that block scores twice as many points as it would in any other
position. Given a positive integer n > 0 , this function should compute
and return its meaningfulness score as the sum of its individual block scores.
| n | Expected result |
|---|---|
| 43333 | 200 |
| 2223 | 10 |
| 777777777 | 20000000 |
| 3888882277777731 | 11001 |
| 2111111747111117777700 | 12002 |
| 9999997777774444488872222 | 21210 |
Nearest smaller element
def nearest_smaller(items):
—|—
Given a list of integer items , create and return a new list of the exact same
length so that each element is replaced with the nearest element in the
original list whose value is smaller. If no smaller elements exist, the
element in the result list should simply remain as it were in the original
list. If there exist smaller elements to both directions that are equidistant
from that element, you should resolve this by using the smaller of these two
elements, again to make the expected results unique and this problem suited in
the automated testing framework.
| items | Expected result |
|---|---|
| [42, 42, 42] | [42, 42, 42] |
| [42, 1, 17] | [1, 1, 1] |
| [42, 17, 1] | [17, 1, 1] |
| [6, 9, 3, 2] | [3, 3, 2, 2] |
Interesting, intersecting
def squares_intersect(s1, s2):
—|—
A square on the two-dimensional plane can be defined as a tuple (x, y, r)
where (x, y) are the coordinates of its bottom left corner and r is the length
of the side of the square. Given two squares as tuples (x1, y1, r1) and (x2,
y2, r2) , this function should determine whether these two squares intersect ,
that is, their areas have at least one point in common, even if that one point
is merely the shared corner point when these two squares are placed kitty
corner. This function should not contain any loops or list comprehensions of
any kind , but should compute the result using only integer comparisons and
conditional statements.
This problem showcases an idea that comes up with some problems of this
nature; that it is actually easier to determine that the two squares do not
intersect, and then just negate that answer. Two squares do not intersect if
one of them ends in the horizontal direction before the other one begins, or
if the same thing happens in the vertical direction. (This technique
generalizes from rectangles lying on the flat two-dimensional plane to not
only three-dimensional cuboids, but to hyperboxes of arbitrary high
dimensions.)
| s1 | s2 | Expected result |
|---|---|---|
| (2, 2, 3) | (5, 5, 2) | True |
| (3, 6, 1) | (8, 3, 5) | False |
| (8, 3, 3) | (9, 6, 8) | True |
| (5, 4, 8) | (3, 5, 5) | True |
| (10, 6, 2) | (3, 10, 7) | False |
| (3000, 6000, 1000) | (8000, 3000, 5000) | False |
