Leetcode个人刷题思路和自我督促贴

jaly50 · 2014-12-28 13:06:07

import java.util.HashMap;
import java.util.Map;
/*
* LeetCode 155 Minimum Window Substring
* Given a string S and a string T,
* find the minimum window in S which will contain all the characters in T in complexity O(n).
* @author: Scarlett Chen
* @date: 12/27/2014 Sat 8:36 PM
* Time: o(2n)
* space: o(n)
* 思路：记录minWindow的开始点sb,每次匹配完T的值后，删掉第一个点，继续往后找，直到T再次匹配完全。
* 每次完全匹配时，更新minWindown是否有更小。
*/
public class MinWindow {
public static String minWindow(String S, String T) {
Map<Character,Integer> map = new HashMap<Character, Integer>();
String minWindow = S;
if (T.length()> S.length()) return "";
if (T.equals(S)) return minWindow;
int count = T.length();
for (int i=0; i<count; i++) {
char ch = T.charAt(i);
if (map.containsKey(ch)) {
map.put(ch, map.get(ch)-1);
}
else map.put(ch, -1);
}
int sb = -1;
boolean ansExist = false;
for (int i=0; i<S.length(); i++ ) {
char ch = S.charAt(i);
if (map.containsKey(ch)) {
System.out.println(ch);
//First beginning of the window
if (sb==-1) sb = i;
map.put(ch, map.get(ch)+1);
if (map.get(ch)<=0)
count--;
while (count==0) {
ansExist = true;
minWindow =i-sb+1 <minWindow.length() ? S.substring(sb,i+1): minWindow;
ch = S.charAt(sb);
// if (map.containsKey(ch)) must contain, since sb is the begining of the minwindow
map.put(ch, map.get(ch)-1);
if (map.get(ch)<0) count++;
sb++;
while (sb <= S.length()-T.length() && !map.containsKey(S.charAt(sb)))
sb++;
if (sb>S.length()-T.length()) return minWindow;
}
}
}
return ansExist? minWindow: "";
}
public static void main(String[] args) {
System.out.println(minWindow("bdab","ab"));
}
}

复制代码

jaly50 · 2014-12-28 16:06:44

import java.util.Stack;
/*
* @Author: Scarlett Chen
* @date: 12/27/2014 Sat 11:42 PM
* LeetCode 156 Largest Rectangle in Histogram
* 1. o(n^2) + 剪枝可过
* 2. 线段树，维护线段之中的最小值 + 分治 recursive 可过 http://www.geeksforgeeks.org/largest-rectangular-area-in-a-histogram-set-1/
* 3. 用栈保持递增序列
* 这个讲得特别好：http://blog.csdn.net/doc_sgl/article/details/11805519
*/
public class LargestRectangleArea {
public int largestRectangleArea(int[] height) {
Stack<Integer> stack = new Stack<Integer>();
int n = height.length;
if (n<1) return 0;
int largest = height[0];
for (int i=0; i<=n; i++) {
int curHeight = i==n? 0: height[i];
while (!stack.isEmpty() && height[stack.peek()] > curHeight) {
int index = stack.pop();
/*
* 拿 0 3 2 5 举例
* 之所以要i-stack.peek()-1
* 是因为在入栈时，2<3,所以3被踢掉了。但在算2为高度的最大面积时
* 就要算从栈内的 0 后面一位直到i：这距离就是 i-stack.peek()【就是0 +1
*/
int curArea = height[index] * (stack.isEmpty()? i:i-stack.peek()-1);
largest = Math.max(largest, curArea);
}
stack.push(i);
}
return largest;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}

复制代码

jaly50 · 2014-12-28 16:47:14

import java.util.Stack;
/*
* LeetCode 157 Maximal Rectangle
* @Author: Scarlett Chen
* @date: 12/28/2014 Sun 12:44 AM
* o(n*m) 有些想法自己怎么就是想不到呢~
* 就是largestRectangle的多层版！！对每一行都进行栈的维护，作为底边，找最大rectangle!
*/
public class MaxRectangle {
public static int maximalRectangle(char[][] matrix) {
int n = matrix.length;
if (n <1) return 0;
int m = matrix[0].length;
//+1 is the fake final one
// to maintain the height of each col when their base is the current row
int[] height = new int[m+1];
height[m] =0 ; // the fake one for the stack maintainance
Stack<Integer> stack = new Stack<Integer>();
int h,row,largest=0,curArea=0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
//Set the height attributes
h = 0;
row = i;
while (row>=0 &&matrix[row][j]=='1') {
row--;
h++;
}
height[j] = h;
}
for (int j=0; j<=m; j++) {
//Get the maximum rectangle area by stack
while (!stack.isEmpty() && height[stack.peek()] > height[j]) {
h = stack.pop();
curArea = height[h] * (stack.isEmpty()? j: j-stack.peek()-1);
largest = Math.max(curArea, largest);
}
stack.push(j);
}
stack.removeAllElements();
}
return largest;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(maximalRectangle(new char[][] {{'1'}} ));
}
}

