java中的一些经典算法code

// 1. 
import java.util.LinkedList;
import java.util.Queue;

public class CandyGame {
    // 定义一个点的类，用于记录位置和当前累计的糖果数量
    static class Point {
        int x, y, steps, candies;

        Point(int x, int y, int steps, int candies) {
            this.x = x;
            this.y = y;
            this.steps = steps;
            this.candies = candies;
        }
    }

    // 主方法，返回妈妈在最短时间内最多能拿到的糖果数量
    public static int maxCandies(int[][] grid, int[] mom, int[] baby) {
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(mom[0], mom[1], 0, grid[mom[0]][mom[1]]));
        visited[mom[0]][mom[1]] = true;

        int maxCandies = 0;
        int minSteps = Integer.MAX_VALUE;

        while (!queue.isEmpty()) {
            Point current = queue.poll();

            if (current.x == baby[0] && current.y == baby[1]) {
                if (current.steps < minSteps) {
                    minSteps = current.steps;
                    maxCandies = current.candies;
                } else if (current.steps == minSteps) {
                    maxCandies = Math.max(maxCandies, current.candies);
                }
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] != -1) {
                    visited[nx][ny] = true;
                    queue.add(new Point(nx, ny, current.steps + 1, current.candies + grid[nx][ny]));
                }
            }
        }

        return maxCandies;
    }

    // 测试方法
    public static void main(String[] args) {
        int[][] grid = {
                {1, 0, 2},
                {0, -1, 3},
                {4, 0, 5}
        };
        int[] mom = {0, 0};
        int[] baby = {2, 2};
        System.out.println(maxCandies(grid, mom, baby));  // 输出7
    }
}

// 2.
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class MaxMinSum {

    public static int maxMinSum(int[] nums, int N) {
        // 去重
        Set<Integer> uniqueNumsSet = new HashSet<>();
        for (int num : nums) {
            uniqueNumsSet.add(num);
        }
        Integer[] uniqueNums = uniqueNumsSet.toArray(new Integer[0]);

        // 检查输入是否合法
        if (uniqueNums.length < 2 * N) {
            return -1;
        }

        // 排序
        Arrays.sort(uniqueNums);

        // 计算最小N个数的和
        int minSum = 0;
        for (int i = 0; i < N; i++) {
            minSum += uniqueNums[i];
        }

        // 计算最大N个数的和
        int maxSum = 0;
        for (int i = uniqueNums.length - 1; i >= uniqueNums.length - N; i--) {
            maxSum += uniqueNums[i];
        }

        // 检查是否有重叠
        if (uniqueNums[N - 1] >= uniqueNums[uniqueNums.length - N]) {
            return -1;
        }

        // 返回总和
        return minSum + maxSum;
    }

    // 测试方法
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int N = 3;
        System.out.println(maxMinSum(nums, N));  // 输出36

        int[] nums2 = {1, 2, 3, 4, 5, 5, 4, 3, 2, 1};
        int N2 = 2;
        System.out.println(maxMinSum(nums2, N2));  // 输出16

        int[] nums3 = {1, 2, 3, 4, 5, 6};
        int N3 = 3;
        System.out.println(maxMinSum(nums3, N3));  // 输出-1 (因为数组长度不足2*N)
    }
}

//3 
public class LongestValidSubstring {
    
    public static int findLongestValidSubstring(String s) {
        int maxLength = -1;  // 初始化为-1，如果找不到满足条件的子串就返回-1
        int n = s.length();
        
        // 遍历字符串
        for (int i = 0; i < n; i++) {
            if (Character.isLetter(s.charAt(i))) { // 确认当前字符是字母
                int left = i - 1;
                int right = i + 1;
                int count = 1; // 当前子串包含的字母数
                int length = 1; // 当前子串的长度
                
                // 向左扩展
                while (left >= 0 && Character.isDigit(s.charAt(left))) {
                    length++;
                    left--;
                }
                
                // 向右扩展
                while (right < n && Character.isDigit(s.charAt(right))) {
                    length++;
                    right++;
                }
                
                // 更新最大长度
                maxLength = Math.max(maxLength, length);
            }
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        String s1 = "abc123d4567";
        System.out.println(findLongestValidSubstring(s1));  // 输出5, 因为最长子串是 "123d4"

        String s2 = "a1b2c3d4";
        System.out.println(findLongestValidSubstring(s2));  // 输出3, 因为最长子串是 "1b2" 或 "2c3" 或 "3d4"

        String s3 = "123456";
        System.out.println(findLongestValidSubstring(s3));  // 输出-1, 因为没有字母

        String s4 = "abcdef";
        System.out.println(findLongestValidSubstring(s4));  // 输出-1, 因为没有数字

        String s5 = "a123b456c";
        System.out.println(findLongestValidSubstring(s5));  // 输出4, 因为最长子串是 "a123" 或 "b456"
    }
}

//4
import java.util.TreeSet;

public class SocialDistanceSeating {

