便利蜂4.10笔试题Java（全AC）

第一题剑指offer原题最大子序列和

package 便利蜂;

import java.util.Scanner;

public class 子序列最大和 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String[] arr = sc.nextLine().split(",");
		System.out.println(maxSum(arr));
	}

	private static int maxSum(String[] arr) {
		int sum = 0;
		int res = 0;
		for(String str: arr) {
			int num = Integer.valueOf(str);
			sum = Math.max(num, sum+num);
			res = Math.max(sum, res);
		}
		return res;
	}

}

第二题半小时做了个有向图用个HashMap保存节点映射方便查询 DFS获得路径放进ArrayList里最后打印出来

package 便利蜂;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

public class 高老庄 {
	
	private HashMap<String, Address> map = new HashMap();;
	private ArrayList<Address> res;
	
	class Address{
		private String addressName;
		private boolean isReached = false;
		private Address east;
		private Address west;
		private Address north;
		private Address south;
		public Address(String addressName) {
			this.addressName = addressName;
		}
	}
	

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		String[] arr = sc.nextLine().split(",");
		
		高老庄 main = new 高老庄();
		main.generateMap();
		main.findPath(arr[0], arr[1]);
		
		main.printPath();
	}
	
	private void printPath() {
		for(int i=1; i<res.size(); i++) {
			Address cur = res.get(i);
			Address pre = res.get(i-1);
			if(pre.north == cur) System.out.print("north");
			else if(pre.south == cur) System.out.print("south");
			else if(pre.west == cur) System.out.print("west");
			else if(pre.east == cur) System.out.print("east");
			if(i != res.size()-1) System.out.print(",");
		}
	}

	public void findPath(String wukong, String bajie) {
		Address start = map.get(wukong);
		Address end = map.get(bajie);
		ArrayList<Address> path = new ArrayList();
		path.add(start);
		start.isReached = true;
		dfs(start, end, path);
	}
	
	private void dfs(Address start, Address end, ArrayList<Address> path) {
		
		if(start == end) {
			if(res == null || path.size() < res.size()) {
				res = new ArrayList(path);
			}
			return;
		}
		int isEnd = 0;
				
		if(start.north != null && !start.north.isReached) {
			path.add(start.north);
			start.north.isReached = true;
			dfs(start.north, end, path);
			path.remove(path.size()-1);
			start.north.isReached = false;
		}
		if(start.south != null && !start.south.isReached) {
			start.south.isReached = true;
			path.add(start.south);
			dfs(start.south, end, path);
			path.remove(path.size()-1);
			start.south.isReached = false;
		}
		if(start.west != null && !start.west.isReached) {
			start.west.isReached = true;
			path.add(start.west);
			dfs(start.west, end, path);
			path.remove(path.size()-1);
			start.west.isReached = false;
		}
		if(start.east != null && !start.east.isReached) {
			start.east.isReached = true;
			path.add(start.east);
			dfs(start.east, end, path);
			path.remove(path.size()-1);
			start.east.isReached = false;
		}
		
	}

	public void generateMap() {
		Address DAOTIAN1 = new Address("DAOTIAN1");
		Address TULU1 = new Address("TULU1");
		Address DAOTIAN = new Address("DAOTIAN");
		Address TULU = new Address("TULU");
		Address CUNKOU = new Address("CUNKOU");
		Address NONGSHE = new Address("NONGSHE");
		Address TULU2 = new Address("TULU2");
		Address JIEDAO = new Address("JIEDAO");
		Address TIEPU = new Address("TIEPU");
		Address LIUJIABUDIAN = new Address("LIUJIABUDIAN");
		Address JIEDAO1 = new Address("JIEDAO1");
		Address XIAOJIUGUAN = new Address("XIAOJIUGUAN");
		Address ZHANGFANG = new Address("ZHANGFANG");
		Address PIANTING = new Address("PIANTING");
		Address GUIGE = new Address("GUIGE");
		Address YASHI = new Address("YASHI");
		Address HUAYUAN = new Address("HUAYUAN");
		Address HOUYUAN = new Address("HOUYUAN");
		Address ZHENGTING = new Address("ZHENGTING");
		Address ZHENGYUAN = new Address("ZHENGYUAN");
		Address GAOJIADAYUAN = new Address("GAOJIADAYUAN");
		Address JIEDAO2 = new Address("JIEDAO2");
		Address PIANFANG = new Address("PIANFANG");
		Address FANTING = new Address("FANTING");
		Address XIYIFANG = new Address("XIYIFANG");
		Address TULU3 = new Address("TULU3");
		Address QINGSHILU = new Address("QINGSHILU");
		
		DAOTIAN1.south = TULU1;
		TULU1.north = DAOTIAN1;
		TULU1.south = DAOTIAN;
		DAOTIAN.north = TULU1;
		DAOTIAN.south = TULU;
		TULU.north = DAOTIAN;
		TULU.south = CUNKOU;
		CUNKOU.north = TULU;
		CUNKOU.east = NONGSHE;
		NONGSHE.west = CUNKOU;
		TULU1.east = TULU2;
		TULU2.west = TULU1;
		TULU2.east = JIEDAO;
		JIEDAO.west = TULU2;
		LIUJIABUDIAN.south = JIEDAO;
		JIEDAO.north = LIUJIABUDIAN;
		JIEDAO.south = TIEPU;
		TIEPU.north = JIEDAO;
		JIEDAO.east = JIEDAO1;
		JIEDAO1.west = JIEDAO;
		JIEDAO1.south = XIAOJIUGUAN;
		XIAOJIUGUAN.north = JIEDAO1;
		YASHI.south = GUIGE;
		GUIGE.north = YASHI;
		GUIGE.east = HOUYUAN;
		HOUYUAN.west = GUIGE;
		PIANTING.east = ZHENGTING;
		ZHENGTING.west = PIANTING;
		ZHANGFANG.east = ZHENGYUAN;
		ZHENGYUAN.west = ZHANGFANG;
		JIEDAO1.east = GAOJIADAYUAN;
		GAOJIADAYUAN.west = JIEDAO1;
		HUAYUAN.south = HOUYUAN;
		HOUYUAN.north = HUAYUAN;
		HOUYUAN.south = ZHENGTING;
		ZHENGTING.north = HOUYUAN;
		ZHENGYUAN.north = ZHENGTING;
		ZHENGTING.south = ZHENGYUAN;
		ZHENGYUAN.south = GAOJIADAYUAN;
		GAOJIADAYUAN.north = ZHENGYUAN;
		HOUYUAN.east = XIYIFANG;
		XIYIFANG.west = HOUYUAN;
		ZHENGTING.east = FANTING;
		FANTING.west = ZHENGTING;
		ZHENGYUAN.east = PIANFANG;
		PIANFANG.west = ZHENGYUAN;
		GAOJIADAYUAN.east = JIEDAO2;
		JIEDAO2.west = GAOJIADAYUAN;
		JIEDAO2.east = TULU3;
		TULU3.west = JIEDAO2;
		TULU3.east = QINGSHILU;
		QINGSHILU.west = TULU3;
		
		
		map.put("DAOTIAN1", DAOTIAN1);
		map.put("TULU1", TULU1);
		map.put("DAOTIAN", DAOTIAN);
		map.put("TULU", TULU);
		map.put("CUNKOU", CUNKOU);
		map.put("NONGSHE", NONGSHE);
		map.put("TULU2", TULU2);
		map.put("LIUJIABUDIAN", LIUJIABUDIAN);
		map.put("JIEDAO", JIEDAO);
		map.put("TIEPU", TIEPU);
		map.put("YASHI", YASHI);
		map.put("GUIGE", GUIGE);
		map.put("PIANTING", PIANTING);
		map.put("ZHANGFANG", ZHANGFANG);
		map.put("JIEDAO1", JIEDAO1);
		map.put("XIAOJIUGUAN", XIAOJIUGUAN);
		map.put("HUAYUAN", HUAYUAN);
		map.put("HOUYUAN", HOUYUAN);
		map.put("ZHENGTING", ZHENGTING);
		map.put("ZHENGYUAN", ZHENGYUAN);
		map.put("GAOJIADAYUAN", GAOJIADAYUAN);
		map.put("XIYIFANG", XIYIFANG);
		map.put("FANTING", FANTING);
		map.put("PIANFANG", PIANFANG);
		map.put("JIEDAO2", JIEDAO2);
		map.put("TULU3", TULU3);
		map.put("QINGSHILU", QINGSHILU);	
	}
}

第三题简单的DFS吧，但是我觉得应该有更好的方法，DFS还是有点太蠢了

package 便利蜂;

import java.util.Scanner;

public class 运送货物 {
	
	private static int res = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] arr = sc.nextLine().split(",");
		dfs(arr, 0, 0);
		if(res == Integer.MAX_VALUE){
            System.out.println(-1);
        }else{
			System.out.println(res);
        }
	}

	private static void dfs(String[] arr, int index, int times) {
		if(index + 1 >  arr.length) return;
		if(index + 1 == arr.length) {
			res = times < res ? times: res;
			return;
		}
		int oil = Integer.valueOf(arr[index]);
		for(int i=index+1; i <= index+oil; i++) {
			times++;
			dfs(arr, i, times);
			times--;
		}
	}

}

#便利蜂##笔试题目##Java工程师#