class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            if(a[0] != b[0]) return a[0] - b[0];
            else return a[1] - b[1];
        });
        int st = -1,ed = -1;
        List<Integer[]> res = new ArrayList<>();
        for(int i = 0;i < intervals.length;i++){
            if(ed < intervals[i][0]){
                //找到一个新的区间
                if(ed != -1) res.add(new Integer[]{st,ed});
                st = intervals[i][0];
                ed = intervals[i][1];
            }
            // 有交集
            else ed = Math.max(ed,intervals[i][1]);
        }
        if(ed != -1) res.add(new Integer[]{st,ed});
        int [][] ans = new int[res.size()][2];
        int i = 0;
        for(Integer[] a : res){
            ans[i][0] = a[0];
            ans[i++][1] = a[1];
        }
        return ans;     
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        // L 和 R 分别表示左右两侧的乘积列表
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];
        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }
        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }
        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }
        return answer;
    }
}