    // 树集合用于记录已占用的座位
    private TreeSet<Integer> occupied;

    public SocialDistanceSeating() {
        occupied = new TreeSet<>();
    }

    // 员工进入会议室，找到最佳座位
    public int enter(int n) {
        if (occupied.isEmpty()) {
            occupied.add(0);
            return 0;
        }

        int bestSeat = -1;
        int maxDistance = -1;

        // 检查第一个位置
        if (!occupied.contains(0)) {
            int first = occupied.first();
            if (first != 0) {
                int distance = first;
                if (distance > maxDistance) {
                    bestSeat = 0;
                    maxDistance = distance;
                }
            }
        }

        // 检查中间位置
        Integer prev = null;
        for (Integer current : occupied) {
            if (prev != null) {
                int distance = (current - prev) / 2;
                int candidate = prev + distance;
                if (distance > maxDistance || (distance == maxDistance && candidate < bestSeat)) {
                    bestSeat = candidate;
                    maxDistance = distance;
                }
            }
            prev = current;
        }

        // 检查最后一个位置
        if (!occupied.contains(n - 1)) {
            int last = occupied.last();
            if (last != n - 1) {
                int distance = (n - 1) - last;
                if (distance > maxDistance) {
                    bestSeat = n - 1;
                    maxDistance = distance;
                }
            }
        }

        occupied.add(bestSeat);
        return bestSeat;
    }

    // 员工离开会议室
    public void leave(int seat) {
        occupied.remove(seat);
    }

    public static void main(String[] args) {
        SocialDistanceSeating sds = new SocialDistanceSeating();
        int n = 10; // 假设有10个座位
        System.out.println(sds.enter(n)); // 输出 0
        System.out.println(sds.enter(n)); // 输出 9
        System.out.println(sds.enter(n)); // 输出 4
        System.out.println(sds.enter(n)); // 输出 2
        sds.leave(4);
        System.out.println(sds.enter(n)); // 输出 4
    }
}

//5
import java.util.Arrays;

public class MaximizeGreaterElements {
    private int maxCount = 0;
    private int optimalPermutations = 0;

    // 主方法，返回所有可以达到最优结果的a数组数量
    public int countOptimalPermutations(int[] a, int[] b) {
        maxCount = 0;
        optimalPermutations = 0;
        permute(a, b, 0);
        return optimalPermutations;
    }

    // 生成a的所有排列并计算满足条件的数量
    private void permute(int[] a, int[] b, int start) {
        if (start == a.length) {
            int count = countGreaterThan(a, b);
            if (count > maxCount) {
                maxCount = count;
                optimalPermutations = 1;
            } else if (count == maxCount) {
                optimalPermutations++;
            }
            return;
        }

        for (int i = start; i < a.length; i++) {
            swap(a, start, i);
            permute(a, b, start + 1);
            swap(a, start, i);
        }
    }

    // 计算a中有多少个元素大于b中的对应元素
    private int countGreaterThan(int[] a, int[] b) {
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > b[i]) {
                count++;
            }
        }
        return count;
    }

    // 交换数组中的两个元素
    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        MaximizeGreaterElements solver = new MaximizeGreaterElements();
        int[] a = {3, 1, 4, 2};
        int[] b = {2, 4, 1, 3};
        System.out.println(solver.countOptimalPermutations(a, b)); // 输出3
    }
}

