有没有中美都适用的安卓手机推荐 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

有没有中美都适用的安卓手机推荐

有没有中美都适用的安卓手机推荐# PDA - 掌中宝

n*n2018-08-27 07:08

1 楼

在面试时遇到这样一个问题，大概意思是：
- A bug is trying to cross the river start from position 0 to position X
- Every time bug can jump no more than the D steps (1 to D steps);
- Leaves will fall from the tree to the river based on schedule A. A[0] = 1
means a leaf will fall on position 1 at time 0;
- Need to find the earliest time that the bug can jump from position 0 to x
using leaves; If there is no answer, return -1;
Example:
A = [1, 3, 1, 4, 2, 5]
X = 7
D = 3
Answer: 3
Explanation: At time 3, there will be leaves on position 1,3, and 4; bug can
jump 1 step, 3 step, and then 3 steps to cross the river;
Expected time complexity is O(n)
请教各位解题思路，先谢谢了~

x*o2018-08-27 07:08

2 楼

老三和环总只有今夜是例外

d*u2018-08-27 07:08

3 楼

如题，刚刚买了Project Fi的LG V35，经常出现system UI isn't responding，所以想
换。因为已经用了安卓好多年，所以暂时不打算买iPhone，有什么推荐吗？
谢谢。

j*72018-08-27 07:08

4 楼

// time O(N). space O(X)
public int solution(int[] A, int X, int D) {
LinkedList deque = new LinkedList();
int[] pos = new int[X + 1];
pos[0] = 0;
pos[X] = 0;
for (int i = 1; i < X; i++) {
pos[i] = -1;
}
for (int i = 0; i < A.length; i++) {
if (pos[A[i]] == -1) {
pos[A[i]] = i;
}
}
int[] DP = new int[X + 1];
DP[0] = 0;
deque.add(0);
for (int i = 1; i <= X; i++) {
while (deque.isEmpty() == false && deque.getFirst() + D < i) {
deque.removeFirst();
}
if (pos[i] == -1 || deque.isEmpty()) {
DP[i] = -1;
continue;
}
DP[i] = Math.max(pos[i], DP[deque.getFirst()]);
while (deque.isEmpty() == false && DP[deque.getLast()] >= DP[i])
{
deque.removeLast();
}
deque.addLast(i);
}
return DP[X];
}

w*c2018-08-27 07:08

5 楼

你怎么知道的
小破献身了

【在 x****o 的大作中提到】

: 老三和环总只有今夜是例外

w*82018-08-27 07:08

6 楼

Moto G5 plus

【在 d*******u 的大作中提到】

: 如题，刚刚买了Project Fi的LG V35，经常出现system UI isn't responding，所以想
: 换。因为已经用了安卓好多年，所以暂时不打算买iPhone，有什么推荐吗？
: 谢谢。

T*U2018-08-27 07:08

7 楼

int[] dp = new int[A.length + 1];
for (int i = 0; i < A.length; i++){
if (A[i] > dp[i] && A[i] - dp[i] <= D){
dp[i + 1] = A[i];
} else {
dp[i + 1] = dp[i];
}
if (dp[i + 1] >= x - D) return i; // jumping takes no time
}
return -1;

1
x

【在 n******n 的大作中提到】

: 在面试时遇到这样一个问题，大概意思是：
: - A bug is trying to cross the river start from position 0 to position X
: - Every time bug can jump no more than the D steps (1 to D steps);
: - Leaves will fall from the tree to the river based on schedule A. A[0] = 1
: means a leaf will fall on position 1 at time 0;
: - Need to find the earliest time that the bug can jump from position 0 to x
: using leaves; If there is no answer, return -1;
: Example:
: A = [1, 3, 1, 4, 2, 5]
: X = 7

R*d2018-08-27 07:08

8 楼

原来第三位剑客是总理您

h*b2018-08-27 07:08

9 楼

你这个错误说明otc升级系统有问题，重新去下一个最新的完整版firmware，用odin重
新刷一下就行了。

n*n2018-08-27 07:08

10 楼

谢谢回复，这个好像不对
如果 A=[5,2,1], X=8, D=4 就会return -1

【在 T****U 的大作中提到】

: int[] dp = new int[A.length + 1];
: for (int i = 0; i < A.length; i++){
: if (A[i] > dp[i] && A[i] - dp[i] <= D){
: dp[i + 1] = A[i];
: } else {
: dp[i + 1] = dp[i];
: }
: if (dp[i + 1] >= x - D) return i; // jumping takes no time
: }
: return -1;

x*o2018-08-27 07:08

11 楼

同性恋的圈子其实很小的

【在 w*****c 的大作中提到】

: 你怎么知道的
: 小破献身了

v*r2018-08-27 07:08

12 楼

Project Fi支持LG V35？
不是只能用狗儿子吗

