Bright's Blog

前言

准备开始刷Leetcode的时候就有听说剑指offer系列是个不错的入门，涵盖各种题型算法和数据结构。

所以这里开个坑，打算放剑指offer系列的解题，希望总结的同时也能帮助到大家！

Description

Difficulty: Medium

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

1 2 3

Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

1 2 3

Input: text1 = "abc", text2 = "abc" >Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

1 2 3

Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Description

Code Jam to I/O for Woman 2014 (2) Zathras (16 pts, 24 pts)

Problem (Simplified)

It is year 2025 on planet Zathras — a world populated exclusively by semi-sentient robots called Zathrinians. There are two kinds of Zathrinians: acrobots and bouncoids. Once a year, the Great Mind makes its Great Decision for that year, and chooses how the Zathrinians will reproduce and be decommissioned. When it’s making the Great Decision, it takes into account two Eternal Parameters: α and β. These parameters, being Eternal, do not change from year to year.

Reproduction: If there are A acrobots and B bouncoids when the Great Mind makes the Great Decision, the Great Mind will create K = min(A, B) reproductive pairs by pairing together an acrobot and a bouncoid. Any remaining robots will be unpaired. The next day, 2% of those K couples (rounded down) will produce one baby Zathrinian each.

Out of all the baby Zathrinians produced, α% (rounded down) are acrobots, and β% (rounded down) are bouncoids. The remaining baby Zathrinians are split evenly between acrobots and bouncoids; if there’s an odd number, the extra baby becomes a bouncoid.

Decommissioning: When the Great Mind makes its Great Decision, 1% of acrobots (rounded down) and 1% of bouncoids (rounded down) are marked for decommissioning. Two days later, they will all be disassembled. Note that the 1% figure is calculated on the day of the Great Decision, before the new Zathrinians are born.

After the Great Decision has been made (day 1), the reproduction has occurred (day 2), and the unlucky Zathrinians have been disassembled (day 3), the entire world continues to function in harmony until next year’s Great Decision takes place at the time scheduled in the Eternal Specification.

Example

If we start with a population of 12345 acrobots and 12890 bouncoids, 123 acrobots and 128 bouncoids will be marked for decommissioning. The number of couples will be min(12345, 12890), which is 12345. This means that 246 offspring will be created that year. Let’s say that α=10 and β=13, so more bouncoids than Zathrinians are created each year. This means that 24 offspring will be acrobots (10% of 246, rounded down); 31 will be bouncoids (13% of 246, rounded down); and the remaining 191 will be split between 95 more acrobots and 96 more bouncoids.

Overall, we started with 12345 acrobots and 12890 bouncoids. One day later, there will be 12464 acrobots and 13017 bouncoids. The next day, there will be 12341 acrobots and 12889 bouncoids. 99 years later, there will be 11993 acrobots and 12676 bouncoids. After a total of 5049 years, we will be down to only 3099 acrobots and 3199 bouncoids — a huge drop in total population size. After that, the populations will remain the same forever.

Given the values of A, B, α, β, and Y, can you compute the acrobot and bouncoid population sizes at the end of Y years?

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains 5 integers: A, B, α, β, and Y.

Output

For each test case, output one line containing “Case #x: AY BY”, where x is the test case number (starting from 1) and (AY, BY) are the populations of acrobots and bouncoids after Y years, respectively.

Description

Code Jam to I/O for Woman 2014 (1) Saturnalia (15 pts)

Problem (Simplified)

Caterina needs a computer program that reads a message and outputs it back, decorated with a box.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains a text message.

Output

For each test case, output four lines. The first one should contain “Case #x:”, where x is the test case number (starting from 1). The next 3 lines should contain the original message surrounded by a box of ‘+’, ‘-‘, and ‘|’ characters, with a space character added on each side of the message. See examples below for the exact formatting requirements. Pay special attention to the spaces.

Sample

Input:

1 2 3 4 5 6

5 Merry Saturnalia, Giovanni! Equus, you're the best! >Caballus, you try really hard! >w

Output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Case #1: +-----------------------------+ >| Merry Saturnalia, Giovanni! | +-----------------------------+ >Case #2: +-------------------------+ | Equus, you're the best! | +-------------------------+ Case #3: +--------------------------------+ | Caballus, you try really hard! | >+--------------------------------+ Case #4: >+-----+ | | +-----+ Case #5: +---+ | w | +---+

Description

Code Jam to I/O for Woman 2014 (3) Seating Chart (17 pts, 28 pts)

Problem (Simplified)