//6
public class MountainPeaks {
    public static int countMountainPeaks(int[] heights) {
        int n = heights.length;
        if (n == 0) {
            return 0;
        }

        int peakCount = 0;

        // 遍历每一个位置，检查是否为山峰
        for (int i = 0; i < n; i++) {
            if (isPeak(heights, i)) {
                peakCount++;
            }
        }

        return peakCount;
    }

    // 判断一个位置是否为山峰
    private static boolean isPeak(int[] heights, int i) {
        int n = heights.length;
        if (i > 0 && i < n - 1) { // 中间位置
            return heights[i] > heights[i - 1] && heights[i] > heights[i + 1];
        } else if (i == 0) { // 边界位置
            return n > 1 && heights[i] > heights[i + 1];
        } else { // 边界位置
            return n > 1 && heights[i] > heights[i - 1];
        }
    }

    public static void main(String[] args) {
        int[] heights = {0, 1, 2, 4, 3, 1, 0, 0, 1, 2, 3, 1, 2, 1, 0};
        int peakCount = countMountainPeaks(heights);
        System.out.println("Number of mountain peaks: " + peakCount); // 输出 2
    }
}

//7
import java.util.*;

public class MountainClimbing {
    public static void main(String[] args) {
        int[] heights = {0, 1, 4, 3, 1, 0, 0, 1, 2, 3, 1, 2, 1, 0};
        System.out.println(evaluateMountains(heights)); // 输出 2
    }

    // 寻找所有山峰的索引
    private static List<Integer> findPeaks(int[] heights) {
        List<Integer> peaks = new ArrayList<>();
        int n = heights.length;
        for (int i = 1; i < n - 1; i++) {
            if (heights[i] > heights[i - 1] && heights[i] > heights[i + 1]) {
                peaks.add(i);
            }
        }
        return peaks;
    }

    // 计算从起点到山峰的体力消耗
    private static int calculateEnergy(int[] heights, int start, int peak) {
        int energy = 0;
        int current = start;

        // 上山
        while (current < peak) {
            if (heights[current] < heights[current + 1]) {
                energy += 2 * (heights[current + 1] - heights[current]);
            } else if (heights[current] > heights[current + 1]) {
                energy += heights[current] - heights[current + 1];
            }
            current++;
        }

        // 下山
        while (current > start) {
            if (heights[current] > heights[current - 1]) {
                energy += 2 * (heights[current] - heights[current - 1]);
            } else if (heights[current] < heights[current - 1]) {
                energy += heights[current - 1] - heights[current];
            }
            current--;
        }

        return energy;
    }

    // 评估可以安全返回的山峰数量
    private static int evaluateMountains(int[] heights) {
        List<Integer> peaks = findPeaks(heights);
        List<Integer> groundPositions = new ArrayList<>();
        for (int i = 0; i < heights.length; i++) {
            if (heights[i] == 0) {
                groundPositions.add(i);
            }
        }

        int safePeaks = 0;
        int maxEnergy = 999;

        for (int peak : peaks) {
            boolean canSafelyClimb = false;
            for (int ground : groundPositions) {
                int energy = calculateEnergy(heights, ground, peak);
                if (energy <= maxEnergy) {
                    canSafelyClimb = true;
                    break;
                }
            }

            if (canSafelyClimb) {
                safePeaks += 1;
            }
        }

        return safePeaks;
    }
}


//9
public class SubsequenceChecker {
    public static void main(String[] args) {
        String S = "ace";
        String L = "abcde";
        System.out.println(isSubsequence(S, L)); // 输出 true
    }

    public static boolean isSubsequence(String S, String L) {
        int sLen = S.length();
        int lLen = L.length();
        
        // 初始化指针
        int i = 0, j = 0;
        
        // 遍历字符串 L
        while (i < sLen && j < lLen) {
            if (S.charAt(i) == L.charAt(j)) {
                i++;
            }
            j++;
        }
        
        // 如果 i 到达 S 的末尾，表示 S 是 L 的有效子序列
        return i == sLen;
    }
}

//10
public class MooncakeDistribution {
    public static void main(String[] args) {
        int m = 3; // 员工人数
        int n = 10; // 月饼数量
        System.out.println(countWays(m, n));
    }

