public class Solution {
public String addBinary(String a, String b) {
StringBuilder sb=new StringBuilder();
int i=a.length()-1,j=b.length()-1;
boolean carry=false;
while(i>=0||j>=0){
if((i<0||a.charAt(i)=='0')&&(j<0||b.charAt(j)=='0')){
if(carry)sb.insert(0,'1');
else sb.insert(0,'0');
carry=false;
}else if(i>=0&&j>=0&&a.charAt(i)=='1'&&b.charAt(j)=='1'){
if(carry)sb.insert(0,'1');
else sb.insert(0,'0');
carry=true;
}else{
if(carry)sb.insert(0,'0');
else sb.insert(0,'1');
}
i--;j--;
}
if(carry)
sb.insert(0,'1');
return sb.toString();
}
}
Monthly Archives: April 2013
Leetcode: Minimum Window Substring
public class Solution {
public String minWindow(String S, String T) {
HashMap<Character,Integer>needToFind=new HashMap<Character,Integer>();
for(char c:T.toCharArray()){
if(needToFind.containsKey(c)){
needToFind.put(c,needToFind.get(c)+1);
}else{
needToFind.put(c,1);
}
}
int found=0;
int min=Integer.MAX_VALUE;
int rstart=0,rend=0;
HashMap<Character,Integer>foundMap=new HashMap<Character,Integer>();
int begin=0;
for(int end=0;end<S.length();end++){
char c=S.charAt(end);
if(!needToFind.containsKey(c))continue;
if(foundMap.containsKey(c)){
foundMap.put(c,foundMap.get(c)+1);
}else{
foundMap.put(c,1);
}
if(foundMap.get(c)<=needToFind.get(c))
found++;
if(found==T.length()){
c=S.charAt(begin);
while(!needToFind.containsKey(c)||
foundMap.get(c)>needToFind.get(c)){
if(needToFind.containsKey(c)){
foundMap.put(c,foundMap.get(c)-1);
}
begin++;
c=S.charAt(begin);
}
if(min>end-begin){
min=end-begin;
rstart=begin;
rend=end;
}
}
}
if(found==T.length())return S.substring(rstart,rend+1);
return "";
}
}
Leetcode: remove duplicates from sorted array II
public class Solution {
public int removeDuplicates(int[] A) {
if (A.length == 0) return 0;
int len = 1;
int dup = 1;
for(int i = 1; i < A.length; i++) {
if(A[i] != A[len - 1]) {
A[len++] = A[i];
dup=1;
// dup less than the max allow here, 1 mean no dup allow
} else if (dup<2) {
A[len++] = A[i];
dup ++;
}
}
return len;
}
}
Leetcode: Subsets II (also work with no dups)
public class Solution {
public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] S) {
// Sort first
Arrays.sort(S);
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
// create a boolean array to track progress
boolean[] b = new boolean[S.length];
while (true) {
// output a good subset
result.add(getR(b, S));
int i = 0;
while (i < S.length) {
if (b[i] == false) {
// if current position is false, just market it true and break;
b[i] = true;
break;
} else {
// see if next position has same character
int k=i+1;
while(k<S.length&&S[k]==S[i]&&b[k]==true){
k++;
}
if(k==S.length){
// reach the end, break;
i=k;
break;
}
if(S[k]==S[i]){
// found a dup character that has false, just mark it true and break;
b[k]=true;
break;
}else{
// all same dup is true, mark everything false and go on
while(i<k){
b[i] = false;
i++;
}
}
}
}
if (i == S.length)
break;
}
return result;
}
public ArrayList<Integer> getR(boolean[]b,int[]S) {
ArrayList<Integer> r=new ArrayList<Integer>();
for(int i=0;i<b.length;i++){
if(b[i])r.add(S[i]);
}
return r;
}
}
Leetcode: Scramble String
public class Solution {
public boolean isScramble(String s1, String s2) {
if(s1.length()!=s2.length())return false;
int x1=0,x2=0;
for(char c:s1.toCharArray()){
x1=x1^(int)c;
}
for(char c:s2.toCharArray()){
x2=x2^(int)c;
}
if(x1!=x2)return false;
if(s1.length()==1)return s1.equals(s2);
for(int i=1;i<s1.length();i++){
if((isScramble(s1.substring(0,i),s2.substring(0,i))&&
isScramble(s1.substring(i),s2.substring(i)))||
(isScramble(s1.substring(0,i),s2.substring(s2.length()-i))&&
isScramble(s1.substring(i),s2.substring(0,s2.length()-i))))
return true;
}
return false;
}
}
Leetcode: Search a 2D Matrix
不是最快的，但是很简单
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int i=matrix.length-1;
int j=0;
while(i>=0&&j<matrix[0].length){
if(matrix[i][j]>target)i--;
else if(target>matrix[i][j])j++;
else return true;
}
return false;
}
}
Leetcode Combinations
public class Solution {
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
return combine(1,n+1,k);
}
public ArrayList<ArrayList<Integer>> combine(int low,int upper, int k) {
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>> ();
if(k==1) {
for(int i=low;i<upper;i++){
ArrayList<Integer>r=new ArrayList<Integer>();
r.add(i);
result.add(r);
}
return result;
}
for(int i=low;i<upper;i++){
ArrayList<ArrayList<Integer>>r=combine(i+1,upper,k-1);
for(ArrayList<Integer> a:r){
a.add(0,i);
}
result.addAll(r);
}
return result;
}
}
Leetcode Permutations
Using linked list:
public class Solution {
public ArrayList<ArrayList<Integer>> permute(int[] num) {
// if need to be unique, sort it first
// Arrays.sort(num);
LinkedList<Integer>l=new LinkedList<Integer>();
for(int i:num){
l.add(i);
}
return permute(l);
}
public ArrayList<ArrayList<Integer>> permute(LinkedList<Integer>l) {
ArrayList<ArrayList<Integer>>result=new ArrayList<ArrayList<Integer>>();
if(l.size()==0)return result;
if(l.size()==1){
ArrayList<Integer> n=new ArrayList<Integer>();
n.add(l.get(0));
result.add(n);
return result;
}
for(int i=0;i<l.size();i++){
// create a new array without i
int current=l.get(i);
// if need to be unique, add following line:
// if(i>0&¤t==l.get(i-1))continue;
l.remove(i);
ArrayList<ArrayList<Integer>>tresult=permute(l);
for(ArrayList<Integer>rr:tresult){
rr.add(0,current);
}
result.addAll(tresult);
l.add(i,current);
}
return result;
}
}
Just use array:
public ArrayList<ArrayList<Integer>> permute(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList<Integer>>result=new ArrayList<ArrayList<Integer>>();
if(num.length==0)return result;
if(num.length==1){
ArrayList<Integer> n=new ArrayList<Integer>();
n.add(num[0]);
result.add(n);
return result;
}
for(int i=0;i<num.length;i++){
// create a new array without i
int[]newnum=new int[num.length-1];
int j=0;
while(j<newnum.length){
newnum[j]=num[j<i?j:j+1];
j++;
}
ArrayList<ArrayList<Integer>>tresult=permute(newnum);
for(ArrayList<Integer>rr:tresult){
rr.add(0,num[i]);
}
result.addAll(tresult);
}
return result;
}
LeetCode: Interleaving String
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length()+s2.length()!=s3.length())return false;
boolean[][]c=new boolean[s1.length()+1][s2.length()+1];
c[0][0]=true;
for(int i=0;i<s1.length();i++){
if(s1.charAt(i)==s3.charAt(i))
c[i+1][0]=true;
else break;
}
for(int i=0;i<s2.length();i++){
if(s2.charAt(i)==s3.charAt(i))
c[0][i+1]=true;
else break;
}
for(int i=1;i<s1.length()+1;i++){
for(int j=1;j<s2.length()+1;j++){
char c3=s3.charAt(i+j-1);
if(s1.charAt(i-1)==c3){
c[i][j]=c[i-1][j];
}
if(s2.charAt(j-1)==c3){
c[i][j]=c[i][j-1]||c[i][j];
}
}
}
return c[s1.length()][s2.length()];
}
}
Leetcode: Regular Expression Matching
public class Solution {
public boolean isMatch(String s, String p) {
//simple match
if(p.length()==0&&s.length()>0)return false;
if(p.length()==0&&s.length()==0)return true;
if(s.length()==0){
if(p.length()>1&&p.charAt(1)=='*')
return isMatch(s,p.substring(2));
else return false;
}
// p and s must has length great than 0 from here
if(p.length()==1){
if(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')
return isMatch(s.substring(1),p.substring(1));
else return false;
}else{
if(p.charAt(1)=='*'){
if(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')
return isMatch(s.substring(1),p.substring(0))||
isMatch(s.substring(0),p.substring(2));
else
return isMatch(s.substring(0),p.substring(2));
}else{
if(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')
return isMatch(s.substring(1),p.substring(1));
else return false;
}
}
}
}