题目一
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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1]
, return 6
.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
这里计算面积不用一般几何书的方法,这里是两边往中间遍历,记录当前第二高点secHight,然后利用这个第二高点减去当前历经的柱子,剩下就装水容量了。
为什么是第二高点?因为两边比较,最高的点不用动,只移动第二高点。
第一个思路,按照上图的思想就能写出非常简洁的程序了,时间复杂度为O(n):
int trap(int A[], int n) { int secHight = 0; int left = 0; int right = n-1; int area = 0; while (left < right){ if (A[left] < A[right]){ secHight = max(A[left], secHight); area += secHight-A[left];//计算当前格的能装雨水的容量 left++; } else { secHight = max(A[right], secHight); area += secHight-A[right]; right--; } } return area; }
题目二
Given a number, can you remove k digits from the number so that the new
formatted number is smallest possible.
input: n = 1432219, k = 3
output: 1219
public class Solution { public static void main(String[] args){ System.out.print(get_smallest("63534",2)); } public static String get_smallest(String n, int k){ int len=n.length()-k;//最后的序列长 int index=0; int temp=0; String result="";//输出结果 for(int i=0;i<len;i++){ int min=9; for(int j=index;j<=n.length()-len+i;j++){ if(Integer.parseInt(String.valueOf(n.charAt(j)))<min){ index=j+1; min=Integer.parseInt(String.valueOf(n.charAt(j))); } } result+=min+""; } return result; } }
题目三
第一题:Median of Two Sorted Arrays
public class Solution { public static void main(String[] args){ int[] list1={1,5,8,8,9}; int[] list2={2,7,7}; System.out.print(get_median(list1,list2)); } public static int get_median(int[] list1,int[] list2){ int len1=list1.length; int len2=list2.length; if(len1==0 && len2==0) return 0; if(len1==0) return list2[len2/2]; if(len2==0) return list1[len1/2]; int median=(len1+len2)/2-2; int index_1=0; int index_2=0; int result=Integer.MIN_VALUE; while(index_1+index_2<=median && index_1<len1 && index_2<len2){ if(list1[index_1]<=list2[index_2]){ result=list2[index_2]; index_1++; } else{ result=list1[index_1]; index_2++; } } if(index_1+index_2-1==median){ return result; } else{ if(index_1==len1){ return list2[median-len1]; } else{ return list1[median-len2]; } } } }
/********************************
* 本文来自博客 “李博Garvin“
* 转载请标明出处:http://blog.csdn.net/buptgshengod
******************************************/