完成Python基础算法和数据结构练习。

## Whenever they zig, you gotta zag

1 | 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

1 | 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

1 | 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

1 | 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

1 | 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

1 | 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 expression `n % 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

1 | 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

1 | 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

1 | 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

1 | 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 |