复制代码

jaly50 · 2014-12-29 02:21:52

/*
* Leetcode 158
* @author: Scarlett Chen
* @date: 12/28/2014 Sun 10:19 AM
* Time(n) easy
* 一开始的想法就是换进制，换成26进制数嘛。
* 但是需要注意的是，这里的数从1-26.和之前从0-n-1是不一样的~ 所以我们手动把数转成n-1
*/
public class ConvertToTitle {
public static String convertToTitle(int n) {
StringBuffer s = new StringBuffer();
char[] tablet = new char[26];
for (int i=0; i<tablet.length; i++)
tablet[i]=(char) ('A'+i);
int carry=0;
while (n>0) {
carry = (n-1) % 26;
n = (n-1)/ 26;
s.insert(0,tablet[carry]);
}
return s.toString();
}
public static void main(String args[]) {
System.out.println(convertToTitle(1));
}
}

复制代码

jaly50 · 2014-12-29 06:42:48

import java.util.Arrays;
/*
* LeetCode 161 Maximum Gap
* @author: Scarlett chen
* @date: 12/28/2014 Sun 2:40
* 找到(max-min)/(n-1) 根据平均差装箱
*/
public class MaximumGap {
public static int maximumGap(int[] num) {
//Get the average distance between two successive elements
int n = num.length;
if (n<2) return 0;
int max= num[0], min = num[0];
// get Max and min in the array
for (int i:num) {
max = i>max? i:max;
min = i<min? i:min;
}
//必须是ceil,否则 min*aveDis(n-1)会小于最大值的~后面就会溢出
int aveDis =(int)(Math.ceil((double)(max-min)/(n-1)));
if (aveDis==0) return 0; // all numbers are same value
// put elements into array based on the average distance
int[] maxA= new int[n+1], minA = new int[n+1];
Arrays.fill(maxA, -1);
Arrays.fill(minA, -1);
int index = 0;
for (int e:num) {
index = (e-min)/aveDis;
if (maxA[index]==-1)
maxA[index] = e;
else maxA[index] = e>maxA[index]? e: maxA[index];
if (minA[index]==-1)
minA[index] = e;
else minA[index] = e< minA[index]? e: minA[index];
}
int gap = 0;
int gapLeft=min, gapRight=0;// left would be maxA[i-1], right is minA[i]
for (int i=0; i<= n; i++) {
if (minA[i]!=-1)
gapRight = minA[i];
gap = Math.max(gap, gapRight-gapLeft);
if (maxA[i]!=-1)
gapLeft = maxA[i];
}
return gap;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(maximumGap(new int[]{}));
}
}

复制代码

jaly50 · 2014-12-29 12:30:00

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
/*
* LeetCode 163 Fraction to Recurring Decimal
* @author : Scarlett chen
* @date: 12/28/2014 Sun 8:10 PM
* 需要注意的地方：符号，整数部分为零的时候符号
* 极值情况如 -2147483648 的余数，商都有可能超过整数范围
* 【最后一道leetCode 好激动！任务圆满完成！
*/
public class FractionToDecimal {
public static String fractionToDecimal(int numerator, int denominator) {
long remainder, num;
// the long is for :fractionToDecimal(-2147483648,-1)
long intPart = (long)numerator/ denominator;
remainder = numerator % denominator;
if (remainder ==0) return String.valueOf(intPart);
//if the ans is not zero, the sign has already been given.
StringBuffer ans = new StringBuffer(String.valueOf(intPart));
ans.append('.');
long fractionPart = 0;
//consider the zero situation
if (Math.signum(remainder)*Math.signum(denominator) <0 && intPart==0) ans.insert(0, "-");
remainder = Math.abs(remainder);
//the long is for fractionToDecimal(-1,-2147483648)
long den = Math.abs((long)denominator);
Map<Long,Integer> map = new HashMap<Long,Integer>();
while (remainder!=0) {
map.put(remainder,ans.length());
num = remainder * 10;
fractionPart = num / den;
remainder = num % den;
ans.append(fractionPart);
if (map.containsKey(remainder)) {
ans.append(')');
ans.insert(map.get(remainder), "(");
return ans.toString();
}
}
return ans.toString();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(fractionToDecimal(-2147483648,-1));
}
}

复制代码

mnmunknown · 2014-12-31 02:05:13

也在刷leetcode，和楼主共勉

[Leetcode] Leetcode个人刷题思路和自我督促贴

浏览过的版块