k*l2018-08-27 07:08

13 楼

这是开发超超级玛莉的group?

1
x

【在 n******n 的大作中提到】

n*42018-08-27 07:08

14 楼

我只好先宣布一下我是个女同。

【在 x****o 的大作中提到】

: 老三和环总只有今夜是例外

d*u2018-08-27 07:08

15 楼

谢谢，果然好用。

【在 h**b 的大作中提到】

: 你这个错误说明otc升级系统有问题，重新去下一个最新的完整版firmware，用odin重
: 新刷一下就行了。

g*y2018-08-27 07:08

16 楼

for each time i = 0 : n
call jump game I function
if it returns true, then return i

1
x

【在 n******n 的大作中提到】

x*o2018-08-27 07:08

17 楼

今夜，在这里，同性恋不分男女，不分肤色，不分物种

【在 n****4 的大作中提到】

: 我只好先宣布一下我是个女同。

k*02018-08-27 07:08

18 楼

google pixel?

【在 d*******u 的大作中提到】

j*72018-08-27 07:08

19 楼

In order to reach position i, we must jump to i from positions
i-D, i-D+1, .... i-1. Thus, there are D number of ways to jump to position i.
DP[i]= the earliest time we can reach position i.
The best way to reach position i is selected from DP[i-D] to DP[i-1]. We
have to find the min value from DP[i-D] to DP[i-1].
In other words, we have to find the minimum value in a sub-array of size D.
Therefore, this problem can be reduced to the problem of finding the minimum
value in a sliding window of size D in an array.
https://leetcode.com/problems/sliding-window-maximum/

1
x

【在 n******n 的大作中提到】

A*r2018-08-27 07:08

20 楼

看到最后四个字我松了一口气

【在 x****o 的大作中提到】

: 今夜，在这里，同性恋不分男女，不分肤色，不分物种

r*72018-08-27 07:08

21 楼

o(n)的n指啥？A中的元素数目？
我可以想到o(A.size() * D)的解法，优化一下可以o(A.size() * lg(D))

1
x

【在 n******n 的大作中提到】

d*f2018-08-27 07:08

22 楼

严格说是不限物种

【在 A*********r 的大作中提到】

: 看到最后四个字我松了一口气

y*s2018-08-27 07:08

23 楼

public static int cross(int[] A, int X, int D) {
int reach = D;
if (reach >= X) {
return 0;
}
PriorityQueue pq = new PriorityQueue();

for (int i = 0; i < A.length; i++) {
if (A[i] <= reach) {
reach = Math.max(reach, A[i] + D);
}
else {
pq.add(A[i]);
}
while (!pq.isEmpty() && reach >= pq.peek()) {
reach = Math.max(reach, pq.poll()+D);
}
if (reach >= X) {
return i;
}
}

return -1;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A = {1, 3, 1, 4, 2, 5};
System.out.println(cross(A, 7, 3));

int[] B = {5, 2, 1};
System.out.println(cross(B, 8, 4));
}

x*o2018-08-27 07:08

24 楼

松了好，松了好

【在 A*********r 的大作中提到】

: 看到最后四个字我松了一口气

l*s2018-08-27 07:08

25 楼

谢谢分享。不过会有time O(n)的可能么？
写了一个O(nln(n))的对付一下。
private static int jumpTimes(int[] leaves, int distance, int maxStep){
SortedDictionary dict = new SortedDictionary();
int i = 0;
for(i = 0; i < leaves.Length; i++)
if(!dict.ContainsKey(leaves[i])) dict[leaves[i]] = i;
int[,] lt = new int[dict.Count, 2];
i = 0;
foreach(var d in dict)
{ lt[i, 0] = d.Key; lt[i++, 1] = d.Value; }
for(i = 0; i < lt.Length; i++){
if(lt[i, 0] - (i == 0 ? 0 : lt[i - 1, 0]) > maxStep) return -1;
int j = i - 1, min = int.MaxValue;
while(j >= 0 && lt[i, 0] - lt[j, 0] <= maxStep){
if(lt[j, 1] > lt[i, 1]) min = Math.Min(min, lt[j, 1]);
else { min = lt[i, 1]; break; }
j--;
}
if(min != int.MaxValue) lt[i, 1] = min;
if(lt[i, 0] + maxStep >= distance) return lt[i, 1];
}
return -1;
}

A*r2018-08-27 07:08

26 楼

今晚上的最终问题来了
老三是0还是1？

【在 x****o 的大作中提到】

: 松了好，松了好

l*s2018-08-27 07:08

27 楼

这个方法是Time O(X)吧，当步幅很大时就要吃亏了，比如X = 2,000,000,000, D =
200,000,000。

【在 j**7 的大作中提到】