    public static int countWays(int m, int n) {
        // dp[i][j] 表示前 i 个员工分配 j 个月饼的方案数
        int[][] dp = new int[m + 1][n + 1];

        // 初始化，dp[0][0] = 1 表示前0个员工分配0个月饼的方法数为1
        dp[0][0] = 1;

        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = i; j <= n; j++) {
                for (int k = 1; k <= j; k++) {
                    if (j - k >= (i - 1)) {
                        dp[i][j] += dp[i - 1][j - k];
                    }
                }
            }
        }

        // 返回前 m 个员工分配 n 个月饼的方案数
        return dp[m][n];
    }
}

//11
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
public class BinaryTree {
    public static TreeNode constructNewTree(TreeNode root) {
        if (root == null) return null;

        // 计算左子树和右子树的和
        int leftSum = sumSubtree(root.left);
        int rightSum = sumSubtree(root.right);

        // 创建新的根节点，其值为左子树和 + 右子树和
        TreeNode newRoot = new TreeNode(leftSum + rightSum);

        // 递归构建左子树和右子树
        newRoot.left = constructNewTree(root.left);
        newRoot.right = constructNewTree(root.right);

        return newRoot;
    }

    // 计算子树和的方法
    private static int sumSubtree(TreeNode node) {
        if (node == null) return 0;
        return node.val + sumSubtree(node.left) + sumSubtree(node.right);
    }

    // 主方法用于测试
    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(7);
        root.right = new TreeNode(9);
        root.left.right = new TreeNode(-2);
        root.right.left = new TreeNode(6);

        TreeNode newRoot = constructNewTree(root);
        printTree(newRoot);
    }

    // 打印二叉树的方法（层次遍历）
    private static void printTree(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
}



//12
public class CircularString {
    public static void main(String[] args) {
        String s = "loxolox";
        System.out.println(longestEvenCountSubstring(s));
    }

    public static int longestEvenCountSubstring(String s) {
        int n = s.length();
        String doubled = s + s;
        int maxLength = 0;

        // 用来记录当前窗口中每个字符的计数
        int[] count = new int[3]; // 0 -> 'l', 1 -> 'o', 2 -> 'x'

        for (int i = 0; i < n; i++) {
            count = new int[3];
            for (int j = i; j < i + n; j++) {
                char c = doubled.charAt(j);
                if (c == 'l') count[0]++;
                else if (c == 'o') count[1]++;
                else if (c == 'x') count[2]++;

                if (isEven(count)) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }

        return maxLength;
    }

    private static boolean isEven(int[] count) {
        for (int c : count) {
            if (c % 2 != 0) return false;
        }
        return true;
    }
}

oh, it's too long, so, next paragraph:

//1
public class CircularString {
    public static void main(String[] args) {
        String s = "oxoxooxx";
        System.out.println(longestEvenOSubstring(s));
    }

    public static int longestEvenOSubstring(String s) {
        int n = s.length();
        String doubled = s + s; // 首尾相连模拟环形字符串
        int maxLength = 0;
        int countO = 0;

        // 使用滑动窗口技术
        for (int i = 0; i < n; i++) {
            countO = 0;
            for (int j = i; j < i + n; j++) {
                if (doubled.charAt(j) == 'o') {
                    countO++;
                }
                if (countO % 2 == 0) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }

        return maxLength;
    }
}

//2
public class SmallestStringTransform {
    public static void main(String[] args) {
        String s = "cbad";
        System.out.println(getSmallestString(s)); // 应输出 "bacd"
    }

    public static String getSmallestString(String s) {
        char[] chars = s.toCharArray();
        int n = s.length();

        // 最小字符及其索引数组
        char[] minChars = new char[n];
        int[] minIndices = new int[n];
        minChars[n - 1] = chars[n - 1];
        minIndices[n - 1] = n - 1;

        // 从后向前构建最小字符及其索引数组
        for (int i = n - 2; i >= 0; i--) {
            if (chars[i] <= minChars[i + 1]) {
                minChars[i] = chars[i];
                minIndices[i] = i;
            } else {
                minChars[i] = minChars[i + 1];
                minIndices[i] = minIndices[i + 1];
            }
        }

        // 查找需要交换的字符
        for (int i = 0; i < n; i++) {
            if (chars[i] > minChars[i + 1]) {
                // 交换
                char temp = chars[i];
                chars[i] = chars[minIndices[i + 1]];
                chars[minIndices[i + 1]] = temp;
                break;
            }
        }

        return new String(chars);
    }
}

//3
public class GreedyMonkey {
    public static void main(String[] args) {
        int[] numbers = {4, 5, 1, 2, 3, 10, 6};
        int N = 3;
        System.out.println(maxBananas(numbers, N)); // 应输出 18
    }

