Mercari 在线测试

发表于
字数统计: 633 words | 阅读时长 ≈ 3 mins

今天的两道题目有一道似曾相识，属于leetcode里面middle的题目，另外一道完全想不到…

第一题

L, R = 0, 1

对于一个数N，L, R 可以经过任意次数变换，变换的规则为
L = L * 2 - R
R = R * 2 - L

那么为了得到N，所需要的最小步数是多少？

  • 举个例子，如果是11， 那么[LRLR] 就可以得到
  • 如果是-11， 那么最少步数为4，[LLRL]

分析：首先需要区别正负进行不同的变换操作，那么先从正数开始，显然0，1已经有了
对于2的指数，可以一直R下去

  • 2 --> R
  • 4 --> RR
    那么比如3，我们就要构造出 2*1 -(-1)的操作, 5的话 2 * (1) - (-3),也就是说在最后一步我们需要通过R操作得到正数。

对于负数，-1 --> L, -2 --> RL,-3 --> LL 对于2的指数，同样前面进行多次R操作,最后一步是L

思路：对于正数的时候，视情况进行左右变换，由此可以进行位运算来判断是否左还是右，因此选择1作为比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def solution(N):
    number = N 
    number = -number if number<=0 else number - 1
    l, r = 0, 1
    moves = []
    if N <= 0:
        while number != 0:
            if number & 1:
                l = l * 2 -r
                moves.append('L')
            else:
                r = r * 2 - l
                moves.append('R')

            number //= 2
    else:
        while number != 0:
            if number & 1:
                r = r * 2 -l
                moves.append('R')
            else:
                l = l * 2 - r
                moves.append('L')

            number //= 2

    return len(moves)

第二题

找座位，leetcode849类似
对于一个0-N的list，A[0] = 10, A[1] = 8, A[2] = -3，其对应的值可以想象成数轴上的点
那么对于一个给定的list，能不能在数轴上找到一个点，使得离它最近的点的距离是最大的，问最大的距离是多少？

思路：leetcode上是直接给了索引好的list，[0,1,1,1,0,0,0,1] 0表示没人坐，1表示有人了，那么这里只需要将数组做一下转化就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(A):
    a, b = abs(min(A)), abs(max(B))
    pool = [0] *(a+b)
    for i in range(len(A)):
        pool[A[i]] = 1 

    racks_split = "".join(map(str, A)).split('1')
    max_dist = max(map(len, racks_split))
    return max(len(racks_split[0]), len(racks_split[1]), int(max_dist/2 + 0.5))

## another 
def solution(A):
    A.sort()
    ans = float('-inf')
    for i in range(len(A)):
        if A[i+1]-A[i] > 1:
            ans = max(ans, A[i+1]-A[i])
    ## take the middle
    return ans // 2