: In order to reach position i, we must jump to i from positions
: i-D, i-D+1, .... i-1. Thus, there are D number of ways to jump to position i.
: DP[i]= the earliest time we can reach position i.
: The best way to reach position i is selected from DP[i-D] to DP[i-1]. We
: have to find the min value from DP[i-D] to DP[i-1].
: In other words, we have to find the minimum value in a sub-array of size D.
: Therefore, this problem can be reduced to the problem of finding the minimum
: value in a sliding window of size D in an array.
: https://leetcode.com/problems/sliding-window-maximum/
:

x*o2018-08-27 07:08

28 楼

博导，同性恋里你是我最佩服的

【在 d********f 的大作中提到】

: 严格说是不限物种

j*72018-08-27 07:08

29 楼

是 O(N+X). 如果X比N要小就是O(N)了。

【在 l******s 的大作中提到】

: 这个方法是Time O(X)吧，当步幅很大时就要吃亏了，比如X = 2,000,000,000, D =
: 200,000,000。

x*o2018-08-27 07:08

30 楼

10100010011010100101001

【在 A*********r 的大作中提到】

: 今晚上的最终问题来了
: 老三是0还是1？

l*22018-08-27 07:08

31 楼

叶子掉下来就一直停那儿？这样的话是不是greedy就可以？每次能跑多远跑多远

1
x

【在 n******n 的大作中提到】

H*g2018-08-27 07:08

32 楼

看最后一位

【在 x****o 的大作中提到】

: 10100010011010100101001

g*z2018-08-27 07:08

33 楼

这题的意思是虫子每轮只能跳一次，还是等到有路径了可以一轮一口气就跳完？如果是
前者，那楼主的例子应该返回4吧？
我按照后者写了一个，看着是O(Dn)的，大家看看有问题没
def jump(A, X, D):
n = len(A)
L = [False]*(X+1)
C = [False]*(X+1)
C[0], C[X] = True, True
L[0] = True
for t in range(n):
C[A[t]] = True
if not L[A[t]] and (L[A[t]-1] or L[A[t]-2] or L[A[t]-3]):
L[A[t]] = True
if A[t]==X:
return t
for i in range(D):
if not L[A[t]+i+1] and C[A[t]+i+1]:
L[A[t]+i+1] = True
if A[t]+i+1==X:
return t
return -1

H*g2018-08-27 07:08

34 楼

张老11
0总

【在 A*********r 的大作中提到】

: 今晚上的最终问题来了
: 老三是0还是1？

l*32018-08-27 07:08

35 楼

没看懂，能讲一下思路吗？谢谢。

【在 j**7 的大作中提到】

: 是 O(N+X). 如果X比N要小就是O(N)了。

A*r2018-08-27 07:08

36 楼

我赌100伪币老三是0，环总是1

【在 H********g 的大作中提到】

: 张老11
: 0总

n*n2018-08-27 07:08

37 楼

我也没怎么看懂jas7的方法，不过他提示了看leetcode的Sliding Window Maximum，感
觉是对的。。。我继续看，yimingts的方法我貌似看懂了，但里面有个priority queue
，所以感觉是nlogn了

【在 l*3 的大作中提到】

: 没看懂，能讲一下思路吗？谢谢。

H*g2018-08-27 07:08

38 楼

我突然理解美国商店为什么标价都写0.99就是不肯写1.00，好让我们确定这是十进制的
数字。

【在 A*********r 的大作中提到】

: 我赌100伪币老三是0，环总是1

l*32018-08-27 07:08

39 楼

这个懂了，谢谢！

i.
.
minimum

【在 j**7 的大作中提到】

x*o2018-08-27 07:08

40 楼

我跟，加1伪币

【在 A*********r 的大作中提到】

: 我赌100伪币老三是0，环总是1

l*32018-08-27 07:08

41 楼

懂了，sliding window maxi算法已看，十分巧妙！

queue

【在 n******n 的大作中提到】

: 我也没怎么看懂jas7的方法，不过他提示了看leetcode的Sliding Window Maximum，感
: 觉是对的。。。我继续看，yimingts的方法我貌似看懂了，但里面有个priority queue
: ，所以感觉是nlogn了

A*r2018-08-27 07:08

42 楼

美国知道二进制的人有总人口的0.1%么？

【在 H********g 的大作中提到】

: 我突然理解美国商店为什么标价都写0.99就是不肯写1.00，好让我们确定这是十进制的
: 数字。

j*32018-08-27 07:08

43 楼

感觉线性时间不现实，严格来说应该是O(Dn)吧。强行忽略window size的系数，才会到
n吧，不然真是白瞎了。
随便写了个O(Dn)，用的DP，我估摸着贪心算法可能可行。
算法链接 cpp.sh/5afu

T*e2018-08-27 07:08

44 楼

其实是16进制

【在 H********g 的大作中提到】

