Zenefit OA#2 分享

原帖地址:一亩三分地

周么做了OA ZEN TEST 2. 题目有人已经发过了,我再发一遍,方便查找。
第一题: filp 1 or 0
You are given a binary array with N elements: d[0], d[1], … d[N -1].
You can perform AT MOST one move on the array: choose any two integers [L, R],
and flip all the elements between (and including) the L-th and R-th bits. L and
R represent the left-most and right-most index of the bits marking the
boundaries of the segment which you have decided to flip.

What is the maximum number of ‘1’-bits (indicated by S) which you can obtain in
the final bit-string?
‘Flipping’ a bit means, that a 0 is transformed to a 1 and a 1 is transformed to
a 0
Input Format
An integer N
Next line contains the N bits, separated by spaces: d[0] d[1] … d[N-1]

Output:
S

Sample Input:
8
1 0 0 1 0 0 1 0
Sample Output:
6

我是用三个变量,扫描一遍数组:
– 如果元素是1, 1出现的次数+1,0的个数-1,但保持0的个数>=0;
– 否则,0的个数+1, 如果0的个数>maxZeros, 更新maxZeros
– 最后返回1的个数 + maxZeros

第二题:

There are a large number of leaves eaten by caterpillars. There are ‘K’ caterpillars which jump onto the leaves in a pre-determined sequence.
All caterpillars start at position 0 and jump onto the leaves at positions1,2,3…,N. Note that there is no leaf at position 0.
Each caterpillar has an associated ‘jump-number’. Let the jump-number of thei-th caterpillar be A [i]. A caterpillar with jump number 7 keeps eating leaves
in the order 1,241,3*1,… till it reaches the end of the leaves – i.e, it eatsthe leaves at the positions which are multiples of .
Given a set A of K element是, K<=15, N <=109, we need to determine the number of uneaten leaves. Input Format: N -number of leaves A – Given array of integers Output Format: An integer denoting the number of uneaten leaves. . from: 1point3acres.com/bbs Sample Input: N = 10 A = [2,4,5] Sample Output: 4 因为N很大, K相对较小,所以不适合用数组来做。我是用Inclusion-Exclusion Principle做的。算法如下: for each subsets ss of length len in [1, K]: for each subset s in ss: calculate least common multiplier of elements in s, let be lcm eatenLeaves = N / lcm totalEatenLeaves += len % 2 == 1 ? eatenLeaves : -eatenLeaves return N – totalEatenLeaves 计算subsets时,我存的是index,因为index 是有序的,所以不许要排序。另外,我写的是nextSubsets,每次调用,在原来的sunsets的基础上多加一个更大的index. 计算lcm时,如果只有一个元素,lcm就是自身。一下是用来计算两个数的lcm. static long lcm(long a, long b) { return a * b / gcd(a, b); } static long gcd(long a, long b) { while (b != 0) { long temp = b; b = a % b; a = temp; } return a; } 希望有所帮助。祝大家好好准备,都有大OFFERS.加油! 俺是新手,能给点米吗?谢谢!