    public static int maxBananas(int[] numbers, int N) {
        int n = numbers.length;
        
        // 边界情况
        if (N >= n) {
            int sum = 0;
            for (int num : numbers) {
                sum += num;
            }
            return sum;
        }

        // 计算从头取 k 个的前缀和
        int[] prefixSum = new int[N + 1];
        for (int i = 0; i < N; i++) {
            prefixSum[i + 1] = prefixSum[i] + numbers[i];
        }

        // 计算从尾取 k 个的后缀和
        int[] suffixSum = new int[N + 1];
        for (int i = 0; i < N; i++) {
            suffixSum[i + 1] = suffixSum[i] + numbers[n - 1 - i];
        }

        // 计算最大香蕉数
        int maxBananas = 0;
        for (int k = 0; k <= N; k++) {
            int currentBananas = prefixSum[k] + suffixSum[N - k];
            maxBananas = Math.max(maxBananas, currentBananas);
        }

        return maxBananas;
    }
}

//4
public class FindNextNumber {
    public static void main(String[] args) {
        int n = 78; // example input
        System.out.println(findNextNumber(n)); // output should be 83
    }

    public static int findNextNumber(int n) {
        // Step 1: Find rightmost 0 and set it to 1
        int rightOne = n & -n;
        int nextHigherOneBit = n + rightOne;

        // Step 2: Calculate right bits pattern
        int rightBits = n ^ nextHigherOneBit;
        rightBits = (rightBits / rightOne) >> 2;

        // Step 3: Combine to get the next number with same number of 1s
        return nextHigherOneBit | rightBits;
    }
}

// 5
import java.util.Stack;

public class MarsMath {
    public static void main(String[] args) {
        String expression = "3#4$2#1"; // Example expression
        System.out.println(evaluate(expression)); // Expected output
    }

    public static int evaluate(String expression) {
        Stack<Integer> values = new Stack<>();
        Stack<Character> operators = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);

            if (Character.isDigit(c)) {
                int num = 0;
                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
                    num = num * 10 + (expression.charAt(i) - '0');
                    i++;
                }
                i--; // Correct the position after inner loop
                values.push(num);
            } else if (c == '#' || c == '$') {
                while (!operators.isEmpty() && precedence(operators.peek()) >= precedence(c)) {
                    values.push(applyOp(operators.pop(), values.pop(), values.pop()));
                }
                operators.push(c);
            }
        }

        while (!operators.isEmpty()) {
            values.push(applyOp(operators.pop(), values.pop(), values.pop()));
        }

        return values.pop();
    }

    public static int precedence(char op) {
        if (op == '#') {
            return 2;
        } else if (op == '$') {
            return 1;
        }
        return 0;
    }

    public static int applyOp(char op, int b, int a) {
        switch (op) {
            case '#':
                return 4 * a + 3 * b + 2;
            case '$':
                return 2 * a + b + 3;
        }
        return 0;
    }
}

//6
import java.util.ArrayList;
import java.util.List;

public class ContinuousSum {

    public static void main(String[] args) {
        int N = 15;
        List<List<Integer>> result = findContinuousSequences(N);
        System.out.println("Number of ways: " + result.size());
        for (List<Integer> sequence : result) {
            System.out.println(sequence);
        }
    }

    public static List<List<Integer>> findContinuousSequences(int N) {
        List<List<Integer>> result = new ArrayList<>();
        int start = 1, end = 2;

        while (start < end) {
            int sum = (end - start + 1) * (start + end) / 2;

            if (sum < N) {
                end++;
            } else if (sum > N) {
                start++;
            } else {
                List<Integer> sequence = new ArrayList<>();
                for (int i = start; i <= end; i++) {
                    sequence.add(i);
                }
                result.add(sequence);
                start++;
            }
        }

        return result;
    }
}

//7
import java.util.ArrayList;
import java.util.List;

class MemoryBlock {
    int start;
    int size;
    boolean isAllocated;

