Algorithm Ideas --under construction

Palindrome:

how to check?

Method 1:

two pointers, starting from head and tail, collapsing towards middle, keep checking if they are same until head>tail. if any one comparison is false, return false, other wise, true.

int h=0,t=s.length()
while(h<=t){
if(s.charAt(h)!=s.charAt(t)) return false; h++;t--; } return true;

Method 2: 

Dynamic Programing. This method actually marks out all palindromes, the index of 2d array is range of index positions in a string.

formula:

Define P[ i, j ] ← true iff the substring S i ... S j is a palindrome, otherwise false.

Therefore, P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )

The base cases are:
P[ i, i ] ← true
P[ i, i+1 ] ← ( Si = Si+1 )

for (int i = s.length() - 1; i >= 0; i--) {
   for (int j = i; j < s.length(); j++) {
    if (s.charAt(i) == s.charAt(j)
      && (j - i < 2 || range[i + 1][j - 1])) {
     range[i][j] = true;
    }
   }
  }

Iterative DFS with help of stack

I am so easily to remember the BFS with queue, but when it comes DFS, just intend to use recursive approach. Here is an example of in-order traversal with stack.

public class Solution {

    public int kthSmallest(TreeNode root, int k) {
        if(root.left==null && root.right==null)return root.val;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        int result=-1;
        while(!stack.isEmpty() || p!=null){
            if(p!=null){//not null, push to stack as in order root
                stack.push(p);
                p = p.left;//then access left
            }else{//when p is null, time to access root
                TreeNode t = stack.pop();//access root
                k--;
                if(k==0)
                    result = t.val;
                p = t.right;//and then access right child
            }
        
        }
        return result;
    }
}

kth Element in unsorted array

Intuitive thought:

sort the array, and pick the kth smallest or biggest element. O(nlgn) running time.

Many similar kth problem can be brute force resolved by this way.

More efficient way: QuickSelect

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)//this is length(A1)+1
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))//this is k-length(A1)-1
  else
    # it's equal to the pivot
    return pivot

Middle of Array

for array index starting with 0, instead of a.length/2, use (a.length-1)/2
good for finding right element for calculating median.

e.g. 0,1,2,3,4: (5-1)/2=2
eg. 0,1,2,3: (4-1)/2=1

Character existence

use an integer to set its corresponding bit to 1 to represent the existence of a letter.
bitCheck |=1<