shz117

public class WordDictionary {
    private class DicNode {
        boolean contains;
        Map<Character, DicNode> children;
        
        DicNode() {
            contains = false;
            children = new HashMap<>();
        }
    }

shz117

    public int rob(int[] m) {
        if (m == null || m.length == 0) return 0;
        if (m.length == 1) return m[0];
        int include_max = 0, include_last = m[0], include_prev = 0, exclude_max = 0, exclude_last = 0, exclude_prev = 0;
        for (int i = 1; i < m.length; i++) {
            include_max = Math.max(i == m.length -1 ? 0:(include_prev + m[i]), include_last);
            include_prev = include_last;
            include_last = include_max;
            
            exclude_max = Math.max(exclude_prev + m[i], exclude_last);

shz117

/*
  kmp like method.
  1. build string  s + "#" + (reversed s)
  2. generate array of length of common prefix and suffix (like building next[] in kmp)
  3. append (reversed s).substring(0, length - next[-1] - 1)) in front of s   (Note: next[-1] - 1 is the length of max length on common prefix suffix at last position)
*/

public String shortestPalindrome(String s) {
        if (s == null || s.length() == 0) return "";
        String rev = new StringBuilder(s).reverse().toString();

shz117

public int mySqrt(int x) {
        if (x == 0) return 0;
        double last = 0;
        double cur = 1;
        while (cur != last) {
            last = cur;
            cur = ( last + x / last ) / 2;
        }
        return (int) cur;
    }

shz117

public class Solution {
    public int largestRectangleArea(int[] height) {
        Stack<Integer> st = new Stack<>();
        int maxArea = 0;
        for (int i = 0; i <= height.length; i++) {
            int h = i == height.length ? 0 : height[i];
            if (st.isEmpty() || h >= height[st.peek()])
                st.push(i);
            else {
                int top = height[st.pop()];

shz117

public class Solution {
    public class Course {
        boolean done;
        boolean visiting;
        List<Course> pre;
        public Course() {
            done = false;
            visiting = false;
            pre = new ArrayList<>();
        }

shz117

// O(n)
public class Solution {
    /*
        [2,3,1,2,4,3] and s = 7
          4 3
    */
    public int minSubArrayLen(int s, int[] nums) {
        if (s < 0 || nums == null || nums.length == 0)
            return 0;
        int start = 0, end = 0, sum = 0, res = 0;

shz117

#include <cstdio>
#include <cstdlib>
#include <cstring>

#define ENTRYNOTFOUND 0
#define ENTRYFOUND 1
#define NOTCOMPLETE 2

struct Trie;
void FindWords(Trie *root);

shz117

/*
  Level 1: 序列123...N，N介于3和9之间，在其中加入+、-或者空格，使其和为0。如123456  1-2 3-4 5+6 7 等价于1-23-45+67=0。请问，如何获得所有组合？ 
*/

import java.util.ArrayList;

/* we use :
0 : space
1 : +
2 : -

shz117

public long[] products(long[] a){
  	if (a==null || a.length == 0 || a.length == 1) return a;
		long[] ret = new long[a.length];
		long product = 1;
		int zeros = 0;
		int zeropos = 0;
		for (int i = 0; i<a.length;i++){
			if (a[i] == 0){
				zeros++;
				zeropos = i;