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);
        }
    }
}

Lintcode: Count of Smaller Number

Solution 1: binary search

public class Solution {
    public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
        Arrays.sort(A);
        ArrayList<Integer> res = new ArrayList<Integer>();
        for (int q : queries) {
            res.add(binarySearch(A, q));
        }
        return res;
    }
    private int binarySearch(int[] A, int val) {
        int start = 0, end = A.length - 1;
        int res = 0;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (A[mid] >= val) {
                end = mid - 1;
            } else {
                res = mid + 1;
                start = mid + 1;
            }
        }
        return res;
    }
}

Solution 2: Segment tree

public class Solution {
    public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (A == null || queries == null || queries.length == 0) {
            return res;
        }
        Arrays.sort(A);
        MaxNode root = buildTree(A, 0, A.length - 1);
        
        for (int q : queries) {
            res.add(query(A, root, q));
        }
        return res;
    }
    private MaxNode buildTree(int[] A, int start, int end) {
        if (start > end) {
            return null;
        }
        MaxNode root = new MaxNode(start, end);
        if (start == end) {
            root.val = A[start];
        } else {
            root.left = buildTree(A, start, (start+end)/2);
            root.right = buildTree(A, (start+end)/2+1, end);
            root.val = root.left == null ? root.right.val : Math.max(root.left.val,
                root.right == null ? 0 : root.right.val);
        }
        return root;
    }
    private int query(int[] A, MaxNode root, int val) {
        if (root == null || A[root.start] > val) {
            return 0;
        }
        if (root.val < val) {
            return root.end - root.start + 1;
        }
        return query(A, root.left, val) + query(A, root.right, val);
    }
    class MaxNode {
        int start;
        int end;
        int val; //how many nodes are between the range start - end (inclusive)
        MaxNode left;
        MaxNode right;
        public MaxNode() {
            
        }
        public MaxNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
        public MaxNode(int start, int end, int val) {
            this(start, end);
            this.val = val;
        }
    }
}

Leetcode & Lintcode : Minimum Size Subarray Sum

Solution 1:
two pointers.当当前sum已经满足条件后，将start往后移至不满足条件的index为止，再更新结果。复杂度O(n)。

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = -1;
        int sum = 0;
        int start = 0;
        for (int end = 0; end < nums.length; end++) {
            sum += nums[end];
            if (sum >= s) {
                if (start == end) {
                    res = 1;
                    break;
                }
                while (start < end && sum - nums[start] >= s) {
                    sum -= nums[start];
                    start++;
                }
                res = res == -1 ? end - start + 1 : Math.min(res, end - start + 1);
            }
        }
        return res == -1 ? 0 : res;
    }
}

Solution 2: 用O(n log n)复杂度。todo

Leetcode: Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

---

public class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return Integer.MAX_VALUE;
        }
        
        boolean neg = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        long result = 0;
        while (a >= b) {
            long tmp = 0;
            long b2 = b;
            while (b2 <= a) {
                tmp = tmp == 0 ? 1 : tmp << 1;
                b2 = b2 << 1;
            }
            b2 = b2 >> 1;
            a = a - b2;
            result += tmp;
        }
        if (result >= Integer.MAX_VALUE) {
            result = neg == true? Integer.MIN_VALUE: Integer.MAX_VALUE;
        } else if (neg == true) {
            result = -result;
        }
        return (int)result;
    }
}

Median of Two Sorted Arrays

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))

---

