cangoal

//
public int trap(int[] height) {
        if(height == null || height.length <= 2) return 0;
        int left = 0, right = height.length - 1, sum = 0, h = 0;
        while(left < right){
            if(height[left] <= height[right]){
                if(height[left] < h){
                    sum += h - height[left];
                }
                h = Math.max(h, height[left]);

cangoal

// use hashmap
public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return head;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode cur = head;
        while(cur != null){
            RandomListNode newNode = new RandomListNode(cur.label);
            map.put(cur, newNode);
            cur = cur.next;
        }

cangoal

// backtracking : time limit exceeded
public boolean wordBreak(String s, Set<String> wordDict) {
        if(s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) return false;
        return helper(0, s, wordDict);
    }
    
    public boolean helper(int p, String s, Set<String> wordDict){
        if(p == s.length()) return true;
        
        for(int i=p+1; i<=s.length(); i++){

cangoal

public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode runner = head;
        ListNode walker = head;
        
        while(runner.next != null && runner.next.next != null){
            runner = runner.next.next;
            walker = walker.next;
            if(runner == walker){
                return true;

cangoal

//
public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) return null;
        ListNode runner = head;
        ListNode walker = head;
        while(runner.next != null && runner.next.next != null){
            runner = runner.next.next;
            walker = walker.next;
            if(runner == walker) break;
        }

cangoal

//
public int evalRPN(String[] tokens) {
        if(tokens == null || tokens.length == 0) return 0;
        Stack<String> stack = new Stack<String>();
        for(int i=0; i<tokens.length; i++){
            String s = tokens[i];
            int value1 = 0, value2 = 0, ret = 0;
            switch(s){
                case "+":
                    value1 = Integer.parseInt(stack.pop());

cangoal

//
public int findMin(int[] nums) {
        if(nums == null || nums.length==0) return -1;
        int left = 0, right = nums.length - 1;
        while(left <= right){
            if(nums[left] <= nums[right]) return nums[left];
            int mid = (left + right) / 2;
            if(nums[mid] <= nums[right]){
                right = mid;
            } else {

cangoal

//
public int findMin(int[] nums) {
        if(nums == null || nums.length==0) return -1;
        int left = 0, right = nums.length - 1;
        while(left <= right){
            while(left < right && nums[left] == nums[right]) left++;
            if(nums[left] <= nums[right]) return nums[left];
            int mid = (left + right) / 2;
            if(nums[mid] <= nums[right]){
                right = mid;

cangoal

//
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode h1 = headA, h2 = headB;
        while(headA != null && headB != null){
            if(headA == headB) return headA;
            headA = headA.next;
            headB = headB.next;
            if(headA == null && headB == null) return null;
            if(headA == null) headA = h2;

cangoal

public int findPeakElement(int[] nums) {
        if(nums==null || nums.length==0) return -1;
        if(nums.length == 1) return 0;
        for(int i=0; i < nums.length; i++){
            if(i==0 && nums[i] > nums[i+1] || i==nums.length-1 && nums[i] > nums[i-1]) return i;
            if(nums[i] > nums[i+1] && nums[i] > nums[i-1]) return i;
        }
        return -1;
    }
//