package y2019.Algorithm.array.medium; /** * @ProjectName: cutter-point * @Package: y2019.Algorithm.array.medium * @ClassName: Trap * @Author: xiaof * @Description: TODO 42. Trapping Rain Water * Given n non-negative integers representing an elevation map where the width of each bar is 1, * compute how much water it is able to trap after raining. * * * * * * * * * * * * * * * * * * 0 1 2 3 4 5 6 7 8 9 0 1 * * * * Input: [0,1,0,2,1,0,1,3,2,1,2,1] * Output: 6 * * @Date: 2019/7/25 8:50 * @Version: 1.0 */ public class Trap { public int solution(int[] height) { //求出每个位置左边最大和右边最大的差值 int leftMax = 0, rightMax = 0, left = 0, right = height.length - 1, res = 0; while(left < right) { //当左边小于右边的时候 if(height[left] < height[right]) { //这里就是说明左边的高度比右边的小，永远能找到一个靠右的墙容纳水 //当左边位置小于右边位置，那么就获取当前位置能容纳多少水 leftMax = Math.max(leftMax, height[left]); //取出当前的左边最大值 //只要知道了左边的最大值,那么就计算差值 res += leftMax - height[left]; ++left; } else { //这里就是标识右边的高度比左边小，那么就可以计算右边容纳的水 //左边不用考虑，肯定有比这个大的，右边只需要考虑更右边的最大值即可 rightMax = Math.max(height[right], rightMax); res += rightMax - height[right]; --right; } } return res; } public int solution1(int[] height) { //从第一个位置开始每个阶段位置宽度都是1，然后当遇到第一个不相等的高度的时候，就可以计算单位 //两高夹一矮就是容水量 int res = 0, mx = 0, n = height.length; int[] dp = new int[n]; //第一遍取每一步的当前最大值 for (int i = 0; i < n; ++i) { dp[i] = mx; mx = Math.max(mx, height[i]); } mx = 0; //第二遍遍历，每次取右边的每一步最小值， for (int i = n - 1; i >= 0; --i) { dp[i] = Math.min(dp[i], mx); // 去最大值的之间的小值 //取当前位置的右边最大值 mx = Math.max(mx, height[i]); //相减值大于0，计算结果差值 if (dp[i] - height[i] > 0) res += dp[i] - height[i]; } return res; } }
package y2019.Algorithm.array.medium; import java.util.HashMap; import java.util.Map; /** * @ProjectName: cutter-point * @Package: y2019.Algorithm.array.medium * @ClassName: LongestConsecutive * @Author: xiaof * @Description: TODO 128. Longest Consecutive Sequence * Given an unsorted array of integers, find the length of the longest consecutive elements sequence. * Your algorithm should run in O(n) complexity. * * Input: [100, 4, 200, 1, 3, 2] * Output: 4 * Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. * * 给定一个未排序的整数数组，找出最长连续序列的长度。 * 要求算法的时间复杂度为 O(n)。 * * @Date: 2019/7/25 9:56 * @Version: 1.0 */ public class LongestConsecutive { public int solution(int[] nums) { //未排序的数组，求最长连续的序列 //用map存放进入当前值，第二个参数是序列长度，当前值的n-left就是这个序列的开始的位置的值，当前值n+right是这个序列结束的位置 int res = 0; Map<Integer, Integer> map = new HashMap<>(); for(int n : nums) { //遍历所有数据 if(!map.containsKey(n)) { //判断map是否包含左边的数据，和右边的数据 int leftSeqLen = map.containsKey(n - 1) ? map.get(n - 1) : 0; //判断是否包含n-1，如果不包含，那就是0 int rightSeqLen = map.containsKey(n + 1) ? map.get(n + 1) : 0; int sum = leftSeqLen + rightSeqLen + 1; //吧两边连起来 //放进去数据 map.put(n, sum); res = Math.max(res, sum); //扩展长度为对应的值,按理说中间的数据也应该更新数据，但是这里重复的数据也不会继续执行 //那么只需要更新两端的数据即可 map.put(n - leftSeqLen, sum); map.put(n + rightSeqLen, sum); } else { //如果已经存在这个数了 continue; } } return res; } public static void main(String[] args) { int data[] = { 100, 4, 200, 1, 3, 2}; LongestConsecutive fuc = new LongestConsecutive(); fuc.solution(data); System.out.println(); } }