Leetcode: Shuffle an Array

Shuffle a set of numbers without duplicates.

将每个数与其之后的随机一个数互换。
注意reset的时候要使用clone。

public class Solution {
    private int[] originals;
    private int[] current;
    public Solution(int[] nums) {
        this.originals = nums.clone();
        this.current = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        current = originals.clone();
        return current;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        Random random = new Random();
        for (int i = 0; i < current.length; i++) {
            int a = current[i];
            int nextIndex = i + random.nextInt(current.length-i);
            current[i] = current[nextIndex];
            current[nextIndex] = a;
        }
        return current;
    }
}

Leetcode: Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

简单题，利用binary search 找square root。

public class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 0) {
            return false;
        }
        if (num <= 1) {
            return true;
        }
        return binarySearch(num, 2, num/2);
    }
    
    private boolean binarySearch(int val, int start, int end) {
        if (start > end) {
            return false;
        }
        int mid = (start + end) / 2;
        if (val/mid == mid && val % mid == 0) {
            return true;
        }
        if (val/mid >= mid) {
            return binarySearch(val, mid + 1, end);
        } else {
            return binarySearch(val, start, mid - 1);
        }
    }
}

Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

通过4， 16， 64找规律，1. num是power of two， 即一个1之后所有位都是0， 2， 0的个数是偶数

public class Solution {
    public boolean isPowerOfFour(int num) {
        return (num & (num -1)) == 0 && (num & 0x55555555) > 0;
    }
}

Rotate Function

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).
观察一下规律不难发现f(n) = f(n-1) + arraySum – arrayLength*A[i-1]

public class Solution {
    public int maxRotateFunction(int[] A) {
        int oneRoundSum = 0;
        int max = 0;
        for (int i = 0; i <A> 0; i--) {
            int cur = prev + oneRoundSum - A.length * A[i];
            max = Math.max(max, cur);
            prev = cur;
        }
        return max;
    }
}

Leetcode: Rectangle Area

先算两个rectangle的面积，再减去重叠面积

public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int areaA = (C-A)*(D-B);
        int areaB = (G-E)*(H-F);
        int overLapWidth = 0;
        if (E <= C && G > A) {
            int leftBar = E < A ? A : E;
            int rightBar = G > C ? C : G;
            overLapWidth = rightBar-leftBar;
        }
        int overLapHeight = 0;
        if (F <= D && H > B) {
            int downBar = F < B ? B : F;
            int upBar = H > D ? D : H;
            overLapHeight = upBar - downBar;
        }
        return areaA -overLapHeight*overLapWidth + areaB; 
    }
}

Lintcode: Find Peak Element II

class Solution {
    public List<Integer> findPeakII(int[][] A) {
        List<Integer> res = new ArrayList<Integer>();
        if (A == null || A.length == 0 || A[0].length == 0) {
        	return res;
        }
        int i = 1, j = 1;
        while (true) {
    		if (isValid(A, i, j)) {
    			res.add(i);
    			res.add(j);
    			return res;
    		}
			if (A[i+1][j] > A[i][j+1]) {
				i++;
			} else {
				j++;
			}
        }
    }
    private boolean isValid(int[][] a, int i, int j) {
    	if (i > 0 && i < a.length - 1 && j > 0 && j < a[0].length - 1 
    		&& a[i-1][j] < a[i][j] && a[i+1][j] < a[i][j] && a[i][j+1] < a[i][j] && a[i][j+1] < a[i][j]) {
    		return true;
    	}
    	return false;
    }
}

Lintcode: Triangle Count

public class Solution {
    public int triangleCount(int S[]) {
        if (S == null || S.length <= 2) {
        	return 0;
        }
        Arrays.sort(S);
        int res = 0;
        for (int end = S.length - 1; end > 1; end--) {
        	int start = 0, mid = end - 1;
        	while (start < mid) {
        		if (S[start] + S[mid] <= S[end]) {
            			start++;
        		} else {
        			res += mid - start;//key point
        			mid--;
        		}
        	}
        }
        return res;
    }
}

Leetcode: Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

---

因为对于任何一位，只要m到n之间有任何数在这一位上等于0，那么此位的and结果就等于0.因此只有当m和n相等的时候才能保证中间的每一个数都相等。[m, n]范围的按位与的结果为m与n的公共“左边首部（left header）”

public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
    	int shifted = 0;
        while (m != n) {
        	m >>= 1;
        	n >>= 1;
        	shifted++;
        }
        return m << shifted;
    }
}

Leetcode: count primes

Count the number of prime numbers less than a non-negative number, n

---

本来用hashset来存从1到n得数再对其remove不是prime的数，但是超时了。在eclipse里面做了实验发现虽然hashset操作是O（1）复杂度，但是还是比操作array慢很多，因为要算hashcode。