    public MemoryBlock(int start, int size, boolean isAllocated) {
        this.start = start;
        this.size = size;
        this.isAllocated = isAllocated;
    }
}

public class MemoryAllocator {
    private static final int TOTAL_SIZE = 100;
    private List<MemoryBlock> memoryBlocks;

    public MemoryAllocator() {
        memoryBlocks = new ArrayList<>();
        memoryBlocks.add(new MemoryBlock(0, TOTAL_SIZE, false)); // Initialize with one big free block
    }

    public int allocate(int size) {
        MemoryBlock bestFit = null;
        for (MemoryBlock block : memoryBlocks) {
            if (!block.isAllocated && block.size >= size) {
                if (bestFit == null || block.size < bestFit.size) {
                    bestFit = block;
                }
            }
        }

        if (bestFit == null) {
            return -1; // No suitable block found
        }

        int allocatedStart = bestFit.start;
        if (bestFit.size == size) {
            bestFit.isAllocated = true;
        } else {
            memoryBlocks.add(memoryBlocks.indexOf(bestFit) + 1, new MemoryBlock(bestFit.start + size, bestFit.size - size, false));
            bestFit.size = size;
            bestFit.isAllocated = true;
        }

        return allocatedStart;
    }

    public void free(int start) {
        MemoryBlock blockToFree = null;
        for (MemoryBlock block : memoryBlocks) {
            if (block.start == start && block.isAllocated) {
                blockToFree = block;
                break;
            }
        }

        if (blockToFree == null) {
            throw new IllegalArgumentException("Invalid start address or block is already free");
        }

        blockToFree.isAllocated = false;
        mergeFreeBlocks();
    }

    private void mergeFreeBlocks() {
        List<MemoryBlock> mergedBlocks = new ArrayList<>();
        for (int i = 0; i < memoryBlocks.size(); i++) {
            MemoryBlock current = memoryBlocks.get(i);
            if (!current.isAllocated && i < memoryBlocks.size() - 1) {
                MemoryBlock next = memoryBlocks.get(i + 1);
                if (!next.isAllocated) {
                    current.size += next.size;
                    i++;
                }
            }
            mergedBlocks.add(current);
        }
        memoryBlocks = mergedBlocks;
    }

    public void printMemoryBlocks() {
        for (MemoryBlock block : memoryBlocks) {
            System.out.println("Start: " + block.start + ", Size: " + block.size + ", Allocated: " + block.isAllocated);
        }
    }

    public static void main(String[] args) {
        MemoryAllocator allocator = new MemoryAllocator();

        // Allocate memory
        int addr1 = allocator.allocate(10);
        System.out.println("Allocated at: " + addr1);
        allocator.printMemoryBlocks();

        int addr2 = allocator.allocate(20);
        System.out.println("Allocated at: " + addr2);
        allocator.printMemoryBlocks();

        // Free memory
        allocator.free(addr1);
        System.out.println("Freed memory at: " + addr1);
        allocator.printMemoryBlocks();

        // Allocate memory again
        int addr3 = allocator.allocate(15);
        System.out.println("Allocated at: " + addr3);
        allocator.printMemoryBlocks();
    }
}

//8
import java.util.*;

public class TrafficLightPath {
    
    public static int calcTime(int[][] lights, int timePerRoad, int rowStart, int colStart, int rowEnd, int colEnd) {
        int n = lights.length;
        int m = lights[0].length;
        
        // 优先队列存储待处理的节点
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.time));
        pq.add(new Node(rowStart, colStart, 0));
        
        // 路径时间数组
        int[][] times = new int[n][m];
        for (int[] row : times) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        times[rowStart][colStart] = 0;
        
        // 方向数组，上下左右
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            
            // 如果已到达终点，返回时间
            if (current.row == rowEnd && current.col == colEnd) {
                return current.time;
            }
            
            // 遍历四个方向
            for (int[] dir : directions) {
                int newRow = current.row + dir[0];
                int newCol = current.col + dir[1];
                
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m) {
                    int newTime = current.time + timePerRoad;
                    
                    // 计算等待时间
                    if (lights[newRow][newCol] != 0) { // 右转无需等待
                        int waitTime = (lights[newRow][newCol] - (newTime % lights[newRow][newCol])) % lights[newRow][newCol];
                        newTime += waitTime;
                    }
                    
                    if (newTime < times[newRow][newCol]) {
                        times[newRow][newCol] = newTime;
                        pq.add(new Node(newRow, newCol, newTime));
                    }
                }
            }
        }
        
        return -1; // 不可能到达终点
    }
    
    static class Node {
        int row;
        int col;
        int time;
        
        Node(int row, int col, int time) {
            this.row = row;
            this.col = col;
            this.time = time;
        }
    }
    
    public static void main(String[] args) {
        int[][] lights = {
            {30, 30, 30},
            {30, 30, 30},
            {30, 30, 30}
        };
        int timePerRoad = 10;
        int rowStart = 0, colStart = 0, rowEnd = 2, colEnd = 2;
        
        int result = calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd);
        System.out.println("The shortest time is: " + result);
    }
}

