public class Singleton {
    // volatile保证可见性和禁止指令重排
    private static volatile Singleton instance;
    
    public static Singleton getInstance() {
        if (instance == null) {  // 第一次检查 不加锁直接读，效率高
            synchronized (Singleton.class) {  // 加锁后再次检查，避免多个线程同时创建实例
                if (instance == null) {  // 第二次检查
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

public boolean canJump(int[] nums) {
    if(nums.length ==1) return true;
    int coverRange = 0;
    for(int i=0; i<=coverRange; i++){ // 遍历coverRange，因为coverRange是当前可以跳跃的最大距离，所以遍历coverRange即可
        coverRange = Math.max(coverRange, i+nums[i]); // 站在第i个位置，最多可以跳nums[i]步
        if(coverRange >= nums.length-1) return true; // 如果coverRange >= nums.length-1（最后一个索引位置），则可以到达最后一个位置 
    }
    return false;
}

public boolean isPalindrome(String s) {
    if (" ".equals(s)) return true; // 如果字符串为空，则返回true 
    int left = 0, right = s.length()-1;
    while(left <= right){
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { // 如果左指针指向的字符不是字母或数字，则移动左指针
            left++;
        }
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { // 如果右指针指向的字符不是字母或数字，则移动右指针
            right--;
        }
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) { // 如果左右指针指向的字符不相同，则返回false
            return false;
        }
        left++; // 移动左指针
        right--; // 移动右指针
    }
    return true;
}

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>(); // 使用哈希表来存储已经遍历过的元素及其索引
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i]; // 计算目标值与当前元素的差值
        if (map.containsKey(complement)) { // 说明之前遍历过的某个数和当前数加起来正好等于target，直接返回这两个数的索引
            return new int[] { map.get(complement), i }; // 返回这两个数的索引
        }
        map.put(nums[i], i); // 将当前元素及其索引添加到哈希表中
    }
    return new int[] { -1, -1 };
}

// 递归
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}
private void inorder(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    inorder(root.left, result);
    result.add(root.val);
    inorder(root.right, result);
}
// 迭代
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // 一直往左走，把所有左子节点入栈
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // 弹出栈顶元素（最左的节点）
        current = stack.pop();
        result.add(current.val);
        
        // 处理右子树
        current = current.right;
    }
    
    return result;
}
// 前序迭代
public List<Integer> preorderIter(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return res;
}
// 后序迭代
public List<Integer> postorderIterOneStack(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    TreeNode lastVisited = null;
    
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        TreeNode peekNode = stack.peek();
        if (peekNode.right != null && lastVisited != peekNode.right) {
            curr = peekNode.right;
        } else {
            res.add(peekNode.val);
            lastVisited = stack.pop();
        }
    }
    return res;
}