————菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜分割线————

昨天在 HackerRank 上刷了四道题，其实前三道花了不到一个小时，最后一道真是炸裂我的菊花，10 个 Test Case 尽力优化后也才过了 8 个，不停的超时，如果在四十五分钟之内做出的解法估计我只能过两个 Test Case，手动微笑。真是菜的抠脚。这篇博客写的差不多的时候又继续去优化了一番才把所有的 Test Case 都过了……

下面记录一下这奇葩的几题，真是和 LeetCode 截然不同的风格。

————菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜菜分割线————

Encircular

原题：

————————————————————————————————————

Determine whether a sequence of commands will restrict the robot’s movements within a circle.

You are working on a computer simulation of a mobile robot. The robot moves on an infinite plane, starting from position (0, 0). Its movements are described by a command string consisting of one or more of the following three letters:

• G instructs the robot to move forward one step
• L instructs the robot to turn left.
• R instructs the robot to turn right.

The robot performs the instructions in a command and repeats them for an infinite time. You want to know whether or not there exists some circle whose radius is a positive real number such that the robot always moves within the circle and never leaves it.

Complete the doesCircleExist function in the editor below. It has one parameter: an array of strings, commands. The function must return an array of n strings where each element i denotes whether or not performing commands i on an infinite loop will restrict the robot’s movements to a circle. If the instruction restricts the robot’s movement to a circle, set index i to “YES”; otherwise, set it to “NO”.

————————————————————————————————————

大意就是有三种操作，前进（在当前向量上加上方向向量 距离 1），左转，右转（左右转都是在修改当前的方向向量），然后给你一个命令串，例如 GLGLGLGR ，这个命令串会无限循环重复，问最终会不会形成一个闭合的图形。没错，不用想的太复杂，就是问你最终会不会形成一个闭合的图形，因为每一段命令是一样的，而方向只有四种，所以也就是说，*如果在四步操作结束的时候没有回到原点，它就再也回不来了，也不可能成为一个 限定范围 内运动的轨迹了。

这一点非常重要 = = 不然画了半天轨迹找了半天规律也看不出个所以然，总是去想 可能发生 的 Corner case。然而就这么简单。至于方向向量，或者用不用向量来计算移动都可以由你决定，我顺便温习了一下向量旋转的矩阵乘法，手动微笑。

代码如下：

def turnRight(directionVector):
    x = directionVector[1] * 1
    y = directionVector[0] * - 1
    return (x,y)

def turnLeft(directionVector):
    x = directionVector[1] * -1
    y = directionVector[0] * 1
    return (x,y)

def fuck(commands):
    r = list()
    for command in commands:
        direction_vector = (0,1)
        current_point = (0,0)

        for i in range(0,4,1):
            for item in command:
                for c in item:
                    if c == "G":
                        current_point = (current_point[0] + direction_vector[0], current_point[1] + direction_vector[1],)
                    elif c == "R":
                        direction_vector = turnRight(direction_vector)
                    elif c == "L":
                        direction_vector = turnLeft(direction_vector)

        if current_point[0] == 0 and current_point[1] == 0:
            r.append(True)
        else:
            r.append(False)
    return r

Elements in Tree

————————————————————————————————————

You are provided a binary search tree with integers. Each node has three primary members: an Integer (which it holds), a pointer to its left child, and a pointer to its right child. A function stub is provided in multiple languages. You need to complete so this function so that it will search for the presence of a specified integer in this tree. If the element (val) is found, return 1. Otherwise return 0.

Each function stub will have its prototype, and an explanation of the data types or classes involved. The section of the program which parses the input and displays the output is complete in each language and will not need to be modified. Your task is to complete the body of the function provided so it returns the correct output.

————————————————————————————————————

简单的树查找。代码：

def isPresent(root,val):
    if root.value == val:
        return 1
    else:
        flag = 0
        if root.left is not None:
            if isPresent(root.left,val):
                flag = 1

        if root.right is not None:
            if isPresent(root.right,val):
                flag = 1

        return flag

Spiral Matrix

————————————————————————————————————

Example:

1,2,3
4,5,6
7,8,9

should be printed as 1,2,3,6,9,8,7,4,5

Input:

You will read input from STDIN and print output to STDOUT.

