-
第 83 楼 / webdriver
- 时间: 2014-9-27 23:58算法问题推荐解法来了...
Jump to the position where we can jump farthest (index + A[index]) next time.
解法（Java）
代码:
public class JumpGameII {
public int jump(int[] A) {
int ret = 0;
int last = 0;
int curr = 0;
for (int i = 0; i < A.length; ++i) {
if (i > last) {
last = curr;
++ret;
}
curr = Math.max(curr, i + A[i]);
}
return ret;
}
}
-
-
- 时间: 2014-9-27 23:59S算法问题: Jump Game
问题描述:
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false. -
-
- 时间: 2014-9-28 00:00算法问题推荐解法来了...
Updated solution: try every reachable index.
Thank to Wenxin Xing for kindly feedback and pointing out my big mistake
解法（Java）
代码:
public class JumpGame {
public boolean canJump(int[] A) {
if (A.length <= 1)
return true;
int curMax = 0;
int max = 0;
for (int i = 0; i < A.length - 1; i++) {
if (i > max)
break;
curMax = A[i] + i;
if (curMax > max) {
max = curMax;
}
if (max >= A.length - 1)
return true;
}
return false;
}
} -
- 时间: 2014-9-28 00:01
-
- 时间: 2014-9-28 00:03
-
- 时间: 2014-9-28 00:05S算法问题: Letter Combinations of a Phone Number
问题描述:
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input
igit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want. -
- 时间: 2014-9-28 00:07算法问题推荐解法来了...
From Matthew. Simpler.
解法（Java）
代码: public class LinkedListCycleII {
public ListNode detectCycle(ListNode head) {
if (head == null)
return head;
ListNode fast = head, slow = head;
do {
if (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
} else {
return null;
}
} while (fast != slow);
slow = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
-
- 时间: 2014-9-28 00:07
-
- 时间: 2014-9-28 00:07算法问题推荐解法来了...
two pointers.
解法（Java）
代码:
public class LinkedListCycle {
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode fast = head;
ListNode late = head;
do {
fast = fast.next;
late = late.next;
if (late == null) {
return false;
} else {
late = late.next;
if (fast == late) {
return true;
}
}
} while(fast != null && late != null);
return false;
}
}
Leetcode Hacking Practice -- Solution in Java Part 1
