class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null)
            return new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        List<Integer> ans = new ArrayList<>();
        while (!q.isEmpty()) {
            int length = q.size();
            TreeNode rightMostNode = q.peek();
            ans.add(rightMostNode.val);
            for (int i = 0; i < length; i++) {
                TreeNode currentNode = q.poll();
                if (currentNode.right != null)
                    q.offer(currentNode.right);
                if (currentNode.left != null)
                    q.offer(currentNode.left);
            }
        }
        return ans;
    }
}

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[dp.length - 1];
    }
}

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int mask = 1, ans = 0;
        while (n != 0) {
            ans += 1;
            n = n & (n - 1);
        }
        return ans;
    }
}

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int mask = 1, ans = 0;
        for (int i = 0; i < 32; i++) {
            ans <<= 1;
            if ((mask & n) != 0)
                ans |= 1;
            mask <<= 1;
        }
        return ans;
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int realK = k % nums.length;
        if (realK == 0)
            return;
        int[] temp = new int[realK];
        for (int i = nums.length - 1, j = temp.length - 1; j >= 0; i--, j--) {
            temp[j] = nums[i];
        }
        int left = nums.length - realK - 1, right = nums.length - 1;
        while (left >= 0) {
            nums[right] = nums[left];
            right -= 1;
            left -= 1;
        }
        while (right >= 0) {
            nums[right] = temp[right];
            right -= 1;
        }
    }
}

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int left = 0, right = 0, firstCount = 0, secondCount = 0, max = 0;
        Character first = null, second = null;
        while (right < s.length()) {
            // 1. Move right pointer
            while (right < s.length()) {
                if (first == null || s.charAt(right) == first) {
                    first = s.charAt(right);
                    firstCount += 1;
                } else if (second == null || s.charAt(right) == second) {
                    second = s.charAt(right);
                    secondCount += 1;
                } else {
                    break;
                }
                right += 1;
            }
            // 2. Check the length
            int currLength = right - left;
            max = Math.max(max, currLength);

            // 3. Move left pointer
            while (firstCount != 0 && secondCount != 0) {
                if (s.charAt(left) == first) {
                    firstCount -= 1;
                } else {
                    secondCount -= 1;
                }
                left += 1;
            }
            if (firstCount == 0) {
                first = null;
                firstCount = 0;
            } else {
                second = null;
                secondCount = 0;
            }
        }
        return max;
    }

}

class Solution {
    public int maxProduct(int[] nums) {
        int min = nums[0], max = nums[0], ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int tempMax = max, tempMin = min;
            max = Math.max(nums[i], Math.max(nums[i] * tempMax, nums[i] * tempMin));
            min = Math.min(nums[i], Math.min(nums[i] * tempMax, nums[i] * tempMin));
            ans = Math.max(ans, max);
        }
        return ans;
    }
}

class LRUCache {
    static class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    Node head, tail;
    Map<Integer, Node> map;
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.prev = null;
        head.next = tail;
        tail.prev = head;
        tail.next = null;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node targetNode = map.get(key);
            moveToHead(targetNode);
            return targetNode.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node targetNode = map.get(key);
            targetNode.value = value;
            moveToHead(targetNode);
        } else {
            Node newNode = new Node(key, value);
            if (map.size() == capacity) {
                map.remove(tail.prev.key);
                popTail();
            }
            map.put(key, newNode);
            addToHead(newNode);
        }
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = null;
        node.next = null;
    }

    private void addToHead(Node node) {
        head.next.prev = node;
        node.next = head.next;
        node.prev = head;
        head.next = node;
    }

    private void moveToHead(Node node) {
        remove(node);
        addToHead(node);
    }

    private void popTail() {
        remove(tail.prev);
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<ListNode>();

        ListNode node = head;
        while (node != null) {
            if (visited.contains(node)) {
                return node;
            }
            visited.add(node);
            node = node.next;
        }

        return null;
    }
}

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet<>(wordDict);
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[s.length()];
        boolean[] added = new boolean[s.length() + 1];
        queue.add(0);
        while (!queue.isEmpty()) {
            int start = queue.remove();
            if (visited[start]) {
                continue;
            }
            for (int end = start + 1; end <= s.length(); end++) {
                if (wordDictSet.contains(s.substring(start, end))) {
                    queue.add(end);
                    if (end == s.length()) {
                        return true;
                    }
                }
            }
            visited[start] = true;
        }
        return false;
    }
}