The first line of input consists of 2 numbers, separated by a comma. The first number denotes the number of rows in the matrix, while the second number specifies the number of columns (the matrix doesn’t have to be square).

The remaining lines specify the actual values inside of the matrix. Each line represents a row, the values inside a separated by commas.

Output:

All values from the matrix in the spiral order (clockwise, starting from top left), separated by commas.

————————————————————————————————————

这也没什么好说的。简单的移动当前输出的 x,y 指针然后遍历二维数组即可，在指针转弯的时候维护一下当前的边界。代码：

k = raw_input().split(",")
row_num = int(k[0])
column_num = int(k[1])
g = list()
output = ""

for i in range(0,row_num):
    t = raw_input().split(",")
    g.append(t)

left = row_num * column_num
pointer_x = pointer_y = 0

left_x = top_y = 0
right_x = column_num - 1
bottom_y = row_num - 1

direction = 1
while left > 0 :
    if left == 1:
        output += str(g[pointer_y][pointer_x])
    else:
        output += str(g[pointer_y][pointer_x]) + ","

    if direction == 1:
        if pointer_x == right_x:
            pointer_y += 1
            direction = 2
            top_y = pointer_y
        else:
            pointer_x += 1

    elif direction == 2:
        if pointer_y == bottom_y:
            pointer_x -= 1
            direction = 3
            right_x = pointer_x
        else:
            pointer_y += 1
    elif direction == 3:
        if pointer_x == left_x:
            pointer_y -= 1
            direction = 4
            bottom_y = pointer_y
        else:
            pointer_x -= 1
    else:
        if pointer_y == top_y:
            pointer_x += 1
            direction = 1
            left_x = pointer_x
        else:
            pointer_y -= 1

    left = left - 1

print output

Lego Block

————————————————————————————————————

You have 4 types of Lego™ blocks, of sizes (1 x 1 x 1), (1 x 1 x 2), (1 x 1 x 3), and (1 x 1 x 4). Assume that you have an infinite number of blocks of each type. For brevity, we can call these types, respectively, the 1-block, 2-block, 3-block and 4-block, or even (1), (2), (3) and (4).

Using these blocks, you want to make a wall of height *N* and width *M*. The wall should be a solid continuous structure with no holes. The wall should be structurally connected, so no straight vertical should exist that would allow the wall to be separated in two without cutting one or more bricks.

Input:
The first line contains the number of test cases *T*. *T* test cases follow. Each case contains two integers, *N* and *M*.

Output:
Output *T* lines, one for each test case, containing the number of ways to build the wall.
As the numbers can be very large, output the result modulo 1,000,000,007.

Constraints:
1 ≤ T ≤ 100
1 ≤ N,M ≤ 1000

Sample Input:
4
2 2
3 2
2 3
4 4

Sample Output:
3
7
9
3375

Explanation:

• For the first case, the 3 ways are:two 2-blocks stacked one on top of another.one 2-block stacked on top of two 1-blocks.two 1-blocks stacked on top of one 2-block.

• For the second case,

  • each row of the wall can contain either two blocks of width 1, or one block of width 2. However, the wall where all rows contain two blocks of width 1 is not a solid one as it can be divided vertically.
  • Thus, the number of ways is 2 × 2 × 2 - 1 = 7.

• For the third case,

  • A 3-unit course of brick can be built four ways:
    • Three singles (1,1,1)
    • One triple (3)
    • A double before a single (2,1)
    • A single before a double (1,2)
  • Any of the four patterns above can go on top of the (3) or on bottom of the (3). Total: 8.
  • If we do not use a 3, then the only other stable pattern is (2,1) on top of (1,2). Cumulative total: 9.