最重要的是要理解为什么每次只能discard 1/4 of the two arrays in total.

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        if ((A.length + B.length) % 2 == 1) {
          return sub(A, 0, A.length - 1, B, 0, B.length - 1, (A.length + B.length)/2 + 1);
        } else {
          double r1 = sub(A, 0, A.length - 1, B, 0, B.length - 1, (A.length + B.length)/2);
          double r2 = sub(A, 0, A.length - 1, B, 0, B.length - 1, (A.length + B.length)/2 + 1);
          return (r1 + r2) / 2;
        }
    }
    private double sub(int[] a, int al, int ar, int[] b, int bl, int br, int order) {
          if (al > ar && bl > br) {
            return 0;
          }
          if (al > ar || bl > br) {
            return al > ar ? b[bl + order-1] : a[al + order-1];
          }
          int mida = (al + ar) / 2;
          int midb = (bl + br) / 2;
          if (a[mida] > b[midb]) {
            if (order >= mida - al + midb - bl + 2) {
              return sub(a, al, ar, b, midb+1, br, order - (midb - bl + 1));
            } else {
              return sub(a, al, mida - 1, b, bl, br, order);
            }
          } else {
            if (order >= mida - al + midb - bl + 2) {
              return sub(a, mida+1, ar, b, bl, br, order - (mida - al + 1));
            } else {
              return sub(a, al, ar, b, bl, midb - 1, order);
            }
          }
        }
}

Lintcode: 183 Wood Cut

Given n pieces of wood with length L[i] (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.
典型的binary search

public class Solution {
    public int woodCut(int[] L, int k) {
        int start = 0, end = 0;
        for (int len : L) {
          if (len > end) {
            end = len;
          }
        }
        int res = 0;
        while (start <= end) {
          int mid = (int)(((long)start + (long)end) / 2);
          if (mid <= 0) {
        	  return 0;
          }
          int count = 0;
          for (int i = 0; i = k) {
            start = mid + 1;
            res = Math.max(res, mid);
          } else {
            end = mid - 1;
          }
        }
        return res;
    }
}

Codility 12.1 MinMaxDivision

Some content on this page was disabled on November 21, 2022 as a result of a DMCA takedown notice from Alicja Zielińska. You can learn more about the DMCA here:

https://wordpress.com/support/copyright-and-the-dmca/

Codility 12.2 NailingPlanks

Some content on this page was disabled on November 21, 2022 as a result of a DMCA takedown notice from Alicja Zielińska. You can learn more about the DMCA here:

https://wordpress.com/support/copyright-and-the-dmca/

11.5 Interspersed string array

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.

public int findString(String[] strs, String target) {
	int start = 0, end = strs.length - 1;
	while (start <= end) {
		int mid = (start + end) / 2;
		if (strs[mid].equals(target)) {
			return mid;
		}
		if (strs[mid].isEmpty()) {
			boolean hasNonEmpty = false;
			for (int i = mid - 1; i >= 0; i--) {
				if (!strs[i].isEmpty()) {
					if (strs[i].compareTo(target) < 0) {
						start = mid + 1;
					} else {
						end = i;
					}
					hasNonEmpty = true;
					break;
				}
			}
			if (hasNonEmpty == false) {
				start = mid + 1;
			}
		} else if (strs[mid].compareTo(target) < 0) {
			start = mid + 1;
		} else if (strs[mid].compareTo(target) > 0) {
			end = mid - 1;
		}
	}
	return -1;
}

To test:

String[] strs = new String[]{"at", "","","", "ball", "","", "car", "","", "dad", "",""};
System.err.println("index : " + scc.findString(strs, "dad"));

9.3 Magic Index

A magic index in an arrayA[l…n-l]is defined to be an index such thatA[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.

---

public int findMagicIndex(int[] num) {
	int start = 0, end = num.length - 1;
	while (start <= end) {
		int mid = (start + end) / 2;
		if (num[mid] == mid) {
			return mid;
		}
		if (num[mid] > mid) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return -1;
}

FOLLOW UP
What if the values are not distinct?
当有重复的时候，两边都要比，但是不用比所有的元素，比较巧妙。

public int findMagicIndex(int[] num) {
	return subFind(num, 0, num.length - 1);
}

private int subFind(int[] num, int start, int end) {
	int result = -1;
	if (start > end) {
		return -1;
	}
	int mid = (start + end) / 2;
	if (num[mid] == mid) {
		return mid;
	}
	if (num[mid] > mid) {
		result = subFind(num, start, mid - 1) == -1 ? result = subFind(num, num[mid], end);
	} else {
		result = subFind(num, mid + 1, end) == -1 ? subFind(num, start, num[mid]);
	}
	return result;
}