EMC面试题

第一次拿使剩下的是另一堆个数-1。

第一题博弈论
第二题深度优先搜索

第二题算法：

节点类

package model;

import java.util.ArrayList;
import java.util.List;

public class Node {

	private String value = "";
	
	private Node parent = null;
	
	private List<Node> children = new ArrayList<Node>();
	
	private boolean isHandled = false;

	public Node(String value){
		this.value = value;
	}
	
	public Node(String value, Node parent){
		this.value = value;
		this.parent = parent;
	}
	
	public String getValue() {
		return value;
	}

	public void setValue(String value) {
		this.value = value;
	}

	public Node getParent() {
		return parent;
	}

	public void setParent(Node parent) {
		this.parent = parent;
	}

	public List<Node> getChildren() {
		return children;
	}

	public void addChild(Node child){
		this.children.add(child);
	}

	public boolean isHandled() {
		return isHandled;
	}

	public void setHandled(boolean isHandled) {
		this.isHandled = isHandled;
	}
}

树构造类

package model;

import java.util.ArrayList;
import java.util.List;


public class TreeFactory {

	/*
	 * 0 => " "
	 * 1 => ""
	 * 2 => "a,b,c"
	 * 3 => "d,e,f"
	 * 4 => "g,h,i"
	 * 5 => "j,k,l"
	 * 6 => "m,n,o"
	 * 7 => "p,q,r,s"
	 * 8 => "t,u,v"
	 * 9 => "w,x,y,z"
	 */
	private static List<Node> createNodes(String number){
		List<Node> ret = new ArrayList<Node>();
		if(number != null && !number.trim().equals("")){
			if (number.equals("0")){
				ret.add(new Node(" "));
			} else if (number.equals("1")){
				ret.add(new Node(""));
			} else if (number.equals("2")){
				ret.add(new Node("a"));
				ret.add(new Node("b"));
				ret.add(new Node("c"));
			} else if (number.equals("3")){
				ret.add(new Node("d"));
				ret.add(new Node("e"));
				ret.add(new Node("f"));
			} else if (number.equals("4")){
				ret.add(new Node("g"));
				ret.add(new Node("h"));
				ret.add(new Node("i"));
			} else if (number.equals("5")){
				ret.add(new Node("j"));
				ret.add(new Node("k"));
				ret.add(new Node("l"));
			} else if (number.equals("6")){
				ret.add(new Node("m"));
				ret.add(new Node("n"));
				ret.add(new Node("o"));
			} else if (number.equals("7")){
				ret.add(new Node("p"));
				ret.add(new Node("q"));
				ret.add(new Node("r"));
				ret.add(new Node("s"));
			} else if (number.equals("8")){
				ret.add(new Node("t"));
				ret.add(new Node("u"));
				ret.add(new Node("v"));
			} else if (number.equals("9")){
				ret.add(new Node("w"));
				ret.add(new Node("x"));
				ret.add(new Node("y"));
				ret.add(new Node("z"));
			}
		}
		return ret;
	}
	
	public static Node createGraph(String str){
		Node root = new Node("", null);
		if (str == null || str.trim().equals("")){
			return root;
		}
		char[] characters = str.trim().toCharArray();
		List<Node> lastLeafs = new ArrayList<Node>();
		lastLeafs.add(root);
		List<Node> cacheNodes = new ArrayList<Node>();
		for (char character : characters){
				for (Node leaf : lastLeafs){
					List<Node> nodes = createNodes(new String(new char[]{character}));
					for (Node newNode : nodes){
						newNode.setParent(leaf);
						leaf.addChild(newNode);
					}
					cacheNodes.addAll(nodes);
				}
			lastLeafs.clear();
			lastLeafs.addAll(cacheNodes);
			cacheNodes.clear();
		}
		return root;
	}
}

深度优先搜索

package dfs;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import model.TreeFactory;
import model.Node;

public class DeepFirstSearch {

	private Stack<Node> stack = new Stack<Node>();
	
	private List<String> ret = new ArrayList<String>();
	
	public static void main(String[] args) {
		String input = "2345";
		List<String> ret = new DeepFirstSearch().getAllPossibleString(input);
		if (ret.size() > 0){
			for (String str : ret){
				System.out.println(str);
			}
		}
	}
	
	public List<String> getRet(){
		return this.ret;
	}

	public List<String> getAllPossibleString(String input){
		Node root = TreeFactory.createGraph(input);
		this.stack.push(root);
		while (this.stack.size() > 0){
			handleNode(this.stack.peek());
		}
		return this.ret;
	}
	
	private void handleNode(Node node){
		if (node.getChildren().size() > 0){
			boolean isHandled = true;
			for (Node child: node.getChildren()){
				this.stack.push(child);
				if (!child.isHandled()){
					handleNode(child);
				}
				isHandled = isHandled && child.isHandled();
			}
			node.setHandled(isHandled);
			if (isHandled){
				this.stack.pop();
			}
		} else {
			node.setHandled(true);
			this.stack.pop();
			String str = "";
			for (int i = 0, j = this.stack.size(); i < j; i++){
				String value = this.stack.get(i).getValue();
				str = str.concat(value == null ? "" : value);
			}
			str = str.concat(node.getValue() == null ? "" : node.getValue());
			if (!this.ret.contains(str) && !"".equals(str)){
				this.ret.add(str);
			}
		}
	}
}

也可以不用深度优先搜索，比较简单的可以用以下方法：
1. 将数字的字符串转换成一棵树。
2. 然后找到树的所有叶节点。
3. 根据每个叶节点找到其父节点，以及父节点的父节点，直到找到根节点为止，这样一个可能的字符串就找到了

4拿3 ，7拿6 从左向右 或 从右向左 执行  完胜

......  表示不理解你说的..或者是你说的太高深了~  别人要是一次拿完一堵 怎么办~   看前面~

第一次从4堆或7堆中拿 保证所拿堆只有两个  剩下只要你不拿得某堆只剩一个你就赢 了 

从7个中拿3个，这样他拿多少，你都赢了

只要保证堆能剩2个就行，4拿2

这不是深度优先么？

另一边可以全部被对方拿走