向大家请教几道面试题

大家好！我想向大家请教几道算法题。请大家帮我想想思路。You will be given an array of size N with integers numbered 1 to N in random order and a number k.

for eg. arr = 2 1 3 4 5, k = 2
Let these players are standing in a queue in a given order, first two players will play a game then whose value is greater will win and the lost one will go to end of a queue.
Whoever player will win consecutive k games is the winner of game.
In the above example,

first match b/w : 2 & 1

second match b/w : 2 & 3

third match b/w : 3 & 4
fourth match b/w : 4 & 5

fifth match b/w : 5 & 1
5 won 2 matches consecutively: 5 is the winner





2. Carpool combinations: given N users, each person has a (pick up time,  drop off time), print all combinations of pickups and dropoffs schedule. E.g, (p1, d1), (p2, d2) for 2 persons, then you need to print
[[p1, d1, p2, d2], [p1, p2, d1, d2], [p1, p2, d2, d1], [p2, p1, d1, d2], [p2, p1, d2, d1]]

第一题不知道到底什么要求, 有很多细节没有写.

假设是第一个出现k次胜利的人为赢家
k <= n
先说最笨的解法, 就是把这个动作按要求做一遍. 这个你写不出来的话可以考虑再刷点题.

但是你也知道, 遇到最大数N之前找不到连着的[大,k个小]的话,那么最大数N即答案.
所以只需要在最大数N左边寻找第一个连续出现k个小数即可, 见739

第二题
我看不懂这题到底想干嘛.
不太确定[p1, d1]具体是什么, 如果和每个人具体上下时间, 那么大时间出现在小时间之前到底有没有道理, 比如你又有[d1, d2] 又有[d2, d1] 所以这到底什么意思呢
你如果是少了一个[p2, d2, p1, d1]就是所有的结果, dfs即可. 把每个人的上下次序全做出来, 和具体数字顺序无关.

请问 这题怎么做？

You are given with an array of 1s and 0s. And you are given with an integer m, which signifies number of flips allowed. find the position of zeros which when flipped will produce maximum continuous series of 1s.

// # e.g.
// # input:
// # arr=[1,1,0,1,1,0,0,1,1,1] m=1
// # output=[1,1,1,1,1,0,0,1,1,1] position=2

// # arr=[1,1,0,1,1,0,0,1,1,1] m=2
// # output=[1,1,0,1,1,1,1,1,1,1] position=5,6

wenhao.ge 发表于 2019-9-26 04:05
请问 这题怎么做？

You are given with an array of 1s and 0s. And you are given with an integer m,  ...

找做多含有m个0的subarray，多刷点题即可
leetcode.com/problems/max-consecutive-ones-iii/

337845818 发表于 2019-9-26 11:09
找做多含有m个0的subarray，多刷点题即可
leetcode.com/problems/max-consecutive-ones-iii/

知道了。感谢回复。

where is p2 d2 p1 d1?

ljhgod 发表于 2019-9-27 04:24
where is p2 d2 p1 d1?

我也不知道

主帖的两道题第一道没说求什么，第二道不知所云 (如果只是要combination的话backtrack一下就行了) ...