旷视08.30笔试 AC
1. 和打家劫舍一样
public class Solution {
public static void main(String[] args) {
int[] nums = new int[]{200, 700, 300, 100, 900};
System.out.println(new Solution().max_steps(nums));
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param nums int整型一维数组 每个跑步机最大步数
* @return int整型
*/
public int max_steps(int[] nums) {
// write code here
int n = nums.length;
if (n == 0) {
return 0;
}
long[][] dp = new long[n][2];
dp[0][0] = 0;
dp[0][1] = nums[0];
for (int i = 1; i < n; i++) {
dp[i][1] = dp[i - 1][0] + nums[i];
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
}
return (int) Math.max(dp[n - 1][1], dp[n - 1][0]);
}
} 2. 使用DFS会栈溢出，可以使用Deque来做 import java.util.Deque;
import java.util.LinkedList;
public class Solution {
public static void main(String[] args) {
int[] arr = new int[]{3, 2, 1, 3, 0, 3, 1, 2, 1};
int start = 2;
System.out.println(new Solution().jump_game(arr, start));
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* <p>
* 可以到达时返回True，否则返回False
*
* @param arr int整型一维数组 非负整数数组
* @param start int整型 起始下标
* @return bool布尔型
*/
public boolean jump_game(int[] arr, int start) {
// write code here
int n = arr.length;
if (start < 0 || start >= n) {
return false;
}
boolean[] visit = new boolean[n];
Deque<Integer> deque = new LinkedList<>();
deque.addLast(start);
while (!deque.isEmpty()) {
int num = deque.removeFirst();
if (visit[num]) {
continue;
}
else {
if (arr[num] == 0) {
return true;
}
else {
visit[num] = true;
if (num + arr[num] >= 0 && num + arr[num] < n) {
deque.add(num + arr[num]);
}
if (num - arr[num] >= 0 && num - arr[num] < n) {
deque.add(num - arr[num]);
}
}
}
}
return false;
}
} 
