首页 > 旷视08.30笔试 AC
头像
plkij
发布于 2021-08-31 00:18
+ 关注

旷视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;
    }

}



全部评论

(0) 回帖
加载中...
话题 回帖