: 我突然理解美国商店为什么标价都写0.99就是不肯写1.00，好让我们确定这是十进制的
: 数字。

M*62018-08-27 07:08

45 楼

原题在这。https://codility.com/demo/results/demoH5GMV3-PV8/
A small frog wants to get to the other side of a river. The frog is
currently located at position 0, and wants to get to position X. Leaves fall
from a tree onto the surface of the river.
You are given a non-empty zero-indexed array A consisting of N integers
representing the falling leaves. A[K] represents the position where one leaf
falls at time K, measured in seconds.
The goal is to find the earliest time when the frog can jump to the other
side of the river. The frog can cross only when leaves appear at every
position across the river from 1 to X. You may assume that the speed of the
current in the river is negligibly small, i.e. the leaves do not change
their positions once they fall in the river.
For example, you are given integer X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
In second 6, a leaf falls into position 5. This is the earliest time when
leaves appear in every position across the river.
Write a function:
class Solution { public int solution(int X, int[] A); }
that, given a non-empty zero-indexed array A consisting of N integers and
integer X, returns the earliest time when the frog can jump to the other
side of the river.
If the frog is never able to jump to the other side of the river, the
function should return −1.
For example, given X = 5 and array A such that:
A[0] = 1
A[1] = 3
A[2] = 1
A[3] = 4
A[4] = 2
A[5] = 3
A[6] = 5
A[7] = 4
the function should return 6, as explained above.
Assume that:
N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(X), beyond input storage (not
counting the storage required for input arguments).
Elements of input arrays can be modified.

d*m2018-08-27 07:08

46 楼

你面的哪家啊？我刚刚做的一个公司的online coding challenge就这道题。
其实没必要想那么麻烦，遍历一边数组记录下来每个位置落叶的最短时间，这个是O(N)
。然后对这个新的数组求一个sliding window minimum就行了，之前有个人已经发过了
，就是leetcode上那题。最后求出所有sliding window minimum里面的maximum就是最
短过河所需时间。
尽管需要三个iteration，但是每个都是O(N)所以还是线性的。

j*72018-08-27 07:08

47 楼

你这题不一样

fall
leaf
the

【在 M***6 的大作中提到】

: 原题在这。https://codility.com/demo/results/demoH5GMV3-PV8/
: A small frog wants to get to the other side of a river. The frog is
: currently located at position 0, and wants to get to position X. Leaves fall
: from a tree onto the surface of the river.
: You are given a non-empty zero-indexed array A consisting of N integers
: representing the falling leaves. A[K] represents the position where one leaf
: falls at time K, measured in seconds.
: The goal is to find the earliest time when the frog can jump to the other
: side of the river. The frog can cross only when leaves appear at every
: position across the river from 1 to X. You may assume that the speed of the

j*72018-08-27 07:08

48 楼

你的思路跟我的一样。sliding window minimum 有个O(N)解法所以这题也是O(N).
我做的一个公司给的Codility test有这道题。Codility要求时间复杂度是O(N)空间复
杂度是O(X).
N is an integer within the range [0..100,000]
X and D are integers within the range [1..100,000]
each element of array A is an integer within the range [1..X-1].
Expected: O(N) time and O(X) extra space.

N)

【在 d****m 的大作中提到】

: 你面的哪家啊？我刚刚做的一个公司的online coding challenge就这道题。
: 其实没必要想那么麻烦，遍历一边数组记录下来每个位置落叶的最短时间，这个是O(N)
: 。然后对这个新的数组求一个sliding window minimum就行了，之前有个人已经发过了
: ，就是leetcode上那题。最后求出所有sliding window minimum里面的maximum就是最
: 短过河所需时间。
: 尽管需要三个iteration，但是每个都是O(N)所以还是线性的。

g*d2018-08-27 07:08

49 楼

贴一个我的解法
https://coderpad.io/W6A44W42
先用一个map，从position对应到出现叶子的时间；如果某位置不会出现叶子，那么就
没这个item。
然后尝试前进1到D步，每次尽量往远的地方走；如果必须等待叶子落下，就前进到等待
最少的地方。
重复直到走到了目的地。

s*g2018-08-27 07:08

50 楼

int bugCrossRiver(vector a, int X, int D)
{
int n = a.size();
int stepToX = X;
int curPos = 0;
int prePos = 0;
for (int i=0; iint diff = a[i]-curPos;
if (diff>0 && diff<=D) {
curPos = a[i];
stepToX -= curPos;
stepToX += prePos;
prePos = a[i];
if (stepToX<=D) {
return i;
}
}
}
return -1;
}

r*72018-08-27 07:08

51 楼

记录每个位置落叶最短时间是什么意思？
如果只遍历N就是原数组，要么就是N*D

N)

【在 d****m 的大作中提到】