便利蜂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--;
}
}
}
投递蚂蚁集团等公司10个岗位 >
