zhousilverbullet / dailyalgorithms Goto Github PK

class Solution {
    public int[] sortedSquares(int[] A) {
        int len = A.length;
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            int value = A[i] * A[i];
            int j = i;
            int temp = value;
            while (j - 1 >= 0 && ans[j - 1] > value) {
                ans[j] = ans[j-1]; 
                j--; 
            }
            ans[j] = temp;
        }
        return ans;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow && fast != null) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            if (size == 1) {
                queue.get(0).next = null;
            } else {
                for (int i = 0; i < size; i++) {
                    if (i == size - 1) {
                        queue.get(i).next = null;
                    } else {
                        queue.get(i).next = queue.get(i + 1);     
                    }      
                }
            }
            while(size > 0) {
                Node node = queue.removeFirst();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                size--;
            }
        }
        return root;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow && fast != null) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

class Solution {
    int maxValue = 0;

    public int getMinimumDifference(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        tranvsal(root, list);
        int min = Integer.MAX_VALUE;
        int maxIndex = 0;
        
        for (int i = 0; i < list.size(); i++) {
            int value = list.get(i);
            for (int j = 0; j < list.size(); j++) {
                if(i != j) {
                    min = Math.min(min, Math.abs(value - list.get(j)));
                }
            }
        }
        return min;
    }

    private void tranvsal(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }

        maxValue = Math.max(root.val, maxValue);
        
        list.add(root.val);
        if (root.left != null) {
            tranvsal(root.left, list);
        }
        if (root.right != null) {
            tranvsal(root.right, list);
        }
    }
}

class Solution {
    int pre = 0;
    int min = 0;

    public int getMinimumDifference(TreeNode root) {
        pre = -1;
        min = Integer.MAX_VALUE;
        tranvsal(root);
        
        return min;
    }

    private void tranvsal(TreeNode root) {
        if (root == null) {
            return;
        }
        
        
        if (root.left != null) {
            tranvsal(root.left);
        }

        if (pre == -1) {
            pre = root.val;
        } else {
            //这里不用abs，需要自己再想想为什么
            min = Math.min(min, root.val - pre);
            pre = root.val;
        }

        if (root.right != null) {
            tranvsal(root.right);
        }
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode(0);
        ListNode temp = dummyNode;
        temp.next = head;
        while (temp != null && temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;

            temp = node1;
        }
        
        return dummyNode.next;
    }
}

class Solution {
    public Node connect(Node root) {
        if(root == null) {
            return null;
        }
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.push(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size > 0) {
                Node node = queue.removeLast();
                if(node.left != null) {
                    queue.addFirst(node.left);
                }
                if(node.right != null) {
                    queue.addFirst(node.right);
                }
                if(size > 1) {
                    node.next = queue.peekLast();
                }
                size--;
            }
        }
        return root;
    }
}