10.9 奇安信笔试

第一题 打家劫舍 力扣链接

class Solution {
    //打家劫舍的变种问题分析理解
    public int rob(int[] nums) {
        //数组的快速复制的api
        if(nums.length == 0 )return 0;
        if(nums.length == 1 )return nums[0];
	    //开头与结尾不能同时取，分成[0,倒数第二位]：包含第一位，可以不取  [1,最后一位]:包含最后一位，可以不取
        int m = robhelp(Arrays.copyOfRange(nums,0,nums.length-1));
        int n = robhelp(Arrays.copyOfRange(nums,1,nums.length));
        return Math.max(m,n);
    }

     //对于动态规划算法的复习分析
    public int robhelp(int[] nums) {
        int m = nums.length;
        //dp[i] 是当前能偷到的max
        int[] dp = new int[m+1];
        dp[1] = nums[0];
        for(int i =2;i<=m;i++){
		    //当前位置偷：dp[i-2]+nums[i-1]  不偷：dp[i-1]
            dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);
        }
        return dp[m];
    }
}

第二题：前缀和考察（可以暴力写）

题目大概：数组元素只有1,0, 0代表消费一个金币，1代表获取一个金币，确保这个数组遍历过后，整个过程是合法（金额不为负数）

public class Main {
//    前缀和对应的考察分析

    public boolean CheckGameResource (int[] sequence) {
        // write code here
        int res = 0;
        int n = sequence.length;
        int ans = 0;
        int[] a = new int[n];
        int bns = 0;
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            if (sequence[i] == 1) {
                ans++;
            }else {
                bns++;
            }
            a[i]=ans;
            b[i]=bns;
            if (a[i]<b[i]) {
                return false;
             }
        }
        if(a[n-1]!=b[n-1]) {
            return false;
        }
        return true;
    }
}