public class Solution {
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int total=(C-A)*(D-B)+(G-E)*(H-F);
return total-getIntersect(A,C,E,G)*getIntersect(B,D,F,H);
}
public int getIntersect(int x1,int x2, int x3, int x4){
if(x2<x3||x1>x4)return 0;
return Math.abs(Math.max(x1,x3)-Math.min(x2,x4));
}
}
Author Archives: shawn
Summary Ranges
public class Solution {
public List<String> summaryRanges(int[] nums) {
int i=0;
List<String> result=new ArrayList<String>();
while(i<nums.length){
int start =nums[i];
int end=nums[i];
while(i<nums.length-1&&nums[i]+1==nums[i+1]){
end++;
i++;
}
if(start==end){
result.add(start+"");
}else{
result.add(start+"->"+end);
}
i++;
}
return result;
}
}
Remove Duplicates from Sorted List II
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
int c;
ListNode newhead=head;
ListNode last=head;
boolean needMoveHead=true;
while(head!=null&&head.next!=null){
c=0;
while(head.next!=null&&head.val==head.next.val){
c++;
head=head.next;
}
if(c>=1){
// need to cut it
if(needMoveHead){
// it's the first element, move the new head
newhead=head.next;
}
// cut it
last.next=head.next;
}else{
// doesn't need to cut it. No need to move new head now
needMoveHead=false;
last=head;
}
head=head.next;
}
return newhead;
}
}
Pocket Mine 5 hidden achievement
Let’s Do This – 20 pts (Hidden)
Shuffle 3 mythical cards in one shuffle
Dream Run – 20 pts (Hidden)
Shuffle 3 5-stars cards in one shuffle
Treasure Hunter – 15 pts (Hidden)
Get 3 treasure-related powerups in one shuffle
Gold Digger – 15 pts (Hidden)
Get 3 gold-related powerups in one shuffle
Is This Real Life!? (Hidden)
Shuffle 3 mythical 5-stars cards in one shuffle
Leetcode: Add Binary
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();
}
}
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;
}
}