public class Solution {
    public int countPrimes(int n) {
        boolean[] store = new boolean[n];
        for (int i = 2; i < n; i++) {
            store[i] = true;
        }
        for (int i = 2; i <= Math.sqrt(n-1); i++) {
            if (store[i] == true) {
                int times = (n - 1)/i;
                while (times > 1) {
                    store[i*times] = false;
                    times--;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (store[i] == true) {
                res++;
            }
        }
        return res;
    }
}

Lintcode: Binary representation

精确的解法应该是用BigDecimal，但是由于Lintcode里的解法是用Double，以下解法在输入为0.6418459415435791的时候和答案不一致。要像通过lintcode，需要将BigDecimal换成double，见Solution 2.

public String binaryRepresentation(String n) {
    	if (n == null || n.length() == 0) {
    		return n;
    	}
        String[] parts = n.split("\\.");
        StringBuilder sb = new StringBuilder();
        int first = Integer.parseInt(parts[0]);
        boolean isNeg = first < 0;
        if (first == Integer.MIN_VALUE) {
        	for (int i = 0; i < 32; i++) {
        		sb.append("1");
        	}
        } else {
        	first = Math.abs(first);
        	while (first != 0) {
        		sb.insert(0, first & 1);
        		first >>= 1;
        	}
        }
        if (sb.length() == 0) {
            sb.append("0");
        }
        //handle the decimal part
        if (parts.length == 2 && Long.parseLong(parts[1]) != 0) {
        	sb.append(".");
        	BigDecimal value = new BigDecimal("0." + parts[1]);
        	Set<BigDecimal> store = new HashSet<BigDecimal>();
        	while (value.compareTo(BigDecimal.ZERO) > 0) {
        		if (sb.substring(sb.indexOf(".") +1).length() > 32 || store.contains(value))  {
        			return "ERROR";
        		}
        		store.add(value);
        		System.out.println(value);
        		if (value.compareTo(new BigDecimal(0.5)) >= 0) {
        			sb.append("1");
        			value = value.multiply(BigDecimal.valueOf(2)).subtract(BigDecimal.ONE);
        		} else {
        			sb.append("0");
        			value = value.multiply(BigDecimal.valueOf(2));
        		}
        	}
        }
        if (isNeg == true) {
        	sb.insert(0, "-");
        }
        return sb.toString();
    }

Solution 2: 其实是错误的，但是lintcode只接受这个答案

import java.math.BigDecimal;
public class Solution {
    /**
     *@param n: Given a decimal number that is passed in as a string
     *@return: A string
     */
    public String binaryRepresentation(String n) {
    	if (n == null || n.length() == 0) {
    		return n;
    	}
        String[] parts = n.split("\\.");
        StringBuilder sb = new StringBuilder();
        int first = Integer.parseInt(parts[0]);
        boolean isNeg = first < 0;
        if (first == Integer.MIN_VALUE) {
        	for (int i = 0; i < 32; i++) {
        		sb.append("1");
        	}
        } else {
        	first = Math.abs(first);
        	while (first != 0) {
        		sb.insert(0, first & 1);
        		first >>= 1;
        	}
        }
        if (sb.length() == 0) {
            sb.append("0");
        }
        //handle the decimal part
        if (parts.length == 2 && Long.parseLong(parts[1]) != 0) {
        	sb.append(".");
        	BigDecimal value = new BigDecimal("0." + parts[1]);
        	double v2 = Double.parseDouble("0." + parts[1]);
        	Set<BigDecimal> store = new HashSet<BigDecimal>();
        	Set<Double> store2 = new HashSet<>();
        	//while (value.compareTo(BigDecimal.ZERO) > 0) {
        	while (v2 > 0) {
        		//if (sb.substring(sb.indexOf(".") +1).length() > 32 || store.contains(value)) {
        		if (sb.substring(sb.indexOf(".") +1).length() > 32 || store2.contains(v2)) {
        			return "ERROR";
        		}
        		store.add(value);
        		store2.add(v2);
        		//System.out.println(value);
        		//System.out.println("double: " + v2);
        		//if (value.compareTo(new BigDecimal(0.5)) >= 0) {
        		if (v2 >= 0.5) {
        			sb.append("1");
        			//value = value.multiply(BigDecimal.valueOf(2)).subtract(BigDecimal.ONE);
        			v2 = v2 * 2 - 1;
        		} else {
        			sb.append("0");
        			//value = value.multiply(BigDecimal.valueOf(2));
        			v2 = v2*2;
        		}
        	}
        }
        if (isNeg == true) {
        	sb.insert(0, "-");
        }
        return sb.toString();
    }
}