• For the fourth case, we have

  • 8 ways of building each of the four layers of bricks:

    • 1,1,1,1
    • 1,1,2
    • 1,2,1
    • 2,1,1
    • 1,1
    • 1,3
    • 3,1
    • 4

    Total number of patterns:

    8^4= 4,096

  • Of these 4,096 patterns, some will fail to satisfy the structural integrity condition. So we need to subtract the patterns that contain a vertical split. There are 3 vertical seams that provide possible locations for the vertical split, and 7 ways of placing any of 1, 2 or 3 splits among these 3 seams.There is exactly one way to have three splits, one on each of the three vertical seams (4 4-high towers of 1-block bricks) .

    Cumulative: 4,096 - 1 = 4,095.

  • If we have two splits, along the left and middle seams, then there are two 1-block towers and one 4-high, 2-wide tower.Exactly one way to build two 4-high towers of 1-blocks15 ways to build the 4-high, 2-wide sub-wall:(1,1) or (2)repeated for at any of four layers,minus the separable pattern where the (1,1) layer repeats 4 times.15 × 1 = 15 ways to have two splits, one along the left seam an done along the middle seam.Similarly, two splits, left and right seams: 15 waysAnd two splits, middle and right seams 15 ways

    Cumulative 4,095 - 15 - 15 - 15 = 4,050.

  • If we have exactly one split down the middle, this meansthere are two separate non-splitting 4-high, 2-wide walls.Each such wall can be built 24-1=15 ways (as above).The count of walls that can split once down the middle is thus 15 × 15 = 225.

    Cumulative: 4,050 - 225 = 3,825.

  • Exactly one split along the leftmost seam:There is one tower of 1-bricks on the left next to a 4-high, 3-wide wall.The ways of building the 4-high, 3-wide wall are: 44 = 256 is the number of ways of repeating any of (1,1,1) or (3) or (2,1) or (1,2) four timesof these 256 patterns, some are separable, hence already accounted for before in the enumerationthe three 1-block towers: one patternone two-wide, four-high tower on the right next to a 1-block tower: 15 patterns (derivation above)ditto on the left: 15 patterns

    Total: 256* - 15 - 15 - 1 = 225

  • Ditto for a split along the rightmost seam: 225 ways

    Cumulative : 3,825 - 225 - 225 = 3,375.

————————————————————————————————————

说实话，题目我看了一个小时才从头看懂到尾（笑，其实题目里提供了很多信息，解题的时候忽略了，然后又回头读题，到最后找到解法了才彻底读透，这题和第一题好像都出现在谷歌的面试题中过，但是这题最大的问题不在于解法，在于时间复杂度和实际的运行时间上。

这道题简单来说可以理解为横着放的乐高积木，总共有四种块，分别长 1，2，3，4，用这些长度的积木来堆积一个 N M 的墙，由于每一层的宽度一致，如果我们令 K 为每一层的所有组合可能性的数量，M 为其高度，即层数，那么*整体排布的可能性就等于 K 的 M 次幂，由于这里涉及到了 Bignum，这里还要在幂运算的同时做个模 1,000,000,007 的运算。

计算 K 的方法就是个简单的动态规划：

K(N) = K(N-1) + K(N-2) + K(N-3) + K(N-4)
K(1) = 1
K(2) = 2
K(3) = 4
K(4) = 8

动态规划算出了每一层的可能性之后，还要继续考虑多层之间不能出现连续分割的情况。例如每一层的最右边都是 1 单位的块，就会出现一个连续的分割，这种情况就需要被排除。这里也是一层动态规划，即如果宽度为 N，那么宽度为 n ，高度为 M 的墙不会出现连续分割的可能情况（题中的 Solid Wall），就等于宽度为 n 高度为 M 的所有可能性组合，减去所有出现连续分割的情况数。

为了计算所有出现连续分割的情况数，我们需要将宽度为 n 的墙分成两部分，一部分是 Solid Wall，也就是没有出现分割的情况 S(n)，乘以剩下的部分所有的可能性 这里的 S(n) 也就是自身，我们可以递归将其分割到最小的 S(1) = 1。如果宽度为 4 ，则宽度为 4 出现连续分割的情况，分别有以下几种情况：

• 左边一列全是 1，右边三列任意排布；
• 左边两列不出现连续分割（若出现连续分割，即包含了前面的那种情况），右边两列任意排列；
• 左边三列不出现连续分割（若出现连续分割，则包含了前面两种情况），右边一列全是 1。

你可能会说，还有一种左边一列 1 右边一列 1 中间一列 2 的情况，但是其实他们包含在了第一种情况里，因为第一种情况里右边三列是任意排布的。其实这个规律，题目的一大堆叙述中确实给出了线索……就是需要读题了。所以我们可以得出公式：

S(N) = K(N) ^ M - SUM(i)(S(i) * (K(N - i) ^ M)) (0 < i < N)