There are K round tables at the dinner, numbered 1 through K. It is important to have exactly the same number of people sitting at each table. If that is impossible (N is not divisible by K), then the table with the most people must have at most one more person sitting at it than the table with the fewest people.

Each of the N people will be assigned a unique number between 0 and N - 1. What matters is who is sitting next to whom, and not exactly where they’re sitting. In other words, two arrangements, A and B, are considered different if there exists a pair of numbers, α and β, such that persons α and β are sitting next to each other at the same table in arrangement A, but they are not sitting next to each other in arrangement B.

For example, if N is 5, and K is 2, we must have 3 people seated at one of the tables, and 2 people seated at the other table. Here is the list of all 10 of the possible arrangements:

1 2 3 4 5 6 7 8 9 10

[[0, 1, 2], [3, 4]] [[0, 1, 3], [2, 4]] [[0, 1, 4], [2, 3]] [[0, 2, 3], [1, 4]] [[0, 2, 4], [1, 3]] [[0, 3, 4], [1, 2]] [[1, 2, 3], [0, 4]] [[1, 2, 4], [0, 3]] [[1, 3, 4], [0, 2]] [[2, 3, 4], [0, 1]]

All other arrangements are similar to one of the arrangements above and are not counted as different. In particular, all of the following arrangements are considered to be the same:

1 2 3 4 5

[[0, 1, 2], [3, 4]] [[2, 0, 1], [3, 4]] [[1, 2, 0], [4, 3]] [[0, 2, 1], [3, 4]] [[3, 4], [0, 2, 1]]

This is because the following pairs of people (and no other pairs) are sitting next to each other in each of these 5 arrangements:

1 2 3 4

0 and 1 0 and 2 1 and 2 3 and 4

Another example is N = 5 and K = 3, which requires having two tables with two people each, and one table with a single person sitting at it. There are 15 possible arrangements in this case:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

[[0, 1], [2, 3], [4]] [[0, 1], [2, 4], [3]] [[0, 1], [3, 4], [2]] [[0, 2], [1, 3], [4]] [[0, 2], [1, 4], [3]] [[0, 2], [3, 4], [1]] [[0, 3], [1, 2], [4]] [[0, 3], [1, 4], [2]] [[0, 3], [2, 4], [1]] [[0, 4], [1, 2], [3]] [[0, 4], [1, 3], [2]] [[0, 4], [2, 3], [1]] [[1, 2], [3, 4], [0]] [[1, 3], [2, 4], [0]] [[1, 4], [2, 3], [0]]

In this final example, N = 5 and K = 1, which means that we only have a single table, seating all 5 guests. Here, the answer is 12:

1 2 3 4 5 6 7 8 9 10 11 12

[[0, 1, 2, 3, 4]] [[0, 1, 2, 4, 3]] [[0, 1, 3, 2, 4]] [[0, 1, 3, 4, 2]] [[0, 1, 4, 2, 3]] [[0, 1, 4, 3, 2]] [[0, 2, 1, 3, 4]] [[0, 2, 1, 4, 3]] [[0, 2, 3, 1, 4]] [[0, 2, 4, 1, 3]] [[0, 3, 1, 2, 4]] [[0, 3, 2, 1, 4]]

Input

The first line of the input gives the number of test cases, T. T lines, each one containing two integers, N and K.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the number of different possible seating arrangements.

Description

Difficulty: Medium

You’re given a two-dimensional array (a matrix) of potentially unequal height and width containing only 0s and 1s. Each 0 represents land and each 1 represents part of a river. A river consists of any number of 1s that are either horizontally or vertically adjacent (but not diagonally adjacent). The number of adjacent 1s forming a river determine its size.

Note that a river can twist. In other words, it doesn’t have to be a straight vertical line or a straight horizontal line; it can be L-shaped, for example.

Write a function that returns an array of the sizes of all rivers represented in the input matrix. The sizes don’t need to be in any particular order.

Example:

1 2 3 4 5 6 7 8

matrix: [ [1,0,0,1,0], [1,0,1,0,0], [0,0,1,0,1], [1,0,1,0,1], [1,0,1,1,0], ] output = [1,2,2,2,5]

Description

Difficulty: Medium

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

1 2 3

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

1 2	Input: height = [1,1] Output: 1

Example 3:

1 2	Input: height = [4,3,2,1,4] Output: 16

Example 4:

1 2	Input: height = [1,2,1] Output: 2

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Description

Difficulty: Medium

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

1 2	Input: [1,2,3,4] Output: [24,12,8,6]

Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)