LeetCode：输出整体轮廓线和最长子数组长度

系统管理员 2023-06-23 07:58 18阅读 0赞

# LeetCode：描述轮廓线和最长子数组长度 #

--------------------

## 目录： ##

1.  输出整体轮廓线
2.  返回最长子数组长度
3.  求数组中奇数和偶数个数相同的最长子数组

--------------------

### 1. 输出整体轮廓线 ###

给定一个N行3列二维数组， 每一行表示有一座大楼， 一共有N座大楼。 所有大楼的底部都坐落在X轴上， 每一行的三个值(a,b,c)代表每座大楼的从(a,0)点开始， 到 (b,0)点结束， 高度为c。 输入的数据可以保证a<b,且a， b， c均为正数。 大楼之间可以有重合。 请输出整体的轮廓线。

例子： 给定一个二维数组 \[ \[1, 3, 3\], \[2, 4, 4\], \[5, 6,1\] \]  
输出为轮廓线 \[ \[1, 2, 3\], \[2, 4, 4\], \[5, 6, 1\] \]

public static class Node {
        
    		public boolean isUp;
    		public int posi;
    		public int h;
    
    		public Node(boolean bORe, int position, int height) {
        
    			isUp = bORe;
    			posi = position;
    			h = height;
    		}
    	}
    
    	public static class NodeComparator implements Comparator<Node> {
        
    		@Override
    		public int compare(Node o1, Node o2) {
        
    			if (o1.posi != o2.posi) {
        				
    				return o1.posi - o2.posi;
    			}
    			if (o1.isUp != o2.isUp) {
        
    				return o1.isUp ? -1 : 1;
    			}
    			return 0;
    		}
    	}
    
    	public static List<List<Integer>> buildingOutline(int[][] buildings) {
        
    		Node[] nodes = new Node[buildings.length * 2];
    		for (int i = 0; i < buildings.length; i++) {
        
    			nodes[i * 2] = new Node(true, buildings[i][0], buildings[i][2]);
    			nodes[i * 2 + 1] = new Node(false, buildings[i][1], buildings[i][2]);
    		}
    		Arrays.sort(nodes, new NodeComparator());
    		TreeMap<Integer, Integer> htMap = new TreeMap<>();
    		TreeMap<Integer, Integer> pmMap = new TreeMap<>();
    		for (int i = 0; i < nodes.length; i++) {
        
    			if (nodes[i].isUp) {
        
    				if (!htMap.containsKey(nodes[i].h)) {
        
    					htMap.put(nodes[i].h, 1);
    				} else {
        
    					htMap.put(nodes[i].h, htMap.get(nodes[i].h) + 1);
    				}
    			} else {
        
    				if (htMap.containsKey(nodes[i].h)) {
        
    					if (htMap.get(nodes[i].h) == 1) {
        
    						htMap.remove(nodes[i].h);
    					} else {
        
    						htMap.put(nodes[i].h, htMap.get(nodes[i].h) - 1);
    					}
    				}
    			}
    			if (htMap.isEmpty()) {
        
    				pmMap.put(nodes[i].posi, 0);
    			} else {
        
    				pmMap.put(nodes[i].posi, htMap.lastKey());
    			}
    		}
    		List<List<Integer>> res = new ArrayList<>();
    		int start = 0;
    		int height = 0;
    		for (Entry<Integer, Integer> entry : pmMap.entrySet()) {
        
    			int curPosition = entry.getKey();
    			int curMaxHeight = entry.getValue();
    			if (height != curMaxHeight) {
        
    				if (height != 0) {
        
    					List<Integer> newRecord = new ArrayList<Integer>();
    					newRecord.add(start);
    					newRecord.add(curPosition);
    					newRecord.add(height);
    					res.add(newRecord);
    				}
    				start = curPosition;
    				height = curMaxHeight;
    			}
    		}
    		return res;
    	}

--------------------

### 2. 返回最长子数组长度 ###

**题目描述**：给定一个数组arr， 和一个整数num， 求在arr中， 累加和等于num的最长子数组的长度

例子：  
arr = \{7,3,2,1,1,7,7,7\} num = 7  
其中有很多的子数组累加和等于7， 但是最长的子数组是\{3,2,1,1\}， 所以返回其长度4

**题解**：创建一个HashMap，key保存从0位置开始到每个位置的长度，value 保存出现长度的位置。如果sum-aim的结果出现在map中，则说明有这个长度，获取长度即可。如果没有出现过，保存在 map 中即可。

public static int maxLength(int[] arr, int aim) {
        
    		if (arr == null || arr.length == 0) {
        
    			return 0;
    		}
    		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    		map.put(0, -1); // important
    		int len = 0;
    		int sum = 0;
    		for (int i = 0; i < arr.length; i++) {
        
    			sum += arr[i];
    			if (map.containsKey(sum - aim)) {
        
    				len = Math.max(i - map.get(sum - aim), len);
    			}
    			if (!map.containsKey(sum)) {
        
    				map.put(sum, i);
    			}
    		}
    		return len;
    	}

--------------------

### 3. 求数组中奇数和偶数个数相同的最长子数组 ###

用动态划分思想，最后一个位置的数肯定会被划分，那么就有两种可能

1.  最后一个数所在部分不是异或和为 0 的子数组，那么 dp\[i\] = dp\[i-1\]
2.  最后一个数所在部分是异或和为 0 的子数组，那么 dp\[i\] = dp\[k-1\] +1

public static int mostEOR(int[] arr) {
        
    		int ans = 0;
    		int xor = 0;
    		int[] dp = new int[arr.length];
    		HashMap<Integer, Integer> map = new HashMap<>();
    		map.put(0, -1);
    		for (int i = 0; i < arr.length; i++) {
        
    			xor ^= arr[i];
    			if (map.containsKey(xor)) {
        
    				int pre = map.get(xor);
    				dp[i] = pre == -1 ? 1 : (dp[pre] + 1);
    			}
    			if (i > 0) {
        
    				dp[i] = Math.max(dp[i - 1], dp[i]);
    			}
    			map.put(xor, i);
    			ans = Math.max(ans, dp[i]);
    		}
    		return ans;
    	}