9.25用友笔试

    public int shrinkCircle (int[] circle) {
        //用链表模拟
        LinkedList<Integer> data = new LinkedList<>();
        //原来要从1开始找
        int i = 0;
        for(; i < circle.length; i++){
            if(circle[i] == 1){
                break;
            }
            data.addLast(circle[i]);
        }
        //出来的时候i是1的位置，那再从末尾元素加到i的位置
        for(int j = circle.length - 1; j >= i; j--){
            data.addFirst(circle[j]);
        }
        //这样子出现的就是
        //1到末尾元素，第一个元素到1的之前
        int remainder = 1;
        while(data.size() > 1){
            Integer temp = data.removeFirst();
            if(temp % 4 == remainder){
                remainder++;
                if(remainder == 4){
                    remainder = 0;
                }
                //符合条件就不要加回去了，就从环中剔除了该元素
                continue;
            }
            data.addLast(temp);
        }
        //只剩最后一个了
        return data.getFirst();
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param x int整型 目标点的X坐标
     * @param y int整型 目标点的Y坐标
     * @param z int整型 目标点的Z坐标
     * @return long长整型
     */
    public long countPaths (int x, int y, int z) {
        long[][][] memo = new long[x + 1][y + 1][z + 1];
        //base case
        //从起点到起点只有一种路径，那就是站着不动，这就是唯一的base case
        memo[0][0][0] = 1;
        return dp(memo, x, y, z);
    }
    //采用记忆化搜索的办法
    private long dp(long[][][] memo, int x, int y, int z){
        //dp含义，从0,0,0到x,y,z的路径数量
        //状态转移
        //依据题意，每次都只能沿着三条坐标轴之一移动一个方向，所以到达x,y,z这个点的，只可能有这三种情况
        //从x-1,y,z过来，从x,y-1,z过来，从x,y,z-1过来
        //因此状态转移方程为
        //dp[x][y][z] = dp[x-1][y][z] + dp[x][y-1][z] + dp[x][y][z-1]
        if(x == -1 || y == -1 || z == -1){
            return 0;
        }
        if(memo[x][y][z] != 0){
            return memo[x][y][z];
        }
        //只能从三个方向而来
        long res = dp(memo, x - 1, y, z) + dp(memo, x, y - 1, z) + dp(memo, x, y, z - 1);
        memo[x][y][z] = res;
        return memo[x][y][z];
    }

    public int lengthOfLIS(int[] nums) {
        //dp数组的含义为，dp[i]的值是以nums[i]结尾的最长递增子序列长度
        //base case为dp[i] = 1，因为递增子序列最少包括自身，自然长度为1
        //状态转移
        //从左往右找，限定j为0到i-1之间
        //当nums[i] > nums[j]
        //dp[i] = MAX { dp[j] + 1 , dp[i] }
        int[] dp = new int[nums.length];
        int res = 1;
        Arrays.fill(dp , 1);
        for(int i = 1; i < dp.length; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i] , dp[j] + 1);
                }
            }
            res = Math.max(dp[i] , res);
        }
        return res;
    }