去哪儿Java编程题解

本菜鸡终于第一次全AC了！！！！ 我就知道我的机会来了~~
第一题：LeetCode 53原题 -- 最大和的连续子数组
// AC

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        while (sc.hasNextInt()) {
            list.add(sc.nextInt());
        }
        int res = maxSubArray(list);
        System.out.println(res);
    }
    private static int maxSubArray(ArrayList<Integer> nums) {
        int res = nums.get(0);
        int sum = nums.get(0);
        for (int i = 1; i < nums.size(); ++i) {
            sum = Math.max(nums.get(i), sum + nums.get(i));
            res = Math.max(res, sum);
        }
        return res;
    }
}

第二题: 棋盘走马
// AC
这里是DFS解法

import java.util.*;
public class Main {
    private static Scanner sc = new Scanner(System.in);
    private static int[][] d = new int[][]{{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, -2}, {1, 2}, {-1, -2}, {-1, -2}};
    private static int res = Integer.MAX_VALUE;
    //起点终点
    private static int stax = sc.nextInt(),stay = sc.nextInt(), ex = sc.nextInt(), ey = sc.nextInt();
    private static boolean[][] vis = new boolean[9][9];
    public static void main(String[] args) {
        solve(stax, stay, 0);
        System.out.println(res);
    }

    private static void solve(int x, int y, int sum) {
        if (sum < res) {
            if (x == ex && y == ey) {
                res = sum;
                return;
            } else {
                for(int i = 0; i < 8; ++i) {
                    int tmpx = x + d[i][0];
                    int tmpy = y + d[i][1];
                    if (tmpx >= 1 && tmpx <= 8 && tmpy >= 1 && tmpy <= 8 && !vis[tmpx][tmpy]) {
                        vis[tmpx][tmpy] = true;
                        solve(tmpx, tmpy, sum + 1);
                        vis[tmpx][tmpy] = false;
                    }
                }
            }
        }
    }
}