자바 와 알고리즘 (3)

자바 와 알고리즘 (3)
제목:
두 갈래 트 리 노드 를 다음 과 같이 정의 합 니 다. public class Node {public int value; public Node left; public Node right;

public Node(int data) {
        this.value = data;
    }
}

하나의 배열 의 MaxTree 정 의 는 다음 과 같다.
1. 배열 에 중복 요소 가 없습니다. 2 MaxTree 는 이 진 트 리 이 고 배열 의 모든 값 은 이 진 트 리 노드 에 대응 합 니 다.
3. MaxTree 나 무 를 포함 하고 그 중의 모든 나무 에서 가장 큰 노드 는 나무의 머리 입 니 다.
중복 요소 가 없 는 배열 arr 를 지정 하여 이 배열 을 만 드 는 MaxTree 함 수 를 작성 합 니 다. 배열 길이 가 N 이면 시간 복잡 도 는 O (N) 이 고 추가 공간 복잡 도 는 O (N) 입 니 다.

public class MaxTree {
	
	/*
	 *    
	 */
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Node getMaxTree(int[] arr) {
		Node[] nArr = new Node[arr.length];
		for (int i = 0; i != arr.length; i++) {
			nArr[i] = new Node(arr[i]);
		}
		Stack stack = new Stack();
		HashMap lBigMap = new HashMap();//                  
		HashMap rBigMap = new HashMap();//                  
		for (int i = 0; i != nArr.length; i++) {
			Node curNode = nArr[i];
			while ((!stack.isEmpty()) && stack.peek().value < curNode.value) {
				popStackSetMap(stack, lBigMap);
			}
			stack.push(curNode);
		}
		while (!stack.isEmpty()) {
			popStackSetMap(stack, lBigMap);
		}
	
		for (int i = nArr.length - 1; i != -1; i--) {
			Node curNode = nArr[i];
			while ((!stack.isEmpty()) && stack.peek().value < curNode.value) {
				popStackSetMap(stack, rBigMap);
			}
			stack.push(curNode);
		}
		while (!stack.isEmpty()) {
			popStackSetMap(stack, rBigMap);
		}
		Node head = null;
		for (int i = 0; i != nArr.length; i++) {
			Node curNode = nArr[i];
			Node left = lBigMap.get(curNode);
			Node right = rBigMap.get(curNode);
			if (left == null && right == null) {
				head = curNode;
			} else if (left == null) {
				if (right.left == null) {
					right.left = curNode;
				} else {
					right.right = curNode;
				}
			} else if (right == null) {
				if (left.left == null) {
					left.left = curNode;
				} else {
					left.right = curNode;
				}
			} else {
				Node parent = left.value < right.value ? left : right;
				if (parent.left == null) {
					parent.left = curNode;
				} else {
					parent.right = curNode;
				}
			}
		}
		return head;
	}

	public static void popStackSetMap(Stack stack, HashMap map) {
		Node popNode = stack.pop();
		if (stack.isEmpty()) {
			map.put(popNode, null);
		} else {
			map.put(popNode, stack.peek());
		}
	}
	
	/*
	 *     
	 */
	public static void printPreOrder(Node head) {
		if (head == null) {
			return;
		}
		System.out.print(head.value + " ");
		printPreOrder(head.left);
		printPreOrder(head.right);
	}

	/*
	 *     
	 */
	public static void printInOrder(Node head) {
		if (head == null) {
			return;
		}
		printPreOrder(head.left);
		System.out.print(head.value + " ");
		printPreOrder(head.right);
	}

	public static void main(String[] args) {
		int[] uniqueArr = { 3, 4, 5, 1, 2 };
		Node head = getMaxTree(uniqueArr);
		
		
		printPreOrder(head);
		System.out.println();
		printInOrder(head);

	}

}

제목:
하나의 정형 매트릭스 맵 을 지정 합 니 다. 그 중에서 0 과 1 두 가지 만 있 습 니 다. 그 중에서 모두 1 의 모든 사각형 구역 중 가장 큰 사각형 구역 은 1 의 수량 입 니 다.
예 를 들 면:
1,1,1,0
그 중 가장 큰 사각형 구역 은 3 개 1 이 므 로 3 으로 되 돌아 갑 니 다.
두 가지 해법:

public class MaximalRectangle {

	public static int maxRecSize(int[][] map) {
		if (map == null || map.length == 0 || map[0].length == 0) {
			return 0;
		}
		int maxArea = 0;
		int[] height = new int[map[0].length];
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
			}
			maxArea = Math.max(maxRecFromBottom(height), maxArea);
		}
		return maxArea;
	}

	public static int maxRecFromBottom(int[] height) {
		if (height == null || height.length == 0) {
			return 0;
		}
		int maxArea = 0;
		Stack stack = new Stack();
		for (int i = 0; i < height.length; i++) {
			while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
				int j = stack.pop();
				int k = stack.isEmpty() ? -1 : stack.peek();
				int curArea = (i - k - 1) * height[j];
				maxArea = Math.max(maxArea, curArea);
			}
			stack.push(i);
		}
		while (!stack.isEmpty()) {
			int j = stack.pop();
			int k = stack.isEmpty() ? -1 : stack.peek();
			int curArea = (height.length - k - 1) * height[j];
			maxArea = Math.max(maxArea, curArea);
		}
		return maxArea;
	}

	public static void main(String[] args) {
		int[][] map = { { 1, 0, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 0 }, };
		System.out.println(maxRecSize(map));
	}

}

public class Exam {
	static int width,height;
	static int max=0;
	public static void dg(int sz[][],int x,int y,int w,int h)
	{
		int num_1=0;
		for(int i=0;ifor(int j=0;jif(sz[x+i][y+j]==1)
			{
				num_1++;
			}
		}
		if((w*h)==num_1)
		{
			if(num_1>max)
			{
				max=num_1;
			}
			if(w+1+x<=width)
			{dg(sz,x,y,w+1,h);}
			if(h+1+y<=height)
			{dg(sz,x,y,w,h+1);}
		}
	}
	public static void main(String args[])
	{
		width=5;
		height=5;
		int shuzu[][]={{1,1,1,1,1}
					,  {1,0,1,0,1}
					,  {1,1,1,1,1}
					,  {1,1,1,0,1}
					,  {1,1,1,1,0}
		
						};
		for(int i=0;ifor(int j=0;j1,1);
		}
		System.out.print(max);
	}
}