//9
import java.util.*;

public class JumpGame {
    public static int sumOfLeft(int[] nums, int jump, int left) {
        int n = nums.length;
        if (left >= n) {
            // 如果left大于或等于数组长度，无需跳数，直接返回所有元素之和
            return Arrays.stream(nums).sum();
        }

        LinkedList<Integer> list = new LinkedList<>();
        for (int num : nums) {
            list.add(num);
        }

        int currentIndex = 0;
        while (list.size() > left) {
            // 计算下一次跳到的位置
            currentIndex = (currentIndex + jump) % list.size();
            list.remove(currentIndex);
        }

        // 计算剩余元素的总和
        int sum = 0;
        for (int num : list) {
            sum += num;
        }

        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int jump = 2;
        int left = 3;

        int result = sumOfLeft(nums, jump, left);
        System.out.println("The sum of left numbers is: " + result);  // 输出: The sum of left numbers is: 18
    }
}

//10
import java.util.*;

public class DirectoryManager {

    private static Deque<String> pathStack = new ArrayDeque<>();

    public static void main(String[] args) {
        // 初始目录为根目录
        pathStack.push("/");

        // 输入命令序列
        String[] commands = {
            "mkdir abc", 
            "cd abc", 
            "mkdir def", 
            "cd def", 
            "pwd", 
            "cd ..", 
            "pwd", 
            "cd ..", 
            "pwd", 
            "cd xyz", // Invalid command
            "cd ..", // Invalid command since we're already at root
            "pwd"
        };

        // 处理命令并输出最后一条命令的结果
        for (String command : commands) {
            processCommand(command);
        }
    }

    public static void processCommand(String command) {
        String[] parts = command.split(" ");
        String cmd = parts[0];

        switch (cmd) {
            case "mkdir":
                if (parts.length == 2) {
                    mkdir(parts[1]);
                }
                break;
            case "cd":
                if (parts.length == 2) {
                    cd(parts[1]);
                }
                break;
            case "pwd":
                pwd();
                break;
            default:
                // Invalid command, do nothing
                break;
        }
    }

    private static void mkdir(String dirName) {
        // 当前目录路径
        String currentPath = getCurrentPath();
        // 检查当前路径下是否存在同名目录
        if (!currentPath.endsWith("/")) {
            currentPath += "/";
        }
        currentPath += dirName;

        // 如果该目录不存在，则创建
        if (!pathStack.contains(currentPath)) {
            pathStack.push(currentPath);
        }
    }

    private static void cd(String dirName) {
        if (dirName.equals("..")) {
            // 返回上一级目录
            if (pathStack.size() > 1) {
                pathStack.pop();
            }
        } else {
            // 进入指定目录
            String currentPath = getCurrentPath();
            if (!currentPath.endsWith("/")) {
                currentPath += "/";
            }
            currentPath += dirName;

            // 如果该目录存在，则进入
            if (pathStack.contains(currentPath)) {
                pathStack.push(currentPath);
            }
        }
    }

    private static void pwd() {
        System.out.println(getCurrentPath());
    }

    private static String getCurrentPath() {
        StringBuilder currentPath = new StringBuilder();
        for (String dir : pathStack) {
            if (!dir.equals("/")) {
                currentPath.append("/").append(dir);
            }
        }
        return currentPath.length() == 0 ? "/" : currentPath.toString();
    }
}