第19天--算法（Leetcode 38,41,42）
38.外观数列
public String countAndSay(int n) { if(n < 1) { return ""; } if(n == 1) { return "1"; } char[] pre = countAndSay(n - 1).toCharArray(); int times = 1; StringBuilder sb = new StringBuilder(); for(int i = 1;i < pre.length;i ++) { if(pre[i - 1] == pre[i]) { times ++; }else { sb.append(times); sb.append(pre[i - 1]); times = 1; } } sb.append(times); sb.append(pre[pre.length - 1]); return sb.toString(); } 41.缺失的第一个正数 public int firstMissingPositive(int[] nums) { int left = 0; int right = nums.length; while(left < right) { if(nums[left] == left + 1) { left ++; }else if(nums[left] <= left || nums[left] > right || nums[nums[left] - 1] == nums[left]) { swap(nums,left,-- right); }else { swap(nums,left,nums[left] - 1); } } return left + 1; } public void swap(int arr[],int x,int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } 42.接雨水 public int trap(int[] height) { if(height == null || height.length < 3) { return 0; } int N = height.length; int L = 1; int R = N - 2; int leftMax = height[0]; int rightMax = height[N - 1]; int res = 0; while(L <= R) { if(leftMax <= rightMax) { res += leftMax - height[L] < 0 ? 0 : leftMax - height[L]; leftMax = Math.max(leftMax,height[L]); L ++; }else { res += rightMax - height[R] < 0 ? 0 : rightMax - height[R]; rightMax = Math.max(rightMax,height[R]); R --; } } return res; }