现在，接下来最主要的事情出现了，按照以上逻辑写出的嵌套动态规划（ K(N) 需要动态规划来计算出来），时间复杂度在 缓存了 K (N) 之后是 O(N^2)， 然而由于每一次 K (N) 即使是从缓存中读取，也仍然需要做一次幂模运算，因为每一次解的时候 M 都是不同的，而它要求最多一次 input 100 个 N * M ，这就要求复杂度更加精简。在同一次解的过程中，S(i) 也是可以缓存的。

代码：

import time
import array

class Solution:

    def __init__(self):
        self.cache_count_fuck_dict = [None] * 1000
        self.cache_count = [0] * 1000

    def findSolutionCount(self,width):
        # print width
        g = width - 1
        if self.cache_count[g] != 0:
            return self.cache_count[g]

        if width > 4:
            f = int(pow(self.findSolutionCount(g) + self.findSolutionCount(width - 2) + self.findSolutionCount(width - 3) + self.findSolutionCount(width - 4),1,1000000007))
            self.cache_count[g] = f
            return f
        else:
            return int(pow(2,width - 1))

    def findTotalSolutionCountForWidth(self,width,height):
        if self.cache_count_fuck[width - 1] != 0:
            # self.totalKTime += time.time() - now_f
            return self.cache_count_fuck[width - 1]
        else:
            f = int(pow(self.findSolutionCount(width),height,1000000007))
            self.cache_count_fuck[width - 1] = f
            # self.totalKTime += time.time() - now_f
            return f

    def findBlock(self,height,width):

        self.height = height
        if self.cache_count_fuck_dict[height] is not None:
            self.cache_count_fuck = self.cache_count_fuck_dict[height]
        else:
            self.cache_count_fuck = [0] * 1000

        self.cache_count_block = [None] * width
        g = [0] * 1000
        self.cache_block = array.array('l', g)

        d = self.block(width,height)
        self.cache_count_fuck_dict[height] = self.cache_count_fuck

        return d

    def block(self,width,height):
        if width == 1:
            return 1

        count = 0
        for i in range(1,width,1):
            if self.cache_count_block[i] is not None:
                b_count = self.cache_count_block[i]
            else:
                b_count = self.block(i,height)
                self.cache_count_block[i] = b_count
            if self.cache_count_fuck[width - i - 1] != 0:
                b_count *= self.cache_count_fuck[width - i - 1]
            else:
                k = self.findTotalSolutionCountForWidth(width - i,height)
                self.cache_count_fuck[width - i - 1] = k
                b_count *= k

            count += b_count
        r = int((self.findTotalSolutionCountForWidth(width,height)  - count) % 1000000007)
        return r
            
t = Solution()

# l = [(2,3),(3,2),(4,4),(800,800),(200,800),(300,800),(400,800),(500,800),(600,800),(700,800),(340,800),(750,800),(800,800),(800,800),(800,800),(800,800),(800,800),(800,800),(4,4)]
l = [(800,800)]

import time
now_f = time.time()
for i in range(0,len(l),1):
    now = time.time()
    print t.findBlock(l[i][0],l[i][1])
    print "takes : " + str(time.time() - now) + " s"
print "total takes : " + str(time.time() - now_f) + " s"

在求幂模操作的时候，由于 Math.pow 不支持 Bigint 运算，所以我一开始换了 **，后来查了一下发现用 pow(x,y,z) 是可以直接求幂模的，而且性能更好：

pow(x, y[, z]) -> number
    
With two arguments, equivalent to x**y.  With three arguments,
equivalent to (x**y) % z, but may be more efficient (e.g. for longs).

将缓存从 Dict 换成 List 也有一定性能提升，这题总共有十个 Test Case，基本上前两个数值小和少的 case 过了就基本说明算法没什么问题了，一开始后面八个 Case 全部都超时，后来不断地优化，换成了 List 缓存，换成了 pow，堪堪过到第八个 Case，剩下两个仍然是超时。虽然昨天已经提交完了进不去了，然而写这些的时候还是不服气想优化一番，于是开始了逐行的时间调试，最后还是在 S (N) 这个函数这里再加了一层缓存优化，性能又差不多提升了三分之一。又注册了个新号，终于把十个 Test Case 全过了。

将 Dict 缓存优化成 List 和 Array 缓存前：

** 替换成 pow(x,y,z) ：

最终：