public class Solution {
public int maxArea(int[] height) {
int i=0,j=height.length-1;
int result=0;
while(i<j){
if(result<Math.min(height[i],height[j])*(j-i)){
result=Math.min(height[i],height[j])*(j-i);
}
if(height[i]<height[j])i++;else j--;
}
return result;
}
}
Monthly Archives: April 2013
Leetcode: First Missing Positive
public class Solution {
public int firstMissingPositive(int[] A) {
for(int i=0;i<A.length;i++){
while(A[i]-1>=0&&A[i]<=A.length&&A[A[i]-1]!=A[i]){
int t=A[i];
int temp=A[t-1];
A[t-1]=A[i];
A[i]=temp;
}
}
int i=0;
for(i=0;i<A.length;i++){
if(i+1!=A[i])break;
}
return i+1;
}
}
Leetcode: Jump Game
public boolean canJump(int[] A) {
int i=A.length-1;
while(i>0){
int j=0;
boolean hasNext=false;
for(j=0;j<i;j++){
if(A[j]+j>=i){
i=j;
hasNext=true;
break;
}
}
if(!hasNext)return false;
}
return true;
}
Leetcode: Jump Game II
思路：从最后一个开始，找到第一个能到最后的，再往前找第一个能到新的位置的，直到第0位：
public class Solution {
public int jump(int[] A) {
int i=A.length-1;
int step=0;
while(i>0){
for(int j=0;j<i;j++){
if(A[j]+j>=i){
step++;
i=j;
break;
}
}
}
return step;
}
}
Leetcode: Median of Two Sorted Arrays
用找第k个最小元素的方法求：
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
int l = A.length + B.length;
if (l % 2 == 0) {
return (find(A, 0, A.length, B, 0, B.length, l / 2) + find(A, 0, A.length, B, 0, B.length, l / 2 - 1)) / 2.0;
} else {
return find(A, 0, A.length, B, 0, B.length, l / 2);
}
}
// k = 0 means the first element
public int find(int A[], int as, int ae, int B[], int bs, int be, int k) {
if (as >= ae)
return B[bs + k];
if (bs >= be)
return A[as + k];
int am = (as + ae) / 2;
int bm = (bs + be) / 2;
//number of half elements including the middle elements
int h = am - as + bm - bs + 2;
if (A[am] < B[bm]) {
if (h > k + 1)
return find(A, as, ae, B, bs, bm, k);
else
return find(A, am + 1, ae, B, bs, be, k - (am - as + 1));
} else {
if (h > k + 1)
return find(A, as, am, B, bs, be, k);
else
return find(A, as, ae, B, bm + 1, be, k - (bm - bs + 1));
}
}
}